43template <
typename GraphT>
class WTO;
45template <
typename GraphT>
class WTONode;
47template <
typename GraphT>
class WTOCycle;
52template <
typename T,
typename =
void>
struct has_nodetype : std::false_type
57struct has_nodetype<T, std::void_t<typename T::NodeType>> : std::true_type
61template <
typename T,
typename =
void>
struct has_edgetype : std::false_type
66struct has_edgetype<T, std::void_t<typename T::EdgeType>> : std::true_type
104 "GraphT must have a nested type named 'NodeType'");
105 typedef typename GraphT::NodeType
NodeT;
111 typedef typename NodeRefList::const_iterator
Iterator;
157 for (
auto this_it =
begin(), other_it = other.
begin();
158 this_it !=
end() && other_it != other.
end(); ++this_it, ++other_it)
160 if (*this_it == *other_it)
181 auto this_it =
begin();
182 auto other_it = other.
begin();
183 while (this_it !=
end())
185 if (other_it == other.
end())
189 else if (*this_it == *other_it)
199 if (other_it == other.
end())
239 std::stringstream rawstr(str);
241 for (
auto it =
begin(), et =
end(); it != et;)
243 rawstr << (*it)->toString();
306 [[nodiscard]]
virtual std::string
toString()
const = 0;
329 "GraphT must have a nested type named 'NodeType'");
330 typedef typename GraphT::NodeType
NodeT;
355 [[nodiscard]] std::string
toString()
const override
358 return std::to_string(
_node->getId());
383 "GraphT must have a nested type named 'NodeType'");
384 typedef typename GraphT::NodeType
NodeT;
393 typedef typename WTOComponentRefList::const_iterator
Iterator;
454 [[nodiscard]] std::string
toString()
const override
457 std::stringstream rawstr(str);
459 rawstr <<
_head->getICFGNode()->getId() <<
", ";
460 for (
auto it =
begin(), et =
end(); it != et;)
462 rawstr << (*it)->toString();
515template <typename GraphT> class
WTO
520 "GraphT must have a nested type named 'NodeType'");
522 "GraphT must have a nested type named 'EdgeType'");
523 typedef typename GraphT::NodeType
NodeT;
524 typedef typename GraphT::EdgeType
EdgeT;
540 typedef std::vector<const NodeT*>
Stack;
546 typedef typename WTOComponentRefList::const_iterator
Iterator;
609 typename NodeRefToWTOCycleMap::const_iterator
headBegin()
const
615 typename NodeRefToWTOCycleMap::const_iterator
headEnd()
const
625 return *(it->second);
648 std::stringstream rawstr(str);
650 for (
auto it =
begin(), et =
end(); it != et;)
652 rawstr << (*it)->toString();
699 const NodeT* head = cycle.
head()->getICFGNode();
705 for (
auto it = cycle.
begin(), et = cycle.
end(); it != et; ++it)
707 (*it)->accept(*
this);
724 std::vector<const NodeT *> succssors;
727 succssors.push_back(e->getDstNode());
750 auto res =
_nodeToCDN.insert(std::make_pair(
n, dfn));
753 (res.first)->second = dfn;
760 assert(!
_stack.empty() &&
"empty stack");
796 visit(succ, partition);
826 min =
visit(succ, partition);
845 while (element != node)
854 partition.push_front(
newNode(node));
864 for (
auto it =
begin(), et =
end(); it != et; ++it)
866 (*it)->accept(builder);
const GEdgeSetTy & getOutEdges() const
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.
WTOCycle< ICFG > WTOCycleT
virtual std::string toString() const =0
friend std::ostream & operator<<(std::ostream &o, const WTOComponent< GraphT > &wto)
Overloading operator << for dumping ICFG node ID.
virtual void accept(WTOComponentVisitor< ICFG > &) const=0
WTOComponent(WTOCT k)
Default constructor.
WTOComponent(const WTOComponent &) noexcept=default
Copy constructor.
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.
WTOCycleDepth & operator=(WTOCycleDepth &&)=default
Move assignment operator.
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.
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 &)=default
Copy assignment operator.
friend std::ostream & operator<<(std::ostream &o, const WTOCycleDepth< GraphT > &wto)
Overloading operator << for dumping ICFG node ID.
WTOCycleDepth operator^(const WTOCycleDepth &other) const
Return the common prefix of the given cycle depths.
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 WTOComponentRefList & getWTOComponents() const
Get all wto components in WTO cycle.
const WTOComponentT * WTOComponentPtr
std::string toString() const override
Dump the cycle, for debugging purpose.
const WTONode< ICFG > * _head
Iterator begin() const
Begin iterator over the components.
WTOComponentRefList _components
void accept(WTOComponentVisitor< GraphT > &v) const override
Accept the given visitor.
WTOComponentRefList::const_iterator Iterator
const WTONode< ICFG > * head() const
WTOComponent< ICFG > 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.
const NodeT * getICFGNode() const
Return the graph node.
std::string toString() const override
Dump the node, for debugging purpose.
WTONode(const NodeT *node)
Constructor.
static bool classof(const WTOComponent< GraphT > *c)
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 & operator=(WTO &&other)=default
Move assignment operator.
WTO(WTO &&other)=default
Move constructor.
Iterator begin() const
Begin iterator over the components.
const NodeT * pop()
Pop a node from the stack.
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.
WTOComponent< ICFG > WTOComponentT
WTOComponentRefList::const_iterator Iterator
Map< const NodeT *, WTOCycleDepthPtr > NodeRefToWTOCycleDepthPtr
NodeRefToCycleDepthNumber _nodeToCDN
const GraphTWTOCycleDepth & cycleDepth(const NodeT *n) const
Return the cycleDepth of the given node.
virtual CycleDepthNumber visit(const NodeT *node, WTOComponentRefList &partition)
NodeRefToWTOCycleMap headRefToCycle
bool isHead(const NodeT *node) const
const WTOCycleT * newCycle(const WTONodeT *node, const WTOComponentRefList &partition)
NodeRefToWTOCycleMap::const_iterator headBegin() const
WTOComponentRefSet _allComponents
WTOCycle< ICFG > WTOCycleT
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.
Map< const NodeT *, const WTOCycleT * > NodeRefToWTOCycleMap
CycleDepthNumber getCDN(const NodeT *n) const
Return the depth-first number of the given node.
WTO & operator=(const WTO &other)=default
No copy assignment operator.
Set< WTOComponentPtr > WTOComponentRefSet
Map< const NodeT *, CycleDepthNumber > NodeRefToCycleDepthNumber
virtual std::vector< const NodeT * > getSuccessors(const NodeT *node)
Return the successors of node.
void push(const NodeT *n)
Push a node on the stack.
virtual const WTOCycleT * component(const NodeT *node)
std::vector< const NodeT * > Stack
NodeRefToWTOCycleDepthPtr _nodeToDepth
const WTOComponentT * WTOComponentPtr
std::list< WTOComponentPtr > WTOComponentRefList
WTOComponentRefList _components
NodeRefToWTOCycleMap::const_iterator headEnd() const
End iterator over the components.
const WTONodeT * newNode(const NodeT *node)
WTOCycleDepth< ICFG > GraphTWTOCycleDepth
Map< const NodeT *, NodeRefList > NodeRefTONodeRefListMap
const WTOComponentRefList & getWTOComponents() const
Get all wto components in WTO.
void accept(WTOComponentVisitor< GraphT > &v)
Accept the given visitor.
friend std::ostream & operator<<(std::ostream &o, const WTO< GraphT > &wto)
Overloading operator << for dumping ICFG node ID.
WTO(const NodeT *entry)
Compute the weak topological order of the given graph.
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map