Mercurial > hg > Members > tobaru > cbc > CbC_llvm

annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
95
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 //===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===//
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 //
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 // The LLVM Compiler Infrastructure
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 //
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 // This file is distributed under the University of Illinois Open Source
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 // License. See LICENSE.TXT for details.
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 //
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 //===----------------------------------------------------------------------===//
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 //
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 95
diff changeset
10 // Compute iterated dominance frontiers using a linear time algorithm.
95
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 //
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 //===----------------------------------------------------------------------===//
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 #include "llvm/Analysis/IteratedDominanceFrontier.h"
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 #include "llvm/IR/CFG.h"
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 #include "llvm/IR/Dominators.h"
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 #include <queue>
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 95
diff changeset
19 namespace llvm {
121
803732b1fca8 LLVM 5.0
kono
parents: 120
diff changeset
20 template <class NodeTy, bool IsPostDom>
803732b1fca8 LLVM 5.0
kono
parents: 120
diff changeset
21 void IDFCalculator<NodeTy, IsPostDom>::calculate(
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 95
diff changeset
22 SmallVectorImpl<BasicBlock *> &PHIBlocks) {
95
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 // Use a priority queue keyed on dominator tree level so that inserted nodes
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 // are handled from the bottom of the dominator tree upwards.
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 less_second> IDFPriorityQueue;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 IDFPriorityQueue PQ;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 for (BasicBlock *BB : *DefBlocks) {
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 if (DomTreeNode *Node = DT.getNode(BB))
121
803732b1fca8 LLVM 5.0
kono
parents: 120
diff changeset
32 PQ.push({Node, Node->getLevel()});
95
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 }
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 SmallVector<DomTreeNode *, 32> Worklist;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 while (!PQ.empty()) {
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 DomTreeNodePair RootPair = PQ.top();
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 PQ.pop();
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 DomTreeNode *Root = RootPair.first;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 unsigned RootLevel = RootPair.second;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 // Walk all dominator tree children of Root, inspecting their CFG edges with
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 // targets elsewhere on the dominator tree. Only targets whose level is at
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 // most Root's level are added to the iterated dominance frontier of the
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 // definition set.
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 Worklist.clear();
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 Worklist.push_back(Root);
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 VisitedWorklist.insert(Root);
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 while (!Worklist.empty()) {
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 DomTreeNode *Node = Worklist.pop_back_val();
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 BasicBlock *BB = Node->getBlock();
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 95
diff changeset
57 // Succ is the successor in the direction we are calculating IDF, so it is
1172e4bd9c6f update 4.0.0
mir3636
parents: 95
diff changeset
58 // successor for IDF, and predecessor for Reverse IDF.
121
803732b1fca8 LLVM 5.0
kono
parents: 120
diff changeset
59 for (auto *Succ : children<NodeTy>(BB)) {
95
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 DomTreeNode *SuccNode = DT.getNode(Succ);
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 // Quickly skip all CFG edges that are also dominator tree edges instead
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 // of catching them below.
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 if (SuccNode->getIDom() == Node)
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 continue;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66
121
803732b1fca8 LLVM 5.0
kono
parents: 120
diff changeset
67 const unsigned SuccLevel = SuccNode->getLevel();
95
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 if (SuccLevel > RootLevel)
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 continue;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 if (!VisitedPQ.insert(SuccNode).second)
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 continue;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 BasicBlock *SuccBB = SuccNode->getBlock();
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 if (useLiveIn && !LiveInBlocks->count(SuccBB))
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 continue;
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 PHIBlocks.emplace_back(SuccBB);
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 if (!DefBlocks->count(SuccBB))
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 PQ.push(std::make_pair(SuccNode, SuccLevel));
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 }
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 for (auto DomChild : *Node) {
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 if (VisitedWorklist.insert(DomChild).second)
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 Worklist.push_back(DomChild);
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 }
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 }
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 }
afa8332a0e37 LLVM 3.8
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 }
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 95
diff changeset
90
121
803732b1fca8 LLVM 5.0
kono
parents: 120
diff changeset
91 template class IDFCalculator<BasicBlock *, false>;
803732b1fca8 LLVM 5.0
kono
parents: 120
diff changeset
92 template class IDFCalculator<Inverse<BasicBlock *>, true>;
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 95
diff changeset
93 }