HexagonHardwareLoops.cpp [plain text]
#define DEBUG_TYPE "hwloops"
#include "llvm/ADT/SmallSet.h"
#include "Hexagon.h"
#include "HexagonTargetMachine.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/PassSupport.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include <algorithm>
#include <vector>
using namespace llvm;
#ifndef NDEBUG
static cl::opt<int> HWLoopLimit("max-hwloop", cl::Hidden, cl::init(-1));
#endif
STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
namespace llvm {
void initializeHexagonHardwareLoopsPass(PassRegistry&);
}
namespace {
class CountValue;
struct HexagonHardwareLoops : public MachineFunctionPass {
MachineLoopInfo *MLI;
MachineRegisterInfo *MRI;
MachineDominatorTree *MDT;
const HexagonTargetMachine *TM;
const HexagonInstrInfo *TII;
const HexagonRegisterInfo *TRI;
#ifndef NDEBUG
static int Counter;
#endif
public:
static char ID;
HexagonHardwareLoops() : MachineFunctionPass(ID) {
initializeHexagonHardwareLoopsPass(*PassRegistry::getPassRegistry());
}
virtual bool runOnMachineFunction(MachineFunction &MF);
const char *getPassName() const { return "Hexagon Hardware Loops"; }
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<MachineDominatorTree>();
AU.addRequired<MachineLoopInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
private:
struct Comparison {
enum Kind {
EQ = 0x01,
NE = 0x02,
L = 0x04, G = 0x08, U = 0x40, LTs = L,
LEs = L | EQ,
GTs = G,
GEs = G | EQ,
LTu = L | U,
LEu = L | EQ | U,
GTu = G | U,
GEu = G | EQ | U
};
static Kind getSwappedComparison(Kind Cmp) {
assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");
if ((Cmp & L) || (Cmp & G))
return (Kind)(Cmp ^ (L|G));
return Cmp;
}
};
bool findInductionRegister(MachineLoop *L, unsigned &Reg,
int64_t &IVBump, MachineInstr *&IVOp) const;
CountValue *getLoopTripCount(MachineLoop *L,
SmallVectorImpl<MachineInstr *> &OldInsts);
CountValue *computeCount(MachineLoop *Loop,
const MachineOperand *Start,
const MachineOperand *End,
unsigned IVReg,
int64_t IVBump,
Comparison::Kind Cmp) const;
bool isInvalidLoopOperation(const MachineInstr *MI) const;
bool containsInvalidInstruction(MachineLoop *L) const;
bool convertToHardwareLoop(MachineLoop *L);
bool isDead(const MachineInstr *MI,
SmallVectorImpl<MachineInstr *> &DeadPhis) const;
void removeIfDead(MachineInstr *MI);
bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
MachineInstr *defWithImmediate(unsigned R);
int64_t getImmediate(MachineOperand &MO);
void setImmediate(MachineOperand &MO, int64_t Val);
bool fixupInductionVariable(MachineLoop *L);
MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
};
char HexagonHardwareLoops::ID = 0;
#ifndef NDEBUG
int HexagonHardwareLoops::Counter = 0;
#endif
class CountValue {
public:
enum CountValueType {
CV_Register,
CV_Immediate
};
private:
CountValueType Kind;
union Values {
struct {
unsigned Reg;
unsigned Sub;
} R;
unsigned ImmVal;
} Contents;
public:
explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) {
Kind = t;
if (Kind == CV_Register) {
Contents.R.Reg = v;
Contents.R.Sub = u;
} else {
Contents.ImmVal = v;
}
}
bool isReg() const { return Kind == CV_Register; }
bool isImm() const { return Kind == CV_Immediate; }
unsigned getReg() const {
assert(isReg() && "Wrong CountValue accessor");
return Contents.R.Reg;
}
unsigned getSubReg() const {
assert(isReg() && "Wrong CountValue accessor");
return Contents.R.Sub;
}
unsigned getImm() const {
assert(isImm() && "Wrong CountValue accessor");
return Contents.ImmVal;
}
void print(raw_ostream &OS, const TargetMachine *TM = 0) const {
const TargetRegisterInfo *TRI = TM ? TM->getRegisterInfo() : 0;
if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); }
if (isImm()) { OS << Contents.ImmVal; }
}
};
}
INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
"Hexagon Hardware Loops", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
"Hexagon Hardware Loops", false, false)
static bool isHardwareLoop(const MachineInstr *MI) {
return MI->getOpcode() == Hexagon::LOOP0_r ||
MI->getOpcode() == Hexagon::LOOP0_i;
}
FunctionPass *llvm::createHexagonHardwareLoops() {
return new HexagonHardwareLoops();
}
bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
bool Changed = false;
MLI = &getAnalysis<MachineLoopInfo>();
MRI = &MF.getRegInfo();
MDT = &getAnalysis<MachineDominatorTree>();
TM = static_cast<const HexagonTargetMachine*>(&MF.getTarget());
TII = static_cast<const HexagonInstrInfo*>(TM->getInstrInfo());
TRI = static_cast<const HexagonRegisterInfo*>(TM->getRegisterInfo());
for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
I != E; ++I) {
MachineLoop *L = *I;
if (!L->getParentLoop())
Changed |= convertToHardwareLoop(L);
}
return Changed;
}
bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
unsigned &Reg,
int64_t &IVBump,
MachineInstr *&IVOp
) const {
MachineBasicBlock *Header = L->getHeader();
MachineBasicBlock *Preheader = L->getLoopPreheader();
MachineBasicBlock *Latch = L->getLoopLatch();
if (!Header || !Preheader || !Latch)
return false;
typedef std::pair<unsigned,int64_t> RegisterBump;
typedef std::map<unsigned,RegisterBump> InductionMap;
InductionMap IndMap;
typedef MachineBasicBlock::instr_iterator instr_iterator;
for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
I != E && I->isPHI(); ++I) {
MachineInstr *Phi = &*I;
for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
if (Phi->getOperand(i+1).getMBB() != Latch)
continue;
unsigned PhiOpReg = Phi->getOperand(i).getReg();
MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
unsigned UpdOpc = DI->getOpcode();
bool isAdd = (UpdOpc == Hexagon::ADD_ri);
if (isAdd) {
unsigned IndReg = DI->getOperand(1).getReg();
if (MRI->getVRegDef(IndReg) == Phi) {
unsigned UpdReg = DI->getOperand(0).getReg();
int64_t V = DI->getOperand(2).getImm();
IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
}
}
} }
SmallVector<MachineOperand,2> Cond;
MachineBasicBlock *TB = 0, *FB = 0;
bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false);
if (NotAnalyzed)
return false;
unsigned CSz = Cond.size();
assert (CSz == 1 || CSz == 2);
unsigned PredR = Cond[CSz-1].getReg();
MachineInstr *PredI = MRI->getVRegDef(PredR);
if (!PredI->isCompare())
return false;
unsigned CmpReg1 = 0, CmpReg2 = 0;
int CmpImm = 0, CmpMask = 0;
bool CmpAnalyzed = TII->analyzeCompare(PredI, CmpReg1, CmpReg2,
CmpMask, CmpImm);
if (!CmpAnalyzed)
return false;
InductionMap::iterator IndMapEnd = IndMap.end();
InductionMap::iterator F = IndMapEnd;
if (CmpReg1 != 0) {
InductionMap::iterator F1 = IndMap.find(CmpReg1);
if (F1 != IndMapEnd)
F = F1;
}
if (CmpReg2 != 0) {
InductionMap::iterator F2 = IndMap.find(CmpReg2);
if (F2 != IndMapEnd) {
if (F != IndMapEnd)
return false;
F = F2;
}
}
if (F == IndMapEnd)
return false;
Reg = F->second.first;
IVBump = F->second.second;
IVOp = MRI->getVRegDef(F->first);
return true;
}
CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
SmallVectorImpl<MachineInstr *> &OldInsts) {
MachineBasicBlock *TopMBB = L->getTopBlock();
MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
assert(PI != TopMBB->pred_end() &&
"Loop must have more than one incoming edge!");
MachineBasicBlock *Backedge = *PI++;
if (PI == TopMBB->pred_end()) return 0;
MachineBasicBlock *Incoming = *PI++;
if (PI != TopMBB->pred_end()) return 0;
if (L->contains(Incoming)) {
if (L->contains(Backedge))
return 0;
std::swap(Incoming, Backedge);
} else if (!L->contains(Backedge))
return 0;
MachineBasicBlock *Latch = L->getLoopLatch();
if (!Latch)
return 0;
unsigned IVReg = 0;
int64_t IVBump = 0;
MachineInstr *IVOp;
bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
if (!FoundIV)
return 0;
MachineBasicBlock *Preheader = L->getLoopPreheader();
MachineOperand *InitialValue = 0;
MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
if (MBB == Preheader)
InitialValue = &IV_Phi->getOperand(i);
else if (MBB == Latch)
IVReg = IV_Phi->getOperand(i).getReg(); }
if (!InitialValue)
return 0;
SmallVector<MachineOperand,2> Cond;
MachineBasicBlock *TB = 0, *FB = 0;
bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false);
if (NotAnalyzed)
return 0;
MachineBasicBlock *Header = L->getHeader();
assert (TB && "Latch block without a branch?");
assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");
if (!TB || (FB && TB != Header && FB != Header))
return 0;
bool Negated = (Cond.size() > 1) ^ (TB != Header);
unsigned PredReg = Cond[Cond.size()-1].getReg();
MachineInstr *CondI = MRI->getVRegDef(PredReg);
unsigned CondOpc = CondI->getOpcode();
unsigned CmpReg1 = 0, CmpReg2 = 0;
int Mask = 0, ImmValue = 0;
bool AnalyzedCmp = TII->analyzeCompare(CondI, CmpReg1, CmpReg2,
Mask, ImmValue);
if (!AnalyzedCmp)
return 0;
OldInsts.push_back(CondI);
OldInsts.push_back(IVOp);
Comparison::Kind Cmp;
bool isSwapped = false;
const MachineOperand &Op1 = CondI->getOperand(1);
const MachineOperand &Op2 = CondI->getOperand(2);
const MachineOperand *EndValue = 0;
if (Op1.isReg()) {
if (Op2.isImm() || Op1.getReg() == IVReg)
EndValue = &Op2;
else {
EndValue = &Op1;
isSwapped = true;
}
}
if (!EndValue)
return 0;
switch (CondOpc) {
case Hexagon::CMPEQri:
case Hexagon::CMPEQrr:
Cmp = !Negated ? Comparison::EQ : Comparison::NE;
break;
case Hexagon::CMPGTUri:
case Hexagon::CMPGTUrr:
Cmp = !Negated ? Comparison::GTu : Comparison::LEu;
break;
case Hexagon::CMPGTri:
case Hexagon::CMPGTrr:
Cmp = !Negated ? Comparison::GTs : Comparison::LEs;
break;
case Hexagon::CMPbEQri_V4:
case Hexagon::CMPhEQri_V4: {
if (IVBump != 1)
return 0;
int64_t InitV, EndV;
assert(EndValue->isImm() && "Unrecognized latch comparison");
EndV = EndValue->getImm();
if (InitialValue->isReg()) {
if (!defWithImmediate(InitialValue->getReg()))
return 0;
InitV = getImmediate(*InitialValue);
} else {
assert(InitialValue->isImm());
InitV = InitialValue->getImm();
}
if (InitV >= EndV)
return 0;
if (CondOpc == Hexagon::CMPbEQri_V4) {
if (!isInt<8>(InitV) || !isInt<8>(EndV))
return 0;
} else { if (!isInt<16>(InitV) || !isInt<16>(EndV))
return 0;
}
Cmp = !Negated ? Comparison::EQ : Comparison::NE;
break;
}
default:
return 0;
}
if (isSwapped)
Cmp = Comparison::getSwappedComparison(Cmp);
if (InitialValue->isReg()) {
unsigned R = InitialValue->getReg();
MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
if (!MDT->properlyDominates(DefBB, Header))
return 0;
OldInsts.push_back(MRI->getVRegDef(R));
}
if (EndValue->isReg()) {
unsigned R = EndValue->getReg();
MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
if (!MDT->properlyDominates(DefBB, Header))
return 0;
}
return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);
}
CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
const MachineOperand *Start,
const MachineOperand *End,
unsigned IVReg,
int64_t IVBump,
Comparison::Kind Cmp) const {
if (Cmp == Comparison::EQ)
return 0;
if (Start->isReg()) {
const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());
if (StartValInstr && StartValInstr->getOpcode() == Hexagon::TFRI)
Start = &StartValInstr->getOperand(1);
}
if (End->isReg()) {
const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
if (EndValInstr && EndValInstr->getOpcode() == Hexagon::TFRI)
End = &EndValInstr->getOperand(1);
}
assert (Start->isReg() || Start->isImm());
assert (End->isReg() || End->isImm());
bool CmpLess = Cmp & Comparison::L;
bool CmpGreater = Cmp & Comparison::G;
bool CmpHasEqual = Cmp & Comparison::EQ;
if (CmpLess && IVBump < 0)
return 0;
if (CmpGreater && IVBump > 0)
return 0;
if (Start->isImm() && End->isImm()) {
int64_t StartV = Start->getImm();
int64_t EndV = End->getImm();
int64_t Dist = EndV - StartV;
if (Dist == 0)
return 0;
bool Exact = (Dist % IVBump) == 0;
if (Cmp == Comparison::NE) {
if (!Exact)
return 0;
if ((Dist < 0) ^ (IVBump < 0))
return 0;
}
if (CmpHasEqual)
Dist = Dist > 0 ? Dist+1 : Dist-1;
assert ((!CmpLess || Dist > 0) && "Loop should never iterate!");
assert ((!CmpGreater || Dist < 0) && "Loop should never iterate!");
int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump-1)) / IVBump
: (-Dist + (-IVBump-1)) / (-IVBump);
assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign.");
uint64_t Count = Dist1;
if (Count > 0xFFFFFFFFULL)
return 0;
return new CountValue(CountValue::CV_Immediate, Count);
}
if (!isPowerOf2_64(abs64(IVBump)))
return 0;
MachineBasicBlock *PH = Loop->getLoopPreheader();
assert (PH && "Should have a preheader by now");
MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
DebugLoc DL = (InsertPos != PH->end()) ? InsertPos->getDebugLoc()
: DebugLoc();
if (IVBump < 0) {
std::swap(Start, End);
IVBump = -IVBump;
}
bool RegToImm = Start->isReg() && End->isImm(); bool RegToReg = Start->isReg() && End->isReg();
int64_t StartV = 0, EndV = 0;
if (Start->isImm())
StartV = Start->getImm();
if (End->isImm())
EndV = End->getImm();
int64_t AdjV = 0;
if (CmpHasEqual) {
if (Start->isImm())
StartV--;
else if (End->isImm())
EndV++;
else
AdjV += 1;
}
if (Cmp != Comparison::NE) {
if (Start->isImm())
StartV -= (IVBump-1);
else if (End->isImm())
EndV += (IVBump-1);
else
AdjV += (IVBump-1);
}
unsigned R = 0, SR = 0;
if (Start->isReg()) {
R = Start->getReg();
SR = Start->getSubReg();
} else {
R = End->getReg();
SR = End->getSubReg();
}
const TargetRegisterClass *RC = MRI->getRegClass(R);
if (!SR && RC == &Hexagon::DoubleRegsRegClass)
return 0;
const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
unsigned DistR, DistSR;
if (Start->isImm() && StartV == 0) {
DistR = End->getReg();
DistSR = End->getSubReg();
} else {
const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::SUB_rr) :
(RegToImm ? TII->get(Hexagon::SUB_ri) :
TII->get(Hexagon::ADD_ri));
unsigned SubR = MRI->createVirtualRegister(IntRC);
MachineInstrBuilder SubIB =
BuildMI(*PH, InsertPos, DL, SubD, SubR);
if (RegToReg) {
SubIB.addReg(End->getReg(), 0, End->getSubReg())
.addReg(Start->getReg(), 0, Start->getSubReg());
} else if (RegToImm) {
SubIB.addImm(EndV)
.addReg(Start->getReg(), 0, Start->getSubReg());
} else { SubIB.addReg(End->getReg(), 0, End->getSubReg())
.addImm(-StartV);
}
DistR = SubR;
DistSR = 0;
}
unsigned AdjR, AdjSR;
if (AdjV == 0) {
AdjR = DistR;
AdjSR = DistSR;
} else {
unsigned AddR = MRI->createVirtualRegister(IntRC);
const MCInstrDesc &AddD = TII->get(Hexagon::ADD_ri);
BuildMI(*PH, InsertPos, DL, AddD, AddR)
.addReg(DistR, 0, DistSR)
.addImm(AdjV);
AdjR = AddR;
AdjSR = 0;
}
unsigned CountR, CountSR;
if (IVBump == 1) {
CountR = AdjR;
CountSR = AdjSR;
} else {
unsigned Shift = Log2_32(IVBump);
unsigned LsrR = MRI->createVirtualRegister(IntRC);
const MCInstrDesc &LsrD = TII->get(Hexagon::LSR_ri);
BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
.addReg(AdjR, 0, AdjSR)
.addImm(Shift);
CountR = LsrR;
CountSR = 0;
}
return new CountValue(CountValue::CV_Register, CountR, CountSR);
}
bool HexagonHardwareLoops::isInvalidLoopOperation(
const MachineInstr *MI) const {
if (MI->getDesc().isCall())
return true;
if (isHardwareLoop(MI))
return true;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.isDef())
continue;
unsigned R = MO.getReg();
if (R == Hexagon::LC0 || R == Hexagon::LC1 ||
R == Hexagon::SA0 || R == Hexagon::SA1)
return true;
}
return false;
}
bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L) const {
const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks();
for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
MachineBasicBlock *MBB = Blocks[i];
for (MachineBasicBlock::iterator
MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
const MachineInstr *MI = &*MII;
if (isInvalidLoopOperation(MI))
return true;
}
}
return false;
}
bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
SmallVectorImpl<MachineInstr *> &DeadPhis) const {
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.isDef())
continue;
unsigned Reg = MO.getReg();
if (MRI->use_nodbg_empty(Reg))
continue;
typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator;
use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
use_nodbg_iterator End = MRI->use_nodbg_end();
if (llvm::next(I) != End || !I.getOperand().getParent()->isPHI())
return false;
MachineInstr *OnePhi = I.getOperand().getParent();
for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
const MachineOperand &OPO = OnePhi->getOperand(j);
if (!OPO.isReg() || !OPO.isDef())
continue;
unsigned OPReg = OPO.getReg();
use_nodbg_iterator nextJ;
for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
J != End; J = nextJ) {
nextJ = llvm::next(J);
MachineOperand &Use = J.getOperand();
MachineInstr *UseMI = Use.getParent();
if (MI != UseMI)
return false;
}
}
DeadPhis.push_back(OnePhi);
}
return true;
}
void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
SmallVector<MachineInstr*, 1> DeadPhis;
if (isDead(MI, DeadPhis)) {
DEBUG(dbgs() << "HW looping will remove: " << *MI);
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.isDef())
continue;
unsigned Reg = MO.getReg();
MachineRegisterInfo::use_iterator nextI;
for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
E = MRI->use_end(); I != E; I = nextI) {
nextI = llvm::next(I); MachineOperand &Use = I.getOperand();
MachineInstr *UseMI = Use.getParent();
if (UseMI == MI)
continue;
if (Use.isDebug())
UseMI->getOperand(0).setReg(0U);
}
}
MI->eraseFromParent();
for (unsigned i = 0; i < DeadPhis.size(); ++i)
DeadPhis[i]->eraseFromParent();
}
}
bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L) {
assert(L->getHeader() && "Loop without a header?");
bool Changed = false;
for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
Changed |= convertToHardwareLoop(*I);
if (Changed)
return Changed;
#ifndef NDEBUG
int Limit = HWLoopLimit;
if (Limit >= 0) {
if (Counter >= HWLoopLimit)
return false;
Counter++;
}
#endif
if (containsInvalidInstruction(L))
return false;
if (!fixupInductionVariable(L))
return false;
MachineBasicBlock *LastMBB = L->getExitingBlock();
if (LastMBB == 0)
return false;
MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
if (LastI == LastMBB->end())
return false;
bool NewPreheader = false;
MachineBasicBlock *Preheader = L->getLoopPreheader();
if (!Preheader) {
Preheader = createPreheaderForLoop(L);
if (!Preheader)
return false;
NewPreheader = true;
}
MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
SmallVector<MachineInstr*, 2> OldInsts;
CountValue *TripCount = getLoopTripCount(L, OldInsts);
if (TripCount == 0)
return false;
if (TripCount->isReg()) {
MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
MachineBasicBlock *BBDef = TCDef->getParent();
if (!NewPreheader) {
if (!MDT->dominates(BBDef, Preheader))
return false;
} else {
if (!MDT->properlyDominates(BBDef, L->getHeader()))
return false;
}
}
MachineBasicBlock *LoopStart = L->getTopBlock();
if (L->getLoopLatch() != LastMBB) {
LoopStart = L->getLoopLatch();
if (!LastMBB->isSuccessor(LoopStart))
return false;
}
DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
DebugLoc DL;
if (InsertPos != Preheader->end())
DL = InsertPos->getDebugLoc();
if (TripCount->isReg()) {
unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
.addReg(TripCount->getReg(), 0, TripCount->getSubReg());
BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_r))
.addMBB(LoopStart)
.addReg(CountReg);
} else {
assert(TripCount->isImm() && "Expecting immediate value for trip count");
int64_t CountImm = TripCount->getImm();
if (!TII->isValidOffset(Hexagon::LOOP0_i, CountImm)) {
unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::TFRI), CountReg)
.addImm(CountImm);
BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_r))
.addMBB(LoopStart).addReg(CountReg);
} else
BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_i))
.addMBB(LoopStart).addImm(CountImm);
}
LoopStart->setHasAddressTaken();
BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
DebugLoc LastIDL = LastI->getDebugLoc();
BuildMI(*LastMBB, LastI, LastIDL,
TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart);
if (LastI->getOpcode() == Hexagon::JMP_t ||
LastI->getOpcode() == Hexagon::JMP_f) {
MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
LastI = LastMBB->erase(LastI);
if (!L->contains(BranchTarget)) {
if (LastI != LastMBB->end())
LastI = LastMBB->erase(LastI);
SmallVector<MachineOperand, 0> Cond;
TII->InsertBranch(*LastMBB, BranchTarget, 0, Cond, LastIDL);
}
} else {
LastMBB->erase(LastI);
}
delete TripCount;
for (unsigned i = 0; i < OldInsts.size(); ++i)
removeIfDead(OldInsts[i]);
++NumHWLoops;
return true;
}
bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
MachineInstr *CmpI) {
assert (BumpI != CmpI && "Bump and compare in the same instruction?");
MachineBasicBlock *BB = BumpI->getParent();
if (CmpI->getParent() != BB)
return false;
typedef MachineBasicBlock::instr_iterator instr_iterator;
for (instr_iterator I = BumpI, E = BB->instr_end(); I != E; ++I)
if (&*I == CmpI)
return true;
unsigned PredR = CmpI->getOperand(0).getReg();
bool FoundBump = false;
instr_iterator CmpIt = CmpI, NextIt = llvm::next(CmpIt);
for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
MachineInstr *In = &*I;
for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
MachineOperand &MO = In->getOperand(i);
if (MO.isReg() && MO.isUse()) {
if (MO.getReg() == PredR) return false;
}
}
if (In == BumpI) {
instr_iterator After = BumpI;
instr_iterator From = CmpI;
BB->splice(llvm::next(After), BB, From);
FoundBump = true;
break;
}
}
assert (FoundBump && "Cannot determine instruction order");
return FoundBump;
}
MachineInstr *HexagonHardwareLoops::defWithImmediate(unsigned R) {
MachineInstr *DI = MRI->getVRegDef(R);
unsigned DOpc = DI->getOpcode();
switch (DOpc) {
case Hexagon::TFRI:
case Hexagon::TFRI64:
case Hexagon::CONST32_Int_Real:
case Hexagon::CONST64_Int_Real:
return DI;
}
return 0;
}
int64_t HexagonHardwareLoops::getImmediate(MachineOperand &MO) {
if (MO.isImm())
return MO.getImm();
assert(MO.isReg());
unsigned R = MO.getReg();
MachineInstr *DI = defWithImmediate(R);
assert(DI && "Need an immediate operand");
int64_t v = DI->getOperand(1).getImm();
return v;
}
void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
if (MO.isImm()) {
MO.setImm(Val);
return;
}
assert(MO.isReg());
unsigned R = MO.getReg();
MachineInstr *DI = defWithImmediate(R);
if (MRI->hasOneNonDBGUse(R)) {
DI->getOperand(1).setImm(Val);
return;
}
const TargetRegisterClass *RC = MRI->getRegClass(R);
unsigned NewR = MRI->createVirtualRegister(RC);
MachineBasicBlock &B = *DI->getParent();
DebugLoc DL = DI->getDebugLoc();
BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR)
.addImm(Val);
MO.setReg(NewR);
}
bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
MachineBasicBlock *Header = L->getHeader();
MachineBasicBlock *Preheader = L->getLoopPreheader();
MachineBasicBlock *Latch = L->getLoopLatch();
if (!Header || !Preheader || !Latch)
return false;
typedef std::pair<unsigned,int64_t> RegisterBump;
typedef std::pair<unsigned,RegisterBump> RegisterInduction;
typedef std::set<RegisterInduction> RegisterInductionSet;
RegisterInductionSet IndRegs;
typedef MachineBasicBlock::instr_iterator instr_iterator;
for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
I != E && I->isPHI(); ++I) {
MachineInstr *Phi = &*I;
for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
if (Phi->getOperand(i+1).getMBB() != Latch)
continue;
unsigned PhiReg = Phi->getOperand(i).getReg();
MachineInstr *DI = MRI->getVRegDef(PhiReg);
unsigned UpdOpc = DI->getOpcode();
bool isAdd = (UpdOpc == Hexagon::ADD_ri);
if (isAdd) {
unsigned IndReg = DI->getOperand(1).getReg();
if (MRI->getVRegDef(IndReg) == Phi) {
unsigned UpdReg = DI->getOperand(0).getReg();
int64_t V = DI->getOperand(2).getImm();
IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
}
}
} }
if (IndRegs.empty())
return false;
MachineBasicBlock *TB = 0, *FB = 0;
SmallVector<MachineOperand,2> Cond;
bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false);
if (NotAnalyzed)
return false;
if (Cond.empty())
return false;
if (TB != Header && FB != Header)
return false;
unsigned CSz = Cond.size();
if (CSz != 1 && CSz != 2)
return false;
unsigned P = Cond[CSz-1].getReg();
MachineInstr *PredDef = MRI->getVRegDef(P);
if (!PredDef->isCompare())
return false;
SmallSet<unsigned,2> CmpRegs;
MachineOperand *CmpImmOp = 0;
for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
MachineOperand &MO = PredDef->getOperand(i);
if (MO.isReg()) {
if (MO.isImplicit())
continue;
if (MO.isUse()) {
unsigned R = MO.getReg();
if (!defWithImmediate(R)) {
CmpRegs.insert(MO.getReg());
continue;
}
if (CmpImmOp)
return false;
CmpImmOp = &MO;
}
} else if (MO.isImm()) {
if (CmpImmOp) return false;
CmpImmOp = &MO;
}
}
if (CmpRegs.empty())
return false;
for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
I != E; ++I) {
if (CmpRegs.count(I->first))
return true;
const RegisterBump &RB = I->second;
if (CmpRegs.count(RB.first)) {
if (!CmpImmOp)
return false;
int64_t CmpImm = getImmediate(*CmpImmOp);
int64_t V = RB.second;
if (V > 0 && CmpImm+V < CmpImm) return false;
if (V < 0 && CmpImm+V > CmpImm) return false;
CmpImm += V;
if (CmpImmOp->isImm() && !isInt<8>(CmpImm))
return false;
MachineInstr *BumpI = MRI->getVRegDef(I->first);
bool Order = orderBumpCompare(BumpI, PredDef);
if (!Order)
return false;
setImmediate(*CmpImmOp, CmpImm);
for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
MachineOperand &MO = PredDef->getOperand(i);
if (MO.isReg() && MO.getReg() == RB.first) {
MO.setReg(I->first);
return true;
}
}
}
}
return false;
}
MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
MachineLoop *L) {
if (MachineBasicBlock *TmpPH = L->getLoopPreheader())
return TmpPH;
MachineBasicBlock *Header = L->getHeader();
MachineBasicBlock *Latch = L->getLoopLatch();
MachineFunction *MF = Header->getParent();
DebugLoc DL;
if (!Latch || Header->hasAddressTaken())
return 0;
typedef MachineBasicBlock::instr_iterator instr_iterator;
typedef std::vector<MachineBasicBlock*> MBBVector;
MBBVector Preds(Header->pred_begin(), Header->pred_end());
SmallVector<MachineOperand,2> Tmp1;
MachineBasicBlock *TB = 0, *FB = 0;
if (TII->AnalyzeBranch(*Latch, TB, FB, Tmp1, false))
return 0;
for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
MachineBasicBlock *PB = *I;
if (PB != Latch) {
bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp1, false);
if (NotAnalyzed)
return 0;
}
}
MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
MF->insert(Header, NewPH);
if (Header->pred_size() > 2) {
for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
I != E && I->isPHI(); ++I) {
MachineInstr *PN = &*I;
const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
NewPH->insert(NewPH->end(), NewPN);
unsigned PR = PN->getOperand(0).getReg();
const TargetRegisterClass *RC = MRI->getRegClass(PR);
unsigned NewPR = MRI->createVirtualRegister(RC);
NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
unsigned PredR = PN->getOperand(i).getReg();
MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
if (PredB == Latch)
continue;
NewPN->addOperand(MachineOperand::CreateReg(PredR, false));
NewPN->addOperand(MachineOperand::CreateMBB(PredB));
}
for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
if (PredB != Latch) {
PN->RemoveOperand(i+1);
PN->RemoveOperand(i);
}
}
PN->addOperand(MachineOperand::CreateReg(NewPR, false));
PN->addOperand(MachineOperand::CreateMBB(NewPH));
}
} else {
assert(Header->pred_size() == 2);
for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
I != E && I->isPHI(); ++I) {
MachineInstr *PN = &*I;
for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
MachineOperand &MO = PN->getOperand(i+1);
if (MO.getMBB() != Latch)
MO.setMBB(NewPH);
}
}
}
SmallVector<MachineOperand,1> Tmp2;
SmallVector<MachineOperand,1> EmptyCond;
TB = FB = 0;
for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
MachineBasicBlock *PB = *I;
if (PB != Latch) {
Tmp2.clear();
bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp2, false);
(void)NotAnalyzed; assert (!NotAnalyzed && "Should be analyzable!");
if (TB != Header && (Tmp2.empty() || FB != Header))
TII->InsertBranch(*PB, NewPH, 0, EmptyCond, DL);
PB->ReplaceUsesOfBlockWith(Header, NewPH);
}
}
TB = FB = 0;
bool LatchNotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Tmp2, false);
(void)LatchNotAnalyzed; assert (!LatchNotAnalyzed && "Should be analyzable!");
if (!TB && !FB)
TII->InsertBranch(*Latch, Header, 0, EmptyCond, DL);
TII->InsertBranch(*NewPH, Header, 0, EmptyCond, DL);
NewPH->addSuccessor(Header);
return NewPH;
}