llvm/lib/Target/WebAssembly/WebAssemblyOptimizeLiveIntervals.cpp

   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<LiveIntervalsWrapperPass>();
  44     AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();
  45     AU.addPreserved<SlotIndexesWrapperPass>();
  46     AU.addPreserved<LiveIntervalsWrapperPass>();
  47     AU.addPreservedID(LiveVariablesID);
  48     AU.addPreservedID(MachineDominatorsID);
  49     MachineFunctionPass::getAnalysisUsage(AU);
  50   }
  51
  52   MachineFunctionProperties getRequiredProperties() const override {
  53     return MachineFunctionProperties().set(
  54         MachineFunctionProperties::Property::TracksLiveness);
  55   }
  56
  57   bool runOnMachineFunction(MachineFunction &MF) override;
  58
  59 public:
  60   static char ID; // Pass identification, replacement for typeid
  61   WebAssemblyOptimizeLiveIntervals() : MachineFunctionPass(ID) {}
  62 };
  63 } // end anonymous namespace
  64
  65 char WebAssemblyOptimizeLiveIntervals::ID = 0;
  66 INITIALIZE_PASS(WebAssemblyOptimizeLiveIntervals, DEBUG_TYPE,
  67                 "Optimize LiveIntervals for WebAssembly", false, false)
  68
  69 FunctionPass *llvm::createWebAssemblyOptimizeLiveIntervals() {
  70   return new WebAssemblyOptimizeLiveIntervals();
  71 }
  72
  73 bool WebAssemblyOptimizeLiveIntervals::runOnMachineFunction(
  74     MachineFunction &MF) {
  75   LLVM_DEBUG(dbgs() << "********** Optimize LiveIntervals **********\n"
  76                        "********** Function: "
  77                     << MF.getName() << '\n');
  78
  79   MachineRegisterInfo &MRI = MF.getRegInfo();
  80   auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
  81
  82   // We don't preserve SSA form.
  83   MRI.leaveSSA();
  84
  85   assert(MRI.tracksLiveness() && "OptimizeLiveIntervals expects liveness");
  86
  87   // Split multiple-VN LiveIntervals into multiple LiveIntervals.
  88   SmallVector<LiveInterval *, 4> SplitLIs;
  89   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
  90     Register Reg = Register::index2VirtReg(I);
  91     auto &TRI = *MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
  92
  93     if (MRI.reg_nodbg_empty(Reg))
  94       continue;
  95
  96     LIS.splitSeparateComponents(LIS.getInterval(Reg), SplitLIs);
  97     if (Reg == TRI.getFrameRegister(MF) && SplitLIs.size() > 0) {
  98       // The live interval for the frame register was split, resulting in a new
  99       // VReg. For now we only support debug info output for a single frame base
 100       // value for the function, so just use the last one. It will certainly be
 101       // wrong for some part of the function, but until we are able to track
 102       // values through live-range splitting and stackification, it will have to
 103       // do.
 104       MF.getInfo<WebAssemblyFunctionInfo>()->setFrameBaseVreg(
 105           SplitLIs.back()->reg());
 106     }
 107     SplitLIs.clear();
 108   }
 109
 110   // In FixIrreducibleControlFlow, we conservatively inserted IMPLICIT_DEF
 111   // instructions to satisfy LiveIntervals' requirement that all uses be
 112   // dominated by defs. Now that LiveIntervals has computed which of these
 113   // defs are actually needed and which are dead, remove the dead ones.
 114   for (MachineInstr &MI : llvm::make_early_inc_range(MF.front())) {
 115     if (MI.isImplicitDef() && MI.getOperand(0).isDead()) {
 116       LiveInterval &LI = LIS.getInterval(MI.getOperand(0).getReg());
 117       LIS.removeVRegDefAt(LI, LIS.getInstructionIndex(MI).getRegSlot());
 118       LIS.RemoveMachineInstrFromMaps(MI);
 119       MI.eraseFromParent();
 120     }
 121   }
 122
 123   return true;
 124 }