Index: include/llvm/Analysis/BlockFrequencyInfoImpl.h =================================================================== --- include/llvm/Analysis/BlockFrequencyInfoImpl.h +++ include/llvm/Analysis/BlockFrequencyInfoImpl.h @@ -1251,7 +1251,7 @@ : DefaultDOTGraphTraits(isSimple) {} typedef GraphTraits GTraits; - typedef typename GTraits::NodeType NodeType; + typedef typename GTraits::NodeRef NodeRef; typedef typename GTraits::ChildIteratorType EdgeIter; typedef typename GTraits::nodes_iterator NodeIter; @@ -1260,8 +1260,7 @@ return G->getFunction()->getName(); } - std::string getNodeAttributes(const NodeType *Node, - const BlockFrequencyInfoT *Graph, + std::string getNodeAttributes(NodeRef Node, const BlockFrequencyInfoT *Graph, unsigned HotPercentThreshold = 0) { std::string Result; if (!HotPercentThreshold) @@ -1272,9 +1271,9 @@ for (NodeIter I = GTraits::nodes_begin(Graph), E = GTraits::nodes_end(Graph); I != E; ++I) { - NodeType &N = *I; + NodeRef N = &*I; MaxFrequency = - std::max(MaxFrequency, Graph->getBlockFreq(&N).getFrequency()); + std::max(MaxFrequency, Graph->getBlockFreq(N).getFrequency()); } } BlockFrequency Freq = Graph->getBlockFreq(Node); @@ -1291,8 +1290,8 @@ return Result; } - std::string getNodeLabel(const NodeType *Node, - const BlockFrequencyInfoT *Graph, GVDAGType GType) { + std::string getNodeLabel(NodeRef Node, const BlockFrequencyInfoT *Graph, + GVDAGType GType) { std::string Result; raw_string_ostream OS(Result); @@ -1319,7 +1318,7 @@ return Result; } - std::string getEdgeAttributes(const NodeType *Node, EdgeIter EI, + std::string getEdgeAttributes(NodeRef Node, EdgeIter EI, const BlockFrequencyInfoT *BFI, const BranchProbabilityInfoT *BPI, unsigned HotPercentThreshold = 0) { Index: include/llvm/Analysis/LoopInfoImpl.h =================================================================== --- include/llvm/Analysis/LoopInfoImpl.h +++ include/llvm/Analysis/LoopInfoImpl.h @@ -137,7 +137,7 @@ for (typename InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(Header), PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) { - typename InvBlockTraits::NodeType *N = *PI; + typename InvBlockTraits::NodeRef N = *PI; if (!contains(N)) { // If the block is not in the loop... if (Out && Out != N) return nullptr; // Multiple predecessors outside the loop @@ -162,7 +162,7 @@ InvBlockTraits::child_end(Header); BlockT *Latch = nullptr; for (; PI != PE; ++PI) { - typename InvBlockTraits::NodeType *N = *PI; + typename InvBlockTraits::NodeRef N = *PI; if (contains(N)) { if (Latch) return nullptr; Latch = N; Index: include/llvm/Analysis/RegionIterator.h =================================================================== --- include/llvm/Analysis/RegionIterator.h +++ include/llvm/Analysis/RegionIterator.h @@ -30,10 +30,10 @@ /// /// For a subregion RegionNode there is just one successor. The RegionNode /// representing the exit of the subregion. -template -class RNSuccIterator : public std::iterator { - typedef std::iterator super; +template +class RNSuccIterator + : public std::iterator { + typedef std::iterator super; typedef GraphTraits BlockTraits; typedef typename BlockTraits::ChildIteratorType SuccIterTy; @@ -49,8 +49,13 @@ ItRgEnd // At the end of the regionnode successor. }; + static_assert(std::is_pointer::value, + "FIXME: Currently RNSuccIterator only supports NodeRef as " + "pointers due to the use of PointerIntPair internally. " + "Generalize it to support non-pointer types"); + // Use two bit to represent the mode iterator. - PointerIntPair Node; + PointerIntPair Node; // The block successor iterator. SuccIterTy BItor; @@ -62,15 +67,15 @@ Node.setInt(ItRgEnd); } - NodeType* getNode() const{ return Node.getPointer(); } + NodeRef getNode() const { return Node.getPointer(); } // isRegionMode - Is the current iterator in region mode? bool isRegionMode() const { return Node.getInt() != ItBB; } // Get the immediate successor. This function may return a Basic Block // RegionNode or a subregion RegionNode. - NodeType* getISucc(BlockT* BB) const { - NodeType *succ; + NodeRef getISucc(BlockT *BB) const { + NodeRef succ; succ = getNode()->getParent()->getNode(BB); assert(succ && "BB not in Region or entered subregion!"); return succ; @@ -87,14 +92,14 @@ return getNode()->getParent()->getExit() == BB; } public: - typedef RNSuccIterator Self; + typedef RNSuccIterator Self; - typedef typename super::pointer pointer; + typedef typename super::value_type value_type; /// @brief Create begin iterator of a RegionNode. - inline RNSuccIterator(NodeType* node) - : Node(node, node->isSubRegion() ? ItRgBegin : ItBB), - BItor(BlockTraits::child_begin(node->getEntry())) { + inline RNSuccIterator(NodeRef node) + : Node(node, node->isSubRegion() ? ItRgBegin : ItBB), + BItor(BlockTraits::child_begin(node->getEntry())) { // Skip the exit block if (!isRegionMode()) @@ -106,9 +111,9 @@ } /// @brief Create an end iterator. - inline RNSuccIterator(NodeType* node, bool) - : Node(node, node->isSubRegion() ? ItRgEnd : ItBB), - BItor(BlockTraits::child_end(node->getEntry())) {} + inline RNSuccIterator(NodeRef node, bool) + : Node(node, node->isSubRegion() ? ItRgEnd : ItBB), + BItor(BlockTraits::child_end(node->getEntry())) {} inline bool operator==(const Self& x) const { assert(isRegionMode() == x.isRegionMode() && "Broken iterator!"); @@ -120,7 +125,7 @@ inline bool operator!=(const Self& x) const { return !operator==(x); } - inline pointer operator*() const { + inline value_type operator*() const { BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor; assert(!isExit(BB) && "Iterator out of range!"); return getISucc(BB); @@ -154,43 +159,41 @@ /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that /// are contained in the Region and its subregions. This is close to a virtual /// control flow graph of the Region. -template -class RNSuccIterator, BlockT, RegionT> - : public std::iterator { - typedef std::iterator super; +template +class RNSuccIterator, BlockT, RegionT> + : public std::iterator { + typedef std::iterator super; typedef GraphTraits BlockTraits; typedef typename BlockTraits::ChildIteratorType SuccIterTy; - NodeType* Node; + NodeRef Node; SuccIterTy Itor; public: - typedef RNSuccIterator, BlockT, RegionT> Self; - typedef typename super::pointer pointer; + typedef RNSuccIterator, BlockT, RegionT> Self; + typedef typename super::value_type value_type; /// @brief Create the iterator from a RegionNode. /// /// Note that the incoming node must be a bb node, otherwise it will trigger /// an assertion when we try to get a BasicBlock. - inline RNSuccIterator(NodeType* node) : - Node(node), - Itor(BlockTraits::child_begin(node->getEntry())) { - assert(!Node->isSubRegion() - && "Subregion node not allowed in flat iterating mode!"); - assert(Node->getParent() && "A BB node must have a parent!"); - - // Skip the exit block of the iterating region. - while (BlockTraits::child_end(Node->getEntry()) != Itor - && Node->getParent()->getExit() == *Itor) - ++Itor; + inline RNSuccIterator(NodeRef node) + : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) { + assert(!Node->isSubRegion() && + "Subregion node not allowed in flat iterating mode!"); + assert(Node->getParent() && "A BB node must have a parent!"); + + // Skip the exit block of the iterating region. + while (BlockTraits::child_end(Node->getEntry()) != Itor && + Node->getParent()->getExit() == *Itor) + ++Itor; } /// @brief Create an end iterator - inline RNSuccIterator(NodeType* node, bool) : - Node(node), - Itor(BlockTraits::child_end(node->getEntry())) { - assert(!Node->isSubRegion() - && "Subregion node not allowed in flat iterating mode!"); + inline RNSuccIterator(NodeRef node, bool) + : Node(node), Itor(BlockTraits::child_end(node->getEntry())) { + assert(!Node->isSubRegion() && + "Subregion node not allowed in flat iterating mode!"); } inline bool operator==(const Self& x) const { @@ -202,7 +205,7 @@ inline bool operator!=(const Self& x) const { return !operator==(x); } - inline pointer operator*() const { + inline value_type operator*() const { BlockT *BB = *Itor; // Get the iterating region. @@ -232,14 +235,14 @@ } }; -template -inline RNSuccIterator succ_begin(NodeType* Node) { - return RNSuccIterator(Node); +template +inline RNSuccIterator succ_begin(NodeRef Node) { + return RNSuccIterator(Node); } -template -inline RNSuccIterator succ_end(NodeType* Node) { - return RNSuccIterator(Node, true); +template +inline RNSuccIterator succ_end(NodeRef Node) { + return RNSuccIterator(Node, true); } //===--------------------------------------------------------------------===// @@ -253,56 +256,58 @@ template <> struct GraphTraits { \ typedef NodeT NodeType; \ typedef NodeT *NodeRef; \ - typedef RNSuccIterator ChildIteratorType; \ - static NodeType *getEntryNode(NodeType *N) { return N; } \ - static inline ChildIteratorType child_begin(NodeType *N) { \ - return RNSuccIterator(N); \ + typedef RNSuccIterator ChildIteratorType; \ + static NodeRef getEntryNode(NodeRef N) { return N; } \ + static inline ChildIteratorType child_begin(NodeRef N) { \ + return RNSuccIterator(N); \ } \ - static inline ChildIteratorType child_end(NodeType *N) { \ - return RNSuccIterator(N, true); \ + static inline ChildIteratorType child_end(NodeRef N) { \ + return RNSuccIterator(N, true); \ } \ }; \ template <> struct GraphTraits> { \ typedef NodeT NodeType; \ typedef NodeT *NodeRef; \ - typedef RNSuccIterator, BlockT, RegionT> ChildIteratorType; \ - static NodeType *getEntryNode(NodeType *N) { return N; } \ - static inline ChildIteratorType child_begin(NodeType *N) { \ - return RNSuccIterator, BlockT, RegionT>(N); \ + typedef RNSuccIterator, BlockT, RegionT> \ + ChildIteratorType; \ + static NodeRef getEntryNode(NodeRef N) { return N; } \ + static inline ChildIteratorType child_begin(NodeRef N) { \ + return RNSuccIterator, BlockT, RegionT>(N); \ } \ - static inline ChildIteratorType child_end(NodeType *N) { \ - return RNSuccIterator, BlockT, RegionT>(N, true); \ + static inline ChildIteratorType child_end(NodeRef N) { \ + return RNSuccIterator, BlockT, RegionT>(N, true); \ } \ } -#define RegionGraphTraits(RegionT, NodeT) \ -template<> struct GraphTraits \ - : public GraphTraits { \ - typedef df_iterator nodes_iterator; \ - static NodeType *getEntryNode(RegionT* R) { \ - return R->getNode(R->getEntry()); \ - } \ - static nodes_iterator nodes_begin(RegionT* R) { \ - return nodes_iterator::begin(getEntryNode(R)); \ - } \ - static nodes_iterator nodes_end(RegionT* R) { \ - return nodes_iterator::end(getEntryNode(R)); \ - } \ -}; \ -template<> struct GraphTraits > \ - : public GraphTraits > { \ - typedef df_iterator, false, \ - GraphTraits > > nodes_iterator; \ - static NodeType *getEntryNode(RegionT* R) { \ - return R->getBBNode(R->getEntry()); \ - } \ - static nodes_iterator nodes_begin(RegionT* R) { \ - return nodes_iterator::begin(getEntryNode(R)); \ - } \ - static nodes_iterator nodes_end(RegionT* R) { \ - return nodes_iterator::end(getEntryNode(R)); \ - } \ -} +#define RegionGraphTraits(RegionT, NodeT) \ + template <> struct GraphTraits : public GraphTraits { \ + typedef df_iterator nodes_iterator; \ + static NodeRef getEntryNode(RegionT *R) { \ + return R->getNode(R->getEntry()); \ + } \ + static nodes_iterator nodes_begin(RegionT *R) { \ + return nodes_iterator::begin(getEntryNode(R)); \ + } \ + static nodes_iterator nodes_end(RegionT *R) { \ + return nodes_iterator::end(getEntryNode(R)); \ + } \ + }; \ + template <> \ + struct GraphTraits> \ + : public GraphTraits> { \ + typedef df_iterator, false, \ + GraphTraits>> \ + nodes_iterator; \ + static NodeRef getEntryNode(RegionT *R) { \ + return R->getBBNode(R->getEntry()); \ + } \ + static nodes_iterator nodes_begin(RegionT *R) { \ + return nodes_iterator::begin(getEntryNode(R)); \ + } \ + static nodes_iterator nodes_end(RegionT *R) { \ + return nodes_iterator::end(getEntryNode(R)); \ + } \ + } RegionNodeGraphTraits(RegionNode, BasicBlock, Region); RegionNodeGraphTraits(const RegionNode, BasicBlock, Region); @@ -312,10 +317,11 @@ template <> struct GraphTraits : public GraphTraits > { - typedef df_iterator, false, - GraphTraits > > nodes_iterator; + typedef df_iterator, false, + GraphTraits>> + nodes_iterator; - static NodeType *getEntryNode(RegionInfo *RI) { + static NodeRef getEntryNode(RegionInfo *RI) { return GraphTraits >::getEntryNode(RI->getTopLevelRegion()); } static nodes_iterator nodes_begin(RegionInfo* RI) { @@ -328,10 +334,11 @@ template <> struct GraphTraits : public GraphTraits { - typedef df_iterator, false, - GraphTraits > > nodes_iterator; + typedef df_iterator, false, + GraphTraits>> + nodes_iterator; - static NodeType *getEntryNode(RegionInfoPass *RI) { + static NodeRef getEntryNode(RegionInfoPass *RI) { return GraphTraits::getEntryNode(&RI->getRegionInfo()); } static nodes_iterator nodes_begin(RegionInfoPass* RI) {