PPCCTRLoops.cpp revision e39b107c468affd0aafa719edce67717cbb4bbec
199f823f94374917174f96a7689955b8463db6816Hal Finkel//===-- PPCCTRLoops.cpp - Identify and generate CTR loops -----------------===// 299f823f94374917174f96a7689955b8463db6816Hal Finkel// 399f823f94374917174f96a7689955b8463db6816Hal Finkel// The LLVM Compiler Infrastructure 499f823f94374917174f96a7689955b8463db6816Hal Finkel// 599f823f94374917174f96a7689955b8463db6816Hal Finkel// This file is distributed under the University of Illinois Open Source 699f823f94374917174f96a7689955b8463db6816Hal Finkel// License. See LICENSE.TXT for details. 799f823f94374917174f96a7689955b8463db6816Hal Finkel// 899f823f94374917174f96a7689955b8463db6816Hal Finkel//===----------------------------------------------------------------------===// 999f823f94374917174f96a7689955b8463db6816Hal Finkel// 1099f823f94374917174f96a7689955b8463db6816Hal Finkel// This pass identifies loops where we can generate the PPC branch instructions 1199f823f94374917174f96a7689955b8463db6816Hal Finkel// that decrement and test the count register (CTR) (bdnz and friends). 1299f823f94374917174f96a7689955b8463db6816Hal Finkel// This pass is based on the HexagonHardwareLoops pass. 1399f823f94374917174f96a7689955b8463db6816Hal Finkel// 1499f823f94374917174f96a7689955b8463db6816Hal Finkel// The pattern that defines the induction variable can changed depending on 1599f823f94374917174f96a7689955b8463db6816Hal Finkel// prior optimizations. For example, the IndVarSimplify phase run by 'opt' 1699f823f94374917174f96a7689955b8463db6816Hal Finkel// normalizes induction variables, and the Loop Strength Reduction pass 1799f823f94374917174f96a7689955b8463db6816Hal Finkel// run by 'llc' may also make changes to the induction variable. 1899f823f94374917174f96a7689955b8463db6816Hal Finkel// The pattern detected by this phase is due to running Strength Reduction. 1999f823f94374917174f96a7689955b8463db6816Hal Finkel// 2099f823f94374917174f96a7689955b8463db6816Hal Finkel// Criteria for CTR loops: 2199f823f94374917174f96a7689955b8463db6816Hal Finkel// - Countable loops (w/ ind. var for a trip count) 2299f823f94374917174f96a7689955b8463db6816Hal Finkel// - Assumes loops are normalized by IndVarSimplify 2399f823f94374917174f96a7689955b8463db6816Hal Finkel// - Try inner-most loops first 2499f823f94374917174f96a7689955b8463db6816Hal Finkel// - No nested CTR loops. 2599f823f94374917174f96a7689955b8463db6816Hal Finkel// - No function calls in loops. 2699f823f94374917174f96a7689955b8463db6816Hal Finkel// 2799f823f94374917174f96a7689955b8463db6816Hal Finkel// Note: As with unconverted loops, PPCBranchSelector must be run after this 2899f823f94374917174f96a7689955b8463db6816Hal Finkel// pass in order to convert long-displacement jumps into jump pairs. 2999f823f94374917174f96a7689955b8463db6816Hal Finkel// 3099f823f94374917174f96a7689955b8463db6816Hal Finkel//===----------------------------------------------------------------------===// 3199f823f94374917174f96a7689955b8463db6816Hal Finkel 3299f823f94374917174f96a7689955b8463db6816Hal Finkel#define DEBUG_TYPE "ctrloops" 3399f823f94374917174f96a7689955b8463db6816Hal Finkel#include "PPC.h" 342741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel#include "MCTargetDesc/PPCPredicates.h" 35d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "PPCTargetMachine.h" 3699f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/ADT/DenseMap.h" 3799f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/ADT/Statistic.h" 3899f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineDominators.h" 3999f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineFunction.h" 4099f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineFunctionPass.h" 4199f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineInstrBuilder.h" 4299f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineLoopInfo.h" 4399f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineRegisterInfo.h" 44d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/Passes.h" 4599f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/RegisterScavenging.h" 460b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 47d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/PassSupport.h" 4899f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/Support/Debug.h" 4999f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/Support/raw_ostream.h" 5099f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/Target/TargetInstrInfo.h" 5199f823f94374917174f96a7689955b8463db6816Hal Finkel#include <algorithm> 5299f823f94374917174f96a7689955b8463db6816Hal Finkel 5399f823f94374917174f96a7689955b8463db6816Hal Finkelusing namespace llvm; 5499f823f94374917174f96a7689955b8463db6816Hal Finkel 5599f823f94374917174f96a7689955b8463db6816Hal FinkelSTATISTIC(NumCTRLoops, "Number of loops converted to CTR loops"); 5699f823f94374917174f96a7689955b8463db6816Hal Finkel 5796848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszeknamespace llvm { 5896848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek void initializePPCCTRLoopsPass(PassRegistry&); 5996848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek} 6096848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek 6199f823f94374917174f96a7689955b8463db6816Hal Finkelnamespace { 6299f823f94374917174f96a7689955b8463db6816Hal Finkel class CountValue; 6399f823f94374917174f96a7689955b8463db6816Hal Finkel struct PPCCTRLoops : public MachineFunctionPass { 6499f823f94374917174f96a7689955b8463db6816Hal Finkel MachineLoopInfo *MLI; 6599f823f94374917174f96a7689955b8463db6816Hal Finkel MachineRegisterInfo *MRI; 6699f823f94374917174f96a7689955b8463db6816Hal Finkel const TargetInstrInfo *TII; 6799f823f94374917174f96a7689955b8463db6816Hal Finkel 6899f823f94374917174f96a7689955b8463db6816Hal Finkel public: 6999f823f94374917174f96a7689955b8463db6816Hal Finkel static char ID; // Pass identification, replacement for typeid 7099f823f94374917174f96a7689955b8463db6816Hal Finkel 7196848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek PPCCTRLoops() : MachineFunctionPass(ID) { 7296848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek initializePPCCTRLoopsPass(*PassRegistry::getPassRegistry()); 7396848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek } 7499f823f94374917174f96a7689955b8463db6816Hal Finkel 7599f823f94374917174f96a7689955b8463db6816Hal Finkel virtual bool runOnMachineFunction(MachineFunction &MF); 7699f823f94374917174f96a7689955b8463db6816Hal Finkel 7799f823f94374917174f96a7689955b8463db6816Hal Finkel const char *getPassName() const { return "PPC CTR Loops"; } 7899f823f94374917174f96a7689955b8463db6816Hal Finkel 7999f823f94374917174f96a7689955b8463db6816Hal Finkel virtual void getAnalysisUsage(AnalysisUsage &AU) const { 8099f823f94374917174f96a7689955b8463db6816Hal Finkel AU.setPreservesCFG(); 8199f823f94374917174f96a7689955b8463db6816Hal Finkel AU.addRequired<MachineDominatorTree>(); 8299f823f94374917174f96a7689955b8463db6816Hal Finkel AU.addPreserved<MachineDominatorTree>(); 8399f823f94374917174f96a7689955b8463db6816Hal Finkel AU.addRequired<MachineLoopInfo>(); 8499f823f94374917174f96a7689955b8463db6816Hal Finkel AU.addPreserved<MachineLoopInfo>(); 8599f823f94374917174f96a7689955b8463db6816Hal Finkel MachineFunctionPass::getAnalysisUsage(AU); 8699f823f94374917174f96a7689955b8463db6816Hal Finkel } 8799f823f94374917174f96a7689955b8463db6816Hal Finkel 8899f823f94374917174f96a7689955b8463db6816Hal Finkel private: 8999f823f94374917174f96a7689955b8463db6816Hal Finkel /// getCanonicalInductionVariable - Check to see if the loop has a canonical 9099f823f94374917174f96a7689955b8463db6816Hal Finkel /// induction variable. 9199f823f94374917174f96a7689955b8463db6816Hal Finkel /// Should be defined in MachineLoop. Based upon version in class Loop. 922741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel void getCanonicalInductionVariable(MachineLoop *L, 932741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel SmallVector<MachineInstr *, 4> &IVars, 942741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel SmallVector<MachineInstr *, 4> &IOps) const; 9599f823f94374917174f96a7689955b8463db6816Hal Finkel 9699f823f94374917174f96a7689955b8463db6816Hal Finkel /// getTripCount - Return a loop-invariant LLVM register indicating the 9799f823f94374917174f96a7689955b8463db6816Hal Finkel /// number of times the loop will be executed. If the trip-count cannot 9899f823f94374917174f96a7689955b8463db6816Hal Finkel /// be determined, this return null. 992741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel CountValue *getTripCount(MachineLoop *L, 10099f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 2> &OldInsts) const; 10199f823f94374917174f96a7689955b8463db6816Hal Finkel 10299f823f94374917174f96a7689955b8463db6816Hal Finkel /// isInductionOperation - Return true if the instruction matches the 10399f823f94374917174f96a7689955b8463db6816Hal Finkel /// pattern for an opertion that defines an induction variable. 10499f823f94374917174f96a7689955b8463db6816Hal Finkel bool isInductionOperation(const MachineInstr *MI, unsigned IVReg) const; 10599f823f94374917174f96a7689955b8463db6816Hal Finkel 10699f823f94374917174f96a7689955b8463db6816Hal Finkel /// isInvalidOperation - Return true if the instruction is not valid within 10799f823f94374917174f96a7689955b8463db6816Hal Finkel /// a CTR loop. 10899f823f94374917174f96a7689955b8463db6816Hal Finkel bool isInvalidLoopOperation(const MachineInstr *MI) const; 10999f823f94374917174f96a7689955b8463db6816Hal Finkel 11099f823f94374917174f96a7689955b8463db6816Hal Finkel /// containsInavlidInstruction - Return true if the loop contains an 11199f823f94374917174f96a7689955b8463db6816Hal Finkel /// instruction that inhibits using the CTR loop. 11299f823f94374917174f96a7689955b8463db6816Hal Finkel bool containsInvalidInstruction(MachineLoop *L) const; 11399f823f94374917174f96a7689955b8463db6816Hal Finkel 11499f823f94374917174f96a7689955b8463db6816Hal Finkel /// converToCTRLoop - Given a loop, check if we can convert it to a 11599f823f94374917174f96a7689955b8463db6816Hal Finkel /// CTR loop. If so, then perform the conversion and return true. 11699f823f94374917174f96a7689955b8463db6816Hal Finkel bool convertToCTRLoop(MachineLoop *L); 11799f823f94374917174f96a7689955b8463db6816Hal Finkel 11899f823f94374917174f96a7689955b8463db6816Hal Finkel /// isDead - Return true if the instruction is now dead. 11999f823f94374917174f96a7689955b8463db6816Hal Finkel bool isDead(const MachineInstr *MI, 12099f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 1> &DeadPhis) const; 12199f823f94374917174f96a7689955b8463db6816Hal Finkel 12299f823f94374917174f96a7689955b8463db6816Hal Finkel /// removeIfDead - Remove the instruction if it is now dead. 12399f823f94374917174f96a7689955b8463db6816Hal Finkel void removeIfDead(MachineInstr *MI); 12499f823f94374917174f96a7689955b8463db6816Hal Finkel }; 12599f823f94374917174f96a7689955b8463db6816Hal Finkel 12699f823f94374917174f96a7689955b8463db6816Hal Finkel char PPCCTRLoops::ID = 0; 12799f823f94374917174f96a7689955b8463db6816Hal Finkel 12899f823f94374917174f96a7689955b8463db6816Hal Finkel 12999f823f94374917174f96a7689955b8463db6816Hal Finkel // CountValue class - Abstraction for a trip count of a loop. A 13099f823f94374917174f96a7689955b8463db6816Hal Finkel // smaller vesrsion of the MachineOperand class without the concerns 13199f823f94374917174f96a7689955b8463db6816Hal Finkel // of changing the operand representation. 13299f823f94374917174f96a7689955b8463db6816Hal Finkel class CountValue { 13399f823f94374917174f96a7689955b8463db6816Hal Finkel public: 13499f823f94374917174f96a7689955b8463db6816Hal Finkel enum CountValueType { 13599f823f94374917174f96a7689955b8463db6816Hal Finkel CV_Register, 13699f823f94374917174f96a7689955b8463db6816Hal Finkel CV_Immediate 13799f823f94374917174f96a7689955b8463db6816Hal Finkel }; 13899f823f94374917174f96a7689955b8463db6816Hal Finkel private: 13999f823f94374917174f96a7689955b8463db6816Hal Finkel CountValueType Kind; 14099f823f94374917174f96a7689955b8463db6816Hal Finkel union Values { 14199f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned RegNum; 14299f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t ImmVal; 14399f823f94374917174f96a7689955b8463db6816Hal Finkel Values(unsigned r) : RegNum(r) {} 14499f823f94374917174f96a7689955b8463db6816Hal Finkel Values(int64_t i) : ImmVal(i) {} 14599f823f94374917174f96a7689955b8463db6816Hal Finkel } Contents; 14699f823f94374917174f96a7689955b8463db6816Hal Finkel bool isNegative; 14799f823f94374917174f96a7689955b8463db6816Hal Finkel 14899f823f94374917174f96a7689955b8463db6816Hal Finkel public: 14999f823f94374917174f96a7689955b8463db6816Hal Finkel CountValue(unsigned r, bool neg) : Kind(CV_Register), Contents(r), 15099f823f94374917174f96a7689955b8463db6816Hal Finkel isNegative(neg) {} 15199f823f94374917174f96a7689955b8463db6816Hal Finkel explicit CountValue(int64_t i) : Kind(CV_Immediate), Contents(i), 15299f823f94374917174f96a7689955b8463db6816Hal Finkel isNegative(i < 0) {} 15399f823f94374917174f96a7689955b8463db6816Hal Finkel CountValueType getType() const { return Kind; } 15499f823f94374917174f96a7689955b8463db6816Hal Finkel bool isReg() const { return Kind == CV_Register; } 15599f823f94374917174f96a7689955b8463db6816Hal Finkel bool isImm() const { return Kind == CV_Immediate; } 15699f823f94374917174f96a7689955b8463db6816Hal Finkel bool isNeg() const { return isNegative; } 15799f823f94374917174f96a7689955b8463db6816Hal Finkel 15899f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned getReg() const { 15999f823f94374917174f96a7689955b8463db6816Hal Finkel assert(isReg() && "Wrong CountValue accessor"); 16099f823f94374917174f96a7689955b8463db6816Hal Finkel return Contents.RegNum; 16199f823f94374917174f96a7689955b8463db6816Hal Finkel } 16299f823f94374917174f96a7689955b8463db6816Hal Finkel void setReg(unsigned Val) { 16399f823f94374917174f96a7689955b8463db6816Hal Finkel Contents.RegNum = Val; 16499f823f94374917174f96a7689955b8463db6816Hal Finkel } 16599f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t getImm() const { 16699f823f94374917174f96a7689955b8463db6816Hal Finkel assert(isImm() && "Wrong CountValue accessor"); 16799f823f94374917174f96a7689955b8463db6816Hal Finkel if (isNegative) { 16899f823f94374917174f96a7689955b8463db6816Hal Finkel return -Contents.ImmVal; 16999f823f94374917174f96a7689955b8463db6816Hal Finkel } 17099f823f94374917174f96a7689955b8463db6816Hal Finkel return Contents.ImmVal; 17199f823f94374917174f96a7689955b8463db6816Hal Finkel } 17299f823f94374917174f96a7689955b8463db6816Hal Finkel void setImm(int64_t Val) { 17399f823f94374917174f96a7689955b8463db6816Hal Finkel Contents.ImmVal = Val; 17499f823f94374917174f96a7689955b8463db6816Hal Finkel } 17599f823f94374917174f96a7689955b8463db6816Hal Finkel 17699f823f94374917174f96a7689955b8463db6816Hal Finkel void print(raw_ostream &OS, const TargetMachine *TM = 0) const { 17799f823f94374917174f96a7689955b8463db6816Hal Finkel if (isReg()) { OS << PrintReg(getReg()); } 17899f823f94374917174f96a7689955b8463db6816Hal Finkel if (isImm()) { OS << getImm(); } 17999f823f94374917174f96a7689955b8463db6816Hal Finkel } 18099f823f94374917174f96a7689955b8463db6816Hal Finkel }; 18199f823f94374917174f96a7689955b8463db6816Hal Finkel} // end anonymous namespace 18299f823f94374917174f96a7689955b8463db6816Hal Finkel 18396848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof ParzyszekINITIALIZE_PASS_BEGIN(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops", 18496848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek false, false) 18596848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof ParzyszekINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 18696848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof ParzyszekINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 18796848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof ParzyszekINITIALIZE_PASS_END(PPCCTRLoops, "ppc-ctr-loops", "PowerPC CTR Loops", 18896848dfc465c8c7f156a562c246803ebefcf21cfKrzysztof Parzyszek false, false) 18999f823f94374917174f96a7689955b8463db6816Hal Finkel 19099f823f94374917174f96a7689955b8463db6816Hal Finkel/// isCompareEquals - Returns true if the instruction is a compare equals 19199f823f94374917174f96a7689955b8463db6816Hal Finkel/// instruction with an immediate operand. 1929887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkelstatic bool isCompareEqualsImm(const MachineInstr *MI, bool &SignedCmp, 1939887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel bool &Int64Cmp) { 1949887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel if (MI->getOpcode() == PPC::CMPWI) { 1952741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel SignedCmp = true; 1969887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel Int64Cmp = false; 19799f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 1989887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel } else if (MI->getOpcode() == PPC::CMPDI) { 1999887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel SignedCmp = true; 2009887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel Int64Cmp = true; 2019887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel return true; 2029887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel } else if (MI->getOpcode() == PPC::CMPLWI) { 2039887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel SignedCmp = false; 2049887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel Int64Cmp = false; 2059887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel return true; 2069887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel } else if (MI->getOpcode() == PPC::CMPLDI) { 2072741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel SignedCmp = false; 2089887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel Int64Cmp = true; 20999f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 21099f823f94374917174f96a7689955b8463db6816Hal Finkel } 21199f823f94374917174f96a7689955b8463db6816Hal Finkel 21299f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 21399f823f94374917174f96a7689955b8463db6816Hal Finkel} 21499f823f94374917174f96a7689955b8463db6816Hal Finkel 21599f823f94374917174f96a7689955b8463db6816Hal Finkel 21699f823f94374917174f96a7689955b8463db6816Hal Finkel/// createPPCCTRLoops - Factory for creating 21799f823f94374917174f96a7689955b8463db6816Hal Finkel/// the CTR loop phase. 21899f823f94374917174f96a7689955b8463db6816Hal FinkelFunctionPass *llvm::createPPCCTRLoops() { 21999f823f94374917174f96a7689955b8463db6816Hal Finkel return new PPCCTRLoops(); 22099f823f94374917174f96a7689955b8463db6816Hal Finkel} 22199f823f94374917174f96a7689955b8463db6816Hal Finkel 22299f823f94374917174f96a7689955b8463db6816Hal Finkel 22399f823f94374917174f96a7689955b8463db6816Hal Finkelbool PPCCTRLoops::runOnMachineFunction(MachineFunction &MF) { 22499f823f94374917174f96a7689955b8463db6816Hal Finkel DEBUG(dbgs() << "********* PPC CTR Loops *********\n"); 22599f823f94374917174f96a7689955b8463db6816Hal Finkel 22699f823f94374917174f96a7689955b8463db6816Hal Finkel bool Changed = false; 22799f823f94374917174f96a7689955b8463db6816Hal Finkel 22899f823f94374917174f96a7689955b8463db6816Hal Finkel // get the loop information 22999f823f94374917174f96a7689955b8463db6816Hal Finkel MLI = &getAnalysis<MachineLoopInfo>(); 23099f823f94374917174f96a7689955b8463db6816Hal Finkel // get the register information 23199f823f94374917174f96a7689955b8463db6816Hal Finkel MRI = &MF.getRegInfo(); 23299f823f94374917174f96a7689955b8463db6816Hal Finkel // the target specific instructio info. 23399f823f94374917174f96a7689955b8463db6816Hal Finkel TII = MF.getTarget().getInstrInfo(); 23499f823f94374917174f96a7689955b8463db6816Hal Finkel 23599f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); 23699f823f94374917174f96a7689955b8463db6816Hal Finkel I != E; ++I) { 23799f823f94374917174f96a7689955b8463db6816Hal Finkel MachineLoop *L = *I; 23899f823f94374917174f96a7689955b8463db6816Hal Finkel if (!L->getParentLoop()) { 23999f823f94374917174f96a7689955b8463db6816Hal Finkel Changed |= convertToCTRLoop(L); 24099f823f94374917174f96a7689955b8463db6816Hal Finkel } 24199f823f94374917174f96a7689955b8463db6816Hal Finkel } 24299f823f94374917174f96a7689955b8463db6816Hal Finkel 24399f823f94374917174f96a7689955b8463db6816Hal Finkel return Changed; 24499f823f94374917174f96a7689955b8463db6816Hal Finkel} 24599f823f94374917174f96a7689955b8463db6816Hal Finkel 24699f823f94374917174f96a7689955b8463db6816Hal Finkel/// getCanonicalInductionVariable - Check to see if the loop has a canonical 24799f823f94374917174f96a7689955b8463db6816Hal Finkel/// induction variable. We check for a simple recurrence pattern - an 24899f823f94374917174f96a7689955b8463db6816Hal Finkel/// integer recurrence that decrements by one each time through the loop and 24999f823f94374917174f96a7689955b8463db6816Hal Finkel/// ends at zero. If so, return the phi node that corresponds to it. 25099f823f94374917174f96a7689955b8463db6816Hal Finkel/// 25199f823f94374917174f96a7689955b8463db6816Hal Finkel/// Based upon the similar code in LoopInfo except this code is specific to 25299f823f94374917174f96a7689955b8463db6816Hal Finkel/// the machine. 25399f823f94374917174f96a7689955b8463db6816Hal Finkel/// This method assumes that the IndVarSimplify pass has been run by 'opt'. 25499f823f94374917174f96a7689955b8463db6816Hal Finkel/// 2552741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkelvoid 2562741d2cfdff89e45c6b98cd520d5cd3fe97829adHal FinkelPPCCTRLoops::getCanonicalInductionVariable(MachineLoop *L, 2572741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel SmallVector<MachineInstr *, 4> &IVars, 2582741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel SmallVector<MachineInstr *, 4> &IOps) const { 25999f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *TopMBB = L->getTopBlock(); 26099f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(); 26199f823f94374917174f96a7689955b8463db6816Hal Finkel assert(PI != TopMBB->pred_end() && 26299f823f94374917174f96a7689955b8463db6816Hal Finkel "Loop must have more than one incoming edge!"); 26399f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *Backedge = *PI++; 2642741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel if (PI == TopMBB->pred_end()) return; // dead loop 26599f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *Incoming = *PI++; 2662741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel if (PI != TopMBB->pred_end()) return; // multiple backedges? 26799f823f94374917174f96a7689955b8463db6816Hal Finkel 26899f823f94374917174f96a7689955b8463db6816Hal Finkel // make sure there is one incoming and one backedge and determine which 26999f823f94374917174f96a7689955b8463db6816Hal Finkel // is which. 27099f823f94374917174f96a7689955b8463db6816Hal Finkel if (L->contains(Incoming)) { 27199f823f94374917174f96a7689955b8463db6816Hal Finkel if (L->contains(Backedge)) 2722741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel return; 27399f823f94374917174f96a7689955b8463db6816Hal Finkel std::swap(Incoming, Backedge); 27499f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (!L->contains(Backedge)) 2752741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel return; 27699f823f94374917174f96a7689955b8463db6816Hal Finkel 27799f823f94374917174f96a7689955b8463db6816Hal Finkel // Loop over all of the PHI nodes, looking for a canonical induction variable: 27899f823f94374917174f96a7689955b8463db6816Hal Finkel // - The PHI node is "reg1 = PHI reg2, BB1, reg3, BB2". 27999f823f94374917174f96a7689955b8463db6816Hal Finkel // - The recurrence comes from the backedge. 28099f823f94374917174f96a7689955b8463db6816Hal Finkel // - the definition is an induction operatio.n 28199f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineBasicBlock::iterator I = TopMBB->begin(), E = TopMBB->end(); 28299f823f94374917174f96a7689955b8463db6816Hal Finkel I != E && I->isPHI(); ++I) { 28399f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *MPhi = &*I; 28499f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned DefReg = MPhi->getOperand(0).getReg(); 28599f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) { 28699f823f94374917174f96a7689955b8463db6816Hal Finkel // Check each operand for the value from the backedge. 28799f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *MBB = MPhi->getOperand(i+1).getMBB(); 28899f823f94374917174f96a7689955b8463db6816Hal Finkel if (L->contains(MBB)) { // operands comes from the backedge 28999f823f94374917174f96a7689955b8463db6816Hal Finkel // Check if the definition is an induction operation. 29099f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *DI = MRI->getVRegDef(MPhi->getOperand(i).getReg()); 29199f823f94374917174f96a7689955b8463db6816Hal Finkel if (isInductionOperation(DI, DefReg)) { 2922741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel IOps.push_back(DI); 2932741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel IVars.push_back(MPhi); 29499f823f94374917174f96a7689955b8463db6816Hal Finkel } 29599f823f94374917174f96a7689955b8463db6816Hal Finkel } 29699f823f94374917174f96a7689955b8463db6816Hal Finkel } 29799f823f94374917174f96a7689955b8463db6816Hal Finkel } 2982741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel return; 29999f823f94374917174f96a7689955b8463db6816Hal Finkel} 30099f823f94374917174f96a7689955b8463db6816Hal Finkel 30199f823f94374917174f96a7689955b8463db6816Hal Finkel/// getTripCount - Return a loop-invariant LLVM value indicating the 30299f823f94374917174f96a7689955b8463db6816Hal Finkel/// number of times the loop will be executed. The trip count can 30399f823f94374917174f96a7689955b8463db6816Hal Finkel/// be either a register or a constant value. If the trip-count 30499f823f94374917174f96a7689955b8463db6816Hal Finkel/// cannot be determined, this returns null. 30599f823f94374917174f96a7689955b8463db6816Hal Finkel/// 30699f823f94374917174f96a7689955b8463db6816Hal Finkel/// We find the trip count from the phi instruction that defines the 30799f823f94374917174f96a7689955b8463db6816Hal Finkel/// induction variable. We follow the links to the CMP instruction 30899f823f94374917174f96a7689955b8463db6816Hal Finkel/// to get the trip count. 30999f823f94374917174f96a7689955b8463db6816Hal Finkel/// 31099f823f94374917174f96a7689955b8463db6816Hal Finkel/// Based upon getTripCount in LoopInfo. 31199f823f94374917174f96a7689955b8463db6816Hal Finkel/// 3122741d2cfdff89e45c6b98cd520d5cd3fe97829adHal FinkelCountValue *PPCCTRLoops::getTripCount(MachineLoop *L, 31399f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 2> &OldInsts) const { 3142741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel MachineBasicBlock *LastMBB = L->getExitingBlock(); 3152741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // Don't generate a CTR loop if the loop has more than one exit. 3162741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel if (LastMBB == 0) 3172741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel return 0; 3182741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3192741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator(); 3202741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel if (LastI->getOpcode() != PPC::BCC) 3212741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel return 0; 3222741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3232741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // We need to make sure that this compare is defining the condition 3242741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // register actually used by the terminating branch. 3252741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3262741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel unsigned PredReg = LastI->getOperand(1).getReg(); 3272741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel DEBUG(dbgs() << "Examining loop with first terminator: " << *LastI); 3282741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3292741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel unsigned PredCond = LastI->getOperand(0).getImm(); 3302741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel if (PredCond != PPC::PRED_EQ && PredCond != PPC::PRED_NE) 3312741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel return 0; 3322741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 33399f823f94374917174f96a7689955b8463db6816Hal Finkel // Check that the loop has a induction variable. 3342741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel SmallVector<MachineInstr *, 4> IVars, IOps; 3352741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel getCanonicalInductionVariable(L, IVars, IOps); 3362741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel for (unsigned i = 0; i < IVars.size(); ++i) { 3372741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel MachineInstr *IOp = IOps[i]; 3382741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel MachineInstr *IV_Inst = IVars[i]; 3392741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3402741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // Canonical loops will end with a 'cmpwi/cmpdi cr, IV, Imm', 3412741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // if Imm is 0, get the count from the PHI opnd 3422741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // if Imm is -M, than M is the count 3432741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // Otherwise, Imm is the count 3442741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel MachineOperand *IV_Opnd; 3452741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel const MachineOperand *InitialValue; 3462741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel if (!L->contains(IV_Inst->getOperand(2).getMBB())) { 3472741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel InitialValue = &IV_Inst->getOperand(1); 3482741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel IV_Opnd = &IV_Inst->getOperand(3); 3492741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel } else { 3502741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel InitialValue = &IV_Inst->getOperand(3); 3512741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel IV_Opnd = &IV_Inst->getOperand(1); 3522741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel } 35399f823f94374917174f96a7689955b8463db6816Hal Finkel 3542741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel DEBUG(dbgs() << "Considering:\n"); 3552741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel DEBUG(dbgs() << " induction operation: " << *IOp); 3562741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel DEBUG(dbgs() << " induction variable: " << *IV_Inst); 3572741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel DEBUG(dbgs() << " initial value: " << *InitialValue << "\n"); 3582741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3592741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // Look for the cmp instruction to determine if we 3602741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // can get a useful trip count. The trip count can 3612741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // be either a register or an immediate. The location 3622741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // of the value depends upon the type (reg or imm). 3630c5f5f4916a5c72b2a6a9cb13f0b2c2add95b6f1Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator 3640c5f5f4916a5c72b2a6a9cb13f0b2c2add95b6f1Jakob Stoklund Olesen RI = MRI->reg_begin(IV_Opnd->getReg()), RE = MRI->reg_end(); 3650c5f5f4916a5c72b2a6a9cb13f0b2c2add95b6f1Jakob Stoklund Olesen RI != RE; ++RI) { 3660c5f5f4916a5c72b2a6a9cb13f0b2c2add95b6f1Jakob Stoklund Olesen IV_Opnd = &RI.getOperand(); 3679887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel bool SignedCmp, Int64Cmp; 3682741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel MachineInstr *MI = IV_Opnd->getParent(); 3699887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel if (L->contains(MI) && isCompareEqualsImm(MI, SignedCmp, Int64Cmp) && 3702741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel MI->getOperand(0).getReg() == PredReg) { 3712741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3722741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel OldInsts.push_back(MI); 3732741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel OldInsts.push_back(IOp); 3742741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3752741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel DEBUG(dbgs() << " compare: " << *MI); 3762741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3772741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel const MachineOperand &MO = MI->getOperand(2); 3782741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel assert(MO.isImm() && "IV Cmp Operand should be an immediate"); 3792741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3802741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel int64_t ImmVal; 3812741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel if (SignedCmp) 3822741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel ImmVal = (short) MO.getImm(); 3832741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel else 3842741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel ImmVal = MO.getImm(); 3852741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3862741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel const MachineInstr *IV_DefInstr = MRI->getVRegDef(IV_Opnd->getReg()); 3872741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel assert(L->contains(IV_DefInstr->getParent()) && 3882741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel "IV definition should occurs in loop"); 3892741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel int64_t iv_value = (short) IV_DefInstr->getOperand(2).getImm(); 3902741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 39199f823f94374917174f96a7689955b8463db6816Hal Finkel assert(InitialValue->isReg() && "Expecting register for init value"); 3922741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel unsigned InitialValueReg = InitialValue->getReg(); 3932741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 3941448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel MachineInstr *DefInstr = MRI->getVRegDef(InitialValueReg); 3952741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 39699f823f94374917174f96a7689955b8463db6816Hal Finkel // Here we need to look for an immediate load (an li or lis/ori pair). 39799f823f94374917174f96a7689955b8463db6816Hal Finkel if (DefInstr && (DefInstr->getOpcode() == PPC::ORI8 || 39899f823f94374917174f96a7689955b8463db6816Hal Finkel DefInstr->getOpcode() == PPC::ORI)) { 3992741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel int64_t start = (short) DefInstr->getOperand(2).getImm(); 4001448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel MachineInstr *DefInstr2 = 4019887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel MRI->getVRegDef(DefInstr->getOperand(1).getReg()); 40299f823f94374917174f96a7689955b8463db6816Hal Finkel if (DefInstr2 && (DefInstr2->getOpcode() == PPC::LIS8 || 40399f823f94374917174f96a7689955b8463db6816Hal Finkel DefInstr2->getOpcode() == PPC::LIS)) { 4042741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel DEBUG(dbgs() << " initial constant: " << *DefInstr); 4052741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel DEBUG(dbgs() << " initial constant: " << *DefInstr2); 40699f823f94374917174f96a7689955b8463db6816Hal Finkel 4072741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel start |= int64_t(short(DefInstr2->getOperand(1).getImm())) << 16; 4082741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 40999f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t count = ImmVal - start; 41099f823f94374917174f96a7689955b8463db6816Hal Finkel if ((count % iv_value) != 0) { 41199f823f94374917174f96a7689955b8463db6816Hal Finkel return 0; 41299f823f94374917174f96a7689955b8463db6816Hal Finkel } 4131448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel 4141448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel OldInsts.push_back(DefInstr); 4151448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel OldInsts.push_back(DefInstr2); 4161448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel 4179887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel // count/iv_value, the trip count, should be positive here. If it 4189887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel // is negative, that indicates that the counter will wrap. 4199887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel if (Int64Cmp) 4209887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel return new CountValue(count/iv_value); 4219887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel else 4229887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel return new CountValue(uint32_t(count/iv_value)); 42399f823f94374917174f96a7689955b8463db6816Hal Finkel } 42499f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (DefInstr && (DefInstr->getOpcode() == PPC::LI8 || 42599f823f94374917174f96a7689955b8463db6816Hal Finkel DefInstr->getOpcode() == PPC::LI)) { 4262741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel DEBUG(dbgs() << " initial constant: " << *DefInstr); 4272741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 428e39b107c468affd0aafa719edce67717cbb4bbecHal Finkel int64_t count = ImmVal - 429e39b107c468affd0aafa719edce67717cbb4bbecHal Finkel int64_t(short(DefInstr->getOperand(1).getImm())); 43099f823f94374917174f96a7689955b8463db6816Hal Finkel if ((count % iv_value) != 0) { 43199f823f94374917174f96a7689955b8463db6816Hal Finkel return 0; 43299f823f94374917174f96a7689955b8463db6816Hal Finkel } 4331448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel 4341448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel OldInsts.push_back(DefInstr); 4351448d06156728712f47e5a71fac8e8edc0aba73bHal Finkel 4369887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel if (Int64Cmp) 4379887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel return new CountValue(count/iv_value); 4389887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel else 4399887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel return new CountValue(uint32_t(count/iv_value)); 4402741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel } else if (iv_value == 1 || iv_value == -1) { 4412741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // We can't determine a constant starting value. 4422741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel if (ImmVal == 0) { 4432741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel return new CountValue(InitialValueReg, iv_value > 0); 4442741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel } 4452741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel // FIXME: handle non-zero end value. 44699f823f94374917174f96a7689955b8463db6816Hal Finkel } 447e39b107c468affd0aafa719edce67717cbb4bbecHal Finkel // FIXME: handle non-unit increments (we might not want to introduce 448e39b107c468affd0aafa719edce67717cbb4bbecHal Finkel // division but we can handle some 2^n cases with shifts). 4492741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 45099f823f94374917174f96a7689955b8463db6816Hal Finkel } 45199f823f94374917174f96a7689955b8463db6816Hal Finkel } 45299f823f94374917174f96a7689955b8463db6816Hal Finkel } 45399f823f94374917174f96a7689955b8463db6816Hal Finkel return 0; 45499f823f94374917174f96a7689955b8463db6816Hal Finkel} 45599f823f94374917174f96a7689955b8463db6816Hal Finkel 45699f823f94374917174f96a7689955b8463db6816Hal Finkel/// isInductionOperation - return true if the operation is matches the 45799f823f94374917174f96a7689955b8463db6816Hal Finkel/// pattern that defines an induction variable: 45899f823f94374917174f96a7689955b8463db6816Hal Finkel/// addi iv, c 45999f823f94374917174f96a7689955b8463db6816Hal Finkel/// 46099f823f94374917174f96a7689955b8463db6816Hal Finkelbool 46199f823f94374917174f96a7689955b8463db6816Hal FinkelPPCCTRLoops::isInductionOperation(const MachineInstr *MI, 46299f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned IVReg) const { 46399f823f94374917174f96a7689955b8463db6816Hal Finkel return ((MI->getOpcode() == PPC::ADDI || MI->getOpcode() == PPC::ADDI8) && 464daa03ec60475a641bcc66799764977f79997ca45Hal Finkel MI->getOperand(1).isReg() && // could be a frame index instead 46599f823f94374917174f96a7689955b8463db6816Hal Finkel MI->getOperand(1).getReg() == IVReg); 46699f823f94374917174f96a7689955b8463db6816Hal Finkel} 46799f823f94374917174f96a7689955b8463db6816Hal Finkel 46899f823f94374917174f96a7689955b8463db6816Hal Finkel/// isInvalidOperation - Return true if the operation is invalid within 46999f823f94374917174f96a7689955b8463db6816Hal Finkel/// CTR loop. 47099f823f94374917174f96a7689955b8463db6816Hal Finkelbool 47199f823f94374917174f96a7689955b8463db6816Hal FinkelPPCCTRLoops::isInvalidLoopOperation(const MachineInstr *MI) const { 47299f823f94374917174f96a7689955b8463db6816Hal Finkel 47399f823f94374917174f96a7689955b8463db6816Hal Finkel // call is not allowed because the callee may use a CTR loop 47499f823f94374917174f96a7689955b8463db6816Hal Finkel if (MI->getDesc().isCall()) { 47599f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 47699f823f94374917174f96a7689955b8463db6816Hal Finkel } 47799f823f94374917174f96a7689955b8463db6816Hal Finkel // check if the instruction defines a CTR loop register 47899f823f94374917174f96a7689955b8463db6816Hal Finkel // (this will also catch nested CTR loops) 47999f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 48099f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineOperand &MO = MI->getOperand(i); 48199f823f94374917174f96a7689955b8463db6816Hal Finkel if (MO.isReg() && MO.isDef() && 48299f823f94374917174f96a7689955b8463db6816Hal Finkel (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) { 48399f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 48499f823f94374917174f96a7689955b8463db6816Hal Finkel } 48599f823f94374917174f96a7689955b8463db6816Hal Finkel } 48699f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 48799f823f94374917174f96a7689955b8463db6816Hal Finkel} 48899f823f94374917174f96a7689955b8463db6816Hal Finkel 48999f823f94374917174f96a7689955b8463db6816Hal Finkel/// containsInvalidInstruction - Return true if the loop contains 49099f823f94374917174f96a7689955b8463db6816Hal Finkel/// an instruction that inhibits the use of the CTR loop function. 49199f823f94374917174f96a7689955b8463db6816Hal Finkel/// 49299f823f94374917174f96a7689955b8463db6816Hal Finkelbool PPCCTRLoops::containsInvalidInstruction(MachineLoop *L) const { 49399f823f94374917174f96a7689955b8463db6816Hal Finkel const std::vector<MachineBasicBlock*> Blocks = L->getBlocks(); 49499f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 49599f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *MBB = Blocks[i]; 49699f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineBasicBlock::iterator 49799f823f94374917174f96a7689955b8463db6816Hal Finkel MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) { 49899f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineInstr *MI = &*MII; 49999f823f94374917174f96a7689955b8463db6816Hal Finkel if (isInvalidLoopOperation(MI)) { 50099f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 50199f823f94374917174f96a7689955b8463db6816Hal Finkel } 50299f823f94374917174f96a7689955b8463db6816Hal Finkel } 50399f823f94374917174f96a7689955b8463db6816Hal Finkel } 50499f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 50599f823f94374917174f96a7689955b8463db6816Hal Finkel} 50699f823f94374917174f96a7689955b8463db6816Hal Finkel 50799f823f94374917174f96a7689955b8463db6816Hal Finkel/// isDead returns true if the instruction is dead 50899f823f94374917174f96a7689955b8463db6816Hal Finkel/// (this was essentially copied from DeadMachineInstructionElim::isDead, but 50999f823f94374917174f96a7689955b8463db6816Hal Finkel/// with special cases for inline asm, physical registers and instructions with 51099f823f94374917174f96a7689955b8463db6816Hal Finkel/// side effects removed) 51199f823f94374917174f96a7689955b8463db6816Hal Finkelbool PPCCTRLoops::isDead(const MachineInstr *MI, 51299f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 1> &DeadPhis) const { 51399f823f94374917174f96a7689955b8463db6816Hal Finkel // Examine each operand. 51499f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 51599f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineOperand &MO = MI->getOperand(i); 51699f823f94374917174f96a7689955b8463db6816Hal Finkel if (MO.isReg() && MO.isDef()) { 51799f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned Reg = MO.getReg(); 51899f823f94374917174f96a7689955b8463db6816Hal Finkel if (!MRI->use_nodbg_empty(Reg)) { 519e39b107c468affd0aafa719edce67717cbb4bbecHal Finkel // This instruction has users, but if the only user is the phi node for 520e39b107c468affd0aafa719edce67717cbb4bbecHal Finkel // the parent block, and the only use of that phi node is this 521e39b107c468affd0aafa719edce67717cbb4bbecHal Finkel // instruction, then this instruction is dead: both it (and the phi 522e39b107c468affd0aafa719edce67717cbb4bbecHal Finkel // node) can be removed. 52399f823f94374917174f96a7689955b8463db6816Hal Finkel MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg); 52499f823f94374917174f96a7689955b8463db6816Hal Finkel if (llvm::next(I) == MRI->use_end() && 52599f823f94374917174f96a7689955b8463db6816Hal Finkel I.getOperand().getParent()->isPHI()) { 52699f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *OnePhi = I.getOperand().getParent(); 52799f823f94374917174f96a7689955b8463db6816Hal Finkel 52899f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) { 52999f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineOperand &OPO = OnePhi->getOperand(j); 53099f823f94374917174f96a7689955b8463db6816Hal Finkel if (OPO.isReg() && OPO.isDef()) { 53199f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned OPReg = OPO.getReg(); 53299f823f94374917174f96a7689955b8463db6816Hal Finkel 53399f823f94374917174f96a7689955b8463db6816Hal Finkel MachineRegisterInfo::use_iterator nextJ; 53499f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineRegisterInfo::use_iterator J = MRI->use_begin(OPReg), 53599f823f94374917174f96a7689955b8463db6816Hal Finkel E = MRI->use_end(); J!=E; J=nextJ) { 53699f823f94374917174f96a7689955b8463db6816Hal Finkel nextJ = llvm::next(J); 53799f823f94374917174f96a7689955b8463db6816Hal Finkel MachineOperand& Use = J.getOperand(); 53899f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *UseMI = Use.getParent(); 53999f823f94374917174f96a7689955b8463db6816Hal Finkel 54099f823f94374917174f96a7689955b8463db6816Hal Finkel if (MI != UseMI) { 54199f823f94374917174f96a7689955b8463db6816Hal Finkel // The phi node has a user that is not MI, bail... 54299f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 54399f823f94374917174f96a7689955b8463db6816Hal Finkel } 54499f823f94374917174f96a7689955b8463db6816Hal Finkel } 54599f823f94374917174f96a7689955b8463db6816Hal Finkel } 54699f823f94374917174f96a7689955b8463db6816Hal Finkel } 54799f823f94374917174f96a7689955b8463db6816Hal Finkel 54899f823f94374917174f96a7689955b8463db6816Hal Finkel DeadPhis.push_back(OnePhi); 54999f823f94374917174f96a7689955b8463db6816Hal Finkel } else { 55099f823f94374917174f96a7689955b8463db6816Hal Finkel // This def has a non-debug use. Don't delete the instruction! 55199f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 55299f823f94374917174f96a7689955b8463db6816Hal Finkel } 55399f823f94374917174f96a7689955b8463db6816Hal Finkel } 55499f823f94374917174f96a7689955b8463db6816Hal Finkel } 55599f823f94374917174f96a7689955b8463db6816Hal Finkel } 55699f823f94374917174f96a7689955b8463db6816Hal Finkel 55799f823f94374917174f96a7689955b8463db6816Hal Finkel // If there are no defs with uses, the instruction is dead. 55899f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 55999f823f94374917174f96a7689955b8463db6816Hal Finkel} 56099f823f94374917174f96a7689955b8463db6816Hal Finkel 56199f823f94374917174f96a7689955b8463db6816Hal Finkelvoid PPCCTRLoops::removeIfDead(MachineInstr *MI) { 56299f823f94374917174f96a7689955b8463db6816Hal Finkel // This procedure was essentially copied from DeadMachineInstructionElim 56399f823f94374917174f96a7689955b8463db6816Hal Finkel 56499f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 1> DeadPhis; 56599f823f94374917174f96a7689955b8463db6816Hal Finkel if (isDead(MI, DeadPhis)) { 56699f823f94374917174f96a7689955b8463db6816Hal Finkel DEBUG(dbgs() << "CTR looping will remove: " << *MI); 56799f823f94374917174f96a7689955b8463db6816Hal Finkel 56899f823f94374917174f96a7689955b8463db6816Hal Finkel // It is possible that some DBG_VALUE instructions refer to this 56999f823f94374917174f96a7689955b8463db6816Hal Finkel // instruction. Examine each def operand for such references; 57099f823f94374917174f96a7689955b8463db6816Hal Finkel // if found, mark the DBG_VALUE as undef (but don't delete it). 57199f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 57299f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineOperand &MO = MI->getOperand(i); 57399f823f94374917174f96a7689955b8463db6816Hal Finkel if (!MO.isReg() || !MO.isDef()) 57499f823f94374917174f96a7689955b8463db6816Hal Finkel continue; 57599f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned Reg = MO.getReg(); 57699f823f94374917174f96a7689955b8463db6816Hal Finkel MachineRegisterInfo::use_iterator nextI; 57799f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg), 57899f823f94374917174f96a7689955b8463db6816Hal Finkel E = MRI->use_end(); I!=E; I=nextI) { 57999f823f94374917174f96a7689955b8463db6816Hal Finkel nextI = llvm::next(I); // I is invalidated by the setReg 58099f823f94374917174f96a7689955b8463db6816Hal Finkel MachineOperand& Use = I.getOperand(); 58199f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *UseMI = Use.getParent(); 58299f823f94374917174f96a7689955b8463db6816Hal Finkel if (UseMI==MI) 58399f823f94374917174f96a7689955b8463db6816Hal Finkel continue; 58499f823f94374917174f96a7689955b8463db6816Hal Finkel if (Use.isDebug()) // this might also be a instr -> phi -> instr case 58599f823f94374917174f96a7689955b8463db6816Hal Finkel // which can also be removed. 58699f823f94374917174f96a7689955b8463db6816Hal Finkel UseMI->getOperand(0).setReg(0U); 58799f823f94374917174f96a7689955b8463db6816Hal Finkel } 58899f823f94374917174f96a7689955b8463db6816Hal Finkel } 58999f823f94374917174f96a7689955b8463db6816Hal Finkel 59099f823f94374917174f96a7689955b8463db6816Hal Finkel MI->eraseFromParent(); 59199f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0; i < DeadPhis.size(); ++i) { 59299f823f94374917174f96a7689955b8463db6816Hal Finkel DeadPhis[i]->eraseFromParent(); 59399f823f94374917174f96a7689955b8463db6816Hal Finkel } 59499f823f94374917174f96a7689955b8463db6816Hal Finkel } 59599f823f94374917174f96a7689955b8463db6816Hal Finkel} 59699f823f94374917174f96a7689955b8463db6816Hal Finkel 59799f823f94374917174f96a7689955b8463db6816Hal Finkel/// converToCTRLoop - check if the loop is a candidate for 59899f823f94374917174f96a7689955b8463db6816Hal Finkel/// converting to a CTR loop. If so, then perform the 59999f823f94374917174f96a7689955b8463db6816Hal Finkel/// transformation. 60099f823f94374917174f96a7689955b8463db6816Hal Finkel/// 60199f823f94374917174f96a7689955b8463db6816Hal Finkel/// This function works on innermost loops first. A loop can 60299f823f94374917174f96a7689955b8463db6816Hal Finkel/// be converted if it is a counting loop; either a register 60399f823f94374917174f96a7689955b8463db6816Hal Finkel/// value or an immediate. 60499f823f94374917174f96a7689955b8463db6816Hal Finkel/// 60599f823f94374917174f96a7689955b8463db6816Hal Finkel/// The code makes several assumptions about the representation 60699f823f94374917174f96a7689955b8463db6816Hal Finkel/// of the loop in llvm. 60799f823f94374917174f96a7689955b8463db6816Hal Finkelbool PPCCTRLoops::convertToCTRLoop(MachineLoop *L) { 60899f823f94374917174f96a7689955b8463db6816Hal Finkel bool Changed = false; 60999f823f94374917174f96a7689955b8463db6816Hal Finkel // Process nested loops first. 61099f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) { 61199f823f94374917174f96a7689955b8463db6816Hal Finkel Changed |= convertToCTRLoop(*I); 61299f823f94374917174f96a7689955b8463db6816Hal Finkel } 61399f823f94374917174f96a7689955b8463db6816Hal Finkel // If a nested loop has been converted, then we can't convert this loop. 61499f823f94374917174f96a7689955b8463db6816Hal Finkel if (Changed) { 61599f823f94374917174f96a7689955b8463db6816Hal Finkel return Changed; 61699f823f94374917174f96a7689955b8463db6816Hal Finkel } 61799f823f94374917174f96a7689955b8463db6816Hal Finkel 61899f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 2> OldInsts; 61999f823f94374917174f96a7689955b8463db6816Hal Finkel // Are we able to determine the trip count for the loop? 6202741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel CountValue *TripCount = getTripCount(L, OldInsts); 62199f823f94374917174f96a7689955b8463db6816Hal Finkel if (TripCount == 0) { 62299f823f94374917174f96a7689955b8463db6816Hal Finkel DEBUG(dbgs() << "failed to get trip count!\n"); 62399f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 62499f823f94374917174f96a7689955b8463db6816Hal Finkel } 6259887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel 6269887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel if (TripCount->isImm()) { 6279887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel DEBUG(dbgs() << "constant trip count: " << TripCount->getImm() << "\n"); 6289887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel 6299887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel // FIXME: We currently can't form 64-bit constants 6309887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel // (including 32-bit unsigned constants) 6319887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel if (!isInt<32>(TripCount->getImm())) 6329887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel return false; 6339887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel } 6349887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel 63599f823f94374917174f96a7689955b8463db6816Hal Finkel // Does the loop contain any invalid instructions? 63699f823f94374917174f96a7689955b8463db6816Hal Finkel if (containsInvalidInstruction(L)) { 63799f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 63899f823f94374917174f96a7689955b8463db6816Hal Finkel } 63999f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *Preheader = L->getLoopPreheader(); 64099f823f94374917174f96a7689955b8463db6816Hal Finkel // No preheader means there's not place for the loop instr. 64199f823f94374917174f96a7689955b8463db6816Hal Finkel if (Preheader == 0) { 64299f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 64399f823f94374917174f96a7689955b8463db6816Hal Finkel } 64499f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator(); 64599f823f94374917174f96a7689955b8463db6816Hal Finkel 64699f823f94374917174f96a7689955b8463db6816Hal Finkel DebugLoc dl; 64799f823f94374917174f96a7689955b8463db6816Hal Finkel if (InsertPos != Preheader->end()) 64899f823f94374917174f96a7689955b8463db6816Hal Finkel dl = InsertPos->getDebugLoc(); 64999f823f94374917174f96a7689955b8463db6816Hal Finkel 65099f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *LastMBB = L->getExitingBlock(); 65199f823f94374917174f96a7689955b8463db6816Hal Finkel // Don't generate CTR loop if the loop has more than one exit. 65299f823f94374917174f96a7689955b8463db6816Hal Finkel if (LastMBB == 0) { 65399f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 65499f823f94374917174f96a7689955b8463db6816Hal Finkel } 65599f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator(); 65699f823f94374917174f96a7689955b8463db6816Hal Finkel 65799f823f94374917174f96a7689955b8463db6816Hal Finkel // Determine the loop start. 65899f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *LoopStart = L->getTopBlock(); 65999f823f94374917174f96a7689955b8463db6816Hal Finkel if (L->getLoopLatch() != LastMBB) { 66099f823f94374917174f96a7689955b8463db6816Hal Finkel // When the exit and latch are not the same, use the latch block as the 66199f823f94374917174f96a7689955b8463db6816Hal Finkel // start. 66299f823f94374917174f96a7689955b8463db6816Hal Finkel // The loop start address is used only after the 1st iteration, and the loop 66399f823f94374917174f96a7689955b8463db6816Hal Finkel // latch may contains instrs. that need to be executed after the 1st iter. 66499f823f94374917174f96a7689955b8463db6816Hal Finkel LoopStart = L->getLoopLatch(); 66599f823f94374917174f96a7689955b8463db6816Hal Finkel // Make sure the latch is a successor of the exit, otherwise it won't work. 66699f823f94374917174f96a7689955b8463db6816Hal Finkel if (!LastMBB->isSuccessor(LoopStart)) { 66799f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 66899f823f94374917174f96a7689955b8463db6816Hal Finkel } 66999f823f94374917174f96a7689955b8463db6816Hal Finkel } 67099f823f94374917174f96a7689955b8463db6816Hal Finkel 67199f823f94374917174f96a7689955b8463db6816Hal Finkel // Convert the loop to a CTR loop 67299f823f94374917174f96a7689955b8463db6816Hal Finkel DEBUG(dbgs() << "Change to CTR loop at "; L->dump()); 67399f823f94374917174f96a7689955b8463db6816Hal Finkel 67499f823f94374917174f96a7689955b8463db6816Hal Finkel MachineFunction *MF = LastMBB->getParent(); 67599f823f94374917174f96a7689955b8463db6816Hal Finkel const PPCSubtarget &Subtarget = MF->getTarget().getSubtarget<PPCSubtarget>(); 67699f823f94374917174f96a7689955b8463db6816Hal Finkel bool isPPC64 = Subtarget.isPPC64(); 67799f823f94374917174f96a7689955b8463db6816Hal Finkel 6782741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel const TargetRegisterClass *GPRC = &PPC::GPRCRegClass; 6792741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel const TargetRegisterClass *G8RC = &PPC::G8RCRegClass; 6802741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel const TargetRegisterClass *RC = isPPC64 ? G8RC : GPRC; 6812741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel 68299f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned CountReg; 68399f823f94374917174f96a7689955b8463db6816Hal Finkel if (TripCount->isReg()) { 68499f823f94374917174f96a7689955b8463db6816Hal Finkel // Create a copy of the loop count register. 6852741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel const TargetRegisterClass *SrcRC = 68699f823f94374917174f96a7689955b8463db6816Hal Finkel MF->getRegInfo().getRegClass(TripCount->getReg()); 68799f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg = MF->getRegInfo().createVirtualRegister(RC); 6882741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel unsigned CopyOp = (isPPC64 && SrcRC == GPRC) ? 6892741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel (unsigned) PPC::EXTSW_32_64 : 6902741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel (unsigned) TargetOpcode::COPY; 69199f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 6922741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel TII->get(CopyOp), CountReg).addReg(TripCount->getReg()); 69399f823f94374917174f96a7689955b8463db6816Hal Finkel if (TripCount->isNeg()) { 69499f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned CountReg1 = CountReg; 69599f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg = MF->getRegInfo().createVirtualRegister(RC); 69699f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 69799f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(isPPC64 ? PPC::NEG8 : PPC::NEG), 69899f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg).addReg(CountReg1); 69999f823f94374917174f96a7689955b8463db6816Hal Finkel } 70099f823f94374917174f96a7689955b8463db6816Hal Finkel } else { 70199f823f94374917174f96a7689955b8463db6816Hal Finkel assert(TripCount->isImm() && "Expecting immedate vaule for trip count"); 70299f823f94374917174f96a7689955b8463db6816Hal Finkel // Put the trip count in a register for transfer into the count register. 70399f823f94374917174f96a7689955b8463db6816Hal Finkel 70499f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t CountImm = TripCount->getImm(); 7059887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel if (TripCount->isNeg()) 7069887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel CountImm = -CountImm; 70799f823f94374917174f96a7689955b8463db6816Hal Finkel 70899f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg = MF->getRegInfo().createVirtualRegister(RC); 7099887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel if (abs64(CountImm) > 0x7FFF) { 71099f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 71199f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(isPPC64 ? PPC::LIS8 : PPC::LIS), 7129887ec31e630ede8541dee1d90c44a1efb63c417Hal Finkel CountReg).addImm((CountImm >> 16) & 0xFFFF); 71399f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned CountReg1 = CountReg; 71499f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg = MF->getRegInfo().createVirtualRegister(RC); 71599f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 71699f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(isPPC64 ? PPC::ORI8 : PPC::ORI), 71799f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg).addReg(CountReg1).addImm(CountImm & 0xFFFF); 71899f823f94374917174f96a7689955b8463db6816Hal Finkel } else { 71999f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 72099f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(isPPC64 ? PPC::LI8 : PPC::LI), 72199f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg).addImm(CountImm); 72299f823f94374917174f96a7689955b8463db6816Hal Finkel } 72399f823f94374917174f96a7689955b8463db6816Hal Finkel } 72499f823f94374917174f96a7689955b8463db6816Hal Finkel 72599f823f94374917174f96a7689955b8463db6816Hal Finkel // Add the mtctr instruction to the beginning of the loop. 72699f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 72799f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(isPPC64 ? PPC::MTCTR8 : PPC::MTCTR)).addReg(CountReg, 72899f823f94374917174f96a7689955b8463db6816Hal Finkel TripCount->isImm() ? RegState::Kill : 0); 72999f823f94374917174f96a7689955b8463db6816Hal Finkel 73099f823f94374917174f96a7689955b8463db6816Hal Finkel // Make sure the loop start always has a reference in the CFG. We need to 73199f823f94374917174f96a7689955b8463db6816Hal Finkel // create a BlockAddress operand to get this mechanism to work both the 73299f823f94374917174f96a7689955b8463db6816Hal Finkel // MachineBasicBlock and BasicBlock objects need the flag set. 73399f823f94374917174f96a7689955b8463db6816Hal Finkel LoopStart->setHasAddressTaken(); 73499f823f94374917174f96a7689955b8463db6816Hal Finkel // This line is needed to set the hasAddressTaken flag on the BasicBlock 73599f823f94374917174f96a7689955b8463db6816Hal Finkel // object 73699f823f94374917174f96a7689955b8463db6816Hal Finkel BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock())); 73799f823f94374917174f96a7689955b8463db6816Hal Finkel 73899f823f94374917174f96a7689955b8463db6816Hal Finkel // Replace the loop branch with a bdnz instruction. 73999f823f94374917174f96a7689955b8463db6816Hal Finkel dl = LastI->getDebugLoc(); 74099f823f94374917174f96a7689955b8463db6816Hal Finkel const std::vector<MachineBasicBlock*> Blocks = L->getBlocks(); 74199f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 74299f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *MBB = Blocks[i]; 74399f823f94374917174f96a7689955b8463db6816Hal Finkel if (MBB != Preheader) 74499f823f94374917174f96a7689955b8463db6816Hal Finkel MBB->addLiveIn(isPPC64 ? PPC::CTR8 : PPC::CTR); 74599f823f94374917174f96a7689955b8463db6816Hal Finkel } 74699f823f94374917174f96a7689955b8463db6816Hal Finkel 74799f823f94374917174f96a7689955b8463db6816Hal Finkel // The loop ends with either: 74899f823f94374917174f96a7689955b8463db6816Hal Finkel // - a conditional branch followed by an unconditional branch, or 74999f823f94374917174f96a7689955b8463db6816Hal Finkel // - a conditional branch to the loop start. 75099f823f94374917174f96a7689955b8463db6816Hal Finkel assert(LastI->getOpcode() == PPC::BCC && 75199f823f94374917174f96a7689955b8463db6816Hal Finkel "loop end must start with a BCC instruction"); 75299f823f94374917174f96a7689955b8463db6816Hal Finkel // Either the BCC branches to the beginning of the loop, or it 75399f823f94374917174f96a7689955b8463db6816Hal Finkel // branches out of the loop and there is an unconditional branch 75499f823f94374917174f96a7689955b8463db6816Hal Finkel // to the start of the loop. 75599f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *BranchTarget = LastI->getOperand(2).getMBB(); 75699f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*LastMBB, LastI, dl, 75799f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get((BranchTarget == LoopStart) ? 75899f823f94374917174f96a7689955b8463db6816Hal Finkel (isPPC64 ? PPC::BDNZ8 : PPC::BDNZ) : 75999f823f94374917174f96a7689955b8463db6816Hal Finkel (isPPC64 ? PPC::BDZ8 : PPC::BDZ))).addMBB(BranchTarget); 76099f823f94374917174f96a7689955b8463db6816Hal Finkel 76199f823f94374917174f96a7689955b8463db6816Hal Finkel // Conditional branch; just delete it. 7622741d2cfdff89e45c6b98cd520d5cd3fe97829adHal Finkel DEBUG(dbgs() << "Removing old branch: " << *LastI); 76399f823f94374917174f96a7689955b8463db6816Hal Finkel LastMBB->erase(LastI); 76499f823f94374917174f96a7689955b8463db6816Hal Finkel 76599f823f94374917174f96a7689955b8463db6816Hal Finkel delete TripCount; 76699f823f94374917174f96a7689955b8463db6816Hal Finkel 76799f823f94374917174f96a7689955b8463db6816Hal Finkel // The induction operation (add) and the comparison (cmpwi) may now be 76899f823f94374917174f96a7689955b8463db6816Hal Finkel // unneeded. If these are unneeded, then remove them. 76999f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0; i < OldInsts.size(); ++i) 77099f823f94374917174f96a7689955b8463db6816Hal Finkel removeIfDead(OldInsts[i]); 77199f823f94374917174f96a7689955b8463db6816Hal Finkel 77299f823f94374917174f96a7689955b8463db6816Hal Finkel ++NumCTRLoops; 77399f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 77499f823f94374917174f96a7689955b8463db6816Hal Finkel} 77599f823f94374917174f96a7689955b8463db6816Hal Finkel 776