lib/Transforms/Utils/SSI.cpp

   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.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #define DEBUG_TYPE "ssi"
  23
  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"
  28
  29 using namespace llvm;
  30
  31 static const std::string SSI_PHI = "SSI_phi";
  32 static const std::string SSI_SIG = "SSI_sigma";
  33
  34 static const unsigned UNSIGNED_INFINITE = ~0U;
  35
  36 STATISTIC(NumSigmaInserted, "Number of sigma functions inserted");
  37 STATISTIC(NumPhiInserted, "Number of phi functions inserted");
  38
  39 void SSI::getAnalysisUsage(AnalysisUsage &AU) const {
  40   AU.addRequired<DominanceFrontier>();
  41   AU.addRequired<DominatorTree>();
  42   AU.setPreservesCFG();
  43 }
  44
  45 bool SSI::runOnFunction(Function &F) {
  46   DT_ = &getAnalysis<DominatorTree>();
  47   return false;
  48 }
  49
  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.
  53 ///
  54 void SSI::createSSI(SmallVectorImpl<Instruction *> &value) {
  55   init(value);
  56
  57   for (unsigned i = 0; i < num_values; ++i) {
  58     if (created.insert(value[i])) {
  59       needConstruction[i] = true;
  60     }
  61   }
  62   insertSigmaFunctions(value);
  63
  64   // Test if there is a need to transform to SSI
  65   if (needConstruction.any()) {
  66     insertPhiFunctions(value);
  67     renameInit(value);
  68     rename(DT_->getRoot());
  69     fixPhis();
  70   }
  71
  72   clean();
  73 }
  74
  75 /// Insert sigma functions (a sigma function is a phi function with one
  76 /// operator)
  77 ///
  78 void SSI::insertSigmaFunctions(SmallVectorImpl<Instruction *> &value) {
  79   for (unsigned i = 0; i < num_values; ++i) {
  80     if (!needConstruction[i])
  81       continue;
  82
  83     for (Value::use_iterator begin = value[i]->use_begin(), end =
  84          value[i]->use_end(); begin != end; ++begin) {
  85       // Test if the Use of the Value is in a comparator
  86       if (CmpInst *CI = dyn_cast<CmpInst>(begin)) {
  87         // Iterates through all uses of CmpInst
  88         for (Value::use_iterator begin_ci = CI->use_begin(), end_ci =
  89              CI->use_end(); begin_ci != end_ci; ++begin_ci) {
  90           // Test if any use of CmpInst is in a Terminator
  91           if (TerminatorInst *TI = dyn_cast<TerminatorInst>(begin_ci)) {
  92             insertSigma(TI, value[i], i);
  93           }
  94         }
  95       }
  96     }
  97   }
  98 }
  99
 100 /// Inserts Sigma Functions in every BasicBlock successor to Terminator
 101 /// Instruction TI. All inserted Sigma Function are related to Instruction I.
 102 ///
 103 void SSI::insertSigma(TerminatorInst *TI, Instruction *I, unsigned pos) {
 104   // Basic Block of the Terminator Instruction
 105   BasicBlock *BB = TI->getParent();
 106   for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
 107     // Next Basic Block
 108     BasicBlock *BB_next = TI->getSuccessor(i);
 109     if (BB_next != BB &&
 110         BB_next->getSinglePredecessor() != NULL &&
 111         dominateAny(BB_next, I)) {
 112       PHINode *PN = PHINode::Create(I->getType(), SSI_SIG, BB_next->begin());
 113       PN->addIncoming(I, BB);
 114       sigmas.insert(std::make_pair(PN, pos));
 115       created.insert(PN);
 116       needConstruction[pos] = true;
 117       defsites[pos].push_back(BB_next);
 118       ++NumSigmaInserted;
 119     }
 120   }
 121 }
 122
 123 /// Insert phi functions when necessary
 124 ///
 125 void SSI::insertPhiFunctions(SmallVectorImpl<Instruction *> &value) {
 126   DominanceFrontier *DF = &getAnalysis<DominanceFrontier>();
 127   for (unsigned i = 0; i < num_values; ++i) {
 128     // Test if there were any sigmas for this variable
 129     if (needConstruction[i]) {
 130
 131       SmallPtrSet<BasicBlock *, 16> BB_visited;
 132
 133       // Insert phi functions if there is any sigma function
 134       while (!defsites[i].empty()) {
 135
 136         BasicBlock *BB = defsites[i].back();
 137
 138         defsites[i].pop_back();
 139         DominanceFrontier::iterator DF_BB = DF->find(BB);
 140
 141         // The BB is unreachable. Skip it.
 142         if (DF_BB == DF->end())
 143           continue;
 144
 145         // Iterates through all the dominance frontier of BB
 146         for (std::set<BasicBlock *>::iterator DF_BB_begin =
 147              DF_BB->second.begin(), DF_BB_end = DF_BB->second.end();
 148              DF_BB_begin != DF_BB_end; ++DF_BB_begin) {
 149           BasicBlock *BB_dominated = *DF_BB_begin;
 150
 151           // Test if has not yet visited this node and if the
 152           // original definition dominates this node
 153           if (BB_visited.insert(BB_dominated) &&
 154               DT_->properlyDominates(value_original[i], BB_dominated) &&
 155               dominateAny(BB_dominated, value[i])) {
 156             PHINode *PN = PHINode::Create(
 157                 value[i]->getType(), SSI_PHI, BB_dominated->begin());
 158             phis.insert(std::make_pair(PN, i));
 159             created.insert(PN);
 160
 161             defsites[i].push_back(BB_dominated);
 162             ++NumPhiInserted;
 163           }
 164         }
 165       }
 166       BB_visited.clear();
 167     }
 168   }
 169 }
 170
 171 /// Some initialization for the rename part
 172 ///
 173 void SSI::renameInit(SmallVectorImpl<Instruction *> &value) {
 174   value_stack.resize(num_values);
 175   for (unsigned i = 0; i < num_values; ++i) {
 176     value_stack[i].push_back(value[i]);
 177   }
 178 }
 179
 180 /// Renames all variables in the specified BasicBlock.
 181 /// Only variables that need to be rename will be.
 182 ///
 183 void SSI::rename(BasicBlock *BB) {
 184   BitVector *defined = new BitVector(num_values, false);
 185
 186   // Iterate through instructions and make appropriate renaming.
 187   // For SSI_PHI (b = PHI()), store b at value_stack as a new
 188   // definition of the variable it represents.
 189   // For SSI_SIG (b = PHI(a)), substitute a with the current
 190   // value of a, present in the value_stack.
 191   // Then store bin the value_stack as the new definition of a.
 192   // For all other instructions (b = OP(a, c, d, ...)), we need to substitute
 193   // all operands with its current value, present in value_stack.
 194   for (BasicBlock::iterator begin = BB->begin(), end = BB->end();
 195        begin != end; ++begin) {
 196     Instruction *I = begin;
 197     if (PHINode *PN = dyn_cast<PHINode>(I)) { // Treat PHI functions
 198       int position;
 199
 200       // Treat SSI_PHI
 201       if ((position = getPositionPhi(PN)) != -1) {
 202         value_stack[position].push_back(PN);
 203         (*defined)[position] = true;
 204       }
 205
 206       // Treat SSI_SIG
 207       else if ((position = getPositionSigma(PN)) != -1) {
 208         substituteUse(I);
 209         value_stack[position].push_back(PN);
 210         (*defined)[position] = true;
 211       }
 212
 213       // Treat all other PHI functions
 214       else {
 215         substituteUse(I);
 216       }
 217     }
 218
 219     // Treat all other functions
 220     else {
 221       substituteUse(I);
 222     }
 223   }
 224
 225   // This loop iterates in all BasicBlocks that are successors of the current
 226   // BasicBlock. For each SSI_PHI instruction found, insert an operand.
 227   // This operand is the current operand in value_stack for the variable
 228   // in "position". And the BasicBlock this operand represents is the current
 229   // BasicBlock.
 230   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) {
 231     BasicBlock *BB_succ = *SI;
 232
 233     for (BasicBlock::iterator begin = BB_succ->begin(),
 234          notPhi = BB_succ->getFirstNonPHI(); begin != *notPhi; ++begin) {
 235       Instruction *I = begin;
 236       PHINode *PN = dyn_cast<PHINode>(I);
 237       int position;
 238       if (PN && ((position = getPositionPhi(PN)) != -1)) {
 239         PN->addIncoming(value_stack[position].back(), BB);
 240       }
 241     }
 242   }
 243
 244   // This loop calls rename on all children from this block. This time children
 245   // refers to a successor block in the dominance tree.
 246   DomTreeNode *DTN = DT_->getNode(BB);
 247   for (DomTreeNode::iterator begin = DTN->begin(), end = DTN->end();
 248        begin != end; ++begin) {
 249     DomTreeNodeBase<BasicBlock> *DTN_children = *begin;
 250     BasicBlock *BB_children = DTN_children->getBlock();
 251     rename(BB_children);
 252   }
 253
 254   // Now we remove all inserted definitions of a variable from the top of
 255   // the stack leaving the previous one as the top.
 256   if (defined->any()) {
 257     for (unsigned i = 0; i < num_values; ++i) {
 258       if ((*defined)[i]) {
 259         value_stack[i].pop_back();
 260       }
 261     }
 262   }
 263
 264   delete defined;
 265 }
 266
 267 /// Substitute any use in this instruction for the last definition of
 268 /// the variable
 269 ///
 270 void SSI::substituteUse(Instruction *I) {
 271   for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
 272     Value *operand = I->getOperand(i);
 273     for (unsigned j = 0; j < num_values; ++j) {
 274       if (operand == value_stack[j].front() &&
 275           I != value_stack[j].back()) {
 276         PHINode *PN_I = dyn_cast<PHINode>(I);
 277         PHINode *PN_vs = dyn_cast<PHINode>(value_stack[j].back());
 278
 279         // If a phi created in a BasicBlock is used as an operand of another
 280         // created in the same BasicBlock, this step marks this second phi,
 281         // to fix this issue later. It cannot be fixed now, because the
 282         // operands of the first phi are not final yet.
 283         if (PN_I && PN_vs &&
 284             value_stack[j].back()->getParent() == I->getParent()) {
 285
 286           phisToFix.insert(PN_I);
 287         }
 288
 289         I->setOperand(i, value_stack[j].back());
 290         break;
 291       }
 292     }
 293   }
 294 }
 295
 296 /// Test if the BasicBlock BB dominates any use or definition of value.
 297 /// If it dominates a phi instruction that is on the same BasicBlock,
 298 /// that does not count.
 299 ///
 300 bool SSI::dominateAny(BasicBlock *BB, Instruction *value) {
 301   for (Value::use_iterator begin = value->use_begin(),
 302        end = value->use_end(); begin != end; ++begin) {
 303     Instruction *I = cast<Instruction>(*begin);
 304     BasicBlock *BB_father = I->getParent();
 305     if (BB == BB_father && isa<PHINode>(I))
 306       continue;
 307     if (DT_->dominates(BB, BB_father)) {
 308       return true;
 309     }
 310   }
 311   return false;
 312 }
 313
 314 /// When there is a phi node that is created in a BasicBlock and it is used
 315 /// as an operand of another phi function used in the same BasicBlock,
 316 /// LLVM looks this as an error. So on the second phi, the first phi is called
 317 /// P and the BasicBlock it incomes is B. This P will be replaced by the value
 318 /// it has for BasicBlock B. It also includes undef values for predecessors
 319 /// that were not included in the phi.
 320 ///
 321 void SSI::fixPhis() {
 322   for (SmallPtrSet<PHINode *, 1>::iterator begin = phisToFix.begin(),
 323        end = phisToFix.end(); begin != end; ++begin) {
 324     PHINode *PN = *begin;
 325     for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
 326       PHINode *PN_father = dyn_cast<PHINode>(PN->getIncomingValue(i));
 327       if (PN_father && PN->getParent() == PN_father->getParent() &&
 328           !DT_->dominates(PN->getParent(), PN->getIncomingBlock(i))) {
 329         BasicBlock *BB = PN->getIncomingBlock(i);
 330         int pos = PN_father->getBasicBlockIndex(BB);
 331         PN->setIncomingValue(i, PN_father->getIncomingValue(pos));
 332       }
 333     }
 334   }
 335
 336   for (DenseMapIterator<PHINode *, unsigned> begin = phis.begin(),
 337        end = phis.end(); begin != end; ++begin) {
 338     PHINode *PN = begin->first;
 339     BasicBlock *BB = PN->getParent();
 340     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 341     SmallVector<BasicBlock*, 8> Preds(PI, PE);
 342     for (unsigned size = Preds.size();
 343          PI != PE && PN->getNumIncomingValues() != size; ++PI) {
 344       bool found = false;
 345       for (unsigned i = 0, pn_end = PN->getNumIncomingValues();
 346            i < pn_end; ++i) {
 347         if (PN->getIncomingBlock(i) == *PI) {
 348           found = true;
 349           break;
 350         }
 351       }
 352       if (!found) {
 353         PN->addIncoming(UndefValue::get(PN->getType()), *PI);
 354       }
 355     }
 356   }
 357 }
 358
 359 /// Return which variable (position on the vector of variables) this phi
 360 /// represents on the phis list.
 361 ///
 362 unsigned SSI::getPositionPhi(PHINode *PN) {
 363   DenseMap<PHINode *, unsigned>::iterator val = phis.find(PN);
 364   if (val == phis.end())
 365     return UNSIGNED_INFINITE;
 366   else
 367     return val->second;
 368 }
 369
 370 /// Return which variable (position on the vector of variables) this phi
 371 /// represents on the sigmas list.
 372 ///
 373 unsigned SSI::getPositionSigma(PHINode *PN) {
 374   DenseMap<PHINode *, unsigned>::iterator val = sigmas.find(PN);
 375   if (val == sigmas.end())
 376     return UNSIGNED_INFINITE;
 377   else
 378     return val->second;
 379 }
 380
 381 /// Initializes
 382 ///
 383 void SSI::init(SmallVectorImpl<Instruction *> &value) {
 384   num_values = value.size();
 385   needConstruction.resize(num_values, false);
 386
 387   value_original.resize(num_values);
 388   defsites.resize(num_values);
 389
 390   for (unsigned i = 0; i < num_values; ++i) {
 391     value_original[i] = value[i]->getParent();
 392     defsites[i].push_back(value_original[i]);
 393   }
 394 }
 395
 396 /// Clean all used resources in this creation of SSI
 397 ///
 398 void SSI::clean() {
 399   for (unsigned i = 0; i < num_values; ++i) {
 400     defsites[i].clear();
 401     if (i < value_stack.size())
 402       value_stack[i].clear();
 403   }
 404
 405   phis.clear();
 406   sigmas.clear();
 407   phisToFix.clear();
 408
 409   defsites.clear();
 410   value_stack.clear();
 411   value_original.clear();
 412   needConstruction.clear();
 413 }
 414
 415 /// createSSIPass - The public interface to this file...
 416 ///
 417 FunctionPass *llvm::createSSIPass() { return new SSI(); }
 418
 419 char SSI::ID = 0;
 420 static RegisterPass<SSI> X("ssi", "Static Single Information Construction");
 421
 422 /// SSIEverything - A pass that runs createSSI on every non-void variable,
 423 /// intended for debugging.
 424 namespace {
 425   struct VISIBILITY_HIDDEN SSIEverything : public FunctionPass {
 426     static char ID; // Pass identification, replacement for typeid
 427     SSIEverything() : FunctionPass(&ID) {}
 428
 429     bool runOnFunction(Function &F);
 430
 431     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 432       AU.addRequired<SSI>();
 433     }
 434   };
 435 }
 436
 437 bool SSIEverything::runOnFunction(Function &F) {
 438   SmallVector<Instruction *, 16> Insts;
 439   SSI &ssi = getAnalysis<SSI>();
 440
 441   if (F.isDeclaration() || F.isIntrinsic()) return false;
 442
 443   for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B)
 444     for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I)
 445       if (I->getType() != Type::getVoidTy(F.getContext()))
 446         Insts.push_back(I);
 447
 448   ssi.createSSI(Insts);
 449   return true;
 450 }
 451
 452 /// createSSIEverythingPass - The public interface to this file...
 453 ///
 454 FunctionPass *llvm::createSSIEverythingPass() { return new SSIEverything(); }
 455
 456 char SSIEverything::ID = 0;
 457 static RegisterPass<SSIEverything>
 458 Y("ssi-everything", "Static Single Information Construction");