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