LiveRangeCalc.cpp Source File (original) (raw)

28#include

29#include

30#include

32using namespace llvm;

34#define DEBUG_TYPE "regalloc"

40 unsigned NumBlocks = MF->getNumBlockIDs();

41 Seen.clear();

42 Seen.resize(NumBlocks);

43 EntryInfos.clear();

44 Map.resize(NumBlocks);

45}

51 MF = mf;

53 Indexes = SI;

54 DomTree = MDT;

55 Alloc = VNIA;

57 LiveIn.clear();

58}

60void LiveRangeCalc::updateFromLiveIns() {

62 for (const LiveInBlock &I : LiveIn) {

63 if (.DomNode)

64 continue;

66 assert(I.Value && "No live-in value found");

70 if (I.Kill.isValid())

72 End = I.Kill;

73 else {

77 Map[MBB] = LiveOutPair(I.Value, nullptr);

78 }

80 Updater.add(Start, End, I.Value);

81 }

82 LiveIn.clear();

83}

87 assert(Use.isValid() && "Invalid SlotIndex");

88 assert(Indexes && "Missing SlotIndexes");

89 assert(DomTree && "Missing dominator tree");

92 assert(UseMBB && "No MBB at Use");

95 auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);

96 if (EP.first != nullptr || EP.second)

97 return;

100

101

102

103 if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))

104 return;

105

106

108}

109

110

111

112

114 assert(Indexes && "Missing SlotIndexes");

115 assert(DomTree && "Missing dominator tree");

116 updateSSA();

117 updateFromLiveIns();

118}

119

123 unsigned BN = MBB.getNumber();

124 if (DefOnEntry[BN])

125 return true;

126 if (UndefOnEntry[BN])

127 return false;

128

131 DefOnEntry[S->getNumber()] = true;

132 DefOnEntry[BN] = true;

133 return true;

134 };

135

137

138

140 WorkList.insert(P->getNumber());

141

142 for (unsigned i = 0; i != WorkList.size(); ++i) {

143

144 unsigned N = WorkList[i];

146 if (Seen[N]) {

147 const LiveOutPair &LOB = Map[&B];

148 if (LOB.first != nullptr && LOB.first != &UndefVNI)

149 return MarkDefined(B);

150 }

151 SlotIndex Begin, End;

152 std::tie(Begin, End) = Indexes->getMBBRange(&B);

153

154

155

156

158 if (UB != LR.begin()) {

159 LiveRange::Segment &Seg = *std::prev(UB);

160 if (Seg.end > Begin) {

161

162

163

164

166 continue;

167 return MarkDefined(B);

168 }

169 }

170

171

172

173 if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {

174 UndefOnEntry[N] = true;

175 continue;

176 }

177 if (DefOnEntry[N])

178 return MarkDefined(B);

179

180

181 for (MachineBasicBlock *P : B.predecessors())

182 WorkList.insert(P->getNumber());

183 }

184

185 UndefOnEntry[BN] = true;

186 return false;

187}

188

192 unsigned UseMBBNum = UseMBB.getNumber();

193

194

195 SmallVector<unsigned, 16> WorkList(1, UseMBBNum);

196

197

198 bool UniqueVNI = true;

199 VNInfo *TheVNI = nullptr;

200

201 bool FoundUndef = false;

202

203

204 for (unsigned i = 0; i != WorkList.size(); ++i) {

205 MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);

206

207#ifndef NDEBUG

210 errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo())

211 << " does not have a corresponding definition on every path:\n";

212 const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);

213 if (MI != nullptr)

216 }

217

219 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();

221 for (MCRegAliasIterator Alias(PhysReg, TRI, false); !IsLiveIn && Alias.isValid(); ++Alias)

223 if (!IsLiveIn) {

227 << ", but is missing from the live-in list.\n";

229 }

230 }

231#endif

233

235

236 if (Seen.test(Pred->getNumber())) {

237 if (VNInfo *VNI = Map[Pred].first) {

238 if (TheVNI && TheVNI != VNI)

239 UniqueVNI = false;

240 TheVNI = VNI;

241 }

242 continue;

243 }

244

245 SlotIndex Start, End;

246 std::tie(Start, End) = Indexes->getMBBRange(Pred);

247

248

249

251 VNInfo *VNI = EP.first;

252 FoundUndef |= EP.second;

254 if (VNI) {

255 if (TheVNI && TheVNI != VNI)

256 UniqueVNI = false;

257 TheVNI = VNI;

258 }

259 if (VNI || EP.second)

260 continue;

261

262

263 if (Pred != &UseMBB)

264 WorkList.push_back(Pred->getNumber());

265 else

266

267 Use = SlotIndex();

268 }

269 }

270

271 LiveIn.clear();

272 FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);

273 if (!Undefs.empty() && FoundUndef)

274 UniqueVNI = false;

275

276

277

278 if (WorkList.size() > 4)

280

281

282 if (UniqueVNI) {

284 LiveRangeUpdater Updater(&LR);

285 for (unsigned BN : WorkList) {

286 SlotIndex Start, End;

287 std::tie(Start, End) = Indexes->getMBBRange(BN);

288

289 if (BN == UseMBBNum && Use.isValid())

290 End = Use;

291 else

292 Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);

293 Updater.add(Start, End, TheVNI);

294 }

295 return true;

296 }

297

298

299 EntryInfoMap::iterator Entry;

300 bool DidInsert;

301 std::tie(Entry, DidInsert) = EntryInfos.insert(

302 std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));

303 if (DidInsert) {

304

305 unsigned N = MF->getNumBlockIDs();

306 Entry->second.first.resize(N);

307 Entry->second.second.resize(N);

308 }

309 BitVector &DefOnEntry = Entry->second.first;

310 BitVector &UndefOnEntry = Entry->second.second;

311

312

313

314 LiveIn.reserve(WorkList.size());

315 for (unsigned BN : WorkList) {

316 MachineBasicBlock *MBB = MF->getBlockNumbered(BN);

317 if (!Undefs.empty() &&

318 !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))

319 continue;

321 if (MBB == &UseMBB)

322 LiveIn.back().Kill = Use;

323 }

324

325 return false;

326}

327

328

329

330void LiveRangeCalc::updateSSA() {

331 assert(Indexes && "Missing SlotIndexes");

332 assert(DomTree && "Missing dominator tree");

333

334

336 do {

338

339

340 for (LiveInBlock &I : LiveIn) {

342

343 if (!Node)

344 continue;

345 MachineBasicBlock *MBB = Node->getBlock();

347 LiveOutPair IDomValue;

348

349

350

351 bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());

352

353

354

355

356 if (!needPHI) {

357 IDomValue = Map[IDom->getBlock()];

358

359

360 if (IDomValue.first && IDomValue.first != &UndefVNI &&

361 !IDomValue.second) {

362 Map[IDom->getBlock()].second = IDomValue.second =

363 DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));

364 }

365

367 LiveOutPair &Value = Map[Pred];

368 if ( Value .first || Value.first == IDomValue.first)

369 continue;

371 needPHI = true;

372 break;

373 }

374

375

376 if ( Value .second)

378 DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));

379

380

381

382

383 if (DomTree->dominates(IDom, Value.second)) {

384 needPHI = true;

385 break;

386 }

387 }

388 }

389

390

391

392

393 LiveOutPair &LOP = Map[MBB];

394

395

396 if (needPHI) {

398 assert(Alloc && "Need VNInfo allocator to create PHI-defs");

399 SlotIndex Start, End;

400 std::tie(Start, End) = Indexes->getMBBRange(MBB);

402 VNInfo *VNI = LR.getNextValue(Start, *Alloc);

403 I.Value = VNI;

404

405 I.DomNode = nullptr;

406

407

408 if (I.Kill.isValid()) {

409 if (VNI)

410 LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));

411 } else {

412 if (VNI)

413 LR.addSegment(LiveInterval::Segment(Start, End, VNI));

414 LOP = LiveOutPair(VNI, Node);

415 }

416 } else if (IDomValue.first && IDomValue.first != &UndefVNI) {

417

418 I.Value = IDomValue.first;

419

420

421 if (I.Kill.isValid())

422 continue;

423

424

425

426 if (LOP.first == IDomValue.first)

427 continue;

429 LOP = IDomValue;

430 }

431 }

433}

434

439 BitVector DefBlocks(MF.getNumBlockIDs());

441 DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber());

442

443 unsigned EntryNum = MF.front().getNumber();

445 PredQueue.insert(MBB->getNumber());

446 for (unsigned i = 0; i != PredQueue.size(); ++i) {

447 unsigned BN = PredQueue[i];

448 if (DefBlocks[BN])

449 continue;

450 if (BN == EntryNum) {

451

452

453 return false;

454 }

457 PredQueue.insert(P->getNumber());

458 }

459 return true;

460}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file implements the BitVector class.

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

static VNInfo UndefVNI(0xbad, SlotIndex())

SI Optimize VGPR LiveRange

This file implements a set that has insertion order iteration characteristics.

This file defines the SmallVector class.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

bool empty() const

empty - Check if the array is empty.

bool test(unsigned Idx) const

static LLVM_ABI bool isJointlyDominated(const MachineBasicBlock *MBB, ArrayRef< SlotIndex > Defs, const SlotIndexes &Indexes)

A diagnostic function to check if the end of the block MBB is jointly dominated by the blocks corresp...

Definition LiveRangeCalc.cpp:435

void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill=SlotIndex())

addLiveInBlock - Add a block with an unknown live-in value.

LLVM_ABI void resetLiveOutMap()

Reset Map and Seen fields.

Definition LiveRangeCalc.cpp:39

LLVM_ABI void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)

reset - Prepare caches for a new set of non-overlapping live ranges.

Definition LiveRangeCalc.cpp:47

LLVM_ABI void extend(LiveRange &LR, SlotIndex Use, Register PhysReg, ArrayRef< SlotIndex > Undefs)

Extend the live range of LR to reach Use.

Definition LiveRangeCalc.cpp:85

LLVM_ABI void calculateValues()

calculateValues - Calculate the value that will be live-in to each block added with addLiveInBlock.

Definition LiveRangeCalc.cpp:113

void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)

setLiveOutValue - Indicate that VNI is live out from MBB.

Helper class for performant LiveRange bulk updates.

void setDest(LiveRange *lr)

Select a different destination live range.

LLVM_ABI void add(LiveRange::Segment)

Add a segment to LR and coalesce when possible, just like LR.addSegment().

This class represents the liveness of a register, stack slot, etc.

LLVM_ABI iterator addSegment(Segment S)

Add the specified Segment to this range, merging segments as appropriate.

Segments::iterator iterator

LLVM_ABI std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)

Attempt to extend a value defined after StartIdx to include Use.

bool isUndefIn(ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const

Returns true if there is an explicit "undef" between Begin End.

VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)

getNextValue - Create a new value number and return it.

int getNumber() const

MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

iterator_range< pred_iterator > predecessors()

LLVM_ABI bool isLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const

Return true if the specified register is in the live in set.

DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

MachineBasicBlock * getBlockNumbered(unsigned N) const

getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...

bool verify(Pass *p=nullptr, const char *Banner=nullptr, raw_ostream *OS=nullptr, bool AbortOnError=true) const

Run the current MachineFunction through the machine code verifier, useful for debugger use.

Wrapper class representing virtual and physical registers.

constexpr bool isPhysical() const

Return true if the specified register number is in the physical register namespace.

A vector that has set insertion semantics.

size_type size() const

Determine the number of elements in the SetVector.

iterator end()

Get an iterator to the end of the SetVector.

iterator begin()

Get an iterator to the beginning of the SetVector.

bool insert(const value_type &X)

Insert a new element into the SetVector.

SlotIndex - An opaque wrapper around machine indexes.

SlotIndex getPrevSlot() const

Returns the previous slot in the index list.

const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const

Return the (start,end) range of the given basic block number.

A Use represents the edge between a Value definition and its users.

VNInfo - Value Number Information.

BumpPtrAllocator Allocator

NodeAddr< UseNode * > Use

NodeAddr< NodeBase * > Node

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

auto upper_bound(R &&Range, T &&Value)

Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...

LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)

DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode

LLVM_ABI raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

void array_pod_sort(IteratorTy Start, IteratorTy End)

array_pod_sort - This sorts an array with the specified start and end extent.

LLVM_ABI 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.

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.