lib/Target/PowerPC/PPCCTRLoops.cpp

   1 //===-- PPCCTRLoops.cpp - Identify and generate CTR loops -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass identifies loops where we can generate the PPC branch instructions
  11 // that decrement and test the count register (CTR) (bdnz and friends).
  12 //
  13 // The pattern that defines the induction variable can changed depending on
  14 // prior optimizations.  For example, the IndVarSimplify phase run by 'opt'
  15 // normalizes induction variables, and the Loop Strength Reduction pass
  16 // run by 'llc' may also make changes to the induction variable.
  17 //
  18 // Criteria for CTR loops:
  19 //  - Countable loops (w/ ind. var for a trip count)
  20 //  - Try inner-most loops first
  21 //  - No nested CTR loops.
  22 //  - No function calls in loops.
  23 //
  24 //===----------------------------------------------------------------------===//
  25
  26 #define DEBUG_TYPE "ctrloops"
  27
  28 #include "llvm/Transforms/Scalar.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include "llvm/Analysis/Dominators.h"
  32 #include "llvm/Analysis/LoopInfo.h"
  33 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  34 #include "llvm/IR/Constants.h"
  35 #include "llvm/IR/DerivedTypes.h"
  36 #include "llvm/IR/Instructions.h"
  37 #include "llvm/IR/IntrinsicInst.h"
  38 #include "llvm/IR/Module.h"
  39 #include "llvm/PassSupport.h"
  40 #include "llvm/Support/CommandLine.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/Support/ValueHandle.h"
  43 #include "llvm/Support/raw_ostream.h"
  44 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  45 #include "llvm/Transforms/Utils/Local.h"
  46 #include "llvm/Target/TargetLibraryInfo.h"
  47 #include "PPCTargetMachine.h"
  48 #include "PPC.h"
  49
  50 #include <algorithm>
  51 #include <vector>
  52
  53 using namespace llvm;
  54
  55 #ifndef NDEBUG
  56 static cl::opt<int> CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1));
  57 #endif
  58
  59 STATISTIC(NumCTRLoops, "Number of loops converted to CTR loops");
  60
  61 namespace llvm {
  62   void initializePPCCTRLoopsPass(PassRegistry&);
  63 }
  64
  65 namespace {
  66   struct PPCCTRLoops : public FunctionPass {
  67
  68 #ifndef NDEBUG
  69     static int Counter;
  70 #endif
  71
  72   public:
  73     static char ID;
  74
  75     PPCCTRLoops() : FunctionPass(ID), TM(0) {
  76       initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry());
  77     }
  78     PPCCTRLoops(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {
  79       initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry());
  80     }
  81
  82     virtual bool runOnFunction(Function &F);
  83
  84     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  85       AU.addRequired<LoopInfo>();
  86       AU.addPreserved<LoopInfo>();
  87       AU.addRequired<DominatorTree>();
  88       AU.addPreserved<DominatorTree>();
  89       AU.addRequired<ScalarEvolution>();
  90     }
  91
  92   private:
  93     // FIXME: Copied from LoopSimplify.
  94     BasicBlock *InsertPreheaderForLoop(Loop *L);
  95     void PlaceSplitBlockCarefully(BasicBlock *NewBB,
  96                                   SmallVectorImpl<BasicBlock*> &SplitPreds,
  97                                   Loop *L);
  98
  99     bool mightUseCTR(const Triple &TT, BasicBlock *BB);
 100     bool convertToCTRLoop(Loop *L);
 101   private:
 102     PPCTargetMachine *TM;
 103     LoopInfo *LI;
 104     ScalarEvolution *SE;
 105     DataLayout *TD;
 106     DominatorTree *DT;
 107     const TargetLibraryInfo *LibInfo;
 108   };
 109
 110   char PPCCTRLoops::ID = 0;
 111 #ifndef NDEBUG
 112   int PPCCTRLoops::Counter = 0;
 113 #endif
 114 } // end anonymous namespace
 115
 116 INITIALIZE_PASS_BEGIN(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops",
 117                       false, false)
 118 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 119 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
 120 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 121 INITIALIZE_PASS_END(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops",
 122                     false, false)
 123
 124 FunctionPass *llvm::createPPCCTRLoops(PPCTargetMachine &TM) {
 125   return new PPCCTRLoops(TM);
 126 }
 127
 128 bool PPCCTRLoops::runOnFunction(Function &F) {
 129   LI = &getAnalysis<LoopInfo>();
 130   SE = &getAnalysis<ScalarEvolution>();
 131   DT = &getAnalysis<DominatorTree>();
 132   TD = getAnalysisIfAvailable<DataLayout>();
 133   LibInfo = getAnalysisIfAvailable<TargetLibraryInfo>();
 134
 135   bool MadeChange = false;
 136
 137   for (LoopInfo::iterator I = LI->begin(), E = LI->end();
 138        I != E; ++I) {
 139     Loop *L = *I;
 140     if (!L->getParentLoop())
 141       MadeChange |= convertToCTRLoop(L);
 142   }
 143
 144   return MadeChange;
 145 }
 146
 147 bool PPCCTRLoops::mightUseCTR(const Triple &TT, BasicBlock *BB) {
 148   for (BasicBlock::iterator J = BB->begin(), JE = BB->end();
 149        J != JE; ++J) {
 150     if (CallInst *CI = dyn_cast<CallInst>(J)) {
 151       if (!TM)
 152         return true;
 153       const TargetLowering *TLI = TM->getTargetLowering();
 154
 155       if (Function *F = CI->getCalledFunction()) {
 156         // Most intrinsics don't become function calls, but some might.
 157         // sin, cos, exp and log are always calls.
 158         unsigned Opcode;
 159         if (F->getIntrinsicID() != Intrinsic::not_intrinsic) {
 160           switch (F->getIntrinsicID()) {
 161           default: continue;
 162
 163 // VisualStudio defines setjmp as _setjmp
 164 #if defined(_MSC_VER) && defined(setjmp) && \
 165                        !defined(setjmp_undefined_for_msvc)
 166 #  pragma push_macro("setjmp")
 167 #  undef setjmp
 168 #  define setjmp_undefined_for_msvc
 169 #endif
 170
 171           case Intrinsic::setjmp:
 172
 173 #if defined(_MSC_VER) && defined(setjmp_undefined_for_msvc)
 174  // let's return it to _setjmp state
 175 #  pragma pop_macro("setjmp")
 176 #  undef setjmp_undefined_for_msvc
 177 #endif
 178
 179           case Intrinsic::longjmp:
 180           case Intrinsic::memcpy:
 181           case Intrinsic::memmove:
 182           case Intrinsic::memset:
 183           case Intrinsic::powi:
 184           case Intrinsic::log:
 185           case Intrinsic::log2:
 186           case Intrinsic::log10:
 187           case Intrinsic::exp:
 188           case Intrinsic::exp2:
 189           case Intrinsic::pow:
 190           case Intrinsic::sin:
 191           case Intrinsic::cos:
 192             return true;
 193           case Intrinsic::sqrt:      Opcode = ISD::FSQRT;      break;
 194           case Intrinsic::floor:     Opcode = ISD::FFLOOR;     break;
 195           case Intrinsic::ceil:      Opcode = ISD::FCEIL;      break;
 196           case Intrinsic::trunc:     Opcode = ISD::FTRUNC;     break;
 197           case Intrinsic::rint:      Opcode = ISD::FRINT;      break;
 198           case Intrinsic::nearbyint: Opcode = ISD::FNEARBYINT; break;
 199           }
 200         }
 201
 202         // PowerPC does not use [US]DIVREM or other library calls for
 203         // operations on regular types which are not otherwise library calls
 204         // (i.e. soft float or atomics). If adapting for targets that do,
 205         // additional care is required here.
 206
 207         LibFunc::Func Func;
 208         if (!F->hasLocalLinkage() && F->hasName() && LibInfo &&
 209             LibInfo->getLibFunc(F->getName(), Func) &&
 210             LibInfo->hasOptimizedCodeGen(Func)) {
 211           // Non-read-only functions are never treated as intrinsics.
 212           if (!CI->onlyReadsMemory())
 213             return true;
 214
 215           // Conversion happens only for FP calls.
 216           if (!CI->getArgOperand(0)->getType()->isFloatingPointTy())
 217             return true;
 218
 219           switch (Func) {
 220           default: return true;
 221           case LibFunc::copysign:
 222           case LibFunc::copysignf:
 223           case LibFunc::copysignl:
 224             continue; // ISD::FCOPYSIGN is never a library call.
 225           case LibFunc::fabs:
 226           case LibFunc::fabsf:
 227           case LibFunc::fabsl:
 228             continue; // ISD::FABS is never a library call.
 229           case LibFunc::sqrt:
 230           case LibFunc::sqrtf:
 231           case LibFunc::sqrtl:
 232             Opcode = ISD::FSQRT; break;
 233           case LibFunc::floor:
 234           case LibFunc::floorf:
 235           case LibFunc::floorl:
 236             Opcode = ISD::FFLOOR; break;
 237           case LibFunc::nearbyint:
 238           case LibFunc::nearbyintf:
 239           case LibFunc::nearbyintl:
 240             Opcode = ISD::FNEARBYINT; break;
 241           case LibFunc::ceil:
 242           case LibFunc::ceilf:
 243           case LibFunc::ceill:
 244             Opcode = ISD::FCEIL; break;
 245           case LibFunc::rint:
 246           case LibFunc::rintf:
 247           case LibFunc::rintl:
 248             Opcode = ISD::FRINT; break;
 249           case LibFunc::trunc:
 250           case LibFunc::truncf:
 251           case LibFunc::truncl:
 252             Opcode = ISD::FTRUNC; break;
 253           }
 254
 255           MVT VTy =
 256             TLI->getSimpleValueType(CI->getArgOperand(0)->getType(), true);
 257           if (VTy == MVT::Other)
 258             return true;
 259
 260           if (TLI->isOperationLegalOrCustom(Opcode, VTy))
 261             continue;
 262           else if (VTy.isVector() &&
 263                    TLI->isOperationLegalOrCustom(Opcode, VTy.getScalarType()))
 264             continue;
 265
 266           return true;
 267         }
 268       }
 269
 270       return true;
 271     } else if (isa<BinaryOperator>(J) &&
 272                J->getType()->getScalarType()->isPPC_FP128Ty()) {
 273       // Most operations on ppc_f128 values become calls.
 274       return true;
 275     } else if (isa<UIToFPInst>(J) || isa<SIToFPInst>(J) ||
 276                isa<FPToUIInst>(J) || isa<FPToSIInst>(J)) {
 277       CastInst *CI = cast<CastInst>(J);
 278       if (CI->getSrcTy()->getScalarType()->isPPC_FP128Ty() ||
 279           CI->getDestTy()->getScalarType()->isPPC_FP128Ty() ||
 280           (TT.isArch32Bit() &&
 281            (CI->getSrcTy()->getScalarType()->isIntegerTy(64) ||
 282             CI->getDestTy()->getScalarType()->isIntegerTy(64))
 283           ))
 284         return true;
 285     } else if (isa<IndirectBrInst>(J) || isa<InvokeInst>(J)) {
 286       // On PowerPC, indirect jumps use the counter register.
 287       return true;
 288     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(J)) {
 289       if (!TM)
 290         return true;
 291       const TargetLowering *TLI = TM->getTargetLowering();
 292
 293       if (TLI->supportJumpTables() &&
 294           SI->getNumCases()+1 >= (unsigned) TLI->getMinimumJumpTableEntries())
 295         return true;
 296     }
 297   }
 298
 299   return false;
 300 }
 301
 302 bool PPCCTRLoops::convertToCTRLoop(Loop *L) {
 303   bool MadeChange = false;
 304
 305   Triple TT = Triple(L->getHeader()->getParent()->getParent()->
 306                      getTargetTriple());
 307   if (!TT.isArch32Bit() && !TT.isArch64Bit())
 308     return MadeChange; // Unknown arch. type.
 309
 310   // Process nested loops first.
 311   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
 312     MadeChange |= convertToCTRLoop(*I);
 313   }
 314
 315   // If a nested loop has been converted, then we can't convert this loop.
 316   if (MadeChange)
 317     return MadeChange;
 318
 319 #ifndef NDEBUG
 320   // Stop trying after reaching the limit (if any).
 321   int Limit = CTRLoopLimit;
 322   if (Limit >= 0) {
 323     if (Counter >= CTRLoopLimit)
 324       return false;
 325     Counter++;
 326   }
 327 #endif
 328
 329   // We don't want to spill/restore the counter register, and so we don't
 330   // want to use the counter register if the loop contains calls.
 331   for (Loop::block_iterator I = L->block_begin(), IE = L->block_end();
 332        I != IE; ++I)
 333     if (mightUseCTR(TT, *I))
 334       return MadeChange;
 335
 336   SmallVector<BasicBlock*, 4> ExitingBlocks;
 337   L->getExitingBlocks(ExitingBlocks);
 338
 339   BasicBlock *CountedExitBlock = 0;
 340   const SCEV *ExitCount = 0;
 341   BranchInst *CountedExitBranch = 0;
 342   for (SmallVector<BasicBlock*, 4>::iterator I = ExitingBlocks.begin(),
 343        IE = ExitingBlocks.end(); I != IE; ++I) {
 344     const SCEV *EC = SE->getExitCount(L, *I);
 345     DEBUG(dbgs() << "Exit Count for " << *L << " from block " <<
 346                     (*I)->getName() << ": " << *EC << "\n");
 347     if (isa<SCEVCouldNotCompute>(EC))
 348       continue;
 349     if (const SCEVConstant *ConstEC = dyn_cast<SCEVConstant>(EC)) {
 350       if (ConstEC->getValue()->isZero())
 351         continue;
 352     } else if (!SE->isLoopInvariant(EC, L))
 353       continue;
 354
 355     // We now have a loop-invariant count of loop iterations (which is not the
 356     // constant zero) for which we know that this loop will not exit via this
 357     // exisiting block.
 358
 359     // We need to make sure that this block will run on every loop iteration.
 360     // For this to be true, we must dominate all blocks with backedges. Such
 361     // blocks are in-loop predecessors to the header block.
 362     bool NotAlways = false;
 363     for (pred_iterator PI = pred_begin(L->getHeader()),
 364          PIE = pred_end(L->getHeader()); PI != PIE; ++PI) {
 365       if (!L->contains(*PI))
 366         continue;
 367
 368       if (!DT->dominates(*I, *PI)) {
 369         NotAlways = true;
 370         break;
 371       }
 372     }
 373
 374     if (NotAlways)
 375       continue;
 376
 377     // Make sure this blocks ends with a conditional branch.
 378     Instruction *TI = (*I)->getTerminator();
 379     if (!TI)
 380       continue;
 381
 382     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 383       if (!BI->isConditional())
 384         continue;
 385
 386       CountedExitBranch = BI;
 387     } else
 388       continue;
 389
 390     // Note that this block may not be the loop latch block, even if the loop
 391     // has a latch block.
 392     CountedExitBlock = *I;
 393     ExitCount = EC;
 394     break;
 395   }
 396
 397   if (!CountedExitBlock)
 398     return MadeChange;
 399
 400   BasicBlock *Preheader = L->getLoopPreheader();
 401
 402   // If we don't have a preheader, then insert one. If we already have a
 403   // preheader, then we can use it (except if the preheader contains a use of
 404   // the CTR register because some such uses might be reordered by the
 405   // selection DAG after the mtctr instruction).
 406   if (!Preheader || mightUseCTR(TT, Preheader))
 407     Preheader = InsertPreheaderForLoop(L);
 408   if (!Preheader)
 409     return MadeChange;
 410
 411   DEBUG(dbgs() << "Preheader for exit count: " << Preheader->getName() << "\n");
 412
 413   // Insert the count into the preheader and replace the condition used by the
 414   // selected branch.
 415   MadeChange = true;
 416
 417   SCEVExpander SCEVE(*SE, "loopcnt");
 418   LLVMContext &C = SE->getContext();
 419   Type *CountType = TT.isArch64Bit() ? Type::getInt64Ty(C) :
 420                                        Type::getInt32Ty(C);
 421   if (!ExitCount->getType()->isPointerTy() &&
 422       ExitCount->getType() != CountType)
 423     ExitCount = SE->getZeroExtendExpr(ExitCount, CountType);
 424   ExitCount = SE->getAddExpr(ExitCount,
 425                              SE->getConstant(CountType, 1));
 426   Value *ECValue = SCEVE.expandCodeFor(ExitCount, CountType,
 427                                        Preheader->getTerminator());
 428
 429   IRBuilder<> CountBuilder(Preheader->getTerminator());
 430   Module *M = Preheader->getParent()->getParent();
 431   Value *MTCTRFunc = Intrinsic::getDeclaration(M, Intrinsic::ppc_mtctr,
 432                                                CountType);
 433   CountBuilder.CreateCall(MTCTRFunc, ECValue);
 434
 435   IRBuilder<> CondBuilder(CountedExitBranch);
 436   Value *DecFunc =
 437     Intrinsic::getDeclaration(M, Intrinsic::ppc_is_decremented_ctr_nonzero);
 438   Value *NewCond = CondBuilder.CreateCall(DecFunc);
 439   Value *OldCond = CountedExitBranch->getCondition();
 440   CountedExitBranch->setCondition(NewCond);
 441
 442   // The false branch must exit the loop.
 443   if (!L->contains(CountedExitBranch->getSuccessor(0)))
 444     CountedExitBranch->swapSuccessors();
 445
 446   // The old condition may be dead now, and may have even created a dead PHI
 447   // (the original induction variable).
 448   RecursivelyDeleteTriviallyDeadInstructions(OldCond);
 449   DeleteDeadPHIs(CountedExitBlock);
 450
 451   ++NumCTRLoops;
 452   return MadeChange;
 453 }
 454
 455 // FIXME: Copied from LoopSimplify.
 456 BasicBlock *PPCCTRLoops::InsertPreheaderForLoop(Loop *L) {
 457   BasicBlock *Header = L->getHeader();
 458
 459   // Compute the set of predecessors of the loop that are not in the loop.
 460   SmallVector<BasicBlock*, 8> OutsideBlocks;
 461   for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
 462        PI != PE; ++PI) {
 463     BasicBlock *P = *PI;
 464     if (!L->contains(P)) {         // Coming in from outside the loop?
 465       // If the loop is branched to from an indirect branch, we won't
 466       // be able to fully transform the loop, because it prohibits
 467       // edge splitting.
 468       if (isa<IndirectBrInst>(P->getTerminator())) return 0;
 469
 470       // Keep track of it.
 471       OutsideBlocks.push_back(P);
 472     }
 473   }
 474
 475   // Split out the loop pre-header.
 476   BasicBlock *PreheaderBB;
 477   if (!Header->isLandingPad()) {
 478     PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader",
 479                                          this);
 480   } else {
 481     SmallVector<BasicBlock*, 2> NewBBs;
 482     SplitLandingPadPredecessors(Header, OutsideBlocks, ".preheader",
 483                                 ".split-lp", this, NewBBs);
 484     PreheaderBB = NewBBs[0];
 485   }
 486
 487   PreheaderBB->getTerminator()->setDebugLoc(
 488                                       Header->getFirstNonPHI()->getDebugLoc());
 489   DEBUG(dbgs() << "Creating pre-header "
 490                << PreheaderBB->getName() << "\n");
 491
 492   // Make sure that NewBB is put someplace intelligent, which doesn't mess up
 493   // code layout too horribly.
 494   PlaceSplitBlockCarefully(PreheaderBB, OutsideBlocks, L);
 495
 496   return PreheaderBB;
 497 }
 498
 499 void PPCCTRLoops::PlaceSplitBlockCarefully(BasicBlock *NewBB,
 500                                        SmallVectorImpl<BasicBlock*> &SplitPreds,
 501                                             Loop *L) {
 502   // Check to see if NewBB is already well placed.
 503   Function::iterator BBI = NewBB; --BBI;
 504   for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
 505     if (&*BBI == SplitPreds[i])
 506       return;
 507   }
 508
 509   // If it isn't already after an outside block, move it after one.  This is
 510   // always good as it makes the uncond branch from the outside block into a
 511   // fall-through.
 512
 513   // Figure out *which* outside block to put this after.  Prefer an outside
 514   // block that neighbors a BB actually in the loop.
 515   BasicBlock *FoundBB = 0;
 516   for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
 517     Function::iterator BBI = SplitPreds[i];
 518     if (++BBI != NewBB->getParent()->end() &&
 519         L->contains(BBI)) {
 520       FoundBB = SplitPreds[i];
 521       break;
 522     }
 523   }
 524
 525   // If our heuristic for a *good* bb to place this after doesn't find
 526   // anything, just pick something.  It's likely better than leaving it within
 527   // the loop.
 528   if (!FoundBB)
 529     FoundBB = SplitPreds[0];
 530   NewBB->moveAfter(FoundBB);
 531 }
 532