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