lib/Transforms/Scalar/LoopIndexSplit.cpp

   1 //===- LoopIndexSplit.cpp - Loop Index Splitting Pass ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Devang Patel and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements Loop Index Splitting Pass.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "loop-index-split"
  15
  16 #include "llvm/Function.h"
  17 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/Analysis/LoopPass.h"
  19 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  20 #include "llvm/Support/Compiler.h"
  21 #include "llvm/ADT/Statistic.h"
  22
  23 using namespace llvm;
  24
  25 STATISTIC(NumIndexSplit, "Number of loops index split");
  26
  27 namespace {
  28
  29   class VISIBILITY_HIDDEN LoopIndexSplit : public LoopPass {
  30
  31   public:
  32     static char ID; // Pass ID, replacement for typeid
  33     LoopIndexSplit() : LoopPass((intptr_t)&ID) {}
  34
  35     // Index split Loop L. Return true if loop is split.
  36     bool runOnLoop(Loop *L, LPPassManager &LPM);
  37
  38     void getAnalysisUsage(AnalysisUsage &AU) const {
  39       AU.addRequired<ScalarEvolution>();
  40       AU.addPreserved<ScalarEvolution>();
  41       AU.addRequiredID(LCSSAID);
  42       AU.addPreservedID(LCSSAID);
  43       AU.addPreserved<LoopInfo>();
  44       AU.addRequiredID(LoopSimplifyID);
  45       AU.addPreservedID(LoopSimplifyID);
  46     }
  47
  48   private:
  49     /// Find condition inside a loop that is suitable candidate for index split.
  50     void findSplitCondition();
  51
  52     /// processOneIterationLoop - Current loop L contains compare instruction
  53     /// that compares induction variable, IndVar, agains loop invariant. If
  54     /// entire (i.e. meaningful) loop body is dominated by this compare
  55     /// instruction then loop body is executed only for one iteration. In
  56     /// such case eliminate loop structure surrounding this loop body. For
  57     bool processOneIterationLoop(LPPassManager &LPM);
  58
  59     // If loop header includes loop variant instruction operands then
  60     // this loop may not be eliminated.
  61     bool safeHeader(BasicBlock *BB);
  62
  63     // If Exit block includes loop variant instructions then this
  64     // loop may not be eliminated.
  65     bool safeExitBlock(BasicBlock *BB);
  66
  67     bool splitLoop();
  68
  69   private:
  70
  71     // Current Loop.
  72     Loop *L;
  73     ScalarEvolution *SE;
  74
  75     // Induction variable whose range is being split by this transformation.
  76     PHINode *IndVar;
  77
  78     // Induction variable's range is split at this value.
  79     Value *SplitValue;
  80
  81     // Induction variable's final loop exit value.
  82     Value *ExitValue;
  83
  84     // This compare instruction compares IndVar against SplitValue.
  85     ICmpInst *SplitCondition;
  86   };
  87
  88   char LoopIndexSplit::ID = 0;
  89   RegisterPass<LoopIndexSplit> X ("loop-index-split", "Index Split Loops");
  90 }
  91
  92 LoopPass *llvm::createLoopIndexSplitPass() {
  93   return new LoopIndexSplit();
  94 }
  95
  96 // Index split Loop L. Return true if loop is split.
  97 bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM) {
  98   bool Changed = false;
  99   L = IncomingLoop;
 100   SplitCondition = NULL;
 101   SE = &getAnalysis<ScalarEvolution>();
 102
 103   findSplitCondition();
 104
 105   if (!SplitCondition)
 106     return false;
 107
 108   if (SplitCondition->getPredicate() == ICmpInst::ICMP_EQ)
 109     // If it is possible to eliminate loop then do so.
 110     Changed = processOneIterationLoop(LPM);
 111   else
 112     Changed = splitLoop();
 113
 114   if (Changed)
 115     ++NumIndexSplit;
 116
 117   return Changed;
 118 }
 119
 120 /// Find condition inside a loop that is suitable candidate for index split.
 121 void LoopIndexSplit::findSplitCondition() {
 122
 123  BasicBlock *Header = L->getHeader();
 124
 125   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 126     PHINode *PN = cast<PHINode>(I);
 127
 128     if (!PN->getType()->isInteger())
 129       continue;
 130
 131     SCEVHandle SCEV = SE->getSCEV(PN);
 132     if (!isa<SCEVAddRecExpr>(SCEV))
 133       continue;
 134
 135     // If this phi node is used in a compare instruction then it is a
 136     // split condition candidate.
 137     for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end();
 138          UI != E; ++UI) {
 139       if (ICmpInst *CI = dyn_cast<ICmpInst>(*UI)) {
 140         SplitCondition = CI;
 141         break;
 142       }
 143     }
 144
 145     // Valid SplitCondition's one operand is phi node and the other operand
 146     // is loop invariant.
 147     if (SplitCondition) {
 148       if (SplitCondition->getOperand(0) != PN)
 149         SplitValue = SplitCondition->getOperand(0);
 150       else
 151         SplitValue = SplitCondition->getOperand(1);
 152       SCEVHandle ValueSCEV = SE->getSCEV(SplitValue);
 153
 154       // If SplitValue is not invariant then SplitCondition is not appropriate.
 155       if (!ValueSCEV->isLoopInvariant(L))
 156         SplitCondition = NULL;
 157     }
 158
 159     // We are looking for only one split condition.
 160     if (SplitCondition) {
 161       IndVar = PN;
 162       break;
 163     }
 164   }
 165 }
 166
 167 /// processOneIterationLoop - Current loop L contains compare instruction
 168 /// that compares induction variable, IndVar, against loop invariant. If
 169 /// entire (i.e. meaningful) loop body is dominated by this compare
 170 /// instruction then loop body is executed only once. In such case eliminate
 171 /// loop structure surrounding this loop body. For example,
 172 ///     for (int i = start; i < end; ++i) {
 173 ///         if ( i == somevalue) {
 174 ///           loop_body
 175 ///         }
 176 ///     }
 177 /// can be transformed into
 178 ///     if (somevalue >= start && somevalue < end) {
 179 ///        i = somevalue;
 180 ///        loop_body
 181 ///     }
 182 bool LoopIndexSplit::processOneIterationLoop(LPPassManager &LPM) {
 183
 184   BasicBlock *Header = L->getHeader();
 185
 186   // First of all, check if SplitCondition dominates entire loop body
 187   // or not.
 188
 189   // If SplitCondition is not in loop header then this loop is not suitable
 190   // for this transformation.
 191   if (SplitCondition->getParent() != Header)
 192     return false;
 193
 194   // If one of the Header block's successor is not an exit block then this
 195   // loop is not a suitable candidate.
 196   BasicBlock *ExitBlock = NULL;
 197   for (succ_iterator SI = succ_begin(Header), E = succ_end(Header); SI != E; ++SI) {
 198     if (L->isLoopExit(*SI)) {
 199       ExitBlock = *SI;
 200       break;
 201     }
 202   }
 203
 204   if (!ExitBlock)
 205     return false;
 206
 207   // If loop header includes loop variant instruction operands then
 208   // this loop may not be eliminated.
 209   if (!safeHeader(Header))
 210     return false;
 211
 212   // If Exit block includes loop variant instructions then this
 213   // loop may not be eliminated.
 214   if (!safeExitBlock(ExitBlock))
 215     return false;
 216
 217   BasicBlock *Latch = L->getLoopLatch();
 218   BasicBlock *Preheader = L->getLoopPreheader();
 219   Instruction *Terminator = Header->getTerminator();
 220   Value *StartValue = IndVar->getIncomingValueForBlock(Preheader);
 221
 222   // Update CFG.
 223
 224   // Replace split condition in header.
 225   // Transform
 226   //      SplitCondition : icmp eq i32 IndVar, SplitValue
 227   // into
 228   //      c1 = icmp uge i32 SplitValue, StartValue
 229   //      c2 = icmp ult i32 vSplitValue, ExitValue
 230   //      and i32 c1, c2
 231   bool SignedPredicate = SplitCondition->isSignedPredicate();
 232   Instruction *C1 = new ICmpInst(SignedPredicate ?
 233                                  ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
 234                                  SplitValue, StartValue, "lisplit", Terminator);
 235   Instruction *C2 = new ICmpInst(SignedPredicate ?
 236                                  ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 237                                  SplitValue, ExitValue, "lisplit", Terminator);
 238   Instruction *NSplitCond = BinaryOperator::create(Instruction::And,
 239                                                    C1, C2, "lisplit", Terminator);
 240   SplitCondition->replaceAllUsesWith(NSplitCond);
 241   SplitCondition->eraseFromParent();
 242
 243   // As a first step to break this loop, remove Latch to Header edge.
 244   BasicBlock *LatchSucc = NULL;
 245   Header->removePredecessor(Latch);
 246   for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch);
 247        SI != E; ++SI) {
 248     if (Header != *SI)
 249       LatchSucc = *SI;
 250   }
 251   BranchInst *BR = dyn_cast<BranchInst>(Latch->getTerminator());
 252   BR->setUnconditionalDest(LatchSucc);
 253
 254   // Now, clear latch block. Remove instructions that are responsible
 255   // to increment induction variable.
 256   Instruction *LTerminator = Latch->getTerminator();
 257   for (BasicBlock::iterator LB = Latch->begin(), LE = Latch->end();
 258        LB != LE; ) {
 259     Instruction *I = LB;
 260     ++LB;
 261     if (isa<PHINode>(I) || I == LTerminator)
 262       continue;
 263
 264     I->replaceAllUsesWith(UndefValue::get(I->getType()));
 265     I->eraseFromParent();
 266   }
 267
 268   LPM.deleteLoopFromQueue(L);
 269   return true;
 270 }
 271
 272 // If loop header includes loop variant instruction operands then
 273 // this loop can not be eliminated. This is used by processOneIterationLoop().
 274 bool LoopIndexSplit::safeHeader(BasicBlock *Header) {
 275
 276   Instruction *Terminator = Header->getTerminator();
 277   for(BasicBlock::iterator BI = Header->begin(), BE = Header->end();
 278       BI != BE; ++BI) {
 279     Instruction *I = BI;
 280
 281     // PHI Nodes are OK.
 282     if (isa<PHINode>(I))
 283       continue;
 284
 285     // SplitCondition itself is OK.
 286     if (ICmpInst *CI = dyn_cast<ICmpInst>(I)) {
 287       if (CI == SplitCondition)
 288         continue;
 289     }
 290
 291     // Terminator is also harmless.
 292     if (I == Terminator)
 293       continue;
 294
 295     // Otherwise we have a instruction that may not be safe.
 296     return false;
 297   }
 298
 299   return true;
 300 }
 301
 302 // If Exit block includes loop variant instructions then this
 303 // loop may not be eliminated. This is used by processOneIterationLoop().
 304 bool LoopIndexSplit::safeExitBlock(BasicBlock *ExitBlock) {
 305
 306   Instruction *ExitCondition = NULL;
 307   Instruction *IndVarIncrement = NULL;
 308
 309   for (BasicBlock::iterator BI = ExitBlock->begin(), BE = ExitBlock->end();
 310        BI != BE; ++BI) {
 311     Instruction *I = BI;
 312
 313     // PHI Nodes are OK.
 314     if (isa<PHINode>(I))
 315       continue;
 316
 317     // Check if I is induction variable increment instruction.
 318     if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(I)) {
 319       if (BOp->getOpcode() != Instruction::Add)
 320         return false;
 321
 322       Value *Op0 = BOp->getOperand(0);
 323       Value *Op1 = BOp->getOperand(1);
 324       PHINode *PN = NULL;
 325       ConstantInt *CI = NULL;
 326
 327       if ((PN = dyn_cast<PHINode>(Op0))) {
 328         if ((CI = dyn_cast<ConstantInt>(Op1)))
 329           IndVarIncrement = I;
 330       } else
 331         if ((PN = dyn_cast<PHINode>(Op1))) {
 332           if ((CI = dyn_cast<ConstantInt>(Op0)))
 333             IndVarIncrement = I;
 334       }
 335
 336       if (IndVarIncrement && PN == IndVar && CI->isOne())
 337         continue;
 338     }
 339     // I is an Exit condition if next instruction is block terminator.
 340     // Exit condition is OK if it compares loop invariant exit value,
 341     // which is checked below.
 342     else if (isa<ICmpInst>(I)) {
 343       ++BI;
 344       Instruction *N = BI;
 345       if (N == ExitBlock->getTerminator()) {
 346         ExitCondition = I;
 347         break;
 348       }
 349     }
 350
 351     // Otherwise we have instruction that may not be safe.
 352     return false;
 353   }
 354
 355   // Check if Exit condition is comparing induction variable against
 356   // loop invariant value. If one operand is induction variable and
 357   // the other operand is loop invaraint then Exit condition is safe.
 358   if (ExitCondition) {
 359     Value *Op0 = ExitCondition->getOperand(0);
 360     Value *Op1 = ExitCondition->getOperand(1);
 361
 362     Instruction *Insn0 = dyn_cast<Instruction>(Op0);
 363     Instruction *Insn1 = dyn_cast<Instruction>(Op1);
 364
 365     if (Insn0 && Insn0 == IndVarIncrement)
 366       ExitValue = Op1;
 367     else if (Insn1 && Insn1 == IndVarIncrement)
 368       ExitValue = Op0;
 369
 370     SCEVHandle ValueSCEV = SE->getSCEV(ExitValue);
 371     if (!ValueSCEV->isLoopInvariant(L))
 372       return false;
 373   }
 374
 375   // We could not find any reason to consider ExitBlock unsafe.
 376   return true;
 377 }
 378
 379 bool LoopIndexSplit::splitLoop() {
 380   // FIXME :)
 381   return false;
 382 }