From adf28177eb0495c60c4ad07a2f2c67ba2fc10dc1 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Thu, 28 Jan 2016 01:22:44 +0000 Subject: [WebAssembly] Enhanced register stackification This patch revamps the RegStackifier pass with a new tree traversal mechanism, enabling three major new features: - Stackification of values with multiple uses, using the result value of set_local - More aggressive stackification of instructions with side effects - Reordering operands in commutative instructions to enable more stackification. llvm-svn: 259009 --- .../Target/WebAssembly/WebAssemblyRegStackify.cpp | 381 +++++++++++++++++---- 1 file changed, 320 insertions(+), 61 deletions(-) (limited to 'llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp') diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp b/llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp index df9e6de5ffc..3377ca0979d 100644 --- a/llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp +++ b/llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp @@ -27,6 +27,8 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/Support/Debug.h" @@ -44,12 +46,13 @@ class WebAssemblyRegStackify final : public MachineFunctionPass { void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); - AU.addPreservedID(MachineDominatorsID); AU.addPreservedID(LiveVariablesID); + AU.addPreserved(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -89,8 +92,8 @@ static void ImposeStackOrdering(MachineInstr *MI) { // TODO: Compute memory dependencies in a way that uses AliasAnalysis to be // more precise. static bool IsSafeToMove(const MachineInstr *Def, const MachineInstr *Insert, - AliasAnalysis &AA, LiveIntervals &LIS, - MachineRegisterInfo &MRI) { + AliasAnalysis &AA, const LiveIntervals &LIS, + const MachineRegisterInfo &MRI) { assert(Def->getParent() == Insert->getParent()); bool SawStore = false, SawSideEffects = false; MachineBasicBlock::const_iterator D(Def), I(Insert); @@ -133,6 +136,250 @@ static bool IsSafeToMove(const MachineInstr *Def, const MachineInstr *Insert, !(SawSideEffects && !Def->isSafeToMove(&AA, SawStore)); } +/// Test whether OneUse, a use of Reg, dominates all of Reg's other uses. +static bool OneUseDominatesOtherUses(unsigned Reg, const MachineOperand &OneUse, + const MachineBasicBlock &MBB, + const MachineRegisterInfo &MRI, + const MachineDominatorTree &MDT) { + for (const MachineOperand &Use : MRI.use_operands(Reg)) { + if (&Use == &OneUse) + continue; + const MachineInstr *UseInst = Use.getParent(); + const MachineInstr *OneUseInst = OneUse.getParent(); + if (UseInst->getOpcode() == TargetOpcode::PHI) { + // Test that the PHI use, which happens on the CFG edge rather than + // within the PHI's own block, is dominated by the one selected use. + const MachineBasicBlock *Pred = + UseInst->getOperand(&Use - &UseInst->getOperand(0) + 1).getMBB(); + if (!MDT.dominates(&MBB, Pred)) + return false; + } else if (UseInst == OneUseInst) { + // Another use in the same instruction. We need to ensure that the one + // selected use happens "before" it. + if (&OneUse > &Use) + return false; + } else { + // Test that the use is dominated by the one selected use. + if (!MDT.dominates(OneUseInst, UseInst)) + return false; + } + } + return true; +} + +/// Get the appropriate tee_local opcode for the given register class. +static unsigned GetTeeLocalOpcode(const TargetRegisterClass *RC) { + if (RC == &WebAssembly::I32RegClass) + return WebAssembly::TEE_LOCAL_I32; + if (RC == &WebAssembly::I64RegClass) + return WebAssembly::TEE_LOCAL_I64; + if (RC == &WebAssembly::F32RegClass) + return WebAssembly::TEE_LOCAL_F32; + if (RC == &WebAssembly::F64RegClass) + return WebAssembly::TEE_LOCAL_F64; + llvm_unreachable("Unexpected register class"); +} + +/// A single-use def in the same block with no intervening memory or register +/// dependencies; move the def down and nest it with the current instruction. +static MachineInstr *MoveForSingleUse(unsigned Reg, MachineInstr *Def, + MachineBasicBlock &MBB, + MachineInstr *Insert, LiveIntervals &LIS, + WebAssemblyFunctionInfo &MFI) { + MBB.splice(Insert, &MBB, Def); + LIS.handleMove(Def); + MFI.stackifyVReg(Reg); + ImposeStackOrdering(Def); + return Def; +} + +/// A trivially cloneable instruction; clone it and nest the new copy with the +/// current instruction. +static MachineInstr * +RematerializeCheapDef(unsigned Reg, MachineOperand &Op, MachineInstr *Def, + MachineBasicBlock &MBB, MachineInstr *Insert, + LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, + MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII, + const WebAssemblyRegisterInfo *TRI) { + unsigned NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg)); + TII->reMaterialize(MBB, Insert, NewReg, 0, Def, *TRI); + Op.setReg(NewReg); + MachineInstr *Clone = &*std::prev(MachineBasicBlock::instr_iterator(Insert)); + LIS.InsertMachineInstrInMaps(Clone); + LIS.createAndComputeVirtRegInterval(NewReg); + MFI.stackifyVReg(NewReg); + ImposeStackOrdering(Clone); + + // If that was the last use of the original, delete the original. + // Otherwise shrink the LiveInterval. + if (MRI.use_empty(Reg)) { + SlotIndex Idx = LIS.getInstructionIndex(Def).getRegSlot(); + LIS.removePhysRegDefAt(WebAssembly::ARGUMENTS, Idx); + LIS.removeVRegDefAt(LIS.getInterval(Reg), Idx); + LIS.removeInterval(Reg); + LIS.RemoveMachineInstrFromMaps(Def); + Def->eraseFromParent(); + } else { + LIS.shrinkToUses(&LIS.getInterval(Reg)); + } + return Clone; +} + +/// A multiple-use def in the same block with no intervening memory or register +/// dependencies; move the def down, nest it with the current instruction, and +/// insert a tee_local to satisfy the rest of the uses. As an illustration, +/// rewrite this: +/// +/// Reg = INST ... // Def +/// INST ..., Reg, ... // Insert +/// INST ..., Reg, ... +/// INST ..., Reg, ... +/// +/// to this: +/// +/// Reg = INST ... // Def (to become the new Insert) +/// TeeReg, NewReg = TEE_LOCAL_... Reg +/// INST ..., TeeReg, ... // Insert +/// INST ..., NewReg, ... +/// INST ..., NewReg, ... +/// +/// with Reg and TeeReg stackified. This eliminates a get_local from the +/// resulting code. +static MachineInstr *MoveAndTeeForMultiUse( + unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB, + MachineInstr *Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, + MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII) { + MBB.splice(Insert, &MBB, Def); + LIS.handleMove(Def); + const auto *RegClass = MRI.getRegClass(Reg); + unsigned NewReg = MRI.createVirtualRegister(RegClass); + unsigned TeeReg = MRI.createVirtualRegister(RegClass); + MRI.replaceRegWith(Reg, NewReg); + MachineInstr *Tee = BuildMI(MBB, Insert, Insert->getDebugLoc(), + TII->get(GetTeeLocalOpcode(RegClass)), TeeReg) + .addReg(NewReg, RegState::Define) + .addReg(Reg); + Op.setReg(TeeReg); + Def->getOperand(0).setReg(Reg); + LIS.InsertMachineInstrInMaps(Tee); + LIS.shrinkToUses(&LIS.getInterval(Reg)); + LIS.createAndComputeVirtRegInterval(NewReg); + LIS.createAndComputeVirtRegInterval(TeeReg); + MFI.stackifyVReg(Reg); + MFI.stackifyVReg(TeeReg); + ImposeStackOrdering(Def); + ImposeStackOrdering(Tee); + return Def; +} + +namespace { +/// A stack for walking the tree of instructions being built, visiting the +/// MachineOperands in DFS order. +class TreeWalkerState { + typedef MachineInstr::mop_iterator mop_iterator; + typedef std::reverse_iterator mop_reverse_iterator; + typedef iterator_range RangeTy; + SmallVector Worklist; + +public: + explicit TreeWalkerState(MachineInstr *Insert) { + const iterator_range &Range = Insert->explicit_uses(); + if (Range.begin() != Range.end()) + Worklist.push_back(reverse(Range)); + } + + bool Done() const { return Worklist.empty(); } + + MachineOperand &Pop() { + RangeTy &Range = Worklist.back(); + MachineOperand &Op = *Range.begin(); + Range = drop_begin(Range, 1); + if (Range.begin() == Range.end()) + Worklist.pop_back(); + assert((Worklist.empty() || + Worklist.back().begin() != Worklist.back().end()) && + "Empty ranges shouldn't remain in the worklist"); + return Op; + } + + /// Push Instr's operands onto the stack to be visited. + void PushOperands(MachineInstr *Instr) { + const iterator_range &Range(Instr->explicit_uses()); + if (Range.begin() != Range.end()) + Worklist.push_back(reverse(Range)); + } + + /// Some of Instr's operands are on the top of the stack; remove them and + /// re-insert them starting from the beginning (because we've commuted them). + void ResetTopOperands(MachineInstr *Instr) { + assert(HasRemainingOperands(Instr) && + "Reseting operands should only be done when the instruction has " + "an operand still on the stack"); + Worklist.back() = reverse(Instr->explicit_uses()); + } + + /// Test whether Instr has operands remaining to be visited at the top of + /// the stack. + bool HasRemainingOperands(const MachineInstr *Instr) const { + if (Worklist.empty()) + return false; + const RangeTy &Range = Worklist.back(); + return Range.begin() != Range.end() && Range.begin()->getParent() == Instr; + } +}; + +/// State to keep track of whether commuting is in flight or whether it's been +/// tried for the current instruction and didn't work. +class CommutingState { + /// There are effectively three states: the initial state where we haven't + /// started commuting anything and we don't know anything yet, the tenative + /// state where we've commuted the operands of the current instruction and are + /// revisting it, and the declined state where we've reverted the operands + /// back to their original order and will no longer commute it further. + bool TentativelyCommuting; + bool Declined; + + /// During the tentative state, these hold the operand indices of the commuted + /// operands. + unsigned Operand0, Operand1; + +public: + CommutingState() : TentativelyCommuting(false), Declined(false) {} + + /// Stackification for an operand was not successful due to ordering + /// constraints. If possible, and if we haven't already tried it and declined + /// it, commute Insert's operands and prepare to revisit it. + void MaybeCommute(MachineInstr *Insert, TreeWalkerState &TreeWalker, + const WebAssemblyInstrInfo *TII) { + if (TentativelyCommuting) { + assert(!Declined && + "Don't decline commuting until you've finished trying it"); + // Commuting didn't help. Revert it. + TII->commuteInstruction(Insert, /*NewMI=*/false, Operand0, Operand1); + TentativelyCommuting = false; + Declined = true; + } else if (!Declined && TreeWalker.HasRemainingOperands(Insert)) { + Operand0 = TargetInstrInfo::CommuteAnyOperandIndex; + Operand1 = TargetInstrInfo::CommuteAnyOperandIndex; + if (TII->findCommutedOpIndices(Insert, Operand0, Operand1)) { + // Tentatively commute the operands and try again. + TII->commuteInstruction(Insert, /*NewMI=*/false, Operand0, Operand1); + TreeWalker.ResetTopOperands(Insert); + TentativelyCommuting = true; + Declined = false; + } + } + } + + /// Stackification for some operand was successful. Reset to the default + /// state. + void Reset() { + TentativelyCommuting = false; + Declined = false; + } +}; +} // end anonymous namespace + bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) { DEBUG(dbgs() << "********** Register Stackifying **********\n" "********** Function: " @@ -144,6 +391,7 @@ bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) { const auto *TII = MF.getSubtarget().getInstrInfo(); const auto *TRI = MF.getSubtarget().getRegisterInfo(); AliasAnalysis &AA = getAnalysis().getAAResults(); + MachineDominatorTree &MDT = getAnalysis(); LiveIntervals &LIS = getAnalysis(); // Walk the instructions from the bottom up. Currently we don't look past @@ -165,19 +413,35 @@ bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) { // Iterate through the inputs in reverse order, since we'll be pulling // operands off the stack in LIFO order. - bool AnyStackified = false; - for (MachineOperand &Op : reverse(Insert->uses())) { + CommutingState Commuting; + TreeWalkerState TreeWalker(Insert); + while (!TreeWalker.Done()) { + MachineOperand &Op = TreeWalker.Pop(); + // We're only interested in explicit virtual register operands. - if (!Op.isReg() || Op.isImplicit() || !Op.isUse()) + if (!Op.isReg()) continue; unsigned Reg = Op.getReg(); + assert(Op.isUse() && "explicit_uses() should only iterate over uses"); + assert(!Op.isImplicit() && + "explicit_uses() should only iterate over explicit operands"); + if (TargetRegisterInfo::isPhysicalRegister(Reg)) + continue; - // Only consider registers with a single definition. - // TODO: Eventually we may relax this, to stackify phi transfers. + // Identify the definition for this register at this point. Most + // registers are in SSA form here so we try a quick MRI query first. MachineInstr *Def = MRI.getUniqueVRegDef(Reg); - if (!Def) - continue; + if (!Def) { + // MRI doesn't know what the Def is. Try asking LIS. + const VNInfo *ValNo = LIS.getInterval(Reg).getVNInfoBefore( + LIS.getInstructionIndex(Insert)); + if (!ValNo) + continue; + Def = LIS.getInstructionFromIndex(ValNo->def); + if (!Def) + continue; + } // Don't nest an INLINE_ASM def into anything, because we don't have // constraints for $pop outputs. @@ -196,59 +460,52 @@ bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) { Def->getOpcode() == WebAssembly::ARGUMENT_F64) continue; - if (MRI.hasOneUse(Reg) && Def->getParent() == &MBB && - IsSafeToMove(Def, Insert, AA, LIS, MRI)) { - // A single-use def in the same block with no intervening memory or - // register dependencies; move the def down and nest it with the - // current instruction. - // TODO: Stackify multiple-use values, taking advantage of set_local - // returning its result. - Changed = true; - AnyStackified = true; - MBB.splice(Insert, &MBB, Def); - LIS.handleMove(Def); - MFI.stackifyVReg(Reg); - ImposeStackOrdering(Def); - Insert = Def; + // Decide which strategy to take. Prefer to move a single-use value + // over cloning it, and prefer cloning over introducing a tee_local. + // For moving, we require the def to be in the same block as the use; + // this makes things simpler (LiveIntervals' handleMove function only + // supports intra-block moves) and it's MachineSink's job to catch all + // the sinking opportunities anyway. + bool SameBlock = Def->getParent() == &MBB; + bool CanMove = SameBlock && IsSafeToMove(Def, Insert, AA, LIS, MRI); + if (CanMove && MRI.hasOneUse(Reg)) { + Insert = MoveForSingleUse(Reg, Def, MBB, Insert, LIS, MFI); } else if (Def->isAsCheapAsAMove() && TII->isTriviallyReMaterializable(Def, &AA)) { - // A trivially cloneable instruction; clone it and nest the new copy - // with the current instruction. - Changed = true; - AnyStackified = true; - unsigned OldReg = Def->getOperand(0).getReg(); - unsigned NewReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg)); - TII->reMaterialize(MBB, Insert, NewReg, 0, Def, *TRI); - Op.setReg(NewReg); - MachineInstr *Clone = - &*std::prev(MachineBasicBlock::instr_iterator(Insert)); - LIS.InsertMachineInstrInMaps(Clone); - LIS.createAndComputeVirtRegInterval(NewReg); - MFI.stackifyVReg(NewReg); - ImposeStackOrdering(Clone); - Insert = Clone; - - // If that was the last use of the original, delete the original. - // Otherwise shrink the LiveInterval. - if (MRI.use_empty(OldReg)) { - SlotIndex Idx = LIS.getInstructionIndex(Def).getRegSlot(); - LIS.removePhysRegDefAt(WebAssembly::ARGUMENTS, Idx); - LIS.removeVRegDefAt(LIS.getInterval(OldReg), Idx); - LIS.removeInterval(OldReg); - LIS.RemoveMachineInstrFromMaps(Def); - Def->eraseFromParent(); - } else { - LIS.shrinkToUses(&LIS.getInterval(OldReg)); - } + Insert = RematerializeCheapDef(Reg, Op, Def, MBB, Insert, LIS, MFI, + MRI, TII, TRI); + } else if (CanMove && + OneUseDominatesOtherUses(Reg, Op, MBB, MRI, MDT)) { + Insert = MoveAndTeeForMultiUse(Reg, Op, Def, MBB, Insert, LIS, MFI, + MRI, TII); + } else { + // We failed to stackify the operand. If the problem was ordering + // constraints, Commuting may be able to help. + if (!CanMove && SameBlock) + Commuting.MaybeCommute(Insert, TreeWalker, TII); + // Proceed to the next operand. + continue; } + + // We stackified an operand. Add the defining instruction's operands to + // the worklist stack now to continue to build an ever deeper tree. + Commuting.Reset(); + TreeWalker.PushOperands(Insert); } - if (AnyStackified) + + // If we stackified any operands, skip over the tree to start looking for + // the next instruction we can build a tree on. + if (Insert != &*MII) { ImposeStackOrdering(&*MII); + MII = std::prev( + make_reverse_iterator(MachineBasicBlock::iterator(Insert))); + Changed = true; + } } } - // If we used EXPR_STACK anywhere, add it to the live-in sets everywhere - // so that it never looks like a use-before-def. + // If we used EXPR_STACK anywhere, add it to the live-in sets everywhere so + // that it never looks like a use-before-def. if (Changed) { MF.getRegInfo().addLiveIn(WebAssembly::EXPR_STACK); for (MachineBasicBlock &MBB : MF) @@ -263,23 +520,25 @@ bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) { for (MachineOperand &MO : reverse(MI.explicit_operands())) { if (!MO.isReg()) continue; - unsigned VReg = MO.getReg(); + unsigned Reg = MO.getReg(); // Don't stackify physregs like SP or FP. - if (!TargetRegisterInfo::isVirtualRegister(VReg)) + if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; - if (MFI.isVRegStackified(VReg)) { + if (MFI.isVRegStackified(Reg)) { if (MO.isDef()) - Stack.push_back(VReg); + Stack.push_back(Reg); else - assert(Stack.pop_back_val() == VReg); + assert(Stack.pop_back_val() == Reg && + "Register stack pop should be paired with a push"); } } } // TODO: Generalize this code to support keeping values on the stack across // basic block boundaries. - assert(Stack.empty()); + assert(Stack.empty() && + "Register stack pushes and pops should be balanced"); } #endif -- cgit v1.2.3