ShCtrlGraph.hpp

// Sh: A GPU metaprogramming language.
//
// Copyright (c) 2003 University of Waterloo Computer Graphics Laboratory
// Project administrator: Michael D. McCool
// Authors: Zheng Qin, Stefanus Du Toit, Kevin Moule, Tiberiu S. Popa,
//          Michael D. McCool
// 
// This software is provided 'as-is', without any express or implied
// warranty. In no event will the authors be held liable for any damages
// arising from the use of this software.
// 
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it
// freely, subject to the following restrictions:
// 
// 1. The origin of this software must not be misrepresented; you must
// not claim that you wrote the original software. If you use this
// software in a product, an acknowledgment in the product documentation
// would be appreciated but is not required.
// 
// 2. Altered source versions must be plainly marked as such, and must
// not be misrepresented as being the original software.
// 
// 3. This notice may not be removed or altered from any source
// distribution.
#ifndef SHCTRLGRAPH_HPP
#define SHCTRLGRAPH_HPP

#include <vector>
#include <list>
#include <iosfwd>
#include "ShDllExport.hpp"
#include "ShRefCount.hpp"
#include "ShBasicBlock.hpp"
#include "ShVariable.hpp"
#include "ShBlock.hpp"

namespace SH {

class ShCtrlGraphNode;

struct
SH_DLLEXPORT ShCtrlGraphBranch {
  ShCtrlGraphBranch(const ShPointer<ShCtrlGraphNode>& node,
                    ShVariable cond);
  
  ShPointer<ShCtrlGraphNode> node; 
  ShVariable cond; 
};

class
SH_DLLEXPORT ShCtrlGraphNode : public ShRefCountable {
public:
  ShCtrlGraphNode();
  ~ShCtrlGraphNode();

  ShBasicBlockPtr block;
  typedef std::vector<ShCtrlGraphBranch> SuccessorList;
  SuccessorList successors; 
  ShPointer<ShCtrlGraphNode> follower; 

  typedef std::list<ShCtrlGraphNode*> ShPredList;
  ShPredList predecessors;

  std::ostream& print(std::ostream& out, int indent) const;

  std::ostream& graphvizDump(std::ostream& out) const;

  void append(const ShPointer<ShCtrlGraphNode>& node);

  void append(const ShPointer<ShCtrlGraphNode>& node,
              ShVariable cond);

  ShPointer<ShCtrlGraphNode> 
  split(ShBasicBlock::ShStmtList::iterator stmt);

  bool marked() const;
  
  // Technically these should not be const. But they're useful in
  // functions which are const, so we just make the "marked" flag
  // mutable.
  void mark() const; 
  void clearMarked() const; 

  
  template<typename F>
  void dfs(F& functor);

  template<typename F>
  void dfs(F& functor) const;

private:
  template<typename F>
  void real_dfs(F& functor);

  template<typename F>
  void real_dfs(F& functor) const;

  mutable bool m_marked;
};

typedef ShPointer<ShCtrlGraphNode> ShCtrlGraphNodePtr;
typedef ShPointer<const ShCtrlGraphNode> ShCtrlGraphNodeCPtr;

class
SH_DLLEXPORT ShCtrlGraph : public ShRefCountable {
public:
  ShCtrlGraph(ShCtrlGraphNodePtr head, ShCtrlGraphNodePtr tail);
  ShCtrlGraph(ShBlockListPtr blocks);
  ~ShCtrlGraph();

  std::ostream& print(std::ostream& out, int indent) const;
  
  std::ostream& graphvizDump(std::ostream& out) const;

  ShCtrlGraphNodePtr entry() const;
  ShCtrlGraphNodePtr exit() const;

  // New entry is marked (so it does not prevent clearMarking on future DFSes)
  ShCtrlGraphNodePtr prependEntry();

  ShCtrlGraphNodePtr appendExit();

  template<typename F>
  void dfs(F& functor);
  
  template<typename F>
  void dfs(F& functor) const;
  
  void computePredecessors();

  // Make a copy of this control graph placing the result into head and tail.
  void copy(ShCtrlGraphNodePtr& head, ShCtrlGraphNodePtr& tail) const;
  
private:
  ShCtrlGraphNodePtr m_entry;
  ShCtrlGraphNodePtr m_exit;

  //  void parse(ShCtrlGraphNodePtr& tail, ShBlockListPtr blocks);
};

typedef ShPointer<ShCtrlGraph> ShCtrlGraphPtr;
typedef ShPointer<const ShCtrlGraph> ShCtrlGraphCPtr;

template<typename F>
void ShCtrlGraphNode::real_dfs(F& functor)
{
  if (this == 0) return;
  if (m_marked) return;
  mark();
  functor(this);
  for (std::vector<ShCtrlGraphBranch>::iterator I = successors.begin(); I != successors.end(); ++I) {
    I->node->real_dfs(functor);
  }
  if (follower) follower->real_dfs(functor);
}

template<typename F>
void ShCtrlGraphNode::real_dfs(F& functor) const
{
  if (this == 0) return;
  if (m_marked) return;
  mark();
  functor(this);
  for (std::vector<ShCtrlGraphBranch>::const_iterator I = successors.begin();
       I != successors.end(); ++I) {
    I->node->real_dfs(functor);
  }
  if (follower) follower->real_dfs(functor);
}

template<typename F>
void ShCtrlGraphNode::dfs(F& functor)
{
  clearMarked();
  real_dfs(functor);
  clearMarked();
}

template<typename F>
void ShCtrlGraphNode::dfs(F& functor) const
{
  clearMarked();
  real_dfs(functor);
  clearMarked();
}

template<typename F>
void ShCtrlGraph::dfs(F& functor)
{
  m_entry->dfs(functor);
}

template<typename F>
void ShCtrlGraph::dfs(F& functor) const
{
  m_entry->dfs(functor);
}

}

#endif

---