1 //===------------------- SSI.cpp - Creates SSI Representation -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass converts a list of variables to the Static Single Information
11 // form. This is a program representation described by Scott Ananian in his
12 // Master Thesis: "The Static Single Information Form (1999)".
13 // We are building an on-demand representation, that is, we do not convert
14 // every single variable in the target function to SSI form. Rather, we receive
15 // a list of target variables that must be converted. We also do not
16 // completely convert a target variable to the SSI format. Instead, we only
17 // change the variable in the points where new information can be attached
18 // to its live range, that is, at branch points.
20 //===----------------------------------------------------------------------===//
22 #define DEBUG_TYPE "ssi"
24 #include "llvm/Transforms/Scalar.h"
25 #include "llvm/Transforms/Utils/SSI.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/Analysis/Dominators.h"
31 static const std::string SSI_PHI
= "SSI_phi";
32 static const std::string SSI_SIG
= "SSI_sigma";
34 STATISTIC(NumSigmaInserted
, "Number of sigma functions inserted");
35 STATISTIC(NumPhiInserted
, "Number of phi functions inserted");
37 void SSI::getAnalysisUsage(AnalysisUsage
&AU
) const {
38 AU
.addRequiredTransitive
<DominanceFrontier
>();
39 AU
.addRequiredTransitive
<DominatorTree
>();
43 bool SSI::runOnFunction(Function
&F
) {
44 DT_
= &getAnalysis
<DominatorTree
>();
48 /// This methods creates the SSI representation for the list of values
49 /// received. It will only create SSI representation if a value is used
50 /// to decide a branch. Repeated values are created only once.
52 void SSI::createSSI(SmallVectorImpl
<Instruction
*> &value
) {
55 SmallPtrSet
<Instruction
*, 4> needConstruction
;
56 for (SmallVectorImpl
<Instruction
*>::iterator I
= value
.begin(),
57 E
= value
.end(); I
!= E
; ++I
)
58 if (created
.insert(*I
))
59 needConstruction
.insert(*I
);
61 insertSigmaFunctions(needConstruction
);
63 // Test if there is a need to transform to SSI
64 if (!needConstruction
.empty()) {
65 insertPhiFunctions(needConstruction
);
66 renameInit(needConstruction
);
67 rename(DT_
->getRoot());
74 /// Insert sigma functions (a sigma function is a phi function with one
77 void SSI::insertSigmaFunctions(SmallPtrSet
<Instruction
*, 4> &value
) {
78 for (SmallPtrSet
<Instruction
*, 4>::iterator I
= value
.begin(),
79 E
= value
.end(); I
!= E
; ++I
) {
80 for (Value::use_iterator begin
= (*I
)->use_begin(),
81 end
= (*I
)->use_end(); begin
!= end
; ++begin
) {
82 // Test if the Use of the Value is in a comparator
83 if (CmpInst
*CI
= dyn_cast
<CmpInst
>(begin
)) {
84 // Iterates through all uses of CmpInst
85 for (Value::use_iterator begin_ci
= CI
->use_begin(),
86 end_ci
= CI
->use_end(); begin_ci
!= end_ci
; ++begin_ci
) {
87 // Test if any use of CmpInst is in a Terminator
88 if (TerminatorInst
*TI
= dyn_cast
<TerminatorInst
>(begin_ci
)) {
97 /// Inserts Sigma Functions in every BasicBlock successor to Terminator
98 /// Instruction TI. All inserted Sigma Function are related to Instruction I.
100 void SSI::insertSigma(TerminatorInst
*TI
, Instruction
*I
) {
101 // Basic Block of the Terminator Instruction
102 BasicBlock
*BB
= TI
->getParent();
103 for (unsigned i
= 0, e
= TI
->getNumSuccessors(); i
< e
; ++i
) {
105 BasicBlock
*BB_next
= TI
->getSuccessor(i
);
107 BB_next
->getSinglePredecessor() != NULL
&&
108 dominateAny(BB_next
, I
)) {
109 PHINode
*PN
= PHINode::Create(I
->getType(), SSI_SIG
, BB_next
->begin());
110 PN
->addIncoming(I
, BB
);
113 defsites
[I
].push_back(BB_next
);
119 /// Insert phi functions when necessary
121 void SSI::insertPhiFunctions(SmallPtrSet
<Instruction
*, 4> &value
) {
122 DominanceFrontier
*DF
= &getAnalysis
<DominanceFrontier
>();
123 for (SmallPtrSet
<Instruction
*, 4>::iterator I
= value
.begin(),
124 E
= value
.end(); I
!= E
; ++I
) {
125 // Test if there were any sigmas for this variable
126 SmallPtrSet
<BasicBlock
*, 16> BB_visited
;
128 // Insert phi functions if there is any sigma function
129 while (!defsites
[*I
].empty()) {
131 BasicBlock
*BB
= defsites
[*I
].back();
133 defsites
[*I
].pop_back();
134 DominanceFrontier::iterator DF_BB
= DF
->find(BB
);
136 // The BB is unreachable. Skip it.
137 if (DF_BB
== DF
->end())
140 // Iterates through all the dominance frontier of BB
141 for (std::set
<BasicBlock
*>::iterator DF_BB_begin
=
142 DF_BB
->second
.begin(), DF_BB_end
= DF_BB
->second
.end();
143 DF_BB_begin
!= DF_BB_end
; ++DF_BB_begin
) {
144 BasicBlock
*BB_dominated
= *DF_BB_begin
;
146 // Test if has not yet visited this node and if the
147 // original definition dominates this node
148 if (BB_visited
.insert(BB_dominated
) &&
149 DT_
->properlyDominates(value_original
[*I
], BB_dominated
) &&
150 dominateAny(BB_dominated
, *I
)) {
151 PHINode
*PN
= PHINode::Create(
152 (*I
)->getType(), SSI_PHI
, BB_dominated
->begin());
153 phis
.insert(std::make_pair(PN
, *I
));
156 defsites
[*I
].push_back(BB_dominated
);
165 /// Some initialization for the rename part
167 void SSI::renameInit(SmallPtrSet
<Instruction
*, 4> &value
) {
168 for (SmallPtrSet
<Instruction
*, 4>::iterator I
= value
.begin(),
169 E
= value
.end(); I
!= E
; ++I
)
170 value_stack
[*I
].push_back(*I
);
173 /// Renames all variables in the specified BasicBlock.
174 /// Only variables that need to be rename will be.
176 void SSI::rename(BasicBlock
*BB
) {
177 SmallPtrSet
<Instruction
*, 8> defined
;
179 // Iterate through instructions and make appropriate renaming.
180 // For SSI_PHI (b = PHI()), store b at value_stack as a new
181 // definition of the variable it represents.
182 // For SSI_SIG (b = PHI(a)), substitute a with the current
183 // value of a, present in the value_stack.
184 // Then store bin the value_stack as the new definition of a.
185 // For all other instructions (b = OP(a, c, d, ...)), we need to substitute
186 // all operands with its current value, present in value_stack.
187 for (BasicBlock::iterator begin
= BB
->begin(), end
= BB
->end();
188 begin
!= end
; ++begin
) {
189 Instruction
*I
= begin
;
190 if (PHINode
*PN
= dyn_cast
<PHINode
>(I
)) { // Treat PHI functions
191 Instruction
* position
;
194 if ((position
= getPositionPhi(PN
))) {
195 value_stack
[position
].push_back(PN
);
196 defined
.insert(position
);
198 } else if ((position
= getPositionSigma(PN
))) {
200 value_stack
[position
].push_back(PN
);
201 defined
.insert(position
);
204 // Treat all other PHI functions
210 // Treat all other functions
216 // This loop iterates in all BasicBlocks that are successors of the current
217 // BasicBlock. For each SSI_PHI instruction found, insert an operand.
218 // This operand is the current operand in value_stack for the variable
219 // in "position". And the BasicBlock this operand represents is the current
221 for (succ_iterator SI
= succ_begin(BB
), SE
= succ_end(BB
); SI
!= SE
; ++SI
) {
222 BasicBlock
*BB_succ
= *SI
;
224 for (BasicBlock::iterator begin
= BB_succ
->begin(),
225 notPhi
= BB_succ
->getFirstNonPHI(); begin
!= *notPhi
; ++begin
) {
226 Instruction
*I
= begin
;
227 PHINode
*PN
= dyn_cast
<PHINode
>(I
);
228 Instruction
* position
;
229 if (PN
&& ((position
= getPositionPhi(PN
)))) {
230 PN
->addIncoming(value_stack
[position
].back(), BB
);
235 // This loop calls rename on all children from this block. This time children
236 // refers to a successor block in the dominance tree.
237 DomTreeNode
*DTN
= DT_
->getNode(BB
);
238 for (DomTreeNode::iterator begin
= DTN
->begin(), end
= DTN
->end();
239 begin
!= end
; ++begin
) {
240 DomTreeNodeBase
<BasicBlock
> *DTN_children
= *begin
;
241 BasicBlock
*BB_children
= DTN_children
->getBlock();
245 // Now we remove all inserted definitions of a variable from the top of
246 // the stack leaving the previous one as the top.
247 for (SmallPtrSet
<Instruction
*, 8>::iterator DI
= defined
.begin(),
248 DE
= defined
.end(); DI
!= DE
; ++DI
)
249 value_stack
[*DI
].pop_back();
252 /// Substitute any use in this instruction for the last definition of
255 void SSI::substituteUse(Instruction
*I
) {
256 for (unsigned i
= 0, e
= I
->getNumOperands(); i
< e
; ++i
) {
257 Value
*operand
= I
->getOperand(i
);
258 for (DenseMap
<Instruction
*, SmallVector
<Instruction
*, 1> >::iterator
259 VI
= value_stack
.begin(), VE
= value_stack
.end(); VI
!= VE
; ++VI
) {
260 if (operand
== VI
->second
.front() &&
261 I
!= VI
->second
.back()) {
262 PHINode
*PN_I
= dyn_cast
<PHINode
>(I
);
263 PHINode
*PN_vs
= dyn_cast
<PHINode
>(VI
->second
.back());
265 // If a phi created in a BasicBlock is used as an operand of another
266 // created in the same BasicBlock, this step marks this second phi,
267 // to fix this issue later. It cannot be fixed now, because the
268 // operands of the first phi are not final yet.
270 VI
->second
.back()->getParent() == I
->getParent()) {
272 phisToFix
.insert(PN_I
);
275 I
->setOperand(i
, VI
->second
.back());
282 /// Test if the BasicBlock BB dominates any use or definition of value.
283 /// If it dominates a phi instruction that is on the same BasicBlock,
284 /// that does not count.
286 bool SSI::dominateAny(BasicBlock
*BB
, Instruction
*value
) {
287 for (Value::use_iterator begin
= value
->use_begin(),
288 end
= value
->use_end(); begin
!= end
; ++begin
) {
289 Instruction
*I
= cast
<Instruction
>(*begin
);
290 BasicBlock
*BB_father
= I
->getParent();
291 if (BB
== BB_father
&& isa
<PHINode
>(I
))
293 if (DT_
->dominates(BB
, BB_father
)) {
300 /// When there is a phi node that is created in a BasicBlock and it is used
301 /// as an operand of another phi function used in the same BasicBlock,
302 /// LLVM looks this as an error. So on the second phi, the first phi is called
303 /// P and the BasicBlock it incomes is B. This P will be replaced by the value
304 /// it has for BasicBlock B. It also includes undef values for predecessors
305 /// that were not included in the phi.
307 void SSI::fixPhis() {
308 for (SmallPtrSet
<PHINode
*, 1>::iterator begin
= phisToFix
.begin(),
309 end
= phisToFix
.end(); begin
!= end
; ++begin
) {
310 PHINode
*PN
= *begin
;
311 for (unsigned i
= 0, e
= PN
->getNumIncomingValues(); i
< e
; ++i
) {
312 PHINode
*PN_father
= dyn_cast
<PHINode
>(PN
->getIncomingValue(i
));
313 if (PN_father
&& PN
->getParent() == PN_father
->getParent() &&
314 !DT_
->dominates(PN
->getParent(), PN
->getIncomingBlock(i
))) {
315 BasicBlock
*BB
= PN
->getIncomingBlock(i
);
316 int pos
= PN_father
->getBasicBlockIndex(BB
);
317 PN
->setIncomingValue(i
, PN_father
->getIncomingValue(pos
));
322 for (DenseMapIterator
<PHINode
*, Instruction
*> begin
= phis
.begin(),
323 end
= phis
.end(); begin
!= end
; ++begin
) {
324 PHINode
*PN
= begin
->first
;
325 BasicBlock
*BB
= PN
->getParent();
326 pred_iterator PI
= pred_begin(BB
), PE
= pred_end(BB
);
327 SmallVector
<BasicBlock
*, 8> Preds(PI
, PE
);
328 for (unsigned size
= Preds
.size();
329 PI
!= PE
&& PN
->getNumIncomingValues() != size
; ++PI
) {
331 for (unsigned i
= 0, pn_end
= PN
->getNumIncomingValues();
333 if (PN
->getIncomingBlock(i
) == *PI
) {
339 PN
->addIncoming(UndefValue::get(PN
->getType()), *PI
);
345 /// Return which variable (position on the vector of variables) this phi
346 /// represents on the phis list.
348 Instruction
* SSI::getPositionPhi(PHINode
*PN
) {
349 DenseMap
<PHINode
*, Instruction
*>::iterator val
= phis
.find(PN
);
350 if (val
== phis
.end())
356 /// Return which variable (position on the vector of variables) this phi
357 /// represents on the sigmas list.
359 Instruction
* SSI::getPositionSigma(PHINode
*PN
) {
360 DenseMap
<PHINode
*, Instruction
*>::iterator val
= sigmas
.find(PN
);
361 if (val
== sigmas
.end())
369 void SSI::init(SmallVectorImpl
<Instruction
*> &value
) {
370 for (SmallVectorImpl
<Instruction
*>::iterator I
= value
.begin(),
371 E
= value
.end(); I
!= E
; ++I
) {
372 value_original
[*I
] = (*I
)->getParent();
373 defsites
[*I
].push_back((*I
)->getParent());
377 /// Clean all used resources in this creation of SSI
386 value_original
.clear();
389 /// createSSIPass - The public interface to this file...
391 FunctionPass
*llvm::createSSIPass() { return new SSI(); }
394 static RegisterPass
<SSI
> X("ssi", "Static Single Information Construction");
396 /// SSIEverything - A pass that runs createSSI on every non-void variable,
397 /// intended for debugging.
399 struct SSIEverything
: public FunctionPass
{
400 static char ID
; // Pass identification, replacement for typeid
401 SSIEverything() : FunctionPass(&ID
) {}
403 bool runOnFunction(Function
&F
);
405 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
406 AU
.addRequired
<SSI
>();
411 bool SSIEverything::runOnFunction(Function
&F
) {
412 SmallVector
<Instruction
*, 16> Insts
;
413 SSI
&ssi
= getAnalysis
<SSI
>();
415 if (F
.isDeclaration() || F
.isIntrinsic()) return false;
417 for (Function::iterator B
= F
.begin(), BE
= F
.end(); B
!= BE
; ++B
)
418 for (BasicBlock::iterator I
= B
->begin(), E
= B
->end(); I
!= E
; ++I
)
419 if (!I
->getType()->isVoidTy())
422 ssi
.createSSI(Insts
);
426 /// createSSIEverythingPass - The public interface to this file...
428 FunctionPass
*llvm::createSSIEverythingPass() { return new SSIEverything(); }
430 char SSIEverything::ID
= 0;
431 static RegisterPass
<SSIEverything
>
432 Y("ssi-everything", "Static Single Information Construction");