//===--- HexagonEarlyIfConv.cpp -------------------------------------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This implements a Hexagon-specific if-conversion pass that runs on the // SSA form. // In SSA it is not straightforward to represent instructions that condi- // tionally define registers, since a conditionally-defined register may // only be used under the same condition on which the definition was based. // To avoid complications of this nature, this patch will only generate // predicated stores, and speculate other instructions from the "if-conver- // ted" block. // The code will recognize CFG patterns where a block with a conditional // branch "splits" into a "true block" and a "false block". Either of these // could be omitted (in case of a triangle, for example). // If after conversion of the side block(s) the CFG allows it, the resul- // ting blocks may be merged. If the "join" block contained PHI nodes, they // will be replaced with MUX (or MUX-like) instructions to maintain the // semantics of the PHI. // // Example: // // %vreg40<def> = L2_loadrub_io %vreg39<kill>, 1 // %vreg41<def> = S2_tstbit_i %vreg40<kill>, 0 // J2_jumpt %vreg41<kill>, <BB#5>, %PC<imp-def,dead> // J2_jump <BB#4>, %PC<imp-def,dead> // Successors according to CFG: BB#4(62) BB#5(62) // // BB#4: derived from LLVM BB %if.then // Predecessors according to CFG: BB#3 // %vreg11<def> = A2_addp %vreg6, %vreg10 // S2_storerd_io %vreg32, 16, %vreg11 // Successors according to CFG: BB#5 // // BB#5: derived from LLVM BB %if.end // Predecessors according to CFG: BB#3 BB#4 // %vreg12<def> = PHI %vreg6, <BB#3>, %vreg11, <BB#4> // %vreg13<def> = A2_addp %vreg7, %vreg12 // %vreg42<def> = C2_cmpeqi %vreg9, 10 // J2_jumpf %vreg42<kill>, <BB#3>, %PC<imp-def,dead> // J2_jump <BB#6>, %PC<imp-def,dead> // Successors according to CFG: BB#6(4) BB#3(124) // // would become: // // %vreg40<def> = L2_loadrub_io %vreg39<kill>, 1 // %vreg41<def> = S2_tstbit_i %vreg40<kill>, 0 // spec-> %vreg11<def> = A2_addp %vreg6, %vreg10 // pred-> S2_pstorerdf_io %vreg41, %vreg32, 16, %vreg11 // %vreg46<def> = MUX64_rr %vreg41, %vreg6, %vreg11 // %vreg13<def> = A2_addp %vreg7, %vreg46 // %vreg42<def> = C2_cmpeqi %vreg9, 10 // J2_jumpf %vreg42<kill>, <BB#3>, %PC<imp-def,dead> // J2_jump <BB#6>, %PC<imp-def,dead> // Successors according to CFG: BB#6 BB#3 #define DEBUG_TYPE "hexagon-eif" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SetVector.h" #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "HexagonTargetMachine.h" #include <functional> #include <set> #include <vector> using namespace llvm; namespace llvm { FunctionPass *createHexagonEarlyIfConversion(); void initializeHexagonEarlyIfConversionPass(PassRegistry& Registry); } namespace { cl::opt<bool> EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden, cl::init(false), cl::desc("Enable branch probability info")); cl::opt<unsigned> SizeLimit("eif-limit", cl::init(6), cl::Hidden, cl::desc("Size limit in Hexagon early if-conversion")); struct PrintMB { PrintMB(const MachineBasicBlock *B) : MB(B) {} const MachineBasicBlock *MB; }; raw_ostream &operator<< (raw_ostream &OS, const PrintMB &P) { if (!P.MB) return OS << "<none>"; return OS << '#' << P.MB->getNumber(); } struct FlowPattern { FlowPattern() : SplitB(0), TrueB(0), FalseB(0), JoinB(0), PredR(0) {} FlowPattern(MachineBasicBlock *B, unsigned PR, MachineBasicBlock *TB, MachineBasicBlock *FB, MachineBasicBlock *JB) : SplitB(B), TrueB(TB), FalseB(FB), JoinB(JB), PredR(PR) {} MachineBasicBlock *SplitB; MachineBasicBlock *TrueB, *FalseB, *JoinB; unsigned PredR; }; struct PrintFP { PrintFP(const FlowPattern &P, const TargetRegisterInfo &T) : FP(P), TRI(T) {} const FlowPattern &FP; const TargetRegisterInfo &TRI; friend raw_ostream &operator<< (raw_ostream &OS, const PrintFP &P); }; raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) LLVM_ATTRIBUTE_UNUSED; raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) { OS << "{ SplitB:" << PrintMB(P.FP.SplitB) << ", PredR:" << PrintReg(P.FP.PredR, &P.TRI) << ", TrueB:" << PrintMB(P.FP.TrueB) << ", FalseB:" << PrintMB(P.FP.FalseB) << ", JoinB:" << PrintMB(P.FP.JoinB) << " }"; return OS; } class HexagonEarlyIfConversion : public MachineFunctionPass { public: static char ID; HexagonEarlyIfConversion() : MachineFunctionPass(ID), TII(0), TRI(0), MFN(0), MRI(0), MDT(0), MLI(0) { initializeHexagonEarlyIfConversionPass(*PassRegistry::getPassRegistry()); } const char *getPassName() const override { return "Hexagon early if conversion"; } void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired<MachineBranchProbabilityInfo>(); AU.addRequired<MachineDominatorTree>(); AU.addPreserved<MachineDominatorTree>(); AU.addRequired<MachineLoopInfo>(); MachineFunctionPass::getAnalysisUsage(AU); } bool runOnMachineFunction(MachineFunction &MF) override; private: typedef DenseSet<MachineBasicBlock*> BlockSetType; bool isPreheader(const MachineBasicBlock *B) const; bool matchFlowPattern(MachineBasicBlock *B, MachineLoop *L, FlowPattern &FP); bool visitBlock(MachineBasicBlock *B, MachineLoop *L); bool visitLoop(MachineLoop *L); bool hasEHLabel(const MachineBasicBlock *B) const; bool hasUncondBranch(const MachineBasicBlock *B) const; bool isValidCandidate(const MachineBasicBlock *B) const; bool usesUndefVReg(const MachineInstr *MI) const; bool isValid(const FlowPattern &FP) const; unsigned countPredicateDefs(const MachineBasicBlock *B) const; unsigned computePhiCost(MachineBasicBlock *B) const; bool isProfitable(const FlowPattern &FP) const; bool isPredicableStore(const MachineInstr *MI) const; bool isSafeToSpeculate(const MachineInstr *MI) const; unsigned getCondStoreOpcode(unsigned Opc, bool IfTrue) const; void predicateInstr(MachineBasicBlock *ToB, MachineBasicBlock::iterator At, MachineInstr *MI, unsigned PredR, bool IfTrue); void predicateBlockNB(MachineBasicBlock *ToB, MachineBasicBlock::iterator At, MachineBasicBlock *FromB, unsigned PredR, bool IfTrue); void updatePhiNodes(MachineBasicBlock *WhereB, const FlowPattern &FP); void convert(const FlowPattern &FP); void removeBlock(MachineBasicBlock *B); void eliminatePhis(MachineBasicBlock *B); void replacePhiEdges(MachineBasicBlock *OldB, MachineBasicBlock *NewB); void mergeBlocks(MachineBasicBlock *PredB, MachineBasicBlock *SuccB); void simplifyFlowGraph(const FlowPattern &FP); const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; MachineFunction *MFN; MachineRegisterInfo *MRI; MachineDominatorTree *MDT; MachineLoopInfo *MLI; BlockSetType Deleted; const MachineBranchProbabilityInfo *MBPI; }; char HexagonEarlyIfConversion::ID = 0; } INITIALIZE_PASS(HexagonEarlyIfConversion, "hexagon-eif", "Hexagon early if conversion", false, false) bool HexagonEarlyIfConversion::isPreheader(const MachineBasicBlock *B) const { if (B->succ_size() != 1) return false; MachineBasicBlock *SB = *B->succ_begin(); MachineLoop *L = MLI->getLoopFor(SB); return L && SB == L->getHeader(); } bool HexagonEarlyIfConversion::matchFlowPattern(MachineBasicBlock *B, MachineLoop *L, FlowPattern &FP) { DEBUG(dbgs() << "Checking flow pattern at BB#" << B->getNumber() << "\n"); // Interested only in conditional branches, no .new, no new-value, etc. // Check the terminators directly, it's easier than handling all responses // from AnalyzeBranch. MachineBasicBlock *TB = 0, *FB = 0; MachineBasicBlock::const_iterator T1I = B->getFirstTerminator(); if (T1I == B->end()) return false; unsigned Opc = T1I->getOpcode(); if (Opc != Hexagon::J2_jumpt && Opc != Hexagon::J2_jumpf) return false; unsigned PredR = T1I->getOperand(0).getReg(); // Get the layout successor, or 0 if B does not have one. MachineFunction::iterator NextBI = std::next(MachineFunction::iterator(B)); MachineBasicBlock *NextB = (NextBI != MFN->end()) ? &*NextBI : 0; MachineBasicBlock *T1B = T1I->getOperand(1).getMBB(); MachineBasicBlock::const_iterator T2I = std::next(T1I); // The second terminator should be an unconditional branch. assert(T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump); MachineBasicBlock *T2B = (T2I == B->end()) ? NextB : T2I->getOperand(0).getMBB(); if (T1B == T2B) { // XXX merge if T1B == NextB, or convert branch to unconditional. // mark as diamond with both sides equal? return false; } // Loop could be null for both. if (MLI->getLoopFor(T1B) != L || MLI->getLoopFor(T2B) != L) return false; // Record the true/false blocks in such a way that "true" means "if (PredR)", // and "false" means "if (!PredR)". if (Opc == Hexagon::J2_jumpt) TB = T1B, FB = T2B; else TB = T2B, FB = T1B; if (!MDT->properlyDominates(B, TB) || !MDT->properlyDominates(B, FB)) return false; // Detect triangle first. In case of a triangle, one of the blocks TB/FB // can fall through into the other, in other words, it will be executed // in both cases. We only want to predicate the block that is executed // conditionally. unsigned TNP = TB->pred_size(), FNP = FB->pred_size(); unsigned TNS = TB->succ_size(), FNS = FB->succ_size(); // A block is predicable if it has one predecessor (it must be B), and // it has a single successor. In fact, the block has to end either with // an unconditional branch (which can be predicated), or with a fall- // through. bool TOk = (TNP == 1) && (TNS == 1); bool FOk = (FNP == 1) && (FNS == 1); // If neither is predicable, there is nothing interesting. if (!TOk && !FOk) return false; MachineBasicBlock *TSB = (TNS > 0) ? *TB->succ_begin() : 0; MachineBasicBlock *FSB = (FNS > 0) ? *FB->succ_begin() : 0; MachineBasicBlock *JB = 0; if (TOk) { if (FOk) { if (TSB == FSB) JB = TSB; // Diamond: "if (P) then TB; else FB;". } else { // TOk && !FOk if (TSB == FB) { JB = FB; FB = 0; } } } else { // !TOk && FOk (at least one must be true by now). if (FSB == TB) { JB = TB; TB = 0; } } // Don't try to predicate loop preheaders. if ((TB && isPreheader(TB)) || (FB && isPreheader(FB))) { DEBUG(dbgs() << "One of blocks " << PrintMB(TB) << ", " << PrintMB(FB) << " is a loop preheader. Skipping.\n"); return false; } FP = FlowPattern(B, PredR, TB, FB, JB); DEBUG(dbgs() << "Detected " << PrintFP(FP, *TRI) << "\n"); return true; } // KLUDGE: HexagonInstrInfo::AnalyzeBranch won't work on a block that // contains EH_LABEL. bool HexagonEarlyIfConversion::hasEHLabel(const MachineBasicBlock *B) const { for (auto &I : *B) if (I.isEHLabel()) return true; return false; } // KLUDGE: HexagonInstrInfo::AnalyzeBranch may be unable to recognize // that a block can never fall-through. bool HexagonEarlyIfConversion::hasUncondBranch(const MachineBasicBlock *B) const { MachineBasicBlock::const_iterator I = B->getFirstTerminator(), E = B->end(); while (I != E) { if (I->isBarrier()) return true; ++I; } return false; } bool HexagonEarlyIfConversion::isValidCandidate(const MachineBasicBlock *B) const { if (!B) return true; if (B->isEHPad() || B->hasAddressTaken()) return false; if (B->succ_size() == 0) return false; for (auto &MI : *B) { if (MI.isDebugValue()) continue; if (MI.isConditionalBranch()) return false; unsigned Opc = MI.getOpcode(); bool IsJMP = (Opc == Hexagon::J2_jump); if (!isPredicableStore(&MI) && !IsJMP && !isSafeToSpeculate(&MI)) return false; // Look for predicate registers defined by this instruction. It's ok // to speculate such an instruction, but the predicate register cannot // be used outside of this block (or else it won't be possible to // update the use of it after predication). PHI uses will be updated // to use a result of a MUX, and a MUX cannot be created for predicate // registers. for (ConstMIOperands MO(&MI); MO.isValid(); ++MO) { if (!MO->isReg() || !MO->isDef()) continue; unsigned R = MO->getReg(); if (!TargetRegisterInfo::isVirtualRegister(R)) continue; if (MRI->getRegClass(R) != &Hexagon::PredRegsRegClass) continue; for (auto U = MRI->use_begin(R); U != MRI->use_end(); ++U) if (U->getParent()->isPHI()) return false; } } return true; } bool HexagonEarlyIfConversion::usesUndefVReg(const MachineInstr *MI) const { for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { if (!MO->isReg() || !MO->isUse()) continue; unsigned R = MO->getReg(); if (!TargetRegisterInfo::isVirtualRegister(R)) continue; const MachineInstr *DefI = MRI->getVRegDef(R); // "Undefined" virtual registers are actually defined via IMPLICIT_DEF. assert(DefI && "Expecting a reaching def in MRI"); if (DefI->isImplicitDef()) return true; } return false; } bool HexagonEarlyIfConversion::isValid(const FlowPattern &FP) const { if (hasEHLabel(FP.SplitB)) // KLUDGE: see function definition return false; if (FP.TrueB && !isValidCandidate(FP.TrueB)) return false; if (FP.FalseB && !isValidCandidate(FP.FalseB)) return false; // Check the PHIs in the join block. If any of them use a register // that is defined as IMPLICIT_DEF, do not convert this. This can // legitimately happen if one side of the split never executes, but // the compiler is unable to prove it. That side may then seem to // provide an "undef" value to the join block, however it will never // execute at run-time. If we convert this case, the "undef" will // be used in a MUX instruction, and that may seem like actually // using an undefined value to other optimizations. This could lead // to trouble further down the optimization stream, cause assertions // to fail, etc. if (FP.JoinB) { const MachineBasicBlock &B = *FP.JoinB; for (auto &MI : B) { if (!MI.isPHI()) break; if (usesUndefVReg(&MI)) return false; unsigned DefR = MI.getOperand(0).getReg(); const TargetRegisterClass *RC = MRI->getRegClass(DefR); if (RC == &Hexagon::PredRegsRegClass) return false; } } return true; } unsigned HexagonEarlyIfConversion::computePhiCost(MachineBasicBlock *B) const { assert(B->pred_size() <= 2); if (B->pred_size() < 2) return 0; unsigned Cost = 0; MachineBasicBlock::const_iterator I, E = B->getFirstNonPHI(); for (I = B->begin(); I != E; ++I) { const MachineOperand &RO1 = I->getOperand(1); const MachineOperand &RO3 = I->getOperand(3); assert(RO1.isReg() && RO3.isReg()); // Must have a MUX if the phi uses a subregister. if (RO1.getSubReg() != 0 || RO3.getSubReg() != 0) { Cost++; continue; } MachineInstr *Def1 = MRI->getVRegDef(RO1.getReg()); MachineInstr *Def3 = MRI->getVRegDef(RO3.getReg()); if (!TII->isPredicable(Def1) || !TII->isPredicable(Def3)) Cost++; } return Cost; } unsigned HexagonEarlyIfConversion::countPredicateDefs( const MachineBasicBlock *B) const { unsigned PredDefs = 0; for (auto &MI : *B) { for (ConstMIOperands MO(&MI); MO.isValid(); ++MO) { if (!MO->isReg() || !MO->isDef()) continue; unsigned R = MO->getReg(); if (!TargetRegisterInfo::isVirtualRegister(R)) continue; if (MRI->getRegClass(R) == &Hexagon::PredRegsRegClass) PredDefs++; } } return PredDefs; } bool HexagonEarlyIfConversion::isProfitable(const FlowPattern &FP) const { if (FP.TrueB && FP.FalseB) { // Do not IfCovert if the branch is one sided. if (MBPI) { BranchProbability Prob(9, 10); if (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob) return false; if (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob) return false; } // If both sides are predicable, convert them if they join, and the // join block has no other predecessors. MachineBasicBlock *TSB = *FP.TrueB->succ_begin(); MachineBasicBlock *FSB = *FP.FalseB->succ_begin(); if (TSB != FSB) return false; if (TSB->pred_size() != 2) return false; } // Calculate the total size of the predicated blocks. // Assume instruction counts without branches to be the approximation of // the code size. If the predicated blocks are smaller than a packet size, // approximate the spare room in the packet that could be filled with the // predicated/speculated instructions. unsigned TS = 0, FS = 0, Spare = 0; if (FP.TrueB) { TS = std::distance(FP.TrueB->begin(), FP.TrueB->getFirstTerminator()); if (TS < HEXAGON_PACKET_SIZE) Spare += HEXAGON_PACKET_SIZE-TS; } if (FP.FalseB) { FS = std::distance(FP.FalseB->begin(), FP.FalseB->getFirstTerminator()); if (FS < HEXAGON_PACKET_SIZE) Spare += HEXAGON_PACKET_SIZE-TS; } unsigned TotalIn = TS+FS; DEBUG(dbgs() << "Total number of instructions to be predicated/speculated: " << TotalIn << ", spare room: " << Spare << "\n"); if (TotalIn >= SizeLimit+Spare) return false; // Count the number of PHI nodes that will need to be updated (converted // to MUX). Those can be later converted to predicated instructions, so // they aren't always adding extra cost. // KLUDGE: Also, count the number of predicate register definitions in // each block. The scheduler may increase the pressure of these and cause // expensive spills (e.g. bitmnp01). unsigned TotalPh = 0; unsigned PredDefs = countPredicateDefs(FP.SplitB); if (FP.JoinB) { TotalPh = computePhiCost(FP.JoinB); PredDefs += countPredicateDefs(FP.JoinB); } else { if (FP.TrueB && FP.TrueB->succ_size() > 0) { MachineBasicBlock *SB = *FP.TrueB->succ_begin(); TotalPh += computePhiCost(SB); PredDefs += countPredicateDefs(SB); } if (FP.FalseB && FP.FalseB->succ_size() > 0) { MachineBasicBlock *SB = *FP.FalseB->succ_begin(); TotalPh += computePhiCost(SB); PredDefs += countPredicateDefs(SB); } } DEBUG(dbgs() << "Total number of extra muxes from converted phis: " << TotalPh << "\n"); if (TotalIn+TotalPh >= SizeLimit+Spare) return false; DEBUG(dbgs() << "Total number of predicate registers: " << PredDefs << "\n"); if (PredDefs > 4) return false; return true; } bool HexagonEarlyIfConversion::visitBlock(MachineBasicBlock *B, MachineLoop *L) { bool Changed = false; // Visit all dominated blocks from the same loop first, then process B. MachineDomTreeNode *N = MDT->getNode(B); typedef GraphTraits<MachineDomTreeNode*> GTN; // We will change CFG/DT during this traversal, so take precautions to // avoid problems related to invalidated iterators. In fact, processing // a child C of B cannot cause another child to be removed, but it can // cause a new child to be added (which was a child of C before C itself // was removed. This new child C, however, would have been processed // prior to processing B, so there is no need to process it again. // Simply keep a list of children of B, and traverse that list. typedef SmallVector<MachineDomTreeNode*,4> DTNodeVectType; DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N)); for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) { MachineBasicBlock *SB = (*I)->getBlock(); if (!Deleted.count(SB)) Changed |= visitBlock(SB, L); } // When walking down the dominator tree, we want to traverse through // blocks from nested (other) loops, because they can dominate blocks // that are in L. Skip the non-L blocks only after the tree traversal. if (MLI->getLoopFor(B) != L) return Changed; FlowPattern FP; if (!matchFlowPattern(B, L, FP)) return Changed; if (!isValid(FP)) { DEBUG(dbgs() << "Conversion is not valid\n"); return Changed; } if (!isProfitable(FP)) { DEBUG(dbgs() << "Conversion is not profitable\n"); return Changed; } convert(FP); simplifyFlowGraph(FP); return true; } bool HexagonEarlyIfConversion::visitLoop(MachineLoop *L) { MachineBasicBlock *HB = L ? L->getHeader() : 0; DEBUG((L ? dbgs() << "Visiting loop H:" << PrintMB(HB) : dbgs() << "Visiting function") << "\n"); bool Changed = false; if (L) { for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) Changed |= visitLoop(*I); } MachineBasicBlock *EntryB = GraphTraits<MachineFunction*>::getEntryNode(MFN); Changed |= visitBlock(L ? HB : EntryB, L); return Changed; } bool HexagonEarlyIfConversion::isPredicableStore(const MachineInstr *MI) const { // Exclude post-increment stores. Those return a value, so we cannot // predicate them. unsigned Opc = MI->getOpcode(); using namespace Hexagon; switch (Opc) { // Store byte: case S2_storerb_io: case S4_storerb_rr: case S2_storerbabs: case S4_storeirb_io: case S2_storerbgp: // Store halfword: case S2_storerh_io: case S4_storerh_rr: case S2_storerhabs: case S4_storeirh_io: case S2_storerhgp: // Store upper halfword: case S2_storerf_io: case S4_storerf_rr: case S2_storerfabs: case S2_storerfgp: // Store word: case S2_storeri_io: case S4_storeri_rr: case S2_storeriabs: case S4_storeiri_io: case S2_storerigp: // Store doubleword: case S2_storerd_io: case S4_storerd_rr: case S2_storerdabs: case S2_storerdgp: return true; } return false; } bool HexagonEarlyIfConversion::isSafeToSpeculate(const MachineInstr *MI) const { if (MI->mayLoad() || MI->mayStore()) return false; if (MI->isCall() || MI->isBarrier() || MI->isBranch()) return false; if (MI->hasUnmodeledSideEffects()) return false; return true; } unsigned HexagonEarlyIfConversion::getCondStoreOpcode(unsigned Opc, bool IfTrue) const { // Exclude post-increment stores. using namespace Hexagon; switch (Opc) { case S2_storerb_io: return IfTrue ? S2_pstorerbt_io : S2_pstorerbf_io; case S4_storerb_rr: return IfTrue ? S4_pstorerbt_rr : S4_pstorerbf_rr; case S2_storerbabs: case S2_storerbgp: return IfTrue ? S4_pstorerbt_abs : S4_pstorerbf_abs; case S4_storeirb_io: return IfTrue ? S4_storeirbt_io : S4_storeirbf_io; case S2_storerh_io: return IfTrue ? S2_pstorerht_io : S2_pstorerhf_io; case S4_storerh_rr: return IfTrue ? S4_pstorerht_rr : S4_pstorerhf_rr; case S2_storerhabs: case S2_storerhgp: return IfTrue ? S4_pstorerht_abs : S4_pstorerhf_abs; case S2_storerf_io: return IfTrue ? S2_pstorerft_io : S2_pstorerff_io; case S4_storerf_rr: return IfTrue ? S4_pstorerft_rr : S4_pstorerff_rr; case S2_storerfabs: case S2_storerfgp: return IfTrue ? S4_pstorerft_abs : S4_pstorerff_abs; case S4_storeirh_io: return IfTrue ? S4_storeirht_io : S4_storeirhf_io; case S2_storeri_io: return IfTrue ? S2_pstorerit_io : S2_pstorerif_io; case S4_storeri_rr: return IfTrue ? S4_pstorerit_rr : S4_pstorerif_rr; case S2_storeriabs: case S2_storerigp: return IfTrue ? S4_pstorerit_abs : S4_pstorerif_abs; case S4_storeiri_io: return IfTrue ? S4_storeirit_io : S4_storeirif_io; case S2_storerd_io: return IfTrue ? S2_pstorerdt_io : S2_pstorerdf_io; case S4_storerd_rr: return IfTrue ? S4_pstorerdt_rr : S4_pstorerdf_rr; case S2_storerdabs: case S2_storerdgp: return IfTrue ? S4_pstorerdt_abs : S4_pstorerdf_abs; } llvm_unreachable("Unexpected opcode"); return 0; } void HexagonEarlyIfConversion::predicateInstr(MachineBasicBlock *ToB, MachineBasicBlock::iterator At, MachineInstr *MI, unsigned PredR, bool IfTrue) { DebugLoc DL; if (At != ToB->end()) DL = At->getDebugLoc(); else if (!ToB->empty()) DL = ToB->back().getDebugLoc(); unsigned Opc = MI->getOpcode(); if (isPredicableStore(MI)) { unsigned COpc = getCondStoreOpcode(Opc, IfTrue); assert(COpc); MachineInstrBuilder MIB = BuildMI(*ToB, At, DL, TII->get(COpc)) .addReg(PredR); for (MIOperands MO(MI); MO.isValid(); ++MO) MIB.addOperand(*MO); // Set memory references. MachineInstr::mmo_iterator MMOBegin = MI->memoperands_begin(); MachineInstr::mmo_iterator MMOEnd = MI->memoperands_end(); MIB.setMemRefs(MMOBegin, MMOEnd); MI->eraseFromParent(); return; } if (Opc == Hexagon::J2_jump) { MachineBasicBlock *TB = MI->getOperand(0).getMBB(); const MCInstrDesc &D = TII->get(IfTrue ? Hexagon::J2_jumpt : Hexagon::J2_jumpf); BuildMI(*ToB, At, DL, D) .addReg(PredR) .addMBB(TB); MI->eraseFromParent(); return; } // Print the offending instruction unconditionally as we are about to // abort. dbgs() << *MI; llvm_unreachable("Unexpected instruction"); } // Predicate/speculate non-branch instructions from FromB into block ToB. // Leave the branches alone, they will be handled later. Btw, at this point // FromB should have at most one branch, and it should be unconditional. void HexagonEarlyIfConversion::predicateBlockNB(MachineBasicBlock *ToB, MachineBasicBlock::iterator At, MachineBasicBlock *FromB, unsigned PredR, bool IfTrue) { DEBUG(dbgs() << "Predicating block " << PrintMB(FromB) << "\n"); MachineBasicBlock::iterator End = FromB->getFirstTerminator(); MachineBasicBlock::iterator I, NextI; for (I = FromB->begin(); I != End; I = NextI) { assert(!I->isPHI()); NextI = std::next(I); if (isSafeToSpeculate(&*I)) ToB->splice(At, FromB, I); else predicateInstr(ToB, At, &*I, PredR, IfTrue); } } void HexagonEarlyIfConversion::updatePhiNodes(MachineBasicBlock *WhereB, const FlowPattern &FP) { // Visit all PHI nodes in the WhereB block and generate MUX instructions // in the split block. Update the PHI nodes with the values of the MUX. auto NonPHI = WhereB->getFirstNonPHI(); for (auto I = WhereB->begin(); I != NonPHI; ++I) { MachineInstr *PN = &*I; // Registers and subregisters corresponding to TrueB, FalseB and SplitB. unsigned TR = 0, TSR = 0, FR = 0, FSR = 0, SR = 0, SSR = 0; for (int i = PN->getNumOperands()-2; i > 0; i -= 2) { const MachineOperand &RO = PN->getOperand(i), &BO = PN->getOperand(i+1); if (BO.getMBB() == FP.SplitB) SR = RO.getReg(), SSR = RO.getSubReg(); else if (BO.getMBB() == FP.TrueB) TR = RO.getReg(), TSR = RO.getSubReg(); else if (BO.getMBB() == FP.FalseB) FR = RO.getReg(), FSR = RO.getSubReg(); else continue; PN->RemoveOperand(i+1); PN->RemoveOperand(i); } if (TR == 0) TR = SR, TSR = SSR; else if (FR == 0) FR = SR, FSR = SSR; assert(TR && FR); using namespace Hexagon; unsigned DR = PN->getOperand(0).getReg(); const TargetRegisterClass *RC = MRI->getRegClass(DR); const MCInstrDesc &D = RC == &IntRegsRegClass ? TII->get(C2_mux) : TII->get(MUX64_rr); MachineBasicBlock::iterator MuxAt = FP.SplitB->getFirstTerminator(); DebugLoc DL; if (MuxAt != FP.SplitB->end()) DL = MuxAt->getDebugLoc(); unsigned MuxR = MRI->createVirtualRegister(RC); BuildMI(*FP.SplitB, MuxAt, DL, D, MuxR) .addReg(FP.PredR) .addReg(TR, 0, TSR) .addReg(FR, 0, FSR); PN->addOperand(MachineOperand::CreateReg(MuxR, false)); PN->addOperand(MachineOperand::CreateMBB(FP.SplitB)); } } void HexagonEarlyIfConversion::convert(const FlowPattern &FP) { MachineBasicBlock *TSB = 0, *FSB = 0; MachineBasicBlock::iterator OldTI = FP.SplitB->getFirstTerminator(); assert(OldTI != FP.SplitB->end()); DebugLoc DL = OldTI->getDebugLoc(); if (FP.TrueB) { TSB = *FP.TrueB->succ_begin(); predicateBlockNB(FP.SplitB, OldTI, FP.TrueB, FP.PredR, true); } if (FP.FalseB) { FSB = *FP.FalseB->succ_begin(); MachineBasicBlock::iterator At = FP.SplitB->getFirstTerminator(); predicateBlockNB(FP.SplitB, At, FP.FalseB, FP.PredR, false); } // Regenerate new terminators in the split block and update the successors. // First, remember any information that may be needed later and remove the // existing terminators/successors from the split block. MachineBasicBlock *SSB = 0; FP.SplitB->erase(OldTI, FP.SplitB->end()); while (FP.SplitB->succ_size() > 0) { MachineBasicBlock *T = *FP.SplitB->succ_begin(); // It's possible that the split block had a successor that is not a pre- // dicated block. This could only happen if there was only one block to // be predicated. Example: // split_b: // if (p) jump true_b // jump unrelated2_b // unrelated1_b: // ... // unrelated2_b: ; can have other predecessors, so it's not "false_b" // jump other_b // true_b: ; only reachable from split_b, can be predicated // ... // // Find this successor (SSB) if it exists. if (T != FP.TrueB && T != FP.FalseB) { assert(!SSB); SSB = T; } FP.SplitB->removeSuccessor(FP.SplitB->succ_begin()); } // Insert new branches and update the successors of the split block. This // may create unconditional branches to the layout successor, etc., but // that will be cleaned up later. For now, make sure that correct code is // generated. if (FP.JoinB) { assert(!SSB || SSB == FP.JoinB); BuildMI(*FP.SplitB, FP.SplitB->end(), DL, TII->get(Hexagon::J2_jump)) .addMBB(FP.JoinB); FP.SplitB->addSuccessor(FP.JoinB); } else { bool HasBranch = false; if (TSB) { BuildMI(*FP.SplitB, FP.SplitB->end(), DL, TII->get(Hexagon::J2_jumpt)) .addReg(FP.PredR) .addMBB(TSB); FP.SplitB->addSuccessor(TSB); HasBranch = true; } if (FSB) { const MCInstrDesc &D = HasBranch ? TII->get(Hexagon::J2_jump) : TII->get(Hexagon::J2_jumpf); MachineInstrBuilder MIB = BuildMI(*FP.SplitB, FP.SplitB->end(), DL, D); if (!HasBranch) MIB.addReg(FP.PredR); MIB.addMBB(FSB); FP.SplitB->addSuccessor(FSB); } if (SSB) { // This cannot happen if both TSB and FSB are set. [TF]SB are the // successor blocks of the TrueB and FalseB (or null of the TrueB // or FalseB block is null). SSB is the potential successor block // of the SplitB that is neither TrueB nor FalseB. BuildMI(*FP.SplitB, FP.SplitB->end(), DL, TII->get(Hexagon::J2_jump)) .addMBB(SSB); FP.SplitB->addSuccessor(SSB); } } // What is left to do is to update the PHI nodes that could have entries // referring to predicated blocks. if (FP.JoinB) { updatePhiNodes(FP.JoinB, FP); } else { if (TSB) updatePhiNodes(TSB, FP); if (FSB) updatePhiNodes(FSB, FP); // Nothing to update in SSB, since SSB's predecessors haven't changed. } } void HexagonEarlyIfConversion::removeBlock(MachineBasicBlock *B) { DEBUG(dbgs() << "Removing block " << PrintMB(B) << "\n"); // Transfer the immediate dominator information from B to its descendants. MachineDomTreeNode *N = MDT->getNode(B); MachineDomTreeNode *IDN = N->getIDom(); if (IDN) { MachineBasicBlock *IDB = IDN->getBlock(); typedef GraphTraits<MachineDomTreeNode*> GTN; typedef SmallVector<MachineDomTreeNode*,4> DTNodeVectType; DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N)); for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) { MachineBasicBlock *SB = (*I)->getBlock(); MDT->changeImmediateDominator(SB, IDB); } } while (B->succ_size() > 0) B->removeSuccessor(B->succ_begin()); for (auto I = B->pred_begin(), E = B->pred_end(); I != E; ++I) (*I)->removeSuccessor(B, true); Deleted.insert(B); MDT->eraseNode(B); MFN->erase(B->getIterator()); } void HexagonEarlyIfConversion::eliminatePhis(MachineBasicBlock *B) { DEBUG(dbgs() << "Removing phi nodes from block " << PrintMB(B) << "\n"); MachineBasicBlock::iterator I, NextI, NonPHI = B->getFirstNonPHI(); for (I = B->begin(); I != NonPHI; I = NextI) { NextI = std::next(I); MachineInstr *PN = &*I; assert(PN->getNumOperands() == 3 && "Invalid phi node"); MachineOperand &UO = PN->getOperand(1); unsigned UseR = UO.getReg(), UseSR = UO.getSubReg(); unsigned DefR = PN->getOperand(0).getReg(); unsigned NewR = UseR; if (UseSR) { // MRI.replaceVregUsesWith does not allow to update the subregister, // so instead of doing the use-iteration here, create a copy into a // "non-subregistered" register. DebugLoc DL = PN->getDebugLoc(); const TargetRegisterClass *RC = MRI->getRegClass(DefR); NewR = MRI->createVirtualRegister(RC); NonPHI = BuildMI(*B, NonPHI, DL, TII->get(TargetOpcode::COPY), NewR) .addReg(UseR, 0, UseSR); } MRI->replaceRegWith(DefR, NewR); B->erase(I); } } void HexagonEarlyIfConversion::replacePhiEdges(MachineBasicBlock *OldB, MachineBasicBlock *NewB) { for (auto I = OldB->succ_begin(), E = OldB->succ_end(); I != E; ++I) { MachineBasicBlock *SB = *I; MachineBasicBlock::iterator P, N = SB->getFirstNonPHI(); for (P = SB->begin(); P != N; ++P) { MachineInstr *PN = &*P; for (MIOperands MO(PN); MO.isValid(); ++MO) if (MO->isMBB() && MO->getMBB() == OldB) MO->setMBB(NewB); } } } void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB, MachineBasicBlock *SuccB) { DEBUG(dbgs() << "Merging blocks " << PrintMB(PredB) << " and " << PrintMB(SuccB) << "\n"); bool TermOk = hasUncondBranch(SuccB); eliminatePhis(SuccB); TII->RemoveBranch(*PredB); PredB->removeSuccessor(SuccB); PredB->splice(PredB->end(), SuccB, SuccB->begin(), SuccB->end()); MachineBasicBlock::succ_iterator I, E = SuccB->succ_end(); for (I = SuccB->succ_begin(); I != E; ++I) PredB->addSuccessor(*I); PredB->normalizeSuccProbs(); replacePhiEdges(SuccB, PredB); removeBlock(SuccB); if (!TermOk) PredB->updateTerminator(); } void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) { if (FP.TrueB) removeBlock(FP.TrueB); if (FP.FalseB) removeBlock(FP.FalseB); FP.SplitB->updateTerminator(); if (FP.SplitB->succ_size() != 1) return; MachineBasicBlock *SB = *FP.SplitB->succ_begin(); if (SB->pred_size() != 1) return; // By now, the split block has only one successor (SB), and SB has only // one predecessor. We can try to merge them. We will need to update ter- // minators in FP.Split+SB, and that requires working AnalyzeBranch, which // fails on Hexagon for blocks that have EH_LABELs. However, if SB ends // with an unconditional branch, we won't need to touch the terminators. if (!hasEHLabel(SB) || hasUncondBranch(SB)) mergeBlocks(FP.SplitB, SB); } bool HexagonEarlyIfConversion::runOnMachineFunction(MachineFunction &MF) { auto &ST = MF.getSubtarget(); TII = ST.getInstrInfo(); TRI = ST.getRegisterInfo(); MFN = &MF; MRI = &MF.getRegInfo(); MDT = &getAnalysis<MachineDominatorTree>(); MLI = &getAnalysis<MachineLoopInfo>(); MBPI = EnableHexagonBP ? &getAnalysis<MachineBranchProbabilityInfo>() : nullptr; Deleted.clear(); bool Changed = false; for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I) Changed |= visitLoop(*I); Changed |= visitLoop(0); return Changed; } //===----------------------------------------------------------------------===// // Public Constructor Functions //===----------------------------------------------------------------------===// FunctionPass *llvm::createHexagonEarlyIfConversion() { return new HexagonEarlyIfConversion(); }