ExecutionDomainFix.cpp Source File (original) (raw)

14using namespace llvm;

16#define DEBUG_TYPE "execution-deps-fix"

19ExecutionDomainFix::regIndices(MCRegister Reg) const {

20 assert(Reg < AliasMap.size() && "Invalid register");

21 const auto &Entry = AliasMap[Reg.id()];

22 return make_range(Entry.begin(), Entry.end());

23}

25DomainValue *ExecutionDomainFix::alloc(int domain) {

26 DomainValue *dv = Avail.empty() ? new (Allocator.Allocate()) DomainValue

27 : Avail.pop_back_val();

28 if (domain >= 0)

30 assert(dv->Refs == 0 && "Reference count wasn't cleared");

31 assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");

32 return dv;

33}

35void ExecutionDomainFix::release(DomainValue *DV) {

36 while (DV) {

37 assert(DV->Refs && "Bad DomainValue");

38 if (--DV->Refs)

39 return;

47 Avail.push_back(DV);

50 }

51}

54 DomainValue *DV = DVRef;

55 if (!DV || !DV->Next)

56 return DV;

59 do

60 DV = DV->Next;

61 while (DV->Next);

64 retain(DV);

66 DVRef = DV;

67 return DV;

68}

70void ExecutionDomainFix::setLiveReg(int rx, DomainValue *dv) {

71 assert(unsigned(rx) < NumRegs && "Invalid index");

72 assert(!LiveRegs.empty() && "Must enter basic block first.");

74 if (LiveRegs[rx] == dv)

75 return;

76 if (LiveRegs[rx])

78 LiveRegs[rx] = retain(dv);

79}

81void ExecutionDomainFix::kill(int rx) {

82 assert(unsigned(rx) < NumRegs && "Invalid index");

83 assert(!LiveRegs.empty() && "Must enter basic block first.");

84 if (!LiveRegs[rx])

85 return;

88 LiveRegs[rx] = nullptr;

89}

91void ExecutionDomainFix::force(int rx, unsigned domain) {

92 assert(unsigned(rx) < NumRegs && "Invalid index");

93 assert(!LiveRegs.empty() && "Must enter basic block first.");

94 if (DomainValue *dv = LiveRegs[rx]) {

98 collapse(dv, domain);

99 else {

100

101

103 assert(LiveRegs[rx] && "Not live after collapse?");

104 LiveRegs[rx]->addDomain(domain);

105 }

106 } else {

107

108 setLiveReg(rx, alloc(domain));

109 }

110}

111

112void ExecutionDomainFix::collapse(DomainValue *dv, unsigned domain) {

114

115

119

120

121 if (!LiveRegs.empty() && dv->Refs > 1)

122 for (unsigned rx = 0; rx != NumRegs; ++rx)

123 if (LiveRegs[rx] == dv)

124 setLiveReg(rx, alloc(domain));

125}

126

128 assert(->isCollapsed() && "Cannot merge into collapsed");

129 assert(->isCollapsed() && "Cannot merge from collapsed");

130 if (A == B)

131 return true;

132

133 unsigned common = A->getCommonDomains(B->AvailableDomains);

134 if (!common)

135 return false;

136 A->AvailableDomains = common;

137 A->Instrs.append(B->Instrs.begin(), B->Instrs.end());

138

139

140 B->clear();

141

142 B->Next = retain(A);

143

144 for (unsigned rx = 0; rx != NumRegs; ++rx) {

145 assert(!LiveRegs.empty() && "no space allocated for live registers");

146 if (LiveRegs[rx] == B)

147 setLiveReg(rx, A);

148 }

149 return true;

150}

151

152void ExecutionDomainFix::enterBasicBlock(

154

155 MachineBasicBlock *MBB = TraversedMBB.MBB;

156

157

158

159 if (LiveRegs.empty())

160 LiveRegs.assign(NumRegs, nullptr);

161

162

165 return;

166 }

167

168

170 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&

171 "Should have pre-allocated MBBInfos for all MBBs");

172 LiveRegsDVInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];

173

174

175 if (Incoming.empty())

176 continue;

177

178 for (unsigned rx = 0; rx != NumRegs; ++rx) {

179 DomainValue *pdv = resolve(Incoming[rx]);

180 if (!pdv)

181 continue;

182 if (!LiveRegs[rx]) {

183 setLiveReg(rx, pdv);

184 continue;

185 }

186

187

188 if (LiveRegs[rx]->isCollapsed()) {

189

190 unsigned Domain = LiveRegs[rx]->getFirstDomain();

192 collapse(pdv, Domain);

193 continue;

194 }

195

196

198 merge(LiveRegs[rx], pdv);

199 else

201 }

202 }

204 << (!TraversedMBB.IsDone ? ": incomplete\n"

205 : ": all preds known\n"));

206}

207

208void ExecutionDomainFix::leaveBasicBlock(

210 assert(!LiveRegs.empty() && "Must enter basic block first.");

211 unsigned MBBNumber = TraversedMBB.MBB->getNumber();

212 assert(MBBNumber < MBBOutRegsInfos.size() &&

213 "Unexpected basic block number.");

214

215 for (DomainValue *OldLiveReg : MBBOutRegsInfos[MBBNumber]) {

217 }

218 MBBOutRegsInfos[MBBNumber] = LiveRegs;

219 LiveRegs.clear();

220}

221

222bool ExecutionDomainFix::visitInstr(MachineInstr *MI) {

223

224 std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);

225 if (DomP.first) {

226 if (DomP.second)

227 visitSoftInstr(MI, DomP.second);

228 else

229 visitHardInstr(MI, DomP.first);

230 }

231

232 return !DomP.first;

233}

234

235void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) {

236 assert(->isDebugInstr() && "Won't process debug values");

237 const MCInstrDesc &MCID = MI->getDesc();

238 for (unsigned i = 0,

239 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();

240 i != e; ++i) {

241 MachineOperand &MO = MI->getOperand(i);

243 continue;

245 continue;

246 for (int rx : regIndices(MO.getReg())) {

247

249

250

251 if (Kill)

252 kill(rx);

253 }

254 }

255}

256

257void ExecutionDomainFix::visitHardInstr(MachineInstr *mi, unsigned domain) {

258

261 i != e; ++i) {

262 MachineOperand &mo = mi->getOperand(i);

264 continue;

265 for (int rx : regIndices(mo.getReg())) {

266 force(rx, domain);

267 }

268 }

269

270

271 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {

272 MachineOperand &mo = mi->getOperand(i);

274 continue;

275 for (int rx : regIndices(mo.getReg())) {

276 kill(rx);

277 force(rx, domain);

278 }

279 }

280}

281

282void ExecutionDomainFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {

283

284

286

287

288 SmallVector<int, 4> used;

289 if (!LiveRegs.empty())

292 i != e; ++i) {

293 MachineOperand &mo = mi->getOperand(i);

295 continue;

296 for (int rx : regIndices(mo.getReg())) {

297 DomainValue *dv = LiveRegs[rx];

298 if (dv == nullptr)

299 continue;

300

302

304

305

306

307 if (common)

309 } else if (common)

310

312 else

313

314

315 kill(rx);

316 }

317 }

318

319

322 TII->setExecutionDomain(*mi, domain);

323 visitHardInstr(mi, domain);

324 return;

325 }

326

327

328

329 SmallVector<int, 4> Regs;

330 for (int rx : used) {

331 assert(!LiveRegs.empty() && "no space allocated for live registers");

332 DomainValue *&LR = LiveRegs[rx];

333

335 kill(rx);

336 continue;

337 }

338

339

340 const int Def = RDI->getReachingDef(mi, RC->getRegister(rx));

342 return RDI->getReachingDef(mi, RC->getRegister(I)) <= Def;

343 });

345 }

346

347

348

349 DomainValue *dv = nullptr;

350 while (!Regs.empty()) {

351 if (!dv) {

353

356 continue;

357 }

358

359 DomainValue *Latest = LiveRegs[Regs.pop_back_val()];

360

361 if (Latest == dv || Latest->Next)

362 continue;

363 if (merge(dv, Latest))

364 continue;

365

366

367 for (int i : used) {

368 assert(!LiveRegs.empty() && "no space allocated for live registers");

369 if (LiveRegs[i] == Latest)

370 kill(i);

371 }

372 }

373

374

375 if (!dv) {

376 dv = alloc();

378 }

380

381

382

383 for (const MachineOperand &mo : mi->operands()) {

385 continue;

386 for (int rx : regIndices(mo.getReg())) {

387 if (!LiveRegs[rx] || (mo.isDef() && LiveRegs[rx] != dv)) {

388 kill(rx);

389 setLiveReg(rx, dv);

390 }

391 }

392 }

393}

394

395void ExecutionDomainFix::processBasicBlock(

397 enterBasicBlock(TraversedMBB);

398

399

400

401

402 for (MachineInstr &MI : *TraversedMBB.MBB) {

403 if (.isDebugInstr()) {

404 bool Kill = false;

406 Kill = visitInstr(&MI);

407 processDefs(&MI, Kill);

408 }

409 }

410 leaveBasicBlock(TraversedMBB);

411}

412

415 return false;

416 MF = &mf;

419 LiveRegs.clear();

420 assert(NumRegs == RC->getNumRegs() && "Bad regclass");

421

422 LLVM_DEBUG(dbgs() << "********** FIX EXECUTION DOMAIN: "

423 << TRI->getRegClassName(RC) << " **********\n");

424

425

426

427 bool anyregs = false;

429 for (unsigned Reg : *RC) {

430 if (MRI.isPhysRegUsed(Reg)) {

431 anyregs = true;

432 break;

433 }

434 }

435 if (!anyregs)

436 return false;

437

439

440

441 if (AliasMap.empty()) {

442

443

444 AliasMap.resize(TRI->getNumRegs());

445 for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)

447 ++AI)

448 AliasMap[(*AI).id()].push_back(i);

449 }

450

451

453

454

458 processBasicBlock(TraversedMBB);

459

460 for (const LiveRegsDVInfo &OutLiveRegs : MBBOutRegsInfos)

461 for (DomainValue *OutLiveReg : OutLiveRegs)

462 if (OutLiveReg)

464

465 MBBOutRegsInfos.clear();

466 Avail.clear();

467 Allocator.DestroyAll();

468

469 return false;

470}

unsigned const MachineRegisterInfo * MRI

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

static constexpr unsigned long long mask(BlockVerifier::State S)

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

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

return !LiveInRegUnits available(Reg)

bool runOnMachineFunction(MachineFunction &MF) override

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

Definition ExecutionDomainFix.cpp:413

bool skipFunction(const Function &F) const

Optional passes call this function to check whether the pass should be skipped.

This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...

TraversalOrder traverse(MachineFunction &MF)

SmallVector< TraversedMBBInfo, 4 > TraversalOrder

Identifies basic blocks that are part of loops and should to be visited twice and returns efficient t...

unsigned getNumOperands() const

Return the number of declared MachineOperands for this MachineInstruction.

unsigned getNumDefs() const

Return the number of MachineOperands that are register definitions.

MCRegAliasIterator enumerates all registers aliasing Reg.

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

int getNumber() const

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

iterator_range< pred_iterator > predecessors()

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Function & getFunction()

Return the LLVM function that this machine code represents.

unsigned getNumBlockIDs() const

getNumBlockIDs - Return the number of MBB ID's allocated.

Representation of each machine instruction.

const MCInstrDesc & getDesc() const

Returns the target instruction descriptor of this MachineInstr.

const MachineOperand & getOperand(unsigned i) const

bool isReg() const

isReg - Tests if this is a MO_Register operand.

getReg - Returns the register number.

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

AnalysisType & getAnalysis() const

getAnalysis() - This function is used by subclasses to get to the analysis information ...

iterator insert(iterator I, T &&Elt)

void push_back(const T &Elt)

const TargetRegisterInfo & getRegisterInfo() const

virtual const TargetInstrInfo * getInstrInfo() const

A range adaptor for a pair of iterators.

@ Kill

The last use of a register.

NodeAddr< DefNode * > Def

This is an optimization pass for GlobalISel generic memory operations.

auto partition_point(R &&Range, Predicate P)

Binary search for the first iterator in a range where a predicate is false.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

int countr_zero(T Val)

Count number of 0's from the least significant bit to the most stopping at the first 1.

constexpr bool isPowerOf2_32(uint32_t Value)

Return true if the argument is a power of two > 0.

LLVM_ABI raw_ostream & dbgs()

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

FunctionAddr VTableAddr Next

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.

A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track of execution domains.

unsigned getCommonDomains(unsigned mask) const

Return bitmask of domains that are available and in mask.

void clear()

Clear this DomainValue and point to next which has all its data.

SmallVector< MachineInstr *, 8 > Instrs

Twiddleable instructions using or defining these registers.

void setSingleDomain(unsigned domain)

bool isCollapsed() const

A collapsed DomainValue has no instructions to twiddle - it simply keeps track of the domains where t...

DomainValue * Next

Pointer to the next DomainValue in a chain.

void addDomain(unsigned domain)

Mark domain as available.

unsigned AvailableDomains

Bitmask of available domains.

unsigned Refs

Basic reference counting.

unsigned getFirstDomain() const

First domain available.

bool hasDomain(unsigned domain) const

Is domain available?

MachineBasicBlock * MBB

The basic block.

bool IsDone

True if the block that is ready for its final round of processing.

bool PrimaryPass

True if this is the first time we process the basic block.