44 template <
typename GraphT>
class WTO;
46 template <
typename GraphT>
class WTONode;
48 template <
typename GraphT>
class WTOCycle;
50 template <
typename GraphT>
class WTOComponentVisitor;
53 template <
typename T,
typename =
void>
struct has_nodetype : std::false_type
62 template <
typename T,
typename =
void>
struct has_edgetype : std::false_type
105 "GraphT must have a nested type named 'NodeType'");
106 typedef typename GraphT::NodeType
NodeT;
112 typedef typename NodeRefList::const_iterator
Iterator;
158 for (
auto this_it =
begin(), other_it = other.
begin();
159 this_it !=
end() && other_it != other.
end(); ++this_it, ++other_it)
161 if (*this_it == *other_it)
182 auto this_it =
begin();
183 auto other_it = other.
begin();
184 while (this_it !=
end())
186 if (other_it == other.
end())
190 else if (*this_it == *other_it)
200 if (other_it == other.
end())
240 std::stringstream rawstr(str);
242 for (
auto it =
begin(), et =
end(); it != et;)
244 rawstr << (*it)->toString();
330 "GraphT must have a nested type named 'NodeType'");
331 typedef typename GraphT::NodeType
NodeT;
359 return std::to_string(
_node->getId());
384 "GraphT must have a nested type named 'NodeType'");
385 typedef typename GraphT::NodeType
NodeT;
394 typedef typename WTOComponentRefList::const_iterator
Iterator;
458 std::stringstream rawstr(str);
460 rawstr <<
_head->getICFGNode()->getId() <<
", ";
461 for (
auto it =
begin(), et =
end(); it != et;)
463 rawstr << (*it)->toString();
516 template <typename GraphT> class
WTO
521 "GraphT must have a nested type named 'NodeType'");
523 "GraphT must have a nested type named 'EdgeType'");
524 typedef typename GraphT::NodeType
NodeT;
525 typedef typename GraphT::EdgeType
EdgeT;
541 typedef std::vector<const NodeT*>
Stack;
547 typedef typename WTOComponentRefList::const_iterator
Iterator;
563 explicit WTO(GraphT* graph,
const NodeT* entry) : _num(0), _graph(graph), _entry(entry)
582 for (
const auto& component : _allComponents)
597 return _components.cbegin();
603 return _components.cend();
608 return headRefToCycle.find(node) != headRefToCycle.end();
611 typename NodeRefToWTOCycleMap::const_iterator
headBegin()
const
613 return headRefToCycle.cbegin();
617 typename NodeRefToWTOCycleMap::const_iterator
headEnd()
const
619 return headRefToCycle.cend();
625 auto it = _nodeToDepth.find(
n);
626 assert(it != _nodeToDepth.end() &&
"node not found");
627 return *(it->second);
633 auto it = _nodeToDepth.find(
n);
634 return it != _nodeToDepth.end();
640 for (
const auto& c : _components)
650 std::stringstream rawstr(str);
652 for (
auto it = begin(), et = end(); it != et;)
654 rawstr << (*it)->toString();
676 visit(_entry, _components);
695 _nodeToWTOCycleDepth(nodeToWTOCycleDepth)
701 const NodeT* head = cycle.
head()->getICFGNode();
703 _nodeToWTOCycleDepth.insert(std::make_pair(head, _wtoCycleDepth));
705 std::make_shared<GraphTWTOCycleDepth>(*_wtoCycleDepth);
706 _wtoCycleDepth->add(head);
707 for (
auto it = cycle.
begin(), et = cycle.
end(); it != et; ++it)
709 (*it)->accept(*
this);
711 _wtoCycleDepth = previous_cycleDepth;
716 _nodeToWTOCycleDepth.insert(
717 std::make_pair(node.
getICFGNode(), _wtoCycleDepth));
726 for (
const auto& e : node->getOutEdges())
728 func(e->getDstNode());
736 auto it = _nodeToCDN.find(
n);
737 if (it != _nodeToCDN.end())
750 auto res = _nodeToCDN.insert(std::make_pair(
n, dfn));
753 (res.first)->second = dfn;
760 assert(!_stack.empty() &&
"empty stack");
761 const NodeT* top = _stack.back();
775 _allComponents.insert(ptr);
783 _allComponents.insert(ptr);
791 forEachSuccessor(node, [&](
const NodeT* succ)
793 if (getCDN(succ) == 0)
795 visit(succ, partition);
798 const WTONodeT* head = newNode(node);
799 const WTOCycleT* ptr = newCycle(head, partition);
800 headRefToCycle.emplace(node, ptr);
819 forEachSuccessor(node, [&](
const NodeT* succ)
824 min =
visit(succ, partition);
837 if (head == getCDN(node))
839 setCDN(node, UINT_MAX);
840 const NodeT* element = pop();
843 while (element != node)
848 partition.push_front(component(node));
852 partition.push_front(newNode(node));
862 for (
auto it = begin(), et = end(); it != et; ++it)
864 (*it)->accept(builder);
virtual void visit(const WTONodeT &)=0
Visit the given node.
WTOComponentVisitor(WTOComponentVisitor &&) noexcept=default
Move constructor.
WTOComponentVisitor(const WTOComponentVisitor &) noexcept=default
Copy constructor.
WTOComponentVisitor()=default
Default constructor.
WTONode< GraphT > WTONodeT
WTOCycle< GraphT > WTOCycleT
virtual std::string toString() const =0
virtual void accept(WTOComponentVisitor< GraphT > &) const =0
Accept the given visitor.
WTOComponent(WTOCT k)
Default constructor.
WTOComponent(const WTOComponent &) noexcept=default
Copy constructor.
friend std::ostream & operator<<(std::ostream &o, const WTOComponent< GraphT > &wto)
Overloading operator << for dumping ICFG node ID.
WTOComponent(WTOComponent &&) noexcept=default
Move constructor.
Iterator begin() const
Begin iterator over the head of cycles.
bool operator>=(const WTOCycleDepth &other) const
~WTOCycleDepth()=default
Destructor.
Iterator end() const
End iterator over the head of cycles.
std::string toString() const
Dump the cycleDepth, for debugging purpose.
bool operator<=(const WTOCycleDepth &other) const
NodeRefList::const_iterator Iterator
bool operator<(const WTOCycleDepth &other) const
bool operator==(const WTOCycleDepth &other) const
WTOCycleDepth(WTOCycleDepth &&)=default
Move constructor.
friend std::ostream & operator<<(std::ostream &o, const WTOCycleDepth< GraphT > &wto)
Overloading operator << for dumping ICFG node ID.
WTOCycleDepth & operator=(WTOCycleDepth &&)=default
Move assignment operator.
WTOCycleDepth(const WTOCycleDepth &)=default
Copy constructor.
bool operator>(const WTOCycleDepth &other) const
void add(const NodeT *head)
Add a cycle head in the cycleDepth.
WTOCycleDepth()=default
Constructor.
WTOCycleDepth operator^(const WTOCycleDepth &other) const
Return the common prefix of the given cycle depths.
WTOCycleDepth & operator=(const WTOCycleDepth &)=default
Copy assignment operator.
std::vector< const NodeT * > NodeRefList
int compare(const WTOCycleDepth &other) const
Compare the given cycle depths.
static bool classof(const WTOComponent< GraphT > *c)
Iterator end() const
End iterator over the components.
std::list< WTOComponentPtr > WTOComponentRefList
const WTONode< GraphT > * head() const
Return the head of the cycle.
const WTOComponentT * WTOComponentPtr
const WTOComponentRefList & getWTOComponents() const
Get all wto components in WTO cycle.
std::string toString() const override
Dump the cycle, for debugging purpose.
const WTONode< GraphT > * _head
Head of the cycle.
Iterator begin() const
Begin iterator over the components.
WTOComponentRefList _components
List of components.
void accept(WTOComponentVisitor< GraphT > &v) const override
Accept the given visitor.
WTOComponentRefList::const_iterator Iterator
Iterator over the components.
WTOComponent< GraphT > WTOComponentT
static bool classof(const WTOCycle< GraphT > *)
ClassOf.
WTOCycle(const WTONode< GraphT > *head, WTOComponentRefList components)
Constructor.
void accept(WTOComponentVisitor< GraphT > &v) const override
Accept the given visitor.
static bool classof(const WTONode< GraphT > *)
ClassOf.
std::string toString() const override
Dump the node, for debugging purpose.
const NodeT * getICFGNode() const
Return the graph node.
WTONode(const NodeT *node)
Constructor.
static bool classof(const WTOComponent< GraphT > *c)
Visitor to build the cycle depths of each node.
void visit(const WTONodeT &node) override
Visit the given node.
WTOCycleDepthBuilder(NodeRefToWTOCycleDepthPtr &nodeToWTOCycleDepth)
NodeRefToWTOCycleDepthPtr & _nodeToWTOCycleDepth
void visit(const WTOCycleT &cycle) override
Visit the given cycle.
WTOCycleDepthPtr _wtoCycleDepth
WTO(WTO &&other)=default
Move constructor.
const WTOComponentRefList & getWTOComponents() const
Get all wto components in WTO.
Iterator begin() const
Begin iterator over the components.
const WTOCycleT * newCycle(const WTONodeT *node, const WTOComponentRefList &partition)
bool in_cycleDepth_table(const NodeT *n) const
Return the cycleDepth of the given node.
std::string toString() const
Dump the order, for debugging purpose.
Iterator end() const
End iterator over the components.
const WTONodeT * newNode(const NodeT *node)
WTOComponent< GraphT > WTOComponentT
WTOComponentRefList::const_iterator Iterator
Iterator over the components.
Map< const NodeT *, WTOCycleDepthPtr > NodeRefToWTOCycleDepthPtr
NodeRefToCycleDepthNumber _nodeToCDN
virtual CycleDepthNumber visit(const NodeT *node, WTOComponentRefList &partition)
NodeRefToWTOCycleMap headRefToCycle
bool isHead(const NodeT *node) const
NodeRefToWTOCycleMap::const_iterator headBegin() const
WTOComponentRefSet _allComponents
virtual void forEachSuccessor(const NodeT *node, std::function< void(const NodeT *)> func) const
WTOCycle< GraphT > WTOCycleT
WTO(GraphT *graph, const NodeT *entry)
Compute the weak topological order of the given graph.
Set< const NodeT * > NodeRefList
void setCDN(const NodeT *n, const CycleDepthNumber &dfn)
Set the depth-first number of the given node.
std::shared_ptr< GraphTWTOCycleDepth > WTOCycleDepthPtr
WTO(const WTO &other)=default
No copy constructor.
virtual const WTOCycleT * component(const NodeT *node)
Create the cycle component for the given node.
Map< const NodeT *, const WTOCycleT * > NodeRefToWTOCycleMap
CycleDepthNumber getCDN(const NodeT *n) const
Return the depth-first number of the given node.
Set< WTOComponentPtr > WTOComponentRefSet
friend std::ostream & operator<<(std::ostream &o, const WTO< GraphT > &wto)
Overloading operator << for dumping ICFG node ID.
Map< const NodeT *, CycleDepthNumber > NodeRefToCycleDepthNumber
WTONode< GraphT > WTONodeT
void push(const NodeT *n)
Push a node on the stack.
const GraphTWTOCycleDepth & cycleDepth(const NodeT *n) const
Return the cycleDepth of the given node.
std::vector< const NodeT * > Stack
NodeRefToWTOCycleDepthPtr _nodeToDepth
const WTOComponentT * WTOComponentPtr
void buildNodeToDepth()
Build the node to WTO cycle depth table.
std::list< WTOComponentPtr > WTOComponentRefList
WTO & operator=(const WTO &other)=default
No copy assignment operator.
WTOComponentRefList _components
NodeRefToWTOCycleMap::const_iterator headEnd() const
End iterator over the components.
WTO & operator=(WTO &&other)=default
Move assignment operator.
WTOCycleDepth< GraphT > GraphTWTOCycleDepth
Map< const NodeT *, NodeRefList > NodeRefTONodeRefListMap
const NodeT * pop()
Pop a node from the stack.
void accept(WTOComponentVisitor< GraphT > &v)
Accept the given visitor.
constexpr std::remove_reference< T >::type && move(T &&t) noexcept
typename make_void< Ts... >::type void_t
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set