xref: /minix3/external/bsd/llvm/dist/llvm/lib/Target/PowerPC/PPCCTRLoops.cpp (revision 0a6a1f1d05b60e214de2f05a7310ddd1f0e590e7)
1f4a2713aSLionel Sambuc //===-- PPCCTRLoops.cpp - Identify and generate CTR loops -----------------===//
2f4a2713aSLionel Sambuc //
3f4a2713aSLionel Sambuc //                     The LLVM Compiler Infrastructure
4f4a2713aSLionel Sambuc //
5f4a2713aSLionel Sambuc // This file is distributed under the University of Illinois Open Source
6f4a2713aSLionel Sambuc // License. See LICENSE.TXT for details.
7f4a2713aSLionel Sambuc //
8f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
9f4a2713aSLionel Sambuc //
10f4a2713aSLionel Sambuc // This pass identifies loops where we can generate the PPC branch instructions
11f4a2713aSLionel Sambuc // that decrement and test the count register (CTR) (bdnz and friends).
12f4a2713aSLionel Sambuc //
13f4a2713aSLionel Sambuc // The pattern that defines the induction variable can changed depending on
14f4a2713aSLionel Sambuc // prior optimizations.  For example, the IndVarSimplify phase run by 'opt'
15f4a2713aSLionel Sambuc // normalizes induction variables, and the Loop Strength Reduction pass
16f4a2713aSLionel Sambuc // run by 'llc' may also make changes to the induction variable.
17f4a2713aSLionel Sambuc //
18f4a2713aSLionel Sambuc // Criteria for CTR loops:
19f4a2713aSLionel Sambuc //  - Countable loops (w/ ind. var for a trip count)
20f4a2713aSLionel Sambuc //  - Try inner-most loops first
21f4a2713aSLionel Sambuc //  - No nested CTR loops.
22f4a2713aSLionel Sambuc //  - No function calls in loops.
23f4a2713aSLionel Sambuc //
24f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
25f4a2713aSLionel Sambuc 
26f4a2713aSLionel Sambuc #include "llvm/Transforms/Scalar.h"
27*0a6a1f1dSLionel Sambuc #include "PPC.h"
28*0a6a1f1dSLionel Sambuc #include "PPCTargetMachine.h"
29f4a2713aSLionel Sambuc #include "llvm/ADT/STLExtras.h"
30*0a6a1f1dSLionel Sambuc #include "llvm/ADT/Statistic.h"
31f4a2713aSLionel Sambuc #include "llvm/Analysis/LoopInfo.h"
32f4a2713aSLionel Sambuc #include "llvm/Analysis/ScalarEvolutionExpander.h"
33f4a2713aSLionel Sambuc #include "llvm/IR/Constants.h"
34f4a2713aSLionel Sambuc #include "llvm/IR/DerivedTypes.h"
35*0a6a1f1dSLionel Sambuc #include "llvm/IR/Dominators.h"
36f4a2713aSLionel Sambuc #include "llvm/IR/InlineAsm.h"
37f4a2713aSLionel Sambuc #include "llvm/IR/Instructions.h"
38f4a2713aSLionel Sambuc #include "llvm/IR/IntrinsicInst.h"
39f4a2713aSLionel Sambuc #include "llvm/IR/Module.h"
40*0a6a1f1dSLionel Sambuc #include "llvm/IR/ValueHandle.h"
41f4a2713aSLionel Sambuc #include "llvm/PassSupport.h"
42f4a2713aSLionel Sambuc #include "llvm/Support/CommandLine.h"
43f4a2713aSLionel Sambuc #include "llvm/Support/Debug.h"
44f4a2713aSLionel Sambuc #include "llvm/Support/raw_ostream.h"
45*0a6a1f1dSLionel Sambuc #include "llvm/Target/TargetLibraryInfo.h"
46f4a2713aSLionel Sambuc #include "llvm/Transforms/Utils/BasicBlockUtils.h"
47f4a2713aSLionel Sambuc #include "llvm/Transforms/Utils/Local.h"
48f4a2713aSLionel Sambuc #include "llvm/Transforms/Utils/LoopUtils.h"
49f4a2713aSLionel Sambuc 
50f4a2713aSLionel Sambuc #ifndef NDEBUG
51f4a2713aSLionel Sambuc #include "llvm/CodeGen/MachineDominators.h"
52f4a2713aSLionel Sambuc #include "llvm/CodeGen/MachineFunction.h"
53f4a2713aSLionel Sambuc #include "llvm/CodeGen/MachineFunctionPass.h"
54f4a2713aSLionel Sambuc #include "llvm/CodeGen/MachineRegisterInfo.h"
55f4a2713aSLionel Sambuc #endif
56f4a2713aSLionel Sambuc 
57f4a2713aSLionel Sambuc #include <algorithm>
58f4a2713aSLionel Sambuc #include <vector>
59f4a2713aSLionel Sambuc 
60f4a2713aSLionel Sambuc using namespace llvm;
61f4a2713aSLionel Sambuc 
62*0a6a1f1dSLionel Sambuc #define DEBUG_TYPE "ctrloops"
63*0a6a1f1dSLionel Sambuc 
64f4a2713aSLionel Sambuc #ifndef NDEBUG
65f4a2713aSLionel Sambuc static cl::opt<int> CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1));
66f4a2713aSLionel Sambuc #endif
67f4a2713aSLionel Sambuc 
68f4a2713aSLionel Sambuc STATISTIC(NumCTRLoops, "Number of loops converted to CTR loops");
69f4a2713aSLionel Sambuc 
70f4a2713aSLionel Sambuc namespace llvm {
71f4a2713aSLionel Sambuc   void initializePPCCTRLoopsPass(PassRegistry&);
72f4a2713aSLionel Sambuc #ifndef NDEBUG
73f4a2713aSLionel Sambuc   void initializePPCCTRLoopsVerifyPass(PassRegistry&);
74f4a2713aSLionel Sambuc #endif
75f4a2713aSLionel Sambuc }
76f4a2713aSLionel Sambuc 
77f4a2713aSLionel Sambuc namespace {
78f4a2713aSLionel Sambuc   struct PPCCTRLoops : public FunctionPass {
79f4a2713aSLionel Sambuc 
80f4a2713aSLionel Sambuc #ifndef NDEBUG
81f4a2713aSLionel Sambuc     static int Counter;
82f4a2713aSLionel Sambuc #endif
83f4a2713aSLionel Sambuc 
84f4a2713aSLionel Sambuc   public:
85f4a2713aSLionel Sambuc     static char ID;
86f4a2713aSLionel Sambuc 
PPCCTRLoops__anon5f4cbdc10111::PPCCTRLoops87*0a6a1f1dSLionel Sambuc     PPCCTRLoops() : FunctionPass(ID), TM(nullptr) {
88f4a2713aSLionel Sambuc       initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry());
89f4a2713aSLionel Sambuc     }
PPCCTRLoops__anon5f4cbdc10111::PPCCTRLoops90f4a2713aSLionel Sambuc     PPCCTRLoops(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {
91f4a2713aSLionel Sambuc       initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry());
92f4a2713aSLionel Sambuc     }
93f4a2713aSLionel Sambuc 
94*0a6a1f1dSLionel Sambuc     bool runOnFunction(Function &F) override;
95f4a2713aSLionel Sambuc 
getAnalysisUsage__anon5f4cbdc10111::PPCCTRLoops96*0a6a1f1dSLionel Sambuc     void getAnalysisUsage(AnalysisUsage &AU) const override {
97f4a2713aSLionel Sambuc       AU.addRequired<LoopInfo>();
98f4a2713aSLionel Sambuc       AU.addPreserved<LoopInfo>();
99*0a6a1f1dSLionel Sambuc       AU.addRequired<DominatorTreeWrapperPass>();
100*0a6a1f1dSLionel Sambuc       AU.addPreserved<DominatorTreeWrapperPass>();
101f4a2713aSLionel Sambuc       AU.addRequired<ScalarEvolution>();
102f4a2713aSLionel Sambuc     }
103f4a2713aSLionel Sambuc 
104f4a2713aSLionel Sambuc   private:
105f4a2713aSLionel Sambuc     bool mightUseCTR(const Triple &TT, BasicBlock *BB);
106f4a2713aSLionel Sambuc     bool convertToCTRLoop(Loop *L);
107f4a2713aSLionel Sambuc 
108f4a2713aSLionel Sambuc   private:
109f4a2713aSLionel Sambuc     PPCTargetMachine *TM;
110f4a2713aSLionel Sambuc     LoopInfo *LI;
111f4a2713aSLionel Sambuc     ScalarEvolution *SE;
112*0a6a1f1dSLionel Sambuc     const DataLayout *DL;
113f4a2713aSLionel Sambuc     DominatorTree *DT;
114f4a2713aSLionel Sambuc     const TargetLibraryInfo *LibInfo;
115f4a2713aSLionel Sambuc   };
116f4a2713aSLionel Sambuc 
117f4a2713aSLionel Sambuc   char PPCCTRLoops::ID = 0;
118f4a2713aSLionel Sambuc #ifndef NDEBUG
119f4a2713aSLionel Sambuc   int PPCCTRLoops::Counter = 0;
120f4a2713aSLionel Sambuc #endif
121f4a2713aSLionel Sambuc 
122f4a2713aSLionel Sambuc #ifndef NDEBUG
123f4a2713aSLionel Sambuc   struct PPCCTRLoopsVerify : public MachineFunctionPass {
124f4a2713aSLionel Sambuc   public:
125f4a2713aSLionel Sambuc     static char ID;
126f4a2713aSLionel Sambuc 
PPCCTRLoopsVerify__anon5f4cbdc10111::PPCCTRLoopsVerify127f4a2713aSLionel Sambuc     PPCCTRLoopsVerify() : MachineFunctionPass(ID) {
128f4a2713aSLionel Sambuc       initializePPCCTRLoopsVerifyPass(*PassRegistry::getPassRegistry());
129f4a2713aSLionel Sambuc     }
130f4a2713aSLionel Sambuc 
getAnalysisUsage__anon5f4cbdc10111::PPCCTRLoopsVerify131*0a6a1f1dSLionel Sambuc     void getAnalysisUsage(AnalysisUsage &AU) const override {
132f4a2713aSLionel Sambuc       AU.addRequired<MachineDominatorTree>();
133f4a2713aSLionel Sambuc       MachineFunctionPass::getAnalysisUsage(AU);
134f4a2713aSLionel Sambuc     }
135f4a2713aSLionel Sambuc 
136*0a6a1f1dSLionel Sambuc     bool runOnMachineFunction(MachineFunction &MF) override;
137f4a2713aSLionel Sambuc 
138f4a2713aSLionel Sambuc   private:
139f4a2713aSLionel Sambuc     MachineDominatorTree *MDT;
140f4a2713aSLionel Sambuc   };
141f4a2713aSLionel Sambuc 
142f4a2713aSLionel Sambuc   char PPCCTRLoopsVerify::ID = 0;
143f4a2713aSLionel Sambuc #endif // NDEBUG
144f4a2713aSLionel Sambuc } // end anonymous namespace
145f4a2713aSLionel Sambuc 
146f4a2713aSLionel Sambuc INITIALIZE_PASS_BEGIN(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops",
147f4a2713aSLionel Sambuc                       false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)148*0a6a1f1dSLionel Sambuc INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
149f4a2713aSLionel Sambuc INITIALIZE_PASS_DEPENDENCY(LoopInfo)
150f4a2713aSLionel Sambuc INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
151f4a2713aSLionel Sambuc INITIALIZE_PASS_END(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops",
152f4a2713aSLionel Sambuc                     false, false)
153f4a2713aSLionel Sambuc 
154f4a2713aSLionel Sambuc FunctionPass *llvm::createPPCCTRLoops(PPCTargetMachine &TM) {
155f4a2713aSLionel Sambuc   return new PPCCTRLoops(TM);
156f4a2713aSLionel Sambuc }
157f4a2713aSLionel Sambuc 
158f4a2713aSLionel Sambuc #ifndef NDEBUG
159f4a2713aSLionel Sambuc INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
160f4a2713aSLionel Sambuc                       "PowerPC CTR Loops Verify", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)161f4a2713aSLionel Sambuc INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
162f4a2713aSLionel Sambuc INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
163f4a2713aSLionel Sambuc                     "PowerPC CTR Loops Verify", false, false)
164f4a2713aSLionel Sambuc 
165f4a2713aSLionel Sambuc FunctionPass *llvm::createPPCCTRLoopsVerify() {
166f4a2713aSLionel Sambuc   return new PPCCTRLoopsVerify();
167f4a2713aSLionel Sambuc }
168f4a2713aSLionel Sambuc #endif // NDEBUG
169f4a2713aSLionel Sambuc 
runOnFunction(Function & F)170f4a2713aSLionel Sambuc bool PPCCTRLoops::runOnFunction(Function &F) {
171f4a2713aSLionel Sambuc   LI = &getAnalysis<LoopInfo>();
172f4a2713aSLionel Sambuc   SE = &getAnalysis<ScalarEvolution>();
173*0a6a1f1dSLionel Sambuc   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
174*0a6a1f1dSLionel Sambuc   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
175*0a6a1f1dSLionel Sambuc   DL = DLP ? &DLP->getDataLayout() : nullptr;
176f4a2713aSLionel Sambuc   LibInfo = getAnalysisIfAvailable<TargetLibraryInfo>();
177f4a2713aSLionel Sambuc 
178f4a2713aSLionel Sambuc   bool MadeChange = false;
179f4a2713aSLionel Sambuc 
180f4a2713aSLionel Sambuc   for (LoopInfo::iterator I = LI->begin(), E = LI->end();
181f4a2713aSLionel Sambuc        I != E; ++I) {
182f4a2713aSLionel Sambuc     Loop *L = *I;
183f4a2713aSLionel Sambuc     if (!L->getParentLoop())
184f4a2713aSLionel Sambuc       MadeChange |= convertToCTRLoop(L);
185f4a2713aSLionel Sambuc   }
186f4a2713aSLionel Sambuc 
187f4a2713aSLionel Sambuc   return MadeChange;
188f4a2713aSLionel Sambuc }
189f4a2713aSLionel Sambuc 
isLargeIntegerTy(bool Is32Bit,Type * Ty)190*0a6a1f1dSLionel Sambuc static bool isLargeIntegerTy(bool Is32Bit, Type *Ty) {
191*0a6a1f1dSLionel Sambuc   if (IntegerType *ITy = dyn_cast<IntegerType>(Ty))
192*0a6a1f1dSLionel Sambuc     return ITy->getBitWidth() > (Is32Bit ? 32U : 64U);
193*0a6a1f1dSLionel Sambuc 
194*0a6a1f1dSLionel Sambuc   return false;
195*0a6a1f1dSLionel Sambuc }
196*0a6a1f1dSLionel Sambuc 
197*0a6a1f1dSLionel Sambuc // Determining the address of a TLS variable results in a function call in
198*0a6a1f1dSLionel Sambuc // certain TLS models.
memAddrUsesCTR(const PPCTargetMachine * TM,const llvm::Value * MemAddr)199*0a6a1f1dSLionel Sambuc static bool memAddrUsesCTR(const PPCTargetMachine *TM,
200*0a6a1f1dSLionel Sambuc                            const llvm::Value *MemAddr) {
201*0a6a1f1dSLionel Sambuc   const auto *GV = dyn_cast<GlobalValue>(MemAddr);
202*0a6a1f1dSLionel Sambuc   if (!GV)
203*0a6a1f1dSLionel Sambuc     return false;
204*0a6a1f1dSLionel Sambuc   if (!GV->isThreadLocal())
205*0a6a1f1dSLionel Sambuc     return false;
206*0a6a1f1dSLionel Sambuc   if (!TM)
207*0a6a1f1dSLionel Sambuc     return true;
208*0a6a1f1dSLionel Sambuc   TLSModel::Model Model = TM->getTLSModel(GV);
209*0a6a1f1dSLionel Sambuc   return Model == TLSModel::GeneralDynamic || Model == TLSModel::LocalDynamic;
210*0a6a1f1dSLionel Sambuc }
211*0a6a1f1dSLionel Sambuc 
mightUseCTR(const Triple & TT,BasicBlock * BB)212f4a2713aSLionel Sambuc bool PPCCTRLoops::mightUseCTR(const Triple &TT, BasicBlock *BB) {
213f4a2713aSLionel Sambuc   for (BasicBlock::iterator J = BB->begin(), JE = BB->end();
214f4a2713aSLionel Sambuc        J != JE; ++J) {
215f4a2713aSLionel Sambuc     if (CallInst *CI = dyn_cast<CallInst>(J)) {
216f4a2713aSLionel Sambuc       if (InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue())) {
217f4a2713aSLionel Sambuc         // Inline ASM is okay, unless it clobbers the ctr register.
218f4a2713aSLionel Sambuc         InlineAsm::ConstraintInfoVector CIV = IA->ParseConstraints();
219f4a2713aSLionel Sambuc         for (unsigned i = 0, ie = CIV.size(); i < ie; ++i) {
220f4a2713aSLionel Sambuc           InlineAsm::ConstraintInfo &C = CIV[i];
221f4a2713aSLionel Sambuc           if (C.Type != InlineAsm::isInput)
222f4a2713aSLionel Sambuc             for (unsigned j = 0, je = C.Codes.size(); j < je; ++j)
223f4a2713aSLionel Sambuc               if (StringRef(C.Codes[j]).equals_lower("{ctr}"))
224f4a2713aSLionel Sambuc                 return true;
225f4a2713aSLionel Sambuc         }
226f4a2713aSLionel Sambuc 
227f4a2713aSLionel Sambuc         continue;
228f4a2713aSLionel Sambuc       }
229f4a2713aSLionel Sambuc 
230f4a2713aSLionel Sambuc       if (!TM)
231f4a2713aSLionel Sambuc         return true;
232*0a6a1f1dSLionel Sambuc       const TargetLowering *TLI = TM->getSubtargetImpl()->getTargetLowering();
233f4a2713aSLionel Sambuc 
234f4a2713aSLionel Sambuc       if (Function *F = CI->getCalledFunction()) {
235f4a2713aSLionel Sambuc         // Most intrinsics don't become function calls, but some might.
236f4a2713aSLionel Sambuc         // sin, cos, exp and log are always calls.
237f4a2713aSLionel Sambuc         unsigned Opcode;
238f4a2713aSLionel Sambuc         if (F->getIntrinsicID() != Intrinsic::not_intrinsic) {
239f4a2713aSLionel Sambuc           switch (F->getIntrinsicID()) {
240f4a2713aSLionel Sambuc           default: continue;
241f4a2713aSLionel Sambuc 
242f4a2713aSLionel Sambuc // VisualStudio defines setjmp as _setjmp
243f4a2713aSLionel Sambuc #if defined(_MSC_VER) && defined(setjmp) && \
244f4a2713aSLionel Sambuc                        !defined(setjmp_undefined_for_msvc)
245f4a2713aSLionel Sambuc #  pragma push_macro("setjmp")
246f4a2713aSLionel Sambuc #  undef setjmp
247f4a2713aSLionel Sambuc #  define setjmp_undefined_for_msvc
248f4a2713aSLionel Sambuc #endif
249f4a2713aSLionel Sambuc 
250f4a2713aSLionel Sambuc           case Intrinsic::setjmp:
251f4a2713aSLionel Sambuc 
252f4a2713aSLionel Sambuc #if defined(_MSC_VER) && defined(setjmp_undefined_for_msvc)
253f4a2713aSLionel Sambuc  // let's return it to _setjmp state
254f4a2713aSLionel Sambuc #  pragma pop_macro("setjmp")
255f4a2713aSLionel Sambuc #  undef setjmp_undefined_for_msvc
256f4a2713aSLionel Sambuc #endif
257f4a2713aSLionel Sambuc 
258f4a2713aSLionel Sambuc           case Intrinsic::longjmp:
259f4a2713aSLionel Sambuc 
260f4a2713aSLionel Sambuc           // Exclude eh_sjlj_setjmp; we don't need to exclude eh_sjlj_longjmp
261f4a2713aSLionel Sambuc           // because, although it does clobber the counter register, the
262f4a2713aSLionel Sambuc           // control can't then return to inside the loop unless there is also
263f4a2713aSLionel Sambuc           // an eh_sjlj_setjmp.
264f4a2713aSLionel Sambuc           case Intrinsic::eh_sjlj_setjmp:
265f4a2713aSLionel Sambuc 
266f4a2713aSLionel Sambuc           case Intrinsic::memcpy:
267f4a2713aSLionel Sambuc           case Intrinsic::memmove:
268f4a2713aSLionel Sambuc           case Intrinsic::memset:
269f4a2713aSLionel Sambuc           case Intrinsic::powi:
270f4a2713aSLionel Sambuc           case Intrinsic::log:
271f4a2713aSLionel Sambuc           case Intrinsic::log2:
272f4a2713aSLionel Sambuc           case Intrinsic::log10:
273f4a2713aSLionel Sambuc           case Intrinsic::exp:
274f4a2713aSLionel Sambuc           case Intrinsic::exp2:
275f4a2713aSLionel Sambuc           case Intrinsic::pow:
276f4a2713aSLionel Sambuc           case Intrinsic::sin:
277f4a2713aSLionel Sambuc           case Intrinsic::cos:
278f4a2713aSLionel Sambuc             return true;
279f4a2713aSLionel Sambuc           case Intrinsic::copysign:
280f4a2713aSLionel Sambuc             if (CI->getArgOperand(0)->getType()->getScalarType()->
281f4a2713aSLionel Sambuc                 isPPC_FP128Ty())
282f4a2713aSLionel Sambuc               return true;
283f4a2713aSLionel Sambuc             else
284f4a2713aSLionel Sambuc               continue; // ISD::FCOPYSIGN is never a library call.
285f4a2713aSLionel Sambuc           case Intrinsic::sqrt:      Opcode = ISD::FSQRT;      break;
286f4a2713aSLionel Sambuc           case Intrinsic::floor:     Opcode = ISD::FFLOOR;     break;
287f4a2713aSLionel Sambuc           case Intrinsic::ceil:      Opcode = ISD::FCEIL;      break;
288f4a2713aSLionel Sambuc           case Intrinsic::trunc:     Opcode = ISD::FTRUNC;     break;
289f4a2713aSLionel Sambuc           case Intrinsic::rint:      Opcode = ISD::FRINT;      break;
290f4a2713aSLionel Sambuc           case Intrinsic::nearbyint: Opcode = ISD::FNEARBYINT; break;
291f4a2713aSLionel Sambuc           case Intrinsic::round:     Opcode = ISD::FROUND;     break;
292f4a2713aSLionel Sambuc           }
293f4a2713aSLionel Sambuc         }
294f4a2713aSLionel Sambuc 
295f4a2713aSLionel Sambuc         // PowerPC does not use [US]DIVREM or other library calls for
296f4a2713aSLionel Sambuc         // operations on regular types which are not otherwise library calls
297f4a2713aSLionel Sambuc         // (i.e. soft float or atomics). If adapting for targets that do,
298f4a2713aSLionel Sambuc         // additional care is required here.
299f4a2713aSLionel Sambuc 
300f4a2713aSLionel Sambuc         LibFunc::Func Func;
301f4a2713aSLionel Sambuc         if (!F->hasLocalLinkage() && F->hasName() && LibInfo &&
302f4a2713aSLionel Sambuc             LibInfo->getLibFunc(F->getName(), Func) &&
303f4a2713aSLionel Sambuc             LibInfo->hasOptimizedCodeGen(Func)) {
304f4a2713aSLionel Sambuc           // Non-read-only functions are never treated as intrinsics.
305f4a2713aSLionel Sambuc           if (!CI->onlyReadsMemory())
306f4a2713aSLionel Sambuc             return true;
307f4a2713aSLionel Sambuc 
308f4a2713aSLionel Sambuc           // Conversion happens only for FP calls.
309f4a2713aSLionel Sambuc           if (!CI->getArgOperand(0)->getType()->isFloatingPointTy())
310f4a2713aSLionel Sambuc             return true;
311f4a2713aSLionel Sambuc 
312f4a2713aSLionel Sambuc           switch (Func) {
313f4a2713aSLionel Sambuc           default: return true;
314f4a2713aSLionel Sambuc           case LibFunc::copysign:
315f4a2713aSLionel Sambuc           case LibFunc::copysignf:
316f4a2713aSLionel Sambuc             continue; // ISD::FCOPYSIGN is never a library call.
317f4a2713aSLionel Sambuc           case LibFunc::copysignl:
318f4a2713aSLionel Sambuc             return true;
319f4a2713aSLionel Sambuc           case LibFunc::fabs:
320f4a2713aSLionel Sambuc           case LibFunc::fabsf:
321f4a2713aSLionel Sambuc           case LibFunc::fabsl:
322f4a2713aSLionel Sambuc             continue; // ISD::FABS is never a library call.
323f4a2713aSLionel Sambuc           case LibFunc::sqrt:
324f4a2713aSLionel Sambuc           case LibFunc::sqrtf:
325f4a2713aSLionel Sambuc           case LibFunc::sqrtl:
326f4a2713aSLionel Sambuc             Opcode = ISD::FSQRT; break;
327f4a2713aSLionel Sambuc           case LibFunc::floor:
328f4a2713aSLionel Sambuc           case LibFunc::floorf:
329f4a2713aSLionel Sambuc           case LibFunc::floorl:
330f4a2713aSLionel Sambuc             Opcode = ISD::FFLOOR; break;
331f4a2713aSLionel Sambuc           case LibFunc::nearbyint:
332f4a2713aSLionel Sambuc           case LibFunc::nearbyintf:
333f4a2713aSLionel Sambuc           case LibFunc::nearbyintl:
334f4a2713aSLionel Sambuc             Opcode = ISD::FNEARBYINT; break;
335f4a2713aSLionel Sambuc           case LibFunc::ceil:
336f4a2713aSLionel Sambuc           case LibFunc::ceilf:
337f4a2713aSLionel Sambuc           case LibFunc::ceill:
338f4a2713aSLionel Sambuc             Opcode = ISD::FCEIL; break;
339f4a2713aSLionel Sambuc           case LibFunc::rint:
340f4a2713aSLionel Sambuc           case LibFunc::rintf:
341f4a2713aSLionel Sambuc           case LibFunc::rintl:
342f4a2713aSLionel Sambuc             Opcode = ISD::FRINT; break;
343f4a2713aSLionel Sambuc           case LibFunc::round:
344f4a2713aSLionel Sambuc           case LibFunc::roundf:
345f4a2713aSLionel Sambuc           case LibFunc::roundl:
346f4a2713aSLionel Sambuc             Opcode = ISD::FROUND; break;
347f4a2713aSLionel Sambuc           case LibFunc::trunc:
348f4a2713aSLionel Sambuc           case LibFunc::truncf:
349f4a2713aSLionel Sambuc           case LibFunc::truncl:
350f4a2713aSLionel Sambuc             Opcode = ISD::FTRUNC; break;
351f4a2713aSLionel Sambuc           }
352f4a2713aSLionel Sambuc 
353f4a2713aSLionel Sambuc           MVT VTy =
354f4a2713aSLionel Sambuc             TLI->getSimpleValueType(CI->getArgOperand(0)->getType(), true);
355f4a2713aSLionel Sambuc           if (VTy == MVT::Other)
356f4a2713aSLionel Sambuc             return true;
357f4a2713aSLionel Sambuc 
358f4a2713aSLionel Sambuc           if (TLI->isOperationLegalOrCustom(Opcode, VTy))
359f4a2713aSLionel Sambuc             continue;
360f4a2713aSLionel Sambuc           else if (VTy.isVector() &&
361f4a2713aSLionel Sambuc                    TLI->isOperationLegalOrCustom(Opcode, VTy.getScalarType()))
362f4a2713aSLionel Sambuc             continue;
363f4a2713aSLionel Sambuc 
364f4a2713aSLionel Sambuc           return true;
365f4a2713aSLionel Sambuc         }
366f4a2713aSLionel Sambuc       }
367f4a2713aSLionel Sambuc 
368f4a2713aSLionel Sambuc       return true;
369f4a2713aSLionel Sambuc     } else if (isa<BinaryOperator>(J) &&
370f4a2713aSLionel Sambuc                J->getType()->getScalarType()->isPPC_FP128Ty()) {
371f4a2713aSLionel Sambuc       // Most operations on ppc_f128 values become calls.
372f4a2713aSLionel Sambuc       return true;
373f4a2713aSLionel Sambuc     } else if (isa<UIToFPInst>(J) || isa<SIToFPInst>(J) ||
374f4a2713aSLionel Sambuc                isa<FPToUIInst>(J) || isa<FPToSIInst>(J)) {
375f4a2713aSLionel Sambuc       CastInst *CI = cast<CastInst>(J);
376f4a2713aSLionel Sambuc       if (CI->getSrcTy()->getScalarType()->isPPC_FP128Ty() ||
377f4a2713aSLionel Sambuc           CI->getDestTy()->getScalarType()->isPPC_FP128Ty() ||
378*0a6a1f1dSLionel Sambuc           isLargeIntegerTy(TT.isArch32Bit(), CI->getSrcTy()->getScalarType()) ||
379*0a6a1f1dSLionel Sambuc           isLargeIntegerTy(TT.isArch32Bit(), CI->getDestTy()->getScalarType()))
380f4a2713aSLionel Sambuc         return true;
381*0a6a1f1dSLionel Sambuc     } else if (isLargeIntegerTy(TT.isArch32Bit(),
382*0a6a1f1dSLionel Sambuc                                 J->getType()->getScalarType()) &&
383f4a2713aSLionel Sambuc                (J->getOpcode() == Instruction::UDiv ||
384f4a2713aSLionel Sambuc                 J->getOpcode() == Instruction::SDiv ||
385f4a2713aSLionel Sambuc                 J->getOpcode() == Instruction::URem ||
386f4a2713aSLionel Sambuc                 J->getOpcode() == Instruction::SRem)) {
387f4a2713aSLionel Sambuc       return true;
388*0a6a1f1dSLionel Sambuc     } else if (TT.isArch32Bit() &&
389*0a6a1f1dSLionel Sambuc                isLargeIntegerTy(false, J->getType()->getScalarType()) &&
390*0a6a1f1dSLionel Sambuc                (J->getOpcode() == Instruction::Shl ||
391*0a6a1f1dSLionel Sambuc                 J->getOpcode() == Instruction::AShr ||
392*0a6a1f1dSLionel Sambuc                 J->getOpcode() == Instruction::LShr)) {
393*0a6a1f1dSLionel Sambuc       // Only on PPC32, for 128-bit integers (specifically not 64-bit
394*0a6a1f1dSLionel Sambuc       // integers), these might be runtime calls.
395*0a6a1f1dSLionel Sambuc       return true;
396f4a2713aSLionel Sambuc     } else if (isa<IndirectBrInst>(J) || isa<InvokeInst>(J)) {
397f4a2713aSLionel Sambuc       // On PowerPC, indirect jumps use the counter register.
398f4a2713aSLionel Sambuc       return true;
399f4a2713aSLionel Sambuc     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(J)) {
400f4a2713aSLionel Sambuc       if (!TM)
401f4a2713aSLionel Sambuc         return true;
402*0a6a1f1dSLionel Sambuc       const TargetLowering *TLI = TM->getSubtargetImpl()->getTargetLowering();
403f4a2713aSLionel Sambuc 
404*0a6a1f1dSLionel Sambuc       if (SI->getNumCases() + 1 >= (unsigned)TLI->getMinimumJumpTableEntries())
405f4a2713aSLionel Sambuc         return true;
406f4a2713aSLionel Sambuc     }
407*0a6a1f1dSLionel Sambuc     for (Value *Operand : J->operands())
408*0a6a1f1dSLionel Sambuc       if (memAddrUsesCTR(TM, Operand))
409*0a6a1f1dSLionel Sambuc         return true;
410f4a2713aSLionel Sambuc   }
411f4a2713aSLionel Sambuc 
412f4a2713aSLionel Sambuc   return false;
413f4a2713aSLionel Sambuc }
414f4a2713aSLionel Sambuc 
convertToCTRLoop(Loop * L)415f4a2713aSLionel Sambuc bool PPCCTRLoops::convertToCTRLoop(Loop *L) {
416f4a2713aSLionel Sambuc   bool MadeChange = false;
417f4a2713aSLionel Sambuc 
418f4a2713aSLionel Sambuc   Triple TT = Triple(L->getHeader()->getParent()->getParent()->
419f4a2713aSLionel Sambuc                      getTargetTriple());
420f4a2713aSLionel Sambuc   if (!TT.isArch32Bit() && !TT.isArch64Bit())
421f4a2713aSLionel Sambuc     return MadeChange; // Unknown arch. type.
422f4a2713aSLionel Sambuc 
423f4a2713aSLionel Sambuc   // Process nested loops first.
424f4a2713aSLionel Sambuc   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
425f4a2713aSLionel Sambuc     MadeChange |= convertToCTRLoop(*I);
426f4a2713aSLionel Sambuc   }
427f4a2713aSLionel Sambuc 
428f4a2713aSLionel Sambuc   // If a nested loop has been converted, then we can't convert this loop.
429f4a2713aSLionel Sambuc   if (MadeChange)
430f4a2713aSLionel Sambuc     return MadeChange;
431f4a2713aSLionel Sambuc 
432f4a2713aSLionel Sambuc #ifndef NDEBUG
433f4a2713aSLionel Sambuc   // Stop trying after reaching the limit (if any).
434f4a2713aSLionel Sambuc   int Limit = CTRLoopLimit;
435f4a2713aSLionel Sambuc   if (Limit >= 0) {
436f4a2713aSLionel Sambuc     if (Counter >= CTRLoopLimit)
437f4a2713aSLionel Sambuc       return false;
438f4a2713aSLionel Sambuc     Counter++;
439f4a2713aSLionel Sambuc   }
440f4a2713aSLionel Sambuc #endif
441f4a2713aSLionel Sambuc 
442f4a2713aSLionel Sambuc   // We don't want to spill/restore the counter register, and so we don't
443f4a2713aSLionel Sambuc   // want to use the counter register if the loop contains calls.
444f4a2713aSLionel Sambuc   for (Loop::block_iterator I = L->block_begin(), IE = L->block_end();
445f4a2713aSLionel Sambuc        I != IE; ++I)
446f4a2713aSLionel Sambuc     if (mightUseCTR(TT, *I))
447f4a2713aSLionel Sambuc       return MadeChange;
448f4a2713aSLionel Sambuc 
449f4a2713aSLionel Sambuc   SmallVector<BasicBlock*, 4> ExitingBlocks;
450f4a2713aSLionel Sambuc   L->getExitingBlocks(ExitingBlocks);
451f4a2713aSLionel Sambuc 
452*0a6a1f1dSLionel Sambuc   BasicBlock *CountedExitBlock = nullptr;
453*0a6a1f1dSLionel Sambuc   const SCEV *ExitCount = nullptr;
454*0a6a1f1dSLionel Sambuc   BranchInst *CountedExitBranch = nullptr;
455f4a2713aSLionel Sambuc   for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
456f4a2713aSLionel Sambuc        IE = ExitingBlocks.end(); I != IE; ++I) {
457f4a2713aSLionel Sambuc     const SCEV *EC = SE->getExitCount(L, *I);
458f4a2713aSLionel Sambuc     DEBUG(dbgs() << "Exit Count for " << *L << " from block " <<
459f4a2713aSLionel Sambuc                     (*I)->getName() << ": " << *EC << "\n");
460f4a2713aSLionel Sambuc     if (isa<SCEVCouldNotCompute>(EC))
461f4a2713aSLionel Sambuc       continue;
462f4a2713aSLionel Sambuc     if (const SCEVConstant *ConstEC = dyn_cast<SCEVConstant>(EC)) {
463f4a2713aSLionel Sambuc       if (ConstEC->getValue()->isZero())
464f4a2713aSLionel Sambuc         continue;
465f4a2713aSLionel Sambuc     } else if (!SE->isLoopInvariant(EC, L))
466f4a2713aSLionel Sambuc       continue;
467f4a2713aSLionel Sambuc 
468f4a2713aSLionel Sambuc     if (SE->getTypeSizeInBits(EC->getType()) > (TT.isArch64Bit() ? 64 : 32))
469f4a2713aSLionel Sambuc       continue;
470f4a2713aSLionel Sambuc 
471f4a2713aSLionel Sambuc     // We now have a loop-invariant count of loop iterations (which is not the
472f4a2713aSLionel Sambuc     // constant zero) for which we know that this loop will not exit via this
473f4a2713aSLionel Sambuc     // exisiting block.
474f4a2713aSLionel Sambuc 
475f4a2713aSLionel Sambuc     // We need to make sure that this block will run on every loop iteration.
476f4a2713aSLionel Sambuc     // For this to be true, we must dominate all blocks with backedges. Such
477f4a2713aSLionel Sambuc     // blocks are in-loop predecessors to the header block.
478f4a2713aSLionel Sambuc     bool NotAlways = false;
479f4a2713aSLionel Sambuc     for (pred_iterator PI = pred_begin(L->getHeader()),
480f4a2713aSLionel Sambuc          PIE = pred_end(L->getHeader()); PI != PIE; ++PI) {
481f4a2713aSLionel Sambuc       if (!L->contains(*PI))
482f4a2713aSLionel Sambuc         continue;
483f4a2713aSLionel Sambuc 
484f4a2713aSLionel Sambuc       if (!DT->dominates(*I, *PI)) {
485f4a2713aSLionel Sambuc         NotAlways = true;
486f4a2713aSLionel Sambuc         break;
487f4a2713aSLionel Sambuc       }
488f4a2713aSLionel Sambuc     }
489f4a2713aSLionel Sambuc 
490f4a2713aSLionel Sambuc     if (NotAlways)
491f4a2713aSLionel Sambuc       continue;
492f4a2713aSLionel Sambuc 
493f4a2713aSLionel Sambuc     // Make sure this blocks ends with a conditional branch.
494f4a2713aSLionel Sambuc     Instruction *TI = (*I)->getTerminator();
495f4a2713aSLionel Sambuc     if (!TI)
496f4a2713aSLionel Sambuc       continue;
497f4a2713aSLionel Sambuc 
498f4a2713aSLionel Sambuc     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
499f4a2713aSLionel Sambuc       if (!BI->isConditional())
500f4a2713aSLionel Sambuc         continue;
501f4a2713aSLionel Sambuc 
502f4a2713aSLionel Sambuc       CountedExitBranch = BI;
503f4a2713aSLionel Sambuc     } else
504f4a2713aSLionel Sambuc       continue;
505f4a2713aSLionel Sambuc 
506f4a2713aSLionel Sambuc     // Note that this block may not be the loop latch block, even if the loop
507f4a2713aSLionel Sambuc     // has a latch block.
508f4a2713aSLionel Sambuc     CountedExitBlock = *I;
509f4a2713aSLionel Sambuc     ExitCount = EC;
510f4a2713aSLionel Sambuc     break;
511f4a2713aSLionel Sambuc   }
512f4a2713aSLionel Sambuc 
513f4a2713aSLionel Sambuc   if (!CountedExitBlock)
514f4a2713aSLionel Sambuc     return MadeChange;
515f4a2713aSLionel Sambuc 
516f4a2713aSLionel Sambuc   BasicBlock *Preheader = L->getLoopPreheader();
517f4a2713aSLionel Sambuc 
518f4a2713aSLionel Sambuc   // If we don't have a preheader, then insert one. If we already have a
519f4a2713aSLionel Sambuc   // preheader, then we can use it (except if the preheader contains a use of
520f4a2713aSLionel Sambuc   // the CTR register because some such uses might be reordered by the
521f4a2713aSLionel Sambuc   // selection DAG after the mtctr instruction).
522f4a2713aSLionel Sambuc   if (!Preheader || mightUseCTR(TT, Preheader))
523f4a2713aSLionel Sambuc     Preheader = InsertPreheaderForLoop(L, this);
524f4a2713aSLionel Sambuc   if (!Preheader)
525f4a2713aSLionel Sambuc     return MadeChange;
526f4a2713aSLionel Sambuc 
527f4a2713aSLionel Sambuc   DEBUG(dbgs() << "Preheader for exit count: " << Preheader->getName() << "\n");
528f4a2713aSLionel Sambuc 
529f4a2713aSLionel Sambuc   // Insert the count into the preheader and replace the condition used by the
530f4a2713aSLionel Sambuc   // selected branch.
531f4a2713aSLionel Sambuc   MadeChange = true;
532f4a2713aSLionel Sambuc 
533f4a2713aSLionel Sambuc   SCEVExpander SCEVE(*SE, "loopcnt");
534f4a2713aSLionel Sambuc   LLVMContext &C = SE->getContext();
535f4a2713aSLionel Sambuc   Type *CountType = TT.isArch64Bit() ? Type::getInt64Ty(C) :
536f4a2713aSLionel Sambuc                                        Type::getInt32Ty(C);
537f4a2713aSLionel Sambuc   if (!ExitCount->getType()->isPointerTy() &&
538f4a2713aSLionel Sambuc       ExitCount->getType() != CountType)
539f4a2713aSLionel Sambuc     ExitCount = SE->getZeroExtendExpr(ExitCount, CountType);
540f4a2713aSLionel Sambuc   ExitCount = SE->getAddExpr(ExitCount,
541f4a2713aSLionel Sambuc                              SE->getConstant(CountType, 1));
542f4a2713aSLionel Sambuc   Value *ECValue = SCEVE.expandCodeFor(ExitCount, CountType,
543f4a2713aSLionel Sambuc                                        Preheader->getTerminator());
544f4a2713aSLionel Sambuc 
545f4a2713aSLionel Sambuc   IRBuilder<> CountBuilder(Preheader->getTerminator());
546f4a2713aSLionel Sambuc   Module *M = Preheader->getParent()->getParent();
547f4a2713aSLionel Sambuc   Value *MTCTRFunc = Intrinsic::getDeclaration(M, Intrinsic::ppc_mtctr,
548f4a2713aSLionel Sambuc                                                CountType);
549f4a2713aSLionel Sambuc   CountBuilder.CreateCall(MTCTRFunc, ECValue);
550f4a2713aSLionel Sambuc 
551f4a2713aSLionel Sambuc   IRBuilder<> CondBuilder(CountedExitBranch);
552f4a2713aSLionel Sambuc   Value *DecFunc =
553f4a2713aSLionel Sambuc     Intrinsic::getDeclaration(M, Intrinsic::ppc_is_decremented_ctr_nonzero);
554f4a2713aSLionel Sambuc   Value *NewCond = CondBuilder.CreateCall(DecFunc);
555f4a2713aSLionel Sambuc   Value *OldCond = CountedExitBranch->getCondition();
556f4a2713aSLionel Sambuc   CountedExitBranch->setCondition(NewCond);
557f4a2713aSLionel Sambuc 
558f4a2713aSLionel Sambuc   // The false branch must exit the loop.
559f4a2713aSLionel Sambuc   if (!L->contains(CountedExitBranch->getSuccessor(0)))
560f4a2713aSLionel Sambuc     CountedExitBranch->swapSuccessors();
561f4a2713aSLionel Sambuc 
562f4a2713aSLionel Sambuc   // The old condition may be dead now, and may have even created a dead PHI
563f4a2713aSLionel Sambuc   // (the original induction variable).
564f4a2713aSLionel Sambuc   RecursivelyDeleteTriviallyDeadInstructions(OldCond);
565f4a2713aSLionel Sambuc   DeleteDeadPHIs(CountedExitBlock);
566f4a2713aSLionel Sambuc 
567f4a2713aSLionel Sambuc   ++NumCTRLoops;
568f4a2713aSLionel Sambuc   return MadeChange;
569f4a2713aSLionel Sambuc }
570f4a2713aSLionel Sambuc 
571f4a2713aSLionel Sambuc #ifndef NDEBUG
clobbersCTR(const MachineInstr * MI)572f4a2713aSLionel Sambuc static bool clobbersCTR(const MachineInstr *MI) {
573f4a2713aSLionel Sambuc   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
574f4a2713aSLionel Sambuc     const MachineOperand &MO = MI->getOperand(i);
575f4a2713aSLionel Sambuc     if (MO.isReg()) {
576f4a2713aSLionel Sambuc       if (MO.isDef() && (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8))
577f4a2713aSLionel Sambuc         return true;
578f4a2713aSLionel Sambuc     } else if (MO.isRegMask()) {
579f4a2713aSLionel Sambuc       if (MO.clobbersPhysReg(PPC::CTR) || MO.clobbersPhysReg(PPC::CTR8))
580f4a2713aSLionel Sambuc         return true;
581f4a2713aSLionel Sambuc     }
582f4a2713aSLionel Sambuc   }
583f4a2713aSLionel Sambuc 
584f4a2713aSLionel Sambuc   return false;
585f4a2713aSLionel Sambuc }
586f4a2713aSLionel Sambuc 
verifyCTRBranch(MachineBasicBlock * MBB,MachineBasicBlock::iterator I)587f4a2713aSLionel Sambuc static bool verifyCTRBranch(MachineBasicBlock *MBB,
588f4a2713aSLionel Sambuc                             MachineBasicBlock::iterator I) {
589f4a2713aSLionel Sambuc   MachineBasicBlock::iterator BI = I;
590f4a2713aSLionel Sambuc   SmallSet<MachineBasicBlock *, 16>   Visited;
591f4a2713aSLionel Sambuc   SmallVector<MachineBasicBlock *, 8> Preds;
592f4a2713aSLionel Sambuc   bool CheckPreds;
593f4a2713aSLionel Sambuc 
594f4a2713aSLionel Sambuc   if (I == MBB->begin()) {
595f4a2713aSLionel Sambuc     Visited.insert(MBB);
596f4a2713aSLionel Sambuc     goto queue_preds;
597f4a2713aSLionel Sambuc   } else
598f4a2713aSLionel Sambuc     --I;
599f4a2713aSLionel Sambuc 
600f4a2713aSLionel Sambuc check_block:
601f4a2713aSLionel Sambuc   Visited.insert(MBB);
602f4a2713aSLionel Sambuc   if (I == MBB->end())
603f4a2713aSLionel Sambuc     goto queue_preds;
604f4a2713aSLionel Sambuc 
605f4a2713aSLionel Sambuc   CheckPreds = true;
606f4a2713aSLionel Sambuc   for (MachineBasicBlock::iterator IE = MBB->begin();; --I) {
607f4a2713aSLionel Sambuc     unsigned Opc = I->getOpcode();
608f4a2713aSLionel Sambuc     if (Opc == PPC::MTCTRloop || Opc == PPC::MTCTR8loop) {
609f4a2713aSLionel Sambuc       CheckPreds = false;
610f4a2713aSLionel Sambuc       break;
611f4a2713aSLionel Sambuc     }
612f4a2713aSLionel Sambuc 
613f4a2713aSLionel Sambuc     if (I != BI && clobbersCTR(I)) {
614f4a2713aSLionel Sambuc       DEBUG(dbgs() << "BB#" << MBB->getNumber() << " (" <<
615f4a2713aSLionel Sambuc                       MBB->getFullName() << ") instruction " << *I <<
616f4a2713aSLionel Sambuc                       " clobbers CTR, invalidating " << "BB#" <<
617f4a2713aSLionel Sambuc                       BI->getParent()->getNumber() << " (" <<
618f4a2713aSLionel Sambuc                       BI->getParent()->getFullName() << ") instruction " <<
619f4a2713aSLionel Sambuc                       *BI << "\n");
620f4a2713aSLionel Sambuc       return false;
621f4a2713aSLionel Sambuc     }
622f4a2713aSLionel Sambuc 
623f4a2713aSLionel Sambuc     if (I == IE)
624f4a2713aSLionel Sambuc       break;
625f4a2713aSLionel Sambuc   }
626f4a2713aSLionel Sambuc 
627f4a2713aSLionel Sambuc   if (!CheckPreds && Preds.empty())
628f4a2713aSLionel Sambuc     return true;
629f4a2713aSLionel Sambuc 
630f4a2713aSLionel Sambuc   if (CheckPreds) {
631f4a2713aSLionel Sambuc queue_preds:
632f4a2713aSLionel Sambuc     if (MachineFunction::iterator(MBB) == MBB->getParent()->begin()) {
633f4a2713aSLionel Sambuc       DEBUG(dbgs() << "Unable to find a MTCTR instruction for BB#" <<
634f4a2713aSLionel Sambuc                       BI->getParent()->getNumber() << " (" <<
635f4a2713aSLionel Sambuc                       BI->getParent()->getFullName() << ") instruction " <<
636f4a2713aSLionel Sambuc                       *BI << "\n");
637f4a2713aSLionel Sambuc       return false;
638f4a2713aSLionel Sambuc     }
639f4a2713aSLionel Sambuc 
640f4a2713aSLionel Sambuc     for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
641f4a2713aSLionel Sambuc          PIE = MBB->pred_end(); PI != PIE; ++PI)
642f4a2713aSLionel Sambuc       Preds.push_back(*PI);
643f4a2713aSLionel Sambuc   }
644f4a2713aSLionel Sambuc 
645f4a2713aSLionel Sambuc   do {
646f4a2713aSLionel Sambuc     MBB = Preds.pop_back_val();
647f4a2713aSLionel Sambuc     if (!Visited.count(MBB)) {
648f4a2713aSLionel Sambuc       I = MBB->getLastNonDebugInstr();
649f4a2713aSLionel Sambuc       goto check_block;
650f4a2713aSLionel Sambuc     }
651f4a2713aSLionel Sambuc   } while (!Preds.empty());
652f4a2713aSLionel Sambuc 
653f4a2713aSLionel Sambuc   return true;
654f4a2713aSLionel Sambuc }
655f4a2713aSLionel Sambuc 
runOnMachineFunction(MachineFunction & MF)656f4a2713aSLionel Sambuc bool PPCCTRLoopsVerify::runOnMachineFunction(MachineFunction &MF) {
657f4a2713aSLionel Sambuc   MDT = &getAnalysis<MachineDominatorTree>();
658f4a2713aSLionel Sambuc 
659f4a2713aSLionel Sambuc   // Verify that all bdnz/bdz instructions are dominated by a loop mtctr before
660f4a2713aSLionel Sambuc   // any other instructions that might clobber the ctr register.
661f4a2713aSLionel Sambuc   for (MachineFunction::iterator I = MF.begin(), IE = MF.end();
662f4a2713aSLionel Sambuc        I != IE; ++I) {
663f4a2713aSLionel Sambuc     MachineBasicBlock *MBB = I;
664f4a2713aSLionel Sambuc     if (!MDT->isReachableFromEntry(MBB))
665f4a2713aSLionel Sambuc       continue;
666f4a2713aSLionel Sambuc 
667f4a2713aSLionel Sambuc     for (MachineBasicBlock::iterator MII = MBB->getFirstTerminator(),
668f4a2713aSLionel Sambuc       MIIE = MBB->end(); MII != MIIE; ++MII) {
669f4a2713aSLionel Sambuc       unsigned Opc = MII->getOpcode();
670f4a2713aSLionel Sambuc       if (Opc == PPC::BDNZ8 || Opc == PPC::BDNZ ||
671f4a2713aSLionel Sambuc           Opc == PPC::BDZ8  || Opc == PPC::BDZ)
672f4a2713aSLionel Sambuc         if (!verifyCTRBranch(MBB, MII))
673f4a2713aSLionel Sambuc           llvm_unreachable("Invalid PPC CTR loop!");
674f4a2713aSLionel Sambuc     }
675f4a2713aSLionel Sambuc   }
676f4a2713aSLionel Sambuc 
677f4a2713aSLionel Sambuc   return false;
678f4a2713aSLionel Sambuc }
679f4a2713aSLionel Sambuc #endif // NDEBUG
680f4a2713aSLionel Sambuc 
681