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, DEBUG_TYPE, "Detect Dead Lanes", false, false)
137 /// Returns true if \p MI will get lowered to a series of COPY instructions.
138 /// We call this a COPY-like instruction.
139 static bool lowersToCopies(const MachineInstr &MI) {
140 // Note: We could support instructions with MCInstrDesc::isRegSequenceLike(),
141 // isExtractSubRegLike(), isInsertSubregLike() in the future even though they
142 // are not lowered to a COPY.
143 switch (MI.getOpcode()) {
144 case TargetOpcode::COPY:
145 case TargetOpcode::PHI:
146 case TargetOpcode::INSERT_SUBREG:
147 case TargetOpcode::REG_SEQUENCE:
148 case TargetOpcode::EXTRACT_SUBREG:
154 static bool isCrossCopy(const MachineRegisterInfo &MRI,
155 const MachineInstr &MI,
156 const TargetRegisterClass *DstRC,
157 const MachineOperand &MO) {
158 assert(lowersToCopies(MI));
159 unsigned SrcReg = MO.getReg();
160 const TargetRegisterClass *SrcRC = MRI.getRegClass(SrcReg);
164 unsigned SrcSubIdx = MO.getSubReg();
166 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
167 unsigned DstSubIdx = 0;
168 switch (MI.getOpcode()) {
169 case TargetOpcode::INSERT_SUBREG:
170 if (MI.getOperandNo(&MO) == 2)
171 DstSubIdx = MI.getOperand(3).getImm();
173 case TargetOpcode::REG_SEQUENCE: {
174 unsigned OpNum = MI.getOperandNo(&MO);
175 DstSubIdx = MI.getOperand(OpNum+1).getImm();
178 case TargetOpcode::EXTRACT_SUBREG: {
179 unsigned SubReg = MI.getOperand(2).getImm();
180 SrcSubIdx = TRI.composeSubRegIndices(SubReg, SrcSubIdx);
184 unsigned PreA, PreB; // Unused.
185 if (SrcSubIdx && DstSubIdx)
186 return !TRI.getCommonSuperRegClass(SrcRC, SrcSubIdx, DstRC, DstSubIdx, PreA,
189 return !TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSubIdx);
191 return !TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSubIdx);
192 return !TRI.getCommonSubClass(SrcRC, DstRC);
195 void DetectDeadLanes::addUsedLanesOnOperand(const MachineOperand &MO,
196 LaneBitmask UsedLanes) {
199 unsigned MOReg = MO.getReg();
200 if (!TargetRegisterInfo::isVirtualRegister(MOReg))
203 unsigned MOSubReg = MO.getSubReg();
205 UsedLanes = TRI->composeSubRegIndexLaneMask(MOSubReg, UsedLanes);
206 UsedLanes &= MRI->getMaxLaneMaskForVReg(MOReg);
208 unsigned MORegIdx = TargetRegisterInfo::virtReg2Index(MOReg);
209 VRegInfo &MORegInfo = VRegInfos[MORegIdx];
210 LaneBitmask PrevUsedLanes = MORegInfo.UsedLanes;
211 // Any change at all?
212 if ((UsedLanes & ~PrevUsedLanes).none())
215 // Set UsedLanes and remember instruction for further propagation.
216 MORegInfo.UsedLanes = PrevUsedLanes | UsedLanes;
217 if (DefinedByCopy.test(MORegIdx))
218 PutInWorklist(MORegIdx);
221 void DetectDeadLanes::transferUsedLanesStep(const MachineInstr &MI,
222 LaneBitmask UsedLanes) {
223 for (const MachineOperand &MO : MI.uses()) {
224 if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
226 LaneBitmask UsedOnMO = transferUsedLanes(MI, UsedLanes, MO);
227 addUsedLanesOnOperand(MO, UsedOnMO);
231 LaneBitmask DetectDeadLanes::transferUsedLanes(const MachineInstr &MI,
232 LaneBitmask UsedLanes,
233 const MachineOperand &MO) const {
234 unsigned OpNum = MI.getOperandNo(&MO);
235 assert(lowersToCopies(MI) && DefinedByCopy[
236 TargetRegisterInfo::virtReg2Index(MI.getOperand(0).getReg())]);
238 switch (MI.getOpcode()) {
239 case TargetOpcode::COPY:
240 case TargetOpcode::PHI:
242 case TargetOpcode::REG_SEQUENCE: {
243 assert(OpNum % 2 == 1);
244 unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
245 return TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
247 case TargetOpcode::INSERT_SUBREG: {
248 unsigned SubIdx = MI.getOperand(3).getImm();
249 LaneBitmask MO2UsedLanes =
250 TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
254 const MachineOperand &Def = MI.getOperand(0);
255 unsigned DefReg = Def.getReg();
256 const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
257 LaneBitmask MO1UsedLanes;
258 if (RC->CoveredBySubRegs)
259 MO1UsedLanes = UsedLanes & ~TRI->getSubRegIndexLaneMask(SubIdx);
261 MO1UsedLanes = RC->LaneMask;
266 case TargetOpcode::EXTRACT_SUBREG: {
268 unsigned SubIdx = MI.getOperand(2).getImm();
269 return TRI->composeSubRegIndexLaneMask(SubIdx, UsedLanes);
272 llvm_unreachable("function must be called with COPY-like instruction");
276 void DetectDeadLanes::transferDefinedLanesStep(const MachineOperand &Use,
277 LaneBitmask DefinedLanes) {
280 // Check whether the operand writes a vreg and is part of a COPY-like
282 const MachineInstr &MI = *Use.getParent();
283 if (MI.getDesc().getNumDefs() != 1)
285 // FIXME: PATCHPOINT instructions announce a Def that does not always exist,
286 // they really need to be modeled differently!
287 if (MI.getOpcode() == TargetOpcode::PATCHPOINT)
289 const MachineOperand &Def = *MI.defs().begin();
290 unsigned DefReg = Def.getReg();
291 if (!TargetRegisterInfo::isVirtualRegister(DefReg))
293 unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
294 if (!DefinedByCopy.test(DefRegIdx))
297 unsigned OpNum = MI.getOperandNo(&Use);
299 TRI->reverseComposeSubRegIndexLaneMask(Use.getSubReg(), DefinedLanes);
300 DefinedLanes = transferDefinedLanes(Def, OpNum, DefinedLanes);
302 VRegInfo &RegInfo = VRegInfos[DefRegIdx];
303 LaneBitmask PrevDefinedLanes = RegInfo.DefinedLanes;
304 // Any change at all?
305 if ((DefinedLanes & ~PrevDefinedLanes).none())
308 RegInfo.DefinedLanes = PrevDefinedLanes | DefinedLanes;
309 PutInWorklist(DefRegIdx);
312 LaneBitmask DetectDeadLanes::transferDefinedLanes(const MachineOperand &Def,
313 unsigned OpNum, LaneBitmask DefinedLanes) const {
314 const MachineInstr &MI = *Def.getParent();
315 // Translate DefinedLanes if necessary.
316 switch (MI.getOpcode()) {
317 case TargetOpcode::REG_SEQUENCE: {
318 unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
319 DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
320 DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
323 case TargetOpcode::INSERT_SUBREG: {
324 unsigned SubIdx = MI.getOperand(3).getImm();
326 DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
327 DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
329 assert(OpNum == 1 && "INSERT_SUBREG must have two operands");
330 // Ignore lanes defined by operand 2.
331 DefinedLanes &= ~TRI->getSubRegIndexLaneMask(SubIdx);
335 case TargetOpcode::EXTRACT_SUBREG: {
336 unsigned SubIdx = MI.getOperand(2).getImm();
337 assert(OpNum == 1 && "EXTRACT_SUBREG must have one register operand only");
338 DefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(SubIdx, DefinedLanes);
341 case TargetOpcode::COPY:
342 case TargetOpcode::PHI:
345 llvm_unreachable("function must be called with COPY-like instruction");
348 assert(Def.getSubReg() == 0 &&
349 "Should not have subregister defs in machine SSA phase");
350 DefinedLanes &= MRI->getMaxLaneMaskForVReg(Def.getReg());
354 LaneBitmask DetectDeadLanes::determineInitialDefinedLanes(unsigned Reg) {
355 // Live-In or unused registers have no definition but are considered fully
357 if (!MRI->hasOneDef(Reg))
358 return LaneBitmask::getAll();
360 const MachineOperand &Def = *MRI->def_begin(Reg);
361 const MachineInstr &DefMI = *Def.getParent();
362 if (lowersToCopies(DefMI)) {
363 // Start optimisatically with no used or defined lanes for copy
364 // instructions. The following dataflow analysis will add more bits.
365 unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
366 DefinedByCopy.set(RegIdx);
367 PutInWorklist(RegIdx);
370 return LaneBitmask::getNone();
372 // COPY/PHI can copy across unrelated register classes (example: float/int)
373 // with incompatible subregister structure. Do not include these in the
374 // dataflow analysis since we cannot transfer lanemasks in a meaningful way.
375 const TargetRegisterClass *DefRC = MRI->getRegClass(Reg);
377 // Determine initially DefinedLanes.
378 LaneBitmask DefinedLanes;
379 for (const MachineOperand &MO : DefMI.uses()) {
380 if (!MO.isReg() || !MO.readsReg())
382 unsigned MOReg = MO.getReg();
386 LaneBitmask MODefinedLanes;
387 if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
388 MODefinedLanes = LaneBitmask::getAll();
389 } else if (isCrossCopy(*MRI, DefMI, DefRC, MO)) {
390 MODefinedLanes = LaneBitmask::getAll();
392 assert(TargetRegisterInfo::isVirtualRegister(MOReg));
393 if (MRI->hasOneDef(MOReg)) {
394 const MachineOperand &MODef = *MRI->def_begin(MOReg);
395 const MachineInstr &MODefMI = *MODef.getParent();
396 // Bits from copy-like operations will be added later.
397 if (lowersToCopies(MODefMI) || MODefMI.isImplicitDef())
400 unsigned MOSubReg = MO.getSubReg();
401 MODefinedLanes = MRI->getMaxLaneMaskForVReg(MOReg);
402 MODefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(
403 MOSubReg, MODefinedLanes);
406 unsigned OpNum = DefMI.getOperandNo(&MO);
407 DefinedLanes |= transferDefinedLanes(Def, OpNum, MODefinedLanes);
411 if (DefMI.isImplicitDef() || Def.isDead())
412 return LaneBitmask::getNone();
414 assert(Def.getSubReg() == 0 &&
415 "Should not have subregister defs in machine SSA phase");
416 return MRI->getMaxLaneMaskForVReg(Reg);
419 LaneBitmask DetectDeadLanes::determineInitialUsedLanes(unsigned Reg) {
420 LaneBitmask UsedLanes = LaneBitmask::getNone();
421 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
425 const MachineInstr &UseMI = *MO.getParent();
429 unsigned SubReg = MO.getSubReg();
430 if (lowersToCopies(UseMI)) {
431 assert(UseMI.getDesc().getNumDefs() == 1);
432 const MachineOperand &Def = *UseMI.defs().begin();
433 unsigned DefReg = Def.getReg();
434 // The used lanes of COPY-like instruction operands are determined by the
435 // following dataflow analysis.
436 if (TargetRegisterInfo::isVirtualRegister(DefReg)) {
437 // But ignore copies across incompatible register classes.
438 bool CrossCopy = false;
439 if (lowersToCopies(UseMI)) {
440 const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
441 CrossCopy = isCrossCopy(*MRI, UseMI, DstRC, MO);
443 DEBUG(dbgs() << "Copy across incompatible classes: " << UseMI);
451 // Shortcut: All lanes are used.
453 return MRI->getMaxLaneMaskForVReg(Reg);
455 UsedLanes |= TRI->getSubRegIndexLaneMask(SubReg);
460 bool DetectDeadLanes::isUndefRegAtInput(const MachineOperand &MO,
461 const VRegInfo &RegInfo) const {
462 unsigned SubReg = MO.getSubReg();
463 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
464 return (RegInfo.DefinedLanes & RegInfo.UsedLanes & Mask).none();
467 bool DetectDeadLanes::isUndefInput(const MachineOperand &MO,
468 bool *CrossCopy) const {
471 const MachineInstr &MI = *MO.getParent();
472 if (!lowersToCopies(MI))
474 const MachineOperand &Def = MI.getOperand(0);
475 unsigned DefReg = Def.getReg();
476 if (!TargetRegisterInfo::isVirtualRegister(DefReg))
478 unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
479 if (!DefinedByCopy.test(DefRegIdx))
482 const VRegInfo &DefRegInfo = VRegInfos[DefRegIdx];
483 LaneBitmask UsedLanes = transferUsedLanes(MI, DefRegInfo.UsedLanes, MO);
487 unsigned MOReg = MO.getReg();
488 if (TargetRegisterInfo::isVirtualRegister(MOReg)) {
489 const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
490 *CrossCopy = isCrossCopy(*MRI, MI, DstRC, MO);
495 bool DetectDeadLanes::runOnce(MachineFunction &MF) {
496 // First pass: Populate defs/uses of vregs with initial values
497 unsigned NumVirtRegs = MRI->getNumVirtRegs();
498 for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
499 unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
501 // Determine used/defined lanes and add copy instructions to worklist.
502 VRegInfo &Info = VRegInfos[RegIdx];
503 Info.DefinedLanes = determineInitialDefinedLanes(Reg);
504 Info.UsedLanes = determineInitialUsedLanes(Reg);
507 // Iterate as long as defined lanes/used lanes keep changing.
508 while (!Worklist.empty()) {
509 unsigned RegIdx = Worklist.front();
510 Worklist.pop_front();
511 WorklistMembers.reset(RegIdx);
512 VRegInfo &Info = VRegInfos[RegIdx];
513 unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
515 // Transfer UsedLanes to operands of DefMI (backwards dataflow).
516 MachineOperand &Def = *MRI->def_begin(Reg);
517 const MachineInstr &MI = *Def.getParent();
518 transferUsedLanesStep(MI, Info.UsedLanes);
519 // Transfer DefinedLanes to users of Reg (forward dataflow).
520 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg))
521 transferDefinedLanesStep(MO, Info.DefinedLanes);
525 dbgs() << "Defined/Used lanes:\n";
526 for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
527 unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
528 const VRegInfo &Info = VRegInfos[RegIdx];
529 dbgs() << PrintReg(Reg, nullptr)
530 << " Used: " << PrintLaneMask(Info.UsedLanes)
531 << " Def: " << PrintLaneMask(Info.DefinedLanes) << '\n';
537 // Mark operands as dead/unused.
538 for (MachineBasicBlock &MBB : MF) {
539 for (MachineInstr &MI : MBB) {
540 for (MachineOperand &MO : MI.operands()) {
543 unsigned Reg = MO.getReg();
544 if (!TargetRegisterInfo::isVirtualRegister(Reg))
546 unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
547 const VRegInfo &RegInfo = VRegInfos[RegIdx];
548 if (MO.isDef() && !MO.isDead() && RegInfo.UsedLanes.none()) {
549 DEBUG(dbgs() << "Marking operand '" << MO << "' as dead in " << MI);
553 bool CrossCopy = false;
554 if (isUndefRegAtInput(MO, RegInfo)) {
555 DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in "
558 } else if (isUndefInput(MO, &CrossCopy)) {
559 DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in "
573 bool DetectDeadLanes::runOnMachineFunction(MachineFunction &MF) {
574 // Don't bother if we won't track subregister liveness later. This pass is
575 // required for correctness if subregister liveness is enabled because the
576 // register coalescer cannot deal with hidden dead defs. However without
577 // subregister liveness enabled, the expected benefits of this pass are small
578 // so we safe the compile time.
579 MRI = &MF.getRegInfo();
580 if (!MRI->subRegLivenessEnabled()) {
581 DEBUG(dbgs() << "Skipping Detect dead lanes pass\n");
585 TRI = MRI->getTargetRegisterInfo();
587 unsigned NumVirtRegs = MRI->getNumVirtRegs();
588 VRegInfos = new VRegInfo[NumVirtRegs];
589 WorklistMembers.resize(NumVirtRegs);
590 DefinedByCopy.resize(NumVirtRegs);
597 DefinedByCopy.clear();
598 WorklistMembers.clear();