DetectDeadLanes.cpp Source File (original) (raw)

37using namespace llvm;

39#define DEBUG_TYPE "detect-dead-lanes"

43 : MRI(MRI), TRI(TRI) {

44 unsigned NumVirtRegs = MRI->getNumVirtRegs();

45 VRegInfos = std::unique_ptr<VRegInfo[]>(new VRegInfo[NumVirtRegs]);

46 WorklistMembers.resize(NumVirtRegs);

47 DefinedByCopy.resize(NumVirtRegs);

48}

56 switch (MI.getOpcode()) {

57 case TargetOpcode::COPY:

58 case TargetOpcode::PHI:

59 case TargetOpcode::INSERT_SUBREG:

60 case TargetOpcode::REG_SEQUENCE:

61 case TargetOpcode::EXTRACT_SUBREG:

62 return true;

63 }

64 return false;

65}

74 if (DstRC == SrcRC)

75 return false;

77 unsigned SrcSubIdx = MO.getSubReg();

80 unsigned DstSubIdx = 0;

81 switch (MI.getOpcode()) {

82 case TargetOpcode::INSERT_SUBREG:

84 DstSubIdx = MI.getOperand(3).getImm();

85 break;

86 case TargetOpcode::REG_SEQUENCE: {

88 DstSubIdx = MI.getOperand(OpNum+1).getImm();

89 break;

90 }

91 case TargetOpcode::EXTRACT_SUBREG: {

92 unsigned SubReg = MI.getOperand(2).getImm();

93 SrcSubIdx = TRI.composeSubRegIndices(SubReg, SrcSubIdx);

94 }

95 }

97 unsigned PreA, PreB;

98 if (SrcSubIdx && DstSubIdx)

99 return TRI .getCommonSuperRegClass(SrcRC, SrcSubIdx, DstRC, DstSubIdx, PreA,

100 PreB);

101 if (SrcSubIdx)

102 return TRI .getMatchingSuperRegClass(SrcRC, DstRC, SrcSubIdx);

103 if (DstSubIdx)

104 return TRI .getMatchingSuperRegClass(DstRC, SrcRC, DstSubIdx);

105 return TRI .getCommonSubClass(SrcRC, DstRC);

106}

107

108void DeadLaneDetector::addUsedLanesOnOperand(const MachineOperand &MO,

111 return;

114 return;

115

116 unsigned MOSubReg = MO.getSubReg();

117 if (MOSubReg != 0)

118 UsedLanes = TRI->composeSubRegIndexLaneMask(MOSubReg, UsedLanes);

119 UsedLanes &= MRI->getMaxLaneMaskForVReg(MOReg);

120

122 DeadLaneDetector::VRegInfo &MORegInfo = VRegInfos[MORegIdx];

123 LaneBitmask PrevUsedLanes = MORegInfo.UsedLanes;

124

125 if ((UsedLanes & ~PrevUsedLanes).none())

126 return;

127

128

129 MORegInfo.UsedLanes = PrevUsedLanes | UsedLanes;

130 if (DefinedByCopy.test(MORegIdx))

131 PutInWorklist(MORegIdx);

132}

133

134void DeadLaneDetector::transferUsedLanesStep(const MachineInstr &MI,

136 for (const MachineOperand &MO : MI.uses()) {

138 continue;

140 addUsedLanesOnOperand(MO, UsedOnMO);

141 }

142}

143

150 DefinedByCopy[MI.getOperand(0).getReg().virtRegIndex()]);

151

152 switch (MI.getOpcode()) {

153 case TargetOpcode::COPY:

154 case TargetOpcode::PHI:

155 return UsedLanes;

156 case TargetOpcode::REG_SEQUENCE: {

157 assert(OpNum % 2 == 1);

158 unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();

159 return TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);

160 }

161 case TargetOpcode::INSERT_SUBREG: {

162 unsigned SubIdx = MI.getOperand(3).getImm();

164 TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);

165 if (OpNum == 2)

166 return MO2UsedLanes;

167

169 Register DefReg = Def.getReg();

173 MO1UsedLanes = UsedLanes & ~TRI->getSubRegIndexLaneMask(SubIdx);

174 else

176

178 return MO1UsedLanes;

179 }

180 case TargetOpcode::EXTRACT_SUBREG: {

182 unsigned SubIdx = MI.getOperand(2).getImm();

183 return TRI->composeSubRegIndexLaneMask(SubIdx, UsedLanes);

184 }

185 default:

186 llvm_unreachable("function must be called with COPY-like instruction");

187 }

188}

189

190void DeadLaneDetector::transferDefinedLanesStep(const MachineOperand &Use,

192 if ( Use .readsReg())

193 return;

194

195

197 if (MI.getDesc().getNumDefs() != 1)

198 return;

199

200

201 if (MI.getOpcode() == TargetOpcode::PATCHPOINT)

202 return;

204 Register DefReg = Def.getReg();

206 return;

208 if (!DefinedByCopy.test(DefRegIdx))

209 return;

210

212 DefinedLanes =

213 TRI->reverseComposeSubRegIndexLaneMask(Use.getSubReg(), DefinedLanes);

215

216 VRegInfo &RegInfo = VRegInfos[DefRegIdx];

217 LaneBitmask PrevDefinedLanes = RegInfo.DefinedLanes;

218

219 if ((DefinedLanes & ~PrevDefinedLanes).none())

220 return;

221

222 RegInfo.DefinedLanes = PrevDefinedLanes | DefinedLanes;

223 PutInWorklist(DefRegIdx);

224}

225

229

230 switch (MI.getOpcode()) {

231 case TargetOpcode::REG_SEQUENCE: {

232 unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();

233 DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);

234 DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);

235 break;

236 }

237 case TargetOpcode::INSERT_SUBREG: {

238 unsigned SubIdx = MI.getOperand(3).getImm();

239 if (OpNum == 2) {

240 DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);

241 DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);

242 } else {

243 assert(OpNum == 1 && "INSERT_SUBREG must have two operands");

244

245 DefinedLanes &= ~TRI->getSubRegIndexLaneMask(SubIdx);

246 }

247 break;

248 }

249 case TargetOpcode::EXTRACT_SUBREG: {

250 unsigned SubIdx = MI.getOperand(2).getImm();

251 assert(OpNum == 1 && "EXTRACT_SUBREG must have one register operand only");

252 DefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(SubIdx, DefinedLanes);

253 break;

254 }

255 case TargetOpcode::COPY:

256 case TargetOpcode::PHI:

257 break;

258 default:

259 llvm_unreachable("function must be called with COPY-like instruction");

260 }

261

262 assert(Def.getSubReg() == 0 &&

263 "Should not have subregister defs in machine SSA phase");

264 DefinedLanes &= MRI->getMaxLaneMaskForVReg(Def.getReg());

265 return DefinedLanes;

266}

267

268LaneBitmask DeadLaneDetector::determineInitialDefinedLanes(Register Reg) {

269

270

271 if ( MRI ->hasOneDef(Reg))

273

277

278

279 unsigned RegIdx = Register(Reg).virtRegIndex();

280 DefinedByCopy.set(RegIdx);

281 PutInWorklist(RegIdx);

282

283 if (Def.isDead())

285

286

287

288

290

291

295 continue;

297 if (!MOReg)

298 continue;

299

305 } else {

307 if (MRI->hasOneDef(MOReg)) {

308 const MachineOperand &MODef = *MRI->def_begin(MOReg);

309 const MachineInstr &MODefMI = *MODef.getParent();

310

312 continue;

313 }

314 unsigned MOSubReg = MO.getSubReg();

315 MODefinedLanes = MRI->getMaxLaneMaskForVReg(MOReg);

316 MODefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(

317 MOSubReg, MODefinedLanes);

318 }

319

322 }

323 return DefinedLanes;

324 }

325 if (DefMI.isImplicitDef() || Def.isDead())

327

329 "Should not have subregister defs in machine SSA phase");

330 return MRI->getMaxLaneMaskForVReg(Reg);

331}

332

335 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {

337 continue;

338

340 if (UseMI.isKill())

341 continue;

342

345 assert(UseMI.getDesc().getNumDefs() == 1);

346 const MachineOperand &Def = *UseMI.defs().begin();

348

349

351

352 bool CrossCopy = false;

354 const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);

356 if (CrossCopy)

358 }

359

360 if (!CrossCopy)

361 continue;

362 }

363 }

364

365

367 return MRI->getMaxLaneMaskForVReg(Reg);

368

369 UsedLanes |= TRI->getSubRegIndexLaneMask(SubReg);

370 }

371 return UsedLanes;

372}

373

374namespace {

375

376class DetectDeadLanes {

377public:

378 bool run(MachineFunction &MF);

379

380private:

381

382

383

384

385

386 std::pair<bool, bool>

387 modifySubRegisterOperandStatus(const DeadLaneDetector &DLD,

388 MachineFunction &MF);

389

390 bool isUndefRegAtInput(const MachineOperand &MO,

391 const DeadLaneDetector::VRegInfo &RegInfo) const;

392

393 bool isUndefInput(const DeadLaneDetector &DLD, const MachineOperand &MO,

394 bool *CrossCopy) const;

395

396 const MachineRegisterInfo *MRI = nullptr;

397 const TargetRegisterInfo *TRI = nullptr;

398};

399

401 static char ID;

402 DetectDeadLanesLegacy() : MachineFunctionPass(ID) {}

403

404 StringRef getPassName() const override { return "Detect Dead Lanes"; }

405

406 void getAnalysisUsage(AnalysisUsage &AU) const override {

409 }

410

411 bool runOnMachineFunction(MachineFunction &MF) override {

412 return DetectDeadLanes().run(MF);

413 }

414};

415

416}

417

418char DetectDeadLanesLegacy::ID = 0;

420

422 false)

423

424bool DetectDeadLanes::isUndefRegAtInput(

426 unsigned SubReg = MO.getSubReg();

428 return (RegInfo.DefinedLanes & RegInfo.UsedLanes & Mask).none();

429}

430

431bool DetectDeadLanes::isUndefInput(const DeadLaneDetector &DLD,

433 bool *CrossCopy) const {

435 return false;

438 return false;

442 return false;

445 return false;

446

449 if (UsedLanes.any())

450 return false;

451

456 }

457 return true;

458}

459

461

462 unsigned NumVirtRegs = MRI->getNumVirtRegs();

463 for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {

465

466

469 Info.UsedLanes = determineInitialUsedLanes(Reg);

470 }

471

472

473 while (!Worklist.empty()) {

474 unsigned RegIdx = Worklist.front();

475 Worklist.pop_front();

476 WorklistMembers.reset(RegIdx);

479

480

481 MachineOperand &Def = *MRI->def_begin(Reg);

482 const MachineInstr &MI = *Def.getParent();

483 transferUsedLanesStep(MI, Info.UsedLanes);

484

485 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg))

486 transferDefinedLanesStep(MO, Info.DefinedLanes);

487 }

488

490 dbgs() << "Defined/Used lanes:\n";

491 for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {

497 }

498 dbgs() << "\n";

499 });

500}

501

502std::pair<bool, bool>

503DetectDeadLanes::modifySubRegisterOperandStatus(const DeadLaneDetector &DLD,

506 bool Again = false;

507

512 continue;

515 continue;

520 << "Marking operand '" << MO << "' as dead in " << MI);

523 }

525 bool CrossCopy = false;

526 if (isUndefRegAtInput(MO, RegInfo)) {

528 << "Marking operand '" << MO << "' as undef in " << MI);

531 } else if (isUndefInput(DLD, MO, &CrossCopy)) {

533 << "Marking operand '" << MO << "' as undef in " << MI);

536 if (CrossCopy)

537 Again = true;

538 }

539 }

540 }

541 }

542 }

543

544 return std::make_pair(Changed, Again);

545}

546

550 if (!DetectDeadLanes().run(MF))

554 return PA;

555}

556

558

559

560

561

562

564 if ( MRI ->subRegLivenessEnabled()) {

565 LLVM_DEBUG(dbgs() << "Skipping Detect dead lanes pass\n");

566 return false;

567 }

568

569 TRI = MRI->getTargetRegisterInfo();

570

572

574 bool Again;

575 do {

577 bool LocalChanged;

578 std::tie(LocalChanged, Again) = modifySubRegisterOperandStatus(DLD, MF);

580 } while (Again);

581

583}

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder & UseMI

MachineInstrBuilder MachineInstrBuilder & DefMI

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

Analysis containing CSE Info

static bool isCrossCopy(const MachineRegisterInfo &MRI, const MachineInstr &MI, const TargetRegisterClass *DstRC, const MachineOperand &MO)

Definition DetectDeadLanes.cpp:67

static bool lowersToCopies(const MachineInstr &MI)

Returns true if MI will get lowered to a series of COPY instructions.

Definition DetectDeadLanes.cpp:52

Analysis that tracks defined/used subregister lanes across COPY instructions and instructions that ge...

Promote Memory to Register

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

LLVM_ABI void setPreservesCFG()

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

bool test(unsigned Idx) const

Represents analyses that only rely on functions' control flow.

LaneBitmask transferUsedLanes(const MachineInstr &MI, LaneBitmask UsedLanes, const MachineOperand &MO) const

Given a mask UsedLanes used from the output of instruction MI determine which lanes are used from ope...

Definition DetectDeadLanes.cpp:145

void computeSubRegisterLaneBitInfo()

Update the DefinedLanes and the UsedLanes for all virtual registers.

DeadLaneDetector(const MachineRegisterInfo *MRI, const TargetRegisterInfo *TRI)

Definition DetectDeadLanes.cpp:41

bool isDefinedByCopy(unsigned RegIdx) const

LaneBitmask transferDefinedLanes(const MachineOperand &Def, unsigned OpNum, LaneBitmask DefinedLanes) const

Given a mask DefinedLanes of lanes defined at operand OpNum of COPY-like instruction,...

Definition DetectDeadLanes.cpp:226

const VRegInfo & getVRegInfo(unsigned RegIdx) const

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

Definition DetectDeadLanes.cpp:548

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

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Representation of each machine instruction.

bool isImplicitDef() const

MachineOperand class - Representation of each machine instruction operand.

unsigned getSubReg() const

LLVM_ABI unsigned getOperandNo() const

Returns the index of this operand in the instruction that it belongs to.

bool readsReg() const

readsReg - Returns true if this operand reads the previous value of its register.

bool isReg() const

isReg - Tests if this is a MO_Register operand.

void setIsDead(bool Val=true)

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

void setIsUndef(bool Val=true)

getReg - Returns the register number.

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

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Wrapper class representing virtual and physical registers.

static Register index2VirtReg(unsigned Index)

Convert a 0-based index to a virtual register number.

unsigned virtRegIndex() const

Convert a virtual register number to a 0-based index.

constexpr bool isVirtual() const

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

constexpr bool isPhysical() const

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

const LaneBitmask LaneMask

const bool CoveredBySubRegs

Whether a combination of subregisters can cover every register in the class.

TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...

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

LLVM_ABI unsigned getOperandNo() const

Return the operand # of this use in its User.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

unsigned ID

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

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

NodeAddr< DefNode * > Def

This is an optimization pass for GlobalISel generic memory operations.

Printable PrintLaneMask(LaneBitmask LaneMask)

Create Printable object to print LaneBitmasks on a raw_ostream.

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()

Returns the minimum set of Analyses that all machine function passes must preserve.

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI char & DetectDeadLanesID

This pass adds dead/undef flags after analyzing subregister lanes.

Definition DetectDeadLanes.cpp:419

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.

Contains a bitmask of which lanes of a given virtual register are defined and which ones are actually...

static constexpr LaneBitmask getAll()

constexpr bool none() const

constexpr bool any() const

static constexpr LaneBitmask getNone()