HexagonHardwareLoops.cpp [plain text]
#define DEBUG_TYPE "hwloops"
#include "llvm/Constants.h"
#include "llvm/PassSupport.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/Passes.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/CodeGen/RegisterScavenging.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include <algorithm>
#include "Hexagon.h"
#include "HexagonTargetMachine.h"
using namespace llvm;
STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
namespace {
class CountValue;
struct HexagonHardwareLoops : public MachineFunctionPass {
MachineLoopInfo *MLI;
MachineRegisterInfo *MRI;
const TargetInstrInfo *TII;
public:
static char ID;
HexagonHardwareLoops() : MachineFunctionPass(ID) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
const char *getPassName() const { return "Hexagon Hardware Loops"; }
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<MachineDominatorTree>();
AU.addPreserved<MachineDominatorTree>();
AU.addRequired<MachineLoopInfo>();
AU.addPreserved<MachineLoopInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
private:
const MachineInstr *getCanonicalInductionVariable(MachineLoop *L) const;
CountValue *getTripCount(MachineLoop *L) const;
bool isInductionOperation(const MachineInstr *MI, unsigned IVReg) const;
bool isInvalidLoopOperation(const MachineInstr *MI) const;
bool containsInvalidInstruction(MachineLoop *L) const;
bool convertToHardwareLoop(MachineLoop *L);
};
char HexagonHardwareLoops::ID = 0;
class CountValue {
public:
enum CountValueType {
CV_Register,
CV_Immediate
};
private:
CountValueType Kind;
union Values {
unsigned RegNum;
int64_t ImmVal;
Values(unsigned r) : RegNum(r) {}
Values(int64_t i) : ImmVal(i) {}
} Contents;
bool isNegative;
public:
CountValue(unsigned r, bool neg) : Kind(CV_Register), Contents(r),
isNegative(neg) {}
explicit CountValue(int64_t i) : Kind(CV_Immediate), Contents(i),
isNegative(i < 0) {}
CountValueType getType() const { return Kind; }
bool isReg() const { return Kind == CV_Register; }
bool isImm() const { return Kind == CV_Immediate; }
bool isNeg() const { return isNegative; }
unsigned getReg() const {
assert(isReg() && "Wrong CountValue accessor");
return Contents.RegNum;
}
void setReg(unsigned Val) {
Contents.RegNum = Val;
}
int64_t getImm() const {
assert(isImm() && "Wrong CountValue accessor");
if (isNegative) {
return -Contents.ImmVal;
}
return Contents.ImmVal;
}
void setImm(int64_t Val) {
Contents.ImmVal = Val;
}
void print(raw_ostream &OS, const TargetMachine *TM = 0) const {
if (isReg()) { OS << PrintReg(getReg()); }
if (isImm()) { OS << getImm(); }
}
};
struct HexagonFixupHwLoops : public MachineFunctionPass {
public:
static char ID;
HexagonFixupHwLoops() : MachineFunctionPass(ID) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
const char *getPassName() const { return "Hexagon Hardware Loop Fixup"; }
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
MachineFunctionPass::getAnalysisUsage(AU);
}
private:
static const unsigned MAX_LOOP_DISTANCE = 200;
bool fixupLoopInstrs(MachineFunction &MF);
void convertLoopInstr(MachineFunction &MF,
MachineBasicBlock::iterator &MII,
RegScavenger &RS);
};
char HexagonFixupHwLoops::ID = 0;
}
static bool isHardwareLoop(const MachineInstr *MI) {
return MI->getOpcode() == Hexagon::LOOP0_r ||
MI->getOpcode() == Hexagon::LOOP0_i;
}
static bool isCompareEqualsImm(const MachineInstr *MI) {
return MI->getOpcode() == Hexagon::CMPEQri;
}
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();
TII = MF.getTarget().getInstrInfo();
for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
I != E; ++I) {
MachineLoop *L = *I;
if (!L->getParentLoop()) {
Changed |= convertToHardwareLoop(L);
}
}
return Changed;
}
const MachineInstr
*HexagonHardwareLoops::getCanonicalInductionVariable(MachineLoop *L) const {
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;
for (MachineBasicBlock::iterator I = TopMBB->begin(), E = TopMBB->end();
I != E && I->isPHI(); ++I) {
const MachineInstr *MPhi = &*I;
unsigned DefReg = MPhi->getOperand(0).getReg();
for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
MachineBasicBlock *MBB = MPhi->getOperand(i+1).getMBB();
if (L->contains(MBB)) { const MachineInstr *DI = MRI->getVRegDef(MPhi->getOperand(i).getReg());
if (isInductionOperation(DI, DefReg)) {
return MPhi;
}
}
}
}
return 0;
}
CountValue *HexagonHardwareLoops::getTripCount(MachineLoop *L) const {
const MachineInstr *IV_Inst = getCanonicalInductionVariable(L);
if (IV_Inst == 0) return 0;
const MachineOperand *IV_Opnd;
const MachineOperand *InitialValue;
if (!L->contains(IV_Inst->getOperand(2).getMBB())) {
InitialValue = &IV_Inst->getOperand(1);
IV_Opnd = &IV_Inst->getOperand(3);
} else {
InitialValue = &IV_Inst->getOperand(3);
IV_Opnd = &IV_Inst->getOperand(1);
}
while ((IV_Opnd = IV_Opnd->getNextOperandForReg())) {
const MachineInstr *MI = IV_Opnd->getParent();
if (L->contains(MI) && isCompareEqualsImm(MI)) {
const MachineOperand &MO = MI->getOperand(2);
assert(MO.isImm() && "IV Cmp Operand should be 0");
int64_t ImmVal = MO.getImm();
const MachineInstr *IV_DefInstr = MRI->getVRegDef(IV_Opnd->getReg());
assert(L->contains(IV_DefInstr->getParent()) &&
"IV definition should occurs in loop");
int64_t iv_value = IV_DefInstr->getOperand(2).getImm();
if (ImmVal == 0) {
if (iv_value != 1 && iv_value != -1) {
return 0;
}
return new CountValue(InitialValue->getReg(), iv_value > 0);
} else {
assert(InitialValue->isReg() && "Expecting register for init value");
const MachineInstr *DefInstr = MRI->getVRegDef(InitialValue->getReg());
if (DefInstr && DefInstr->getOpcode() == Hexagon::TFRI) {
int64_t count = ImmVal - DefInstr->getOperand(1).getImm();
if ((count % iv_value) != 0) {
return 0;
}
return new CountValue(count/iv_value);
}
}
}
}
return 0;
}
bool
HexagonHardwareLoops::isInductionOperation(const MachineInstr *MI,
unsigned IVReg) const {
return (MI->getOpcode() ==
Hexagon::ADD_ri && MI->getOperand(1).getReg() == IVReg);
}
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() &&
(MO.getReg() == Hexagon::LC0 || MO.getReg() == Hexagon::LC1 ||
MO.getReg() == Hexagon::SA0 || MO.getReg() == Hexagon::SA0)) {
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::convertToHardwareLoop(MachineLoop *L) {
bool Changed = false;
for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
Changed |= convertToHardwareLoop(*I);
}
if (Changed) {
return Changed;
}
CountValue *TripCount = getTripCount(L);
if (TripCount == 0) {
return false;
}
if (containsInvalidInstruction(L)) {
return false;
}
MachineBasicBlock *Preheader = L->getLoopPreheader();
if (Preheader == 0) {
return false;
}
MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
MachineBasicBlock *LastMBB = L->getExitingBlock();
if (LastMBB == 0) {
return false;
}
MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
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());
if (TripCount->isReg()) {
MachineFunction *MF = LastMBB->getParent();
const TargetRegisterClass *RC =
MF->getRegInfo().getRegClass(TripCount->getReg());
unsigned CountReg = MF->getRegInfo().createVirtualRegister(RC);
BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
TII->get(TargetOpcode::COPY), CountReg).addReg(TripCount->getReg());
if (TripCount->isNeg()) {
unsigned CountReg1 = CountReg;
CountReg = MF->getRegInfo().createVirtualRegister(RC);
BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
TII->get(Hexagon::NEG), CountReg).addReg(CountReg1);
}
BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
TII->get(Hexagon::LOOP0_r)).addMBB(LoopStart).addReg(CountReg);
} else {
assert(TripCount->isImm() && "Expecting immedate vaule for trip count");
int64_t CountImm = TripCount->getImm();
BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
TII->get(Hexagon::LOOP0_i)).addMBB(LoopStart).addImm(CountImm);
}
LoopStart->setHasAddressTaken();
BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
DebugLoc dl = LastI->getDebugLoc();
BuildMI(*LastMBB, LastI, dl, TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart);
if (LastI->getOpcode() == Hexagon::JMP_c ||
LastI->getOpcode() == Hexagon::JMP_cNot) {
MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
LastI = LastMBB->erase(LastI);
if (!L->contains(BranchTarget)) {
if (LastI != LastMBB->end()) {
TII->RemoveBranch(*LastMBB);
}
SmallVector<MachineOperand, 0> Cond;
TII->InsertBranch(*LastMBB, BranchTarget, 0, Cond, dl);
}
} else {
LastMBB->erase(LastI);
}
delete TripCount;
++NumHWLoops;
return true;
}
FunctionPass *llvm::createHexagonFixupHwLoops() {
return new HexagonFixupHwLoops();
}
bool HexagonFixupHwLoops::runOnMachineFunction(MachineFunction &MF) {
DEBUG(dbgs() << "****** Hexagon Hardware Loop Fixup ******\n");
bool Changed = fixupLoopInstrs(MF);
return Changed;
}
bool HexagonFixupHwLoops::fixupLoopInstrs(MachineFunction &MF) {
unsigned InstOffset = 0;
DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
for (MachineFunction::iterator MBB = MF.begin(), MBBe = MF.end();
MBB != MBBe; ++MBB) {
BlockToInstOffset[MBB] = InstOffset;
InstOffset += (MBB->size() * 4);
}
InstOffset = 0;
bool Changed = false;
RegScavenger RS;
for (MachineFunction::iterator MBB = MF.begin(), MBBe = MF.end();
MBB != MBBe; ++MBB) {
InstOffset = BlockToInstOffset[MBB];
RS.enterBasicBlock(MBB);
MachineBasicBlock::iterator MIE = MBB->end();
MachineBasicBlock::iterator MII = MBB->begin();
while (MII != MIE) {
if (isHardwareLoop(MII)) {
RS.forward(MII);
assert(MII->getOperand(0).isMBB() &&
"Expect a basic block as loop operand");
int diff = InstOffset - BlockToInstOffset[MII->getOperand(0).getMBB()];
diff = (diff > 0 ? diff : -diff);
if ((unsigned)diff > MAX_LOOP_DISTANCE) {
convertLoopInstr(MF, MII, RS);
MII = MBB->erase(MII);
Changed = true;
} else {
++MII;
}
} else {
++MII;
}
InstOffset += 4;
}
}
return Changed;
}
void HexagonFixupHwLoops::convertLoopInstr(MachineFunction &MF,
MachineBasicBlock::iterator &MII,
RegScavenger &RS) {
const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
MachineBasicBlock *MBB = MII->getParent();
DebugLoc DL = MII->getDebugLoc();
unsigned Scratch = RS.scavengeRegister(Hexagon::IntRegsRegisterClass, MII, 0);
if (MII->getOperand(1).isReg()) {
BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::LC0)
.addReg(MII->getOperand(1).getReg());
} else {
BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFRI), Scratch)
.addImm(MII->getOperand(1).getImm());
BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::LC0)
.addReg(Scratch);
}
BuildMI(*MBB, MII, DL, TII->get(Hexagon::CONST32_Label), Scratch)
.addMBB(MII->getOperand(0).getMBB());
BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::SA0).addReg(Scratch);
}