While DAE can't modify the function signature of an externally visible function,
[llvm.git] / lib / Transforms / Utils / SSI.cpp
blob4e813ddf95c7d44593965775d1f8f1e23bdb36b0
1 //===------------------- SSI.cpp - Creates SSI Representation -------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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"
29 using namespace llvm;
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>();
40 AU.setPreservesAll();
43 bool SSI::runOnFunction(Function &F) {
44 DT_ = &getAnalysis<DominatorTree>();
45 return false;
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.
51 ///
52 void SSI::createSSI(SmallVectorImpl<Instruction *> &value) {
53 init(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());
68 fixPhis();
71 clean();
74 /// Insert sigma functions (a sigma function is a phi function with one
75 /// operator)
76 ///
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)) {
89 insertSigma(TI, *I);
97 /// Inserts Sigma Functions in every BasicBlock successor to Terminator
98 /// Instruction TI. All inserted Sigma Function are related to Instruction I.
99 ///
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) {
104 // Next Basic Block
105 BasicBlock *BB_next = TI->getSuccessor(i);
106 if (BB_next != BB &&
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);
111 sigmas[PN] = I;
112 created.insert(PN);
113 defsites[I].push_back(BB_next);
114 ++NumSigmaInserted;
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())
138 continue;
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));
154 created.insert(PN);
156 defsites[*I].push_back(BB_dominated);
157 ++NumPhiInserted;
161 BB_visited.clear();
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;
193 // Treat SSI_PHI
194 if ((position = getPositionPhi(PN))) {
195 value_stack[position].push_back(PN);
196 defined.insert(position);
197 // Treat SSI_SIG
198 } else if ((position = getPositionSigma(PN))) {
199 substituteUse(I);
200 value_stack[position].push_back(PN);
201 defined.insert(position);
204 // Treat all other PHI functions
205 else {
206 substituteUse(I);
210 // Treat all other functions
211 else {
212 substituteUse(I);
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
220 // BasicBlock.
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();
242 rename(BB_children);
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
253 /// the variable
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.
269 if (PN_I && PN_vs &&
270 VI->second.back()->getParent() == I->getParent()) {
272 phisToFix.insert(PN_I);
275 I->setOperand(i, VI->second.back());
276 break;
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))
292 continue;
293 if (DT_->dominates(BB, BB_father)) {
294 return true;
297 return false;
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) {
330 bool found = false;
331 for (unsigned i = 0, pn_end = PN->getNumIncomingValues();
332 i < pn_end; ++i) {
333 if (PN->getIncomingBlock(i) == *PI) {
334 found = true;
335 break;
338 if (!found) {
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())
351 return 0;
352 else
353 return val->second;
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())
362 return 0;
363 else
364 return val->second;
367 /// Initializes
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
379 void SSI::clean() {
380 phis.clear();
381 sigmas.clear();
382 phisToFix.clear();
384 defsites.clear();
385 value_stack.clear();
386 value_original.clear();
389 /// createSSIPass - The public interface to this file...
391 FunctionPass *llvm::createSSIPass() { return new SSI(); }
393 char SSI::ID = 0;
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.
398 namespace {
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())
420 Insts.push_back(I);
422 ssi.createSSI(Insts);
423 return true;
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");