diff options
Diffstat (limited to 'contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp')
| -rw-r--r-- | contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp | 1310 |
1 files changed, 1310 insertions, 0 deletions
diff --git a/contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp b/contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp new file mode 100644 index 000000000000..734f3c6658d9 --- /dev/null +++ b/contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp @@ -0,0 +1,1310 @@ +//===--- HexagonExpandCondsets.cpp ----------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// Replace mux instructions with the corresponding legal instructions. +// It is meant to work post-SSA, but still on virtual registers. It was +// originally placed between register coalescing and machine instruction +// scheduler. +// In this place in the optimization sequence, live interval analysis had +// been performed, and the live intervals should be preserved. A large part +// of the code deals with preserving the liveness information. +// +// Liveness tracking aside, the main functionality of this pass is divided +// into two steps. The first step is to replace an instruction +// vreg0 = C2_mux vreg1, vreg2, vreg3 +// with a pair of conditional transfers +// vreg0 = A2_tfrt vreg1, vreg2 +// vreg0 = A2_tfrf vreg1, vreg3 +// It is the intention that the execution of this pass could be terminated +// after this step, and the code generated would be functionally correct. +// +// If the uses of the source values vreg1 and vreg2 are kills, and their +// definitions are predicable, then in the second step, the conditional +// transfers will then be rewritten as predicated instructions. E.g. +// vreg0 = A2_or vreg1, vreg2 +// vreg3 = A2_tfrt vreg99, vreg0<kill> +// will be rewritten as +// vreg3 = A2_port vreg99, vreg1, vreg2 +// +// This replacement has two variants: "up" and "down". Consider this case: +// vreg0 = A2_or vreg1, vreg2 +// ... [intervening instructions] ... +// vreg3 = A2_tfrt vreg99, vreg0<kill> +// variant "up": +// vreg3 = A2_port vreg99, vreg1, vreg2 +// ... [intervening instructions, vreg0->vreg3] ... +// [deleted] +// variant "down": +// [deleted] +// ... [intervening instructions] ... +// vreg3 = A2_port vreg99, vreg1, vreg2 +// +// Both, one or none of these variants may be valid, and checks are made +// to rule out inapplicable variants. +// +// As an additional optimization, before either of the two steps above is +// executed, the pass attempts to coalesce the target register with one of +// the source registers, e.g. given an instruction +// vreg3 = C2_mux vreg0, vreg1, vreg2 +// vreg3 will be coalesced with either vreg1 or vreg2. If this succeeds, +// the instruction would then be (for example) +// vreg3 = C2_mux vreg0, vreg3, vreg2 +// and, under certain circumstances, this could result in only one predicated +// instruction: +// vreg3 = A2_tfrf vreg0, vreg2 +// + +// Splitting a definition of a register into two predicated transfers +// creates a complication in liveness tracking. Live interval computation +// will see both instructions as actual definitions, and will mark the +// first one as dead. The definition is not actually dead, and this +// situation will need to be fixed. For example: +// vreg1<def,dead> = A2_tfrt ... ; marked as dead +// vreg1<def> = A2_tfrf ... +// +// Since any of the individual predicated transfers may end up getting +// removed (in case it is an identity copy), some pre-existing def may +// be marked as dead after live interval recomputation: +// vreg1<def,dead> = ... ; marked as dead +// ... +// vreg1<def> = A2_tfrf ... ; if A2_tfrt is removed +// This case happens if vreg1 was used as a source in A2_tfrt, which means +// that is it actually live at the A2_tfrf, and so the now dead definition +// of vreg1 will need to be updated to non-dead at some point. +// +// This issue could be remedied by adding implicit uses to the predicated +// transfers, but this will create a problem with subsequent predication, +// since the transfers will no longer be possible to reorder. To avoid +// that, the initial splitting will not add any implicit uses. These +// 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. + +#define DEBUG_TYPE "expand-condsets" + +#include "HexagonInstrInfo.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SetVector.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/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 "llvm/Target/TargetRegisterInfo.h" +#include <cassert> +#include <iterator> +#include <set> +#include <utility> + +using namespace llvm; + +static cl::opt<unsigned> OptTfrLimit("expand-condsets-tfr-limit", + cl::init(~0U), cl::Hidden, cl::desc("Max number of mux expansions")); +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(nullptr), TRI(nullptr), MRI(nullptr), + LIS(nullptr), CoaLimitActive(false), + TfrLimitActive(false), CoaCounter(0), TfrCounter(0) { + if (OptCoaLimit.getPosition()) + CoaLimitActive = true, CoaLimit = OptCoaLimit; + if (OptTfrLimit.getPosition()) + TfrLimitActive = true, TfrLimit = OptTfrLimit; + initializeHexagonExpandCondsetsPass(*PassRegistry::getPassRegistry()); + } + + StringRef getPassName() const override { return "Hexagon Expand Condsets"; } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired<LiveIntervals>(); + AU.addPreserved<LiveIntervals>(); + AU.addPreserved<SlotIndexes>(); + AU.addRequired<MachineDominatorTree>(); + AU.addPreserved<MachineDominatorTree>(); + MachineFunctionPass::getAnalysisUsage(AU); + } + + bool runOnMachineFunction(MachineFunction &MF) override; + + private: + const HexagonInstrInfo *HII; + const TargetRegisterInfo *TRI; + MachineDominatorTree *MDT; + MachineRegisterInfo *MRI; + LiveIntervals *LIS; + + bool CoaLimitActive, TfrLimitActive; + unsigned CoaLimit, TfrLimit, CoaCounter, TfrCounter; + + struct RegisterRef { + 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; + } + bool operator!= (RegisterRef RR) const { return !operator==(RR); } + bool operator< (RegisterRef RR) const { + return Reg < RR.Reg || (Reg == RR.Reg && Sub < RR.Sub); + } + + unsigned Reg, Sub; + }; + + typedef DenseMap<unsigned,unsigned> ReferenceMap; + enum { Sub_Low = 0x1, Sub_High = 0x2, Sub_None = (Sub_Low | Sub_High) }; + enum { Exec_Then = 0x10, Exec_Else = 0x20 }; + unsigned getMaskForSub(unsigned Sub); + bool isCondset(const MachineInstr &MI); + LaneBitmask getLaneMask(unsigned Reg, unsigned Sub); + + void addRefToMap(RegisterRef RR, ReferenceMap &Map, unsigned Exec); + bool isRefInMap(RegisterRef, ReferenceMap &Map, unsigned Exec); + + void updateDeadsInRange(unsigned Reg, LaneBitmask LM, LiveRange &Range); + void updateKillFlags(unsigned Reg); + void updateDeadFlags(unsigned Reg); + void recalculateLiveInterval(unsigned Reg); + void removeInstr(MachineInstr &MI); + void updateLiveness(std::set<unsigned> &RegSet, bool Recalc, + bool UpdateKills, bool UpdateDeads); + + unsigned getCondTfrOpcode(const MachineOperand &SO, bool Cond); + MachineInstr *genCondTfrFor(MachineOperand &SrcOp, + MachineBasicBlock::iterator At, unsigned DstR, + unsigned DstSR, const MachineOperand &PredOp, bool PredSense, + bool ReadUndef, bool ImpUse); + bool split(MachineInstr &MI, std::set<unsigned> &UpdRegs); + + bool isPredicable(MachineInstr *MI); + MachineInstr *getReachingDefForPred(RegisterRef RD, + MachineBasicBlock::iterator UseIt, unsigned PredR, bool Cond); + bool canMoveOver(MachineInstr &MI, ReferenceMap &Defs, ReferenceMap &Uses); + bool canMoveMemTo(MachineInstr &MI, MachineInstr &ToI, bool IsDown); + void predicateAt(const MachineOperand &DefOp, MachineInstr &MI, + MachineBasicBlock::iterator Where, + const MachineOperand &PredOp, bool Cond, + std::set<unsigned> &UpdRegs); + void renameInRange(RegisterRef RO, RegisterRef RN, unsigned PredR, + bool Cond, MachineBasicBlock::iterator First, + MachineBasicBlock::iterator Last); + bool predicate(MachineInstr &TfrI, bool Cond, std::set<unsigned> &UpdRegs); + bool predicateInBlock(MachineBasicBlock &B, + std::set<unsigned> &UpdRegs); + + bool isIntReg(RegisterRef RR, unsigned &BW); + bool isIntraBlocks(LiveInterval &LI); + bool coalesceRegisters(RegisterRef R1, RegisterRef R2); + 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) +INITIALIZE_PASS_DEPENDENCY(SlotIndexes) +INITIALIZE_PASS_DEPENDENCY(LiveIntervals) +INITIALIZE_PASS_END(HexagonExpandCondsets, "expand-condsets", + "Hexagon Expand Condsets", false, false) + +unsigned HexagonExpandCondsets::getMaskForSub(unsigned Sub) { + switch (Sub) { + case Hexagon::isub_lo: + case Hexagon::vsub_lo: + return Sub_Low; + case Hexagon::isub_hi: + case Hexagon::vsub_hi: + return Sub_High; + case Hexagon::NoSubRegister: + return Sub_None; + } + llvm_unreachable("Invalid subregister"); +} + +bool HexagonExpandCondsets::isCondset(const MachineInstr &MI) { + unsigned Opc = MI.getOpcode(); + switch (Opc) { + case Hexagon::C2_mux: + case Hexagon::C2_muxii: + case Hexagon::C2_muxir: + case Hexagon::C2_muxri: + 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; + ReferenceMap::iterator F = Map.find(RR.Reg); + if (F == Map.end()) + Map.insert(std::make_pair(RR.Reg, Mask)); + else + F->second |= Mask; +} + +bool HexagonExpandCondsets::isRefInMap(RegisterRef RR, ReferenceMap &Map, + unsigned Exec) { + ReferenceMap::iterator F = Map.find(RR.Reg); + if (F == Map.end()) + return false; + unsigned Mask = getMaskForSub(RR.Sub) | Exec; + if (Mask & F->second) + return true; + 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. + MachineInstr *MI = LIS->getInstructionFromIndex(K); + for (auto &Op : MI->operands()) { + if (!Op.isReg() || !Op.isUse() || Op.getReg() != Reg) + continue; + LaneBitmask SLM = getLaneMask(Reg, Op.getSubReg()); + if ((SLM & LM) == SLM) { + // Only set the kill flag on the first encountered use of Reg in this + // instruction. + Op.setIsKill(true); + break; + } + } + }; + + LiveInterval &LI = LIS->getInterval(Reg); + for (auto I = LI.begin(), E = LI.end(); I != E; ++I) { + if (!I->end.isRegister()) + continue; + // Do not mark the end of the segment as <kill>, if the next segment + // starts with a predicated instruction. + auto NextI = std::next(I); + if (NextI != E && NextI->start.isRegister()) { + MachineInstr *DefI = LIS->getInstructionFromIndex(NextI->start); + if (HII->isPredicated(*DefI)) + continue; + } + bool WholeReg = true; + if (LI.hasSubRanges()) { + auto EndsAtI = [I] (LiveInterval::SubRange &S) -> bool { + LiveRange::iterator F = S.find(I->end); + return F != S.end() && I->end == F->end; + }; + // Check if all subranges end at I->end. If so, make sure to kill + // the whole register. + for (LiveInterval::SubRange &S : LI.subranges()) { + if (EndsAtI(S)) + KillAt(I->end, S.LaneMask); + else + WholeReg = false; + } + } + if (WholeReg) + KillAt(I->end, MRI->getMaxLaneMaskForVReg(Reg)); + } +} + +void HexagonExpandCondsets::updateDeadsInRange(unsigned Reg, LaneBitmask LM, + LiveRange &Range) { + assert(TargetRegisterInfo::isVirtualRegister(Reg)); + if (Range.empty()) + return; + + // Return two booleans: { def-modifes-reg, def-covers-reg }. + auto IsRegDef = [this,Reg,LM] (MachineOperand &Op) -> std::pair<bool,bool> { + if (!Op.isReg() || !Op.isDef()) + return { false, false }; + unsigned DR = Op.getReg(), DSR = Op.getSubReg(); + if (!TargetRegisterInfo::isVirtualRegister(DR) || DR != Reg) + return { false, false }; + LaneBitmask SLM = getLaneMask(DR, DSR); + LaneBitmask A = SLM & LM; + return { A.any(), A == SLM }; + }; + + // The splitting step will create pairs of predicated definitions without + // any implicit uses (since implicit uses would interfere with predication). + // This can cause the reaching defs to become dead after live range + // recomputation, even though they are not really dead. + // We need to identify predicated defs that need implicit uses, and + // dead defs that are not really dead, and correct both problems. + + auto Dominate = [this] (SetVector<MachineBasicBlock*> &Defs, + MachineBasicBlock *Dest) -> bool { + for (MachineBasicBlock *D : Defs) + if (D != Dest && MDT->dominates(D, Dest)) + return true; + + MachineBasicBlock *Entry = &Dest->getParent()->front(); + SetVector<MachineBasicBlock*> Work(Dest->pred_begin(), Dest->pred_end()); + for (unsigned i = 0; i < Work.size(); ++i) { + MachineBasicBlock *B = Work[i]; + if (Defs.count(B)) + continue; + if (B == Entry) + return false; + for (auto *P : B->predecessors()) + Work.insert(P); + } + return true; + }; + + // 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); + 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); + auto P = Range.extendInBlock(Undefs, LIS->getMBBStartIdx(BB), SI); + if (P.first != nullptr || P.second) + SI = SlotIndex(); + } + + // Calculate reachability for those predicated defs that were not handled + // by the in-block extension. + SmallVector<SlotIndex,4> ExtTo; + for (auto &SI : PredDefs) { + if (!SI.isValid()) + continue; + MachineBasicBlock *BB = LIS->getMBBFromIndex(SI); + 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); + } + + 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 + // the necessary implicit uses. + // At the same time, add <dead> flag to all defs that are actually dead. + // This can happen, for example, when a mux with identical inputs is + // replaced with a COPY: the use of the predicate register disappears and + // the dead can become dead. + std::set<RegisterRef> DefRegs; + for (auto &Seg : Range) { + if (!Seg.start.isRegister()) + continue; + MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start); + for (auto &Op : DefI->operands()) { + auto P = IsRegDef(Op); + if (P.second && Seg.end.isDead()) { + Op.setIsDead(true); + } else if (P.first) { + DefRegs.insert(Op); + Op.setIsDead(false); + } + } + } + + // Now, add implicit uses to each predicated def that is reached + // 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; + // 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.clear(); + LIS->constructMainRangeFromSubranges(LI); + } else { + updateDeadsInRange(Reg, MRI->getMaxLaneMaskForVReg(Reg), LI); + } +} + +void HexagonExpandCondsets::recalculateLiveInterval(unsigned Reg) { + LIS->removeInterval(Reg); + LIS->createAndComputeVirtRegInterval(Reg); +} + +void HexagonExpandCondsets::removeInstr(MachineInstr &MI) { + LIS->RemoveMachineInstrFromMaps(MI); + MI.eraseFromParent(); +} + +void HexagonExpandCondsets::updateLiveness(std::set<unsigned> &RegSet, + bool Recalc, bool UpdateKills, bool UpdateDeads) { + UpdateKills |= UpdateDeads; + for (auto R : RegSet) { + if (Recalc) + recalculateLiveInterval(R); + if (UpdateKills) + MRI->clearKillFlags(R); + if (UpdateDeads) + updateDeadFlags(R); + // Fixing <dead> flags may extend live ranges, so reset <kill> flags + // after that. + if (UpdateKills) + updateKillFlags(R); + LIS->getInterval(R).verify(); + } +} + +/// 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; + if (TargetRegisterInfo::isVirtualRegister(RS.Reg)) { + const TargetRegisterClass *VC = MRI->getRegClass(RS.Reg); + assert(VC->begin() != VC->end() && "Empty register class"); + PhysR = *VC->begin(); + } else { + assert(TargetRegisterInfo::isPhysicalRegister(RS.Reg)); + PhysR = RS.Reg; + } + unsigned PhysS = (RS.Sub == 0) ? PhysR : TRI->getSubReg(PhysR, RS.Sub); + const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(PhysS); + switch (TRI->getRegSizeInBits(*RC)) { + case 32: + return IfTrue ? A2_tfrt : A2_tfrf; + case 64: + return IfTrue ? A2_tfrpt : A2_tfrpf; + } + llvm_unreachable("Invalid register operand"); + } + switch (SO.getType()) { + case MachineOperand::MO_Immediate: + case MachineOperand::MO_FPImmediate: + case MachineOperand::MO_ConstantPoolIndex: + case MachineOperand::MO_TargetIndex: + case MachineOperand::MO_JumpTableIndex: + case MachineOperand::MO_ExternalSymbol: + case MachineOperand::MO_GlobalAddress: + case MachineOperand::MO_BlockAddress: + return IfTrue ? C2_cmoveit : C2_cmoveif; + default: + break; + } + 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 +/// if(PredOp), or if(!PredOp). +MachineInstr *HexagonExpandCondsets::genCondTfrFor(MachineOperand &SrcOp, + MachineBasicBlock::iterator At, + unsigned DstR, unsigned DstSR, const MachineOperand &PredOp, + bool PredSense, bool ReadUndef, bool ImpUse) { + MachineInstr *MI = SrcOp.getParent(); + MachineBasicBlock &B = *At->getParent(); + const DebugLoc &DL = MI->getDebugLoc(); + + // Don't avoid identity copies here (i.e. if the source and the destination + // are the same registers). It is actually better to generate them here, + // since this would cause the copy to potentially be predicated in the next + // step. The predication will remove such a copy if it is unable to + /// predicate. + + unsigned Opc = getCondTfrOpcode(SrcOp, PredSense); + 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()) + .add(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, + std::set<unsigned> &UpdRegs) { + if (TfrLimitActive) { + if (TfrCounter >= TfrLimit) + return false; + TfrCounter++; + } + DEBUG(dbgs() << "\nsplitting BB#" << MI.getParent()->getNumber() << ": " + << MI); + MachineOperand &MD = MI.getOperand(0); // Definition + MachineOperand &MP = MI.getOperand(1); // Predicate register + assert(MD.isDef()); + unsigned DR = MD.getReg(), DSR = MD.getSubReg(); + bool ReadUndef = MD.isUndef(); + MachineBasicBlock::iterator At = MI; + + auto updateRegs = [&UpdRegs] (const MachineInstr &MI) -> void { + for (auto &Op : MI.operands()) + if (Op.isReg()) + UpdRegs.insert(Op.getReg()); + }; + + // 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)) { + // Copy regs to update first. + updateRegs(MI); + 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; + } + } + + // 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(ST, At, DR, DSR, MP, true, ReadUndef, false); + MachineInstr *TfrF = + genCondTfrFor(SF, At, DR, DSR, MP, false, ReadUndef, true); + LIS->InsertMachineInstrInMaps(*TfrT); + LIS->InsertMachineInstrInMaps(*TfrF); + + // Will need to recalculate live intervals for all registers in MI. + updateRegs(MI); + + removeInstr(MI); + return true; +} + +bool HexagonExpandCondsets::isPredicable(MachineInstr *MI) { + if (HII->isPredicated(*MI) || !HII->isPredicable(*MI)) + return false; + if (MI->hasUnmodeledSideEffects() || MI->mayStore()) + return false; + // Reject instructions with multiple defs (e.g. post-increment loads). + bool HasDef = false; + for (auto &Op : MI->operands()) { + if (!Op.isReg() || !Op.isDef()) + continue; + if (HasDef) + return false; + HasDef = true; + } + for (auto &Mo : MI->memoperands()) + if (Mo->isVolatile()) + return false; + 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. +MachineInstr *HexagonExpandCondsets::getReachingDefForPred(RegisterRef RD, + MachineBasicBlock::iterator UseIt, unsigned PredR, bool Cond) { + MachineBasicBlock &B = *UseIt->getParent(); + MachineBasicBlock::iterator I = UseIt, S = B.begin(); + if (I == S) + return nullptr; + + bool PredValid = true; + do { + --I; + MachineInstr *MI = &*I; + // Check if this instruction can be ignored, i.e. if it is predicated + // on the complementary condition. + if (PredValid && HII->isPredicated(*MI)) { + if (MI->readsRegister(PredR) && (Cond != HII->isPredicatedTrue(*MI))) + continue; + } + + // Check the defs. If the PredR is defined, invalidate it. If RD is + // defined, return the instruction or 0, depending on the circumstances. + for (auto &Op : MI->operands()) { + if (!Op.isReg() || !Op.isDef()) + continue; + RegisterRef RR = Op; + if (RR.Reg == PredR) { + PredValid = false; + continue; + } + if (RR.Reg != RD.Reg) + continue; + // If the "Reg" part agrees, there is still the subregister to check. + // If we are looking for vreg1:loreg, we can skip vreg1:hireg, but + // not vreg1 (w/o subregisters). + if (RR.Sub == RD.Sub) + return MI; + if (RR.Sub == 0 || RD.Sub == 0) + return nullptr; + // We have different subregisters, so we can continue looking. + } + } while (I != S); + + 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 +/// that depend on the same predicate register to allow moving instructions +/// over instructions predicated on the opposite condition. +bool HexagonExpandCondsets::canMoveOver(MachineInstr &MI, ReferenceMap &Defs, + ReferenceMap &Uses) { + // In order to be able to safely move MI over instructions that define + // "Defs" and use "Uses", no def operand from MI can be defined or used + // and no use operand can be defined. + for (auto &Op : MI.operands()) { + if (!Op.isReg()) + continue; + RegisterRef RR = Op; + // For physical register we would need to check register aliases, etc. + // and we don't want to bother with that. It would be of little value + // before the actual register rewriting (from virtual to physical). + if (!TargetRegisterInfo::isVirtualRegister(RR.Reg)) + return false; + // No redefs for any operand. + if (isRefInMap(RR, Defs, Exec_Then)) + return false; + // For defs, there cannot be uses. + if (Op.isDef() && isRefInMap(RR, Uses, Exec_Then)) + return false; + } + return true; +} + +/// Check if the instruction accessing memory (TheI) can be moved to the +/// location ToI. +bool HexagonExpandCondsets::canMoveMemTo(MachineInstr &TheI, MachineInstr &ToI, + bool IsDown) { + bool IsLoad = TheI.mayLoad(), IsStore = TheI.mayStore(); + if (!IsLoad && !IsStore) + return true; + if (HII->areMemAccessesTriviallyDisjoint(TheI, ToI)) + return true; + if (TheI.hasUnmodeledSideEffects()) + return false; + + MachineBasicBlock::iterator StartI = IsDown ? TheI : ToI; + MachineBasicBlock::iterator EndI = IsDown ? ToI : TheI; + bool Ordered = TheI.hasOrderedMemoryRef(); + + // Search for aliased memory reference in (StartI, EndI). + for (MachineBasicBlock::iterator I = std::next(StartI); I != EndI; ++I) { + MachineInstr *MI = &*I; + if (MI->hasUnmodeledSideEffects()) + return false; + bool L = MI->mayLoad(), S = MI->mayStore(); + if (!L && !S) + continue; + if (Ordered && MI->hasOrderedMemoryRef()) + return false; + + bool Conflict = (L && IsStore) || S; + if (Conflict) + return false; + } + 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, + MachineInstr &MI, + MachineBasicBlock::iterator Where, + const MachineOperand &PredOp, bool Cond, + std::set<unsigned> &UpdRegs) { + // The problem with updating live intervals is that we can move one def + // past another def. In particular, this can happen when moving an A2_tfrt + // over an A2_tfrf defining the same register. From the point of view of + // live intervals, these two instructions are two separate definitions, + // and each one starts another live segment. LiveIntervals's "handleMove" + // does not allow such moves, so we need to handle it ourselves. To avoid + // invalidating liveness data while we are using it, the move will be + // implemented in 4 steps: (1) add a clone of the instruction MI at the + // target location, (2) update liveness, (3) delete the old instruction, + // and (4) update liveness again. + + MachineBasicBlock &B = *MI.getParent(); + DebugLoc DL = Where->getDebugLoc(); // "Where" points to an instruction. + unsigned Opc = MI.getOpcode(); + unsigned PredOpc = HII->getCondOpcode(Opc, !Cond); + MachineInstrBuilder MB = BuildMI(B, Where, DL, HII->get(PredOpc)); + unsigned Ox = 0, NP = MI.getNumOperands(); + // Skip all defs from MI first. + while (Ox < NP) { + MachineOperand &MO = MI.getOperand(Ox); + if (!MO.isReg() || !MO.isDef()) + break; + Ox++; + } + // Add the new def, then the predicate register, then the rest of the + // operands. + MB.addReg(DefOp.getReg(), getRegState(DefOp), DefOp.getSubReg()); + MB.addReg(PredOp.getReg(), PredOp.isUndef() ? RegState::Undef : 0, + PredOp.getSubReg()); + while (Ox < NP) { + MachineOperand &MO = MI.getOperand(Ox); + if (!MO.isReg() || !MO.isImplicit()) + MB.add(MO); + Ox++; + } + + MachineFunction &MF = *B.getParent(); + MachineInstr::mmo_iterator I = MI.memoperands_begin(); + unsigned NR = std::distance(I, MI.memoperands_end()); + MachineInstr::mmo_iterator MemRefs = MF.allocateMemRefsArray(NR); + for (unsigned i = 0; i < NR; ++i) + MemRefs[i] = *I++; + MB.setMemRefs(MemRefs, MemRefs+NR); + + MachineInstr *NewI = MB; + NewI->clearKillInfo(); + LIS->InsertMachineInstrInMaps(*NewI); + + for (auto &Op : NewI->operands()) + if (Op.isReg()) + 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. +void HexagonExpandCondsets::renameInRange(RegisterRef RO, RegisterRef RN, + unsigned PredR, bool Cond, MachineBasicBlock::iterator First, + MachineBasicBlock::iterator Last) { + MachineBasicBlock::iterator End = std::next(Last); + for (MachineBasicBlock::iterator I = First; I != End; ++I) { + MachineInstr *MI = &*I; + // Do not touch instructions that are not predicated, or are predicated + // on the opposite condition. + if (!HII->isPredicated(*MI)) + continue; + if (!MI->readsRegister(PredR) || (Cond != HII->isPredicatedTrue(*MI))) + continue; + + for (auto &Op : MI->operands()) { + if (!Op.isReg() || RO != RegisterRef(Op)) + continue; + Op.setReg(RN.Reg); + Op.setSubReg(RN.Sub); + // In practice, this isn't supposed to see any defs. + assert(!Op.isDef() && "Not expecting a def"); + } + } +} + +/// 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). +bool HexagonExpandCondsets::predicate(MachineInstr &TfrI, bool Cond, + std::set<unsigned> &UpdRegs) { + // TfrI - A2_tfr[tf] Instruction (not A2_tfrsi). + unsigned Opc = TfrI.getOpcode(); + (void)Opc; + assert(Opc == Hexagon::A2_tfrt || Opc == Hexagon::A2_tfrf); + DEBUG(dbgs() << "\nattempt to predicate if-" << (Cond ? "true" : "false") + << ": " << TfrI); + + MachineOperand &MD = TfrI.getOperand(0); + MachineOperand &MP = TfrI.getOperand(1); + MachineOperand &MS = TfrI.getOperand(2); + // The source operand should be a <kill>. This is not strictly necessary, + // but it makes things a lot simpler. Otherwise, we would need to rename + // some registers, which would complicate the transformation considerably. + if (!MS.isKill()) + return false; + // Avoid predicating instructions that define a subregister if subregister + // liveness tracking is not enabled. + if (MD.getSubReg() && !MRI->shouldTrackSubRegLiveness(MD.getReg())) + return false; + + RegisterRef RT(MS); + unsigned PredR = MP.getReg(); + MachineInstr *DefI = getReachingDefForPred(RT, TfrI, PredR, Cond); + if (!DefI || !isPredicable(DefI)) + return false; + + DEBUG(dbgs() << "Source def: " << *DefI); + + // Collect the information about registers defined and used between the + // DefI and the TfrI. + // Map: reg -> bitmask of subregs + ReferenceMap Uses, Defs; + MachineBasicBlock::iterator DefIt = DefI, TfrIt = TfrI; + + // Check if the predicate register is valid between DefI and TfrI. + // If it is, we can then ignore instructions predicated on the negated + // conditions when collecting def and use information. + bool PredValid = true; + for (MachineBasicBlock::iterator I = std::next(DefIt); I != TfrIt; ++I) { + if (!I->modifiesRegister(PredR, nullptr)) + continue; + PredValid = false; + break; + } + + for (MachineBasicBlock::iterator I = std::next(DefIt); I != TfrIt; ++I) { + MachineInstr *MI = &*I; + // If this instruction is predicated on the same register, it could + // potentially be ignored. + // By default assume that the instruction executes on the same condition + // as TfrI (Exec_Then), and also on the opposite one (Exec_Else). + unsigned Exec = Exec_Then | Exec_Else; + if (PredValid && HII->isPredicated(*MI) && MI->readsRegister(PredR)) + Exec = (Cond == HII->isPredicatedTrue(*MI)) ? Exec_Then : Exec_Else; + + for (auto &Op : MI->operands()) { + if (!Op.isReg()) + continue; + // We don't want to deal with physical registers. The reason is that + // they can be aliased with other physical registers. Aliased virtual + // registers must share the same register number, and can only differ + // in the subregisters, which we are keeping track of. Physical + // registers ters no longer have subregisters---their super- and + // subregisters are other physical registers, and we are not checking + // that. + RegisterRef RR = Op; + if (!TargetRegisterInfo::isVirtualRegister(RR.Reg)) + 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); + } + } + + // The situation: + // RT = DefI + // ... + // RD = TfrI ..., RT + + // If the register-in-the-middle (RT) is used or redefined between + // DefI and TfrI, we may not be able proceed with this transformation. + // We can ignore a def that will not execute together with TfrI, and a + // use that will. If there is such a use (that does execute together with + // TfrI), we will not be able to move DefI down. If there is a use that + // executed if TfrI's condition is false, then RT must be available + // unconditionally (cannot be predicated). + // Essentially, we need to be able to rename RT to RD in this segment. + if (isRefInMap(RT, Defs, Exec_Then) || isRefInMap(RT, Uses, Exec_Else)) + return false; + RegisterRef RD = MD; + // If the predicate register is defined between DefI and TfrI, the only + // potential thing to do would be to move the DefI down to TfrI, and then + // predicate. The reaching def (DefI) must be movable down to the location + // of the TfrI. + // If the target register of the TfrI (RD) is not used or defined between + // DefI and TfrI, consider moving TfrI up to DefI. + bool CanUp = canMoveOver(TfrI, Defs, Uses); + bool CanDown = canMoveOver(*DefI, Defs, Uses); + // The TfrI does not access memory, but DefI could. Check if it's safe + // to move DefI down to TfrI. + if (DefI->mayLoad() || DefI->mayStore()) + if (!canMoveMemTo(*DefI, TfrI, true)) + CanDown = false; + + DEBUG(dbgs() << "Can move up: " << (CanUp ? "yes" : "no") + << ", can move down: " << (CanDown ? "yes\n" : "no\n")); + MachineBasicBlock::iterator PastDefIt = std::next(DefIt); + if (CanUp) + predicateAt(MD, *DefI, PastDefIt, MP, Cond, UpdRegs); + else if (CanDown) + predicateAt(MD, *DefI, TfrIt, MP, Cond, UpdRegs); + else + return false; + + if (RT != RD) { + renameInRange(RT, RD, PredR, Cond, PastDefIt, TfrIt); + UpdRegs.insert(RT.Reg); + } + + removeInstr(TfrI); + removeInstr(*DefI); + return true; +} + +/// Predicate all cases of conditional copies in the specified block. +bool HexagonExpandCondsets::predicateInBlock(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); + unsigned Opc = I->getOpcode(); + if (Opc == Hexagon::A2_tfrt || Opc == Hexagon::A2_tfrf) { + bool Done = predicate(*I, (Opc == Hexagon::A2_tfrt), UpdRegs); + if (!Done) { + // If we didn't predicate I, we may need to remove it in case it is + // an "identity" copy, e.g. vreg1 = A2_tfrt vreg2, vreg1. + if (RegisterRef(I->getOperand(0)) == RegisterRef(I->getOperand(2))) { + for (auto &Op : I->operands()) + if (Op.isReg()) + UpdRegs.insert(Op.getReg()); + removeInstr(*I); + } + } + Changed |= Done; + } + } + return Changed; +} + +bool HexagonExpandCondsets::isIntReg(RegisterRef RR, unsigned &BW) { + if (!TargetRegisterInfo::isVirtualRegister(RR.Reg)) + return false; + const TargetRegisterClass *RC = MRI->getRegClass(RR.Reg); + if (RC == &Hexagon::IntRegsRegClass) { + BW = 32; + return true; + } + if (RC == &Hexagon::DoubleRegsRegClass) { + BW = (RR.Sub != 0) ? 32 : 64; + return true; + } + return false; +} + +bool HexagonExpandCondsets::isIntraBlocks(LiveInterval &LI) { + for (LiveInterval::iterator I = LI.begin(), E = LI.end(); I != E; ++I) { + LiveRange::Segment &LR = *I; + // Range must start at a register... + if (!LR.start.isRegister()) + return false; + // ...and end in a register or in a dead slot. + if (!LR.end.isRegister() && !LR.end.isDead()) + return false; + } + return true; +} + +bool HexagonExpandCondsets::coalesceRegisters(RegisterRef R1, RegisterRef R2) { + if (CoaLimitActive) { + if (CoaCounter >= CoaLimit) + return false; + CoaCounter++; + } + unsigned BW1, BW2; + if (!isIntReg(R1, BW1) || !isIntReg(R2, BW2) || BW1 != BW2) + return false; + if (MRI->isLiveIn(R1.Reg)) + return false; + if (MRI->isLiveIn(R2.Reg)) + return false; + + 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: (" + << (Overlap ? "overlap" : "disjoint") << ")\n " + << PrintReg(R1.Reg, TRI, R1.Sub) << " " << L1 << "\n " + << PrintReg(R2.Reg, TRI, R2.Sub) << " " << L2 << "\n"); + if (R1.Sub || R2.Sub) + return false; + if (Overlap) + return false; + + // Coalescing could have a negative impact on scheduling, so try to limit + // to some reasonable extent. Only consider coalescing segments, when one + // of them does not cross basic block boundaries. + if (!isIntraBlocks(L1) && !isIntraBlocks(L2)) + return false; + + MRI->replaceRegWith(R2.Reg, R1.Reg); + + // Move all live segments from L2 to L1. + typedef DenseMap<VNInfo*,VNInfo*> ValueInfoMap; + ValueInfoMap VM; + for (LiveInterval::iterator I = L2.begin(), E = L2.end(); I != E; ++I) { + VNInfo *NewVN, *OldVN = I->valno; + ValueInfoMap::iterator F = VM.find(OldVN); + if (F == VM.end()) { + NewVN = L1.getNextValue(I->valno->def, LIS->getVNInfoAllocator()); + VM.insert(std::make_pair(OldVN, NewVN)); + } else { + NewVN = F->second; + } + L1.addSegment(LiveRange::Segment(I->start, I->end, NewVN)); + } + while (L2.begin() != L2.end()) + L2.removeSegment(*L2.begin()); + LIS->removeInterval(R2.Reg); + + updateKillFlags(R1.Reg); + DEBUG(dbgs() << "coalesced: " << L1 << "\n"); + L1.verify(); + + return true; +} + +/// 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( + 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 (MachineInstr *CI : TwoRegs) { + RegisterRef RD = CI->getOperand(0); + RegisterRef RP = CI->getOperand(1); + MachineOperand &S1 = CI->getOperand(2), &S2 = CI->getOperand(3); + bool Done = false; + // Consider this case: + // vreg1 = instr1 ... + // vreg2 = instr2 ... + // vreg0 = C2_mux ..., vreg1, vreg2 + // If vreg0 was coalesced with vreg1, we could end up with the following + // code: + // vreg0 = instr1 ... + // vreg2 = instr2 ... + // vreg0 = A2_tfrf ..., vreg2 + // which will later become: + // vreg0 = instr1 ... + // vreg0 = instr2_cNotPt ... + // i.e. there will be an unconditional definition (instr1) of vreg0 + // followed by a conditional one. The output dependency was there before + // and it unavoidable, but if instr1 is predicable, we will no longer be + // able to predicate it here. + // To avoid this scenario, don't coalesce the destination register with + // a source register that is defined by a predicable instruction. + if (S1.isReg()) { + RegisterRef RS = S1; + MachineInstr *RDef = getReachingDefForPred(RS, CI, RP.Reg, true); + 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)) { + 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; + + HII = static_cast<const HexagonInstrInfo*>(MF.getSubtarget().getInstrInfo()); + TRI = MF.getSubtarget().getRegisterInfo(); + MDT = &getAnalysis<MachineDominatorTree>(); + LIS = &getAnalysis<LiveIntervals>(); + MRI = &MF.getRegInfo(); + + DEBUG(LIS->print(dbgs() << "Before expand-condsets\n", + MF.getFunction()->getParent())); + + bool Changed = false; + 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(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 (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. + // Walk over all the instructions again, so we may catch pre-existing + // 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); + + DEBUG({ + if (Changed) + LIS->print(dbgs() << "After expand-condsets\n", + MF.getFunction()->getParent()); + }); + + return Changed; +} + +//===----------------------------------------------------------------------===// +// Public Constructor Functions +//===----------------------------------------------------------------------===// + +FunctionPass *llvm::createHexagonExpandCondsets() { + return new HexagonExpandCondsets(); +} |