HexagonGenInsert.cpp [plain text]
#define DEBUG_TYPE "hexinsert"
#include "llvm/Pass.h"
#include "llvm/PassRegistry.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/Timer.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "Hexagon.h"
#include "HexagonRegisterInfo.h"
#include "HexagonTargetMachine.h"
#include "HexagonBitTracker.h"
#include <map>
#include <vector>
using namespace llvm;
static cl::opt<unsigned> VRegIndexCutoff("insert-vreg-cutoff", cl::init(~0U),
cl::Hidden, cl::ZeroOrMore, cl::desc("Vreg# cutoff for insert generation."));
static cl::opt<unsigned> VRegDistCutoff("insert-dist-cutoff", cl::init(30U),
cl::Hidden, cl::ZeroOrMore, cl::desc("Vreg distance cutoff for insert "
"generation."));
static cl::opt<bool> OptTiming("insert-timing", cl::init(false), cl::Hidden,
cl::ZeroOrMore, cl::desc("Enable timing of insert generation"));
static cl::opt<bool> OptTimingDetail("insert-timing-detail", cl::init(false),
cl::Hidden, cl::ZeroOrMore, cl::desc("Enable detailed timing of insert "
"generation"));
static cl::opt<bool> OptSelectAll0("insert-all0", cl::init(false), cl::Hidden,
cl::ZeroOrMore);
static cl::opt<bool> OptSelectHas0("insert-has0", cl::init(false), cl::Hidden,
cl::ZeroOrMore);
static cl::opt<bool> OptConst("insert-const", cl::init(false), cl::Hidden,
cl::ZeroOrMore);
namespace {
inline bool isDebug() {
#ifndef NDEBUG
return ::llvm::DebugFlag && ::llvm::isCurrentDebugType(DEBUG_TYPE);
#else
return false;
#endif
}
}
namespace {
struct RegisterSet : private BitVector {
RegisterSet() = default;
explicit RegisterSet(unsigned s, bool t = false) : BitVector(s, t) {}
using BitVector::clear;
unsigned find_first() const {
int First = BitVector::find_first();
if (First < 0)
return 0;
return x2v(First);
}
unsigned find_next(unsigned Prev) const {
int Next = BitVector::find_next(v2x(Prev));
if (Next < 0)
return 0;
return x2v(Next);
}
RegisterSet &insert(unsigned R) {
unsigned Idx = v2x(R);
ensure(Idx);
return static_cast<RegisterSet&>(BitVector::set(Idx));
}
RegisterSet &remove(unsigned R) {
unsigned Idx = v2x(R);
if (Idx >= size())
return *this;
return static_cast<RegisterSet&>(BitVector::reset(Idx));
}
RegisterSet &insert(const RegisterSet &Rs) {
return static_cast<RegisterSet&>(BitVector::operator|=(Rs));
}
RegisterSet &remove(const RegisterSet &Rs) {
return static_cast<RegisterSet&>(BitVector::reset(Rs));
}
reference operator[](unsigned R) {
unsigned Idx = v2x(R);
ensure(Idx);
return BitVector::operator[](Idx);
}
bool operator[](unsigned R) const {
unsigned Idx = v2x(R);
assert(Idx < size());
return BitVector::operator[](Idx);
}
bool has(unsigned R) const {
unsigned Idx = v2x(R);
if (Idx >= size())
return false;
return BitVector::test(Idx);
}
bool empty() const {
return !BitVector::any();
}
bool includes(const RegisterSet &Rs) const {
return !Rs.BitVector::test(*this);
}
bool intersects(const RegisterSet &Rs) const {
return BitVector::anyCommon(Rs);
}
private:
void ensure(unsigned Idx) {
if (size() <= Idx)
resize(std::max(Idx+1, 32U));
}
static inline unsigned v2x(unsigned v) {
return TargetRegisterInfo::virtReg2Index(v);
}
static inline unsigned x2v(unsigned x) {
return TargetRegisterInfo::index2VirtReg(x);
}
};
struct PrintRegSet {
PrintRegSet(const RegisterSet &S, const TargetRegisterInfo *RI)
: RS(S), TRI(RI) {}
friend raw_ostream &operator<< (raw_ostream &OS,
const PrintRegSet &P);
private:
const RegisterSet &RS;
const TargetRegisterInfo *TRI;
};
raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) {
OS << '{';
for (unsigned R = P.RS.find_first(); R; R = P.RS.find_next(R))
OS << ' ' << PrintReg(R, P.TRI);
OS << " }";
return OS;
}
}
namespace {
struct UnsignedMap : public DenseMap<unsigned,unsigned> {
UnsignedMap() : BaseType() {}
private:
typedef DenseMap<unsigned,unsigned> BaseType;
};
struct RegisterOrdering : public UnsignedMap {
RegisterOrdering() : UnsignedMap() {}
unsigned operator[](unsigned VR) const {
const_iterator F = find(VR);
assert(F != end());
return F->second;
}
bool operator() (unsigned VR1, unsigned VR2) const {
return operator[](VR1) < operator[](VR2);
}
};
}
namespace {
struct BitValueOrdering {
BitValueOrdering(const RegisterOrdering &RB) : BaseOrd(RB) {}
bool operator() (const BitTracker::BitValue &V1,
const BitTracker::BitValue &V2) const;
const RegisterOrdering &BaseOrd;
};
}
bool BitValueOrdering::operator() (const BitTracker::BitValue &V1,
const BitTracker::BitValue &V2) const {
if (V1 == V2)
return false;
if (V1.is(0) || V2.is(0))
return V1.is(0);
if (V2.is(1) || V1.is(1))
return !V2.is(1);
unsigned Ind1 = BaseOrd[V1.RefI.Reg], Ind2 = BaseOrd[V2.RefI.Reg];
if (Ind1 != Ind2)
return Ind1 < Ind2;
assert(V1.RefI.Pos != V2.RefI.Pos && "Bit values should be different");
return V1.RefI.Pos < V2.RefI.Pos;
}
namespace {
struct CellMapShadow {
CellMapShadow(const BitTracker &T) : BT(T) {}
const BitTracker::RegisterCell &lookup(unsigned VR) {
unsigned RInd = TargetRegisterInfo::virtReg2Index(VR);
if (RInd >= CVect.size())
CVect.resize(std::max(RInd+16, 32U), 0);
const BitTracker::RegisterCell *CP = CVect[RInd];
if (CP == 0)
CP = CVect[RInd] = &BT.lookup(VR);
return *CP;
}
const BitTracker &BT;
private:
typedef std::vector<const BitTracker::RegisterCell*> CellVectType;
CellVectType CVect;
};
}
namespace {
struct RegisterCellLexCompare {
RegisterCellLexCompare(const BitValueOrdering &BO, CellMapShadow &M)
: BitOrd(BO), CM(M) {}
bool operator() (unsigned VR1, unsigned VR2) const;
private:
const BitValueOrdering &BitOrd;
CellMapShadow &CM;
};
struct RegisterCellBitCompareSel {
RegisterCellBitCompareSel(unsigned R, unsigned B, unsigned N,
const BitValueOrdering &BO, CellMapShadow &M)
: SelR(R), SelB(B), BitN(N), BitOrd(BO), CM(M) {}
bool operator() (unsigned VR1, unsigned VR2) const;
private:
const unsigned SelR, SelB;
const unsigned BitN;
const BitValueOrdering &BitOrd;
CellMapShadow &CM;
};
}
bool RegisterCellLexCompare::operator() (unsigned VR1, unsigned VR2) const {
if (VR1 == VR2)
return false;
const BitTracker::RegisterCell &RC1 = CM.lookup(VR1), &RC2 = CM.lookup(VR2);
uint16_t W1 = RC1.width(), W2 = RC2.width();
for (uint16_t i = 0, w = std::min(W1, W2); i < w; ++i) {
const BitTracker::BitValue &V1 = RC1[i], &V2 = RC2[i];
if (V1 != V2)
return BitOrd(V1, V2);
}
if (W1 != W2)
return W1 < W2;
return BitOrd.BaseOrd[VR1] < BitOrd.BaseOrd[VR2];
}
bool RegisterCellBitCompareSel::operator() (unsigned VR1, unsigned VR2) const {
if (VR1 == VR2)
return false;
const BitTracker::RegisterCell &RC1 = CM.lookup(VR1);
const BitTracker::RegisterCell &RC2 = CM.lookup(VR2);
uint16_t W1 = RC1.width(), W2 = RC2.width();
uint16_t Bit1 = (VR1 == SelR) ? SelB : BitN;
uint16_t Bit2 = (VR2 == SelR) ? SelB : BitN;
if (W1 <= Bit1)
return Bit2 < W2;
if (W2 <= Bit2)
return false;
const BitTracker::BitValue &V1 = RC1[Bit1], V2 = RC2[Bit2];
if (V1 != V2)
return BitOrd(V1, V2);
return false;
}
namespace {
class OrderedRegisterList {
typedef std::vector<unsigned> ListType;
public:
OrderedRegisterList(const RegisterOrdering &RO) : Ord(RO) {}
void insert(unsigned VR);
void remove(unsigned VR);
unsigned operator[](unsigned Idx) const {
assert(Idx < Seq.size());
return Seq[Idx];
}
unsigned size() const {
return Seq.size();
}
typedef ListType::iterator iterator;
typedef ListType::const_iterator const_iterator;
iterator begin() { return Seq.begin(); }
iterator end() { return Seq.end(); }
const_iterator begin() const { return Seq.begin(); }
const_iterator end() const { return Seq.end(); }
unsigned idx(iterator It) const { return It-begin(); }
private:
ListType Seq;
const RegisterOrdering &Ord;
};
struct PrintORL {
PrintORL(const OrderedRegisterList &L, const TargetRegisterInfo *RI)
: RL(L), TRI(RI) {}
friend raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P);
private:
const OrderedRegisterList &RL;
const TargetRegisterInfo *TRI;
};
raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P) {
OS << '(';
OrderedRegisterList::const_iterator B = P.RL.begin(), E = P.RL.end();
for (OrderedRegisterList::const_iterator I = B; I != E; ++I) {
if (I != B)
OS << ", ";
OS << PrintReg(*I, P.TRI);
}
OS << ')';
return OS;
}
}
void OrderedRegisterList::insert(unsigned VR) {
iterator L = std::lower_bound(Seq.begin(), Seq.end(), VR, Ord);
if (L == Seq.end())
Seq.push_back(VR);
else
Seq.insert(L, VR);
}
void OrderedRegisterList::remove(unsigned VR) {
iterator L = std::lower_bound(Seq.begin(), Seq.end(), VR, Ord);
assert(L != Seq.end());
Seq.erase(L);
}
namespace {
struct IFRecord {
IFRecord(unsigned SR = 0, unsigned IR = 0, uint16_t W = 0, uint16_t O = 0)
: SrcR(SR), InsR(IR), Wdh(W), Off(O) {}
unsigned SrcR, InsR;
uint16_t Wdh, Off;
};
struct PrintIFR {
PrintIFR(const IFRecord &R, const TargetRegisterInfo *RI)
: IFR(R), TRI(RI) {}
private:
const IFRecord &IFR;
const TargetRegisterInfo *TRI;
friend raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P);
};
raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P) {
unsigned SrcR = P.IFR.SrcR, InsR = P.IFR.InsR;
OS << '(' << PrintReg(SrcR, P.TRI) << ',' << PrintReg(InsR, P.TRI)
<< ",#" << P.IFR.Wdh << ",#" << P.IFR.Off << ')';
return OS;
}
typedef std::pair<IFRecord,RegisterSet> IFRecordWithRegSet;
}
namespace llvm {
void initializeHexagonGenInsertPass(PassRegistry&);
FunctionPass *createHexagonGenInsert();
}
namespace {
class HexagonGenInsert : public MachineFunctionPass {
public:
static char ID;
HexagonGenInsert() : MachineFunctionPass(ID), HII(0), HRI(0) {
initializeHexagonGenInsertPass(*PassRegistry::getPassRegistry());
}
virtual const char *getPassName() const {
return "Hexagon generate \"insert\" instructions";
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<MachineDominatorTree>();
AU.addPreserved<MachineDominatorTree>();
MachineFunctionPass::getAnalysisUsage(AU);
}
virtual bool runOnMachineFunction(MachineFunction &MF);
private:
typedef DenseMap<std::pair<unsigned,unsigned>,unsigned> PairMapType;
void buildOrderingMF(RegisterOrdering &RO) const;
void buildOrderingBT(RegisterOrdering &RB, RegisterOrdering &RO) const;
bool isIntClass(const TargetRegisterClass *RC) const;
bool isConstant(unsigned VR) const;
bool isSmallConstant(unsigned VR) const;
bool isValidInsertForm(unsigned DstR, unsigned SrcR, unsigned InsR,
uint16_t L, uint16_t S) const;
bool findSelfReference(unsigned VR) const;
bool findNonSelfReference(unsigned VR) const;
void getInstrDefs(const MachineInstr *MI, RegisterSet &Defs) const;
void getInstrUses(const MachineInstr *MI, RegisterSet &Uses) const;
unsigned distance(const MachineBasicBlock *FromB,
const MachineBasicBlock *ToB, const UnsignedMap &RPO,
PairMapType &M) const;
unsigned distance(MachineBasicBlock::const_iterator FromI,
MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO,
PairMapType &M) const;
bool findRecordInsertForms(unsigned VR, OrderedRegisterList &AVs);
void collectInBlock(MachineBasicBlock *B, OrderedRegisterList &AVs);
void findRemovableRegisters(unsigned VR, IFRecord IF,
RegisterSet &RMs) const;
void computeRemovableRegisters();
void pruneEmptyLists();
void pruneCoveredSets(unsigned VR);
void pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO, PairMapType &M);
void pruneRegCopies(unsigned VR);
void pruneCandidates();
void selectCandidates();
bool generateInserts();
bool removeDeadCode(MachineDomTreeNode *N);
typedef std::vector<IFRecordWithRegSet> IFListType;
typedef DenseMap<unsigned,IFListType> IFMapType;
void dump_map() const;
const HexagonInstrInfo *HII;
const HexagonRegisterInfo *HRI;
MachineFunction *MFN;
MachineRegisterInfo *MRI;
MachineDominatorTree *MDT;
CellMapShadow *CMS;
RegisterOrdering BaseOrd;
RegisterOrdering CellOrd;
IFMapType IFMap;
};
char HexagonGenInsert::ID = 0;
}
void HexagonGenInsert::dump_map() const {
typedef IFMapType::const_iterator iterator;
for (iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
dbgs() << " " << PrintReg(I->first, HRI) << ":\n";
const IFListType &LL = I->second;
for (unsigned i = 0, n = LL.size(); i < n; ++i)
dbgs() << " " << PrintIFR(LL[i].first, HRI) << ", "
<< PrintRegSet(LL[i].second, HRI) << '\n';
}
}
void HexagonGenInsert::buildOrderingMF(RegisterOrdering &RO) const {
unsigned Index = 0;
typedef MachineFunction::const_iterator mf_iterator;
for (mf_iterator A = MFN->begin(), Z = MFN->end(); A != Z; ++A) {
const MachineBasicBlock &B = *A;
if (!CMS->BT.reached(&B))
continue;
typedef MachineBasicBlock::const_iterator mb_iterator;
for (mb_iterator I = B.begin(), E = B.end(); I != E; ++I) {
const MachineInstr *MI = &*I;
for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (MO.isReg() && MO.isDef()) {
unsigned R = MO.getReg();
assert(MO.getSubReg() == 0 && "Unexpected subregister in definition");
if (TargetRegisterInfo::isVirtualRegister(R))
RO.insert(std::make_pair(R, Index++));
}
}
}
}
}
void HexagonGenInsert::buildOrderingBT(RegisterOrdering &RB,
RegisterOrdering &RO) const {
BitValueOrdering BVO(RB);
RegisterCellLexCompare LexCmp(BVO, *CMS);
typedef std::vector<unsigned> SortableVectorType;
SortableVectorType VRs;
for (RegisterOrdering::iterator I = RB.begin(), E = RB.end(); I != E; ++I)
VRs.push_back(I->first);
std::sort(VRs.begin(), VRs.end(), LexCmp);
for (unsigned i = 0, n = VRs.size(); i < n; ++i)
RO.insert(std::make_pair(VRs[i], i));
}
inline bool HexagonGenInsert::isIntClass(const TargetRegisterClass *RC) const {
return RC == &Hexagon::IntRegsRegClass || RC == &Hexagon::DoubleRegsRegClass;
}
bool HexagonGenInsert::isConstant(unsigned VR) const {
const BitTracker::RegisterCell &RC = CMS->lookup(VR);
uint16_t W = RC.width();
for (uint16_t i = 0; i < W; ++i) {
const BitTracker::BitValue &BV = RC[i];
if (BV.is(0) || BV.is(1))
continue;
return false;
}
return true;
}
bool HexagonGenInsert::isSmallConstant(unsigned VR) const {
const BitTracker::RegisterCell &RC = CMS->lookup(VR);
uint16_t W = RC.width();
if (W > 64)
return false;
uint64_t V = 0, B = 1;
for (uint16_t i = 0; i < W; ++i) {
const BitTracker::BitValue &BV = RC[i];
if (BV.is(1))
V |= B;
else if (!BV.is(0))
return false;
B <<= 1;
}
if (W == 32)
return isInt<16>(V);
return isInt<8>(Lo_32(V)) && isInt<8>(Hi_32(V));
}
bool HexagonGenInsert::isValidInsertForm(unsigned DstR, unsigned SrcR,
unsigned InsR, uint16_t L, uint16_t S) const {
const TargetRegisterClass *DstRC = MRI->getRegClass(DstR);
const TargetRegisterClass *SrcRC = MRI->getRegClass(SrcR);
const TargetRegisterClass *InsRC = MRI->getRegClass(InsR);
if (!isIntClass(DstRC) || !isIntClass(SrcRC) || !isIntClass(InsRC))
return false;
if (DstRC != SrcRC)
return false;
if (DstRC == InsRC)
return true;
if (DstRC == &Hexagon::DoubleRegsRegClass)
return false;
if (S < 32 && S+L > 32)
return false;
return true;
}
bool HexagonGenInsert::findSelfReference(unsigned VR) const {
const BitTracker::RegisterCell &RC = CMS->lookup(VR);
for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
const BitTracker::BitValue &V = RC[i];
if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg == VR)
return true;
}
return false;
}
bool HexagonGenInsert::findNonSelfReference(unsigned VR) const {
BitTracker::RegisterCell RC = CMS->lookup(VR);
for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
const BitTracker::BitValue &V = RC[i];
if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != VR)
return true;
}
return false;
}
void HexagonGenInsert::getInstrDefs(const MachineInstr *MI,
RegisterSet &Defs) const {
for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.isDef())
continue;
unsigned R = MO.getReg();
if (!TargetRegisterInfo::isVirtualRegister(R))
continue;
Defs.insert(R);
}
}
void HexagonGenInsert::getInstrUses(const MachineInstr *MI,
RegisterSet &Uses) const {
for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.isUse())
continue;
unsigned R = MO.getReg();
if (!TargetRegisterInfo::isVirtualRegister(R))
continue;
Uses.insert(R);
}
}
unsigned HexagonGenInsert::distance(const MachineBasicBlock *FromB,
const MachineBasicBlock *ToB, const UnsignedMap &RPO,
PairMapType &M) const {
assert(FromB != ToB);
unsigned FromN = FromB->getNumber(), ToN = ToB->getNumber();
PairMapType::iterator F = M.find(std::make_pair(FromN, ToN));
if (F != M.end())
return F->second;
unsigned ToRPO = RPO.lookup(ToN);
unsigned MaxD = 0;
typedef MachineBasicBlock::const_pred_iterator pred_iterator;
for (pred_iterator I = ToB->pred_begin(), E = ToB->pred_end(); I != E; ++I) {
const MachineBasicBlock *PB = *I;
if (PB == FromB || RPO.lookup(PB->getNumber()) >= ToRPO)
continue;
unsigned D = PB->size() + distance(FromB, PB, RPO, M);
if (D > MaxD)
MaxD = D;
}
M.insert(std::make_pair(std::make_pair(FromN, ToN), MaxD));
return MaxD;
}
unsigned HexagonGenInsert::distance(MachineBasicBlock::const_iterator FromI,
MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO,
PairMapType &M) const {
const MachineBasicBlock *FB = FromI->getParent(), *TB = ToI->getParent();
if (FB == TB)
return std::distance(FromI, ToI);
unsigned D1 = std::distance(TB->begin(), ToI);
unsigned D2 = distance(FB, TB, RPO, M);
unsigned D3 = std::distance(FromI, FB->end());
return D1+D2+D3;
}
bool HexagonGenInsert::findRecordInsertForms(unsigned VR,
OrderedRegisterList &AVs) {
if (isDebug()) {
dbgs() << LLVM_FUNCTION_NAME << ": " << PrintReg(VR, HRI)
<< " AVs: " << PrintORL(AVs, HRI) << "\n";
}
if (AVs.size() == 0)
return false;
typedef OrderedRegisterList::iterator iterator;
BitValueOrdering BVO(BaseOrd);
const BitTracker::RegisterCell &RC = CMS->lookup(VR);
uint16_t W = RC.width();
typedef std::pair<unsigned,uint16_t> RSRecord; typedef std::vector<RSRecord> RSListType;
typedef DenseMap<unsigned,RSListType> LRSMapType;
LRSMapType LM;
for (uint16_t S = 0; S < W; ++S) {
iterator B = AVs.begin(), E = AVs.end();
uint16_t L;
for (L = 0; L < W-S; ++L) {
RegisterCellBitCompareSel RCB(VR, S+L, L, BVO, *CMS);
iterator NewB = std::lower_bound(B, E, VR, RCB);
iterator NewE = std::upper_bound(NewB, E, VR, RCB);
if (L > 0) {
for (iterator I = B; I != NewB; ++I)
LM[L].push_back(std::make_pair(*I, S));
for (iterator I = NewE; I != E; ++I)
LM[L].push_back(std::make_pair(*I, S));
}
B = NewB, E = NewE;
if (B == E)
break;
}
assert(B == E || L == W-S);
if (B != E) {
for (iterator I = B; I != E; ++I)
LM[L].push_back(std::make_pair(*I, S));
break;
}
}
if (isDebug()) {
dbgs() << "Prefixes matching register " << PrintReg(VR, HRI) << "\n";
for (LRSMapType::iterator I = LM.begin(), E = LM.end(); I != E; ++I) {
dbgs() << " L=" << I->first << ':';
const RSListType &LL = I->second;
for (unsigned i = 0, n = LL.size(); i < n; ++i)
dbgs() << " (" << PrintReg(LL[i].first, HRI) << ",@"
<< LL[i].second << ')';
dbgs() << '\n';
}
}
bool Recorded = false;
for (iterator I = AVs.begin(), E = AVs.end(); I != E; ++I) {
unsigned SrcR = *I;
int FDi = -1, LDi = -1; const BitTracker::RegisterCell &AC = CMS->lookup(SrcR);
uint16_t AW = AC.width();
for (uint16_t i = 0, w = std::min(W, AW); i < w; ++i) {
if (RC[i] == AC[i])
continue;
if (FDi == -1)
FDi = i;
LDi = i;
}
if (FDi == -1)
continue; uint16_t FD = FDi, LD = LDi; uint16_t MinL = LD-FD+1;
for (uint16_t L = MinL; L < W; ++L) {
LRSMapType::iterator F = LM.find(L);
if (F == LM.end())
continue;
RSListType &LL = F->second;
for (unsigned i = 0, n = LL.size(); i < n; ++i) {
uint16_t S = LL[i].second;
if (S > FD) continue;
uint16_t EL = L-MinL;
uint16_t LowS = (EL < FD) ? FD-EL : 0;
if (S < LowS) continue;
unsigned InsR = LL[i].first;
if (!isValidInsertForm(VR, SrcR, InsR, L, S))
continue;
if (isDebug()) {
dbgs() << PrintReg(VR, HRI) << " = insert(" << PrintReg(SrcR, HRI)
<< ',' << PrintReg(InsR, HRI) << ",#" << L << ",#"
<< S << ")\n";
}
IFRecordWithRegSet RR(IFRecord(SrcR, InsR, L, S), RegisterSet());
IFMap[VR].push_back(RR);
Recorded = true;
}
}
}
return Recorded;
}
void HexagonGenInsert::collectInBlock(MachineBasicBlock *B,
OrderedRegisterList &AVs) {
if (isDebug())
dbgs() << "visiting block BB#" << B->getNumber() << "\n";
if (!CMS->BT.reached(B))
return;
bool DoConst = OptConst;
RegisterSet BlockDefs, InsDefs;
for (MachineBasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
MachineInstr *MI = &*I;
InsDefs.clear();
getInstrDefs(MI, InsDefs);
bool Skip = MI->isCopy() || MI->isRegSequence();
if (!Skip) {
for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR)) {
if (!DoConst && isConstant(VR))
continue;
if (findSelfReference(VR) || isSmallConstant(VR))
continue;
findRecordInsertForms(VR, AVs);
}
}
for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR))
AVs.insert(VR);
BlockDefs.insert(InsDefs);
}
MachineDomTreeNode *N = MDT->getNode(B);
typedef GraphTraits<MachineDomTreeNode*> GTN;
typedef GTN::ChildIteratorType ChildIter;
for (ChildIter I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) {
MachineBasicBlock *SB = (*I)->getBlock();
collectInBlock(SB, AVs);
}
for (unsigned VR = BlockDefs.find_first(); VR; VR = BlockDefs.find_next(VR))
AVs.remove(VR);
}
void HexagonGenInsert::findRemovableRegisters(unsigned VR, IFRecord IF,
RegisterSet &RMs) const {
RegisterSet Regs[2];
unsigned S = 0; Regs[S].insert(VR);
while (!Regs[S].empty()) {
unsigned OtherS = 1-S;
Regs[OtherS].clear();
for (unsigned R = Regs[S].find_first(); R; R = Regs[S].find_next(R)) {
Regs[S].remove(R);
if (R == IF.SrcR || R == IF.InsR)
continue;
if (!findNonSelfReference(R))
continue;
RMs.insert(R);
const MachineInstr *DefI = MRI->getVRegDef(R);
assert(DefI);
if (DefI->isPHI())
continue;
getInstrUses(DefI, Regs[OtherS]);
}
S = OtherS;
}
RMs.remove(VR);
}
void HexagonGenInsert::computeRemovableRegisters() {
for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
IFListType &LL = I->second;
for (unsigned i = 0, n = LL.size(); i < n; ++i)
findRemovableRegisters(I->first, LL[i].first, LL[i].second);
}
}
void HexagonGenInsert::pruneEmptyLists() {
typedef SmallVector<IFMapType::iterator,16> IterListType;
IterListType Prune;
for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
if (I->second.size() == 0)
Prune.push_back(I);
}
for (unsigned i = 0, n = Prune.size(); i < n; ++i)
IFMap.erase(Prune[i]);
}
void HexagonGenInsert::pruneCoveredSets(unsigned VR) {
IFMapType::iterator F = IFMap.find(VR);
assert(F != IFMap.end());
IFListType &LL = F->second;
MachineInstr *DefVR = MRI->getVRegDef(VR);
bool DefEx = HII->isConstExtended(DefVR);
bool HasNE = false;
for (unsigned i = 0, n = LL.size(); i < n; ++i) {
if (LL[i].second.empty())
continue;
HasNE = true;
break;
}
if (!DefEx || HasNE) {
auto IsEmpty = [] (const IFRecordWithRegSet &IR) -> bool {
return IR.second.empty();
};
auto End = std::remove_if(LL.begin(), LL.end(), IsEmpty);
if (End != LL.end())
LL.erase(End, LL.end());
} else {
IFRecord MaxIF = LL[0].first;
for (unsigned i = 1, n = LL.size(); i < n; ++i) {
const IFRecord &IF = LL[i].first;
unsigned M0 = BaseOrd[MaxIF.SrcR], M1 = BaseOrd[MaxIF.InsR];
unsigned R0 = BaseOrd[IF.SrcR], R1 = BaseOrd[IF.InsR];
if (M0 > R0)
continue;
if (M0 == R0) {
if (M1 > R1)
continue;
if (M1 == R1) {
if (MaxIF.Wdh > IF.Wdh)
continue;
if (MaxIF.Wdh == IF.Wdh && MaxIF.Off >= IF.Off)
continue;
}
}
MaxIF = IF;
}
LL.clear();
LL.push_back(std::make_pair(MaxIF, RegisterSet()));
}
for (unsigned i = 0, n = LL.size(); i < n; ) {
const RegisterSet &RMi = LL[i].second;
unsigned j = 0;
while (j < n) {
if (j != i && LL[j].second.includes(RMi))
break;
j++;
}
if (j == n) { i++;
continue;
}
LL.erase(LL.begin()+i);
n = LL.size();
}
}
void HexagonGenInsert::pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO,
PairMapType &M) {
IFMapType::iterator F = IFMap.find(VR);
assert(F != IFMap.end());
IFListType &LL = F->second;
unsigned Cutoff = VRegDistCutoff;
const MachineInstr *DefV = MRI->getVRegDef(VR);
for (unsigned i = LL.size(); i > 0; --i) {
unsigned SR = LL[i-1].first.SrcR, IR = LL[i-1].first.InsR;
const MachineInstr *DefS = MRI->getVRegDef(SR);
const MachineInstr *DefI = MRI->getVRegDef(IR);
unsigned DSV = distance(DefS, DefV, RPO, M);
if (DSV < Cutoff) {
unsigned DIV = distance(DefI, DefV, RPO, M);
if (DIV < Cutoff)
continue;
}
LL.erase(LL.begin()+(i-1));
}
}
void HexagonGenInsert::pruneRegCopies(unsigned VR) {
IFMapType::iterator F = IFMap.find(VR);
assert(F != IFMap.end());
IFListType &LL = F->second;
auto IsCopy = [] (const IFRecordWithRegSet &IR) -> bool {
return IR.first.Wdh == 32 && (IR.first.Off == 0 || IR.first.Off == 32);
};
auto End = std::remove_if(LL.begin(), LL.end(), IsCopy);
if (End != LL.end())
LL.erase(End, LL.end());
}
void HexagonGenInsert::pruneCandidates() {
for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
pruneCoveredSets(I->first);
UnsignedMap RPO;
typedef ReversePostOrderTraversal<const MachineFunction*> RPOTType;
RPOTType RPOT(MFN);
unsigned RPON = 0;
for (RPOTType::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I)
RPO[(*I)->getNumber()] = RPON++;
PairMapType Memo; for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
pruneUsesTooFar(I->first, RPO, Memo);
pruneEmptyLists();
for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
pruneRegCopies(I->first);
}
namespace {
struct IFOrdering {
IFOrdering(const UnsignedMap &UC, const RegisterOrdering &BO)
: UseC(UC), BaseOrd(BO) {}
bool operator() (const IFRecordWithRegSet &A,
const IFRecordWithRegSet &B) const;
private:
void stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero,
unsigned &Sum) const;
const UnsignedMap &UseC;
const RegisterOrdering &BaseOrd;
};
}
bool IFOrdering::operator() (const IFRecordWithRegSet &A,
const IFRecordWithRegSet &B) const {
unsigned SizeA = 0, ZeroA = 0, SumA = 0;
unsigned SizeB = 0, ZeroB = 0, SumB = 0;
stats(A.second, SizeA, ZeroA, SumA);
stats(B.second, SizeB, ZeroB, SumB);
if (ZeroA != ZeroB)
return ZeroA > ZeroB;
uint64_t AvgA = SumA*SizeB, AvgB = SumB*SizeA;
if (AvgA != AvgB)
return AvgA < AvgB;
unsigned OSA = BaseOrd[A.first.SrcR], OSB = BaseOrd[B.first.SrcR];
if (OSA != OSB)
return OSA < OSB;
unsigned OIA = BaseOrd[A.first.InsR], OIB = BaseOrd[B.first.InsR];
if (OIA != OIB)
return OIA < OIB;
if (A.first.Wdh != B.first.Wdh)
return A.first.Wdh < B.first.Wdh;
return A.first.Off < B.first.Off;
}
void IFOrdering::stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero,
unsigned &Sum) const {
for (unsigned R = Rs.find_first(); R; R = Rs.find_next(R)) {
UnsignedMap::const_iterator F = UseC.find(R);
assert(F != UseC.end());
unsigned UC = F->second;
if (UC == 0)
Zero++;
Sum += UC;
Size++;
}
}
void HexagonGenInsert::selectCandidates() {
RegisterSet AllRMs;
UnsignedMap UseC, RemC;
IFMapType::iterator End = IFMap.end();
for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
const IFListType &LL = I->second;
RegisterSet TT;
for (unsigned i = 0, n = LL.size(); i < n; ++i)
TT.insert(LL[i].second);
for (unsigned R = TT.find_first(); R; R = TT.find_next(R))
RemC[R]++;
AllRMs.insert(TT);
}
for (unsigned R = AllRMs.find_first(); R; R = AllRMs.find_next(R)) {
typedef MachineRegisterInfo::use_nodbg_iterator use_iterator;
typedef SmallSet<const MachineInstr*,16> InstrSet;
InstrSet UIs;
use_iterator E = MRI->use_nodbg_end();
for (use_iterator I = MRI->use_nodbg_begin(R); I != E; ++I)
UIs.insert(I->getParent());
unsigned C = UIs.size();
unsigned D = RemC[R];
UseC[R] = (C > D) ? C-D : 0; }
bool SelectAll0 = OptSelectAll0, SelectHas0 = OptSelectHas0;
if (!SelectAll0 && !SelectHas0)
SelectAll0 = true;
IFOrdering IFO(UseC, BaseOrd);
for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
IFListType &LL = I->second;
if (LL.empty())
continue;
IFListType::iterator MinI = std::min_element(LL.begin(), LL.end(), IFO);
assert(MinI != LL.end());
IFRecordWithRegSet M = *MinI;
LL.clear();
RegisterSet Us;
const MachineInstr *DefI = MRI->getVRegDef(I->first);
getInstrUses(DefI, Us);
bool Accept = false;
if (SelectAll0) {
bool All0 = true;
for (unsigned R = Us.find_first(); R; R = Us.find_next(R)) {
if (UseC[R] == 0)
continue;
All0 = false;
break;
}
Accept = All0;
} else if (SelectHas0) {
bool Has0 = false;
for (unsigned R = Us.find_first(); R; R = Us.find_next(R)) {
if (UseC[R] != 0)
continue;
Has0 = true;
break;
}
Accept = Has0;
}
if (Accept)
LL.push_back(M);
}
AllRMs.clear();
for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
const IFListType &LL = I->second;
if (LL.size() > 0)
AllRMs.insert(LL[0].second);
}
for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
IFListType &LL = I->second;
if (LL.size() == 0)
continue;
unsigned SR = LL[0].first.SrcR, IR = LL[0].first.InsR;
if (AllRMs[SR] || AllRMs[IR])
LL.clear();
}
pruneEmptyLists();
}
bool HexagonGenInsert::generateInserts() {
UnsignedMap RegMap;
for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
unsigned VR = I->first;
const TargetRegisterClass *RC = MRI->getRegClass(VR);
unsigned NewVR = MRI->createVirtualRegister(RC);
RegMap[VR] = NewVR;
}
for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
MachineInstr *MI = MRI->getVRegDef(I->first);
MachineBasicBlock &B = *MI->getParent();
DebugLoc DL = MI->getDebugLoc();
unsigned NewR = RegMap[I->first];
bool R32 = MRI->getRegClass(NewR) == &Hexagon::IntRegsRegClass;
const MCInstrDesc &D = R32 ? HII->get(Hexagon::S2_insert)
: HII->get(Hexagon::S2_insertp);
IFRecord IF = I->second[0].first;
unsigned Wdh = IF.Wdh, Off = IF.Off;
unsigned InsS = 0;
if (R32 && MRI->getRegClass(IF.InsR) == &Hexagon::DoubleRegsRegClass) {
InsS = Hexagon::subreg_loreg;
if (Off >= 32) {
InsS = Hexagon::subreg_hireg;
Off -= 32;
}
}
MachineBasicBlock::iterator At = MI;
if (MI->isPHI())
At = B.getFirstNonPHI();
BuildMI(B, At, DL, D, NewR)
.addReg(IF.SrcR)
.addReg(IF.InsR, 0, InsS)
.addImm(Wdh)
.addImm(Off);
MRI->clearKillFlags(IF.SrcR);
MRI->clearKillFlags(IF.InsR);
}
for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
MachineInstr *DefI = MRI->getVRegDef(I->first);
MRI->replaceRegWith(I->first, RegMap[I->first]);
DefI->eraseFromParent();
}
return true;
}
bool HexagonGenInsert::removeDeadCode(MachineDomTreeNode *N) {
bool Changed = false;
typedef GraphTraits<MachineDomTreeNode*> GTN;
for (auto I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I)
Changed |= removeDeadCode(*I);
MachineBasicBlock *B = N->getBlock();
std::vector<MachineInstr*> Instrs;
for (auto I = B->rbegin(), E = B->rend(); I != E; ++I)
Instrs.push_back(&*I);
for (auto I = Instrs.begin(), E = Instrs.end(); I != E; ++I) {
MachineInstr *MI = *I;
unsigned Opc = MI->getOpcode();
if (Opc == TargetOpcode::LIFETIME_START ||
Opc == TargetOpcode::LIFETIME_END)
continue;
bool Store = false;
if (MI->isInlineAsm() || !MI->isSafeToMove(nullptr, Store))
continue;
bool AllDead = true;
SmallVector<unsigned,2> Regs;
for (ConstMIOperands Op(MI); Op.isValid(); ++Op) {
if (!Op->isReg() || !Op->isDef())
continue;
unsigned R = Op->getReg();
if (!TargetRegisterInfo::isVirtualRegister(R) ||
!MRI->use_nodbg_empty(R)) {
AllDead = false;
break;
}
Regs.push_back(R);
}
if (!AllDead)
continue;
B->erase(MI);
for (unsigned I = 0, N = Regs.size(); I != N; ++I)
MRI->markUsesInDebugValueAsUndef(Regs[I]);
Changed = true;
}
return Changed;
}
bool HexagonGenInsert::runOnMachineFunction(MachineFunction &MF) {
bool Timing = OptTiming, TimingDetail = Timing && OptTimingDetail;
bool Changed = false;
TimerGroup __G("hexinsert");
NamedRegionTimer __T("hexinsert", Timing && !TimingDetail);
assert(!OptSelectAll0 || !OptSelectHas0);
IFMap.clear();
BaseOrd.clear();
CellOrd.clear();
const auto &ST = MF.getSubtarget<HexagonSubtarget>();
HII = ST.getInstrInfo();
HRI = ST.getRegisterInfo();
MFN = &MF;
MRI = &MF.getRegInfo();
MDT = &getAnalysis<MachineDominatorTree>();
Changed = removeDeadCode(MDT->getRootNode());
const HexagonEvaluator HE(*HRI, *MRI, *HII, MF);
BitTracker BTLoc(HE, MF);
BTLoc.trace(isDebug());
BTLoc.run();
CellMapShadow MS(BTLoc);
CMS = &MS;
buildOrderingMF(BaseOrd);
buildOrderingBT(BaseOrd, CellOrd);
if (isDebug()) {
dbgs() << "Cell ordering:\n";
for (RegisterOrdering::iterator I = CellOrd.begin(), E = CellOrd.end();
I != E; ++I) {
unsigned VR = I->first, Pos = I->second;
dbgs() << PrintReg(VR, HRI) << " -> " << Pos << "\n";
}
}
MachineBasicBlock *RootB = MDT->getRoot();
OrderedRegisterList AvailR(CellOrd);
{
NamedRegionTimer _T("collection", "hexinsert", TimingDetail);
collectInBlock(RootB, AvailR);
computeRemovableRegisters();
}
if (isDebug()) {
dbgs() << "Candidates after collection:\n";
dump_map();
}
if (IFMap.empty())
return Changed;
{
NamedRegionTimer _T("pruning", "hexinsert", TimingDetail);
pruneCandidates();
}
if (isDebug()) {
dbgs() << "Candidates after pruning:\n";
dump_map();
}
if (IFMap.empty())
return Changed;
{
NamedRegionTimer _T("selection", "hexinsert", TimingDetail);
selectCandidates();
}
if (isDebug()) {
dbgs() << "Candidates after selection:\n";
dump_map();
}
if (VRegIndexCutoff.getPosition()) {
unsigned Cutoff = VRegIndexCutoff;
typedef SmallVector<IFMapType::iterator,16> IterListType;
IterListType Out;
for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
unsigned Idx = TargetRegisterInfo::virtReg2Index(I->first);
if (Idx >= Cutoff)
Out.push_back(I);
}
for (unsigned i = 0, n = Out.size(); i < n; ++i)
IFMap.erase(Out[i]);
}
if (IFMap.empty())
return Changed;
{
NamedRegionTimer _T("generation", "hexinsert", TimingDetail);
generateInserts();
}
return true;
}
FunctionPass *llvm::createHexagonGenInsert() {
return new HexagonGenInsert();
}
INITIALIZE_PASS_BEGIN(HexagonGenInsert, "hexinsert",
"Hexagon generate \"insert\" instructions", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_END(HexagonGenInsert, "hexinsert",
"Hexagon generate \"insert\" instructions", false, false)