AArch64A57FPLoadBalancing.cpp [plain text]
#include "AArch64.h"
#include "AArch64InstrInfo.h"
#include "AArch64Subtarget.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <list>
using namespace llvm;
#define DEBUG_TYPE "aarch64-a57-fp-load-balancing"
static cl::opt<bool>
TransformAll("aarch64-a57-fp-load-balancing-force-all",
cl::desc("Always modify dest registers regardless of color"),
cl::init(false), cl::Hidden);
static cl::opt<unsigned>
OverrideBalance("aarch64-a57-fp-load-balancing-override",
cl::desc("Ignore balance information, always return "
"(1: Even, 2: Odd)."),
cl::init(0), cl::Hidden);
static bool isMul(MachineInstr *MI) {
switch (MI->getOpcode()) {
case AArch64::FMULSrr:
case AArch64::FNMULSrr:
case AArch64::FMULDrr:
case AArch64::FNMULDrr:
case AArch64::FMULv2f32:
return true;
default:
return false;
}
}
static bool isMla(MachineInstr *MI) {
switch (MI->getOpcode()) {
case AArch64::FMSUBSrrr:
case AArch64::FMADDSrrr:
case AArch64::FNMSUBSrrr:
case AArch64::FNMADDSrrr:
case AArch64::FMSUBDrrr:
case AArch64::FMADDDrrr:
case AArch64::FNMSUBDrrr:
case AArch64::FNMADDDrrr:
case AArch64::FMLAv2f32:
case AArch64::FMLSv2f32:
return true;
default:
return false;
}
}
namespace {
enum class Color { Even, Odd };
#ifndef NDEBUG
static const char *ColorNames[2] = { "Even", "Odd" };
#endif
class Chain;
class AArch64A57FPLoadBalancing : public MachineFunctionPass {
const AArch64InstrInfo *TII;
MachineRegisterInfo *MRI;
const TargetRegisterInfo *TRI;
RegisterClassInfo RCI;
public:
static char ID;
explicit AArch64A57FPLoadBalancing() : MachineFunctionPass(ID) {}
bool runOnMachineFunction(MachineFunction &F) override;
const char *getPassName() const override {
return "A57 FP Anti-dependency breaker";
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
MachineFunctionPass::getAnalysisUsage(AU);
}
private:
bool runOnBasicBlock(MachineBasicBlock &MBB);
bool colorChainSet(std::vector<Chain*> GV, MachineBasicBlock &MBB,
int &Balance);
bool colorChain(Chain *G, Color C, MachineBasicBlock &MBB);
int scavengeRegister(Chain *G, Color C, MachineBasicBlock &MBB);
void scanInstruction(MachineInstr *MI, unsigned Idx,
std::map<unsigned, Chain*> &Chains,
std::set<Chain*> &ChainSet);
void maybeKillChain(MachineOperand &MO, unsigned Idx,
std::map<unsigned, Chain*> &RegChains);
Color getColor(unsigned Register);
Chain *getAndEraseNext(Color PreferredColor, std::vector<Chain*> &L);
};
char AArch64A57FPLoadBalancing::ID = 0;
class Chain {
public:
MachineInstr *StartInst, *LastInst, *KillInst;
unsigned StartInstIdx, LastInstIdx, KillInstIdx;
std::set<MachineInstr*> Insts;
bool KillIsImmutable;
Color LastColor;
Chain(MachineInstr *MI, unsigned Idx, Color C) :
StartInst(MI), LastInst(MI), KillInst(NULL),
StartInstIdx(Idx), LastInstIdx(Idx), KillInstIdx(0),
LastColor(C) {
Insts.insert(MI);
}
void add(MachineInstr *MI, unsigned Idx, Color C) {
LastInst = MI;
LastInstIdx = Idx;
LastColor = C;
Insts.insert(MI);
}
bool contains(MachineInstr *MI) { return Insts.count(MI) > 0; }
unsigned size() const {
return Insts.size();
}
void setKill(MachineInstr *MI, unsigned Idx, bool Immutable) {
KillInst = MI;
KillInstIdx = Idx;
KillIsImmutable = Immutable;
}
MachineInstr *getStart() const { return StartInst; }
MachineInstr *getLast() const { return LastInst; }
MachineInstr *getKill() const { return KillInst; }
MachineInstr *getEnd() const {
return ++MachineBasicBlock::iterator(KillInst ? KillInst : LastInst);
}
bool isKillImmutable() const { return KillIsImmutable; }
Color getPreferredColor() {
if (OverrideBalance != 0)
return OverrideBalance == 1 ? Color::Even : Color::Odd;
return LastColor;
}
bool rangeOverlapsWith(Chain *Other) {
unsigned End = KillInst ? KillInstIdx : LastInstIdx;
unsigned OtherEnd = Other->KillInst ?
Other->KillInstIdx : Other->LastInstIdx;
return StartInstIdx <= OtherEnd && Other->StartInstIdx <= End;
}
bool startsBefore(Chain *Other) {
return StartInstIdx < Other->StartInstIdx;
}
bool requiresFixup() const {
return (getKill() && isKillImmutable()) || !getKill();
}
std::string str() const {
std::string S;
raw_string_ostream OS(S);
OS << "{";
StartInst->print(OS, NULL, true);
OS << " -> ";
LastInst->print(OS, NULL, true);
if (KillInst) {
OS << " (kill @ ";
KillInst->print(OS, NULL, true);
OS << ")";
}
OS << "}";
return OS.str();
}
};
}
bool AArch64A57FPLoadBalancing::runOnMachineFunction(MachineFunction &F) {
bool Changed = false;
DEBUG(dbgs() << "***** AArch64A57FPLoadBalancing *****\n");
const TargetMachine &TM = F.getTarget();
MRI = &F.getRegInfo();
TRI = F.getRegInfo().getTargetRegisterInfo();
TII = TM.getSubtarget<AArch64Subtarget>().getInstrInfo();
RCI.runOnMachineFunction(F);
for (auto &MBB : F) {
Changed |= runOnBasicBlock(MBB);
}
return Changed;
}
bool AArch64A57FPLoadBalancing::runOnBasicBlock(MachineBasicBlock &MBB) {
bool Changed = false;
DEBUG(dbgs() << "Running on MBB: " << MBB << " - scanning instructions...\n");
std::map<unsigned, Chain*> ActiveChains;
std::set<Chain*> AllChains;
unsigned Idx = 0;
for (auto &MI : MBB)
scanInstruction(&MI, Idx++, ActiveChains, AllChains);
DEBUG(dbgs() << "Scan complete, "<< AllChains.size() << " chains created.\n");
EquivalenceClasses<Chain*> EC;
for (auto *I : AllChains)
EC.insert(I);
for (auto *I : AllChains) {
for (auto *J : AllChains) {
if (I != J && I->rangeOverlapsWith(J))
EC.unionSets(I, J);
}
}
DEBUG(dbgs() << "Created " << EC.getNumClasses() << " disjoint sets.\n");
std::vector<std::vector<Chain*> > V;
for (auto I = EC.begin(), E = EC.end(); I != E; ++I) {
std::vector<Chain*> Cs(EC.member_begin(I), EC.member_end());
if (Cs.empty()) continue;
V.push_back(Cs);
}
std::sort(V.begin(), V.end(),
[](const std::vector<Chain*> &A,
const std::vector<Chain*> &B) {
return A.front()->startsBefore(B.front());
});
int Parity = 0;
for (auto &I : V)
Changed |= colorChainSet(I, MBB, Parity);
for (auto *C : AllChains)
delete C;
return Changed;
}
Chain *AArch64A57FPLoadBalancing::getAndEraseNext(Color PreferredColor,
std::vector<Chain*> &L) {
if (L.empty())
return nullptr;
const unsigned SizeFuzz = 1;
unsigned MinSize = L.front()->size() - SizeFuzz;
for (auto I = L.begin(), E = L.end(); I != E; ++I) {
if ((*I)->size() <= MinSize) {
Chain *Ch = *--I;
L.erase(I);
return Ch;
}
if ((*I)->getPreferredColor() == PreferredColor) {
Chain *Ch = *I;
L.erase(I);
return Ch;
}
}
Chain *Ch = L.front();
L.erase(L.begin());
return Ch;
}
bool AArch64A57FPLoadBalancing::colorChainSet(std::vector<Chain*> GV,
MachineBasicBlock &MBB,
int &Parity) {
bool Changed = false;
DEBUG(dbgs() << "colorChainSet(): #sets=" << GV.size() << "\n");
std::sort(GV.begin(), GV.end(), [](const Chain *G1, const Chain *G2) {
if (G1->size() != G2->size())
return G1->size() > G2->size();
return G1->requiresFixup() > G2->requiresFixup();
});
Color PreferredColor = Parity < 0 ? Color::Even : Color::Odd;
while (Chain *G = getAndEraseNext(PreferredColor, GV)) {
Color C = PreferredColor;
if (Parity == 0)
C = G->getPreferredColor();
DEBUG(dbgs() << " - Parity=" << Parity << ", Color="
<< ColorNames[(int)C] << "\n");
if (G->requiresFixup() && C != G->getPreferredColor()) {
C = G->getPreferredColor();
DEBUG(dbgs() << " - " << G->str() << " - not worthwhile changing; "
"color remains " << ColorNames[(int)C] << "\n");
}
Changed |= colorChain(G, C, MBB);
Parity += (C == Color::Even) ? G->size() : -G->size();
PreferredColor = Parity < 0 ? Color::Even : Color::Odd;
}
return Changed;
}
int AArch64A57FPLoadBalancing::scavengeRegister(Chain *G, Color C,
MachineBasicBlock &MBB) {
RegScavenger RS;
RS.enterBasicBlock(&MBB);
RS.forward(MachineBasicBlock::iterator(G->getStart()));
unsigned RegClassID = G->getStart()->getDesc().OpInfo[0].RegClass;
BitVector AvailableRegs = RS.getRegsAvailable(TRI->getRegClass(RegClassID));
for (MachineBasicBlock::iterator I = G->getStart(), E = G->getEnd();
I != E; ++I) {
RS.forward(I);
AvailableRegs &= RS.getRegsAvailable(TRI->getRegClass(RegClassID));
for (auto J : I->operands()) {
if (J.isRegMask())
AvailableRegs.clearBitsNotInMask(J.getRegMask());
}
}
auto Ord = RCI.getOrder(TRI->getRegClass(RegClassID));
for (auto Reg : Ord) {
if (!AvailableRegs[Reg])
continue;
if ((C == Color::Even && (Reg % 2) == 0) ||
(C == Color::Odd && (Reg % 2) == 1))
return Reg;
}
return -1;
}
bool AArch64A57FPLoadBalancing::colorChain(Chain *G, Color C,
MachineBasicBlock &MBB) {
bool Changed = false;
DEBUG(dbgs() << " - colorChain(" << G->str() << ", "
<< ColorNames[(int)C] << ")\n");
int Reg = scavengeRegister(G, C, MBB);
if (Reg == -1) {
DEBUG(dbgs() << "Scavenging (thus coloring) failed!\n");
return false;
}
DEBUG(dbgs() << " - Scavenged register: " << TRI->getName(Reg) << "\n");
std::map<unsigned, unsigned> Substs;
for (MachineBasicBlock::iterator I = G->getStart(), E = G->getEnd();
I != E; ++I) {
if (!G->contains(I) &&
(&*I != G->getKill() || G->isKillImmutable()))
continue;
std::vector<unsigned> ToErase;
for (auto &U : I->operands()) {
if (U.isReg() && U.isUse() && Substs.find(U.getReg()) != Substs.end()) {
unsigned OrigReg = U.getReg();
U.setReg(Substs[OrigReg]);
if (U.isKill())
ToErase.push_back(OrigReg);
} else if (U.isRegMask()) {
for (auto J : Substs) {
if (U.clobbersPhysReg(J.first))
ToErase.push_back(J.first);
}
}
}
for (auto J : ToErase)
Substs.erase(J);
if (&*I != G->getKill()) {
MachineOperand &MO = I->getOperand(0);
bool Change = TransformAll || getColor(MO.getReg()) != C;
if (G->requiresFixup() && &*I == G->getLast())
Change = false;
if (Change) {
Substs[MO.getReg()] = Reg;
MO.setReg(Reg);
MRI->setPhysRegUsed(Reg);
Changed = true;
}
}
}
assert(Substs.size() == 0 && "No substitutions should be left active!");
if (G->getKill()) {
DEBUG(dbgs() << " - Kill instruction seen.\n");
} else {
DEBUG(dbgs() << " - Destination register not changed.\n");
}
return Changed;
}
void AArch64A57FPLoadBalancing::
scanInstruction(MachineInstr *MI, unsigned Idx,
std::map<unsigned, Chain*> &ActiveChains,
std::set<Chain*> &AllChains) {
if (isMul(MI)) {
for (auto &I : MI->operands())
maybeKillChain(I, Idx, ActiveChains);
unsigned DestReg = MI->getOperand(0).getReg();
DEBUG(dbgs() << "New chain started for register "
<< TRI->getName(DestReg) << " at " << *MI);
Chain *G = new Chain(MI, Idx, getColor(DestReg));
ActiveChains[DestReg] = G;
AllChains.insert(G);
} else if (isMla(MI)) {
unsigned DestReg = MI->getOperand(0).getReg();
unsigned AccumReg = MI->getOperand(3).getReg();
maybeKillChain(MI->getOperand(1), Idx, ActiveChains);
maybeKillChain(MI->getOperand(2), Idx, ActiveChains);
if (DestReg != AccumReg)
maybeKillChain(MI->getOperand(0), Idx, ActiveChains);
if (ActiveChains.find(AccumReg) != ActiveChains.end()) {
DEBUG(dbgs() << "Chain found for accumulator register "
<< TRI->getName(AccumReg) << " in MI " << *MI);
if (MI->getOperand(3).isKill()) {
DEBUG(dbgs() << "Instruction was successfully added to chain.\n");
ActiveChains[AccumReg]->add(MI, Idx, getColor(DestReg));
ActiveChains[DestReg] = ActiveChains[AccumReg];
return;
}
DEBUG(dbgs() << "Cannot add to chain because accumulator operand wasn't "
<< "marked <kill>!\n");
maybeKillChain(MI->getOperand(3), Idx, ActiveChains);
}
DEBUG(dbgs() << "Creating new chain for dest register "
<< TRI->getName(DestReg) << "\n");
Chain *G = new Chain(MI, Idx, getColor(DestReg));
ActiveChains[DestReg] = G;
AllChains.insert(G);
} else {
for (auto &I : MI->operands())
maybeKillChain(I, Idx, ActiveChains);
}
}
void AArch64A57FPLoadBalancing::
maybeKillChain(MachineOperand &MO, unsigned Idx,
std::map<unsigned, Chain*> &ActiveChains) {
MachineInstr *MI = MO.getParent();
if (MO.isReg()) {
if (MO.isKill() && ActiveChains.find(MO.getReg()) != ActiveChains.end()) {
DEBUG(dbgs() << "Kill seen for chain " << TRI->getName(MO.getReg())
<< "\n");
ActiveChains[MO.getReg()]->setKill(MI, Idx, MO.isTied());
}
ActiveChains.erase(MO.getReg());
} else if (MO.isRegMask()) {
for (auto I = ActiveChains.begin(), E = ActiveChains.end();
I != E;) {
if (MO.clobbersPhysReg(I->first)) {
DEBUG(dbgs() << "Kill (regmask) seen for chain "
<< TRI->getName(I->first) << "\n");
I->second->setKill(MI, Idx, true);
ActiveChains.erase(I++);
} else
++I;
}
}
}
Color AArch64A57FPLoadBalancing::getColor(unsigned Reg) {
if ((TRI->getEncodingValue(Reg) % 2) == 0)
return Color::Even;
else
return Color::Odd;
}
FunctionPass *llvm::createAArch64A57FPLoadBalancing() {
return new AArch64A57FPLoadBalancing();
}