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