PPCCTRLoops.cpp revision 99f823f94374917174f96a7689955b8463db6816
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" 3499f823f94374917174f96a7689955b8463db6816Hal Finkel#include "PPCTargetMachine.h" 3599f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/Constants.h" 3699f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/PassSupport.h" 3799f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/ADT/DenseMap.h" 3899f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/ADT/Statistic.h" 3999f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/Passes.h" 4099f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineDominators.h" 4199f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineFunction.h" 4299f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineFunctionPass.h" 4399f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineInstrBuilder.h" 4499f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineLoopInfo.h" 4599f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/MachineRegisterInfo.h" 4699f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/CodeGen/RegisterScavenging.h" 4799f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/Support/Debug.h" 4899f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/Support/raw_ostream.h" 4999f823f94374917174f96a7689955b8463db6816Hal Finkel#include "llvm/Target/TargetInstrInfo.h" 5099f823f94374917174f96a7689955b8463db6816Hal Finkel#include <algorithm> 5199f823f94374917174f96a7689955b8463db6816Hal Finkel 5299f823f94374917174f96a7689955b8463db6816Hal Finkelusing namespace llvm; 5399f823f94374917174f96a7689955b8463db6816Hal Finkel 5499f823f94374917174f96a7689955b8463db6816Hal FinkelSTATISTIC(NumCTRLoops, "Number of loops converted to CTR loops"); 5599f823f94374917174f96a7689955b8463db6816Hal Finkel 5699f823f94374917174f96a7689955b8463db6816Hal Finkelnamespace { 5799f823f94374917174f96a7689955b8463db6816Hal Finkel class CountValue; 5899f823f94374917174f96a7689955b8463db6816Hal Finkel struct PPCCTRLoops : public MachineFunctionPass { 5999f823f94374917174f96a7689955b8463db6816Hal Finkel MachineLoopInfo *MLI; 6099f823f94374917174f96a7689955b8463db6816Hal Finkel MachineRegisterInfo *MRI; 6199f823f94374917174f96a7689955b8463db6816Hal Finkel const TargetInstrInfo *TII; 6299f823f94374917174f96a7689955b8463db6816Hal Finkel 6399f823f94374917174f96a7689955b8463db6816Hal Finkel public: 6499f823f94374917174f96a7689955b8463db6816Hal Finkel static char ID; // Pass identification, replacement for typeid 6599f823f94374917174f96a7689955b8463db6816Hal Finkel 6699f823f94374917174f96a7689955b8463db6816Hal Finkel PPCCTRLoops() : MachineFunctionPass(ID) {} 6799f823f94374917174f96a7689955b8463db6816Hal Finkel 6899f823f94374917174f96a7689955b8463db6816Hal Finkel virtual bool runOnMachineFunction(MachineFunction &MF); 6999f823f94374917174f96a7689955b8463db6816Hal Finkel 7099f823f94374917174f96a7689955b8463db6816Hal Finkel const char *getPassName() const { return "PPC CTR Loops"; } 7199f823f94374917174f96a7689955b8463db6816Hal Finkel 7299f823f94374917174f96a7689955b8463db6816Hal Finkel virtual void getAnalysisUsage(AnalysisUsage &AU) const { 7399f823f94374917174f96a7689955b8463db6816Hal Finkel AU.setPreservesCFG(); 7499f823f94374917174f96a7689955b8463db6816Hal Finkel AU.addRequired<MachineDominatorTree>(); 7599f823f94374917174f96a7689955b8463db6816Hal Finkel AU.addPreserved<MachineDominatorTree>(); 7699f823f94374917174f96a7689955b8463db6816Hal Finkel AU.addRequired<MachineLoopInfo>(); 7799f823f94374917174f96a7689955b8463db6816Hal Finkel AU.addPreserved<MachineLoopInfo>(); 7899f823f94374917174f96a7689955b8463db6816Hal Finkel MachineFunctionPass::getAnalysisUsage(AU); 7999f823f94374917174f96a7689955b8463db6816Hal Finkel } 8099f823f94374917174f96a7689955b8463db6816Hal Finkel 8199f823f94374917174f96a7689955b8463db6816Hal Finkel private: 8299f823f94374917174f96a7689955b8463db6816Hal Finkel /// getCanonicalInductionVariable - Check to see if the loop has a canonical 8399f823f94374917174f96a7689955b8463db6816Hal Finkel /// induction variable. 8499f823f94374917174f96a7689955b8463db6816Hal Finkel /// Should be defined in MachineLoop. Based upon version in class Loop. 8599f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *getCanonicalInductionVariable(MachineLoop *L, 8699f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *&IOp) const; 8799f823f94374917174f96a7689955b8463db6816Hal Finkel 8899f823f94374917174f96a7689955b8463db6816Hal Finkel /// getTripCount - Return a loop-invariant LLVM register indicating the 8999f823f94374917174f96a7689955b8463db6816Hal Finkel /// number of times the loop will be executed. If the trip-count cannot 9099f823f94374917174f96a7689955b8463db6816Hal Finkel /// be determined, this return null. 9199f823f94374917174f96a7689955b8463db6816Hal Finkel CountValue *getTripCount(MachineLoop *L, bool &WordCmp, 9299f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 2> &OldInsts) const; 9399f823f94374917174f96a7689955b8463db6816Hal Finkel 9499f823f94374917174f96a7689955b8463db6816Hal Finkel /// isInductionOperation - Return true if the instruction matches the 9599f823f94374917174f96a7689955b8463db6816Hal Finkel /// pattern for an opertion that defines an induction variable. 9699f823f94374917174f96a7689955b8463db6816Hal Finkel bool isInductionOperation(const MachineInstr *MI, unsigned IVReg) const; 9799f823f94374917174f96a7689955b8463db6816Hal Finkel 9899f823f94374917174f96a7689955b8463db6816Hal Finkel /// isInvalidOperation - Return true if the instruction is not valid within 9999f823f94374917174f96a7689955b8463db6816Hal Finkel /// a CTR loop. 10099f823f94374917174f96a7689955b8463db6816Hal Finkel bool isInvalidLoopOperation(const MachineInstr *MI) const; 10199f823f94374917174f96a7689955b8463db6816Hal Finkel 10299f823f94374917174f96a7689955b8463db6816Hal Finkel /// containsInavlidInstruction - Return true if the loop contains an 10399f823f94374917174f96a7689955b8463db6816Hal Finkel /// instruction that inhibits using the CTR loop. 10499f823f94374917174f96a7689955b8463db6816Hal Finkel bool containsInvalidInstruction(MachineLoop *L) const; 10599f823f94374917174f96a7689955b8463db6816Hal Finkel 10699f823f94374917174f96a7689955b8463db6816Hal Finkel /// converToCTRLoop - Given a loop, check if we can convert it to a 10799f823f94374917174f96a7689955b8463db6816Hal Finkel /// CTR loop. If so, then perform the conversion and return true. 10899f823f94374917174f96a7689955b8463db6816Hal Finkel bool convertToCTRLoop(MachineLoop *L); 10999f823f94374917174f96a7689955b8463db6816Hal Finkel 11099f823f94374917174f96a7689955b8463db6816Hal Finkel /// isDead - Return true if the instruction is now dead. 11199f823f94374917174f96a7689955b8463db6816Hal Finkel bool isDead(const MachineInstr *MI, 11299f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 1> &DeadPhis) const; 11399f823f94374917174f96a7689955b8463db6816Hal Finkel 11499f823f94374917174f96a7689955b8463db6816Hal Finkel /// removeIfDead - Remove the instruction if it is now dead. 11599f823f94374917174f96a7689955b8463db6816Hal Finkel void removeIfDead(MachineInstr *MI); 11699f823f94374917174f96a7689955b8463db6816Hal Finkel }; 11799f823f94374917174f96a7689955b8463db6816Hal Finkel 11899f823f94374917174f96a7689955b8463db6816Hal Finkel char PPCCTRLoops::ID = 0; 11999f823f94374917174f96a7689955b8463db6816Hal Finkel 12099f823f94374917174f96a7689955b8463db6816Hal Finkel 12199f823f94374917174f96a7689955b8463db6816Hal Finkel // CountValue class - Abstraction for a trip count of a loop. A 12299f823f94374917174f96a7689955b8463db6816Hal Finkel // smaller vesrsion of the MachineOperand class without the concerns 12399f823f94374917174f96a7689955b8463db6816Hal Finkel // of changing the operand representation. 12499f823f94374917174f96a7689955b8463db6816Hal Finkel class CountValue { 12599f823f94374917174f96a7689955b8463db6816Hal Finkel public: 12699f823f94374917174f96a7689955b8463db6816Hal Finkel enum CountValueType { 12799f823f94374917174f96a7689955b8463db6816Hal Finkel CV_Register, 12899f823f94374917174f96a7689955b8463db6816Hal Finkel CV_Immediate 12999f823f94374917174f96a7689955b8463db6816Hal Finkel }; 13099f823f94374917174f96a7689955b8463db6816Hal Finkel private: 13199f823f94374917174f96a7689955b8463db6816Hal Finkel CountValueType Kind; 13299f823f94374917174f96a7689955b8463db6816Hal Finkel union Values { 13399f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned RegNum; 13499f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t ImmVal; 13599f823f94374917174f96a7689955b8463db6816Hal Finkel Values(unsigned r) : RegNum(r) {} 13699f823f94374917174f96a7689955b8463db6816Hal Finkel Values(int64_t i) : ImmVal(i) {} 13799f823f94374917174f96a7689955b8463db6816Hal Finkel } Contents; 13899f823f94374917174f96a7689955b8463db6816Hal Finkel bool isNegative; 13999f823f94374917174f96a7689955b8463db6816Hal Finkel 14099f823f94374917174f96a7689955b8463db6816Hal Finkel public: 14199f823f94374917174f96a7689955b8463db6816Hal Finkel CountValue(unsigned r, bool neg) : Kind(CV_Register), Contents(r), 14299f823f94374917174f96a7689955b8463db6816Hal Finkel isNegative(neg) {} 14399f823f94374917174f96a7689955b8463db6816Hal Finkel explicit CountValue(int64_t i) : Kind(CV_Immediate), Contents(i), 14499f823f94374917174f96a7689955b8463db6816Hal Finkel isNegative(i < 0) {} 14599f823f94374917174f96a7689955b8463db6816Hal Finkel CountValueType getType() const { return Kind; } 14699f823f94374917174f96a7689955b8463db6816Hal Finkel bool isReg() const { return Kind == CV_Register; } 14799f823f94374917174f96a7689955b8463db6816Hal Finkel bool isImm() const { return Kind == CV_Immediate; } 14899f823f94374917174f96a7689955b8463db6816Hal Finkel bool isNeg() const { return isNegative; } 14999f823f94374917174f96a7689955b8463db6816Hal Finkel 15099f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned getReg() const { 15199f823f94374917174f96a7689955b8463db6816Hal Finkel assert(isReg() && "Wrong CountValue accessor"); 15299f823f94374917174f96a7689955b8463db6816Hal Finkel return Contents.RegNum; 15399f823f94374917174f96a7689955b8463db6816Hal Finkel } 15499f823f94374917174f96a7689955b8463db6816Hal Finkel void setReg(unsigned Val) { 15599f823f94374917174f96a7689955b8463db6816Hal Finkel Contents.RegNum = Val; 15699f823f94374917174f96a7689955b8463db6816Hal Finkel } 15799f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t getImm() const { 15899f823f94374917174f96a7689955b8463db6816Hal Finkel assert(isImm() && "Wrong CountValue accessor"); 15999f823f94374917174f96a7689955b8463db6816Hal Finkel if (isNegative) { 16099f823f94374917174f96a7689955b8463db6816Hal Finkel return -Contents.ImmVal; 16199f823f94374917174f96a7689955b8463db6816Hal Finkel } 16299f823f94374917174f96a7689955b8463db6816Hal Finkel return Contents.ImmVal; 16399f823f94374917174f96a7689955b8463db6816Hal Finkel } 16499f823f94374917174f96a7689955b8463db6816Hal Finkel void setImm(int64_t Val) { 16599f823f94374917174f96a7689955b8463db6816Hal Finkel Contents.ImmVal = Val; 16699f823f94374917174f96a7689955b8463db6816Hal Finkel } 16799f823f94374917174f96a7689955b8463db6816Hal Finkel 16899f823f94374917174f96a7689955b8463db6816Hal Finkel void print(raw_ostream &OS, const TargetMachine *TM = 0) const { 16999f823f94374917174f96a7689955b8463db6816Hal Finkel if (isReg()) { OS << PrintReg(getReg()); } 17099f823f94374917174f96a7689955b8463db6816Hal Finkel if (isImm()) { OS << getImm(); } 17199f823f94374917174f96a7689955b8463db6816Hal Finkel } 17299f823f94374917174f96a7689955b8463db6816Hal Finkel }; 17399f823f94374917174f96a7689955b8463db6816Hal Finkel} // end anonymous namespace 17499f823f94374917174f96a7689955b8463db6816Hal Finkel 17599f823f94374917174f96a7689955b8463db6816Hal Finkel 17699f823f94374917174f96a7689955b8463db6816Hal Finkel/// isCompareEquals - Returns true if the instruction is a compare equals 17799f823f94374917174f96a7689955b8463db6816Hal Finkel/// instruction with an immediate operand. 17899f823f94374917174f96a7689955b8463db6816Hal Finkelstatic bool isCompareEqualsImm(const MachineInstr *MI, bool &WordCmp) { 17999f823f94374917174f96a7689955b8463db6816Hal Finkel if (MI->getOpcode() == PPC::CMPWI || MI->getOpcode() == PPC::CMPLWI) { 18099f823f94374917174f96a7689955b8463db6816Hal Finkel WordCmp = true; 18199f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 18299f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (MI->getOpcode() == PPC::CMPDI || MI->getOpcode() == PPC::CMPLDI) { 18399f823f94374917174f96a7689955b8463db6816Hal Finkel WordCmp = false; 18499f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 18599f823f94374917174f96a7689955b8463db6816Hal Finkel } 18699f823f94374917174f96a7689955b8463db6816Hal Finkel 18799f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 18899f823f94374917174f96a7689955b8463db6816Hal Finkel} 18999f823f94374917174f96a7689955b8463db6816Hal Finkel 19099f823f94374917174f96a7689955b8463db6816Hal Finkel 19199f823f94374917174f96a7689955b8463db6816Hal Finkel/// createPPCCTRLoops - Factory for creating 19299f823f94374917174f96a7689955b8463db6816Hal Finkel/// the CTR loop phase. 19399f823f94374917174f96a7689955b8463db6816Hal FinkelFunctionPass *llvm::createPPCCTRLoops() { 19499f823f94374917174f96a7689955b8463db6816Hal Finkel return new PPCCTRLoops(); 19599f823f94374917174f96a7689955b8463db6816Hal Finkel} 19699f823f94374917174f96a7689955b8463db6816Hal Finkel 19799f823f94374917174f96a7689955b8463db6816Hal Finkel 19899f823f94374917174f96a7689955b8463db6816Hal Finkelbool PPCCTRLoops::runOnMachineFunction(MachineFunction &MF) { 19999f823f94374917174f96a7689955b8463db6816Hal Finkel DEBUG(dbgs() << "********* PPC CTR Loops *********\n"); 20099f823f94374917174f96a7689955b8463db6816Hal Finkel 20199f823f94374917174f96a7689955b8463db6816Hal Finkel bool Changed = false; 20299f823f94374917174f96a7689955b8463db6816Hal Finkel 20399f823f94374917174f96a7689955b8463db6816Hal Finkel // get the loop information 20499f823f94374917174f96a7689955b8463db6816Hal Finkel MLI = &getAnalysis<MachineLoopInfo>(); 20599f823f94374917174f96a7689955b8463db6816Hal Finkel // get the register information 20699f823f94374917174f96a7689955b8463db6816Hal Finkel MRI = &MF.getRegInfo(); 20799f823f94374917174f96a7689955b8463db6816Hal Finkel // the target specific instructio info. 20899f823f94374917174f96a7689955b8463db6816Hal Finkel TII = MF.getTarget().getInstrInfo(); 20999f823f94374917174f96a7689955b8463db6816Hal Finkel 21099f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); 21199f823f94374917174f96a7689955b8463db6816Hal Finkel I != E; ++I) { 21299f823f94374917174f96a7689955b8463db6816Hal Finkel MachineLoop *L = *I; 21399f823f94374917174f96a7689955b8463db6816Hal Finkel if (!L->getParentLoop()) { 21499f823f94374917174f96a7689955b8463db6816Hal Finkel Changed |= convertToCTRLoop(L); 21599f823f94374917174f96a7689955b8463db6816Hal Finkel } 21699f823f94374917174f96a7689955b8463db6816Hal Finkel } 21799f823f94374917174f96a7689955b8463db6816Hal Finkel 21899f823f94374917174f96a7689955b8463db6816Hal Finkel return Changed; 21999f823f94374917174f96a7689955b8463db6816Hal Finkel} 22099f823f94374917174f96a7689955b8463db6816Hal Finkel 22199f823f94374917174f96a7689955b8463db6816Hal Finkel/// getCanonicalInductionVariable - Check to see if the loop has a canonical 22299f823f94374917174f96a7689955b8463db6816Hal Finkel/// induction variable. We check for a simple recurrence pattern - an 22399f823f94374917174f96a7689955b8463db6816Hal Finkel/// integer recurrence that decrements by one each time through the loop and 22499f823f94374917174f96a7689955b8463db6816Hal Finkel/// ends at zero. If so, return the phi node that corresponds to it. 22599f823f94374917174f96a7689955b8463db6816Hal Finkel/// 22699f823f94374917174f96a7689955b8463db6816Hal Finkel/// Based upon the similar code in LoopInfo except this code is specific to 22799f823f94374917174f96a7689955b8463db6816Hal Finkel/// the machine. 22899f823f94374917174f96a7689955b8463db6816Hal Finkel/// This method assumes that the IndVarSimplify pass has been run by 'opt'. 22999f823f94374917174f96a7689955b8463db6816Hal Finkel/// 23099f823f94374917174f96a7689955b8463db6816Hal FinkelMachineInstr 23199f823f94374917174f96a7689955b8463db6816Hal Finkel*PPCCTRLoops::getCanonicalInductionVariable(MachineLoop *L, 23299f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *&IOp) const { 23399f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *TopMBB = L->getTopBlock(); 23499f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(); 23599f823f94374917174f96a7689955b8463db6816Hal Finkel assert(PI != TopMBB->pred_end() && 23699f823f94374917174f96a7689955b8463db6816Hal Finkel "Loop must have more than one incoming edge!"); 23799f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *Backedge = *PI++; 23899f823f94374917174f96a7689955b8463db6816Hal Finkel if (PI == TopMBB->pred_end()) return 0; // dead loop 23999f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *Incoming = *PI++; 24099f823f94374917174f96a7689955b8463db6816Hal Finkel if (PI != TopMBB->pred_end()) return 0; // multiple backedges? 24199f823f94374917174f96a7689955b8463db6816Hal Finkel 24299f823f94374917174f96a7689955b8463db6816Hal Finkel // make sure there is one incoming and one backedge and determine which 24399f823f94374917174f96a7689955b8463db6816Hal Finkel // is which. 24499f823f94374917174f96a7689955b8463db6816Hal Finkel if (L->contains(Incoming)) { 24599f823f94374917174f96a7689955b8463db6816Hal Finkel if (L->contains(Backedge)) 24699f823f94374917174f96a7689955b8463db6816Hal Finkel return 0; 24799f823f94374917174f96a7689955b8463db6816Hal Finkel std::swap(Incoming, Backedge); 24899f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (!L->contains(Backedge)) 24999f823f94374917174f96a7689955b8463db6816Hal Finkel return 0; 25099f823f94374917174f96a7689955b8463db6816Hal Finkel 25199f823f94374917174f96a7689955b8463db6816Hal Finkel // Loop over all of the PHI nodes, looking for a canonical induction variable: 25299f823f94374917174f96a7689955b8463db6816Hal Finkel // - The PHI node is "reg1 = PHI reg2, BB1, reg3, BB2". 25399f823f94374917174f96a7689955b8463db6816Hal Finkel // - The recurrence comes from the backedge. 25499f823f94374917174f96a7689955b8463db6816Hal Finkel // - the definition is an induction operatio.n 25599f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineBasicBlock::iterator I = TopMBB->begin(), E = TopMBB->end(); 25699f823f94374917174f96a7689955b8463db6816Hal Finkel I != E && I->isPHI(); ++I) { 25799f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *MPhi = &*I; 25899f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned DefReg = MPhi->getOperand(0).getReg(); 25999f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) { 26099f823f94374917174f96a7689955b8463db6816Hal Finkel // Check each operand for the value from the backedge. 26199f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *MBB = MPhi->getOperand(i+1).getMBB(); 26299f823f94374917174f96a7689955b8463db6816Hal Finkel if (L->contains(MBB)) { // operands comes from the backedge 26399f823f94374917174f96a7689955b8463db6816Hal Finkel // Check if the definition is an induction operation. 26499f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *DI = MRI->getVRegDef(MPhi->getOperand(i).getReg()); 26599f823f94374917174f96a7689955b8463db6816Hal Finkel if (isInductionOperation(DI, DefReg)) { 26699f823f94374917174f96a7689955b8463db6816Hal Finkel IOp = DI; 26799f823f94374917174f96a7689955b8463db6816Hal Finkel return MPhi; 26899f823f94374917174f96a7689955b8463db6816Hal Finkel } 26999f823f94374917174f96a7689955b8463db6816Hal Finkel } 27099f823f94374917174f96a7689955b8463db6816Hal Finkel } 27199f823f94374917174f96a7689955b8463db6816Hal Finkel } 27299f823f94374917174f96a7689955b8463db6816Hal Finkel return 0; 27399f823f94374917174f96a7689955b8463db6816Hal Finkel} 27499f823f94374917174f96a7689955b8463db6816Hal Finkel 27599f823f94374917174f96a7689955b8463db6816Hal Finkel/// getTripCount - Return a loop-invariant LLVM value indicating the 27699f823f94374917174f96a7689955b8463db6816Hal Finkel/// number of times the loop will be executed. The trip count can 27799f823f94374917174f96a7689955b8463db6816Hal Finkel/// be either a register or a constant value. If the trip-count 27899f823f94374917174f96a7689955b8463db6816Hal Finkel/// cannot be determined, this returns null. 27999f823f94374917174f96a7689955b8463db6816Hal Finkel/// 28099f823f94374917174f96a7689955b8463db6816Hal Finkel/// We find the trip count from the phi instruction that defines the 28199f823f94374917174f96a7689955b8463db6816Hal Finkel/// induction variable. We follow the links to the CMP instruction 28299f823f94374917174f96a7689955b8463db6816Hal Finkel/// to get the trip count. 28399f823f94374917174f96a7689955b8463db6816Hal Finkel/// 28499f823f94374917174f96a7689955b8463db6816Hal Finkel/// Based upon getTripCount in LoopInfo. 28599f823f94374917174f96a7689955b8463db6816Hal Finkel/// 28699f823f94374917174f96a7689955b8463db6816Hal FinkelCountValue *PPCCTRLoops::getTripCount(MachineLoop *L, bool &WordCmp, 28799f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 2> &OldInsts) const { 28899f823f94374917174f96a7689955b8463db6816Hal Finkel // Check that the loop has a induction variable. 28999f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *IOp; 29099f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *IV_Inst = getCanonicalInductionVariable(L, IOp); 29199f823f94374917174f96a7689955b8463db6816Hal Finkel if (IV_Inst == 0) return 0; 29299f823f94374917174f96a7689955b8463db6816Hal Finkel 29399f823f94374917174f96a7689955b8463db6816Hal Finkel // Canonical loops will end with a 'cmpwi/cmpdi cr, IV, Imm', 29499f823f94374917174f96a7689955b8463db6816Hal Finkel // if Imm is 0, get the count from the PHI opnd 29599f823f94374917174f96a7689955b8463db6816Hal Finkel // if Imm is -M, than M is the count 29699f823f94374917174f96a7689955b8463db6816Hal Finkel // Otherwise, Imm is the count 29799f823f94374917174f96a7689955b8463db6816Hal Finkel MachineOperand *IV_Opnd; 29899f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineOperand *InitialValue; 29999f823f94374917174f96a7689955b8463db6816Hal Finkel if (!L->contains(IV_Inst->getOperand(2).getMBB())) { 30099f823f94374917174f96a7689955b8463db6816Hal Finkel InitialValue = &IV_Inst->getOperand(1); 30199f823f94374917174f96a7689955b8463db6816Hal Finkel IV_Opnd = &IV_Inst->getOperand(3); 30299f823f94374917174f96a7689955b8463db6816Hal Finkel } else { 30399f823f94374917174f96a7689955b8463db6816Hal Finkel InitialValue = &IV_Inst->getOperand(3); 30499f823f94374917174f96a7689955b8463db6816Hal Finkel IV_Opnd = &IV_Inst->getOperand(1); 30599f823f94374917174f96a7689955b8463db6816Hal Finkel } 30699f823f94374917174f96a7689955b8463db6816Hal Finkel 30799f823f94374917174f96a7689955b8463db6816Hal Finkel // Look for the cmp instruction to determine if we 30899f823f94374917174f96a7689955b8463db6816Hal Finkel // can get a useful trip count. The trip count can 30999f823f94374917174f96a7689955b8463db6816Hal Finkel // be either a register or an immediate. The location 31099f823f94374917174f96a7689955b8463db6816Hal Finkel // of the value depends upon the type (reg or imm). 31199f823f94374917174f96a7689955b8463db6816Hal Finkel while ((IV_Opnd = IV_Opnd->getNextOperandForReg())) { 31299f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *MI = IV_Opnd->getParent(); 31399f823f94374917174f96a7689955b8463db6816Hal Finkel if (L->contains(MI) && isCompareEqualsImm(MI, WordCmp)) { 31499f823f94374917174f96a7689955b8463db6816Hal Finkel OldInsts.push_back(MI); 31599f823f94374917174f96a7689955b8463db6816Hal Finkel OldInsts.push_back(IOp); 31699f823f94374917174f96a7689955b8463db6816Hal Finkel 31799f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineOperand &MO = MI->getOperand(2); 31899f823f94374917174f96a7689955b8463db6816Hal Finkel assert(MO.isImm() && "IV Cmp Operand should be an immediate"); 31999f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t ImmVal = MO.getImm(); 32099f823f94374917174f96a7689955b8463db6816Hal Finkel 32199f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineInstr *IV_DefInstr = MRI->getVRegDef(IV_Opnd->getReg()); 32299f823f94374917174f96a7689955b8463db6816Hal Finkel assert(L->contains(IV_DefInstr->getParent()) && 32399f823f94374917174f96a7689955b8463db6816Hal Finkel "IV definition should occurs in loop"); 32499f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t iv_value = IV_DefInstr->getOperand(2).getImm(); 32599f823f94374917174f96a7689955b8463db6816Hal Finkel 32699f823f94374917174f96a7689955b8463db6816Hal Finkel if (ImmVal == 0) { 32799f823f94374917174f96a7689955b8463db6816Hal Finkel // Make sure the induction variable changes by one on each iteration. 32899f823f94374917174f96a7689955b8463db6816Hal Finkel if (iv_value != 1 && iv_value != -1) { 32999f823f94374917174f96a7689955b8463db6816Hal Finkel return 0; 33099f823f94374917174f96a7689955b8463db6816Hal Finkel } 33199f823f94374917174f96a7689955b8463db6816Hal Finkel return new CountValue(InitialValue->getReg(), iv_value > 0); 33299f823f94374917174f96a7689955b8463db6816Hal Finkel } else { 33399f823f94374917174f96a7689955b8463db6816Hal Finkel assert(InitialValue->isReg() && "Expecting register for init value"); 33499f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineInstr *DefInstr = MRI->getVRegDef(InitialValue->getReg()); 33599f823f94374917174f96a7689955b8463db6816Hal Finkel 33699f823f94374917174f96a7689955b8463db6816Hal Finkel // Here we need to look for an immediate load (an li or lis/ori pair). 33799f823f94374917174f96a7689955b8463db6816Hal Finkel if (DefInstr && (DefInstr->getOpcode() == PPC::ORI8 || 33899f823f94374917174f96a7689955b8463db6816Hal Finkel DefInstr->getOpcode() == PPC::ORI)) { 33999f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t start = DefInstr->getOperand(2).getImm(); 34099f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineInstr *DefInstr2 = 34199f823f94374917174f96a7689955b8463db6816Hal Finkel MRI->getVRegDef(DefInstr->getOperand(0).getReg()); 34299f823f94374917174f96a7689955b8463db6816Hal Finkel if (DefInstr2 && (DefInstr2->getOpcode() == PPC::LIS8 || 34399f823f94374917174f96a7689955b8463db6816Hal Finkel DefInstr2->getOpcode() == PPC::LIS)) { 34499f823f94374917174f96a7689955b8463db6816Hal Finkel start |= DefInstr2->getOperand(1).getImm() << 16; 34599f823f94374917174f96a7689955b8463db6816Hal Finkel 34699f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t count = ImmVal - start; 34799f823f94374917174f96a7689955b8463db6816Hal Finkel if ((count % iv_value) != 0) { 34899f823f94374917174f96a7689955b8463db6816Hal Finkel return 0; 34999f823f94374917174f96a7689955b8463db6816Hal Finkel } 35099f823f94374917174f96a7689955b8463db6816Hal Finkel return new CountValue(count/iv_value); 35199f823f94374917174f96a7689955b8463db6816Hal Finkel } 35299f823f94374917174f96a7689955b8463db6816Hal Finkel } else if (DefInstr && (DefInstr->getOpcode() == PPC::LI8 || 35399f823f94374917174f96a7689955b8463db6816Hal Finkel DefInstr->getOpcode() == PPC::LI)) { 35499f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t count = ImmVal - DefInstr->getOperand(1).getImm(); 35599f823f94374917174f96a7689955b8463db6816Hal Finkel if ((count % iv_value) != 0) { 35699f823f94374917174f96a7689955b8463db6816Hal Finkel return 0; 35799f823f94374917174f96a7689955b8463db6816Hal Finkel } 35899f823f94374917174f96a7689955b8463db6816Hal Finkel return new CountValue(count/iv_value); 35999f823f94374917174f96a7689955b8463db6816Hal Finkel } 36099f823f94374917174f96a7689955b8463db6816Hal Finkel } 36199f823f94374917174f96a7689955b8463db6816Hal Finkel } 36299f823f94374917174f96a7689955b8463db6816Hal Finkel } 36399f823f94374917174f96a7689955b8463db6816Hal Finkel return 0; 36499f823f94374917174f96a7689955b8463db6816Hal Finkel} 36599f823f94374917174f96a7689955b8463db6816Hal Finkel 36699f823f94374917174f96a7689955b8463db6816Hal Finkel/// isInductionOperation - return true if the operation is matches the 36799f823f94374917174f96a7689955b8463db6816Hal Finkel/// pattern that defines an induction variable: 36899f823f94374917174f96a7689955b8463db6816Hal Finkel/// addi iv, c 36999f823f94374917174f96a7689955b8463db6816Hal Finkel/// 37099f823f94374917174f96a7689955b8463db6816Hal Finkelbool 37199f823f94374917174f96a7689955b8463db6816Hal FinkelPPCCTRLoops::isInductionOperation(const MachineInstr *MI, 37299f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned IVReg) const { 37399f823f94374917174f96a7689955b8463db6816Hal Finkel return ((MI->getOpcode() == PPC::ADDI || MI->getOpcode() == PPC::ADDI8) && 37499f823f94374917174f96a7689955b8463db6816Hal Finkel MI->getOperand(1).getReg() == IVReg); 37599f823f94374917174f96a7689955b8463db6816Hal Finkel} 37699f823f94374917174f96a7689955b8463db6816Hal Finkel 37799f823f94374917174f96a7689955b8463db6816Hal Finkel/// isInvalidOperation - Return true if the operation is invalid within 37899f823f94374917174f96a7689955b8463db6816Hal Finkel/// CTR loop. 37999f823f94374917174f96a7689955b8463db6816Hal Finkelbool 38099f823f94374917174f96a7689955b8463db6816Hal FinkelPPCCTRLoops::isInvalidLoopOperation(const MachineInstr *MI) const { 38199f823f94374917174f96a7689955b8463db6816Hal Finkel 38299f823f94374917174f96a7689955b8463db6816Hal Finkel // call is not allowed because the callee may use a CTR loop 38399f823f94374917174f96a7689955b8463db6816Hal Finkel if (MI->getDesc().isCall()) { 38499f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 38599f823f94374917174f96a7689955b8463db6816Hal Finkel } 38699f823f94374917174f96a7689955b8463db6816Hal Finkel // check if the instruction defines a CTR loop register 38799f823f94374917174f96a7689955b8463db6816Hal Finkel // (this will also catch nested CTR loops) 38899f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 38999f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineOperand &MO = MI->getOperand(i); 39099f823f94374917174f96a7689955b8463db6816Hal Finkel if (MO.isReg() && MO.isDef() && 39199f823f94374917174f96a7689955b8463db6816Hal Finkel (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8)) { 39299f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 39399f823f94374917174f96a7689955b8463db6816Hal Finkel } 39499f823f94374917174f96a7689955b8463db6816Hal Finkel } 39599f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 39699f823f94374917174f96a7689955b8463db6816Hal Finkel} 39799f823f94374917174f96a7689955b8463db6816Hal Finkel 39899f823f94374917174f96a7689955b8463db6816Hal Finkel/// containsInvalidInstruction - Return true if the loop contains 39999f823f94374917174f96a7689955b8463db6816Hal Finkel/// an instruction that inhibits the use of the CTR loop function. 40099f823f94374917174f96a7689955b8463db6816Hal Finkel/// 40199f823f94374917174f96a7689955b8463db6816Hal Finkelbool PPCCTRLoops::containsInvalidInstruction(MachineLoop *L) const { 40299f823f94374917174f96a7689955b8463db6816Hal Finkel const std::vector<MachineBasicBlock*> Blocks = L->getBlocks(); 40399f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 40499f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *MBB = Blocks[i]; 40599f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineBasicBlock::iterator 40699f823f94374917174f96a7689955b8463db6816Hal Finkel MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) { 40799f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineInstr *MI = &*MII; 40899f823f94374917174f96a7689955b8463db6816Hal Finkel if (isInvalidLoopOperation(MI)) { 40999f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 41099f823f94374917174f96a7689955b8463db6816Hal Finkel } 41199f823f94374917174f96a7689955b8463db6816Hal Finkel } 41299f823f94374917174f96a7689955b8463db6816Hal Finkel } 41399f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 41499f823f94374917174f96a7689955b8463db6816Hal Finkel} 41599f823f94374917174f96a7689955b8463db6816Hal Finkel 41699f823f94374917174f96a7689955b8463db6816Hal Finkel/// isDead returns true if the instruction is dead 41799f823f94374917174f96a7689955b8463db6816Hal Finkel/// (this was essentially copied from DeadMachineInstructionElim::isDead, but 41899f823f94374917174f96a7689955b8463db6816Hal Finkel/// with special cases for inline asm, physical registers and instructions with 41999f823f94374917174f96a7689955b8463db6816Hal Finkel/// side effects removed) 42099f823f94374917174f96a7689955b8463db6816Hal Finkelbool PPCCTRLoops::isDead(const MachineInstr *MI, 42199f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 1> &DeadPhis) const { 42299f823f94374917174f96a7689955b8463db6816Hal Finkel // Examine each operand. 42399f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 42499f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineOperand &MO = MI->getOperand(i); 42599f823f94374917174f96a7689955b8463db6816Hal Finkel if (MO.isReg() && MO.isDef()) { 42699f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned Reg = MO.getReg(); 42799f823f94374917174f96a7689955b8463db6816Hal Finkel if (!MRI->use_nodbg_empty(Reg)) { 42899f823f94374917174f96a7689955b8463db6816Hal Finkel // This instruction has users, but if the only user is the phi node for the 42999f823f94374917174f96a7689955b8463db6816Hal Finkel // parent block, and the only use of that phi node is this instruction, then 43099f823f94374917174f96a7689955b8463db6816Hal Finkel // this instruction is dead: both it (and the phi node) can be removed. 43199f823f94374917174f96a7689955b8463db6816Hal Finkel MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg); 43299f823f94374917174f96a7689955b8463db6816Hal Finkel if (llvm::next(I) == MRI->use_end() && 43399f823f94374917174f96a7689955b8463db6816Hal Finkel I.getOperand().getParent()->isPHI()) { 43499f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *OnePhi = I.getOperand().getParent(); 43599f823f94374917174f96a7689955b8463db6816Hal Finkel 43699f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) { 43799f823f94374917174f96a7689955b8463db6816Hal Finkel const MachineOperand &OPO = OnePhi->getOperand(j); 43899f823f94374917174f96a7689955b8463db6816Hal Finkel if (OPO.isReg() && OPO.isDef()) { 43999f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned OPReg = OPO.getReg(); 44099f823f94374917174f96a7689955b8463db6816Hal Finkel 44199f823f94374917174f96a7689955b8463db6816Hal Finkel MachineRegisterInfo::use_iterator nextJ; 44299f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineRegisterInfo::use_iterator J = MRI->use_begin(OPReg), 44399f823f94374917174f96a7689955b8463db6816Hal Finkel E = MRI->use_end(); J!=E; J=nextJ) { 44499f823f94374917174f96a7689955b8463db6816Hal Finkel nextJ = llvm::next(J); 44599f823f94374917174f96a7689955b8463db6816Hal Finkel MachineOperand& Use = J.getOperand(); 44699f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *UseMI = Use.getParent(); 44799f823f94374917174f96a7689955b8463db6816Hal Finkel 44899f823f94374917174f96a7689955b8463db6816Hal Finkel if (MI != UseMI) { 44999f823f94374917174f96a7689955b8463db6816Hal Finkel // The phi node has a user that is not MI, bail... 45099f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 45199f823f94374917174f96a7689955b8463db6816Hal Finkel } 45299f823f94374917174f96a7689955b8463db6816Hal Finkel } 45399f823f94374917174f96a7689955b8463db6816Hal Finkel } 45499f823f94374917174f96a7689955b8463db6816Hal Finkel } 45599f823f94374917174f96a7689955b8463db6816Hal Finkel 45699f823f94374917174f96a7689955b8463db6816Hal Finkel DeadPhis.push_back(OnePhi); 45799f823f94374917174f96a7689955b8463db6816Hal Finkel } else { 45899f823f94374917174f96a7689955b8463db6816Hal Finkel // This def has a non-debug use. Don't delete the instruction! 45999f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 46099f823f94374917174f96a7689955b8463db6816Hal Finkel } 46199f823f94374917174f96a7689955b8463db6816Hal Finkel } 46299f823f94374917174f96a7689955b8463db6816Hal Finkel } 46399f823f94374917174f96a7689955b8463db6816Hal Finkel } 46499f823f94374917174f96a7689955b8463db6816Hal Finkel 46599f823f94374917174f96a7689955b8463db6816Hal Finkel // If there are no defs with uses, the instruction is dead. 46699f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 46799f823f94374917174f96a7689955b8463db6816Hal Finkel} 46899f823f94374917174f96a7689955b8463db6816Hal Finkel 46999f823f94374917174f96a7689955b8463db6816Hal Finkelvoid PPCCTRLoops::removeIfDead(MachineInstr *MI) { 47099f823f94374917174f96a7689955b8463db6816Hal Finkel // This procedure was essentially copied from DeadMachineInstructionElim 47199f823f94374917174f96a7689955b8463db6816Hal Finkel 47299f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 1> DeadPhis; 47399f823f94374917174f96a7689955b8463db6816Hal Finkel if (isDead(MI, DeadPhis)) { 47499f823f94374917174f96a7689955b8463db6816Hal Finkel DEBUG(dbgs() << "CTR looping will remove: " << *MI); 47599f823f94374917174f96a7689955b8463db6816Hal Finkel 47699f823f94374917174f96a7689955b8463db6816Hal Finkel // It is possible that some DBG_VALUE instructions refer to this 47799f823f94374917174f96a7689955b8463db6816Hal Finkel // instruction. Examine each def operand for such references; 47899f823f94374917174f96a7689955b8463db6816Hal Finkel // if found, mark the DBG_VALUE as undef (but don't delete it). 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 continue; 48399f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned Reg = MO.getReg(); 48499f823f94374917174f96a7689955b8463db6816Hal Finkel MachineRegisterInfo::use_iterator nextI; 48599f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg), 48699f823f94374917174f96a7689955b8463db6816Hal Finkel E = MRI->use_end(); I!=E; I=nextI) { 48799f823f94374917174f96a7689955b8463db6816Hal Finkel nextI = llvm::next(I); // I is invalidated by the setReg 48899f823f94374917174f96a7689955b8463db6816Hal Finkel MachineOperand& Use = I.getOperand(); 48999f823f94374917174f96a7689955b8463db6816Hal Finkel MachineInstr *UseMI = Use.getParent(); 49099f823f94374917174f96a7689955b8463db6816Hal Finkel if (UseMI==MI) 49199f823f94374917174f96a7689955b8463db6816Hal Finkel continue; 49299f823f94374917174f96a7689955b8463db6816Hal Finkel if (Use.isDebug()) // this might also be a instr -> phi -> instr case 49399f823f94374917174f96a7689955b8463db6816Hal Finkel // which can also be removed. 49499f823f94374917174f96a7689955b8463db6816Hal Finkel UseMI->getOperand(0).setReg(0U); 49599f823f94374917174f96a7689955b8463db6816Hal Finkel } 49699f823f94374917174f96a7689955b8463db6816Hal Finkel } 49799f823f94374917174f96a7689955b8463db6816Hal Finkel 49899f823f94374917174f96a7689955b8463db6816Hal Finkel MI->eraseFromParent(); 49999f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0; i < DeadPhis.size(); ++i) { 50099f823f94374917174f96a7689955b8463db6816Hal Finkel DeadPhis[i]->eraseFromParent(); 50199f823f94374917174f96a7689955b8463db6816Hal Finkel } 50299f823f94374917174f96a7689955b8463db6816Hal Finkel } 50399f823f94374917174f96a7689955b8463db6816Hal Finkel} 50499f823f94374917174f96a7689955b8463db6816Hal Finkel 50599f823f94374917174f96a7689955b8463db6816Hal Finkel/// converToCTRLoop - check if the loop is a candidate for 50699f823f94374917174f96a7689955b8463db6816Hal Finkel/// converting to a CTR loop. If so, then perform the 50799f823f94374917174f96a7689955b8463db6816Hal Finkel/// transformation. 50899f823f94374917174f96a7689955b8463db6816Hal Finkel/// 50999f823f94374917174f96a7689955b8463db6816Hal Finkel/// This function works on innermost loops first. A loop can 51099f823f94374917174f96a7689955b8463db6816Hal Finkel/// be converted if it is a counting loop; either a register 51199f823f94374917174f96a7689955b8463db6816Hal Finkel/// value or an immediate. 51299f823f94374917174f96a7689955b8463db6816Hal Finkel/// 51399f823f94374917174f96a7689955b8463db6816Hal Finkel/// The code makes several assumptions about the representation 51499f823f94374917174f96a7689955b8463db6816Hal Finkel/// of the loop in llvm. 51599f823f94374917174f96a7689955b8463db6816Hal Finkelbool PPCCTRLoops::convertToCTRLoop(MachineLoop *L) { 51699f823f94374917174f96a7689955b8463db6816Hal Finkel bool Changed = false; 51799f823f94374917174f96a7689955b8463db6816Hal Finkel // Process nested loops first. 51899f823f94374917174f96a7689955b8463db6816Hal Finkel for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) { 51999f823f94374917174f96a7689955b8463db6816Hal Finkel Changed |= convertToCTRLoop(*I); 52099f823f94374917174f96a7689955b8463db6816Hal Finkel } 52199f823f94374917174f96a7689955b8463db6816Hal Finkel // If a nested loop has been converted, then we can't convert this loop. 52299f823f94374917174f96a7689955b8463db6816Hal Finkel if (Changed) { 52399f823f94374917174f96a7689955b8463db6816Hal Finkel return Changed; 52499f823f94374917174f96a7689955b8463db6816Hal Finkel } 52599f823f94374917174f96a7689955b8463db6816Hal Finkel 52699f823f94374917174f96a7689955b8463db6816Hal Finkel bool WordCmp; 52799f823f94374917174f96a7689955b8463db6816Hal Finkel SmallVector<MachineInstr *, 2> OldInsts; 52899f823f94374917174f96a7689955b8463db6816Hal Finkel // Are we able to determine the trip count for the loop? 52999f823f94374917174f96a7689955b8463db6816Hal Finkel CountValue *TripCount = getTripCount(L, WordCmp, OldInsts); 53099f823f94374917174f96a7689955b8463db6816Hal Finkel if (TripCount == 0) { 53199f823f94374917174f96a7689955b8463db6816Hal Finkel DEBUG(dbgs() << "failed to get trip count!\n"); 53299f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 53399f823f94374917174f96a7689955b8463db6816Hal Finkel } 53499f823f94374917174f96a7689955b8463db6816Hal Finkel // Does the loop contain any invalid instructions? 53599f823f94374917174f96a7689955b8463db6816Hal Finkel if (containsInvalidInstruction(L)) { 53699f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 53799f823f94374917174f96a7689955b8463db6816Hal Finkel } 53899f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *Preheader = L->getLoopPreheader(); 53999f823f94374917174f96a7689955b8463db6816Hal Finkel // No preheader means there's not place for the loop instr. 54099f823f94374917174f96a7689955b8463db6816Hal Finkel if (Preheader == 0) { 54199f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 54299f823f94374917174f96a7689955b8463db6816Hal Finkel } 54399f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator(); 54499f823f94374917174f96a7689955b8463db6816Hal Finkel 54599f823f94374917174f96a7689955b8463db6816Hal Finkel DebugLoc dl; 54699f823f94374917174f96a7689955b8463db6816Hal Finkel if (InsertPos != Preheader->end()) 54799f823f94374917174f96a7689955b8463db6816Hal Finkel dl = InsertPos->getDebugLoc(); 54899f823f94374917174f96a7689955b8463db6816Hal Finkel 54999f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *LastMBB = L->getExitingBlock(); 55099f823f94374917174f96a7689955b8463db6816Hal Finkel // Don't generate CTR loop if the loop has more than one exit. 55199f823f94374917174f96a7689955b8463db6816Hal Finkel if (LastMBB == 0) { 55299f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 55399f823f94374917174f96a7689955b8463db6816Hal Finkel } 55499f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator(); 55599f823f94374917174f96a7689955b8463db6816Hal Finkel 55699f823f94374917174f96a7689955b8463db6816Hal Finkel // Determine the loop start. 55799f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *LoopStart = L->getTopBlock(); 55899f823f94374917174f96a7689955b8463db6816Hal Finkel if (L->getLoopLatch() != LastMBB) { 55999f823f94374917174f96a7689955b8463db6816Hal Finkel // When the exit and latch are not the same, use the latch block as the 56099f823f94374917174f96a7689955b8463db6816Hal Finkel // start. 56199f823f94374917174f96a7689955b8463db6816Hal Finkel // The loop start address is used only after the 1st iteration, and the loop 56299f823f94374917174f96a7689955b8463db6816Hal Finkel // latch may contains instrs. that need to be executed after the 1st iter. 56399f823f94374917174f96a7689955b8463db6816Hal Finkel LoopStart = L->getLoopLatch(); 56499f823f94374917174f96a7689955b8463db6816Hal Finkel // Make sure the latch is a successor of the exit, otherwise it won't work. 56599f823f94374917174f96a7689955b8463db6816Hal Finkel if (!LastMBB->isSuccessor(LoopStart)) { 56699f823f94374917174f96a7689955b8463db6816Hal Finkel return false; 56799f823f94374917174f96a7689955b8463db6816Hal Finkel } 56899f823f94374917174f96a7689955b8463db6816Hal Finkel } 56999f823f94374917174f96a7689955b8463db6816Hal Finkel 57099f823f94374917174f96a7689955b8463db6816Hal Finkel // Convert the loop to a CTR loop 57199f823f94374917174f96a7689955b8463db6816Hal Finkel DEBUG(dbgs() << "Change to CTR loop at "; L->dump()); 57299f823f94374917174f96a7689955b8463db6816Hal Finkel 57399f823f94374917174f96a7689955b8463db6816Hal Finkel MachineFunction *MF = LastMBB->getParent(); 57499f823f94374917174f96a7689955b8463db6816Hal Finkel const PPCSubtarget &Subtarget = MF->getTarget().getSubtarget<PPCSubtarget>(); 57599f823f94374917174f96a7689955b8463db6816Hal Finkel bool isPPC64 = Subtarget.isPPC64(); 57699f823f94374917174f96a7689955b8463db6816Hal Finkel 57799f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned CountReg; 57899f823f94374917174f96a7689955b8463db6816Hal Finkel if (TripCount->isReg()) { 57999f823f94374917174f96a7689955b8463db6816Hal Finkel // Create a copy of the loop count register. 58099f823f94374917174f96a7689955b8463db6816Hal Finkel const TargetRegisterClass *RC = 58199f823f94374917174f96a7689955b8463db6816Hal Finkel MF->getRegInfo().getRegClass(TripCount->getReg()); 58299f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg = MF->getRegInfo().createVirtualRegister(RC); 58399f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 58499f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(TargetOpcode::COPY), CountReg).addReg(TripCount->getReg()); 58599f823f94374917174f96a7689955b8463db6816Hal Finkel if (TripCount->isNeg()) { 58699f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned CountReg1 = CountReg; 58799f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg = MF->getRegInfo().createVirtualRegister(RC); 58899f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 58999f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(isPPC64 ? PPC::NEG8 : PPC::NEG), 59099f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg).addReg(CountReg1); 59199f823f94374917174f96a7689955b8463db6816Hal Finkel } 59299f823f94374917174f96a7689955b8463db6816Hal Finkel 59399f823f94374917174f96a7689955b8463db6816Hal Finkel // On a 64-bit system, if the original comparison was only 32-bit, then 59499f823f94374917174f96a7689955b8463db6816Hal Finkel // mask out the higher-order part of the count. 59599f823f94374917174f96a7689955b8463db6816Hal Finkel if (isPPC64 && WordCmp) { 59699f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned CountReg1 = CountReg; 59799f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg = MF->getRegInfo().createVirtualRegister(RC); 59899f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 59999f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(PPC::RLDICL), CountReg).addReg(CountReg1 60099f823f94374917174f96a7689955b8463db6816Hal Finkel ).addImm(0).addImm(32); 60199f823f94374917174f96a7689955b8463db6816Hal Finkel } 60299f823f94374917174f96a7689955b8463db6816Hal Finkel } else { 60399f823f94374917174f96a7689955b8463db6816Hal Finkel assert(TripCount->isImm() && "Expecting immedate vaule for trip count"); 60499f823f94374917174f96a7689955b8463db6816Hal Finkel // Put the trip count in a register for transfer into the count register. 60599f823f94374917174f96a7689955b8463db6816Hal Finkel const TargetRegisterClass *GPRC = &PPC::GPRCRegClass; 60699f823f94374917174f96a7689955b8463db6816Hal Finkel const TargetRegisterClass *G8RC = &PPC::G8RCRegClass; 60799f823f94374917174f96a7689955b8463db6816Hal Finkel const TargetRegisterClass *RC = isPPC64 ? G8RC : GPRC; 60899f823f94374917174f96a7689955b8463db6816Hal Finkel 60999f823f94374917174f96a7689955b8463db6816Hal Finkel int64_t CountImm = TripCount->getImm(); 61099f823f94374917174f96a7689955b8463db6816Hal Finkel if (TripCount->isNeg()) 61199f823f94374917174f96a7689955b8463db6816Hal Finkel CountImm = -CountImm; 61299f823f94374917174f96a7689955b8463db6816Hal Finkel 61399f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg = MF->getRegInfo().createVirtualRegister(RC); 61499f823f94374917174f96a7689955b8463db6816Hal Finkel if (CountImm > 0xFFFF) { 61599f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 61699f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(isPPC64 ? PPC::LIS8 : PPC::LIS), 61799f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg).addImm(CountImm >> 16); 61899f823f94374917174f96a7689955b8463db6816Hal Finkel unsigned CountReg1 = CountReg; 61999f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg = MF->getRegInfo().createVirtualRegister(RC); 62099f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 62199f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(isPPC64 ? PPC::ORI8 : PPC::ORI), 62299f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg).addReg(CountReg1).addImm(CountImm & 0xFFFF); 62399f823f94374917174f96a7689955b8463db6816Hal Finkel } else { 62499f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 62599f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(isPPC64 ? PPC::LI8 : PPC::LI), 62699f823f94374917174f96a7689955b8463db6816Hal Finkel CountReg).addImm(CountImm); 62799f823f94374917174f96a7689955b8463db6816Hal Finkel } 62899f823f94374917174f96a7689955b8463db6816Hal Finkel } 62999f823f94374917174f96a7689955b8463db6816Hal Finkel 63099f823f94374917174f96a7689955b8463db6816Hal Finkel // Add the mtctr instruction to the beginning of the loop. 63199f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*Preheader, InsertPos, dl, 63299f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get(isPPC64 ? PPC::MTCTR8 : PPC::MTCTR)).addReg(CountReg, 63399f823f94374917174f96a7689955b8463db6816Hal Finkel TripCount->isImm() ? RegState::Kill : 0); 63499f823f94374917174f96a7689955b8463db6816Hal Finkel 63599f823f94374917174f96a7689955b8463db6816Hal Finkel // Make sure the loop start always has a reference in the CFG. We need to 63699f823f94374917174f96a7689955b8463db6816Hal Finkel // create a BlockAddress operand to get this mechanism to work both the 63799f823f94374917174f96a7689955b8463db6816Hal Finkel // MachineBasicBlock and BasicBlock objects need the flag set. 63899f823f94374917174f96a7689955b8463db6816Hal Finkel LoopStart->setHasAddressTaken(); 63999f823f94374917174f96a7689955b8463db6816Hal Finkel // This line is needed to set the hasAddressTaken flag on the BasicBlock 64099f823f94374917174f96a7689955b8463db6816Hal Finkel // object 64199f823f94374917174f96a7689955b8463db6816Hal Finkel BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock())); 64299f823f94374917174f96a7689955b8463db6816Hal Finkel 64399f823f94374917174f96a7689955b8463db6816Hal Finkel // Replace the loop branch with a bdnz instruction. 64499f823f94374917174f96a7689955b8463db6816Hal Finkel dl = LastI->getDebugLoc(); 64599f823f94374917174f96a7689955b8463db6816Hal Finkel const std::vector<MachineBasicBlock*> Blocks = L->getBlocks(); 64699f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 64799f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *MBB = Blocks[i]; 64899f823f94374917174f96a7689955b8463db6816Hal Finkel if (MBB != Preheader) 64999f823f94374917174f96a7689955b8463db6816Hal Finkel MBB->addLiveIn(isPPC64 ? PPC::CTR8 : PPC::CTR); 65099f823f94374917174f96a7689955b8463db6816Hal Finkel } 65199f823f94374917174f96a7689955b8463db6816Hal Finkel 65299f823f94374917174f96a7689955b8463db6816Hal Finkel // The loop ends with either: 65399f823f94374917174f96a7689955b8463db6816Hal Finkel // - a conditional branch followed by an unconditional branch, or 65499f823f94374917174f96a7689955b8463db6816Hal Finkel // - a conditional branch to the loop start. 65599f823f94374917174f96a7689955b8463db6816Hal Finkel assert(LastI->getOpcode() == PPC::BCC && 65699f823f94374917174f96a7689955b8463db6816Hal Finkel "loop end must start with a BCC instruction"); 65799f823f94374917174f96a7689955b8463db6816Hal Finkel // Either the BCC branches to the beginning of the loop, or it 65899f823f94374917174f96a7689955b8463db6816Hal Finkel // branches out of the loop and there is an unconditional branch 65999f823f94374917174f96a7689955b8463db6816Hal Finkel // to the start of the loop. 66099f823f94374917174f96a7689955b8463db6816Hal Finkel MachineBasicBlock *BranchTarget = LastI->getOperand(2).getMBB(); 66199f823f94374917174f96a7689955b8463db6816Hal Finkel BuildMI(*LastMBB, LastI, dl, 66299f823f94374917174f96a7689955b8463db6816Hal Finkel TII->get((BranchTarget == LoopStart) ? 66399f823f94374917174f96a7689955b8463db6816Hal Finkel (isPPC64 ? PPC::BDNZ8 : PPC::BDNZ) : 66499f823f94374917174f96a7689955b8463db6816Hal Finkel (isPPC64 ? PPC::BDZ8 : PPC::BDZ))).addMBB(BranchTarget); 66599f823f94374917174f96a7689955b8463db6816Hal Finkel 66699f823f94374917174f96a7689955b8463db6816Hal Finkel // Conditional branch; just delete it. 66799f823f94374917174f96a7689955b8463db6816Hal Finkel LastMBB->erase(LastI); 66899f823f94374917174f96a7689955b8463db6816Hal Finkel 66999f823f94374917174f96a7689955b8463db6816Hal Finkel delete TripCount; 67099f823f94374917174f96a7689955b8463db6816Hal Finkel 67199f823f94374917174f96a7689955b8463db6816Hal Finkel // The induction operation (add) and the comparison (cmpwi) may now be 67299f823f94374917174f96a7689955b8463db6816Hal Finkel // unneeded. If these are unneeded, then remove them. 67399f823f94374917174f96a7689955b8463db6816Hal Finkel for (unsigned i = 0; i < OldInsts.size(); ++i) 67499f823f94374917174f96a7689955b8463db6816Hal Finkel removeIfDead(OldInsts[i]); 67599f823f94374917174f96a7689955b8463db6816Hal Finkel 67699f823f94374917174f96a7689955b8463db6816Hal Finkel ++NumCTRLoops; 67799f823f94374917174f96a7689955b8463db6816Hal Finkel return true; 67899f823f94374917174f96a7689955b8463db6816Hal Finkel} 67999f823f94374917174f96a7689955b8463db6816Hal Finkel 680