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/Transforms/Scalar.h"
  17 #include "llvm/Function.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
  50     class SplitInfo {
  51     public:
  52       SplitInfo() : IndVar(NULL), SplitValue(NULL), ExitValue(NULL),
  53                     SplitCondition(NULL), ExitCondition(NULL) {}
  54       // Induction variable whose range is being split by this transformation.
  55       PHINode *IndVar;
  56
  57       // Induction variable's range is split at this value.
  58       Value *SplitValue;
  59
  60       // Induction variable's final loop exit value.
  61       Value *ExitValue;
  62
  63       // This compare instruction compares IndVar against SplitValue.
  64       ICmpInst *SplitCondition;
  65
  66       // Loop exit condition.
  67       ICmpInst *ExitCondition;
  68
  69       // Clear split info.
  70       void clear() {
  71         IndVar = NULL;
  72         SplitValue = NULL;
  73         ExitValue = NULL;
  74         SplitCondition = NULL;
  75         ExitCondition = NULL;
  76       }
  77     };
  78
  79   private:
  80     /// Find condition inside a loop that is suitable candidate for index split.
  81     void findSplitCondition();
  82
  83     /// processOneIterationLoop - Current loop L contains compare instruction
  84     /// that compares induction variable, IndVar, agains loop invariant. If
  85     /// entire (i.e. meaningful) loop body is dominated by this compare
  86     /// instruction then loop body is executed only for one iteration. In
  87     /// such case eliminate loop structure surrounding this loop body. For
  88     bool processOneIterationLoop(SplitInfo &SD, LPPassManager &LPM);
  89
  90     // If loop header includes loop variant instruction operands then
  91     // this loop may not be eliminated.
  92     bool safeHeader(SplitInfo &SD,  BasicBlock *BB);
  93
  94     // If Exit block includes loop variant instructions then this
  95     // loop may not be eliminated.
  96     bool safeExitBlock(SplitInfo &SD, BasicBlock *BB);
  97
  98     bool splitLoop(SplitInfo &SD);
  99
 100   private:
 101
 102     // Current Loop.
 103     Loop *L;
 104     ScalarEvolution *SE;
 105
 106     SmallVector<SplitInfo, 4> SplitData;
 107   };
 108
 109   char LoopIndexSplit::ID = 0;
 110   RegisterPass<LoopIndexSplit> X ("loop-index-split", "Index Split Loops");
 111 }
 112
 113 LoopPass *llvm::createLoopIndexSplitPass() {
 114   return new LoopIndexSplit();
 115 }
 116
 117 // Index split Loop L. Return true if loop is split.
 118 bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM) {
 119   bool Changed = false;
 120   L = IncomingLoop;
 121
 122   SE = &getAnalysis<ScalarEvolution>();
 123
 124   findSplitCondition();
 125
 126   if (SplitData.empty())
 127     return false;
 128
 129   // First see if it is possible to eliminate loop itself or not.
 130   for (SmallVector<SplitInfo, 4>::iterator SI = SplitData.begin(),
 131          E = SplitData.end(); SI != E; ++SI) {
 132     SplitInfo &SD = *SI;
 133     if (SD.SplitCondition->getPredicate() == ICmpInst::ICMP_EQ) {
 134       Changed = processOneIterationLoop(SD,LPM);
 135       if (Changed) {
 136         ++NumIndexSplit;
 137         // If is loop is eliminated then nothing else to do here.
 138         return Changed;
 139       }
 140     }
 141   }
 142
 143   for (SmallVector<SplitInfo, 4>::iterator SI = SplitData.begin(),
 144          E = SplitData.end(); SI != E; ++SI) {
 145     SplitInfo &SD = *SI;
 146
 147     // ICM_EQs are already handled above.
 148     if (SD.SplitCondition->getPredicate() == ICmpInst::ICMP_EQ)
 149       continue;
 150
 151     // FIXME : Collect Spliting cost for all SD. Only operate on profitable SDs.
 152     Changed = splitLoop(SD);
 153   }
 154
 155   if (Changed)
 156     ++NumIndexSplit;
 157
 158   return Changed;
 159 }
 160
 161 /// Find condition inside a loop that is suitable candidate for index split.
 162 void LoopIndexSplit::findSplitCondition() {
 163
 164   SplitInfo SD;
 165   BasicBlock *Header = L->getHeader();
 166
 167   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 168     PHINode *PN = cast<PHINode>(I);
 169
 170     if (!PN->getType()->isInteger())
 171       continue;
 172
 173     SCEVHandle SCEV = SE->getSCEV(PN);
 174     if (!isa<SCEVAddRecExpr>(SCEV))
 175       continue;
 176
 177     // If this phi node is used in a compare instruction then it is a
 178     // split condition candidate.
 179     for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end();
 180          UI != E; ++UI) {
 181       if (ICmpInst *CI = dyn_cast<ICmpInst>(*UI)) {
 182         SD.SplitCondition = CI;
 183         break;
 184       }
 185     }
 186
 187     // Valid SplitCondition's one operand is phi node and the other operand
 188     // is loop invariant.
 189     if (SD.SplitCondition) {
 190       if (SD.SplitCondition->getOperand(0) != PN)
 191         SD.SplitValue = SD.SplitCondition->getOperand(0);
 192       else
 193         SD.SplitValue = SD.SplitCondition->getOperand(1);
 194       SCEVHandle ValueSCEV = SE->getSCEV(SD.SplitValue);
 195
 196       // If SplitValue is not invariant then SplitCondition is not appropriate.
 197       if (!ValueSCEV->isLoopInvariant(L))
 198         SD.SplitCondition = NULL;
 199     }
 200
 201     // We are looking for only one split condition.
 202     if (SD.SplitCondition) {
 203       SD.IndVar = PN;
 204       SplitData.push_back(SD);
 205       // Before reusing SD for next split condition clear its content.
 206       SD.clear();
 207     }
 208   }
 209 }
 210
 211 /// processOneIterationLoop - Current loop L contains compare instruction
 212 /// that compares induction variable, IndVar, against loop invariant. If
 213 /// entire (i.e. meaningful) loop body is dominated by this compare
 214 /// instruction then loop body is executed only once. In such case eliminate
 215 /// loop structure surrounding this loop body. For example,
 216 ///     for (int i = start; i < end; ++i) {
 217 ///         if ( i == somevalue) {
 218 ///           loop_body
 219 ///         }
 220 ///     }
 221 /// can be transformed into
 222 ///     if (somevalue >= start && somevalue < end) {
 223 ///        i = somevalue;
 224 ///        loop_body
 225 ///     }
 226 bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD, LPPassManager &LPM) {
 227
 228   BasicBlock *Header = L->getHeader();
 229
 230   // First of all, check if SplitCondition dominates entire loop body
 231   // or not.
 232
 233   // If SplitCondition is not in loop header then this loop is not suitable
 234   // for this transformation.
 235   if (SD.SplitCondition->getParent() != Header)
 236     return false;
 237
 238   // If one of the Header block's successor is not an exit block then this
 239   // loop is not a suitable candidate.
 240   BasicBlock *ExitBlock = NULL;
 241   for (succ_iterator SI = succ_begin(Header), E = succ_end(Header); SI != E; ++SI) {
 242     if (L->isLoopExit(*SI)) {
 243       ExitBlock = *SI;
 244       break;
 245     }
 246   }
 247
 248   if (!ExitBlock)
 249     return false;
 250
 251   // If loop header includes loop variant instruction operands then
 252   // this loop may not be eliminated.
 253   if (!safeHeader(SD, Header))
 254     return false;
 255
 256   // If Exit block includes loop variant instructions then this
 257   // loop may not be eliminated.
 258   if (!safeExitBlock(SD, ExitBlock))
 259     return false;
 260
 261   // Update CFG.
 262
 263   // As a first step to break this loop, remove Latch to Header edge.
 264   BasicBlock *Latch = L->getLoopLatch();
 265   BasicBlock *LatchSucc = NULL;
 266   BranchInst *BR = dyn_cast<BranchInst>(Latch->getTerminator());
 267   if (!BR)
 268     return false;
 269   Header->removePredecessor(Latch);
 270   for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch);
 271        SI != E; ++SI) {
 272     if (Header != *SI)
 273       LatchSucc = *SI;
 274   }
 275   BR->setUnconditionalDest(LatchSucc);
 276
 277   BasicBlock *Preheader = L->getLoopPreheader();
 278   Instruction *Terminator = Header->getTerminator();
 279   Value *StartValue = SD.IndVar->getIncomingValueForBlock(Preheader);
 280
 281   // Replace split condition in header.
 282   // Transform
 283   //      SplitCondition : icmp eq i32 IndVar, SplitValue
 284   // into
 285   //      c1 = icmp uge i32 SplitValue, StartValue
 286   //      c2 = icmp ult i32 vSplitValue, ExitValue
 287   //      and i32 c1, c2
 288   bool SignedPredicate = SD.ExitCondition->isSignedPredicate();
 289   Instruction *C1 = new ICmpInst(SignedPredicate ?
 290                                  ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
 291                                  SD.SplitValue, StartValue, "lisplit",
 292                                  Terminator);
 293   Instruction *C2 = new ICmpInst(SignedPredicate ?
 294                                  ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 295                                  SD.SplitValue, SD.ExitValue, "lisplit",
 296                                  Terminator);
 297   Instruction *NSplitCond = BinaryOperator::createAnd(C1, C2, "lisplit",
 298                                                       Terminator);
 299   SD.SplitCondition->replaceAllUsesWith(NSplitCond);
 300   SD.SplitCondition->eraseFromParent();
 301
 302   // Now, clear latch block. Remove instructions that are responsible
 303   // to increment induction variable.
 304   Instruction *LTerminator = Latch->getTerminator();
 305   for (BasicBlock::iterator LB = Latch->begin(), LE = Latch->end();
 306        LB != LE; ) {
 307     Instruction *I = LB;
 308     ++LB;
 309     if (isa<PHINode>(I) || I == LTerminator)
 310       continue;
 311
 312     I->replaceAllUsesWith(UndefValue::get(I->getType()));
 313     I->eraseFromParent();
 314   }
 315
 316   LPM.deleteLoopFromQueue(L);
 317   return true;
 318 }
 319
 320 // If loop header includes loop variant instruction operands then
 321 // this loop can not be eliminated. This is used by processOneIterationLoop().
 322 bool LoopIndexSplit::safeHeader(SplitInfo &SD, BasicBlock *Header) {
 323
 324   Instruction *Terminator = Header->getTerminator();
 325   for(BasicBlock::iterator BI = Header->begin(), BE = Header->end();
 326       BI != BE; ++BI) {
 327     Instruction *I = BI;
 328
 329     // PHI Nodes are OK. FIXME : Handle last value assignments.
 330     if (isa<PHINode>(I))
 331       continue;
 332
 333     // SplitCondition itself is OK.
 334     if (I == SD.SplitCondition)
 335       continue;
 336
 337     // Terminator is also harmless.
 338     if (I == Terminator)
 339       continue;
 340
 341     // Otherwise we have a instruction that may not be safe.
 342     return false;
 343   }
 344
 345   return true;
 346 }
 347
 348 // If Exit block includes loop variant instructions then this
 349 // loop may not be eliminated. This is used by processOneIterationLoop().
 350 bool LoopIndexSplit::safeExitBlock(SplitInfo &SD, BasicBlock *ExitBlock) {
 351
 352   Instruction *IndVarIncrement = NULL;
 353
 354   for (BasicBlock::iterator BI = ExitBlock->begin(), BE = ExitBlock->end();
 355        BI != BE; ++BI) {
 356     Instruction *I = BI;
 357
 358     // PHI Nodes are OK. FIXME : Handle last value assignments.
 359     if (isa<PHINode>(I))
 360       continue;
 361
 362     // Check if I is induction variable increment instruction.
 363     if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(I)) {
 364       if (BOp->getOpcode() != Instruction::Add)
 365         return false;
 366
 367       Value *Op0 = BOp->getOperand(0);
 368       Value *Op1 = BOp->getOperand(1);
 369       PHINode *PN = NULL;
 370       ConstantInt *CI = NULL;
 371
 372       if ((PN = dyn_cast<PHINode>(Op0))) {
 373         if ((CI = dyn_cast<ConstantInt>(Op1)))
 374           IndVarIncrement = I;
 375       } else
 376         if ((PN = dyn_cast<PHINode>(Op1))) {
 377           if ((CI = dyn_cast<ConstantInt>(Op0)))
 378             IndVarIncrement = I;
 379       }
 380
 381       if (IndVarIncrement && PN == SD.IndVar && CI->isOne())
 382         continue;
 383     }
 384
 385     // I is an Exit condition if next instruction is block terminator.
 386     // Exit condition is OK if it compares loop invariant exit value,
 387     // which is checked below.
 388     else if (ICmpInst *EC = dyn_cast<ICmpInst>(I)) {
 389       ++BI;
 390       Instruction *N = BI;
 391       if (N == ExitBlock->getTerminator()) {
 392         SD.ExitCondition = EC;
 393         continue;
 394       }
 395     }
 396
 397     // Otherwise we have instruction that may not be safe.
 398     return false;
 399   }
 400
 401   // Check if Exit condition is comparing induction variable against
 402   // loop invariant value. If one operand is induction variable and
 403   // the other operand is loop invaraint then Exit condition is safe.
 404   if (SD.ExitCondition) {
 405     Value *Op0 = SD.ExitCondition->getOperand(0);
 406     Value *Op1 = SD.ExitCondition->getOperand(1);
 407
 408     Instruction *Insn0 = dyn_cast<Instruction>(Op0);
 409     Instruction *Insn1 = dyn_cast<Instruction>(Op1);
 410
 411     if (Insn0 && Insn0 == IndVarIncrement)
 412       SD.ExitValue = Op1;
 413     else if (Insn1 && Insn1 == IndVarIncrement)
 414       SD.ExitValue = Op0;
 415
 416     SCEVHandle ValueSCEV = SE->getSCEV(SD.ExitValue);
 417     if (!ValueSCEV->isLoopInvariant(L))
 418       return false;
 419   }
 420
 421   // We could not find any reason to consider ExitBlock unsafe.
 422   return true;
 423 }
 424
 425 bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
 426   // FIXME :)
 427   return false;
 428 }