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