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