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     bool need = false;
  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();
  93
  94         for (unsigned j = 0, e = TI->getNumSuccessors(); j < e; ++j) {
  95           // Next Basic Block
  96           BasicBlock *BB_next = TI->getSuccessor(j);
  97           if (BB_next != BB &&
  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));
 104             created.insert(PN);
 105             need = true;
 106             defsites[i].push_back(BB_next);
 107             ++NumSigmaInserted;
 108           }
 109         }
 110       }
 111     }
 112     needConstruction[i] = need;
 113   }
 114 }
 115
 116 /// Insert phi functions when necessary
 117 ///
 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]) {
 123
 124       SmallPtrSet<BasicBlock *, 16> BB_visited;
 125
 126       // Insert phi functions if there is any sigma function
 127       while (!defsites[i].empty()) {
 128
 129         BasicBlock *BB = defsites[i].back();
 130
 131         defsites[i].pop_back();
 132         DominanceFrontier::iterator DF_BB = DF->find(BB);
 133
 134         // The BB is unreachable. Skip it.
 135         if (DF_BB == DF->end())
 136           continue;
 137
 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;
 143
 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));
 152             created.insert(PN);
 153
 154             defsites[i].push_back(BB_dominated);
 155             ++NumPhiInserted;
 156           }
 157         }
 158       }
 159       BB_visited.clear();
 160     }
 161   }
 162 }
 163
 164 /// Some initialization for the rename part
 165 ///
 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]);
 170   }
 171 }
 172
 173 /// Renames all variables in the specified BasicBlock.
 174 /// Only variables that need to be rename will be.
 175 ///
 176 void SSI::rename(BasicBlock *BB) {
 177   BitVector *defined = new BitVector(num_values, false);
 178
 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       int position;
 192
 193       // Treat SSI_PHI
 194       if ((position = getPositionPhi(PN)) != -1) {
 195         value_stack[position].push_back(PN);
 196         (*defined)[position] = true;
 197       }
 198
 199       // Treat SSI_SIG
 200       else if ((position = getPositionSigma(PN)) != -1) {
 201         substituteUse(I);
 202         value_stack[position].push_back(PN);
 203         (*defined)[position] = true;
 204       }
 205
 206       // Treat all other PHI functions
 207       else {
 208         substituteUse(I);
 209       }
 210     }
 211
 212     // Treat all other functions
 213     else {
 214       substituteUse(I);
 215     }
 216   }
 217
 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
 222   // BasicBlock.
 223   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) {
 224     BasicBlock *BB_succ = *SI;
 225
 226     for (BasicBlock::iterator begin = BB_succ->begin(),
 227          notPhi = BB_succ->getFirstNonPHI(); begin != *notPhi; ++begin) {
 228       Instruction *I = begin;
 229       PHINode *PN;
 230       int position;
 231       if ((PN = dyn_cast<PHINode>(I)) && ((position
 232           = getPositionPhi(PN)) != -1)) {
 233         PN->addIncoming(value_stack[position].back(), BB);
 234       }
 235     }
 236   }
 237
 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();
 245     rename(BB_children);
 246   }
 247
 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) {
 252       if ((*defined)[i]) {
 253         value_stack[i].pop_back();
 254       }
 255     }
 256   }
 257 }
 258
 259 /// Substitute any use in this instruction for the last definition of
 260 /// the variable
 261 ///
 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());
 270
 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.
 275         if (PN_I && PN_vs &&
 276             value_stack[j].back()->getParent() == I->getParent()) {
 277
 278           phisToFix.insert(PN_I);
 279         }
 280
 281         I->setOperand(i, value_stack[j].back());
 282         break;
 283       }
 284     }
 285   }
 286 }
 287
 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.
 291 ///
 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))
 298       continue;
 299     if (DT_->dominates(BB, BB_father)) {
 300       return true;
 301     }
 302   }
 303   return false;
 304 }
 305
 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.
 311 ///
 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) {
 317       PHINode *PN_father;
 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));
 324       }
 325     }
 326   }
 327 }
 328
 329 /// Return which variable (position on the vector of variables) this phi
 330 /// represents on the phis list.
 331 ///
 332 unsigned SSI::getPositionPhi(PHINode *PN) {
 333   DenseMap<PHINode *, unsigned>::iterator val = phis.find(PN);
 334   if (val == phis.end())
 335     return UNSIGNED_INFINITE;
 336   else
 337     return val->second;
 338 }
 339
 340 /// Return which variable (position on the vector of variables) this phi
 341 /// represents on the sigmas list.
 342 ///
 343 unsigned SSI::getPositionSigma(PHINode *PN) {
 344   DenseMap<PHINode *, unsigned>::iterator val = sigmas.find(PN);
 345   if (val == sigmas.end())
 346     return UNSIGNED_INFINITE;
 347   else
 348     return val->second;
 349 }
 350
 351 /// Return true if the the Comparison Instruction is an operator
 352 /// of the Terminator instruction of its Basic Block.
 353 ///
 354 unsigned SSI::isUsedInTerminator(CmpInst *CI) {
 355   TerminatorInst *TI = CI->getParent()->getTerminator();
 356   if (TI->getNumOperands() == 0) {
 357     return false;
 358   } else if (CI == TI->getOperand(0)) {
 359     return true;
 360   } else {
 361     return false;
 362   }
 363 }
 364
 365 /// Initializes
 366 ///
 367 void SSI::init(SmallVectorImpl<Instruction *> &value) {
 368   num_values = value.size();
 369   needConstruction.resize(num_values, false);
 370
 371   value_original.resize(num_values);
 372   defsites.resize(num_values);
 373
 374   for (unsigned i = 0; i < num_values; ++i) {
 375     value_original[i] = value[i]->getParent();
 376     defsites[i].push_back(value_original[i]);
 377   }
 378 }
 379
 380 /// Clean all used resources in this creation of SSI
 381 ///
 382 void SSI::clean() {
 383   for (unsigned i = 0; i < num_values; ++i) {
 384     defsites[i].clear();
 385     if (i < value_stack.size())
 386       value_stack[i].clear();
 387   }
 388
 389   phis.clear();
 390   sigmas.clear();
 391   phisToFix.clear();
 392
 393   defsites.clear();
 394   value_stack.clear();
 395   value_original.clear();
 396   needConstruction.clear();
 397 }
 398
 399 /// createSSIPass - The public interface to this file...
 400 ///
 401 FunctionPass *llvm::createSSIPass() { return new SSI(); }
 402
 403 char SSI::ID = 0;
 404 static RegisterPass<SSI> X("ssi", "Static Single Information Construction");
 405
 406 /// SSIEverything - A pass that runs createSSI on every non-void variable,
 407 /// intended for debugging.
 408 namespace {
 409   struct VISIBILITY_HIDDEN SSIEverything : public FunctionPass {
 410     static char ID; // Pass identification, replacement for typeid
 411     SSIEverything() : FunctionPass(&ID) {}
 412
 413     bool runOnFunction(Function &F);
 414
 415     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 416       AU.addRequired<SSI>();
 417     }
 418   };
 419 }
 420
 421 bool SSIEverything::runOnFunction(Function &F) {
 422   SmallVector<Instruction *, 16> Insts;
 423   SSI &ssi = getAnalysis<SSI>();
 424
 425   if (F.isDeclaration() || F.isIntrinsic()) return false;
 426
 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()))
 430         Insts.push_back(I);
 431
 432   ssi.createSSI(Insts);
 433   return true;
 434 }
 435
 436 /// createSSIEverythingPass - The public interface to this file...
 437 ///
 438 FunctionPass *llvm::createSSIEverythingPass() { return new SSIEverything(); }
 439
 440 char SSIEverything::ID = 0;
 441 static RegisterPass<SSIEverything>
 442 Y("ssi-everything", "Static Single Information Construction");