RegAllocBase.cpp revision 360784 
1//===- RegAllocBase.cpp - Register Allocator Base Class -------------------===//
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// This file defines the RegAllocBase class which provides common functionality
10// for LiveIntervalUnion-based register allocators.
11//
12//===----------------------------------------------------------------------===//
13
14#include "RegAllocBase.h"
15#include "Spiller.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/CodeGen/LiveInterval.h"
19#include "llvm/CodeGen/LiveIntervals.h"
20#include "llvm/CodeGen/LiveRegMatrix.h"
21#include "llvm/CodeGen/MachineInstr.h"
22#include "llvm/CodeGen/MachineModuleInfo.h"
23#include "llvm/CodeGen/MachineRegisterInfo.h"
24#include "llvm/CodeGen/TargetRegisterInfo.h"
25#include "llvm/CodeGen/VirtRegMap.h"
26#include "llvm/Pass.h"
27#include "llvm/Support/CommandLine.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/ErrorHandling.h"
30#include "llvm/Support/Timer.h"
31#include "llvm/Support/raw_ostream.h"
32#include <cassert>
33
34using namespace llvm;
35
36#define DEBUG_TYPE "regalloc"
37
38STATISTIC(NumNewQueued    , "Number of new live ranges queued");
39
40// Temporary verification option until we can put verification inside
41// MachineVerifier.
42static cl::opt<bool, true>
43    VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled),
44                   cl::Hidden, cl::desc("Verify during register allocation"));
45
46const char RegAllocBase::TimerGroupName[] = "regalloc";
47const char RegAllocBase::TimerGroupDescription[] = "Register Allocation";
48bool RegAllocBase::VerifyEnabled = false;
49
50//===----------------------------------------------------------------------===//
51//                         RegAllocBase Implementation
52//===----------------------------------------------------------------------===//
53
54// Pin the vtable to this file.
55void RegAllocBase::anchor() {}
56
57void RegAllocBase::init(VirtRegMap &vrm,
58                        LiveIntervals &lis,
59                        LiveRegMatrix &mat) {
60  TRI = &vrm.getTargetRegInfo();
61  MRI = &vrm.getRegInfo();
62  VRM = &vrm;
63  LIS = &lis;
64  Matrix = &mat;
65  MRI->freezeReservedRegs(vrm.getMachineFunction());
66  RegClassInfo.runOnMachineFunction(vrm.getMachineFunction());
67}
68
69// Visit all the live registers. If they are already assigned to a physical
70// register, unify them with the corresponding LiveIntervalUnion, otherwise push
71// them on the priority queue for later assignment.
72void RegAllocBase::seedLiveRegs() {
73  NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName,
74                     TimerGroupDescription, TimePassesIsEnabled);
75  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
76    unsigned Reg = Register::index2VirtReg(i);
77    if (MRI->reg_nodbg_empty(Reg))
78      continue;
79    enqueue(&LIS->getInterval(Reg));
80  }
81}
82
83// Top-level driver to manage the queue of unassigned VirtRegs and call the
84// selectOrSplit implementation.
85void RegAllocBase::allocatePhysRegs() {
86  seedLiveRegs();
87
88  // Continue assigning vregs one at a time to available physical registers.
89  while (LiveInterval *VirtReg = dequeue()) {
90    assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned");
91
92    // Unused registers can appear when the spiller coalesces snippets.
93    if (MRI->reg_nodbg_empty(VirtReg->reg)) {
94      LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n');
95      aboutToRemoveInterval(*VirtReg);
96      LIS->removeInterval(VirtReg->reg);
97      continue;
98    }
99
100    // Invalidate all interference queries, live ranges could have changed.
101    Matrix->invalidateVirtRegs();
102
103    // selectOrSplit requests the allocator to return an available physical
104    // register if possible and populate a list of new live intervals that
105    // result from splitting.
106    LLVM_DEBUG(dbgs() << "\nselectOrSplit "
107                      << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg))
108                      << ':' << *VirtReg << " w=" << VirtReg->weight << '\n');
109
110    using VirtRegVec = SmallVector<unsigned, 4>;
111
112    VirtRegVec SplitVRegs;
113    unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
114
115    if (AvailablePhysReg == ~0u) {
116      // selectOrSplit failed to find a register!
117      // Probably caused by an inline asm.
118      MachineInstr *MI = nullptr;
119      for (MachineRegisterInfo::reg_instr_iterator
120           I = MRI->reg_instr_begin(VirtReg->reg), E = MRI->reg_instr_end();
121           I != E; ) {
122        MI = &*(I++);
123        if (MI->isInlineAsm())
124          break;
125      }
126      if (MI && MI->isInlineAsm()) {
127        MI->emitError("inline assembly requires more registers than available");
128      } else if (MI) {
129        LLVMContext &Context =
130            MI->getParent()->getParent()->getMMI().getModule()->getContext();
131        Context.emitError("ran out of registers during register allocation");
132      } else {
133        report_fatal_error("ran out of registers during register allocation");
134      }
135      // Keep going after reporting the error.
136      VRM->assignVirt2Phys(VirtReg->reg,
137                 RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front());
138      continue;
139    }
140
141    if (AvailablePhysReg)
142      Matrix->assign(*VirtReg, AvailablePhysReg);
143
144    for (unsigned Reg : SplitVRegs) {
145      assert(LIS->hasInterval(Reg));
146
147      LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
148      assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned");
149      if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) {
150        assert(SplitVirtReg->empty() && "Non-empty but used interval");
151        LLVM_DEBUG(dbgs() << "not queueing unused  " << *SplitVirtReg << '\n');
152        aboutToRemoveInterval(*SplitVirtReg);
153        LIS->removeInterval(SplitVirtReg->reg);
154        continue;
155      }
156      LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
157      assert(Register::isVirtualRegister(SplitVirtReg->reg) &&
158             "expect split value in virtual register");
159      enqueue(SplitVirtReg);
160      ++NumNewQueued;
161    }
162  }
163}
164
165void RegAllocBase::postOptimization() {
166  spiller().postOptimization();
167  for (auto DeadInst : DeadRemats) {
168    LIS->RemoveMachineInstrFromMaps(*DeadInst);
169    DeadInst->eraseFromParent();
170  }
171  DeadRemats.clear();
172}
173