1 //===-- PPCCTRLoops.cpp - Identify and generate CTR loops -----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass identifies loops where we can generate the PPC branch instructions
10 // that decrement and test the count register (CTR) (bdnz and friends).
11 //
12 // The pattern that defines the induction variable can changed depending on
13 // prior optimizations.  For example, the IndVarSimplify phase run by 'opt'
14 // normalizes induction variables, and the Loop Strength Reduction pass
15 // run by 'llc' may also make changes to the induction variable.
16 //
17 // Criteria for CTR loops:
18 //  - Countable loops (w/ ind. var for a trip count)
19 //  - Try inner-most loops first
20 //  - No nested CTR loops.
21 //  - No function calls in loops.
22 //
23 //===----------------------------------------------------------------------===//
24 
25 #include "PPC.h"
26 #include "PPCSubtarget.h"
27 #include "PPCTargetMachine.h"
28 #include "PPCTargetTransformInfo.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/Analysis/AssumptionCache.h"
32 #include "llvm/Analysis/CFG.h"
33 #include "llvm/Analysis/CodeMetrics.h"
34 #include "llvm/Analysis/LoopInfo.h"
35 #include "llvm/Analysis/LoopIterator.h"
36 #include "llvm/Analysis/TargetLibraryInfo.h"
37 #include "llvm/Analysis/TargetTransformInfo.h"
38 #include "llvm/CodeGen/TargetPassConfig.h"
39 #include "llvm/CodeGen/TargetSchedule.h"
40 #include "llvm/IR/Constants.h"
41 #include "llvm/IR/DerivedTypes.h"
42 #include "llvm/IR/Dominators.h"
43 #include "llvm/IR/InlineAsm.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/IntrinsicInst.h"
46 #include "llvm/IR/Module.h"
47 #include "llvm/IR/ValueHandle.h"
48 #include "llvm/InitializePasses.h"
49 #include "llvm/PassSupport.h"
50 #include "llvm/Support/CommandLine.h"
51 #include "llvm/Support/Debug.h"
52 #include "llvm/Support/raw_ostream.h"
53 #include "llvm/Transforms/Scalar.h"
54 #include "llvm/Transforms/Utils.h"
55 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
56 #include "llvm/Transforms/Utils/Local.h"
57 #include "llvm/Transforms/Utils/LoopUtils.h"
58 
59 #ifndef NDEBUG
60 #include "llvm/CodeGen/MachineDominators.h"
61 #include "llvm/CodeGen/MachineFunction.h"
62 #include "llvm/CodeGen/MachineFunctionPass.h"
63 #include "llvm/CodeGen/MachineRegisterInfo.h"
64 #endif
65 
66 using namespace llvm;
67 
68 #define DEBUG_TYPE "ctrloops"
69 
70 #ifndef NDEBUG
71 static cl::opt<int> CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1));
72 #endif
73 
74 namespace {
75 
76 #ifndef NDEBUG
77   struct PPCCTRLoopsVerify : public MachineFunctionPass {
78   public:
79     static char ID;
80 
81     PPCCTRLoopsVerify() : MachineFunctionPass(ID) {
82       initializePPCCTRLoopsVerifyPass(*PassRegistry::getPassRegistry());
83     }
84 
85     void getAnalysisUsage(AnalysisUsage &AU) const override {
86       AU.addRequired<MachineDominatorTree>();
87       MachineFunctionPass::getAnalysisUsage(AU);
88     }
89 
90     bool runOnMachineFunction(MachineFunction &MF) override;
91 
92   private:
93     MachineDominatorTree *MDT;
94   };
95 
96   char PPCCTRLoopsVerify::ID = 0;
97 #endif // NDEBUG
98 } // end anonymous namespace
99 
100 #ifndef NDEBUG
101 INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
102                       "PowerPC CTR Loops Verify", false, false)
103 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
104 INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
105                     "PowerPC CTR Loops Verify", false, false)
106 
107 FunctionPass *llvm::createPPCCTRLoopsVerify() {
108   return new PPCCTRLoopsVerify();
109 }
110 #endif // NDEBUG
111 
112 #ifndef NDEBUG
113 static bool clobbersCTR(const MachineInstr &MI) {
114   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
115     const MachineOperand &MO = MI.getOperand(i);
116     if (MO.isReg()) {
117       if (MO.isDef() && (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8))
118         return true;
119     } else if (MO.isRegMask()) {
120       if (MO.clobbersPhysReg(PPC::CTR) || MO.clobbersPhysReg(PPC::CTR8))
121         return true;
122     }
123   }
124 
125   return false;
126 }
127 
128 static bool verifyCTRBranch(MachineBasicBlock *MBB,
129                             MachineBasicBlock::iterator I) {
130   MachineBasicBlock::iterator BI = I;
131   SmallSet<MachineBasicBlock *, 16>   Visited;
132   SmallVector<MachineBasicBlock *, 8> Preds;
133   bool CheckPreds;
134 
135   if (I == MBB->begin()) {
136     Visited.insert(MBB);
137     goto queue_preds;
138   } else
139     --I;
140 
141 check_block:
142   Visited.insert(MBB);
143   if (I == MBB->end())
144     goto queue_preds;
145 
146   CheckPreds = true;
147   for (MachineBasicBlock::iterator IE = MBB->begin();; --I) {
148     unsigned Opc = I->getOpcode();
149     if (Opc == PPC::MTCTRloop || Opc == PPC::MTCTR8loop) {
150       CheckPreds = false;
151       break;
152     }
153 
154     if (I != BI && clobbersCTR(*I)) {
155       LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " (" << MBB->getFullName()
156                         << ") instruction " << *I
157                         << " clobbers CTR, invalidating "
158                         << printMBBReference(*BI->getParent()) << " ("
159                         << BI->getParent()->getFullName() << ") instruction "
160                         << *BI << "\n");
161       return false;
162     }
163 
164     if (I == IE)
165       break;
166   }
167 
168   if (!CheckPreds && Preds.empty())
169     return true;
170 
171   if (CheckPreds) {
172 queue_preds:
173     if (MachineFunction::iterator(MBB) == MBB->getParent()->begin()) {
174       LLVM_DEBUG(dbgs() << "Unable to find a MTCTR instruction for "
175                         << printMBBReference(*BI->getParent()) << " ("
176                         << BI->getParent()->getFullName() << ") instruction "
177                         << *BI << "\n");
178       return false;
179     }
180 
181     for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
182          PIE = MBB->pred_end(); PI != PIE; ++PI)
183       Preds.push_back(*PI);
184   }
185 
186   do {
187     MBB = Preds.pop_back_val();
188     if (!Visited.count(MBB)) {
189       I = MBB->getLastNonDebugInstr();
190       goto check_block;
191     }
192   } while (!Preds.empty());
193 
194   return true;
195 }
196 
197 bool PPCCTRLoopsVerify::runOnMachineFunction(MachineFunction &MF) {
198   MDT = &getAnalysis<MachineDominatorTree>();
199 
200   // Verify that all bdnz/bdz instructions are dominated by a loop mtctr before
201   // any other instructions that might clobber the ctr register.
202   for (MachineFunction::iterator I = MF.begin(), IE = MF.end();
203        I != IE; ++I) {
204     MachineBasicBlock *MBB = &*I;
205     if (!MDT->isReachableFromEntry(MBB))
206       continue;
207 
208     for (MachineBasicBlock::iterator MII = MBB->getFirstTerminator(),
209       MIIE = MBB->end(); MII != MIIE; ++MII) {
210       unsigned Opc = MII->getOpcode();
211       if (Opc == PPC::BDNZ8 || Opc == PPC::BDNZ ||
212           Opc == PPC::BDZ8  || Opc == PPC::BDZ)
213         if (!verifyCTRBranch(MBB, MII))
214           llvm_unreachable("Invalid PPC CTR loop!");
215     }
216   }
217 
218   return false;
219 }
220 #endif // NDEBUG
221