diff options
Diffstat (limited to 'contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp')
| -rw-r--r-- | contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp | 390 |
1 files changed, 180 insertions, 210 deletions
diff --git a/contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp b/contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp index bd5bb9c..8f070d8 100644 --- a/contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp +++ b/contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp @@ -85,78 +85,33 @@ // implicit uses will be added later, after predication. The extra price, // however, is that finding the locations where the implicit uses need // to be added, and updating the live ranges will be more involved. -// -// An additional problem appears when subregister liveness tracking is -// enabled. In such a scenario, the live interval for the super-register -// will have live ranges for each subregister (i.e. subranges). This sub- -// range contains all liveness information about the subregister, except -// for one case: a "read-undef" flag from another subregister will not -// be reflected: given -// vreg1:subreg_hireg<def,read-undef> = ... ; "undefines" subreg_loreg -// the subrange for subreg_loreg will not have any indication that it is -// undefined at this point. Calculating subregister liveness based only -// on the information from the subrange may create a segment which spans -// over such a "read-undef" flag. This would create inconsistencies in -// the liveness data, resulting in assertions or incorrect code. -// Example: -// vreg1:subreg_loreg<def> = ... -// vreg1:subreg_hireg<def, read-undef> = ... ; "undefines" subreg_loreg -// ... -// vreg1:subreg_loreg<def> = A2_tfrt ... ; may end up with imp-use -// ; of subreg_loreg -// The remedy takes advantage of the fact, that at this point we have -// an unconditional definition of the subregister. What this means is -// that any preceding value in this subregister will be overwritten, -// or in other words, the last use before this def is a kill. This also -// implies that the first of the predicated transfers at this location -// should not have any implicit uses. -// Assume for a moment that no part of the corresponding super-register -// is used as a source. In such case, the entire super-register can be -// considered undefined immediately before this instruction. Because of -// that, we can insert an IMPLICIT_DEF of the super-register at this -// location, which will cause it to be reflected in all the associated -// subranges. What is important here is that if an IMPLICIT_DEF of -// subreg_loreg was used, we would lose the indication that subreg_hireg -// is also considered undefined. This could lead to having implicit uses -// incorrectly added. -// -// What is left is the two cases when the super-register is used as a -// source. -// * Case 1: the used part is the same as the one that is defined: -// vreg1<def> = ... -// ... -// vreg1:subreg_loreg<def,read-undef> = C2_mux ..., vreg1:subreg_loreg -// In the end, the subreg_loreg should be marked as live at the point of -// the splitting: -// vreg1:subreg_loreg<def,read-undef> = A2_tfrt ; should have imp-use -// vreg1:subreg_loreg<def,read-undef> = A2_tfrf ; should have imp-use -// Hence, an IMPLICIT_DEF of only vreg1:subreg_hireg would be sufficient. -// * Case 2: the used part does not overlap the part being defined: -// vreg1<def> = ... -// ... -// vreg1:subreg_loreg<def,read-undef> = C2_mux ..., vreg1:subreg_hireg -// For this case, we insert an IMPLICIT_DEF of vreg1:subreg_hireg after -// the C2_mux. #define DEBUG_TYPE "expand-condsets" -#include "HexagonTargetMachine.h" +#include "HexagonInstrInfo.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SetVector.h" -#include "llvm/CodeGen/Passes.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" #include "llvm/CodeGen/LiveInterval.h" #include "llvm/CodeGen/LiveIntervalAnalysis.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/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/IR/DebugLoc.h" +#include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" - -#include <algorithm> +#include "llvm/Target/TargetRegisterInfo.h" +#include <cassert> #include <iterator> #include <set> #include <utility> @@ -169,17 +124,21 @@ static cl::opt<unsigned> OptCoaLimit("expand-condsets-coa-limit", cl::init(~0U), cl::Hidden, cl::desc("Max number of segment coalescings")); namespace llvm { + void initializeHexagonExpandCondsetsPass(PassRegistry&); FunctionPass *createHexagonExpandCondsets(); -} + +} // end namespace llvm namespace { + class HexagonExpandCondsets : public MachineFunctionPass { public: static char ID; + HexagonExpandCondsets() : - MachineFunctionPass(ID), HII(0), TRI(0), MRI(0), - LIS(0), CoaLimitActive(false), + MachineFunctionPass(ID), HII(nullptr), TRI(nullptr), MRI(nullptr), + LIS(nullptr), CoaLimitActive(false), TfrLimitActive(false), CoaCounter(0), TfrCounter(0) { if (OptCoaLimit.getPosition()) CoaLimitActive = true, CoaLimit = OptCoaLimit; @@ -188,9 +147,8 @@ namespace { initializeHexagonExpandCondsetsPass(*PassRegistry::getPassRegistry()); } - const char *getPassName() const override { - return "Hexagon Expand Condsets"; - } + StringRef getPassName() const override { return "Hexagon Expand Condsets"; } + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired<LiveIntervals>(); AU.addPreserved<LiveIntervals>(); @@ -199,6 +157,7 @@ namespace { AU.addPreserved<MachineDominatorTree>(); MachineFunctionPass::getAnalysisUsage(AU); } + bool runOnMachineFunction(MachineFunction &MF) override; private: @@ -207,7 +166,6 @@ namespace { MachineDominatorTree *MDT; MachineRegisterInfo *MRI; LiveIntervals *LIS; - std::set<MachineInstr*> LocalImpDefs; bool CoaLimitActive, TfrLimitActive; unsigned CoaLimit, TfrLimit, CoaCounter, TfrCounter; @@ -216,6 +174,7 @@ namespace { RegisterRef(const MachineOperand &Op) : Reg(Op.getReg()), Sub(Op.getSubReg()) {} RegisterRef(unsigned R = 0, unsigned S = 0) : Reg(R), Sub(S) {} + bool operator== (RegisterRef RR) const { return Reg == RR.Reg && Sub == RR.Sub; } @@ -223,6 +182,7 @@ namespace { bool operator< (RegisterRef RR) const { return Reg < RR.Reg || (Reg == RR.Reg && Sub < RR.Sub); } + unsigned Reg, Sub; }; @@ -236,7 +196,6 @@ namespace { void addRefToMap(RegisterRef RR, ReferenceMap &Map, unsigned Exec); bool isRefInMap(RegisterRef, ReferenceMap &Map, unsigned Exec); - void removeImpDefSegments(LiveRange &Range); void updateDeadsInRange(unsigned Reg, LaneBitmask LM, LiveRange &Range); void updateKillFlags(unsigned Reg); void updateDeadFlags(unsigned Reg); @@ -251,7 +210,6 @@ namespace { unsigned DstSR, const MachineOperand &PredOp, bool PredSense, bool ReadUndef, bool ImpUse); bool split(MachineInstr &MI, std::set<unsigned> &UpdRegs); - bool splitInBlock(MachineBasicBlock &B, std::set<unsigned> &UpdRegs); bool isPredicable(MachineInstr *MI); MachineInstr *getReachingDefForPred(RegisterRef RD, @@ -272,12 +230,20 @@ namespace { bool isIntReg(RegisterRef RR, unsigned &BW); bool isIntraBlocks(LiveInterval &LI); bool coalesceRegisters(RegisterRef R1, RegisterRef R2); - bool coalesceSegments(MachineFunction &MF); + bool coalesceSegments(const SmallVectorImpl<MachineInstr*> &Condsets, + std::set<unsigned> &UpdRegs); }; -} + +} // end anonymous namespace char HexagonExpandCondsets::ID = 0; +namespace llvm { + + char &HexagonExpandCondsetsID = HexagonExpandCondsets::ID; + +} // end namespace llvm + INITIALIZE_PASS_BEGIN(HexagonExpandCondsets, "expand-condsets", "Hexagon Expand Condsets", false, false) INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) @@ -288,9 +254,11 @@ INITIALIZE_PASS_END(HexagonExpandCondsets, "expand-condsets", unsigned HexagonExpandCondsets::getMaskForSub(unsigned Sub) { switch (Sub) { - case Hexagon::subreg_loreg: + case Hexagon::isub_lo: + case Hexagon::vsub_lo: return Sub_Low; - case Hexagon::subreg_hireg: + case Hexagon::isub_hi: + case Hexagon::vsub_hi: return Sub_High; case Hexagon::NoSubRegister: return Sub_None; @@ -305,21 +273,19 @@ bool HexagonExpandCondsets::isCondset(const MachineInstr &MI) { case Hexagon::C2_muxii: case Hexagon::C2_muxir: case Hexagon::C2_muxri: - case Hexagon::MUX64_rr: + case Hexagon::PS_pselect: return true; break; } return false; } - LaneBitmask HexagonExpandCondsets::getLaneMask(unsigned Reg, unsigned Sub) { assert(TargetRegisterInfo::isVirtualRegister(Reg)); return Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub) : MRI->getMaxLaneMaskForVReg(Reg); } - void HexagonExpandCondsets::addRefToMap(RegisterRef RR, ReferenceMap &Map, unsigned Exec) { unsigned Mask = getMaskForSub(RR.Sub) | Exec; @@ -330,7 +296,6 @@ void HexagonExpandCondsets::addRefToMap(RegisterRef RR, ReferenceMap &Map, F->second |= Mask; } - bool HexagonExpandCondsets::isRefInMap(RegisterRef RR, ReferenceMap &Map, unsigned Exec) { ReferenceMap::iterator F = Map.find(RR.Reg); @@ -342,7 +307,6 @@ bool HexagonExpandCondsets::isRefInMap(RegisterRef RR, ReferenceMap &Map, return false; } - void HexagonExpandCondsets::updateKillFlags(unsigned Reg) { auto KillAt = [this,Reg] (SlotIndex K, LaneBitmask LM) -> void { // Set the <kill> flag on a use of Reg whose lane mask is contained in LM. @@ -392,16 +356,6 @@ void HexagonExpandCondsets::updateKillFlags(unsigned Reg) { } } - -void HexagonExpandCondsets::removeImpDefSegments(LiveRange &Range) { - auto StartImpDef = [this] (LiveRange::Segment &S) -> bool { - return S.start.isRegister() && - LocalImpDefs.count(LIS->getInstructionFromIndex(S.start)); - }; - Range.segments.erase(std::remove_if(Range.begin(), Range.end(), StartImpDef), - Range.end()); -} - void HexagonExpandCondsets::updateDeadsInRange(unsigned Reg, LaneBitmask LM, LiveRange &Range) { assert(TargetRegisterInfo::isVirtualRegister(Reg)); @@ -415,7 +369,7 @@ void HexagonExpandCondsets::updateDeadsInRange(unsigned Reg, LaneBitmask LM, if (!TargetRegisterInfo::isVirtualRegister(DR) || DR != Reg) return false; LaneBitmask SLM = getLaneMask(DR, DSR); - return (SLM & LM) != 0; + return (SLM & LM).any(); }; // The splitting step will create pairs of predicated definitions without @@ -425,7 +379,6 @@ void HexagonExpandCondsets::updateDeadsInRange(unsigned Reg, LaneBitmask LM, // We need to identify predicated defs that need implicit uses, and // dead defs that are not really dead, and correct both problems. - SetVector<MachineBasicBlock*> Defs; auto Dominate = [this] (SetVector<MachineBasicBlock*> &Defs, MachineBasicBlock *Dest) -> bool { for (MachineBasicBlock *D : Defs) @@ -449,20 +402,25 @@ void HexagonExpandCondsets::updateDeadsInRange(unsigned Reg, LaneBitmask LM, // First, try to extend live range within individual basic blocks. This // will leave us only with dead defs that do not reach any predicated // defs in the same block. + SetVector<MachineBasicBlock*> Defs; SmallVector<SlotIndex,4> PredDefs; for (auto &Seg : Range) { if (!Seg.start.isRegister()) continue; MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start); - if (LocalImpDefs.count(DefI)) - continue; Defs.insert(DefI->getParent()); if (HII->isPredicated(*DefI)) PredDefs.push_back(Seg.start); } + + SmallVector<SlotIndex,8> Undefs; + LiveInterval &LI = LIS->getInterval(Reg); + LI.computeSubRangeUndefs(Undefs, LM, *MRI, *LIS->getSlotIndexes()); + for (auto &SI : PredDefs) { MachineBasicBlock *BB = LIS->getMBBFromIndex(SI); - if (Range.extendInBlock(LIS->getMBBStartIdx(BB), SI)) + auto P = Range.extendInBlock(Undefs, LIS->getMBBStartIdx(BB), SI); + if (P.first != nullptr || P.second) SI = SlotIndex(); } @@ -476,10 +434,21 @@ void HexagonExpandCondsets::updateDeadsInRange(unsigned Reg, LaneBitmask LM, if (BB->pred_empty()) continue; // If the defs from this range reach SI via all predecessors, it is live. + // It can happen that SI is reached by the defs through some paths, but + // not all. In the IR coming into this optimization, SI would not be + // considered live, since the defs would then not jointly dominate SI. + // That means that SI is an overwriting def, and no implicit use is + // needed at this point. Do not add SI to the extension points, since + // extendToIndices will abort if there is no joint dominance. + // If the abort was avoided by adding extra undefs added to Undefs, + // extendToIndices could actually indicate that SI is live, contrary + // to the original IR. if (Dominate(Defs, BB)) ExtTo.push_back(SI); } - LIS->extendToIndices(Range, ExtTo); + + if (!ExtTo.empty()) + LIS->extendToIndices(Range, ExtTo, Undefs); // Remove <dead> flags from all defs that are not dead after live range // extension, and collect all def operands. They will be used to generate @@ -489,8 +458,6 @@ void HexagonExpandCondsets::updateDeadsInRange(unsigned Reg, LaneBitmask LM, if (!Seg.start.isRegister()) continue; MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start); - if (LocalImpDefs.count(DefI)) - continue; for (auto &Op : DefI->operands()) { if (Seg.start.isDead() || !IsRegDef(Op)) continue; @@ -499,40 +466,34 @@ void HexagonExpandCondsets::updateDeadsInRange(unsigned Reg, LaneBitmask LM, } } - // Finally, add implicit uses to each predicated def that is reached - // by other defs. Remove segments started by implicit-defs first, since - // they do not define registers. - removeImpDefSegments(Range); - + // by other defs. for (auto &Seg : Range) { if (!Seg.start.isRegister() || !Range.liveAt(Seg.start.getPrevSlot())) continue; MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start); if (!HII->isPredicated(*DefI)) continue; - MachineFunction &MF = *DefI->getParent()->getParent(); // Construct the set of all necessary implicit uses, based on the def // operands in the instruction. std::set<RegisterRef> ImpUses; for (auto &Op : DefI->operands()) if (Op.isReg() && Op.isDef() && DefRegs.count(Op)) ImpUses.insert(Op); + if (ImpUses.empty()) + continue; + MachineFunction &MF = *DefI->getParent()->getParent(); for (RegisterRef R : ImpUses) MachineInstrBuilder(MF, DefI).addReg(R.Reg, RegState::Implicit, R.Sub); } } - void HexagonExpandCondsets::updateDeadFlags(unsigned Reg) { LiveInterval &LI = LIS->getInterval(Reg); if (LI.hasSubRanges()) { for (LiveInterval::SubRange &S : LI.subranges()) { updateDeadsInRange(Reg, S.LaneMask, S); LIS->shrinkToUses(S, Reg); - // LI::shrinkToUses will add segments started by implicit-defs. - // Remove them again. - removeImpDefSegments(S); } LI.clear(); LIS->constructMainRangeFromSubranges(LI); @@ -541,7 +502,6 @@ void HexagonExpandCondsets::updateDeadFlags(unsigned Reg) { } } - void HexagonExpandCondsets::recalculateLiveInterval(unsigned Reg) { LIS->removeInterval(Reg); LIS->createAndComputeVirtRegInterval(Reg); @@ -552,7 +512,6 @@ void HexagonExpandCondsets::removeInstr(MachineInstr &MI) { MI.eraseFromParent(); } - void HexagonExpandCondsets::updateLiveness(std::set<unsigned> &RegSet, bool Recalc, bool UpdateKills, bool UpdateDeads) { UpdateKills |= UpdateDeads; @@ -571,12 +530,12 @@ void HexagonExpandCondsets::updateLiveness(std::set<unsigned> &RegSet, } } - /// Get the opcode for a conditional transfer of the value in SO (source /// operand). The condition (true/false) is given in Cond. unsigned HexagonExpandCondsets::getCondTfrOpcode(const MachineOperand &SO, bool IfTrue) { using namespace Hexagon; + if (SO.isReg()) { unsigned PhysR; RegisterRef RS = SO; @@ -603,7 +562,6 @@ unsigned HexagonExpandCondsets::getCondTfrOpcode(const MachineOperand &SO, llvm_unreachable("Unexpected source operand"); } - /// Generate a conditional transfer, copying the value SrcOp to the /// destination register DstR:DstSR, and using the predicate register from /// PredOp. The Cond argument specifies whether the predicate is to be @@ -623,19 +581,29 @@ MachineInstr *HexagonExpandCondsets::genCondTfrFor(MachineOperand &SrcOp, /// predicate. unsigned Opc = getCondTfrOpcode(SrcOp, PredSense); - unsigned State = RegState::Define | (ReadUndef ? RegState::Undef : 0); - MachineInstrBuilder MIB = BuildMI(B, At, DL, HII->get(Opc)) - .addReg(DstR, State, DstSR) - .addOperand(PredOp) - .addOperand(SrcOp); - - // We don't want any kills yet. - MIB->clearKillInfo(); + unsigned DstState = RegState::Define | (ReadUndef ? RegState::Undef : 0); + unsigned PredState = getRegState(PredOp) & ~RegState::Kill; + MachineInstrBuilder MIB; + + if (SrcOp.isReg()) { + unsigned SrcState = getRegState(SrcOp); + if (RegisterRef(SrcOp) == RegisterRef(DstR, DstSR)) + SrcState &= ~RegState::Kill; + MIB = BuildMI(B, At, DL, HII->get(Opc)) + .addReg(DstR, DstState, DstSR) + .addReg(PredOp.getReg(), PredState, PredOp.getSubReg()) + .addReg(SrcOp.getReg(), SrcState, SrcOp.getSubReg()); + } else { + MIB = BuildMI(B, At, DL, HII->get(Opc)) + .addReg(DstR, DstState, DstSR) + .addReg(PredOp.getReg(), PredState, PredOp.getSubReg()) + .addOperand(SrcOp); + } + DEBUG(dbgs() << "created an initial copy: " << *MIB); return &*MIB; } - /// Replace a MUX instruction MI with a pair A2_tfrt/A2_tfrf. This function /// performs all necessary changes to complete the replacement. bool HexagonExpandCondsets::split(MachineInstr &MI, @@ -649,44 +617,36 @@ bool HexagonExpandCondsets::split(MachineInstr &MI, << MI); MachineOperand &MD = MI.getOperand(0); // Definition MachineOperand &MP = MI.getOperand(1); // Predicate register - MachineOperand &MS1 = MI.getOperand(2); // Source value #1 - MachineOperand &MS2 = MI.getOperand(3); // Source value #2 assert(MD.isDef()); unsigned DR = MD.getReg(), DSR = MD.getSubReg(); bool ReadUndef = MD.isUndef(); MachineBasicBlock::iterator At = MI; - if (ReadUndef && DSR != 0 && MRI->shouldTrackSubRegLiveness(DR)) { - unsigned NewSR = 0; - MachineBasicBlock::iterator DefAt = At; - bool SameReg = (MS1.isReg() && DR == MS1.getReg()) || - (MS2.isReg() && DR == MS2.getReg()); - if (SameReg) { - NewSR = (DSR == Hexagon::subreg_loreg) ? Hexagon::subreg_hireg - : Hexagon::subreg_loreg; - // Advance the insertion point if the subregisters differ between - // the source and the target (with the same super-register). - // Note: this case has never occured during tests. - if ((MS1.isReg() && NewSR == MS1.getSubReg()) || - (MS2.isReg() && NewSR == MS2.getSubReg())) - ++DefAt; + // If this is a mux of the same register, just replace it with COPY. + // Ideally, this would happen earlier, so that register coalescing would + // see it. + MachineOperand &ST = MI.getOperand(2); + MachineOperand &SF = MI.getOperand(3); + if (ST.isReg() && SF.isReg()) { + RegisterRef RT(ST); + if (RT == RegisterRef(SF)) { + MI.setDesc(HII->get(TargetOpcode::COPY)); + unsigned S = getRegState(ST); + while (MI.getNumOperands() > 1) + MI.RemoveOperand(MI.getNumOperands()-1); + MachineFunction &MF = *MI.getParent()->getParent(); + MachineInstrBuilder(MF, MI).addReg(RT.Reg, S, RT.Sub); + return true; } - // Use "At", since "DefAt" may be end(). - MachineBasicBlock &B = *At->getParent(); - DebugLoc DL = At->getDebugLoc(); - auto ImpD = BuildMI(B, DefAt, DL, HII->get(TargetOpcode::IMPLICIT_DEF)) - .addReg(DR, RegState::Define, NewSR); - LIS->InsertMachineInstrInMaps(*ImpD); - LocalImpDefs.insert(&*ImpD); } // First, create the two invididual conditional transfers, and add each // of them to the live intervals information. Do that first and then remove // the old instruction from live intervals. MachineInstr *TfrT = - genCondTfrFor(MI.getOperand(2), At, DR, DSR, MP, true, ReadUndef, false); + genCondTfrFor(ST, At, DR, DSR, MP, true, ReadUndef, false); MachineInstr *TfrF = - genCondTfrFor(MI.getOperand(3), At, DR, DSR, MP, false, ReadUndef, true); + genCondTfrFor(SF, At, DR, DSR, MP, false, ReadUndef, true); LIS->InsertMachineInstrInMaps(*TfrT); LIS->InsertMachineInstrInMaps(*TfrF); @@ -699,22 +659,6 @@ bool HexagonExpandCondsets::split(MachineInstr &MI, return true; } - -/// Split all MUX instructions in the given block into pairs of conditional -/// transfers. -bool HexagonExpandCondsets::splitInBlock(MachineBasicBlock &B, - std::set<unsigned> &UpdRegs) { - bool Changed = false; - MachineBasicBlock::iterator I, E, NextI; - for (I = B.begin(), E = B.end(); I != E; I = NextI) { - NextI = std::next(I); - if (isCondset(*I)) - Changed |= split(*I, UpdRegs); - } - return Changed; -} - - bool HexagonExpandCondsets::isPredicable(MachineInstr *MI) { if (HII->isPredicated(*MI) || !HII->isPredicable(*MI)) return false; @@ -735,7 +679,6 @@ bool HexagonExpandCondsets::isPredicable(MachineInstr *MI) { return true; } - /// Find the reaching definition for a predicated use of RD. The RD is used /// under the conditions given by PredR and Cond, and this function will ignore /// definitions that set RD under the opposite conditions. @@ -744,7 +687,7 @@ MachineInstr *HexagonExpandCondsets::getReachingDefForPred(RegisterRef RD, MachineBasicBlock &B = *UseIt->getParent(); MachineBasicBlock::iterator I = UseIt, S = B.begin(); if (I == S) - return 0; + return nullptr; bool PredValid = true; do { @@ -775,15 +718,14 @@ MachineInstr *HexagonExpandCondsets::getReachingDefForPred(RegisterRef RD, if (RR.Sub == RD.Sub) return MI; if (RR.Sub == 0 || RD.Sub == 0) - return 0; + return nullptr; // We have different subregisters, so we can continue looking. } } while (I != S); - return 0; + return nullptr; } - /// Check if the instruction MI can be safely moved over a set of instructions /// whose side-effects (in terms of register defs and uses) are expressed in /// the maps Defs and Uses. These maps reflect the conditional defs and uses @@ -813,7 +755,6 @@ bool HexagonExpandCondsets::canMoveOver(MachineInstr &MI, ReferenceMap &Defs, return true; } - /// Check if the instruction accessing memory (TheI) can be moved to the /// location ToI. bool HexagonExpandCondsets::canMoveMemTo(MachineInstr &TheI, MachineInstr &ToI, @@ -848,7 +789,6 @@ bool HexagonExpandCondsets::canMoveMemTo(MachineInstr &TheI, MachineInstr &ToI, return true; } - /// Generate a predicated version of MI (where the condition is given via /// PredR and Cond) at the point indicated by Where. void HexagonExpandCondsets::predicateAt(const MachineOperand &DefOp, @@ -909,7 +849,6 @@ void HexagonExpandCondsets::predicateAt(const MachineOperand &DefOp, UpdRegs.insert(Op.getReg()); } - /// In the range [First, Last], rename all references to the "old" register RO /// to the "new" register RN, but only in instructions predicated on the given /// condition. @@ -937,7 +876,6 @@ void HexagonExpandCondsets::renameInRange(RegisterRef RO, RegisterRef RN, } } - /// For a given conditional copy, predicate the definition of the source of /// the copy under the given condition (using the same predicate register as /// the copy). @@ -982,7 +920,7 @@ bool HexagonExpandCondsets::predicate(MachineInstr &TfrI, bool Cond, // conditions when collecting def and use information. bool PredValid = true; for (MachineBasicBlock::iterator I = std::next(DefIt); I != TfrIt; ++I) { - if (!I->modifiesRegister(PredR, 0)) + if (!I->modifiesRegister(PredR, nullptr)) continue; PredValid = false; break; @@ -1013,6 +951,13 @@ bool HexagonExpandCondsets::predicate(MachineInstr &TfrI, bool Cond, return false; ReferenceMap &Map = Op.isDef() ? Defs : Uses; + if (Op.isDef() && Op.isUndef()) { + assert(RR.Sub && "Expecting a subregister on <def,read-undef>"); + // If this is a <def,read-undef>, then it invalidates the non-written + // part of the register. For the purpose of checking the validity of + // the move, assume that it modifies the whole register. + RR.Sub = 0; + } addRefToMap(RR, Map, Exec); } } @@ -1067,7 +1012,6 @@ bool HexagonExpandCondsets::predicate(MachineInstr &TfrI, bool Cond, return true; } - /// Predicate all cases of conditional copies in the specified block. bool HexagonExpandCondsets::predicateInBlock(MachineBasicBlock &B, std::set<unsigned> &UpdRegs) { @@ -1094,7 +1038,6 @@ bool HexagonExpandCondsets::predicateInBlock(MachineBasicBlock &B, return Changed; } - bool HexagonExpandCondsets::isIntReg(RegisterRef RR, unsigned &BW) { if (!TargetRegisterInfo::isVirtualRegister(RR.Reg)) return false; @@ -1110,7 +1053,6 @@ bool HexagonExpandCondsets::isIntReg(RegisterRef RR, unsigned &BW) { return false; } - bool HexagonExpandCondsets::isIntraBlocks(LiveInterval &LI) { for (LiveInterval::iterator I = LI.begin(), E = LI.end(); I != E; ++I) { LiveRange::Segment &LR = *I; @@ -1124,7 +1066,6 @@ bool HexagonExpandCondsets::isIntraBlocks(LiveInterval &LI) { return true; } - bool HexagonExpandCondsets::coalesceRegisters(RegisterRef R1, RegisterRef R2) { if (CoaLimitActive) { if (CoaCounter >= CoaLimit) @@ -1141,6 +1082,10 @@ bool HexagonExpandCondsets::coalesceRegisters(RegisterRef R1, RegisterRef R2) { LiveInterval &L1 = LIS->getInterval(R1.Reg); LiveInterval &L2 = LIS->getInterval(R2.Reg); + if (L2.empty()) + return false; + if (L1.hasSubRanges() || L2.hasSubRanges()) + return false; bool Overlap = L1.overlaps(L2); DEBUG(dbgs() << "compatible registers: (" @@ -1176,6 +1121,7 @@ bool HexagonExpandCondsets::coalesceRegisters(RegisterRef R1, RegisterRef R2) { } while (L2.begin() != L2.end()) L2.removeSegment(*L2.begin()); + LIS->removeInterval(R2.Reg); updateKillFlags(R1.Reg); DEBUG(dbgs() << "coalesced: " << L1 << "\n"); @@ -1184,28 +1130,22 @@ bool HexagonExpandCondsets::coalesceRegisters(RegisterRef R1, RegisterRef R2) { return true; } - -/// Attempt to coalesce one of the source registers to a MUX intruction with +/// Attempt to coalesce one of the source registers to a MUX instruction with /// the destination register. This could lead to having only one predicated /// instruction in the end instead of two. -bool HexagonExpandCondsets::coalesceSegments(MachineFunction &MF) { - SmallVector<MachineInstr*,16> Condsets; - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { - MachineBasicBlock &B = *I; - for (MachineBasicBlock::iterator J = B.begin(), F = B.end(); J != F; ++J) { - MachineInstr *MI = &*J; - if (!isCondset(*MI)) - continue; - MachineOperand &S1 = MI->getOperand(2), &S2 = MI->getOperand(3); - if (!S1.isReg() && !S2.isReg()) - continue; - Condsets.push_back(MI); - } +bool HexagonExpandCondsets::coalesceSegments( + const SmallVectorImpl<MachineInstr*> &Condsets, + std::set<unsigned> &UpdRegs) { + SmallVector<MachineInstr*,16> TwoRegs; + for (MachineInstr *MI : Condsets) { + MachineOperand &S1 = MI->getOperand(2), &S2 = MI->getOperand(3); + if (!S1.isReg() && !S2.isReg()) + continue; + TwoRegs.push_back(MI); } bool Changed = false; - for (unsigned i = 0, n = Condsets.size(); i < n; ++i) { - MachineInstr *CI = Condsets[i]; + for (MachineInstr *CI : TwoRegs) { RegisterRef RD = CI->getOperand(0); RegisterRef RP = CI->getOperand(1); MachineOperand &S1 = CI->getOperand(2), &S2 = CI->getOperand(3); @@ -1231,21 +1171,30 @@ bool HexagonExpandCondsets::coalesceSegments(MachineFunction &MF) { if (S1.isReg()) { RegisterRef RS = S1; MachineInstr *RDef = getReachingDefForPred(RS, CI, RP.Reg, true); - if (!RDef || !HII->isPredicable(*RDef)) + if (!RDef || !HII->isPredicable(*RDef)) { Done = coalesceRegisters(RD, RegisterRef(S1)); + if (Done) { + UpdRegs.insert(RD.Reg); + UpdRegs.insert(S1.getReg()); + } + } } if (!Done && S2.isReg()) { RegisterRef RS = S2; MachineInstr *RDef = getReachingDefForPred(RS, CI, RP.Reg, false); - if (!RDef || !HII->isPredicable(*RDef)) + if (!RDef || !HII->isPredicable(*RDef)) { Done = coalesceRegisters(RD, RegisterRef(S2)); + if (Done) { + UpdRegs.insert(RD.Reg); + UpdRegs.insert(S2.getReg()); + } + } } Changed |= Done; } return Changed; } - bool HexagonExpandCondsets::runOnMachineFunction(MachineFunction &MF) { if (skipFunction(*MF.getFunction())) return false; @@ -1255,25 +1204,54 @@ bool HexagonExpandCondsets::runOnMachineFunction(MachineFunction &MF) { MDT = &getAnalysis<MachineDominatorTree>(); LIS = &getAnalysis<LiveIntervals>(); MRI = &MF.getRegInfo(); - LocalImpDefs.clear(); DEBUG(LIS->print(dbgs() << "Before expand-condsets\n", MF.getFunction()->getParent())); bool Changed = false; - std::set<unsigned> SplitUpd, PredUpd; + std::set<unsigned> CoalUpd, PredUpd; + + SmallVector<MachineInstr*,16> Condsets; + for (auto &B : MF) + for (auto &I : B) + if (isCondset(I)) + Condsets.push_back(&I); // Try to coalesce the target of a mux with one of its sources. // This could eliminate a register copy in some circumstances. - Changed |= coalesceSegments(MF); + Changed |= coalesceSegments(Condsets, CoalUpd); + + // Update kill flags on all source operands. This is done here because + // at this moment (when expand-condsets runs), there are no kill flags + // in the IR (they have been removed by live range analysis). + // Updating them right before we split is the easiest, because splitting + // adds definitions which would interfere with updating kills afterwards. + std::set<unsigned> KillUpd; + for (MachineInstr *MI : Condsets) + for (MachineOperand &Op : MI->operands()) + if (Op.isReg() && Op.isUse()) + if (!CoalUpd.count(Op.getReg())) + KillUpd.insert(Op.getReg()); + updateLiveness(KillUpd, false, true, false); + DEBUG(LIS->print(dbgs() << "After coalescing\n", + MF.getFunction()->getParent())); // First, simply split all muxes into a pair of conditional transfers // and update the live intervals to reflect the new arrangement. The // goal is to update the kill flags, since predication will rely on // them. - for (auto &B : MF) - Changed |= splitInBlock(B, SplitUpd); - updateLiveness(SplitUpd, true, true, false); + for (MachineInstr *MI : Condsets) + Changed |= split(*MI, PredUpd); + Condsets.clear(); // The contents of Condsets are invalid here anyway. + + // Do not update live ranges after splitting. Recalculation of live + // intervals removes kill flags, which were preserved by splitting on + // the source operands of condsets. These kill flags are needed by + // predication, and after splitting they are difficult to recalculate + // (because of predicated defs), so make sure they are left untouched. + // Predication does not use live intervals. + DEBUG(LIS->print(dbgs() << "After splitting\n", + MF.getFunction()->getParent())); // Traverse all blocks and collapse predicable instructions feeding // conditional transfers into predicated instructions. @@ -1281,18 +1259,11 @@ bool HexagonExpandCondsets::runOnMachineFunction(MachineFunction &MF) { // cases that were not created in the previous step. for (auto &B : MF) Changed |= predicateInBlock(B, PredUpd); + DEBUG(LIS->print(dbgs() << "After predicating\n", + MF.getFunction()->getParent())); + PredUpd.insert(CoalUpd.begin(), CoalUpd.end()); updateLiveness(PredUpd, true, true, true); - // Remove from SplitUpd all registers contained in PredUpd to avoid - // unnecessary liveness recalculation. - std::set<unsigned> Diff; - std::set_difference(SplitUpd.begin(), SplitUpd.end(), - PredUpd.begin(), PredUpd.end(), - std::inserter(Diff, Diff.begin())); - updateLiveness(Diff, false, false, true); - - for (auto *ImpD : LocalImpDefs) - removeInstr(*ImpD); DEBUG({ if (Changed) @@ -1303,7 +1274,6 @@ bool HexagonExpandCondsets::runOnMachineFunction(MachineFunction &MF) { return Changed; } - //===----------------------------------------------------------------------===// // Public Constructor Functions //===----------------------------------------------------------------------===// |
