1 //===- DetectDeadLanes.h - SubRegister Lane Usage Analysis --*- C++ -*-----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// Analysis that tracks defined/used subregister lanes across COPY instructions
11 /// and instructions that get lowered to a COPY (PHI, REG_SEQUENCE,
12 /// INSERT_SUBREG, EXTRACT_SUBREG).
13 /// The information is used to detect dead definitions and the usage of
14 /// (completely) undefined values and mark the operands as such.
15 /// This pass is necessary because the dead/undef status is not obvious anymore
16 /// when subregisters are involved.
17 ///
18 /// Example:
19 ///    %0 = some definition
20 ///    %1 = IMPLICIT_DEF
21 ///    %2 = REG_SEQUENCE %0, sub0, %1, sub1
22 ///    %3 = EXTRACT_SUBREG %2, sub1
23 ///       = use %3
24 /// The %0 definition is dead and %3 contains an undefined value.
25 //
26 //===----------------------------------------------------------------------===//
27 
28 #ifndef LLVM_CODEGEN_DETECTDEADLANES_H
29 #define LLVM_CODEGEN_DETECTDEADLANES_H
30 
31 #include "llvm/ADT/BitVector.h"
32 #include "llvm/MC/LaneBitmask.h"
33 #include <deque>
34 
35 namespace llvm {
36 
37 class MachineInstr;
38 class MachineOperand;
39 class MachineRegisterInfo;
40 class TargetRegisterInfo;
41 
42 class DeadLaneDetector {
43 public:
44   /// Contains a bitmask of which lanes of a given virtual register are
45   /// defined and which ones are actually used.
46   struct VRegInfo {
47     LaneBitmask UsedLanes;
48     LaneBitmask DefinedLanes;
49   };
50 
51   DeadLaneDetector(const MachineRegisterInfo *MRI,
52                    const TargetRegisterInfo *TRI);
53 
54   /// Update the \p DefinedLanes and the \p UsedLanes for all virtual registers.
55   void computeSubRegisterLaneBitInfo();
56 
57   const VRegInfo &getVRegInfo(unsigned RegIdx) const {
58     return VRegInfos[RegIdx];
59   }
60 
61   bool isDefinedByCopy(unsigned RegIdx) const {
62     return DefinedByCopy.test(RegIdx);
63   }
64 
65 private:
66   /// Add used lane bits on the register used by operand \p MO. This translates
67   /// the bitmask based on the operands subregister, and puts the register into
68   /// the worklist if any new bits were added.
69   void addUsedLanesOnOperand(const MachineOperand &MO, LaneBitmask UsedLanes);
70 
71   /// Given a bitmask \p UsedLanes for the used lanes on a def output of a
72   /// COPY-like instruction determine the lanes used on the use operands
73   /// and call addUsedLanesOnOperand() for them.
74   void transferUsedLanesStep(const MachineInstr &MI, LaneBitmask UsedLanes);
75 
76   /// Given a use regiser operand \p Use and a mask of defined lanes, check
77   /// if the operand belongs to a lowersToCopies() instruction, transfer the
78   /// mask to the def and put the instruction into the worklist.
79   void transferDefinedLanesStep(const MachineOperand &Use,
80                                 LaneBitmask DefinedLanes);
81 
82 public:
83   /// Given a mask \p DefinedLanes of lanes defined at operand \p OpNum
84   /// of COPY-like instruction, determine which lanes are defined at the output
85   /// operand \p Def.
86   LaneBitmask transferDefinedLanes(const MachineOperand &Def, unsigned OpNum,
87                                    LaneBitmask DefinedLanes) const;
88 
89   /// Given a mask \p UsedLanes used from the output of instruction \p MI
90   /// determine which lanes are used from operand \p MO of this instruction.
91   LaneBitmask transferUsedLanes(const MachineInstr &MI, LaneBitmask UsedLanes,
92                                 const MachineOperand &MO) const;
93 
94 private:
95   LaneBitmask determineInitialDefinedLanes(unsigned Reg);
96   LaneBitmask determineInitialUsedLanes(unsigned Reg);
97 
98   const MachineRegisterInfo *MRI;
99   const TargetRegisterInfo *TRI;
100 
101   void PutInWorklist(unsigned RegIdx) {
102     if (WorklistMembers.test(RegIdx))
103       return;
104     WorklistMembers.set(RegIdx);
105     Worklist.push_back(RegIdx);
106   }
107 
108   std::unique_ptr<VRegInfo[]> VRegInfos;
109   /// Worklist containing virtreg indexes.
110   std::deque<unsigned> Worklist;
111   BitVector WorklistMembers;
112   /// This bitvector is set for each vreg index where the vreg is defined
113   /// by an instruction where lowersToCopies()==true.
114   BitVector DefinedByCopy;
115 };
116 
117 } // end namespace llvm
118 
119 #endif // LLVM_CODEGEN_DETECTDEADLANES_H
120