1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
//===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// BreakCriticalEdges pass - Break all of the critical edges in the CFG by
// inserting a dummy basic block. This pass may be "required" by passes that
// cannot deal with critical edges. For this usage, the structure type is
// forward declared. This pass obviously invalidates the CFG, but can update
// forward dominator (set, immediate dominators, tree, and frontier)
// information.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Support/CFG.h"
#include "Support/Statistic.h"
using namespace llvm;
namespace {
Statistic<> NumBroken("break-crit-edges", "Number of blocks inserted");
struct BreakCriticalEdges : public FunctionPass {
virtual bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<DominatorSet>();
AU.addPreserved<ImmediateDominators>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<DominanceFrontier>();
// No loop canonicalization guarantees are broken by this pass.
AU.addPreservedID(LoopSimplifyID);
}
};
RegisterOpt<BreakCriticalEdges> X("break-crit-edges",
"Break critical edges in CFG");
}
// Publically exposed interface to pass...
const PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo();
FunctionPass *llvm::createBreakCriticalEdgesPass() {
return new BreakCriticalEdges();
}
// runOnFunction - Loop over all of the edges in the CFG, breaking critical
// edges as they are found.
//
bool BreakCriticalEdges::runOnFunction(Function &F) {
bool Changed = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
TerminatorInst *TI = I->getTerminator();
if (TI->getNumSuccessors() > 1)
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
if (SplitCriticalEdge(TI, i, this)) {
++NumBroken;
Changed = true;
}
}
return Changed;
}
//===----------------------------------------------------------------------===//
// Implementation of the external critical edge manipulation functions
//===----------------------------------------------------------------------===//
// isCriticalEdge - Return true if the specified edge is a critical edge.
// Critical edges are edges from a block with multiple successors to a block
// with multiple predecessors.
//
bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) {
assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
if (TI->getNumSuccessors() == 1) return false;
const BasicBlock *Dest = TI->getSuccessor(SuccNum);
pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest);
// If there is more than one predecessor, this is a critical edge...
assert(I != E && "No preds, but we have an edge to the block?");
++I; // Skip one edge due to the incoming arc from TI.
return I != E;
}
// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
// split the critical edge. This will update DominatorSet, ImmediateDominator,
// DominatorTree, and DominatorFrontier information if it is available, thus
// calling this pass will not invalidate either of them. This returns true if
// the edge was split, false otherwise.
//
bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) {
if (!isCriticalEdge(TI, SuccNum)) return false;
BasicBlock *TIBB = TI->getParent();
BasicBlock *DestBB = TI->getSuccessor(SuccNum);
// Create a new basic block, linking it into the CFG.
BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." +
DestBB->getName() + "_crit_edge");
// Create our unconditional branch...
new BranchInst(DestBB, NewBB);
// Branch to the new block, breaking the edge...
TI->setSuccessor(SuccNum, NewBB);
// Insert the block into the function... right after the block TI lives in.
Function &F = *TIBB->getParent();
F.getBasicBlockList().insert(TIBB->getNext(), NewBB);
// If there are any PHI nodes in DestBB, we need to update them so that they
// merge incoming values from NewBB instead of from TIBB.
//
for (BasicBlock::iterator I = DestBB->begin();
PHINode *PN = dyn_cast<PHINode>(I); ++I) {
// We no longer enter through TIBB, now we come in through NewBB. Revector
// exactly one entry in the PHI node that used to come from TIBB to come
// from NewBB.
Value *InVal = PN->removeIncomingValue(TIBB, false);
PN->addIncoming(InVal, NewBB);
}
// If we don't have a pass object, we can't update anything...
if (P == 0) return true;
// Now update analysis information. These are the analyses that we are
// currently capable of updating...
//
// Should we update DominatorSet information?
if (DominatorSet *DS = P->getAnalysisToUpdate<DominatorSet>()) {
// The blocks that dominate the new one are the blocks that dominate TIBB
// plus the new block itself.
DominatorSet::DomSetType DomSet = DS->getDominators(TIBB);
DomSet.insert(NewBB); // A block always dominates itself.
DS->addBasicBlock(NewBB, DomSet);
}
// Should we update ImmediateDominator information?
if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) {
// TIBB is the new immediate dominator for NewBB. NewBB doesn't dominate
// anything.
ID->addNewBlock(NewBB, TIBB);
}
// Should we update DominatorTree information?
if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) {
DominatorTree::Node *TINode = DT->getNode(TIBB);
// The new block is not the immediate dominator for any other nodes, but
// TINode is the immediate dominator for the new node.
//
if (TINode) // Don't break unreachable code!
DT->createNewNode(NewBB, TINode);
}
// Should we update DominanceFrontier information?
if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) {
// Since the new block is dominated by its only predecessor TIBB,
// it cannot be in any block's dominance frontier. Its dominance
// frontier is {DestBB}.
DominanceFrontier::DomSetType NewDFSet;
NewDFSet.insert(DestBB);
DF->addBasicBlock(NewBB, NewDFSet);
}
return true;
}
|
