Mercurial > hg > Members > tobaru > cbc > CbC_llvm

comparison lib/Analysis/IteratedDominanceFrontier.cpp @ 121:803732b1fca8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 5.0
author kono
date Fri, 27 Oct 2017 17:07:41 +0900
parents 1172e4bd9c6f
children
comparison
equal deleted inserted replaced
120:1172e4bd9c6f 121:803732b1fca8
15 #include "llvm/IR/CFG.h" 15 #include "llvm/IR/CFG.h"
16 #include "llvm/IR/Dominators.h" 16 #include "llvm/IR/Dominators.h"
17 #include <queue> 17 #include <queue>
18 18
19 namespace llvm { 19 namespace llvm {
20 template <class NodeTy> 20 template <class NodeTy, bool IsPostDom>
21 void IDFCalculator<NodeTy>::calculate( 21 void IDFCalculator<NodeTy, IsPostDom>::calculate(
22 SmallVectorImpl<BasicBlock *> &PHIBlocks) { 22 SmallVectorImpl<BasicBlock *> &PHIBlocks) {
23 // If we haven't computed dominator tree levels, do so now.
24 if (DomLevels.empty()) {
25 for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode());
26 DFI != DFE; ++DFI) {
27 DomLevels[*DFI] = DFI.getPathLength() - 1;
28 }
29 }
30
31 // Use a priority queue keyed on dominator tree level so that inserted nodes 23 // Use a priority queue keyed on dominator tree level so that inserted nodes
32 // are handled from the bottom of the dominator tree upwards. 24 // are handled from the bottom of the dominator tree upwards.
33 typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair; 25 typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
34 typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>, 26 typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
35 less_second> IDFPriorityQueue; 27 less_second> IDFPriorityQueue;
36 IDFPriorityQueue PQ; 28 IDFPriorityQueue PQ;
37 29
38 for (BasicBlock *BB : *DefBlocks) { 30 for (BasicBlock *BB : *DefBlocks) {
39 if (DomTreeNode *Node = DT.getNode(BB)) 31 if (DomTreeNode *Node = DT.getNode(BB))
40 PQ.push(std::make_pair(Node, DomLevels.lookup(Node))); 32 PQ.push({Node, Node->getLevel()});
41 } 33 }
42 34
43 SmallVector<DomTreeNode *, 32> Worklist; 35 SmallVector<DomTreeNode *, 32> Worklist;
44 SmallPtrSet<DomTreeNode *, 32> VisitedPQ; 36 SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
45 SmallPtrSet<DomTreeNode *, 32> VisitedWorklist; 37 SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
62 while (!Worklist.empty()) { 54 while (!Worklist.empty()) {
63 DomTreeNode *Node = Worklist.pop_back_val(); 55 DomTreeNode *Node = Worklist.pop_back_val();
64 BasicBlock *BB = Node->getBlock(); 56 BasicBlock *BB = Node->getBlock();
65 // Succ is the successor in the direction we are calculating IDF, so it is 57 // Succ is the successor in the direction we are calculating IDF, so it is
66 // successor for IDF, and predecessor for Reverse IDF. 58 // successor for IDF, and predecessor for Reverse IDF.
67 for (auto SuccIter = GraphTraits<NodeTy>::child_begin(BB), 59 for (auto *Succ : children<NodeTy>(BB)) {
68 End = GraphTraits<NodeTy>::child_end(BB);
69 SuccIter != End; ++SuccIter) {
70 BasicBlock *Succ = *SuccIter;
71 DomTreeNode *SuccNode = DT.getNode(Succ); 60 DomTreeNode *SuccNode = DT.getNode(Succ);
72 61
73 // Quickly skip all CFG edges that are also dominator tree edges instead 62 // Quickly skip all CFG edges that are also dominator tree edges instead
74 // of catching them below. 63 // of catching them below.
75 if (SuccNode->getIDom() == Node) 64 if (SuccNode->getIDom() == Node)
76 continue; 65 continue;
77 66
78 unsigned SuccLevel = DomLevels.lookup(SuccNode); 67 const unsigned SuccLevel = SuccNode->getLevel();
79 if (SuccLevel > RootLevel) 68 if (SuccLevel > RootLevel)
80 continue; 69 continue;
81 70
82 if (!VisitedPQ.insert(SuccNode).second) 71 if (!VisitedPQ.insert(SuccNode).second)
83 continue; 72 continue;
97 } 86 }
98 } 87 }
99 } 88 }
100 } 89 }
101 90
102 template class IDFCalculator<BasicBlock *>; 91 template class IDFCalculator<BasicBlock *, false>;
103 template class IDFCalculator<Inverse<BasicBlock *>>; 92 template class IDFCalculator<Inverse<BasicBlock *>, true>;
104 } 93 }