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 static const unsigned UNSIGNED_INFINITE = ~0U;
36 STATISTIC(NumSigmaInserted, "Number of sigma functions inserted");
37 STATISTIC(NumPhiInserted, "Number of phi functions inserted");
39 void SSI::getAnalysisUsage(AnalysisUsage &AU) const {
40 AU.addRequired<DominanceFrontier>();
41 AU.addRequired<DominatorTree>();
45 bool SSI::runOnFunction(Function &F) {
46 DT_ = &getAnalysis<DominatorTree>();
50 /// This methods creates the SSI representation for the list of values
51 /// received. It will only create SSI representation if a value is used
52 /// in a to decide a branch. Repeated values are created only once.
54 void SSI::createSSI(SmallVectorImpl<Instruction *> &value) {
57 for (unsigned i = 0; i < num_values; ++i) {
58 if (created.insert(value[i])) {
59 needConstruction[i] = true;
62 insertSigmaFunctions(value);
64 // Test if there is a need to transform to SSI
65 if (needConstruction.any()) {
66 insertPhiFunctions(value);
68 rename(DT_->getRoot());
75 /// Insert sigma functions (a sigma function is a phi function with one
78 void SSI::insertSigmaFunctions(SmallVectorImpl<Instruction *> &value) {
79 for (unsigned i = 0; i < num_values; ++i) {
80 if (!needConstruction[i])
84 for (Value::use_iterator begin = value[i]->use_begin(), end =
85 value[i]->use_end(); begin != end; ++begin) {
86 // Test if the Use of the Value is in a comparator
87 CmpInst *CI = dyn_cast<CmpInst>(begin);
88 if (CI && isUsedInTerminator(CI)) {
89 // Basic Block of the Instruction
90 BasicBlock *BB = CI->getParent();
91 // Last Instruction of the Basic Block
92 const TerminatorInst *TI = BB->getTerminator();
94 for (unsigned j = 0, e = TI->getNumSuccessors(); j < e; ++j) {
96 BasicBlock *BB_next = TI->getSuccessor(j);
98 BB_next->getSinglePredecessor() != NULL &&
99 dominateAny(BB_next, value[i])) {
100 PHINode *PN = PHINode::Create(
101 value[i]->getType(), SSI_SIG, BB_next->begin());
102 PN->addIncoming(value[i], BB);
103 sigmas.insert(std::make_pair(PN, i));
106 defsites[i].push_back(BB_next);
112 needConstruction[i] = need;
116 /// Insert phi functions when necessary
118 void SSI::insertPhiFunctions(SmallVectorImpl<Instruction *> &value) {
119 DominanceFrontier *DF = &getAnalysis<DominanceFrontier>();
120 for (unsigned i = 0; i < num_values; ++i) {
121 // Test if there were any sigmas for this variable
122 if (needConstruction[i]) {
124 SmallPtrSet<BasicBlock *, 16> BB_visited;
126 // Insert phi functions if there is any sigma function
127 while (!defsites[i].empty()) {
129 BasicBlock *BB = defsites[i].back();
131 defsites[i].pop_back();
132 DominanceFrontier::iterator DF_BB = DF->find(BB);
134 // The BB is unreachable. Skip it.
135 if (DF_BB == DF->end())
138 // Iterates through all the dominance frontier of BB
139 for (std::set<BasicBlock *>::iterator DF_BB_begin =
140 DF_BB->second.begin(), DF_BB_end = DF_BB->second.end();
141 DF_BB_begin != DF_BB_end; ++DF_BB_begin) {
142 BasicBlock *BB_dominated = *DF_BB_begin;
144 // Test if has not yet visited this node and if the
145 // original definition dominates this node
146 if (BB_visited.insert(BB_dominated) &&
147 DT_->properlyDominates(value_original[i], BB_dominated) &&
148 dominateAny(BB_dominated, value[i])) {
149 PHINode *PN = PHINode::Create(
150 value[i]->getType(), SSI_PHI, BB_dominated->begin());
151 phis.insert(std::make_pair(PN, i));
154 defsites[i].push_back(BB_dominated);
164 /// Some initialization for the rename part
166 void SSI::renameInit(SmallVectorImpl<Instruction *> &value) {
167 value_stack.resize(num_values);
168 for (unsigned i = 0; i < num_values; ++i) {
169 value_stack[i].push_back(value[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 BitVector *defined = new BitVector(num_values, false);
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
194 if ((position = getPositionPhi(PN)) != -1) {
195 value_stack[position].push_back(PN);
196 (*defined)[position] = true;
200 else if ((position = getPositionSigma(PN)) != -1) {
202 value_stack[position].push_back(PN);
203 (*defined)[position] = true;
206 // Treat all other PHI functions
212 // Treat all other functions
218 // This loop iterates in all BasicBlocks that are successors of the current
219 // BasicBlock. For each SSI_PHI instruction found, insert an operand.
220 // This operand is the current operand in value_stack for the variable
221 // in "position". And the BasicBlock this operand represents is the current
223 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) {
224 BasicBlock *BB_succ = *SI;
226 for (BasicBlock::iterator begin = BB_succ->begin(),
227 notPhi = BB_succ->getFirstNonPHI(); begin != *notPhi; ++begin) {
228 Instruction *I = begin;
231 if ((PN = dyn_cast<PHINode>(I)) && ((position
232 = getPositionPhi(PN)) != -1)) {
233 PN->addIncoming(value_stack[position].back(), BB);
238 // This loop calls rename on all children from this block. This time children
239 // refers to a successor block in the dominance tree.
240 DomTreeNode *DTN = DT_->getNode(BB);
241 for (DomTreeNode::iterator begin = DTN->begin(), end = DTN->end();
242 begin != end; ++begin) {
243 DomTreeNodeBase<BasicBlock> *DTN_children = *begin;
244 BasicBlock *BB_children = DTN_children->getBlock();
248 // Now we remove all inserted definitions of a variable from the top of
249 // the stack leaving the previous one as the top.
250 if (defined->any()) {
251 for (unsigned i = 0; i < num_values; ++i) {
253 value_stack[i].pop_back();
259 /// Substitute any use in this instruction for the last definition of
262 void SSI::substituteUse(Instruction *I) {
263 for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
264 Value *operand = I->getOperand(i);
265 for (unsigned j = 0; j < num_values; ++j) {
266 if (operand == value_stack[j].front() &&
267 I != value_stack[j].back()) {
268 PHINode *PN_I = dyn_cast<PHINode>(I);
269 PHINode *PN_vs = dyn_cast<PHINode>(value_stack[j].back());
271 // If a phi created in a BasicBlock is used as an operand of another
272 // created in the same BasicBlock, this step marks this second phi,
273 // to fix this issue later. It cannot be fixed now, because the
274 // operands of the first phi are not final yet.
276 value_stack[j].back()->getParent() == I->getParent()) {
278 phisToFix.insert(PN_I);
281 I->setOperand(i, value_stack[j].back());
288 /// Test if the BasicBlock BB dominates any use or definition of value.
289 /// If it dominates a phi instruction that is on the same BasicBlock,
290 /// that does not count.
292 bool SSI::dominateAny(BasicBlock *BB, Instruction *value) {
293 for (Value::use_iterator begin = value->use_begin(),
294 end = value->use_end(); begin != end; ++begin) {
295 Instruction *I = cast<Instruction>(*begin);
296 BasicBlock *BB_father = I->getParent();
297 if (BB == BB_father && isa<PHINode>(I))
299 if (DT_->dominates(BB, BB_father)) {
306 /// When there is a phi node that is created in a BasicBlock and it is used
307 /// as an operand of another phi function used in the same BasicBlock,
308 /// LLVM looks this as an error. So on the second phi, the first phi is called
309 /// P and the BasicBlock it incomes is B. This P will be replaced by the value
310 /// it has for BasicBlock B.
312 void SSI::fixPhis() {
313 for (SmallPtrSet<PHINode *, 1>::iterator begin = phisToFix.begin(),
314 end = phisToFix.end(); begin != end; ++begin) {
315 PHINode *PN = *begin;
316 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
318 if ((PN_father = dyn_cast<PHINode>(PN->getIncomingValue(i))) &&
319 PN->getParent() == PN_father->getParent() &&
320 !DT_->dominates(PN->getParent(), PN->getIncomingBlock(i))) {
321 BasicBlock *BB = PN->getIncomingBlock(i);
322 int pos = PN_father->getBasicBlockIndex(BB);
323 PN->setIncomingValue(i, PN_father->getIncomingValue(pos));
329 /// Return which variable (position on the vector of variables) this phi
330 /// represents on the phis list.
332 unsigned SSI::getPositionPhi(PHINode *PN) {
333 DenseMap<PHINode *, unsigned>::iterator val = phis.find(PN);
334 if (val == phis.end())
335 return UNSIGNED_INFINITE;
340 /// Return which variable (position on the vector of variables) this phi
341 /// represents on the sigmas list.
343 unsigned SSI::getPositionSigma(PHINode *PN) {
344 DenseMap<PHINode *, unsigned>::iterator val = sigmas.find(PN);
345 if (val == sigmas.end())
346 return UNSIGNED_INFINITE;
351 /// Return true if the the Comparison Instruction is an operator
352 /// of the Terminator instruction of its Basic Block.
354 unsigned SSI::isUsedInTerminator(CmpInst *CI) {
355 TerminatorInst *TI = CI->getParent()->getTerminator();
356 if (TI->getNumOperands() == 0) {
358 } else if (CI == TI->getOperand(0)) {
367 void SSI::init(SmallVectorImpl<Instruction *> &value) {
368 num_values = value.size();
369 needConstruction.resize(num_values, false);
371 value_original.resize(num_values);
372 defsites.resize(num_values);
374 for (unsigned i = 0; i < num_values; ++i) {
375 value_original[i] = value[i]->getParent();
376 defsites[i].push_back(value_original[i]);
380 /// Clean all used resources in this creation of SSI
383 for (unsigned i = 0; i < num_values; ++i) {
385 if (i < value_stack.size())
386 value_stack[i].clear();
395 value_original.clear();
396 needConstruction.clear();
399 /// createSSIPass - The public interface to this file...
401 FunctionPass *llvm::createSSIPass() { return new SSI(); }
404 static RegisterPass<SSI> X("ssi", "Static Single Information Construction");
406 /// SSIEverything - A pass that runs createSSI on every non-void variable,
407 /// intended for debugging.
409 struct VISIBILITY_HIDDEN SSIEverything : public FunctionPass {
410 static char ID; // Pass identification, replacement for typeid
411 SSIEverything() : FunctionPass(&ID) {}
413 bool runOnFunction(Function &F);
415 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
416 AU.addRequired<SSI>();
421 bool SSIEverything::runOnFunction(Function &F) {
422 SmallVector<Instruction *, 16> Insts;
423 SSI &ssi = getAnalysis<SSI>();
425 if (F.isDeclaration() || F.isIntrinsic()) return false;
427 for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B)
428 for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I)
429 if (I->getType() != Type::getVoidTy(F.getContext()))
432 ssi.createSSI(Insts);
436 /// createSSIEverythingPass - The public interface to this file...
438 FunctionPass *llvm::createSSIEverythingPass() { return new SSIEverything(); }
440 char SSIEverything::ID = 0;
441 static RegisterPass<SSIEverything>
442 Y("ssi-everything", "Static Single Information Construction");