diff options
Diffstat (limited to 'llvm/lib')
-rw-r--r-- | llvm/lib/Target/Hexagon/RDFGraph.cpp | 116 | ||||
-rw-r--r-- | llvm/lib/Target/Hexagon/RDFGraph.h | 35 | ||||
-rw-r--r-- | llvm/lib/Target/Hexagon/RDFRegisters.cpp | 143 | ||||
-rw-r--r-- | llvm/lib/Target/Hexagon/RDFRegisters.h | 57 |
4 files changed, 272 insertions, 79 deletions
diff --git a/llvm/lib/Target/Hexagon/RDFGraph.cpp b/llvm/lib/Target/Hexagon/RDFGraph.cpp index 98744d5c8de..4b5c212a7f8 100644 --- a/llvm/lib/Target/Hexagon/RDFGraph.cpp +++ b/llvm/lib/Target/Hexagon/RDFGraph.cpp @@ -424,7 +424,7 @@ RegisterRef RefNode::getRegRef(const DataFlowGraph &G) const { if (NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef) return G.unpack(Ref.PR); assert(Ref.Op != nullptr); - return G.makeRegRef(Ref.Op->getReg(), Ref.Op->getSubReg()); + return G.makeRegRef(*Ref.Op); } // Set the register reference in the reference node directly (for references @@ -755,17 +755,6 @@ unsigned DataFlowGraph::DefStack::nextDown(unsigned P) const { // Register information. -// Get the list of references aliased to RR. Lane masks are ignored. -RegisterSet DataFlowGraph::getAliasSet(RegisterId Reg) const { - // Do not include RR in the alias set. - RegisterSet AS; - assert(TargetRegisterInfo::isPhysicalRegister(Reg)); - - for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI) - AS.insert(RegisterRef(*AI)); - return AS; -} - RegisterSet DataFlowGraph::getLandingPadLiveIns() const { RegisterSet LR; const Function &F = *MF.getFunction(); @@ -977,26 +966,34 @@ void DataFlowGraph::build(unsigned Options) { } RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const { - assert(TargetRegisterInfo::isPhysicalRegister(Reg)); + assert(PhysicalRegisterInfo::isRegMaskId(Reg) || + TargetRegisterInfo::isPhysicalRegister(Reg)); + assert(Reg != 0); if (Sub != 0) Reg = TRI.getSubReg(Reg, Sub); return RegisterRef(Reg); } +RegisterRef DataFlowGraph::makeRegRef(const MachineOperand &Op) const { + assert(Op.isReg() || Op.isRegMask()); + if (Op.isReg()) + return makeRegRef(Op.getReg(), Op.getSubReg()); + return RegisterRef(PRI.getRegMaskId(Op.getRegMask()), LaneBitmask::getAll()); +} + RegisterRef DataFlowGraph::normalizeRef(RegisterRef RR) const { // FIXME copied from RegisterAggr - RegisterId SuperReg = RR.Reg; - while (true) { - MCSuperRegIterator SR(SuperReg, &TRI, false); - if (!SR.isValid()) - break; - SuperReg = *SR; - } - - uint32_t Sub = TRI.getSubRegIndex(SuperReg, RR.Reg); - const TargetRegisterClass &RC = *TRI.getMinimalPhysRegClass(RR.Reg); - LaneBitmask SuperMask = RR.Mask & - TRI.composeSubRegIndexLaneMask(Sub, RC.LaneMask); + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) + return RR; + const TargetRegisterClass *RC = PRI.RegInfos[RR.Reg].RegClass; + LaneBitmask RCMask = RC != nullptr ? RC->LaneMask : LaneBitmask(0x00000001); + LaneBitmask Common = RR.Mask & RCMask; + + RegisterId SuperReg = PRI.RegInfos[RR.Reg].MaxSuper; +// Ex: IP/EIP/RIP +// assert(RC != nullptr || RR.Reg == SuperReg); + uint32_t Sub = PRI.getTRI().getSubRegIndex(SuperReg, RR.Reg); + LaneBitmask SuperMask = PRI.getTRI().composeSubRegIndexLaneMask(Sub, Common); return RegisterRef(SuperReg, SuperMask); } @@ -1012,7 +1009,7 @@ RegisterRef DataFlowGraph::restrictRef(RegisterRef AR, RegisterRef BR) const { #endif // This isn't strictly correct, because the overlap may happen in the // part masked out. - if (TRI.regsOverlap(AR.Reg, BR.Reg)) + if (PRI.alias(AR, BR)) return AR; return RegisterRef(); } @@ -1083,10 +1080,10 @@ void DataFlowGraph::pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { // Push the definition on the stack for the register and all aliases. // The def stack traversal in linkNodeUp will check the exact aliasing. DefM[RR.Reg].push(DA); - for (RegisterRef A : getAliasSet(RR.Reg /*FIXME? use RegisterRef*/)) { + for (RegisterId A : PRI.getAliasSet(RR.Reg)) { // Check that we don't push the same def twice. - assert(A != RR); - DefM[A.Reg].push(DA); + assert(A != RR.Reg); + DefM[A].push(DA); } // Mark all the related defs as visited. for (NodeAddr<NodeBase*> T : Rel) @@ -1223,20 +1220,26 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { if (In.isCall()) return true; // Is tail call? - if (In.isBranch()) + if (In.isBranch()) { for (const MachineOperand &Op : In.operands()) if (Op.isGlobal() || Op.isSymbol()) return true; + // Assume indirect branches are calls. This is for the purpose of + // keeping implicit operands, and so it won't hurt on intra-function + // indirect branches. + if (In.isIndirectBranch()) + return true; + } return false; }; auto isDefUndef = [this] (const MachineInstr &In, RegisterRef DR) -> bool { // This instruction defines DR. Check if there is a use operand that // would make DR live on entry to the instruction. - for (const MachineOperand &UseOp : In.operands()) { - if (!UseOp.isReg() || !UseOp.isUse() || UseOp.isUndef()) + for (const MachineOperand &Op : In.operands()) { + if (!Op.isReg() || Op.getReg() == 0 || !Op.isUse() || Op.isUndef()) continue; - RegisterRef UR = makeRegRef(UseOp.getReg(), UseOp.getSubReg()); + RegisterRef UR = makeRegRef(Op); if (PRI.alias(DR, UR)) return false; } @@ -1263,18 +1266,20 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { // defs that define registers that overlap, but it is not clear how to // interpret that in the absence of explicit defs. Overlapping explicit // defs are likely illegal already. - RegisterSet DoneDefs; + BitVector DoneDefs(TRI.getNumRegs()); // Process explicit defs first. for (unsigned OpN = 0; OpN < NumOps; ++OpN) { MachineOperand &Op = In.getOperand(OpN); if (!Op.isReg() || !Op.isDef() || Op.isImplicit()) continue; - RegisterRef RR = makeRegRef(Op.getReg(), Op.getSubReg()); + unsigned R = Op.getReg(); + if (!R || !TargetRegisterInfo::isPhysicalRegister(R)) + continue; uint16_t Flags = NodeAttrs::None; if (TOI.isPreserving(In, OpN)) { Flags |= NodeAttrs::Preserving; // If the def is preserving, check if it is also undefined. - if (isDefUndef(In, RR)) + if (isDefUndef(In, makeRegRef(Op))) Flags |= NodeAttrs::Undef; } if (TOI.isClobbering(In, OpN)) @@ -1285,7 +1290,25 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { Flags |= NodeAttrs::Dead; NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); SA.Addr->addMember(DA, *this); - DoneDefs.insert(RR); + assert(!DoneDefs.test(R)); + DoneDefs.set(R); + } + + // Process reg-masks (as clobbers). + BitVector DoneClobbers(TRI.getNumRegs()); + for (unsigned OpN = 0; OpN < NumOps; ++OpN) { + MachineOperand &Op = In.getOperand(OpN); + if (!Op.isRegMask()) + continue; + uint16_t Flags = NodeAttrs::Clobbering | NodeAttrs::Fixed | + NodeAttrs::Dead; + NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); + SA.Addr->addMember(DA, *this); + // Record all clobbered registers in DoneDefs. + const uint32_t *RM = Op.getRegMask(); + for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) + if (!(RM[i/32] & (1u << (i%32)))) + DoneClobbers.set(i); } // Process implicit defs, skipping those that have already been added @@ -1294,10 +1317,11 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { MachineOperand &Op = In.getOperand(OpN); if (!Op.isReg() || !Op.isDef() || !Op.isImplicit()) continue; - RegisterRef RR = makeRegRef(Op.getReg(), Op.getSubReg()); - if (!NeedsImplicit && !ImpDefs.count(RR)) + unsigned R = Op.getReg(); + if (!R || !TargetRegisterInfo::isPhysicalRegister(R) || DoneDefs.test(R)) continue; - if (DoneDefs.count(RR)) + RegisterRef RR = makeRegRef(Op); + if (!NeedsImplicit && !ImpDefs.count(RR)) continue; uint16_t Flags = NodeAttrs::None; if (TOI.isPreserving(In, OpN)) { @@ -1310,18 +1334,24 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { Flags |= NodeAttrs::Clobbering; if (TOI.isFixedReg(In, OpN)) Flags |= NodeAttrs::Fixed; - if (IsCall && Op.isDead()) + if (IsCall && Op.isDead()) { + if (DoneClobbers.test(R)) + continue; Flags |= NodeAttrs::Dead; + } NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); SA.Addr->addMember(DA, *this); - DoneDefs.insert(RR); + DoneDefs.set(R); } for (unsigned OpN = 0; OpN < NumOps; ++OpN) { MachineOperand &Op = In.getOperand(OpN); if (!Op.isReg() || !Op.isUse()) continue; - RegisterRef RR = makeRegRef(Op.getReg(), Op.getSubReg()); + unsigned R = Op.getReg(); + if (!R || !TargetRegisterInfo::isPhysicalRegister(R)) + continue; + RegisterRef RR = makeRegRef(Op); // Add implicit uses on return and call instructions, and on predicated // instructions regardless of whether or not they appear in the instruction // descriptor's list. diff --git a/llvm/lib/Target/Hexagon/RDFGraph.h b/llvm/lib/Target/Hexagon/RDFGraph.h index eae742016a6..a10dad58756 100644 --- a/llvm/lib/Target/Hexagon/RDFGraph.h +++ b/llvm/lib/Target/Hexagon/RDFGraph.h @@ -431,39 +431,6 @@ namespace rdf { uint32_t MaskId; }; - // Template class for a map translating uint32_t into arbitrary types. - // The map will act like an indexed set: upon insertion of a new object, - // it will automatically assign a new index to it. Index of 0 is treated - // as invalid and is never allocated. - template <typename T, unsigned N = 32> - struct IndexedSet { - IndexedSet() : Map() { Map.reserve(N); } - - T get(uint32_t Idx) const { - // Index Idx corresponds to Map[Idx-1]. - assert(Idx != 0 && !Map.empty() && Idx-1 < Map.size()); - return Map[Idx-1]; - } - - uint32_t insert(T Val) { - // Linear search. - auto F = llvm::find(Map, Val); - if (F != Map.end()) - return F - Map.begin() + 1; - Map.push_back(Val); - return Map.size(); // Return actual_index + 1. - } - - uint32_t find(T Val) const { - auto F = llvm::find(Map, Val); - assert(F != Map.end()); - return F - Map.begin(); - } - - private: - std::vector<T> Map; - }; - struct LaneMaskIndex : private IndexedSet<LaneBitmask> { LaneMaskIndex() = default; @@ -777,6 +744,7 @@ namespace rdf { } RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const; + RegisterRef makeRegRef(const MachineOperand &Op) const; RegisterRef normalizeRef(RegisterRef RR) const; RegisterRef restrictRef(RegisterRef AR, RegisterRef BR) const; @@ -842,7 +810,6 @@ namespace rdf { private: void reset(); - RegisterSet getAliasSet(RegisterId Reg) const; RegisterSet getLandingPadLiveIns() const; NodeAddr<NodeBase*> newNode(uint16_t Attrs); diff --git a/llvm/lib/Target/Hexagon/RDFRegisters.cpp b/llvm/lib/Target/Hexagon/RDFRegisters.cpp index 5cb8f9a12d4..fc5ad0aedb1 100644 --- a/llvm/lib/Target/Hexagon/RDFRegisters.cpp +++ b/llvm/lib/Target/Hexagon/RDFRegisters.cpp @@ -8,6 +8,7 @@ //===----------------------------------------------------------------------===// #include "RDFRegisters.h" +#include "llvm/ADT/BitVector.h" #include "llvm/CodeGen/MachineFunction.h" using namespace llvm; @@ -38,9 +39,38 @@ PhysicalRegisterInfo::PhysicalRegisterInfo(const TargetRegisterInfo &tri, SuperR = *S; RegInfos[R].MaxSuper = SuperR; } + + for (const uint32_t *RM : TRI.getRegMasks()) + RegMasks.insert(RM); + for (const MachineBasicBlock &B : mf) + for (const MachineInstr &In : B) + for (const MachineOperand &Op : In.operands()) + if (Op.isRegMask()) + RegMasks.insert(Op.getRegMask()); +} + +std::set<RegisterId> PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const { + // Do not include RR in the alias set. + std::set<RegisterId> AS; + assert(isRegMaskId(Reg) || TargetRegisterInfo::isPhysicalRegister(Reg)); + if (isRegMaskId(Reg)) { + // XXX SLOW + // XXX Add other regmasks to the set. + const uint32_t *MB = getRegMaskBits(Reg); + for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) { + if (MB[i/32] & (1u << (i%32))) + continue; + AS.insert(i); + } + return AS; + } + + for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI) + AS.insert(*AI); + return AS; } -bool PhysicalRegisterInfo::alias(RegisterRef RA, RegisterRef RB) const { +bool PhysicalRegisterInfo::aliasRR(RegisterRef RA, RegisterRef RB) const { assert(TargetRegisterInfo::isPhysicalRegister(RA.Reg)); assert(TargetRegisterInfo::isPhysicalRegister(RB.Reg)); MCRegUnitMaskIterator UMA(RA.Reg, &TRI); @@ -92,7 +122,73 @@ bool PhysicalRegisterInfo::alias(RegisterRef RA, RegisterRef RB) const { return false; } +bool PhysicalRegisterInfo::aliasRM(RegisterRef RR, RegisterRef RM) const { + assert(TargetRegisterInfo::isPhysicalRegister(RR.Reg) && isRegMaskId(RM.Reg)); + const uint32_t *MB = getRegMaskBits(RM.Reg); + bool Preserved = MB[RR.Reg/32] & (1u << (RR.Reg%32)); + // If the lane mask information is "full", e.g. when the given lane mask + // is a superset of the lane mask from the register class, check the regmask + // bit directly. + if (RR.Mask == LaneBitmask::getAll()) + return Preserved; + const TargetRegisterClass *RC = RegInfos[RR.Reg].RegClass; + if (RC != nullptr && (RR.Mask & RC->LaneMask) == RC->LaneMask) + return Preserved; + + // Otherwise, check all subregisters whose lane mask overlaps the given + // mask. For each such register, if it is preserved by the regmask, then + // clear the corresponding bits in the given mask. If at the end, all + // bits have been cleared, the register does not alias the regmask (i.e. + // is it preserved by it). + LaneBitmask M = RR.Mask; + for (MCSubRegIndexIterator SI(RR.Reg, &TRI); SI.isValid(); ++SI) { + LaneBitmask SM = TRI.getSubRegIndexLaneMask(SI.getSubRegIndex()); + if ((SM & RR.Mask).none()) + continue; + unsigned SR = SI.getSubReg(); + if (!(MB[SR/32] & (1u << (SR%32)))) + continue; + // The subregister SR is preserved. + M &= ~SM; + if (M.none()) + return false; + } + + return true; +} + +bool PhysicalRegisterInfo::aliasMM(RegisterRef RM, RegisterRef RN) const { + assert(isRegMaskId(RM.Reg) && isRegMaskId(RN.Reg)); + unsigned NumRegs = TRI.getNumRegs(); + const uint32_t *BM = getRegMaskBits(RM.Reg); + const uint32_t *BN = getRegMaskBits(RN.Reg); + + for (unsigned w = 0, nw = NumRegs/32; w != nw; ++w) { + // Intersect the negations of both words. Disregard reg=0, + // i.e. 0th bit in the 0th word. + uint32_t C = ~BM[w] & ~BN[w]; + if (w == 0) + C &= ~1; + if (C) + return true; + } + + // Check the remaining registers in the last word. + unsigned TailRegs = NumRegs % 32; + if (TailRegs == 0) + return false; + unsigned TW = NumRegs / 32; + uint32_t TailMask = (1u << TailRegs) - 1; + if (~BM[TW] & ~BN[TW] & TailMask) + return true; + + return false; +} + + RegisterRef RegisterAggr::normalize(RegisterRef RR) const { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) + return RR; const TargetRegisterClass *RC = PRI.RegInfos[RR.Reg].RegClass; LaneBitmask RCMask = RC != nullptr ? RC->LaneMask : LaneBitmask(0x00000001); LaneBitmask Common = RR.Mask & RCMask; @@ -106,6 +202,17 @@ RegisterRef RegisterAggr::normalize(RegisterRef RR) const { } bool RegisterAggr::hasAliasOf(RegisterRef RR) const { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { + // XXX SLOW + const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); + for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { + if (MB[i/32] & (1u << (i%32))) + continue; + if (hasAliasOf(RegisterRef(i, LaneBitmask::getAll()))) + return true; + } + } + RegisterRef NR = normalize(RR); auto F = Masks.find(NR.Reg); if (F != Masks.end()) { @@ -121,6 +228,18 @@ bool RegisterAggr::hasAliasOf(RegisterRef RR) const { } bool RegisterAggr::hasCoverOf(RegisterRef RR) const { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { + // XXX SLOW + const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); + for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { + if (MB[i/32] & (1u << (i%32))) + continue; + if (!hasCoverOf(RegisterRef(i, LaneBitmask::getAll()))) + return false; + } + return true; + } + // Always have a cover for empty lane mask. RegisterRef NR = normalize(RR); if (NR.Mask.none()) @@ -132,6 +251,17 @@ bool RegisterAggr::hasCoverOf(RegisterRef RR) const { } RegisterAggr &RegisterAggr::insert(RegisterRef RR) { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { + // XXX SLOW + const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); + for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { + if (MB[i/32] & (1u << (i%32))) + continue; + insert(RegisterRef(i, LaneBitmask::getAll())); + } + return *this; + } + RegisterRef NR = normalize(RR); auto F = Masks.find(NR.Reg); if (F == Masks.end()) @@ -160,6 +290,17 @@ RegisterAggr &RegisterAggr::insert(const RegisterAggr &RG) { } RegisterAggr &RegisterAggr::clear(RegisterRef RR) { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { + // XXX SLOW + const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); + for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { + if (MB[i/32] & (1u << (i%32))) + continue; + clear(RegisterRef(i, LaneBitmask::getAll())); + } + return *this; + } + RegisterRef NR = normalize(RR); auto F = Masks.find(NR.Reg); if (F == Masks.end()) diff --git a/llvm/lib/Target/Hexagon/RDFRegisters.h b/llvm/lib/Target/Hexagon/RDFRegisters.h index fbeea2150b6..bad0e70091a 100644 --- a/llvm/lib/Target/Hexagon/RDFRegisters.h +++ b/llvm/lib/Target/Hexagon/RDFRegisters.h @@ -13,6 +13,7 @@ #include "llvm/ADT/BitVector.h" #include "llvm/Target/TargetRegisterInfo.h" +#include <set> #include <unordered_map> #include <vector> @@ -21,6 +22,39 @@ namespace rdf { typedef uint32_t RegisterId; + // Template class for a map translating uint32_t into arbitrary types. + // The map will act like an indexed set: upon insertion of a new object, + // it will automatically assign a new index to it. Index of 0 is treated + // as invalid and is never allocated. + template <typename T, unsigned N = 32> + struct IndexedSet { + IndexedSet() : Map() { Map.reserve(N); } + + T get(uint32_t Idx) const { + // Index Idx corresponds to Map[Idx-1]. + assert(Idx != 0 && !Map.empty() && Idx-1 < Map.size()); + return Map[Idx-1]; + } + + uint32_t insert(T Val) { + // Linear search. + auto F = llvm::find(Map, Val); + if (F != Map.end()) + return F - Map.begin() + 1; + Map.push_back(Val); + return Map.size(); // Return actual_index + 1. + } + + uint32_t find(T Val) const { + auto F = llvm::find(Map, Val); + assert(F != Map.end()); + return F - Map.begin() + 1; + } + + private: + std::vector<T> Map; + }; + struct RegisterRef { RegisterId Reg = 0; LaneBitmask Mask = LaneBitmask::getNone(); @@ -48,7 +82,22 @@ namespace rdf { PhysicalRegisterInfo(const TargetRegisterInfo &tri, const MachineFunction &mf); - bool alias(RegisterRef RA, RegisterRef RB) const; + static bool isRegMaskId(RegisterId R) { + return TargetRegisterInfo::isStackSlot(R); + } + RegisterId getRegMaskId(const uint32_t *RM) const { + return TargetRegisterInfo::index2StackSlot(RegMasks.find(RM)); + } + const uint32_t *getRegMaskBits(RegisterId R) const { + return RegMasks.get(TargetRegisterInfo::stackSlot2Index(R)); + } + + bool alias(RegisterRef RA, RegisterRef RB) const { + if (!isRegMaskId(RA.Reg)) + return !isRegMaskId(RB.Reg) ? aliasRR(RA, RB) : aliasRM(RA, RB); + return !isRegMaskId(RB.Reg) ? aliasRM(RB, RA) : aliasMM(RA, RB); + } + std::set<RegisterId> getAliasSet(RegisterId Reg) const; const TargetRegisterInfo &getTRI() const { return TRI; } @@ -60,6 +109,11 @@ namespace rdf { const TargetRegisterInfo &TRI; std::vector<RegInfo> RegInfos; + IndexedSet<const uint32_t*> RegMasks; + + bool aliasRR(RegisterRef RA, RegisterRef RB) const; + bool aliasRM(RegisterRef RR, RegisterRef RM) const; + bool aliasMM(RegisterRef RM, RegisterRef RN) const; }; @@ -101,6 +155,7 @@ namespace rdf { const PhysicalRegisterInfo &PRI; }; + // Optionally print the lane mask, if it is not ~0. struct PrintLaneMaskOpt { PrintLaneMaskOpt(LaneBitmask M) : Mask(M) {} |