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 "WebAssemblySubtarget.h"
  24 #include "llvm/CodeGen/LiveIntervals.h"
  25 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
  26 #include "llvm/CodeGen/MachineRegisterInfo.h"
  27 #include "llvm/CodeGen/Passes.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 using namespace llvm;
  31
  32 #define DEBUG_TYPE "wasm-optimize-live-intervals"
  33
  34 namespace {
  35 class WebAssemblyOptimizeLiveIntervals final : public MachineFunctionPass {
  36   StringRef getPassName() const override {
  37     return "WebAssembly Optimize Live Intervals";
  38   }
  39
  40   void getAnalysisUsage(AnalysisUsage &AU) const override {
  41     AU.setPreservesCFG();
  42     AU.addRequired<LiveIntervals>();
  43     AU.addPreserved<MachineBlockFrequencyInfo>();
  44     AU.addPreserved<SlotIndexes>();
  45     AU.addPreserved<LiveIntervals>();
  46     AU.addPreservedID(LiveVariablesID);
  47     AU.addPreservedID(MachineDominatorsID);
  48     MachineFunctionPass::getAnalysisUsage(AU);
  49   }
  50
  51   bool runOnMachineFunction(MachineFunction &MF) override;
  52
  53 public:
  54   static char ID; // Pass identification, replacement for typeid
  55   WebAssemblyOptimizeLiveIntervals() : MachineFunctionPass(ID) {}
  56 };
  57 } // end anonymous namespace
  58
  59 char WebAssemblyOptimizeLiveIntervals::ID = 0;
  60 INITIALIZE_PASS(WebAssemblyOptimizeLiveIntervals, DEBUG_TYPE,
  61                 "Optimize LiveIntervals for WebAssembly", false, false)
  62
  63 FunctionPass *llvm::createWebAssemblyOptimizeLiveIntervals() {
  64   return new WebAssemblyOptimizeLiveIntervals();
  65 }
  66
  67 bool WebAssemblyOptimizeLiveIntervals::runOnMachineFunction(
  68     MachineFunction &MF) {
  69   LLVM_DEBUG(dbgs() << "********** Optimize LiveIntervals **********\n"
  70                        "********** Function: "
  71                     << MF.getName() << '\n');
  72
  73   MachineRegisterInfo &MRI = MF.getRegInfo();
  74   auto &LIS = getAnalysis<LiveIntervals>();
  75
  76   // We don't preserve SSA form.
  77   MRI.leaveSSA();
  78
  79   assert(MRI.tracksLiveness() && "OptimizeLiveIntervals expects liveness");
  80
  81   // Split multiple-VN LiveIntervals into multiple LiveIntervals.
  82   SmallVector<LiveInterval *, 4> SplitLIs;
  83   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
  84     unsigned Reg = Register::index2VirtReg(I);
  85     if (MRI.reg_nodbg_empty(Reg))
  86       continue;
  87
  88     LIS.splitSeparateComponents(LIS.getInterval(Reg), SplitLIs);
  89     SplitLIs.clear();
  90   }
  91
  92   // In PrepareForLiveIntervals, we conservatively inserted IMPLICIT_DEF
  93   // instructions to satisfy LiveIntervals' requirement that all uses be
  94   // dominated by defs. Now that LiveIntervals has computed which of these
  95   // defs are actually needed and which are dead, remove the dead ones.
  96   for (auto MII = MF.begin()->begin(), MIE = MF.begin()->end(); MII != MIE;) {
  97     MachineInstr *MI = &*MII++;
  98     if (MI->isImplicitDef() && MI->getOperand(0).isDead()) {
  99       LiveInterval &LI = LIS.getInterval(MI->getOperand(0).getReg());
 100       LIS.removeVRegDefAt(LI, LIS.getInstructionIndex(*MI).getRegSlot());
 101       LIS.RemoveMachineInstrFromMaps(*MI);
 102       MI->eraseFromParent();
 103     }
 104   }
 105
 106   return false;
 107 }