1 //===- DetectDeadLanes.cpp - SubRegister Lane Usage Analysis --*- C++ -*---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// Analysis that tracks defined/used subregister lanes across COPY instructions
12 /// and instructions that get lowered to a COPY (PHI, REG_SEQUENCE,
13 /// INSERT_SUBREG, EXTRACT_SUBREG).
14 /// The information is used to detect dead definitions and the usage of
15 /// (completely) undefined values and mark the operands as such.
16 /// This pass is necessary because the dead/undef status is not obvious anymore
17 /// when subregisters are involved.
20 /// %0 = some definition
22 /// %2 = REG_SEQUENCE %0, sub0, %1, sub1
23 /// %3 = EXTRACT_SUBREG %2, sub1
25 /// The %0 definition is dead and %3 contains an undefined value.
27 //===----------------------------------------------------------------------===//
32 #include "llvm/ADT/BitVector.h"
33 #include "llvm/ADT/SetVector.h"
34 #include "llvm/CodeGen/MachineFunctionPass.h"
35 #include "llvm/CodeGen/MachineRegisterInfo.h"
36 #include "llvm/CodeGen/Passes.h"
37 #include "llvm/CodeGen/TargetRegisterInfo.h"
38 #include "llvm/CodeGen/TargetSubtargetInfo.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
41 #include "llvm/PassRegistry.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/Support/raw_ostream.h"
47 #define DEBUG_TYPE "detect-dead-lanes"
51 /// Contains a bitmask of which lanes of a given virtual register are
52 /// defined and which ones are actually used.
54 LaneBitmask UsedLanes;
55 LaneBitmask DefinedLanes;
58 class DetectDeadLanes : public MachineFunctionPass {
60 bool runOnMachineFunction(MachineFunction &MF) override;
63 DetectDeadLanes() : MachineFunctionPass(ID) {}
65 StringRef getPassName() const override { return "Detect Dead Lanes"; }
67 void getAnalysisUsage(AnalysisUsage &AU) const override {
69 MachineFunctionPass::getAnalysisUsage(AU);
73 /// Add used lane bits on the register used by operand \p MO. This translates
74 /// the bitmask based on the operands subregister, and puts the register into
75 /// the worklist if any new bits were added.
76 void addUsedLanesOnOperand(const MachineOperand &MO, LaneBitmask UsedLanes);
78 /// Given a bitmask \p UsedLanes for the used lanes on a def output of a
79 /// COPY-like instruction determine the lanes used on the use operands
80 /// and call addUsedLanesOnOperand() for them.
81 void transferUsedLanesStep(const MachineInstr &MI, LaneBitmask UsedLanes);
83 /// Given a use regiser operand \p Use and a mask of defined lanes, check
84 /// if the operand belongs to a lowersToCopies() instruction, transfer the
85 /// mask to the def and put the instruction into the worklist.
86 void transferDefinedLanesStep(const MachineOperand &Use,
87 LaneBitmask DefinedLanes);
89 /// Given a mask \p DefinedLanes of lanes defined at operand \p OpNum
90 /// of COPY-like instruction, determine which lanes are defined at the output
92 LaneBitmask transferDefinedLanes(const MachineOperand &Def, unsigned OpNum,
93 LaneBitmask DefinedLanes) const;
95 /// Given a mask \p UsedLanes used from the output of instruction \p MI
96 /// determine which lanes are used from operand \p MO of this instruction.
97 LaneBitmask transferUsedLanes(const MachineInstr &MI, LaneBitmask UsedLanes,
98 const MachineOperand &MO) const;
100 bool runOnce(MachineFunction &MF);
102 LaneBitmask determineInitialDefinedLanes(unsigned Reg);
103 LaneBitmask determineInitialUsedLanes(unsigned Reg);
105 bool isUndefRegAtInput(const MachineOperand &MO,
106 const VRegInfo &RegInfo) const;
108 bool isUndefInput(const MachineOperand &MO, bool *CrossCopy) const;
110 const MachineRegisterInfo *MRI;
111 const TargetRegisterInfo *TRI;
113 void PutInWorklist(unsigned RegIdx) {
114 if (WorklistMembers.test(RegIdx))
116 WorklistMembers.set(RegIdx);
117 Worklist.push_back(RegIdx);
121 /// Worklist containing virtreg indexes.
122 std::deque<unsigned> Worklist;
123 BitVector WorklistMembers;
124 /// This bitvector is set for each vreg index where the vreg is defined
125 /// by an instruction where lowersToCopies()==true.
126 BitVector DefinedByCopy;
129 } // end anonymous namespace
131 char DetectDeadLanes::ID = 0;
132 char &llvm::DetectDeadLanesID = DetectDeadLanes::ID;
134 INITIALIZE_PASS(DetectDeadLanes, DEBUG_TYPE, "Detect Dead Lanes", false, false)
136 /// Returns true if \p MI will get lowered to a series of COPY instructions.
137 /// We call this a COPY-like instruction.
138 static bool lowersToCopies(const MachineInstr &MI) {
139 // Note: We could support instructions with MCInstrDesc::isRegSequenceLike(),
140 // isExtractSubRegLike(), isInsertSubregLike() in the future even though they
141 // are not lowered to a COPY.
142 switch (MI.getOpcode()) {
143 case TargetOpcode::COPY:
144 case TargetOpcode::PHI:
145 case TargetOpcode::INSERT_SUBREG:
146 case TargetOpcode::REG_SEQUENCE:
147 case TargetOpcode::EXTRACT_SUBREG:
153 static bool isCrossCopy(const MachineRegisterInfo &MRI,
154 const MachineInstr &MI,
155 const TargetRegisterClass *DstRC,
156 const MachineOperand &MO) {
157 assert(lowersToCopies(MI));
158 unsigned SrcReg = MO.getReg();
159 const TargetRegisterClass *SrcRC = MRI.getRegClass(SrcReg);
163 unsigned SrcSubIdx = MO.getSubReg();
165 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
166 unsigned DstSubIdx = 0;
167 switch (MI.getOpcode()) {
168 case TargetOpcode::INSERT_SUBREG:
169 if (MI.getOperandNo(&MO) == 2)
170 DstSubIdx = MI.getOperand(3).getImm();
172 case TargetOpcode::REG_SEQUENCE: {
173 unsigned OpNum = MI.getOperandNo(&MO);
174 DstSubIdx = MI.getOperand(OpNum+1).getImm();
177 case TargetOpcode::EXTRACT_SUBREG: {
178 unsigned SubReg = MI.getOperand(2).getImm();
179 SrcSubIdx = TRI.composeSubRegIndices(SubReg, SrcSubIdx);
183 unsigned PreA, PreB; // Unused.
184 if (SrcSubIdx && DstSubIdx)
185 return !TRI.getCommonSuperRegClass(SrcRC, SrcSubIdx, DstRC, DstSubIdx, PreA,
188 return !TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSubIdx);
190 return !TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSubIdx);
191 return !TRI.getCommonSubClass(SrcRC, DstRC);
194 void DetectDeadLanes::addUsedLanesOnOperand(const MachineOperand &MO,
195 LaneBitmask UsedLanes) {
198 unsigned MOReg = MO.getReg();
199 if (!TargetRegisterInfo::isVirtualRegister(MOReg))
202 unsigned MOSubReg = MO.getSubReg();
204 UsedLanes = TRI->composeSubRegIndexLaneMask(MOSubReg, UsedLanes);
205 UsedLanes &= MRI->getMaxLaneMaskForVReg(MOReg);
207 unsigned MORegIdx = TargetRegisterInfo::virtReg2Index(MOReg);
208 VRegInfo &MORegInfo = VRegInfos[MORegIdx];
209 LaneBitmask PrevUsedLanes = MORegInfo.UsedLanes;
210 // Any change at all?
211 if ((UsedLanes & ~PrevUsedLanes).none())
214 // Set UsedLanes and remember instruction for further propagation.
215 MORegInfo.UsedLanes = PrevUsedLanes | UsedLanes;
216 if (DefinedByCopy.test(MORegIdx))
217 PutInWorklist(MORegIdx);
220 void DetectDeadLanes::transferUsedLanesStep(const MachineInstr &MI,
221 LaneBitmask UsedLanes) {
222 for (const MachineOperand &MO : MI.uses()) {
223 if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
225 LaneBitmask UsedOnMO = transferUsedLanes(MI, UsedLanes, MO);
226 addUsedLanesOnOperand(MO, UsedOnMO);
230 LaneBitmask DetectDeadLanes::transferUsedLanes(const MachineInstr &MI,
231 LaneBitmask UsedLanes,
232 const MachineOperand &MO) const {
233 unsigned OpNum = MI.getOperandNo(&MO);
234 assert(lowersToCopies(MI) && DefinedByCopy[
235 TargetRegisterInfo::virtReg2Index(MI.getOperand(0).getReg())]);
237 switch (MI.getOpcode()) {
238 case TargetOpcode::COPY:
239 case TargetOpcode::PHI:
241 case TargetOpcode::REG_SEQUENCE: {
242 assert(OpNum % 2 == 1);
243 unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
244 return TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
246 case TargetOpcode::INSERT_SUBREG: {
247 unsigned SubIdx = MI.getOperand(3).getImm();
248 LaneBitmask MO2UsedLanes =
249 TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
253 const MachineOperand &Def = MI.getOperand(0);
254 unsigned DefReg = Def.getReg();
255 const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
256 LaneBitmask MO1UsedLanes;
257 if (RC->CoveredBySubRegs)
258 MO1UsedLanes = UsedLanes & ~TRI->getSubRegIndexLaneMask(SubIdx);
260 MO1UsedLanes = RC->LaneMask;
265 case TargetOpcode::EXTRACT_SUBREG: {
267 unsigned SubIdx = MI.getOperand(2).getImm();
268 return TRI->composeSubRegIndexLaneMask(SubIdx, UsedLanes);
271 llvm_unreachable("function must be called with COPY-like instruction");
275 void DetectDeadLanes::transferDefinedLanesStep(const MachineOperand &Use,
276 LaneBitmask DefinedLanes) {
279 // Check whether the operand writes a vreg and is part of a COPY-like
281 const MachineInstr &MI = *Use.getParent();
282 if (MI.getDesc().getNumDefs() != 1)
284 // FIXME: PATCHPOINT instructions announce a Def that does not always exist,
285 // they really need to be modeled differently!
286 if (MI.getOpcode() == TargetOpcode::PATCHPOINT)
288 const MachineOperand &Def = *MI.defs().begin();
289 unsigned DefReg = Def.getReg();
290 if (!TargetRegisterInfo::isVirtualRegister(DefReg))
292 unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
293 if (!DefinedByCopy.test(DefRegIdx))
296 unsigned OpNum = MI.getOperandNo(&Use);
298 TRI->reverseComposeSubRegIndexLaneMask(Use.getSubReg(), DefinedLanes);
299 DefinedLanes = transferDefinedLanes(Def, OpNum, DefinedLanes);
301 VRegInfo &RegInfo = VRegInfos[DefRegIdx];
302 LaneBitmask PrevDefinedLanes = RegInfo.DefinedLanes;
303 // Any change at all?
304 if ((DefinedLanes & ~PrevDefinedLanes).none())
307 RegInfo.DefinedLanes = PrevDefinedLanes | DefinedLanes;
308 PutInWorklist(DefRegIdx);
311 LaneBitmask DetectDeadLanes::transferDefinedLanes(const MachineOperand &Def,
312 unsigned OpNum, LaneBitmask DefinedLanes) const {
313 const MachineInstr &MI = *Def.getParent();
314 // Translate DefinedLanes if necessary.
315 switch (MI.getOpcode()) {
316 case TargetOpcode::REG_SEQUENCE: {
317 unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
318 DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
319 DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
322 case TargetOpcode::INSERT_SUBREG: {
323 unsigned SubIdx = MI.getOperand(3).getImm();
325 DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
326 DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
328 assert(OpNum == 1 && "INSERT_SUBREG must have two operands");
329 // Ignore lanes defined by operand 2.
330 DefinedLanes &= ~TRI->getSubRegIndexLaneMask(SubIdx);
334 case TargetOpcode::EXTRACT_SUBREG: {
335 unsigned SubIdx = MI.getOperand(2).getImm();
336 assert(OpNum == 1 && "EXTRACT_SUBREG must have one register operand only");
337 DefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(SubIdx, DefinedLanes);
340 case TargetOpcode::COPY:
341 case TargetOpcode::PHI:
344 llvm_unreachable("function must be called with COPY-like instruction");
347 assert(Def.getSubReg() == 0 &&
348 "Should not have subregister defs in machine SSA phase");
349 DefinedLanes &= MRI->getMaxLaneMaskForVReg(Def.getReg());
353 LaneBitmask DetectDeadLanes::determineInitialDefinedLanes(unsigned Reg) {
354 // Live-In or unused registers have no definition but are considered fully
356 if (!MRI->hasOneDef(Reg))
357 return LaneBitmask::getAll();
359 const MachineOperand &Def = *MRI->def_begin(Reg);
360 const MachineInstr &DefMI = *Def.getParent();
361 if (lowersToCopies(DefMI)) {
362 // Start optimisatically with no used or defined lanes for copy
363 // instructions. The following dataflow analysis will add more bits.
364 unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
365 DefinedByCopy.set(RegIdx);
366 PutInWorklist(RegIdx);
369 return LaneBitmask::getNone();
371 // COPY/PHI can copy across unrelated register classes (example: float/int)
372 // with incompatible subregister structure. Do not include these in the
373 // dataflow analysis since we cannot transfer lanemasks in a meaningful way.
374 const TargetRegisterClass *DefRC = MRI->getRegClass(Reg);
376 // Determine initially DefinedLanes.
377 LaneBitmask DefinedLanes;
378 for (const MachineOperand &MO : DefMI.uses()) {
379 if (!MO.isReg() || !MO.readsReg())
381 unsigned MOReg = MO.getReg();
385 LaneBitmask MODefinedLanes;
386 if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
387 MODefinedLanes = LaneBitmask::getAll();
388 } else if (isCrossCopy(*MRI, DefMI, DefRC, MO)) {
389 MODefinedLanes = LaneBitmask::getAll();
391 assert(TargetRegisterInfo::isVirtualRegister(MOReg));
392 if (MRI->hasOneDef(MOReg)) {
393 const MachineOperand &MODef = *MRI->def_begin(MOReg);
394 const MachineInstr &MODefMI = *MODef.getParent();
395 // Bits from copy-like operations will be added later.
396 if (lowersToCopies(MODefMI) || MODefMI.isImplicitDef())
399 unsigned MOSubReg = MO.getSubReg();
400 MODefinedLanes = MRI->getMaxLaneMaskForVReg(MOReg);
401 MODefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(
402 MOSubReg, MODefinedLanes);
405 unsigned OpNum = DefMI.getOperandNo(&MO);
406 DefinedLanes |= transferDefinedLanes(Def, OpNum, MODefinedLanes);
410 if (DefMI.isImplicitDef() || Def.isDead())
411 return LaneBitmask::getNone();
413 assert(Def.getSubReg() == 0 &&
414 "Should not have subregister defs in machine SSA phase");
415 return MRI->getMaxLaneMaskForVReg(Reg);
418 LaneBitmask DetectDeadLanes::determineInitialUsedLanes(unsigned Reg) {
419 LaneBitmask UsedLanes = LaneBitmask::getNone();
420 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
424 const MachineInstr &UseMI = *MO.getParent();
428 unsigned SubReg = MO.getSubReg();
429 if (lowersToCopies(UseMI)) {
430 assert(UseMI.getDesc().getNumDefs() == 1);
431 const MachineOperand &Def = *UseMI.defs().begin();
432 unsigned DefReg = Def.getReg();
433 // The used lanes of COPY-like instruction operands are determined by the
434 // following dataflow analysis.
435 if (TargetRegisterInfo::isVirtualRegister(DefReg)) {
436 // But ignore copies across incompatible register classes.
437 bool CrossCopy = false;
438 if (lowersToCopies(UseMI)) {
439 const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
440 CrossCopy = isCrossCopy(*MRI, UseMI, DstRC, MO);
442 DEBUG(dbgs() << "Copy across incompatible classes: " << UseMI);
450 // Shortcut: All lanes are used.
452 return MRI->getMaxLaneMaskForVReg(Reg);
454 UsedLanes |= TRI->getSubRegIndexLaneMask(SubReg);
459 bool DetectDeadLanes::isUndefRegAtInput(const MachineOperand &MO,
460 const VRegInfo &RegInfo) const {
461 unsigned SubReg = MO.getSubReg();
462 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
463 return (RegInfo.DefinedLanes & RegInfo.UsedLanes & Mask).none();
466 bool DetectDeadLanes::isUndefInput(const MachineOperand &MO,
467 bool *CrossCopy) const {
470 const MachineInstr &MI = *MO.getParent();
471 if (!lowersToCopies(MI))
473 const MachineOperand &Def = MI.getOperand(0);
474 unsigned DefReg = Def.getReg();
475 if (!TargetRegisterInfo::isVirtualRegister(DefReg))
477 unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
478 if (!DefinedByCopy.test(DefRegIdx))
481 const VRegInfo &DefRegInfo = VRegInfos[DefRegIdx];
482 LaneBitmask UsedLanes = transferUsedLanes(MI, DefRegInfo.UsedLanes, MO);
486 unsigned MOReg = MO.getReg();
487 if (TargetRegisterInfo::isVirtualRegister(MOReg)) {
488 const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
489 *CrossCopy = isCrossCopy(*MRI, MI, DstRC, MO);
494 bool DetectDeadLanes::runOnce(MachineFunction &MF) {
495 // First pass: Populate defs/uses of vregs with initial values
496 unsigned NumVirtRegs = MRI->getNumVirtRegs();
497 for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
498 unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
500 // Determine used/defined lanes and add copy instructions to worklist.
501 VRegInfo &Info = VRegInfos[RegIdx];
502 Info.DefinedLanes = determineInitialDefinedLanes(Reg);
503 Info.UsedLanes = determineInitialUsedLanes(Reg);
506 // Iterate as long as defined lanes/used lanes keep changing.
507 while (!Worklist.empty()) {
508 unsigned RegIdx = Worklist.front();
509 Worklist.pop_front();
510 WorklistMembers.reset(RegIdx);
511 VRegInfo &Info = VRegInfos[RegIdx];
512 unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
514 // Transfer UsedLanes to operands of DefMI (backwards dataflow).
515 MachineOperand &Def = *MRI->def_begin(Reg);
516 const MachineInstr &MI = *Def.getParent();
517 transferUsedLanesStep(MI, Info.UsedLanes);
518 // Transfer DefinedLanes to users of Reg (forward dataflow).
519 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg))
520 transferDefinedLanesStep(MO, Info.DefinedLanes);
524 dbgs() << "Defined/Used lanes:\n";
525 for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
526 unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
527 const VRegInfo &Info = VRegInfos[RegIdx];
528 dbgs() << printReg(Reg, nullptr)
529 << " Used: " << PrintLaneMask(Info.UsedLanes)
530 << " Def: " << PrintLaneMask(Info.DefinedLanes) << '\n';
536 // Mark operands as dead/unused.
537 for (MachineBasicBlock &MBB : MF) {
538 for (MachineInstr &MI : MBB) {
539 for (MachineOperand &MO : MI.operands()) {
542 unsigned Reg = MO.getReg();
543 if (!TargetRegisterInfo::isVirtualRegister(Reg))
545 unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
546 const VRegInfo &RegInfo = VRegInfos[RegIdx];
547 if (MO.isDef() && !MO.isDead() && RegInfo.UsedLanes.none()) {
548 DEBUG(dbgs() << "Marking operand '" << MO << "' as dead in " << MI);
552 bool CrossCopy = false;
553 if (isUndefRegAtInput(MO, RegInfo)) {
554 DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in "
557 } else if (isUndefInput(MO, &CrossCopy)) {
558 DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in "
572 bool DetectDeadLanes::runOnMachineFunction(MachineFunction &MF) {
573 // Don't bother if we won't track subregister liveness later. This pass is
574 // required for correctness if subregister liveness is enabled because the
575 // register coalescer cannot deal with hidden dead defs. However without
576 // subregister liveness enabled, the expected benefits of this pass are small
577 // so we safe the compile time.
578 MRI = &MF.getRegInfo();
579 if (!MRI->subRegLivenessEnabled()) {
580 DEBUG(dbgs() << "Skipping Detect dead lanes pass\n");
584 TRI = MRI->getTargetRegisterInfo();
586 unsigned NumVirtRegs = MRI->getNumVirtRegs();
587 VRegInfos = new VRegInfo[NumVirtRegs];
588 WorklistMembers.resize(NumVirtRegs);
589 DefinedByCopy.resize(NumVirtRegs);
596 DefinedByCopy.clear();
597 WorklistMembers.clear();