1 //===- DetectDeadLanes.cpp - SubRegister Lane Usage Analysis --*- C++ -*---===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file
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.
18 ///
19 /// Example:
20 ///    %vreg0 = some definition
21 ///    %vreg1 = IMPLICIT_DEF
22 ///    %vreg2 = REG_SEQUENCE %vreg0, sub0, %vreg1, sub1
23 ///    %vreg3 = EXTRACT_SUBREG %vreg2, sub1
24 ///           = use %vreg3
25 /// The %vreg0 definition is dead and %vreg3 contains an undefined value.
26 //
27 //===----------------------------------------------------------------------===//
28 
29 #include <deque>
30 #include <vector>
31 
32 #include "llvm/ADT/BitVector.h"
33 #include "llvm/CodeGen/MachineFunctionPass.h"
34 #include "llvm/CodeGen/MachineRegisterInfo.h"
35 #include "llvm/CodeGen/Passes.h"
36 #include "llvm/InitializePasses.h"
37 #include "llvm/Pass.h"
38 #include "llvm/PassRegistry.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/raw_ostream.h"
41 #include "llvm/Target/TargetInstrInfo.h"
42 #include "llvm/Target/TargetRegisterInfo.h"
43 #include "llvm/Target/TargetSubtargetInfo.h"
44 
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "detect-dead-lanes"
48 
49 namespace {
50 
51 /// Contains a bitmask of which lanes of a given virtual register are
52 /// defined and which ones are actually used.
53 struct VRegInfo {
54   LaneBitmask UsedLanes;
55   LaneBitmask DefinedLanes;
56 };
57 
58 class DetectDeadLanes : public MachineFunctionPass {
59 public:
60   bool runOnMachineFunction(MachineFunction &MF) override;
61 
62   static char ID;
63   DetectDeadLanes() : MachineFunctionPass(ID) {}
64 
65   const char *getPassName() const override { return "Detect Dead Lanes"; }
66 
67 private:
68   /// Add used lane bits on the register used by operand \p MO. This translates
69   /// the bitmask based on the operands subregister, and puts the register into
70   /// the worklist if any new bits were added.
71   void addUsedLanesOnOperand(const MachineOperand &MO, LaneBitmask UsedLanes);
72 
73   /// Given a bitmask \p UsedLanes for the used lanes on a def output of a
74   /// COPY-like instruction determine the lanes used on the use operands
75   /// and call addUsedLanesOnOperand() for them.
76   void transferUsedLanesStep(const MachineOperand &Def, LaneBitmask UsedLanes);
77 
78   /// Given a use regiser operand \p Use and a mask of defined lanes, check
79   /// if the operand belongs to a lowerToCopies() instruction, transfer the
80   /// mask to the def and put the instruction into the worklist.
81   void transferDefinedLanesStep(const MachineOperand &Use,
82                                 LaneBitmask DefinedLanes);
83 
84   /// Given a mask \p DefinedLanes of lanes defined at operand \p OpNum
85   /// of COPY-like instruction, determine which lanes are defined at the output
86   /// operand \p Def.
87   LaneBitmask transferDefinedLanes(const MachineOperand &Def, unsigned OpNum,
88                                    LaneBitmask DefinedLanes);
89 
90   LaneBitmask determineInitialDefinedLanes(unsigned Reg);
91   LaneBitmask determineInitialUsedLanes(unsigned Reg);
92 
93   const MachineRegisterInfo *MRI;
94   const TargetRegisterInfo *TRI;
95 
96   void PutInWorklist(unsigned RegIdx) {
97     if (WorklistMembers.test(RegIdx))
98       return;
99     WorklistMembers.set(RegIdx);
100     Worklist.push_back(RegIdx);
101   }
102 
103   VRegInfo *VRegInfos;
104   /// Worklist containing virtreg indexes.
105   std::deque<unsigned> Worklist;
106   BitVector WorklistMembers;
107   /// This bitvector is set for each vreg index where the vreg is defined
108   /// by an instruction where lowersToCopies()==true.
109   BitVector DefinedByCopy;
110 };
111 
112 } // end anonymous namespace
113 
114 char DetectDeadLanes::ID = 0;
115 char &llvm::DetectDeadLanesID = DetectDeadLanes::ID;
116 
117 INITIALIZE_PASS(DetectDeadLanes, "detect-dead-lanes", "Detect Dead Lanes",
118                 false, false)
119 
120 /// Returns true if \p MI will get lowered to a series of COPY instructions.
121 /// We call this a COPY-like instruction.
122 static bool lowersToCopies(const MachineInstr &MI) {
123   // Note: We could support instructions with MCInstrDesc::isRegSequenceLike(),
124   // isExtractSubRegLike(), isInsertSubregLike() in the future even though they
125   // are not lowered to a COPY.
126   switch (MI.getOpcode()) {
127   case TargetOpcode::COPY:
128   case TargetOpcode::PHI:
129   case TargetOpcode::INSERT_SUBREG:
130   case TargetOpcode::REG_SEQUENCE:
131   case TargetOpcode::EXTRACT_SUBREG:
132     return true;
133   }
134   return false;
135 }
136 
137 static bool isCrossCopy(const MachineRegisterInfo &MRI,
138                         const MachineInstr &MI,
139                         const TargetRegisterClass *DstRC,
140                         const MachineOperand &MO) {
141   assert(lowersToCopies(MI));
142   unsigned SrcReg = MO.getReg();
143   const TargetRegisterClass *SrcRC = MRI.getRegClass(SrcReg);
144   if (DstRC == SrcRC)
145     return false;
146 
147   unsigned SrcSubIdx = MO.getSubReg();
148 
149   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
150   unsigned DstSubIdx = 0;
151   switch (MI.getOpcode()) {
152   case TargetOpcode::INSERT_SUBREG:
153     if (MI.getOperandNo(&MO) == 2)
154       DstSubIdx = MI.getOperand(3).getImm();
155     break;
156   case TargetOpcode::REG_SEQUENCE: {
157     unsigned OpNum = MI.getOperandNo(&MO);
158     DstSubIdx = MI.getOperand(OpNum+1).getImm();
159     break;
160   }
161   case TargetOpcode::EXTRACT_SUBREG: {
162     unsigned SubReg = MI.getOperand(2).getImm();
163     SrcSubIdx = TRI.composeSubRegIndices(SubReg, SrcSubIdx);
164   }
165   }
166 
167   unsigned PreA, PreB; // Unused.
168   if (SrcSubIdx && DstSubIdx)
169     return !TRI.getCommonSuperRegClass(SrcRC, SrcSubIdx, DstRC, DstSubIdx, PreA,
170                                        PreB);
171   if (SrcSubIdx)
172     return !TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSubIdx);
173   if (DstSubIdx)
174     return !TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSubIdx);
175   return !TRI.getCommonSubClass(SrcRC, DstRC);
176 }
177 
178 void DetectDeadLanes::addUsedLanesOnOperand(const MachineOperand &MO,
179                                             LaneBitmask UsedLanes) {
180   if (!MO.readsReg())
181     return;
182   unsigned MOReg = MO.getReg();
183   if (!TargetRegisterInfo::isVirtualRegister(MOReg))
184     return;
185 
186   unsigned MOSubReg = MO.getSubReg();
187   if (MOSubReg != 0)
188     UsedLanes = TRI->composeSubRegIndexLaneMask(MOSubReg, UsedLanes);
189   UsedLanes &= MRI->getMaxLaneMaskForVReg(MOReg);
190 
191   unsigned MORegIdx = TargetRegisterInfo::virtReg2Index(MOReg);
192   VRegInfo &MORegInfo = VRegInfos[MORegIdx];
193   LaneBitmask PrevUsedLanes = MORegInfo.UsedLanes;
194   // Any change at all?
195   if ((UsedLanes & ~PrevUsedLanes) == 0)
196     return;
197 
198   // Set UsedLanes and remember instruction for further propagation.
199   MORegInfo.UsedLanes = PrevUsedLanes | UsedLanes;
200   if (DefinedByCopy.test(MORegIdx))
201     PutInWorklist(MORegIdx);
202 }
203 
204 void DetectDeadLanes::transferUsedLanesStep(const MachineOperand &Def,
205                                             LaneBitmask UsedLanes) {
206   const MachineInstr &MI = *Def.getParent();
207   switch (MI.getOpcode()) {
208   case TargetOpcode::COPY:
209   case TargetOpcode::PHI:
210     for (const MachineOperand &MO : MI.uses()) {
211       if (MO.isReg() && MO.isUse())
212         addUsedLanesOnOperand(MO, UsedLanes);
213     }
214     break;
215   case TargetOpcode::REG_SEQUENCE: {
216     // Note: This loop makes the conservative assumption that subregister
217     // indices do not overlap or that we do not know how the overlap is
218     // resolved when lowering to copies.
219     for (unsigned I = 1, N = MI.getNumOperands(); I < N; I += 2) {
220       const MachineOperand &MO = MI.getOperand(I);
221       unsigned SubIdx = MI.getOperand(I + 1).getImm();
222       LaneBitmask MOUsedLanes =
223           TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
224 
225       addUsedLanesOnOperand(MO, MOUsedLanes);
226     }
227     break;
228   }
229   case TargetOpcode::INSERT_SUBREG: {
230     const MachineOperand &MO2 = MI.getOperand(2);
231     unsigned SubIdx = MI.getOperand(3).getImm();
232     LaneBitmask MO2UsedLanes =
233         TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
234     addUsedLanesOnOperand(MO2, MO2UsedLanes);
235 
236     const MachineOperand &MO1 = MI.getOperand(1);
237     unsigned DefReg = Def.getReg();
238     const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
239     LaneBitmask MO1UsedLanes;
240     if (RC->CoveredBySubRegs)
241       MO1UsedLanes = UsedLanes & ~TRI->getSubRegIndexLaneMask(SubIdx);
242     else
243       MO1UsedLanes = RC->LaneMask;
244     addUsedLanesOnOperand(MO1, MO1UsedLanes);
245     break;
246   }
247   case TargetOpcode::EXTRACT_SUBREG: {
248     const MachineOperand &MO = MI.getOperand(1);
249     unsigned SubIdx = MI.getOperand(2).getImm();
250     LaneBitmask MOUsedLanes =
251         TRI->composeSubRegIndexLaneMask(SubIdx, UsedLanes);
252     addUsedLanesOnOperand(MO, MOUsedLanes);
253     break;
254   }
255   default:
256     llvm_unreachable("function must be called with COPY-like instruction");
257   }
258 }
259 
260 void DetectDeadLanes::transferDefinedLanesStep(const MachineOperand &Use,
261                                                LaneBitmask DefinedLanes) {
262   if (!Use.readsReg())
263     return;
264   // Check whether the operand writes a vreg and is part of a COPY-like
265   // instruction.
266   const MachineInstr &MI = *Use.getParent();
267   if (MI.getDesc().getNumDefs() != 1)
268     return;
269   // FIXME: PATCHPOINT instructions announce a Def that does not always exist,
270   // they really need to be modeled differently!
271   if (MI.getOpcode() == TargetOpcode::PATCHPOINT)
272     return;
273   const MachineOperand &Def = *MI.defs().begin();
274   unsigned DefReg = Def.getReg();
275   if (!TargetRegisterInfo::isVirtualRegister(DefReg))
276     return;
277   unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
278   if (!DefinedByCopy.test(DefRegIdx))
279     return;
280 
281   unsigned OpNum = MI.getOperandNo(&Use);
282   DefinedLanes =
283       TRI->reverseComposeSubRegIndexLaneMask(Use.getSubReg(), DefinedLanes);
284   DefinedLanes = transferDefinedLanes(Def, OpNum, DefinedLanes);
285 
286   VRegInfo &RegInfo = VRegInfos[DefRegIdx];
287   LaneBitmask PrevDefinedLanes = RegInfo.DefinedLanes;
288   // Any change at all?
289   if ((DefinedLanes & ~PrevDefinedLanes) == 0)
290     return;
291 
292   RegInfo.DefinedLanes = PrevDefinedLanes | DefinedLanes;
293   PutInWorklist(DefRegIdx);
294 }
295 
296 LaneBitmask DetectDeadLanes::transferDefinedLanes(const MachineOperand &Def,
297                                                   unsigned OpNum,
298                                                   LaneBitmask DefinedLanes) {
299   const MachineInstr &MI = *Def.getParent();
300   // Translate DefinedLanes if necessary.
301   switch (MI.getOpcode()) {
302   case TargetOpcode::REG_SEQUENCE: {
303     unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
304     DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
305     DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
306     break;
307   }
308   case TargetOpcode::INSERT_SUBREG: {
309     unsigned SubIdx = MI.getOperand(3).getImm();
310     if (OpNum == 2) {
311       DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
312       DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
313     } else {
314       assert(OpNum == 1 && "INSERT_SUBREG must have two operands");
315       // Ignore lanes defined by operand 2.
316       DefinedLanes &= ~TRI->getSubRegIndexLaneMask(SubIdx);
317     }
318     break;
319   }
320   case TargetOpcode::EXTRACT_SUBREG: {
321     unsigned SubIdx = MI.getOperand(2).getImm();
322     assert(OpNum == 1 && "EXTRACT_SUBREG must have one register operand only");
323     DefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(SubIdx, DefinedLanes);
324     break;
325   }
326   case TargetOpcode::COPY:
327   case TargetOpcode::PHI:
328     break;
329   default:
330     llvm_unreachable("function must be called with COPY-like instruction");
331   }
332 
333   unsigned SubIdx = Def.getSubReg();
334   DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
335   DefinedLanes &= MRI->getMaxLaneMaskForVReg(Def.getReg());
336   return DefinedLanes;
337 }
338 
339 LaneBitmask DetectDeadLanes::determineInitialDefinedLanes(unsigned Reg) {
340   // Live-In or unused registers have no definition but are considered fully
341   // defined.
342   if (!MRI->hasOneDef(Reg))
343     return ~0u;
344 
345   const MachineOperand &Def = *MRI->def_begin(Reg);
346   const MachineInstr &DefMI = *Def.getParent();
347   if (lowersToCopies(DefMI)) {
348     // Start optimisatically with no used or defined lanes for copy
349     // instructions. The following dataflow analysis will add more bits.
350     unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
351     DefinedByCopy.set(RegIdx);
352     PutInWorklist(RegIdx);
353 
354     if (Def.isDead())
355       return 0;
356 
357     // COPY/PHI can copy across unrelated register classes (example: float/int)
358     // with incompatible subregister structure. Do not include these in the
359     // dataflow analysis since we cannot transfer lanemasks in a meaningful way.
360     const TargetRegisterClass *DefRC = MRI->getRegClass(Reg);
361 
362     // Determine initially DefinedLanes.
363     LaneBitmask DefinedLanes = 0;
364     for (const MachineOperand &MO : DefMI.uses()) {
365       if (!MO.isReg() || !MO.readsReg())
366         continue;
367       unsigned MOReg = MO.getReg();
368       if (!MOReg)
369         continue;
370 
371       LaneBitmask MODefinedLanes;
372       if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
373         MODefinedLanes = ~0u;
374       } else if (isCrossCopy(*MRI, DefMI, DefRC, MO)) {
375         MODefinedLanes = ~0u;
376       } else {
377         assert(TargetRegisterInfo::isVirtualRegister(MOReg));
378         if (MRI->hasOneDef(MOReg)) {
379           const MachineOperand &MODef = *MRI->def_begin(MOReg);
380           const MachineInstr &MODefMI = *MODef.getParent();
381           // Bits from copy-like operations will be added later.
382           if (lowersToCopies(MODefMI) || MODefMI.isImplicitDef())
383             continue;
384         }
385         unsigned MOSubReg = MO.getSubReg();
386         MODefinedLanes = MRI->getMaxLaneMaskForVReg(MOReg);
387         MODefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(
388             MOSubReg, MODefinedLanes);
389       }
390 
391       unsigned OpNum = DefMI.getOperandNo(&MO);
392       DefinedLanes |= transferDefinedLanes(Def, OpNum, MODefinedLanes);
393     }
394     return DefinedLanes;
395   }
396   if (DefMI.isImplicitDef() || Def.isDead())
397     return 0;
398 
399   unsigned SubReg = Def.getSubReg();
400   return SubReg != 0 ? TRI->getSubRegIndexLaneMask(SubReg)
401                      : MRI->getMaxLaneMaskForVReg(Reg);
402 }
403 
404 LaneBitmask DetectDeadLanes::determineInitialUsedLanes(unsigned Reg) {
405   LaneBitmask UsedLanes = 0;
406   for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
407     if (!MO.readsReg())
408       continue;
409 
410     const MachineInstr &UseMI = *MO.getParent();
411     if (UseMI.isKill())
412       continue;
413 
414     unsigned SubReg = MO.getSubReg();
415     if (lowersToCopies(UseMI)) {
416       assert(UseMI.getDesc().getNumDefs() == 1);
417       const MachineOperand &Def = *UseMI.defs().begin();
418       unsigned DefReg = Def.getReg();
419       // The used lanes of COPY-like instruction operands are determined by the
420       // following dataflow analysis.
421       if (TargetRegisterInfo::isVirtualRegister(DefReg)) {
422         // But ignore copies across incompatible register classes.
423         bool CrossCopy = false;
424         if (lowersToCopies(UseMI)) {
425           const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
426           CrossCopy = isCrossCopy(*MRI, UseMI, DstRC, MO);
427         }
428 
429         if (!CrossCopy)
430           continue;
431       }
432     }
433 
434     // Shortcut: All lanes are used.
435     if (SubReg == 0)
436       return MRI->getMaxLaneMaskForVReg(Reg);
437 
438     UsedLanes |= TRI->getSubRegIndexLaneMask(SubReg);
439   }
440   return UsedLanes;
441 }
442 
443 bool DetectDeadLanes::runOnMachineFunction(MachineFunction &MF) {
444   // Don't bother if we won't track subregister liveness later.  This pass is
445   // required for correctness if subregister liveness is enabled because the
446   // register coalescer cannot deal with hidden dead defs. However without
447   // subregister liveness enabled, the expected benefits of this pass are small
448   // so we safe the compile time.
449   if (!MF.getSubtarget().enableSubRegLiveness()) {
450     DEBUG(dbgs() << "Skipping Detect dead lanes pass\n");
451     return false;
452   }
453 
454   MRI = &MF.getRegInfo();
455   TRI = MRI->getTargetRegisterInfo();
456 
457   unsigned NumVirtRegs = MRI->getNumVirtRegs();
458   VRegInfos = new VRegInfo[NumVirtRegs];
459   WorklistMembers.resize(NumVirtRegs);
460   DefinedByCopy.resize(NumVirtRegs);
461 
462   // First pass: Populate defs/uses of vregs with initial values
463   for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
464     unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
465 
466     // Determine used/defined lanes and add copy instructions to worklist.
467     VRegInfo &Info = VRegInfos[RegIdx];
468     Info.DefinedLanes = determineInitialDefinedLanes(Reg);
469     Info.UsedLanes = determineInitialUsedLanes(Reg);
470   }
471 
472   // Iterate as long as defined lanes/used lanes keep changing.
473   while (!Worklist.empty()) {
474     unsigned RegIdx = Worklist.front();
475     Worklist.pop_front();
476     WorklistMembers.reset(RegIdx);
477     VRegInfo &Info = VRegInfos[RegIdx];
478     unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
479 
480     // Transfer UsedLanes to operands of DefMI (backwards dataflow).
481     MachineOperand &Def = *MRI->def_begin(Reg);
482     transferUsedLanesStep(Def, Info.UsedLanes);
483     // Transfer DefinedLanes to users of Reg (forward dataflow).
484     for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg))
485       transferDefinedLanesStep(MO, Info.DefinedLanes);
486   }
487 
488   DEBUG(
489     dbgs() << "Defined/Used lanes:\n";
490     for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
491       unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
492       const VRegInfo &Info = VRegInfos[RegIdx];
493       dbgs() << PrintReg(Reg, nullptr)
494              << " Used: " << PrintLaneMask(Info.UsedLanes)
495              << " Def: " << PrintLaneMask(Info.DefinedLanes) << '\n';
496     }
497     dbgs() << "\n";
498   );
499 
500   // Mark operands as dead/unused.
501   for (MachineBasicBlock &MBB : MF) {
502     for (MachineInstr &MI : MBB) {
503       for (MachineOperand &MO : MI.operands()) {
504         if (!MO.isReg())
505           continue;
506         unsigned Reg = MO.getReg();
507         if (!TargetRegisterInfo::isVirtualRegister(Reg))
508           continue;
509         unsigned SubReg = MO.getSubReg();
510         LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
511         unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
512         const VRegInfo &RegInfo = VRegInfos[RegIdx];
513         if (RegInfo.UsedLanes == 0 && MO.isDef() && !MO.isDead()) {
514           DEBUG(dbgs() << "Marking operand '" << MO << "' as dead in " << MI);
515           MO.setIsDead();
516         }
517         if (((RegInfo.UsedLanes & Mask) == 0 ||
518              (RegInfo.DefinedLanes & Mask) == 0) && MO.readsReg()) {
519           DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in " << MI);
520           MO.setIsUndef();
521         }
522       }
523     }
524   }
525 
526   DefinedByCopy.clear();
527   WorklistMembers.clear();
528   delete[] VRegInfos;
529   return true;
530 }
531