Home | History | Annotate | Line # | Download | only in WebAssembly 
      1 //===--- WebAssemblyOptimizeLiveIntervals.cpp - LiveInterval processing ---===//
      2 //
      3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
      4 // See https://llvm.org/LICENSE.txt for license information.
      5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
      6 //
      7 //===----------------------------------------------------------------------===//
      8 ///
      9 /// \file
     10 /// Optimize LiveIntervals for use in a post-RA context.
     11 //
     12 /// LiveIntervals normally runs before register allocation when the code is
     13 /// only recently lowered out of SSA form, so it's uncommon for registers to
     14 /// have multiple defs, and when they do, the defs are usually closely related.
     15 /// Later, after coalescing, tail duplication, and other optimizations, it's
     16 /// more common to see registers with multiple unrelated defs. This pass
     17 /// updates LiveIntervals to distribute the value numbers across separate
     18 /// LiveIntervals.
     19 ///
     20 //===----------------------------------------------------------------------===//
     21 
     22 #include "WebAssembly.h"
     23 #include "WebAssemblyMachineFunctionInfo.h"
     24 #include "WebAssemblySubtarget.h"
     25 #include "llvm/CodeGen/LiveIntervals.h"
     26 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
     27 #include "llvm/CodeGen/MachineRegisterInfo.h"
     28 #include "llvm/CodeGen/Passes.h"
     29 #include "llvm/Support/Debug.h"
     30 #include "llvm/Support/raw_ostream.h"
     31 using namespace llvm;
     32 
     33 #define DEBUG_TYPE "wasm-optimize-live-intervals"
     34 
     35 namespace {
     36 class WebAssemblyOptimizeLiveIntervals final : public MachineFunctionPass {
     37   StringRef getPassName() const override {
     38     return "WebAssembly Optimize Live Intervals";
     39   }
     40 
     41   void getAnalysisUsage(AnalysisUsage &AU) const override {
     42     AU.setPreservesCFG();
     43     AU.addRequired<LiveIntervals>();
     44     AU.addPreserved<MachineBlockFrequencyInfo>();
     45     AU.addPreserved<SlotIndexes>();
     46     AU.addPreserved<LiveIntervals>();
     47     AU.addPreservedID(LiveVariablesID);
     48     AU.addPreservedID(MachineDominatorsID);
     49     MachineFunctionPass::getAnalysisUsage(AU);
     50   }
     51 
     52   bool runOnMachineFunction(MachineFunction &MF) override;
     53 
     54 public:
     55   static char ID; // Pass identification, replacement for typeid
     56   WebAssemblyOptimizeLiveIntervals() : MachineFunctionPass(ID) {}
     57 };
     58 } // end anonymous namespace
     59 
     60 char WebAssemblyOptimizeLiveIntervals::ID = 0;
     61 INITIALIZE_PASS(WebAssemblyOptimizeLiveIntervals, DEBUG_TYPE,
     62                 "Optimize LiveIntervals for WebAssembly", false, false)
     63 
     64 FunctionPass *llvm::createWebAssemblyOptimizeLiveIntervals() {
     65   return new WebAssemblyOptimizeLiveIntervals();
     66 }
     67 
     68 bool WebAssemblyOptimizeLiveIntervals::runOnMachineFunction(
     69     MachineFunction &MF) {
     70   LLVM_DEBUG(dbgs() << "********** Optimize LiveIntervals **********\n"
     71                        "********** Function: "
     72                     << MF.getName() << '\n');
     73 
     74   MachineRegisterInfo &MRI = MF.getRegInfo();
     75   auto &LIS = getAnalysis<LiveIntervals>();
     76 
     77   // We don't preserve SSA form.
     78   MRI.leaveSSA();
     79 
     80   assert(MRI.tracksLiveness() && "OptimizeLiveIntervals expects liveness");
     81 
     82   // Split multiple-VN LiveIntervals into multiple LiveIntervals.
     83   SmallVector<LiveInterval *, 4> SplitLIs;
     84   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
     85     unsigned Reg = Register::index2VirtReg(I);
     86     auto &TRI = *MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
     87 
     88     if (MRI.reg_nodbg_empty(Reg))
     89       continue;
     90 
     91     LIS.splitSeparateComponents(LIS.getInterval(Reg), SplitLIs);
     92     if (Reg == TRI.getFrameRegister(MF) && SplitLIs.size() > 0) {
     93       // The live interval for the frame register was split, resulting in a new
     94       // VReg. For now we only support debug info output for a single frame base
     95       // value for the function, so just use the last one. It will certainly be
     96       // wrong for some part of the function, but until we are able to track
     97       // values through live-range splitting and stackification, it will have to
     98       // do.
     99       MF.getInfo<WebAssemblyFunctionInfo>()->setFrameBaseVreg(
    100           SplitLIs.back()->reg());
    101     }
    102     SplitLIs.clear();
    103   }
    104 
    105   // In PrepareForLiveIntervals, we conservatively inserted IMPLICIT_DEF
    106   // instructions to satisfy LiveIntervals' requirement that all uses be
    107   // dominated by defs. Now that LiveIntervals has computed which of these
    108   // defs are actually needed and which are dead, remove the dead ones.
    109   for (auto MII = MF.begin()->begin(), MIE = MF.begin()->end(); MII != MIE;) {
    110     MachineInstr *MI = &*MII++;
    111     if (MI->isImplicitDef() && MI->getOperand(0).isDead()) {
    112       LiveInterval &LI = LIS.getInterval(MI->getOperand(0).getReg());
    113       LIS.removeVRegDefAt(LI, LIS.getInstructionIndex(*MI).getRegSlot());
    114       LIS.RemoveMachineInstrFromMaps(*MI);
    115       MI->eraseFromParent();
    116     }
    117   }
    118 
    119   return true;
    120 }
    121