RegAllocBasic.cpp Source File (original) (raw)

36#include

38using namespace llvm;

40#define DEBUG_TYPE "regalloc"

45namespace {

46 struct CompSpillWeight {

48 return A->weight() < B->weight();

49 }

50 };

51}

53namespace {

66 std::unique_ptr SpillerInstance;

67 std::priority_queue<const LiveInterval *, std::vector<const LiveInterval *>,

68 CompSpillWeight>

78public:

89 Spiller &spiller() override { return *SpillerInstance; }

94 if (Queue.empty())

95 return nullptr;

98 return LI;

99 }

100

103

104

106

109 MachineFunctionProperties::Property::NoPHIs);

110 }

111

114 MachineFunctionProperties::Property::IsSSA);

115 }

116

117

118

119

122

123 static char ID;

124};

125

126char RABasic::ID = 0;

127

128}

129

131

133 false, false)

148

149bool RABasic::LRE_CanEraseVirtReg(Register VirtReg) {

150 LiveInterval &LI = LIS->getInterval(VirtReg);

151 if (VRM->hasPhys(VirtReg)) {

152 Matrix->unassign(LI);

153 aboutToRemoveInterval(LI);

154 return true;

155 }

156

157

158

159

161 return false;

162}

163

164void RABasic::LRE_WillShrinkVirtReg(Register VirtReg) {

165 if (!VRM->hasPhys(VirtReg))

166 return;

167

168

169 LiveInterval &LI = LIS->getInterval(VirtReg);

170 Matrix->unassign(LI);

171 enqueue(&LI);

172}

173

176

177void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {

201}

202

203void RABasic::releaseMemory() {

204 SpillerInstance.reset();

205}

206

207

208

209

210

211bool RABasic::spillInterferences(const LiveInterval &VirtReg,

214

215

217

218

219 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {

222 if (!Intf->isSpillable() || Intf->weight() > VirtReg.weight())

223 return false;

225 }

226 }

228 << " interferences with " << VirtReg << "\n");

229 assert(!Intfs.empty() && "expected interference");

230

231

233

234 if (!VRM->hasPhys(Spill->reg()))

235 continue;

236

237

238

239 Matrix->unassign(*Spill);

240

241

242 LiveRangeEdit LRE(Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);

243 spiller().spill(LRE);

244 }

245 return true;

246}

247

248

249

250

251

252

253

254

255

256

257

258

259

262

264

265

266 auto Order =

270

271 switch (Matrix->checkInterference(VirtReg, PhysReg)) {

273

274 return PhysReg;

275

277

278 PhysRegSpillCands.push_back(PhysReg);

279 continue;

280

281 default:

282

283 continue;

284 }

285 }

286

287

288 for (MCRegister &PhysReg : PhysRegSpillCands) {

289 if (!spillInterferences(VirtReg, PhysReg, SplitVRegs))

290 continue;

291

292 assert( Matrix ->checkInterference(VirtReg, PhysReg) &&

293 "Interference after spill.");

294

295 return PhysReg;

296 }

297

298

299 LLVM_DEBUG(dbgs() << "spilling: " << VirtReg << '\n');

301 return ~0u;

302 LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);

303 spiller().spill(LRE);

304

305

306

307 return 0;

308}

309

311 LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"

312 << "********** Function: " << mf.getName() << '\n');

313

314 MF = &mf;

315 auto &MBFI = getAnalysis().getMBFI();

316 auto &LiveStks = getAnalysis().getLS();

317 auto &MDT = getAnalysis().getDomTree();

318

320 getAnalysis().getLIS(),

321 getAnalysis().getLRM());

323 getAnalysis().getLI(), MBFI,

324 &getAnalysis().getPSI());

325 VRAI.calculateSpillWeightsAndHints();

326

327 SpillerInstance.reset(

329

330 allocatePhysRegs();

331 postOptimization();

332

333

334 LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");

335

336 releaseMemory();

337 return true;

338}

339

341 return new RABasic();

342}

343

345 return new RABasic(F);

346}

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

unsigned const TargetRegisterInfo * TRI

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", createBasicRegisterAllocator)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.

static AllocationOrder create(unsigned VirtReg, const VirtRegMap &VRM, const RegisterClassInfo &RegClassInfo, const LiveRegMatrix *Matrix)

Create a new AllocationOrder for VirtReg.

Represent the analysis usage information of a pass.

AnalysisUsage & addRequiredID(const void *ID)

AnalysisUsage & addPreservedID(const void *ID)

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

void setPreservesCFG()

This function should be called by the pass, iff they do not:

FunctionPass class - This class is used to implement most global optimizations.

Query interferences between a single live virtual register and a live interval union.

const SmallVectorImpl< const LiveInterval * > & interferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())

LiveInterval - This class represents the liveness of a register, or stack slot.

bool isSpillable() const

isSpillable - Can this interval be spilled?

Callback methods for LiveRangeEdit owners.

virtual bool LRE_CanEraseVirtReg(Register)

Called when a virtual register is no longer used.

virtual void LRE_WillShrinkVirtReg(Register)

Called before shrinking the live range of a virtual register.

@ IK_VirtReg

Virtual register interference.

@ IK_Free

No interference, go ahead and assign.

Wrapper class representing physical registers. Should be passed by value.

constexpr bool isValid() const

Analysis pass which computes a MachineDominatorTree.

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

virtual MachineFunctionProperties getClearedProperties() const

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

virtual bool runOnMachineFunction(MachineFunction &MF)=0

runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...

virtual MachineFunctionProperties getRequiredProperties() const

Properties which a MachineFunction may have at a given point in time.

MachineFunctionProperties & set(Property P)

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

virtual StringRef getPassName() const

getPassName - Return a nice clean name for a pass.

virtual void releaseMemory()

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...

An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.

RegAllocBase provides the register allocation driver and interface that can be extended to add intere...

virtual MCRegister selectOrSplit(const LiveInterval &VirtReg, SmallVectorImpl< Register > &splitLVRs)=0

void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat)

virtual Spiller & spiller()=0

virtual const LiveInterval * dequeue()=0

dequeue - Return the next unassigned register, or NULL.

virtual void enqueueImpl(const LiveInterval *LI)=0

enqueue - Add VirtReg to the priority queue of unassigned registers.

Wrapper class representing virtual and physical registers.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

This is an optimization pass for GlobalISel generic memory operations.

std::function< bool(const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, const Register Reg)> RegAllocFilterFunc

Filter function for register classes during regalloc.

char & MachineDominatorsID

MachineDominators - This pass is a machine dominators analysis pass.

auto reverse(ContainerTy &&C)

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

Spiller * createInlineSpiller(const Spiller::RequiredAnalyses &Analyses, MachineFunction &MF, VirtRegMap &VRM, VirtRegAuxInfo &VRAI)

Create and return a spiller that will insert spill code directly instead of deferring though VirtRegM...

FunctionPass * createBasicRegisterAllocator()

BasicRegisterAllocation Pass - This pass implements a degenerate global register allocator using the ...

Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)

Prints virtual and physical registers with or without a TRI instance.

char & RABasicID

Basic register allocator.