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