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 // This pass is based on the HexagonHardwareLoops pass.
13 //
14 // The pattern that defines the induction variable can changed depending on
15 // prior optimizations. For example, the IndVarSimplify phase run by 'opt'
16 // normalizes induction variables, and the Loop Strength Reduction pass
17 // run by 'llc' may also make changes to the induction variable.
18 // The pattern detected by this phase is due to running Strength Reduction.
19 //
20 // Criteria for CTR loops:
21 // - Countable loops (w/ ind. var for a trip count)
22 // - Assumes loops are normalized by IndVarSimplify
23 // - Try inner-most loops first
24 // - No nested CTR loops.
25 // - No function calls in loops.
26 //
27 // Note: As with unconverted loops, PPCBranchSelector must be run after this
28 // pass in order to convert long-displacement jumps into jump pairs.
29 //
30 //===----------------------------------------------------------------------===//
31
32 #define DEBUG_TYPE "ctrloops"
33 #include "PPC.h"
34 #include "MCTargetDesc/PPCPredicates.h"
35 #include "PPCTargetMachine.h"
36 #include "llvm/ADT/DenseMap.h"
37 #include "llvm/ADT/Statistic.h"
38 #include "llvm/CodeGen/MachineDominators.h"
39 #include "llvm/CodeGen/MachineFunction.h"
40 #include "llvm/CodeGen/MachineFunctionPass.h"
41 #include "llvm/CodeGen/MachineInstrBuilder.h"
42 #include "llvm/CodeGen/MachineLoopInfo.h"
43 #include "llvm/CodeGen/MachineRegisterInfo.h"
44 #include "llvm/CodeGen/Passes.h"
45 #include "llvm/CodeGen/RegisterScavenging.h"
46 #include "llvm/IR/Constants.h"
47 #include "llvm/PassSupport.h"
48 #include "llvm/Support/Debug.h"
49 #include "llvm/Support/raw_ostream.h"
50 #include "llvm/Target/TargetInstrInfo.h"
51 #include <algorithm>
52
53 using namespace llvm;
54
55 STATISTIC(NumCTRLoops, "Number of loops converted to CTR loops");
56
57 namespace llvm {
58 void initializePPCCTRLoopsPass(PassRegistry&);
59 }
60
61 namespace {
62 class CountValue;
63 struct PPCCTRLoops : public MachineFunctionPass {
64 MachineLoopInfo *MLI;
65 MachineRegisterInfo *MRI;
66 const TargetInstrInfo *TII;
67
68 public:
69 static char ID; // Pass identification, replacement for typeid
70
PPCCTRLoops__anon9f6c02960111::PPCCTRLoops71 PPCCTRLoops() : MachineFunctionPass(ID) {
72 initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry());
73 }
74
75 virtual bool runOnMachineFunction(MachineFunction &MF);
76
getPassName__anon9f6c02960111::PPCCTRLoops77 const char *getPassName() const { return "PPC CTR Loops"; }
78
getAnalysisUsage__anon9f6c02960111::PPCCTRLoops79 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
80 AU.setPreservesCFG();
81 AU.addRequired<MachineDominatorTree>();
82 AU.addPreserved<MachineDominatorTree>();
83 AU.addRequired<MachineLoopInfo>();
84 AU.addPreserved<MachineLoopInfo>();
85 MachineFunctionPass::getAnalysisUsage(AU);
86 }
87
88 private:
89 /// getCanonicalInductionVariable - Check to see if the loop has a canonical
90 /// induction variable.
91 /// Should be defined in MachineLoop. Based upon version in class Loop.
92 void getCanonicalInductionVariable(MachineLoop *L,
93 SmallVector<MachineInstr *, 4> &IVars,
94 SmallVector<MachineInstr *, 4> &IOps) const;
95
96 /// getTripCount - Return a loop-invariant LLVM register indicating the
97 /// number of times the loop will be executed. If the trip-count cannot
98 /// be determined, this return null.
99 CountValue *getTripCount(MachineLoop *L,
100 SmallVector<MachineInstr *, 2> &OldInsts) const;
101
102 /// isInductionOperation - Return true if the instruction matches the
103 /// pattern for an opertion that defines an induction variable.
104 bool isInductionOperation(const MachineInstr *MI, unsigned IVReg) const;
105
106 /// isInvalidOperation - Return true if the instruction is not valid within
107 /// a CTR loop.
108 bool isInvalidLoopOperation(const MachineInstr *MI) const;
109
110 /// containsInavlidInstruction - Return true if the loop contains an
111 /// instruction that inhibits using the CTR loop.
112 bool containsInvalidInstruction(MachineLoop *L) const;
113
114 /// converToCTRLoop - Given a loop, check if we can convert it to a
115 /// CTR loop. If so, then perform the conversion and return true.
116 bool convertToCTRLoop(MachineLoop *L);
117
118 /// isDead - Return true if the instruction is now dead.
119 bool isDead(const MachineInstr *MI,
120 SmallVector<MachineInstr *, 1> &DeadPhis) const;
121
122 /// removeIfDead - Remove the instruction if it is now dead.
123 void removeIfDead(MachineInstr *MI);
124 };
125
126 char PPCCTRLoops::ID = 0;
127
128
129 // CountValue class - Abstraction for a trip count of a loop. A
130 // smaller vesrsion of the MachineOperand class without the concerns
131 // of changing the operand representation.
132 class CountValue {
133 public:
134 enum CountValueType {
135 CV_Register,
136 CV_Immediate
137 };
138 private:
139 CountValueType Kind;
140 union Values {
141 unsigned RegNum;
142 int64_t ImmVal;
Values(unsigned r)143 Values(unsigned r) : RegNum(r) {}
Values(int64_t i)144 Values(int64_t i) : ImmVal(i) {}
145 } Contents;
146 bool isNegative;
147
148 public:
CountValue(unsigned r,bool neg)149 CountValue(unsigned r, bool neg) : Kind(CV_Register), Contents(r),
150 isNegative(neg) {}
CountValue(int64_t i)151 explicit CountValue(int64_t i) : Kind(CV_Immediate), Contents(i),
152 isNegative(i < 0) {}
getType() const153 CountValueType getType() const { return Kind; }
isReg() const154 bool isReg() const { return Kind == CV_Register; }
isImm() const155 bool isImm() const { return Kind == CV_Immediate; }
isNeg() const156 bool isNeg() const { return isNegative; }
157
getReg() const158 unsigned getReg() const {
159 assert(isReg() && "Wrong CountValue accessor");
160 return Contents.RegNum;
161 }
setReg(unsigned Val)162 void setReg(unsigned Val) {
163 Contents.RegNum = Val;
164 }
getImm() const165 int64_t getImm() const {
166 assert(isImm() && "Wrong CountValue accessor");
167 if (isNegative) {
168 return -Contents.ImmVal;
169 }
170 return Contents.ImmVal;
171 }
setImm(int64_t Val)172 void setImm(int64_t Val) {
173 Contents.ImmVal = Val;
174 }
175
print(raw_ostream & OS,const TargetMachine * TM=0) const176 void print(raw_ostream &OS, const TargetMachine *TM = 0) const {
177 if (isReg()) { OS << PrintReg(getReg()); }
178 if (isImm()) { OS << getImm(); }
179 }
180 };
181 } // end anonymous namespace
182
183 INITIALIZE_PASS_BEGIN(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops",
184 false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)185 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
186 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
187 INITIALIZE_PASS_END(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops",
188 false, false)
189
190 /// isCompareEquals - Returns true if the instruction is a compare equals
191 /// instruction with an immediate operand.
192 static bool isCompareEqualsImm(const MachineInstr *MI, bool &SignedCmp,
193 bool &Int64Cmp) {
194 if (MI->getOpcode() == PPC::CMPWI) {
195 SignedCmp = true;
196 Int64Cmp = false;
197 return true;
198 } else if (MI->getOpcode() == PPC::CMPDI) {
199 SignedCmp = true;
200 Int64Cmp = true;
201 return true;
202 } else if (MI->getOpcode() == PPC::CMPLWI) {
203 SignedCmp = false;
204 Int64Cmp = false;
205 return true;
206 } else if (MI->getOpcode() == PPC::CMPLDI) {
207 SignedCmp = false;
208 Int64Cmp = true;
209 return true;
210 }
211
212 return false;
213 }
214
215
216 /// createPPCCTRLoops - Factory for creating
217 /// the CTR loop phase.
createPPCCTRLoops()218 FunctionPass *llvm::createPPCCTRLoops() {
219 return new PPCCTRLoops();
220 }
221
222
runOnMachineFunction(MachineFunction & MF)223 bool PPCCTRLoops::runOnMachineFunction(MachineFunction &MF) {
224 DEBUG(dbgs() << "********* PPC CTR Loops *********\n");
225
226 bool Changed = false;
227
228 // get the loop information
229 MLI = &getAnalysis<MachineLoopInfo>();
230 // get the register information
231 MRI = &MF.getRegInfo();
232 // the target specific instructio info.
233 TII = MF.getTarget().getInstrInfo();
234
235 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
236 I != E; ++I) {
237 MachineLoop *L = *I;
238 if (!L->getParentLoop()) {
239 Changed |= convertToCTRLoop(L);
240 }
241 }
242
243 return Changed;
244 }
245
246 /// getCanonicalInductionVariable - Check to see if the loop has a canonical
247 /// induction variable. We check for a simple recurrence pattern - an
248 /// integer recurrence that decrements by one each time through the loop and
249 /// ends at zero. If so, return the phi node that corresponds to it.
250 ///
251 /// Based upon the similar code in LoopInfo except this code is specific to
252 /// the machine.
253 /// This method assumes that the IndVarSimplify pass has been run by 'opt'.
254 ///
255 void
getCanonicalInductionVariable(MachineLoop * L,SmallVector<MachineInstr *,4> & IVars,SmallVector<MachineInstr *,4> & IOps) const256 PPCCTRLoops::getCanonicalInductionVariable(MachineLoop *L,
257 SmallVector<MachineInstr *, 4> &IVars,
258 SmallVector<MachineInstr *, 4> &IOps) const {
259 MachineBasicBlock *TopMBB = L->getTopBlock();
260 MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
261 assert(PI != TopMBB->pred_end() &&
262 "Loop must have more than one incoming edge!");
263 MachineBasicBlock *Backedge = *PI++;
264 if (PI == TopMBB->pred_end()) return; // dead loop
265 MachineBasicBlock *Incoming = *PI++;
266 if (PI != TopMBB->pred_end()) return; // multiple backedges?
267
268 // make sure there is one incoming and one backedge and determine which
269 // is which.
270 if (L->contains(Incoming)) {
271 if (L->contains(Backedge))
272 return;
273 std::swap(Incoming, Backedge);
274 } else if (!L->contains(Backedge))
275 return;
276
277 // Loop over all of the PHI nodes, looking for a canonical induction variable:
278 // - The PHI node is "reg1 = PHI reg2, BB1, reg3, BB2".
279 // - The recurrence comes from the backedge.
280 // - the definition is an induction operatio.n
281 for (MachineBasicBlock::iterator I = TopMBB->begin(), E = TopMBB->end();
282 I != E && I->isPHI(); ++I) {
283 MachineInstr *MPhi = &*I;
284 unsigned DefReg = MPhi->getOperand(0).getReg();
285 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
286 // Check each operand for the value from the backedge.
287 MachineBasicBlock *MBB = MPhi->getOperand(i+1).getMBB();
288 if (L->contains(MBB)) { // operands comes from the backedge
289 // Check if the definition is an induction operation.
290 MachineInstr *DI = MRI->getVRegDef(MPhi->getOperand(i).getReg());
291 if (isInductionOperation(DI, DefReg)) {
292 IOps.push_back(DI);
293 IVars.push_back(MPhi);
294 }
295 }
296 }
297 }
298 return;
299 }
300
301 /// getTripCount - Return a loop-invariant LLVM value indicating the
302 /// number of times the loop will be executed. The trip count can
303 /// be either a register or a constant value. If the trip-count
304 /// cannot be determined, this returns null.
305 ///
306 /// We find the trip count from the phi instruction that defines the
307 /// induction variable. We follow the links to the CMP instruction
308 /// to get the trip count.
309 ///
310 /// Based upon getTripCount in LoopInfo.
311 ///
getTripCount(MachineLoop * L,SmallVector<MachineInstr *,2> & OldInsts) const312 CountValue *PPCCTRLoops::getTripCount(MachineLoop *L,
313 SmallVector<MachineInstr *, 2> &OldInsts) const {
314 MachineBasicBlock *LastMBB = L->getExitingBlock();
315 // Don't generate a CTR loop if the loop has more than one exit.
316 if (LastMBB == 0)
317 return 0;
318
319 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
320 if (LastI->getOpcode() != PPC::BCC)
321 return 0;
322
323 // We need to make sure that this compare is defining the condition
324 // register actually used by the terminating branch.
325
326 unsigned PredReg = LastI->getOperand(1).getReg();
327 DEBUG(dbgs() << "Examining loop with first terminator: " << *LastI);
328
329 unsigned PredCond = LastI->getOperand(0).getImm();
330 if (PredCond != PPC::PRED_EQ && PredCond != PPC::PRED_NE)
331 return 0;
332
333 // Check that the loop has a induction variable.
334 SmallVector<MachineInstr *, 4> IVars, IOps;
335 getCanonicalInductionVariable(L, IVars, IOps);
336 for (unsigned i = 0; i < IVars.size(); ++i) {
337 MachineInstr *IOp = IOps[i];
338 MachineInstr *IV_Inst = IVars[i];
339
340 // Canonical loops will end with a 'cmpwi/cmpdi cr, IV, Imm',
341 // if Imm is 0, get the count from the PHI opnd
342 // if Imm is -M, than M is the count
343 // Otherwise, Imm is the count
344 MachineOperand *IV_Opnd;
345 const MachineOperand *InitialValue;
346 if (!L->contains(IV_Inst->getOperand(2).getMBB())) {
347 InitialValue = &IV_Inst->getOperand(1);
348 IV_Opnd = &IV_Inst->getOperand(3);
349 } else {
350 InitialValue = &IV_Inst->getOperand(3);
351 IV_Opnd = &IV_Inst->getOperand(1);
352 }
353
354 DEBUG(dbgs() << "Considering:\n");
355 DEBUG(dbgs() << " induction operation: " << *IOp);
356 DEBUG(dbgs() << " induction variable: " << *IV_Inst);
357 DEBUG(dbgs() << " initial value: " << *InitialValue << "\n");
358
359 // Look for the cmp instruction to determine if we
360 // can get a useful trip count. The trip count can
361 // be either a register or an immediate. The location
362 // of the value depends upon the type (reg or imm).
363 for (MachineRegisterInfo::reg_iterator
364 RI = MRI->reg_begin(IV_Opnd->getReg()), RE = MRI->reg_end();
365 RI != RE; ++RI) {
366 IV_Opnd = &RI.getOperand();
367 bool SignedCmp, Int64Cmp;
368 MachineInstr *MI = IV_Opnd->getParent();
369 if (L->contains(MI) && isCompareEqualsImm(MI, SignedCmp, Int64Cmp) &&
370 MI->getOperand(0).getReg() == PredReg) {
371
372 OldInsts.push_back(MI);
373 OldInsts.push_back(IOp);
374
375 DEBUG(dbgs() << " compare: " << *MI);
376
377 const MachineOperand &MO = MI->getOperand(2);
378 assert(MO.isImm() && "IV Cmp Operand should be an immediate");
379
380 int64_t ImmVal;
381 if (SignedCmp)
382 ImmVal = (short) MO.getImm();
383 else
384 ImmVal = MO.getImm();
385
386 const MachineInstr *IV_DefInstr = MRI->getVRegDef(IV_Opnd->getReg());
387 assert(L->contains(IV_DefInstr->getParent()) &&
388 "IV definition should occurs in loop");
389 int64_t iv_value = (short) IV_DefInstr->getOperand(2).getImm();
390
391 assert(InitialValue->isReg() && "Expecting register for init value");
392 unsigned InitialValueReg = InitialValue->getReg();
393
394 MachineInstr *DefInstr = MRI->getVRegDef(InitialValueReg);
395
396 // Here we need to look for an immediate load (an li or lis/ori pair).
397 if (DefInstr && (DefInstr->getOpcode() == PPC::ORI8 ||
398 DefInstr->getOpcode() == PPC::ORI)) {
399 int64_t start = (short) DefInstr->getOperand(2).getImm();
400 MachineInstr *DefInstr2 =
401 MRI->getVRegDef(DefInstr->getOperand(1).getReg());
402 if (DefInstr2 && (DefInstr2->getOpcode() == PPC::LIS8 ||
403 DefInstr2->getOpcode() == PPC::LIS)) {
404 DEBUG(dbgs() << " initial constant: " << *DefInstr);
405 DEBUG(dbgs() << " initial constant: " << *DefInstr2);
406
407 start |= int64_t(short(DefInstr2->getOperand(1).getImm())) << 16;
408
409 int64_t count = ImmVal - start;
410 if ((count % iv_value) != 0) {
411 return 0;
412 }
413
414 OldInsts.push_back(DefInstr);
415 OldInsts.push_back(DefInstr2);
416
417 // count/iv_value, the trip count, should be positive here. If it
418 // is negative, that indicates that the counter will wrap.
419 if (Int64Cmp)
420 return new CountValue(count/iv_value);
421 else
422 return new CountValue(uint32_t(count/iv_value));
423 }
424 } else if (DefInstr && (DefInstr->getOpcode() == PPC::LI8 ||
425 DefInstr->getOpcode() == PPC::LI)) {
426 DEBUG(dbgs() << " initial constant: " << *DefInstr);
427
428 int64_t count = ImmVal -
429 int64_t(short(DefInstr->getOperand(1).getImm()));
430 if ((count % iv_value) != 0) {
431 return 0;
432 }
433
434 OldInsts.push_back(DefInstr);
435
436 if (Int64Cmp)
437 return new CountValue(count/iv_value);
438 else
439 return new CountValue(uint32_t(count/iv_value));
440 } else if (iv_value == 1 || iv_value == -1) {
441 // We can't determine a constant starting value.
442 if (ImmVal == 0) {
443 return new CountValue(InitialValueReg, iv_value > 0);
444 }
445 // FIXME: handle non-zero end value.
446 }
447 // FIXME: handle non-unit increments (we might not want to introduce
448 // division but we can handle some 2^n cases with shifts).
449
450 }
451 }
452 }
453 return 0;
454 }
455
456 /// isInductionOperation - return true if the operation is matches the
457 /// pattern that defines an induction variable:
458 /// addi iv, c
459 ///
460 bool
isInductionOperation(const MachineInstr * MI,unsigned IVReg) const461 PPCCTRLoops::isInductionOperation(const MachineInstr *MI,
462 unsigned IVReg) const {
463 return ((MI->getOpcode() == PPC::ADDI || MI->getOpcode() == PPC::ADDI8) &&
464 MI->getOperand(1).isReg() && // could be a frame index instead
465 MI->getOperand(1).getReg() == IVReg);
466 }
467
468 /// isInvalidOperation - Return true if the operation is invalid within
469 /// CTR loop.
470 bool
isInvalidLoopOperation(const MachineInstr * MI) const471 PPCCTRLoops::isInvalidLoopOperation(const MachineInstr *MI) const {
472
473 // call is not allowed because the callee may use a CTR loop
474 if (MI->getDesc().isCall()) {
475 return true;
476 }
477 // check if the instruction defines a CTR loop register
478 // (this will also catch nested CTR loops)
479 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
480 const MachineOperand &MO = MI->getOperand(i);
481 if (MO.isReg() && MO.isDef() &&
482 (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) {
483 return true;
484 }
485 }
486 return false;
487 }
488
489 /// containsInvalidInstruction - Return true if the loop contains
490 /// an instruction that inhibits the use of the CTR loop function.
491 ///
containsInvalidInstruction(MachineLoop * L) const492 bool PPCCTRLoops::containsInvalidInstruction(MachineLoop *L) const {
493 const std::vector<MachineBasicBlock*> Blocks = L->getBlocks();
494 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
495 MachineBasicBlock *MBB = Blocks[i];
496 for (MachineBasicBlock::iterator
497 MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
498 const MachineInstr *MI = &*MII;
499 if (isInvalidLoopOperation(MI)) {
500 return true;
501 }
502 }
503 }
504 return false;
505 }
506
507 /// isDead returns true if the instruction is dead
508 /// (this was essentially copied from DeadMachineInstructionElim::isDead, but
509 /// with special cases for inline asm, physical registers and instructions with
510 /// side effects removed)
isDead(const MachineInstr * MI,SmallVector<MachineInstr *,1> & DeadPhis) const511 bool PPCCTRLoops::isDead(const MachineInstr *MI,
512 SmallVector<MachineInstr *, 1> &DeadPhis) const {
513 // Examine each operand.
514 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
515 const MachineOperand &MO = MI->getOperand(i);
516 if (MO.isReg() && MO.isDef()) {
517 unsigned Reg = MO.getReg();
518 if (!MRI->use_nodbg_empty(Reg)) {
519 // This instruction has users, but if the only user is the phi node for
520 // the parent block, and the only use of that phi node is this
521 // instruction, then this instruction is dead: both it (and the phi
522 // node) can be removed.
523 MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg);
524 if (llvm::next(I) == MRI->use_end() &&
525 I.getOperand().getParent()->isPHI()) {
526 MachineInstr *OnePhi = I.getOperand().getParent();
527
528 for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
529 const MachineOperand &OPO = OnePhi->getOperand(j);
530 if (OPO.isReg() && OPO.isDef()) {
531 unsigned OPReg = OPO.getReg();
532
533 MachineRegisterInfo::use_iterator nextJ;
534 for (MachineRegisterInfo::use_iterator J = MRI->use_begin(OPReg),
535 E = MRI->use_end(); J!=E; J=nextJ) {
536 nextJ = llvm::next(J);
537 MachineOperand& Use = J.getOperand();
538 MachineInstr *UseMI = Use.getParent();
539
540 if (MI != UseMI) {
541 // The phi node has a user that is not MI, bail...
542 return false;
543 }
544 }
545 }
546 }
547
548 DeadPhis.push_back(OnePhi);
549 } else {
550 // This def has a non-debug use. Don't delete the instruction!
551 return false;
552 }
553 }
554 }
555 }
556
557 // If there are no defs with uses, the instruction is dead.
558 return true;
559 }
560
removeIfDead(MachineInstr * MI)561 void PPCCTRLoops::removeIfDead(MachineInstr *MI) {
562 // This procedure was essentially copied from DeadMachineInstructionElim
563
564 SmallVector<MachineInstr *, 1> DeadPhis;
565 if (isDead(MI, DeadPhis)) {
566 DEBUG(dbgs() << "CTR looping will remove: " << *MI);
567
568 // It is possible that some DBG_VALUE instructions refer to this
569 // instruction. Examine each def operand for such references;
570 // if found, mark the DBG_VALUE as undef (but don't delete it).
571 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
572 const MachineOperand &MO = MI->getOperand(i);
573 if (!MO.isReg() || !MO.isDef())
574 continue;
575 unsigned Reg = MO.getReg();
576 MachineRegisterInfo::use_iterator nextI;
577 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
578 E = MRI->use_end(); I!=E; I=nextI) {
579 nextI = llvm::next(I); // I is invalidated by the setReg
580 MachineOperand& Use = I.getOperand();
581 MachineInstr *UseMI = Use.getParent();
582 if (UseMI==MI)
583 continue;
584 if (Use.isDebug()) // this might also be a instr -> phi -> instr case
585 // which can also be removed.
586 UseMI->getOperand(0).setReg(0U);
587 }
588 }
589
590 MI->eraseFromParent();
591 for (unsigned i = 0; i < DeadPhis.size(); ++i) {
592 DeadPhis[i]->eraseFromParent();
593 }
594 }
595 }
596
597 /// converToCTRLoop - check if the loop is a candidate for
598 /// converting to a CTR loop. If so, then perform the
599 /// transformation.
600 ///
601 /// This function works on innermost loops first. A loop can
602 /// be converted if it is a counting loop; either a register
603 /// value or an immediate.
604 ///
605 /// The code makes several assumptions about the representation
606 /// of the loop in llvm.
convertToCTRLoop(MachineLoop * L)607 bool PPCCTRLoops::convertToCTRLoop(MachineLoop *L) {
608 bool Changed = false;
609 // Process nested loops first.
610 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
611 Changed |= convertToCTRLoop(*I);
612 }
613 // If a nested loop has been converted, then we can't convert this loop.
614 if (Changed) {
615 return Changed;
616 }
617
618 SmallVector<MachineInstr *, 2> OldInsts;
619 // Are we able to determine the trip count for the loop?
620 CountValue *TripCount = getTripCount(L, OldInsts);
621 if (TripCount == 0) {
622 DEBUG(dbgs() << "failed to get trip count!\n");
623 return false;
624 }
625
626 if (TripCount->isImm()) {
627 DEBUG(dbgs() << "constant trip count: " << TripCount->getImm() << "\n");
628
629 // FIXME: We currently can't form 64-bit constants
630 // (including 32-bit unsigned constants)
631 if (!isInt<32>(TripCount->getImm()))
632 return false;
633 }
634
635 // Does the loop contain any invalid instructions?
636 if (containsInvalidInstruction(L)) {
637 return false;
638 }
639 MachineBasicBlock *Preheader = L->getLoopPreheader();
640 // No preheader means there's not place for the loop instr.
641 if (Preheader == 0) {
642 return false;
643 }
644 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
645
646 DebugLoc dl;
647 if (InsertPos != Preheader->end())
648 dl = InsertPos->getDebugLoc();
649
650 MachineBasicBlock *LastMBB = L->getExitingBlock();
651 // Don't generate CTR loop if the loop has more than one exit.
652 if (LastMBB == 0) {
653 return false;
654 }
655 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
656
657 // Determine the loop start.
658 MachineBasicBlock *LoopStart = L->getTopBlock();
659 if (L->getLoopLatch() != LastMBB) {
660 // When the exit and latch are not the same, use the latch block as the
661 // start.
662 // The loop start address is used only after the 1st iteration, and the loop
663 // latch may contains instrs. that need to be executed after the 1st iter.
664 LoopStart = L->getLoopLatch();
665 // Make sure the latch is a successor of the exit, otherwise it won't work.
666 if (!LastMBB->isSuccessor(LoopStart)) {
667 return false;
668 }
669 }
670
671 // Convert the loop to a CTR loop
672 DEBUG(dbgs() << "Change to CTR loop at "; L->dump());
673
674 MachineFunction *MF = LastMBB->getParent();
675 const PPCSubtarget &Subtarget = MF->getTarget().getSubtarget<PPCSubtarget>();
676 bool isPPC64 = Subtarget.isPPC64();
677
678 const TargetRegisterClass *GPRC = &PPC::GPRCRegClass;
679 const TargetRegisterClass *G8RC = &PPC::G8RCRegClass;
680 const TargetRegisterClass *RC = isPPC64 ? G8RC : GPRC;
681
682 unsigned CountReg;
683 if (TripCount->isReg()) {
684 // Create a copy of the loop count register.
685 const TargetRegisterClass *SrcRC =
686 MF->getRegInfo().getRegClass(TripCount->getReg());
687 CountReg = MF->getRegInfo().createVirtualRegister(RC);
688 unsigned CopyOp = (isPPC64 && SrcRC == GPRC) ?
689 (unsigned) PPC::EXTSW_32_64 :
690 (unsigned) TargetOpcode::COPY;
691 BuildMI(*Preheader, InsertPos, dl,
692 TII->get(CopyOp), CountReg).addReg(TripCount->getReg());
693 if (TripCount->isNeg()) {
694 unsigned CountReg1 = CountReg;
695 CountReg = MF->getRegInfo().createVirtualRegister(RC);
696 BuildMI(*Preheader, InsertPos, dl,
697 TII->get(isPPC64 ? PPC::NEG8 : PPC::NEG),
698 CountReg).addReg(CountReg1);
699 }
700 } else {
701 assert(TripCount->isImm() && "Expecting immedate vaule for trip count");
702 // Put the trip count in a register for transfer into the count register.
703
704 int64_t CountImm = TripCount->getImm();
705 if (TripCount->isNeg())
706 CountImm = -CountImm;
707
708 CountReg = MF->getRegInfo().createVirtualRegister(RC);
709 if (abs64(CountImm) > 0x7FFF) {
710 BuildMI(*Preheader, InsertPos, dl,
711 TII->get(isPPC64 ? PPC::LIS8 : PPC::LIS),
712 CountReg).addImm((CountImm >> 16) & 0xFFFF);
713 unsigned CountReg1 = CountReg;
714 CountReg = MF->getRegInfo().createVirtualRegister(RC);
715 BuildMI(*Preheader, InsertPos, dl,
716 TII->get(isPPC64 ? PPC::ORI8 : PPC::ORI),
717 CountReg).addReg(CountReg1).addImm(CountImm & 0xFFFF);
718 } else {
719 BuildMI(*Preheader, InsertPos, dl,
720 TII->get(isPPC64 ? PPC::LI8 : PPC::LI),
721 CountReg).addImm(CountImm);
722 }
723 }
724
725 // Add the mtctr instruction to the beginning of the loop.
726 BuildMI(*Preheader, InsertPos, dl,
727 TII->get(isPPC64 ? PPC::MTCTR8 : PPC::MTCTR)).addReg(CountReg,
728 TripCount->isImm() ? RegState::Kill : 0);
729
730 // Make sure the loop start always has a reference in the CFG. We need to
731 // create a BlockAddress operand to get this mechanism to work both the
732 // MachineBasicBlock and BasicBlock objects need the flag set.
733 LoopStart->setHasAddressTaken();
734 // This line is needed to set the hasAddressTaken flag on the BasicBlock
735 // object
736 BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
737
738 // Replace the loop branch with a bdnz instruction.
739 dl = LastI->getDebugLoc();
740 const std::vector<MachineBasicBlock*> Blocks = L->getBlocks();
741 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
742 MachineBasicBlock *MBB = Blocks[i];
743 if (MBB != Preheader)
744 MBB->addLiveIn(isPPC64 ? PPC::CTR8 : PPC::CTR);
745 }
746
747 // The loop ends with either:
748 // - a conditional branch followed by an unconditional branch, or
749 // - a conditional branch to the loop start.
750 assert(LastI->getOpcode() == PPC::BCC &&
751 "loop end must start with a BCC instruction");
752 // Either the BCC branches to the beginning of the loop, or it
753 // branches out of the loop and there is an unconditional branch
754 // to the start of the loop.
755 MachineBasicBlock *BranchTarget = LastI->getOperand(2).getMBB();
756 BuildMI(*LastMBB, LastI, dl,
757 TII->get((BranchTarget == LoopStart) ?
758 (isPPC64 ? PPC::BDNZ8 : PPC::BDNZ) :
759 (isPPC64 ? PPC::BDZ8 : PPC::BDZ))).addMBB(BranchTarget);
760
761 // Conditional branch; just delete it.
762 DEBUG(dbgs() << "Removing old branch: " << *LastI);
763 LastMBB->erase(LastI);
764
765 delete TripCount;
766
767 // The induction operation (add) and the comparison (cmpwi) may now be
768 // unneeded. If these are unneeded, then remove them.
769 for (unsigned i = 0; i < OldInsts.size(); ++i)
770 removeIfDead(OldInsts[i]);
771
772 ++NumCTRLoops;
773 return true;
774 }
775
776