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 /// %vreg0 = some definition
21 /// %vreg1 = IMPLICIT_DEF
22 /// %vreg2 = REG_SEQUENCE %vreg0, sub0, %vreg1, sub1
23 /// %vreg3 = EXTRACT_SUBREG %vreg2, sub1
25 /// The %vreg0 definition is dead and %vreg3 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/InitializePasses.h"
38 #include "llvm/Pass.h"
39 #include "llvm/PassRegistry.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetRegisterInfo.h"
44 #include "llvm/Target/TargetSubtargetInfo.h"
48 #define DEBUG_TYPE "detect-dead-lanes"
52 /// Contains a bitmask of which lanes of a given virtual register are
53 /// defined and which ones are actually used.
55 LaneBitmask UsedLanes;
56 LaneBitmask DefinedLanes;
59 class DetectDeadLanes : public MachineFunctionPass {
61 bool runOnMachineFunction(MachineFunction &MF) override;
64 DetectDeadLanes() : MachineFunctionPass(ID) {}
66 StringRef getPassName() const override { return "Detect Dead Lanes"; }
68 void getAnalysisUsage(AnalysisUsage &AU) const override {
70 MachineFunctionPass::getAnalysisUsage(AU);
74 /// Add used lane bits on the register used by operand \p MO. This translates
75 /// the bitmask based on the operands subregister, and puts the register into
76 /// the worklist if any new bits were added.
77 void addUsedLanesOnOperand(const MachineOperand &MO, LaneBitmask UsedLanes);
79 /// Given a bitmask \p UsedLanes for the used lanes on a def output of a
80 /// COPY-like instruction determine the lanes used on the use operands
81 /// and call addUsedLanesOnOperand() for them.
82 void transferUsedLanesStep(const MachineInstr &MI, LaneBitmask UsedLanes);
84 /// Given a use regiser operand \p Use and a mask of defined lanes, check
85 /// if the operand belongs to a lowersToCopies() instruction, transfer the
86 /// mask to the def and put the instruction into the worklist.
87 void transferDefinedLanesStep(const MachineOperand &Use,
88 LaneBitmask DefinedLanes);
90 /// Given a mask \p DefinedLanes of lanes defined at operand \p OpNum
91 /// of COPY-like instruction, determine which lanes are defined at the output
93 LaneBitmask transferDefinedLanes(const MachineOperand &Def, unsigned OpNum,
94 LaneBitmask DefinedLanes) const;
96 /// Given a mask \p UsedLanes used from the output of instruction \p MI
97 /// determine which lanes are used from operand \p MO of this instruction.
98 LaneBitmask transferUsedLanes(const MachineInstr &MI, LaneBitmask UsedLanes,
99 const MachineOperand &MO) const;
101 bool runOnce(MachineFunction &MF);
103 LaneBitmask determineInitialDefinedLanes(unsigned Reg);
104 LaneBitmask determineInitialUsedLanes(unsigned Reg);
106 bool isUndefRegAtInput(const MachineOperand &MO,
107 const VRegInfo &RegInfo) const;
109 bool isUndefInput(const MachineOperand &MO, bool *CrossCopy) const;
111 const MachineRegisterInfo *MRI;
112 const TargetRegisterInfo *TRI;
114 void PutInWorklist(unsigned RegIdx) {
115 if (WorklistMembers.test(RegIdx))
117 WorklistMembers.set(RegIdx);
118 Worklist.push_back(RegIdx);
122 /// Worklist containing virtreg indexes.
123 std::deque<unsigned> Worklist;
124 BitVector WorklistMembers;
125 /// This bitvector is set for each vreg index where the vreg is defined
126 /// by an instruction where lowersToCopies()==true.
127 BitVector DefinedByCopy;
130 } // end anonymous namespace
132 char DetectDeadLanes::ID = 0;
133 char &llvm::DetectDeadLanesID = DetectDeadLanes::ID;
135 INITIALIZE_PASS(DetectDeadLanes, "detect-dead-lanes", "Detect Dead Lanes",
138 /// Returns true if \p MI will get lowered to a series of COPY instructions.
139 /// We call this a COPY-like instruction.
140 static bool lowersToCopies(const MachineInstr &MI) {
141 // Note: We could support instructions with MCInstrDesc::isRegSequenceLike(),
142 // isExtractSubRegLike(), isInsertSubregLike() in the future even though they
143 // are not lowered to a COPY.
144 switch (MI.getOpcode()) {
145 case TargetOpcode::COPY:
146 case TargetOpcode::PHI:
147 case TargetOpcode::INSERT_SUBREG:
148 case TargetOpcode::REG_SEQUENCE:
149 case TargetOpcode::EXTRACT_SUBREG:
155 static bool isCrossCopy(const MachineRegisterInfo &MRI,
156 const MachineInstr &MI,
157 const TargetRegisterClass *DstRC,
158 const MachineOperand &MO) {
159 assert(lowersToCopies(MI));
160 unsigned SrcReg = MO.getReg();
161 const TargetRegisterClass *SrcRC = MRI.getRegClass(SrcReg);
165 unsigned SrcSubIdx = MO.getSubReg();
167 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
168 unsigned DstSubIdx = 0;
169 switch (MI.getOpcode()) {
170 case TargetOpcode::INSERT_SUBREG:
171 if (MI.getOperandNo(&MO) == 2)
172 DstSubIdx = MI.getOperand(3).getImm();
174 case TargetOpcode::REG_SEQUENCE: {
175 unsigned OpNum = MI.getOperandNo(&MO);
176 DstSubIdx = MI.getOperand(OpNum+1).getImm();
179 case TargetOpcode::EXTRACT_SUBREG: {
180 unsigned SubReg = MI.getOperand(2).getImm();
181 SrcSubIdx = TRI.composeSubRegIndices(SubReg, SrcSubIdx);
185 unsigned PreA, PreB; // Unused.
186 if (SrcSubIdx && DstSubIdx)
187 return !TRI.getCommonSuperRegClass(SrcRC, SrcSubIdx, DstRC, DstSubIdx, PreA,
190 return !TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSubIdx);
192 return !TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSubIdx);
193 return !TRI.getCommonSubClass(SrcRC, DstRC);
196 void DetectDeadLanes::addUsedLanesOnOperand(const MachineOperand &MO,
197 LaneBitmask UsedLanes) {
200 unsigned MOReg = MO.getReg();
201 if (!TargetRegisterInfo::isVirtualRegister(MOReg))
204 unsigned MOSubReg = MO.getSubReg();
206 UsedLanes = TRI->composeSubRegIndexLaneMask(MOSubReg, UsedLanes);
207 UsedLanes &= MRI->getMaxLaneMaskForVReg(MOReg);
209 unsigned MORegIdx = TargetRegisterInfo::virtReg2Index(MOReg);
210 VRegInfo &MORegInfo = VRegInfos[MORegIdx];
211 LaneBitmask PrevUsedLanes = MORegInfo.UsedLanes;
212 // Any change at all?
213 if ((UsedLanes & ~PrevUsedLanes).none())
216 // Set UsedLanes and remember instruction for further propagation.
217 MORegInfo.UsedLanes = PrevUsedLanes | UsedLanes;
218 if (DefinedByCopy.test(MORegIdx))
219 PutInWorklist(MORegIdx);
222 void DetectDeadLanes::transferUsedLanesStep(const MachineInstr &MI,
223 LaneBitmask UsedLanes) {
224 for (const MachineOperand &MO : MI.uses()) {
225 if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
227 LaneBitmask UsedOnMO = transferUsedLanes(MI, UsedLanes, MO);
228 addUsedLanesOnOperand(MO, UsedOnMO);
232 LaneBitmask DetectDeadLanes::transferUsedLanes(const MachineInstr &MI,
233 LaneBitmask UsedLanes,
234 const MachineOperand &MO) const {
235 unsigned OpNum = MI.getOperandNo(&MO);
236 assert(lowersToCopies(MI) && DefinedByCopy[
237 TargetRegisterInfo::virtReg2Index(MI.getOperand(0).getReg())]);
239 switch (MI.getOpcode()) {
240 case TargetOpcode::COPY:
241 case TargetOpcode::PHI:
243 case TargetOpcode::REG_SEQUENCE: {
244 assert(OpNum % 2 == 1);
245 unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
246 return TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
248 case TargetOpcode::INSERT_SUBREG: {
249 unsigned SubIdx = MI.getOperand(3).getImm();
250 LaneBitmask MO2UsedLanes =
251 TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
255 const MachineOperand &Def = MI.getOperand(0);
256 unsigned DefReg = Def.getReg();
257 const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
258 LaneBitmask MO1UsedLanes;
259 if (RC->CoveredBySubRegs)
260 MO1UsedLanes = UsedLanes & ~TRI->getSubRegIndexLaneMask(SubIdx);
262 MO1UsedLanes = RC->LaneMask;
267 case TargetOpcode::EXTRACT_SUBREG: {
269 unsigned SubIdx = MI.getOperand(2).getImm();
270 return TRI->composeSubRegIndexLaneMask(SubIdx, UsedLanes);
273 llvm_unreachable("function must be called with COPY-like instruction");
277 void DetectDeadLanes::transferDefinedLanesStep(const MachineOperand &Use,
278 LaneBitmask DefinedLanes) {
281 // Check whether the operand writes a vreg and is part of a COPY-like
283 const MachineInstr &MI = *Use.getParent();
284 if (MI.getDesc().getNumDefs() != 1)
286 // FIXME: PATCHPOINT instructions announce a Def that does not always exist,
287 // they really need to be modeled differently!
288 if (MI.getOpcode() == TargetOpcode::PATCHPOINT)
290 const MachineOperand &Def = *MI.defs().begin();
291 unsigned DefReg = Def.getReg();
292 if (!TargetRegisterInfo::isVirtualRegister(DefReg))
294 unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
295 if (!DefinedByCopy.test(DefRegIdx))
298 unsigned OpNum = MI.getOperandNo(&Use);
300 TRI->reverseComposeSubRegIndexLaneMask(Use.getSubReg(), DefinedLanes);
301 DefinedLanes = transferDefinedLanes(Def, OpNum, DefinedLanes);
303 VRegInfo &RegInfo = VRegInfos[DefRegIdx];
304 LaneBitmask PrevDefinedLanes = RegInfo.DefinedLanes;
305 // Any change at all?
306 if ((DefinedLanes & ~PrevDefinedLanes).none())
309 RegInfo.DefinedLanes = PrevDefinedLanes | DefinedLanes;
310 PutInWorklist(DefRegIdx);
313 LaneBitmask DetectDeadLanes::transferDefinedLanes(const MachineOperand &Def,
314 unsigned OpNum, LaneBitmask DefinedLanes) const {
315 const MachineInstr &MI = *Def.getParent();
316 // Translate DefinedLanes if necessary.
317 switch (MI.getOpcode()) {
318 case TargetOpcode::REG_SEQUENCE: {
319 unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
320 DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
321 DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
324 case TargetOpcode::INSERT_SUBREG: {
325 unsigned SubIdx = MI.getOperand(3).getImm();
327 DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
328 DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
330 assert(OpNum == 1 && "INSERT_SUBREG must have two operands");
331 // Ignore lanes defined by operand 2.
332 DefinedLanes &= ~TRI->getSubRegIndexLaneMask(SubIdx);
336 case TargetOpcode::EXTRACT_SUBREG: {
337 unsigned SubIdx = MI.getOperand(2).getImm();
338 assert(OpNum == 1 && "EXTRACT_SUBREG must have one register operand only");
339 DefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(SubIdx, DefinedLanes);
342 case TargetOpcode::COPY:
343 case TargetOpcode::PHI:
346 llvm_unreachable("function must be called with COPY-like instruction");
349 assert(Def.getSubReg() == 0 &&
350 "Should not have subregister defs in machine SSA phase");
351 DefinedLanes &= MRI->getMaxLaneMaskForVReg(Def.getReg());
355 LaneBitmask DetectDeadLanes::determineInitialDefinedLanes(unsigned Reg) {
356 // Live-In or unused registers have no definition but are considered fully
358 if (!MRI->hasOneDef(Reg))
359 return LaneBitmask::getAll();
361 const MachineOperand &Def = *MRI->def_begin(Reg);
362 const MachineInstr &DefMI = *Def.getParent();
363 if (lowersToCopies(DefMI)) {
364 // Start optimisatically with no used or defined lanes for copy
365 // instructions. The following dataflow analysis will add more bits.
366 unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
367 DefinedByCopy.set(RegIdx);
368 PutInWorklist(RegIdx);
371 return LaneBitmask::getNone();
373 // COPY/PHI can copy across unrelated register classes (example: float/int)
374 // with incompatible subregister structure. Do not include these in the
375 // dataflow analysis since we cannot transfer lanemasks in a meaningful way.
376 const TargetRegisterClass *DefRC = MRI->getRegClass(Reg);
378 // Determine initially DefinedLanes.
379 LaneBitmask DefinedLanes;
380 for (const MachineOperand &MO : DefMI.uses()) {
381 if (!MO.isReg() || !MO.readsReg())
383 unsigned MOReg = MO.getReg();
387 LaneBitmask MODefinedLanes;
388 if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
389 MODefinedLanes = LaneBitmask::getAll();
390 } else if (isCrossCopy(*MRI, DefMI, DefRC, MO)) {
391 MODefinedLanes = LaneBitmask::getAll();
393 assert(TargetRegisterInfo::isVirtualRegister(MOReg));
394 if (MRI->hasOneDef(MOReg)) {
395 const MachineOperand &MODef = *MRI->def_begin(MOReg);
396 const MachineInstr &MODefMI = *MODef.getParent();
397 // Bits from copy-like operations will be added later.
398 if (lowersToCopies(MODefMI) || MODefMI.isImplicitDef())
401 unsigned MOSubReg = MO.getSubReg();
402 MODefinedLanes = MRI->getMaxLaneMaskForVReg(MOReg);
403 MODefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(
404 MOSubReg, MODefinedLanes);
407 unsigned OpNum = DefMI.getOperandNo(&MO);
408 DefinedLanes |= transferDefinedLanes(Def, OpNum, MODefinedLanes);
412 if (DefMI.isImplicitDef() || Def.isDead())
413 return LaneBitmask::getNone();
415 assert(Def.getSubReg() == 0 &&
416 "Should not have subregister defs in machine SSA phase");
417 return MRI->getMaxLaneMaskForVReg(Reg);
420 LaneBitmask DetectDeadLanes::determineInitialUsedLanes(unsigned Reg) {
421 LaneBitmask UsedLanes = LaneBitmask::getNone();
422 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
426 const MachineInstr &UseMI = *MO.getParent();
430 unsigned SubReg = MO.getSubReg();
431 if (lowersToCopies(UseMI)) {
432 assert(UseMI.getDesc().getNumDefs() == 1);
433 const MachineOperand &Def = *UseMI.defs().begin();
434 unsigned DefReg = Def.getReg();
435 // The used lanes of COPY-like instruction operands are determined by the
436 // following dataflow analysis.
437 if (TargetRegisterInfo::isVirtualRegister(DefReg)) {
438 // But ignore copies across incompatible register classes.
439 bool CrossCopy = false;
440 if (lowersToCopies(UseMI)) {
441 const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
442 CrossCopy = isCrossCopy(*MRI, UseMI, DstRC, MO);
444 DEBUG(dbgs() << "Copy accross incompatible classes: " << UseMI);
452 // Shortcut: All lanes are used.
454 return MRI->getMaxLaneMaskForVReg(Reg);
456 UsedLanes |= TRI->getSubRegIndexLaneMask(SubReg);
461 bool DetectDeadLanes::isUndefRegAtInput(const MachineOperand &MO,
462 const VRegInfo &RegInfo) const {
463 unsigned SubReg = MO.getSubReg();
464 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
465 return (RegInfo.DefinedLanes & RegInfo.UsedLanes & Mask).none();
468 bool DetectDeadLanes::isUndefInput(const MachineOperand &MO,
469 bool *CrossCopy) const {
472 const MachineInstr &MI = *MO.getParent();
473 if (!lowersToCopies(MI))
475 const MachineOperand &Def = MI.getOperand(0);
476 unsigned DefReg = Def.getReg();
477 if (!TargetRegisterInfo::isVirtualRegister(DefReg))
479 unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
480 if (!DefinedByCopy.test(DefRegIdx))
483 const VRegInfo &DefRegInfo = VRegInfos[DefRegIdx];
484 LaneBitmask UsedLanes = transferUsedLanes(MI, DefRegInfo.UsedLanes, MO);
488 unsigned MOReg = MO.getReg();
489 if (TargetRegisterInfo::isVirtualRegister(MOReg)) {
490 const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
491 *CrossCopy = isCrossCopy(*MRI, MI, DstRC, MO);
496 bool DetectDeadLanes::runOnce(MachineFunction &MF) {
497 // First pass: Populate defs/uses of vregs with initial values
498 unsigned NumVirtRegs = MRI->getNumVirtRegs();
499 for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
500 unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
502 // Determine used/defined lanes and add copy instructions to worklist.
503 VRegInfo &Info = VRegInfos[RegIdx];
504 Info.DefinedLanes = determineInitialDefinedLanes(Reg);
505 Info.UsedLanes = determineInitialUsedLanes(Reg);
508 // Iterate as long as defined lanes/used lanes keep changing.
509 while (!Worklist.empty()) {
510 unsigned RegIdx = Worklist.front();
511 Worklist.pop_front();
512 WorklistMembers.reset(RegIdx);
513 VRegInfo &Info = VRegInfos[RegIdx];
514 unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
516 // Transfer UsedLanes to operands of DefMI (backwards dataflow).
517 MachineOperand &Def = *MRI->def_begin(Reg);
518 const MachineInstr &MI = *Def.getParent();
519 transferUsedLanesStep(MI, Info.UsedLanes);
520 // Transfer DefinedLanes to users of Reg (forward dataflow).
521 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg))
522 transferDefinedLanesStep(MO, Info.DefinedLanes);
526 dbgs() << "Defined/Used lanes:\n";
527 for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
528 unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
529 const VRegInfo &Info = VRegInfos[RegIdx];
530 dbgs() << PrintReg(Reg, nullptr)
531 << " Used: " << PrintLaneMask(Info.UsedLanes)
532 << " Def: " << PrintLaneMask(Info.DefinedLanes) << '\n';
538 // Mark operands as dead/unused.
539 for (MachineBasicBlock &MBB : MF) {
540 for (MachineInstr &MI : MBB) {
541 for (MachineOperand &MO : MI.operands()) {
544 unsigned Reg = MO.getReg();
545 if (!TargetRegisterInfo::isVirtualRegister(Reg))
547 unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
548 const VRegInfo &RegInfo = VRegInfos[RegIdx];
549 if (MO.isDef() && !MO.isDead() && RegInfo.UsedLanes.none()) {
550 DEBUG(dbgs() << "Marking operand '" << MO << "' as dead in " << MI);
554 bool CrossCopy = false;
555 if (isUndefRegAtInput(MO, RegInfo)) {
556 DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in "
559 } else if (isUndefInput(MO, &CrossCopy)) {
560 DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in "
574 bool DetectDeadLanes::runOnMachineFunction(MachineFunction &MF) {
575 // Don't bother if we won't track subregister liveness later. This pass is
576 // required for correctness if subregister liveness is enabled because the
577 // register coalescer cannot deal with hidden dead defs. However without
578 // subregister liveness enabled, the expected benefits of this pass are small
579 // so we safe the compile time.
580 MRI = &MF.getRegInfo();
581 if (!MRI->subRegLivenessEnabled()) {
582 DEBUG(dbgs() << "Skipping Detect dead lanes pass\n");
586 TRI = MRI->getTargetRegisterInfo();
588 unsigned NumVirtRegs = MRI->getNumVirtRegs();
589 VRegInfos = new VRegInfo[NumVirtRegs];
590 WorklistMembers.resize(NumVirtRegs);
591 DefinedByCopy.resize(NumVirtRegs);
598 DefinedByCopy.clear();
599 WorklistMembers.clear();