ShCtrlGraph.hpp

// Sh: A GPU metaprogramming language.
//
// Copyright 2003-2006 Serious Hack Inc.
// 
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 
// MA  02110-1301, USA
#ifndef SHCTRLGRAPH_HPP
#define SHCTRLGRAPH_HPP

#include <set>
#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 ShInfoHolder {
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);

  typedef std::set<ShVariableNodePtr> DeclSet;
  typedef DeclSet::const_iterator DeclIt;

  void addDecl(const ShVariableNodePtr& node);

  bool hasDecl(const ShVariableNodePtr& node) const;

  void insert_decls(DeclIt f, DeclIt l);

  DeclIt decl_begin() const;
  DeclIt decl_end() const;


  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;

  DeclSet m_decls; 
};

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

class
SH_DLLEXPORT ShCtrlGraph : public ShRefCountable {
public:
  ShCtrlGraph(const ShCtrlGraphNodePtr& head, const ShCtrlGraphNodePtr& tail);
  ShCtrlGraph(const 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();

  void prepend(ShPointer<ShCtrlGraph> cfg); 

  void append(ShPointer<ShCtrlGraph> cfg); 


  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

---