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