PPCCTRLoops.cpp revision 4e6b24ffcfafbc0c5eda1bb89163ccd56f394fdf
199f823f94374917174f96a7689955b8463db6816Hal Finkel//===-- PPCCTRLoops.cpp - Identify and generate CTR loops -----------------===// 299f823f94374917174f96a7689955b8463db6816Hal Finkel// 399f823f94374917174f96a7689955b8463db6816Hal Finkel// The LLVM Compiler Infrastructure 499f823f94374917174f96a7689955b8463db6816Hal Finkel// 599f823f94374917174f96a7689955b8463db6816Hal Finkel// This file is distributed under the University of Illinois Open Source 699f823f94374917174f96a7689955b8463db6816Hal Finkel// License. See LICENSE.TXT for details. 799f823f94374917174f96a7689955b8463db6816Hal Finkel// 899f823f94374917174f96a7689955b8463db6816Hal Finkel//===----------------------------------------------------------------------===// 999f823f94374917174f96a7689955b8463db6816Hal Finkel// 1099f823f94374917174f96a7689955b8463db6816Hal Finkel// This pass identifies loops where we can generate the PPC branch instructions 1199f823f94374917174f96a7689955b8463db6816Hal Finkel// that decrement and test the count register (CTR) (bdnz and friends). 1299f823f94374917174f96a7689955b8463db6816Hal Finkel// 1399f823f94374917174f96a7689955b8463db6816Hal Finkel// The pattern that defines the induction variable can changed depending on 1499f823f94374917174f96a7689955b8463db6816Hal Finkel// prior optimizations. For example, the IndVarSimplify phase run by 'opt' 1599f823f94374917174f96a7689955b8463db6816Hal Finkel// normalizes induction variables, and the Loop Strength Reduction pass 1699f823f94374917174f96a7689955b8463db6816Hal Finkel// run by 'llc' may also make changes to the induction variable. 1799f823f94374917174f96a7689955b8463db6816Hal Finkel// 1899f823f94374917174f96a7689955b8463db6816Hal Finkel// Criteria for CTR loops: 1999f823f94374917174f96a7689955b8463db6816Hal Finkel// - Countable loops (w/ ind. var for a trip count) 2099f823f94374917174f96a7689955b8463db6816Hal Finkel// - Try inner-most loops first 2199f823f94374917174f96a7689955b8463db6816Hal Finkel// - No nested CTR loops. 2299f823f94374917174f96a7689955b8463db6816Hal Finkel// - No function calls in loops. 2399f823f94374917174f96a7689955b8463db6816Hal Finkel// 2499f823f94374917174f96a7689955b8463db6816Hal Finkel//===----------------------------------------------------------------------===// 2599f823f94374917174f96a7689955b8463db6816Hal Finkel 2699f823f94374917174f96a7689955b8463db6816Hal Finkel#define DEBUG_TYPE "ctrloops" 27b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 28b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/Transforms/Scalar.h" 2999f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/ADT/Statistic.h" 30b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/ADT/STLExtras.h" 31b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/Analysis/Dominators.h" 32b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/Analysis/LoopInfo.h" 33b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/Analysis/ScalarEvolutionExpander.h" 340b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 35b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/IR/DerivedTypes.h" 36bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel#include "llvm/IR/InlineAsm.h" 37b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/IR/Instructions.h" 38b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/IR/IntrinsicInst.h" 39b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/IR/Module.h" 40d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/PassSupport.h" 41b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/Support/CommandLine.h" 4299f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/Support/Debug.h" 43b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/Support/ValueHandle.h" 4499f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/Support/raw_ostream.h" 45b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/Transforms/Utils/BasicBlockUtils.h" 46b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/Transforms/Utils/Local.h" 474e6b24ffcfafbc0c5eda1bb89163ccd56f394fdfHal Finkel#include "llvm/Transforms/Utils/LoopUtils.h" 48b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "llvm/Target/TargetLibraryInfo.h" 49b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "PPCTargetMachine.h" 50b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include "PPC.h" 51b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 52e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#ifndef NDEBUG 53e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#include "llvm/CodeGen/MachineDominators.h" 54e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#include "llvm/CodeGen/MachineFunction.h" 55e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#include "llvm/CodeGen/MachineFunctionPass.h" 56e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#include "llvm/CodeGen/MachineRegisterInfo.h" 57e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#endif 58e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 5999f823f94374917174f96a7689955b8463db6816Hal Finkel#include <algorithm> 60b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#include <vector> 6199f823f94374917174f96a7689955b8463db6816Hal Finkel 6299f823f94374917174f96a7689955b8463db6816Hal Finkelusing namespace llvm; 6399f823f94374917174f96a7689955b8463db6816Hal Finkel 64b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#ifndef NDEBUG 65b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkelstatic cl::opt<int> CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1)); 66b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#endif 67b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 6899f823f94374917174f96a7689955b8463db6816Hal FinkelSTATISTIC(NumCTRLoops, "Number of loops converted to CTR loops"); 6999f823f94374917174f96a7689955b8463db6816Hal Finkel 7096848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszeknamespace llvm { 7196848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek void initializePPCCTRLoopsPass(PassRegistry&); 72e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#ifndef NDEBUG 73e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel void initializePPCCTRLoopsVerifyPass(PassRegistry&); 74e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#endif 7596848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek} 7696848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek 7799f823f94374917174f96a7689955b8463db6816Hal Finkelnamespace { 78b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel struct PPCCTRLoops : public FunctionPass { 79b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 80b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#ifndef NDEBUG 81b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel static int Counter; 82b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#endif 8399f823f94374917174f96a7689955b8463db6816Hal Finkel 8499f823f94374917174f96a7689955b8463db6816Hal Finkel public: 85b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel static char ID; 8699f823f94374917174f96a7689955b8463db6816Hal Finkel 87b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel PPCCTRLoops() : FunctionPass(ID), TM(0) { 88b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry()); 89b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel } 90b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel PPCCTRLoops(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) { 9196848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry()); 9296848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek } 9399f823f94374917174f96a7689955b8463db6816Hal Finkel 94b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel virtual bool runOnFunction(Function &F); 9599f823f94374917174f96a7689955b8463db6816Hal Finkel 9699f823f94374917174f96a7689955b8463db6816Hal Finkel virtual void getAnalysisUsage(AnalysisUsage &AU) const { 97b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel AU.addRequired<LoopInfo>(); 98b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel AU.addPreserved<LoopInfo>(); 99b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel AU.addRequired<DominatorTree>(); 100b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel AU.addPreserved<DominatorTree>(); 101b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel AU.addRequired<ScalarEvolution>(); 10299f823f94374917174f96a7689955b8463db6816Hal Finkel } 10399f823f94374917174f96a7689955b8463db6816Hal Finkel 10499f823f94374917174f96a7689955b8463db6816Hal Finkel private: 105c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel bool mightUseCTR(const Triple &TT, BasicBlock *BB); 106b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel bool convertToCTRLoop(Loop *L); 10708f92c98ac1cdb43ec35653536c89964401d936cHal Finkel 10899f823f94374917174f96a7689955b8463db6816Hal Finkel private: 109b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel PPCTargetMachine *TM; 110b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel LoopInfo *LI; 111b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel ScalarEvolution *SE; 112b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel DataLayout *TD; 113b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel DominatorTree *DT; 114b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel const TargetLibraryInfo *LibInfo; 11599f823f94374917174f96a7689955b8463db6816Hal Finkel }; 116b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 117b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel char PPCCTRLoops::ID = 0; 118b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#ifndef NDEBUG 119b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel int PPCCTRLoops::Counter = 0; 120b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#endif 121e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 122e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#ifndef NDEBUG 123e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel struct PPCCTRLoopsVerify : public MachineFunctionPass { 124e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel public: 125e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel static char ID; 126e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 127e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel PPCCTRLoopsVerify() : MachineFunctionPass(ID) { 128e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel initializePPCCTRLoopsVerifyPass(*PassRegistry::getPassRegistry()); 129e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 130e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 131e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel virtual void getAnalysisUsage(AnalysisUsage &AU) const { 132e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel AU.addRequired<MachineDominatorTree>(); 133e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel MachineFunctionPass::getAnalysisUsage(AU); 134e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 135e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 136e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel virtual bool runOnMachineFunction(MachineFunction &MF); 137e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 138e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel private: 139e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel MachineDominatorTree *MDT; 140e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel }; 141e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 142e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel char PPCCTRLoopsVerify::ID = 0; 143e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#endif // NDEBUG 14499f823f94374917174f96a7689955b8463db6816Hal Finkel} // end anonymous namespace 14599f823f94374917174f96a7689955b8463db6816Hal Finkel 14696848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof ParzyszekINITIALIZE_PASS_BEGIN(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops", 14796848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek false, false) 148b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal FinkelINITIALIZE_PASS_DEPENDENCY(DominatorTree) 149b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal FinkelINITIALIZE_PASS_DEPENDENCY(LoopInfo) 150b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal FinkelINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 15196848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof ParzyszekINITIALIZE_PASS_END(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops", 15296848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek false, false) 15399f823f94374917174f96a7689955b8463db6816Hal Finkel 154b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal FinkelFunctionPass *llvm::createPPCCTRLoops(PPCTargetMachine &TM) { 155b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel return new PPCCTRLoops(TM); 15699f823f94374917174f96a7689955b8463db6816Hal Finkel} 15799f823f94374917174f96a7689955b8463db6816Hal Finkel 158e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#ifndef NDEBUG 159e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal FinkelINITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 160e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel "PowerPC CTR Loops Verify", false, false) 161e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal FinkelINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 162e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal FinkelINITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", 163e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel "PowerPC CTR Loops Verify", false, false) 164e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 165e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal FinkelFunctionPass *llvm::createPPCCTRLoopsVerify() { 166e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel return new PPCCTRLoopsVerify(); 167e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel} 168e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#endif // NDEBUG 169e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 170b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkelbool PPCCTRLoops::runOnFunction(Function &F) { 171b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel LI = &getAnalysis<LoopInfo>(); 172b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel SE = &getAnalysis<ScalarEvolution>(); 173b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel DT = &getAnalysis<DominatorTree>(); 174b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel TD = getAnalysisIfAvailable<DataLayout>(); 175b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel LibInfo = getAnalysisIfAvailable<TargetLibraryInfo>(); 17699f823f94374917174f96a7689955b8463db6816Hal Finkel 177b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel bool MadeChange = false; 17899f823f94374917174f96a7689955b8463db6816Hal Finkel 179b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel for (LoopInfo::iterator I = LI->begin(), E = LI->end(); 18099f823f94374917174f96a7689955b8463db6816Hal Finkel I != E; ++I) { 181b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Loop *L = *I; 182b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (!L->getParentLoop()) 183b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel MadeChange |= convertToCTRLoop(L); 18499f823f94374917174f96a7689955b8463db6816Hal Finkel } 18599f823f94374917174f96a7689955b8463db6816Hal Finkel 186b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel return MadeChange; 18799f823f94374917174f96a7689955b8463db6816Hal Finkel} 18899f823f94374917174f96a7689955b8463db6816Hal Finkel 189c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkelbool PPCCTRLoops::mightUseCTR(const Triple &TT, BasicBlock *BB) { 190c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel for (BasicBlock::iterator J = BB->begin(), JE = BB->end(); 191c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel J != JE; ++J) { 192c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (CallInst *CI = dyn_cast<CallInst>(J)) { 193bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel if (InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue())) { 194bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel // Inline ASM is okay, unless it clobbers the ctr register. 195bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel InlineAsm::ConstraintInfoVector CIV = IA->ParseConstraints(); 196bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel for (unsigned i = 0, ie = CIV.size(); i < ie; ++i) { 197bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel InlineAsm::ConstraintInfo &C = CIV[i]; 198bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel if (C.Type != InlineAsm::isInput) 199bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel for (unsigned j = 0, je = C.Codes.size(); j < je; ++j) 200bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel if (StringRef(C.Codes[j]).equals_lower("{ctr}")) 201bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel return true; 202bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel } 203bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel 204bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel continue; 205bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel } 206bf0bc3b2a2e11ff7e79b881ca82324fe17919a97Hal Finkel 207c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (!TM) 208c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 209c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel const TargetLowering *TLI = TM->getTargetLowering(); 210c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 211c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (Function *F = CI->getCalledFunction()) { 212c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // Most intrinsics don't become function calls, but some might. 213c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // sin, cos, exp and log are always calls. 214c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel unsigned Opcode; 215c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (F->getIntrinsicID() != Intrinsic::not_intrinsic) { 216c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel switch (F->getIntrinsicID()) { 217c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel default: continue; 218c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 219c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel// VisualStudio defines setjmp as _setjmp 220c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel#if defined(_MSC_VER) && defined(setjmp) && \ 221c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel !defined(setjmp_undefined_for_msvc) 222c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel# pragma push_macro("setjmp") 223c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel# undef setjmp 224c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel# define setjmp_undefined_for_msvc 225c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel#endif 226c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 227c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::setjmp: 228c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 229c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel#if defined(_MSC_VER) && defined(setjmp_undefined_for_msvc) 230c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // let's return it to _setjmp state 231c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel# pragma pop_macro("setjmp") 232c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel# undef setjmp_undefined_for_msvc 233c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel#endif 234c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 235c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::longjmp: 236c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::memcpy: 237c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::memmove: 238c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::memset: 239c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::powi: 240c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::log: 241c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::log2: 242c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::log10: 243c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::exp: 244c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::exp2: 245c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::pow: 246c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::sin: 247c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::cos: 248c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 249c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::sqrt: Opcode = ISD::FSQRT; break; 250c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::floor: Opcode = ISD::FFLOOR; break; 251c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::ceil: Opcode = ISD::FCEIL; break; 252c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::trunc: Opcode = ISD::FTRUNC; break; 253c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::rint: Opcode = ISD::FRINT; break; 254c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case Intrinsic::nearbyint: Opcode = ISD::FNEARBYINT; break; 255c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } 256c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } 257c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 258c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // PowerPC does not use [US]DIVREM or other library calls for 259c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // operations on regular types which are not otherwise library calls 260c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // (i.e. soft float or atomics). If adapting for targets that do, 261c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // additional care is required here. 262c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 263c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel LibFunc::Func Func; 264c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (!F->hasLocalLinkage() && F->hasName() && LibInfo && 265c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel LibInfo->getLibFunc(F->getName(), Func) && 266c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel LibInfo->hasOptimizedCodeGen(Func)) { 267c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // Non-read-only functions are never treated as intrinsics. 268c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (!CI->onlyReadsMemory()) 269c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 270c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 271c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // Conversion happens only for FP calls. 272c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (!CI->getArgOperand(0)->getType()->isFloatingPointTy()) 273c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 274c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 275c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel switch (Func) { 276c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel default: return true; 277c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::copysign: 278c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::copysignf: 279c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::copysignl: 280c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel continue; // ISD::FCOPYSIGN is never a library call. 281c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::fabs: 282c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::fabsf: 283c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::fabsl: 284c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel continue; // ISD::FABS is never a library call. 285c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::sqrt: 286c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::sqrtf: 287c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::sqrtl: 288c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel Opcode = ISD::FSQRT; break; 289c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::floor: 290c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::floorf: 291c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::floorl: 292c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel Opcode = ISD::FFLOOR; break; 293c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::nearbyint: 294c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::nearbyintf: 295c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::nearbyintl: 296c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel Opcode = ISD::FNEARBYINT; break; 297c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::ceil: 298c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::ceilf: 299c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::ceill: 300c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel Opcode = ISD::FCEIL; break; 301c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::rint: 302c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::rintf: 303c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::rintl: 304c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel Opcode = ISD::FRINT; break; 305c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::trunc: 306c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::truncf: 307c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel case LibFunc::truncl: 308c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel Opcode = ISD::FTRUNC; break; 309c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } 310c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 311c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel MVT VTy = 312c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel TLI->getSimpleValueType(CI->getArgOperand(0)->getType(), true); 313c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (VTy == MVT::Other) 314c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 315c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 316c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (TLI->isOperationLegalOrCustom(Opcode, VTy)) 317c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel continue; 318c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel else if (VTy.isVector() && 319c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel TLI->isOperationLegalOrCustom(Opcode, VTy.getScalarType())) 320c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel continue; 321c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 322c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 323c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } 324c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } 325c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 326c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 327c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } else if (isa<BinaryOperator>(J) && 328c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel J->getType()->getScalarType()->isPPC_FP128Ty()) { 329c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // Most operations on ppc_f128 values become calls. 330c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 331c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } else if (isa<UIToFPInst>(J) || isa<SIToFPInst>(J) || 332c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel isa<FPToUIInst>(J) || isa<FPToSIInst>(J)) { 333c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel CastInst *CI = cast<CastInst>(J); 334c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (CI->getSrcTy()->getScalarType()->isPPC_FP128Ty() || 335c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel CI->getDestTy()->getScalarType()->isPPC_FP128Ty() || 336c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel (TT.isArch32Bit() && 337c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel (CI->getSrcTy()->getScalarType()->isIntegerTy(64) || 338c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel CI->getDestTy()->getScalarType()->isIntegerTy(64)) 339c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel )) 340c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 341c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } else if (isa<IndirectBrInst>(J) || isa<InvokeInst>(J)) { 342c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // On PowerPC, indirect jumps use the counter register. 343c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 344c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } else if (SwitchInst *SI = dyn_cast<SwitchInst>(J)) { 345c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (!TM) 346c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 347c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel const TargetLowering *TLI = TM->getTargetLowering(); 348c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 349c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (TLI->supportJumpTables() && 350c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel SI->getNumCases()+1 >= (unsigned) TLI->getMinimumJumpTableEntries()) 351c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return true; 352c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } 353c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel } 354c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 355c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return false; 356c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel} 357c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 358b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkelbool PPCCTRLoops::convertToCTRLoop(Loop *L) { 359b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel bool MadeChange = false; 36099f823f94374917174f96a7689955b8463db6816Hal Finkel 361b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Triple TT = Triple(L->getHeader()->getParent()->getParent()-> 362b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel getTargetTriple()); 363b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (!TT.isArch32Bit() && !TT.isArch64Bit()) 364b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel return MadeChange; // Unknown arch. type. 3651448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel 366b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // Process nested loops first. 367b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) { 368b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel MadeChange |= convertToCTRLoop(*I); 369b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel } 3701448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel 371b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // If a nested loop has been converted, then we can't convert this loop. 372b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (MadeChange) 373b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel return MadeChange; 374b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 375b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#ifndef NDEBUG 376b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // Stop trying after reaching the limit (if any). 377b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel int Limit = CTRLoopLimit; 378b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (Limit >= 0) { 379b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (Counter >= CTRLoopLimit) 380b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel return false; 381b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Counter++; 382b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel } 383b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel#endif 384b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 385b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // We don't want to spill/restore the counter register, and so we don't 386b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // want to use the counter register if the loop contains calls. 387b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel for (Loop::block_iterator I = L->block_begin(), IE = L->block_end(); 388c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel I != IE; ++I) 389c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (mightUseCTR(TT, *I)) 390c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel return MadeChange; 39199f823f94374917174f96a7689955b8463db6816Hal Finkel 392b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel SmallVector<BasicBlock*, 4> ExitingBlocks; 393b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel L->getExitingBlocks(ExitingBlocks); 394b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 395b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel BasicBlock *CountedExitBlock = 0; 396b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel const SCEV *ExitCount = 0; 397b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel BranchInst *CountedExitBranch = 0; 398b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel for (SmallVector<BasicBlock*, 4>::iterator I = ExitingBlocks.begin(), 399b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel IE = ExitingBlocks.end(); I != IE; ++I) { 400b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel const SCEV *EC = SE->getExitCount(L, *I); 401b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel DEBUG(dbgs() << "Exit Count for " << *L << " from block " << 402b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel (*I)->getName() << ": " << *EC << "\n"); 403b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (isa<SCEVCouldNotCompute>(EC)) 404b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel continue; 405b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (const SCEVConstant *ConstEC = dyn_cast<SCEVConstant>(EC)) { 406b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (ConstEC->getValue()->isZero()) 407b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel continue; 408b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel } else if (!SE->isLoopInvariant(EC, L)) 409b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel continue; 410b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 411b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // We now have a loop-invariant count of loop iterations (which is not the 412b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // constant zero) for which we know that this loop will not exit via this 413b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // exisiting block. 414b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 415b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // We need to make sure that this block will run on every loop iteration. 416b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // For this to be true, we must dominate all blocks with backedges. Such 417b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // blocks are in-loop predecessors to the header block. 418b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel bool NotAlways = false; 419b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel for (pred_iterator PI = pred_begin(L->getHeader()), 420b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel PIE = pred_end(L->getHeader()); PI != PIE; ++PI) { 421b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (!L->contains(*PI)) 422b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel continue; 42399f823f94374917174f96a7689955b8463db6816Hal Finkel 424b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (!DT->dominates(*I, *PI)) { 425b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel NotAlways = true; 426b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel break; 42799f823f94374917174f96a7689955b8463db6816Hal Finkel } 42899f823f94374917174f96a7689955b8463db6816Hal Finkel } 42999f823f94374917174f96a7689955b8463db6816Hal Finkel 430b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (NotAlways) 431b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel continue; 43299f823f94374917174f96a7689955b8463db6816Hal Finkel 433b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // Make sure this blocks ends with a conditional branch. 434b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Instruction *TI = (*I)->getTerminator(); 435b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (!TI) 436b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel continue; 43799f823f94374917174f96a7689955b8463db6816Hal Finkel 438b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 439b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (!BI->isConditional()) 44099f823f94374917174f96a7689955b8463db6816Hal Finkel continue; 44199f823f94374917174f96a7689955b8463db6816Hal Finkel 442b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel CountedExitBranch = BI; 443b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel } else 444b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel continue; 44599f823f94374917174f96a7689955b8463db6816Hal Finkel 446b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // Note that this block may not be the loop latch block, even if the loop 447b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // has a latch block. 448b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel CountedExitBlock = *I; 449b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel ExitCount = EC; 450b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel break; 45199f823f94374917174f96a7689955b8463db6816Hal Finkel } 45299f823f94374917174f96a7689955b8463db6816Hal Finkel 453b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (!CountedExitBlock) 454b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel return MadeChange; 455b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 456b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel BasicBlock *Preheader = L->getLoopPreheader(); 457c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel 458c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // If we don't have a preheader, then insert one. If we already have a 459c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // preheader, then we can use it (except if the preheader contains a use of 460c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // the CTR register because some such uses might be reordered by the 461c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel // selection DAG after the mtctr instruction). 462c482454e3cc2a33a2cf2d1cf0881c7c5e2641c80Hal Finkel if (!Preheader || mightUseCTR(TT, Preheader)) 46308f92c98ac1cdb43ec35653536c89964401d936cHal Finkel Preheader = InsertPreheaderForLoop(L, this); 464b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (!Preheader) 465b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel return MadeChange; 466b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 467b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel DEBUG(dbgs() << "Preheader for exit count: " << Preheader->getName() << "\n"); 468b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 469b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // Insert the count into the preheader and replace the condition used by the 470b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // selected branch. 471b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel MadeChange = true; 472b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 473b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel SCEVExpander SCEVE(*SE, "loopcnt"); 474b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel LLVMContext &C = SE->getContext(); 475b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Type *CountType = TT.isArch64Bit() ? Type::getInt64Ty(C) : 476b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Type::getInt32Ty(C); 477b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (!ExitCount->getType()->isPointerTy() && 478b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel ExitCount->getType() != CountType) 479b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel ExitCount = SE->getZeroExtendExpr(ExitCount, CountType); 480b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel ExitCount = SE->getAddExpr(ExitCount, 481b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel SE->getConstant(CountType, 1)); 482b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Value *ECValue = SCEVE.expandCodeFor(ExitCount, CountType, 483b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Preheader->getTerminator()); 484b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 485b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel IRBuilder<> CountBuilder(Preheader->getTerminator()); 486b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Module *M = Preheader->getParent()->getParent(); 487b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Value *MTCTRFunc = Intrinsic::getDeclaration(M, Intrinsic::ppc_mtctr, 488b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel CountType); 489b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel CountBuilder.CreateCall(MTCTRFunc, ECValue); 490b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 491b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel IRBuilder<> CondBuilder(CountedExitBranch); 492b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Value *DecFunc = 493b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Intrinsic::getDeclaration(M, Intrinsic::ppc_is_decremented_ctr_nonzero); 494b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Value *NewCond = CondBuilder.CreateCall(DecFunc); 495b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel Value *OldCond = CountedExitBranch->getCondition(); 496b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel CountedExitBranch->setCondition(NewCond); 497b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 498b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // The false branch must exit the loop. 499b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel if (!L->contains(CountedExitBranch->getSuccessor(0))) 500b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel CountedExitBranch->swapSuccessors(); 501b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel 502b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // The old condition may be dead now, and may have even created a dead PHI 503b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel // (the original induction variable). 504b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel RecursivelyDeleteTriviallyDeadInstructions(OldCond); 505b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel DeleteDeadPHIs(CountedExitBlock); 5069887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel 507b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel ++NumCTRLoops; 508b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel return MadeChange; 509b1fd3cd78f8acd21dbf514b75fef991827c343b6Hal Finkel} 5109887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel 511e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#ifndef NDEBUG 512e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkelstatic bool clobbersCTR(const MachineInstr *MI) { 513e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 514e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel const MachineOperand &MO = MI->getOperand(i); 515e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (MO.isReg()) { 516e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (MO.isDef() && (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) 517e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel return true; 518e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } else if (MO.isRegMask()) { 519e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (MO.clobbersPhysReg(PPC::CTR) || MO.clobbersPhysReg(PPC::CTR8)) 520e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel return true; 521e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 522e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 523e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 524e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel return false; 525e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel} 526e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 527e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkelstatic bool verifyCTRBranch(MachineBasicBlock *MBB, 528e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel MachineBasicBlock::iterator I) { 529e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel MachineBasicBlock::iterator BI = I; 530e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel SmallSet<MachineBasicBlock *, 16> Visited; 531e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel SmallVector<MachineBasicBlock *, 8> Preds; 532e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel bool CheckPreds; 533e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 534e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (I == MBB->begin()) { 535e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel Visited.insert(MBB); 536e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel goto queue_preds; 537e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } else 538e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel --I; 539e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 540e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkelcheck_block: 541e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel Visited.insert(MBB); 542e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (I == MBB->end()) 543e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel goto queue_preds; 544e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 545e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel CheckPreds = true; 546e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel for (MachineBasicBlock::iterator IE = MBB->begin();; --I) { 547e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel unsigned Opc = I->getOpcode(); 54885c08b059ce4248ee739e756cf717a9b429e2ec2Hal Finkel if (Opc == PPC::MTCTRloop || Opc == PPC::MTCTR8loop) { 549e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel CheckPreds = false; 550e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel break; 551e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 552e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 553e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (I != BI && clobbersCTR(I)) { 554e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel DEBUG(dbgs() << "BB#" << MBB->getNumber() << " (" << 555e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel MBB->getFullName() << ") instruction " << *I << 556e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel " clobbers CTR, invalidating " << "BB#" << 557e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel BI->getParent()->getNumber() << " (" << 558e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel BI->getParent()->getFullName() << ") instruction " << 559e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel *BI << "\n"); 560e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel return false; 561e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 562e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 563e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (I == IE) 564e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel break; 565e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 566e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 567e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (!CheckPreds && Preds.empty()) 568e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel return true; 569e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 570e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (CheckPreds) { 571e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkelqueue_preds: 572e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (MachineFunction::iterator(MBB) == MBB->getParent()->begin()) { 573e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel DEBUG(dbgs() << "Unable to find a MTCTR instruction for BB#" << 574e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel BI->getParent()->getNumber() << " (" << 575e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel BI->getParent()->getFullName() << ") instruction " << 576e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel *BI << "\n"); 577e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel return false; 578e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 579e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 580e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 581e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel PIE = MBB->pred_end(); PI != PIE; ++PI) 582e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel Preds.push_back(*PI); 583e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 584e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 585e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel do { 586e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel MBB = Preds.pop_back_val(); 587e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (!Visited.count(MBB)) { 588e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel I = MBB->getLastNonDebugInstr(); 589e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel goto check_block; 590e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 591e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } while (!Preds.empty()); 592e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 593e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel return true; 594e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel} 595e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 596e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkelbool PPCCTRLoopsVerify::runOnMachineFunction(MachineFunction &MF) { 597e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel MDT = &getAnalysis<MachineDominatorTree>(); 598e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 599e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel // Verify that all bdnz/bdz instructions are dominated by a loop mtctr before 600e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel // any other instructions that might clobber the ctr register. 601e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel for (MachineFunction::iterator I = MF.begin(), IE = MF.end(); 602e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel I != IE; ++I) { 603e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel MachineBasicBlock *MBB = I; 604e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (!MDT->isReachableFromEntry(MBB)) 605e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel continue; 606e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 607e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel for (MachineBasicBlock::iterator MII = MBB->getFirstTerminator(), 608e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel MIIE = MBB->end(); MII != MIIE; ++MII) { 609e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel unsigned Opc = MII->getOpcode(); 610e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (Opc == PPC::BDNZ8 || Opc == PPC::BDNZ || 611e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel Opc == PPC::BDZ8 || Opc == PPC::BDZ) 612e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel if (!verifyCTRBranch(MBB, MII)) 613e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel llvm_unreachable("Invalid PPC CTR loop!"); 614e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 615e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel } 616e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 617e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel return false; 618e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel} 619e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel#endif // NDEBUG 620e50c8c1f81a38f0ecebafa5dc60a163814a9713aHal Finkel 621