summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Target/Hexagon/HexagonGenInsert.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Target/Hexagon/HexagonGenInsert.cpp')
-rw-r--r--llvm/lib/Target/Hexagon/HexagonGenInsert.cpp170
1 files changed, 84 insertions, 86 deletions
diff --git a/llvm/lib/Target/Hexagon/HexagonGenInsert.cpp b/llvm/lib/Target/Hexagon/HexagonGenInsert.cpp
index 6f2ccfb079c..5a8e392d127 100644
--- a/llvm/lib/Target/Hexagon/HexagonGenInsert.cpp
+++ b/llvm/lib/Target/Hexagon/HexagonGenInsert.cpp
@@ -9,29 +9,39 @@
#define DEBUG_TYPE "hexinsert"
+#include "BitTracker.h"
+#include "HexagonBitTracker.h"
+#include "HexagonInstrInfo.h"
+#include "HexagonRegisterInfo.h"
+#include "HexagonSubtarget.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/IR/Constants.h"
+#include "llvm/IR/DebugLoc.h"
#include "llvm/Pass.h"
-#include "llvm/PassRegistry.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
-#include "llvm/Support/Timer.h"
+#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetMachine.h"
+#include "llvm/Support/Timer.h"
#include "llvm/Target/TargetRegisterInfo.h"
-
-#include "Hexagon.h"
-#include "HexagonRegisterInfo.h"
-#include "HexagonTargetMachine.h"
-#include "HexagonBitTracker.h"
-
+#include <algorithm>
+#include <cassert>
+#include <cstdint>
+#include <iterator>
+#include <utility>
#include <vector>
using namespace llvm;
@@ -59,20 +69,18 @@ static cl::opt<bool> OptSelectHas0("insert-has0", cl::init(false), cl::Hidden,
static cl::opt<bool> OptConst("insert-const", cl::init(false), cl::Hidden,
cl::ZeroOrMore);
-namespace {
- // The preprocessor gets confused when the DEBUG macro is passed larger
- // chunks of code. Use this function to detect debugging.
- inline bool isDebug() {
+// The preprocessor gets confused when the DEBUG macro is passed larger
+// chunks of code. Use this function to detect debugging.
+inline static bool isDebug() {
#ifndef NDEBUG
- return ::llvm::DebugFlag && ::llvm::isCurrentDebugType(DEBUG_TYPE);
+ return DebugFlag && isCurrentDebugType(DEBUG_TYPE);
#else
- return false;
+ return false;
#endif
- }
}
-
namespace {
+
// Set of virtual registers, based on BitVector.
struct RegisterSet : private BitVector {
RegisterSet() = default;
@@ -146,20 +154,23 @@ namespace {
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;
@@ -172,14 +183,12 @@ namespace {
OS << " }";
return OS;
}
-}
-
-namespace {
// A convenience class to associate unsigned numbers (such as virtual
// registers) with unsigned numbers.
struct UnsignedMap : public DenseMap<unsigned,unsigned> {
- UnsignedMap() : BaseType() {}
+ UnsignedMap() = default;
+
private:
typedef DenseMap<unsigned,unsigned> BaseType;
};
@@ -190,22 +199,21 @@ namespace {
// by a potentially expensive comparison function, or obtained by a proce-
// dure that should not be repeated each time two registers are compared.
struct RegisterOrdering : public UnsignedMap {
- RegisterOrdering() : UnsignedMap() {}
+ RegisterOrdering() = default;
+
unsigned operator[](unsigned VR) const {
const_iterator F = find(VR);
assert(F != end());
return F->second;
}
+
// Add operator(), so that objects of this class can be used as
// comparators in std::sort et al.
bool operator() (unsigned VR1, unsigned VR2) const {
return operator[](VR1) < operator[](VR2);
}
};
-}
-
-namespace {
// Ordering of bit values. This class does not have operator[], but
// is supplies a comparison operator() for use in std:: algorithms.
// The order is as follows:
@@ -214,12 +222,14 @@ namespace {
// or ord(ref1.Reg) == ord(ref2.Reg), and ref1.Pos < ref2.Pos.
struct BitValueOrdering {
BitValueOrdering(const RegisterOrdering &RB) : BaseOrd(RB) {}
+
bool operator() (const BitTracker::BitValue &V1,
const BitTracker::BitValue &V2) const;
+
const RegisterOrdering &BaseOrd;
};
-}
+} // end anonymous namespace
bool BitValueOrdering::operator() (const BitTracker::BitValue &V1,
const BitTracker::BitValue &V2) const {
@@ -241,20 +251,21 @@ bool BitValueOrdering::operator() (const BitTracker::BitValue &V1,
return V1.RefI.Pos < V2.RefI.Pos;
}
-
namespace {
+
// Cache for the BitTracker's cell map. Map lookup has a logarithmic
// complexity, this class will memoize the lookup results to reduce
// the access time for repeated lookups of the same cell.
struct CellMapShadow {
CellMapShadow(const BitTracker &T) : BT(T) {}
+
const BitTracker::RegisterCell &lookup(unsigned VR) {
unsigned RInd = TargetRegisterInfo::virtReg2Index(VR);
// Grow the vector to at least 32 elements.
if (RInd >= CVect.size())
- CVect.resize(std::max(RInd+16, 32U), 0);
+ CVect.resize(std::max(RInd+16, 32U), nullptr);
const BitTracker::RegisterCell *CP = CVect[RInd];
- if (CP == 0)
+ if (CP == nullptr)
CP = CVect[RInd] = &BT.lookup(VR);
return *CP;
}
@@ -265,16 +276,15 @@ namespace {
typedef std::vector<const BitTracker::RegisterCell*> CellVectType;
CellVectType CVect;
};
-}
-
-namespace {
// Comparator class for lexicographic ordering of virtual registers
// according to the corresponding BitTracker::RegisterCell objects.
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;
@@ -290,15 +300,17 @@ namespace {
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;
};
-}
+} // end anonymous namespace
bool RegisterCellLexCompare::operator() (unsigned VR1, unsigned VR2) const {
// Ordering of registers, made up from two given orderings:
@@ -327,7 +339,6 @@ bool RegisterCellLexCompare::operator() (unsigned VR1, unsigned VR2) const {
return BitOrd.BaseOrd[VR1] < BitOrd.BaseOrd[VR2];
}
-
bool RegisterCellBitCompareSel::operator() (unsigned VR1, unsigned VR2) const {
if (VR1 == VR2)
return false;
@@ -353,18 +364,22 @@ bool RegisterCellBitCompareSel::operator() (unsigned VR1, unsigned VR2) const {
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();
}
@@ -378,16 +393,18 @@ namespace {
// Convenience function to convert an iterator to the corresponding index.
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;
@@ -404,8 +421,8 @@ namespace {
OS << ')';
return OS;
}
-}
+} // end anonymous namespace
void OrderedRegisterList::insert(unsigned VR) {
iterator L = std::lower_bound(Seq.begin(), Seq.end(), VR, Ord);
@@ -415,21 +432,21 @@ void OrderedRegisterList::insert(unsigned VR) {
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 {
+
// A record of the insert form. The fields correspond to the operands
// of the "insert" instruction:
// ... = insert(SrcR, InsR, #Wdh, #Off)
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;
};
@@ -437,10 +454,12 @@ namespace {
struct PrintIFR {
PrintIFR(const IFRecord &R, const TargetRegisterInfo *RI)
: IFR(R), TRI(RI) {}
+
private:
+ friend raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P);
+
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) {
@@ -451,31 +470,37 @@ namespace {
}
typedef std::pair<IFRecord,RegisterSet> IFRecordWithRegSet;
-}
+} // end anonymous namespace
namespace llvm {
+
void initializeHexagonGenInsertPass(PassRegistry&);
FunctionPass *createHexagonGenInsert();
-}
+} // end namespace llvm
namespace {
+
class HexagonGenInsert : public MachineFunctionPass {
public:
static char ID;
- HexagonGenInsert() : MachineFunctionPass(ID), HII(0), HRI(0) {
+
+ HexagonGenInsert() : MachineFunctionPass(ID), HII(nullptr), HRI(nullptr) {
initializeHexagonGenInsertPass(*PassRegistry::getPassRegistry());
}
- virtual StringRef getPassName() const {
+
+ StringRef getPassName() const override {
return "Hexagon generate \"insert\" instructions";
}
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<MachineDominatorTree>();
AU.addPreserved<MachineDominatorTree>();
MachineFunctionPass::getAnalysisUsage(AU);
}
- virtual bool runOnMachineFunction(MachineFunction &MF);
+
+ bool runOnMachineFunction(MachineFunction &MF) override;
private:
typedef DenseMap<std::pair<unsigned,unsigned>,unsigned> PairMapType;
@@ -533,8 +558,8 @@ namespace {
};
char HexagonGenInsert::ID = 0;
-}
+} // end anonymous namespace
void HexagonGenInsert::dump_map() const {
typedef IFMapType::const_iterator iterator;
@@ -547,7 +572,6 @@ void HexagonGenInsert::dump_map() const {
}
}
-
void HexagonGenInsert::buildOrderingMF(RegisterOrdering &RO) const {
unsigned Index = 0;
typedef MachineFunction::const_iterator mf_iterator;
@@ -574,7 +598,6 @@ void HexagonGenInsert::buildOrderingMF(RegisterOrdering &RO) const {
// in the map.
}
-
void HexagonGenInsert::buildOrderingBT(RegisterOrdering &RB,
RegisterOrdering &RO) const {
// Create a vector of all virtual registers (collect them from the base
@@ -591,12 +614,10 @@ void HexagonGenInsert::buildOrderingBT(RegisterOrdering &RB,
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();
@@ -609,7 +630,6 @@ bool HexagonGenInsert::isConstant(unsigned VR) const {
return true;
}
-
bool HexagonGenInsert::isSmallConstant(unsigned VR) const {
const BitTracker::RegisterCell &RC = CMS->lookup(VR);
uint16_t W = RC.width();
@@ -633,7 +653,6 @@ bool HexagonGenInsert::isSmallConstant(unsigned VR) const {
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);
@@ -656,7 +675,6 @@ bool HexagonGenInsert::isValidInsertForm(unsigned DstR, unsigned SrcR,
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) {
@@ -667,7 +685,6 @@ bool HexagonGenInsert::findSelfReference(unsigned VR) const {
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) {
@@ -678,7 +695,6 @@ bool HexagonGenInsert::findNonSelfReference(unsigned VR) const {
return false;
}
-
void HexagonGenInsert::getInstrDefs(const MachineInstr *MI,
RegisterSet &Defs) const {
for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
@@ -692,7 +708,6 @@ void HexagonGenInsert::getInstrDefs(const MachineInstr *MI,
}
}
-
void HexagonGenInsert::getInstrUses(const MachineInstr *MI,
RegisterSet &Uses) const {
for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
@@ -706,7 +721,6 @@ void HexagonGenInsert::getInstrUses(const MachineInstr *MI,
}
}
-
unsigned HexagonGenInsert::distance(const MachineBasicBlock *FromB,
const MachineBasicBlock *ToB, const UnsignedMap &RPO,
PairMapType &M) const {
@@ -740,7 +754,6 @@ unsigned HexagonGenInsert::distance(const MachineBasicBlock *FromB,
return MaxD;
}
-
unsigned HexagonGenInsert::distance(MachineBasicBlock::const_iterator FromI,
MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO,
PairMapType &M) const {
@@ -753,7 +766,6 @@ unsigned HexagonGenInsert::distance(MachineBasicBlock::const_iterator FromI,
return D1+D2+D3;
}
-
bool HexagonGenInsert::findRecordInsertForms(unsigned VR,
OrderedRegisterList &AVs) {
if (isDebug()) {
@@ -832,7 +844,6 @@ bool HexagonGenInsert::findRecordInsertForms(unsigned VR,
}
}
-
bool Recorded = false;
for (iterator I = AVs.begin(), E = AVs.end(); I != E; ++I) {
@@ -888,7 +899,6 @@ bool HexagonGenInsert::findRecordInsertForms(unsigned VR,
return Recorded;
}
-
void HexagonGenInsert::collectInBlock(MachineBasicBlock *B,
OrderedRegisterList &AVs) {
if (isDebug())
@@ -949,7 +959,6 @@ void HexagonGenInsert::collectInBlock(MachineBasicBlock *B,
AVs.remove(VR);
}
-
void HexagonGenInsert::findRemovableRegisters(unsigned VR, IFRecord IF,
RegisterSet &RMs) const {
// For a given register VR and a insert form, find the registers that are
@@ -1001,7 +1010,6 @@ void HexagonGenInsert::findRemovableRegisters(unsigned VR, IFRecord IF,
RMs.remove(VR);
}
-
void HexagonGenInsert::computeRemovableRegisters() {
for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
IFListType &LL = I->second;
@@ -1010,21 +1018,19 @@ void HexagonGenInsert::computeRemovableRegisters() {
}
}
-
void HexagonGenInsert::pruneEmptyLists() {
// Remove all entries from the map, where the register has no insert forms
// associated with it.
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)
+ if (I->second.empty())
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());
@@ -1052,7 +1058,7 @@ void HexagonGenInsert::pruneCoveredSets(unsigned VR) {
auto IsEmpty = [] (const IFRecordWithRegSet &IR) -> bool {
return IR.second.empty();
};
- auto End = remove_if(LL, IsEmpty);
+ auto End = llvm::remove_if(LL, IsEmpty);
if (End != LL.end())
LL.erase(End, LL.end());
} else {
@@ -1112,7 +1118,6 @@ void HexagonGenInsert::pruneCoveredSets(unsigned VR) {
}
}
-
void HexagonGenInsert::pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO,
PairMapType &M) {
IFMapType::iterator F = IFMap.find(VR);
@@ -1135,7 +1140,6 @@ void HexagonGenInsert::pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO,
}
}
-
void HexagonGenInsert::pruneRegCopies(unsigned VR) {
IFMapType::iterator F = IFMap.find(VR);
assert(F != IFMap.end());
@@ -1144,12 +1148,11 @@ void HexagonGenInsert::pruneRegCopies(unsigned VR) {
auto IsCopy = [] (const IFRecordWithRegSet &IR) -> bool {
return IR.first.Wdh == 32 && (IR.first.Off == 0 || IR.first.Off == 32);
};
- auto End = remove_if(LL, IsCopy);
+ auto End = llvm::remove_if(LL, IsCopy);
if (End != LL.end())
LL.erase(End, LL.end());
}
-
void HexagonGenInsert::pruneCandidates() {
// Remove candidates that are not beneficial, regardless of the final
// selection method.
@@ -1176,8 +1179,8 @@ void HexagonGenInsert::pruneCandidates() {
pruneRegCopies(I->first);
}
-
namespace {
+
// Class for comparing IF candidates for registers that have multiple of
// them. The smaller the candidate, according to this ordering, the better.
// First, compare the number of zeros in the associated potentially remova-
@@ -1189,16 +1192,19 @@ 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;
};
-}
+} // end anonymous namespace
bool IFOrdering::operator() (const IFRecordWithRegSet &A,
const IFRecordWithRegSet &B) const {
@@ -1228,7 +1234,6 @@ bool IFOrdering::operator() (const IFRecordWithRegSet &A,
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)) {
@@ -1242,7 +1247,6 @@ void IFOrdering::stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero,
}
}
-
void HexagonGenInsert::selectCandidates() {
// Some registers may have multiple valid candidates. Pick the best one
// (or decide not to use any).
@@ -1280,7 +1284,6 @@ void HexagonGenInsert::selectCandidates() {
UseC[R] = (C > D) ? C-D : 0; // doz
}
-
bool SelectAll0 = OptSelectAll0, SelectHas0 = OptSelectHas0;
if (!SelectAll0 && !SelectHas0)
SelectAll0 = true;
@@ -1345,12 +1348,12 @@ void HexagonGenInsert::selectCandidates() {
AllRMs.clear();
for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
const IFListType &LL = I->second;
- if (LL.size() > 0)
+ if (!LL.empty())
AllRMs.insert(LL[0].second);
}
for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
IFListType &LL = I->second;
- if (LL.size() == 0)
+ if (LL.empty())
continue;
unsigned SR = LL[0].first.SrcR, IR = LL[0].first.InsR;
if (AllRMs[SR] || AllRMs[IR])
@@ -1360,7 +1363,6 @@ void HexagonGenInsert::selectCandidates() {
pruneEmptyLists();
}
-
bool HexagonGenInsert::generateInserts() {
// Create a new register for each one from IFMap, and store them in the
// map.
@@ -1418,7 +1420,6 @@ bool HexagonGenInsert::generateInserts() {
return true;
}
-
bool HexagonGenInsert::removeDeadCode(MachineDomTreeNode *N) {
bool Changed = false;
typedef GraphTraits<MachineDomTreeNode*> GTN;
@@ -1467,7 +1468,6 @@ bool HexagonGenInsert::removeDeadCode(MachineDomTreeNode *N) {
return Changed;
}
-
bool HexagonGenInsert::runOnMachineFunction(MachineFunction &MF) {
if (skipFunction(*MF.getFunction()))
return false;
@@ -1586,12 +1586,10 @@ bool HexagonGenInsert::runOnMachineFunction(MachineFunction &MF) {
return true;
}
-
FunctionPass *llvm::createHexagonGenInsert() {
return new HexagonGenInsert();
}
-
//===----------------------------------------------------------------------===//
// Public Constructor Functions
//===----------------------------------------------------------------------===//
OpenPOWER on IntegriCloud