contrib/llvm-project/llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

   1 //==--- llvm/CodeGen/ReachingDefAnalysis.h - Reaching Def 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 Reaching Defs Analysis pass.
  10 ///
  11 /// This pass tracks for each instruction what is the "closest" reaching def of
  12 /// a given register. It is used by BreakFalseDeps (for clearance calculation)
  13 /// and ExecutionDomainFix (for arbitrating conflicting domains).
  14 ///
  15 /// Note that this is different from the usual definition notion of liveness.
  16 /// The CPU doesn't care whether or not we consider a register killed.
  17 ///
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_CODEGEN_REACHINGDEFSANALYSIS_H
  22 #define LLVM_CODEGEN_REACHINGDEFSANALYSIS_H
  23
  24 #include "llvm/ADT/DenseMap.h"
  25 #include "llvm/ADT/SmallVector.h"
  26 #include "llvm/ADT/TinyPtrVector.h"
  27 #include "llvm/CodeGen/LoopTraversal.h"
  28 #include "llvm/CodeGen/MachineFunctionPass.h"
  29 #include "llvm/InitializePasses.h"
  30
  31 namespace llvm {
  32
  33 class MachineBasicBlock;
  34 class MachineInstr;
  35
  36 /// Thin wrapper around "int" used to store reaching definitions,
  37 /// using an encoding that makes it compatible with TinyPtrVector.
  38 /// The 0th LSB is forced zero (and will be used for pointer union tagging),
  39 /// The 1st LSB is forced one (to make sure the value is non-zero).
  40 class ReachingDef {
  41   uintptr_t Encoded;
  42   friend struct PointerLikeTypeTraits<ReachingDef>;
  43   explicit ReachingDef(uintptr_t Encoded) : Encoded(Encoded) {}
  44
  45 public:
  46   ReachingDef(std::nullptr_t) : Encoded(0) {}
  47   ReachingDef(int Instr) : Encoded(((uintptr_t) Instr << 2) | 2) {}
  48   operator int() const { return ((int) Encoded) >> 2; }
  49 };
  50
  51 template<>
  52 struct PointerLikeTypeTraits<ReachingDef> {
  53   static constexpr int NumLowBitsAvailable = 1;
  54
  55   static inline void *getAsVoidPointer(const ReachingDef &RD) {
  56     return reinterpret_cast<void *>(RD.Encoded);
  57   }
  58
  59   static inline ReachingDef getFromVoidPointer(void *P) {
  60     return ReachingDef(reinterpret_cast<uintptr_t>(P));
  61   }
  62
  63   static inline ReachingDef getFromVoidPointer(const void *P) {
  64     return ReachingDef(reinterpret_cast<uintptr_t>(P));
  65   }
  66 };
  67
  68 /// This class provides the reaching def analysis.
  69 class ReachingDefAnalysis : public MachineFunctionPass {
  70 private:
  71   MachineFunction *MF;
  72   const TargetRegisterInfo *TRI;
  73   LoopTraversal::TraversalOrder TraversedMBBOrder;
  74   unsigned NumRegUnits;
  75   /// Instruction that defined each register, relative to the beginning of the
  76   /// current basic block.  When a LiveRegsDefInfo is used to represent a
  77   /// live-out register, this value is relative to the end of the basic block,
  78   /// so it will be a negative number.
  79   using LiveRegsDefInfo = std::vector<int>;
  80   LiveRegsDefInfo LiveRegs;
  81
  82   /// Keeps clearance information for all registers. Note that this
  83   /// is different from the usual definition notion of liveness. The CPU
  84   /// doesn't care whether or not we consider a register killed.
  85   using OutRegsInfoMap = SmallVector<LiveRegsDefInfo, 4>;
  86   OutRegsInfoMap MBBOutRegsInfos;
  87
  88   /// Current instruction number.
  89   /// The first instruction in each basic block is 0.
  90   int CurInstr;
  91
  92   /// Maps instructions to their instruction Ids, relative to the beginning of
  93   /// their basic blocks.
  94   DenseMap<MachineInstr *, int> InstIds;
  95
  96   /// All reaching defs of a given RegUnit for a given MBB.
  97   using MBBRegUnitDefs = TinyPtrVector<ReachingDef>;
  98   /// All reaching defs of all reg units for a given MBB
  99   using MBBDefsInfo = std::vector<MBBRegUnitDefs>;
 100   /// All reaching defs of all reg units for a all MBBs
 101   using MBBReachingDefsInfo = SmallVector<MBBDefsInfo, 4>;
 102   MBBReachingDefsInfo MBBReachingDefs;
 103
 104   /// Default values are 'nothing happened a long time ago'.
 105   const int ReachingDefDefaultVal = -(1 << 20);
 106
 107   using InstSet = SmallPtrSetImpl<MachineInstr*>;
 108   using BlockSet = SmallPtrSetImpl<MachineBasicBlock*>;
 109
 110 public:
 111   static char ID; // Pass identification, replacement for typeid
 112
 113   ReachingDefAnalysis() : MachineFunctionPass(ID) {
 114     initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry());
 115   }
 116   void releaseMemory() override;
 117
 118   void getAnalysisUsage(AnalysisUsage &AU) const override {
 119     AU.setPreservesAll();
 120     MachineFunctionPass::getAnalysisUsage(AU);
 121   }
 122
 123   bool runOnMachineFunction(MachineFunction &MF) override;
 124
 125   MachineFunctionProperties getRequiredProperties() const override {
 126     return MachineFunctionProperties().set(
 127         MachineFunctionProperties::Property::NoVRegs).set(
 128           MachineFunctionProperties::Property::TracksLiveness);
 129   }
 130
 131   /// Re-run the analysis.
 132   void reset();
 133
 134   /// Initialize data structures.
 135   void init();
 136
 137   /// Traverse the machine function, mapping definitions.
 138   void traverse();
 139
 140   /// Provides the instruction id of the closest reaching def instruction of
 141   /// PhysReg that reaches MI, relative to the begining of MI's basic block.
 142   int getReachingDef(MachineInstr *MI, int PhysReg) const;
 143
 144   /// Return whether A and B use the same def of PhysReg.
 145   bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, int PhysReg) const;
 146
 147   /// Return whether the reaching def for MI also is live out of its parent
 148   /// block.
 149   bool isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const;
 150
 151   /// Return the local MI that produces the live out value for PhysReg, or
 152   /// nullptr for a non-live out or non-local def.
 153   MachineInstr *getLocalLiveOutMIDef(MachineBasicBlock *MBB,
 154                                      int PhysReg) const;
 155
 156   /// If a single MachineInstr creates the reaching definition, then return it.
 157   /// Otherwise return null.
 158   MachineInstr *getUniqueReachingMIDef(MachineInstr *MI, int PhysReg) const;
 159
 160   /// If a single MachineInstr creates the reaching definition, for MIs operand
 161   /// at Idx, then return it. Otherwise return null.
 162   MachineInstr *getMIOperand(MachineInstr *MI, unsigned Idx) const;
 163
 164   /// If a single MachineInstr creates the reaching definition, for MIs MO,
 165   /// then return it. Otherwise return null.
 166   MachineInstr *getMIOperand(MachineInstr *MI, MachineOperand &MO) const;
 167
 168   /// Provide whether the register has been defined in the same basic block as,
 169   /// and before, MI.
 170   bool hasLocalDefBefore(MachineInstr *MI, int PhysReg) const;
 171
 172   /// Return whether the given register is used after MI, whether it's a local
 173   /// use or a live out.
 174   bool isRegUsedAfter(MachineInstr *MI, int PhysReg) const;
 175
 176   /// Return whether the given register is defined after MI.
 177   bool isRegDefinedAfter(MachineInstr *MI, int PhysReg) const;
 178
 179   /// Provides the clearance - the number of instructions since the closest
 180   /// reaching def instuction of PhysReg that reaches MI.
 181   int getClearance(MachineInstr *MI, MCPhysReg PhysReg) const;
 182
 183   /// Provides the uses, in the same block as MI, of register that MI defines.
 184   /// This does not consider live-outs.
 185   void getReachingLocalUses(MachineInstr *MI, int PhysReg,
 186                             InstSet &Uses) const;
 187
 188   /// Search MBB for a definition of PhysReg and insert it into Defs. If no
 189   /// definition is found, recursively search the predecessor blocks for them.
 190   void getLiveOuts(MachineBasicBlock *MBB, int PhysReg, InstSet &Defs,
 191                    BlockSet &VisitedBBs) const;
 192   void getLiveOuts(MachineBasicBlock *MBB, int PhysReg, InstSet &Defs) const;
 193
 194   /// For the given block, collect the instructions that use the live-in
 195   /// value of the provided register. Return whether the value is still
 196   /// live on exit.
 197   bool getLiveInUses(MachineBasicBlock *MBB, int PhysReg,
 198                      InstSet &Uses) const;
 199
 200   /// Collect the users of the value stored in PhysReg, which is defined
 201   /// by MI.
 202   void getGlobalUses(MachineInstr *MI, int PhysReg,
 203                      InstSet &Uses) const;
 204
 205   /// Return whether From can be moved forwards to just before To.
 206   bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const;
 207
 208   /// Return whether From can be moved backwards to just after To.
 209   bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const;
 210
 211   /// Assuming MI is dead, recursively search the incoming operands which are
 212   /// killed by MI and collect those that would become dead.
 213   void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const;
 214
 215   /// Return whether removing this instruction will have no effect on the
 216   /// program, returning the redundant use-def chain.
 217   bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const;
 218
 219   /// Return whether removing this instruction will have no effect on the
 220   /// program, ignoring the possible effects on some instructions, returning
 221   /// the redundant use-def chain.
 222   bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove,
 223                       InstSet &Ignore) const;
 224
 225   /// Return whether a MachineInstr could be inserted at MI and safely define
 226   /// the given register without affecting the program.
 227   bool isSafeToDefRegAt(MachineInstr *MI, int PhysReg) const;
 228
 229   /// Return whether a MachineInstr could be inserted at MI and safely define
 230   /// the given register without affecting the program, ignoring any effects
 231   /// on the provided instructions.
 232   bool isSafeToDefRegAt(MachineInstr *MI, int PhysReg, InstSet &Ignore) const;
 233
 234 private:
 235   /// Set up LiveRegs by merging predecessor live-out values.
 236   void enterBasicBlock(MachineBasicBlock *MBB);
 237
 238   /// Update live-out values.
 239   void leaveBasicBlock(MachineBasicBlock *MBB);
 240
 241   /// Process he given basic block.
 242   void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 243
 244   /// Process block that is part of a loop again.
 245   void reprocessBasicBlock(MachineBasicBlock *MBB);
 246
 247   /// Update def-ages for registers defined by MI.
 248   /// Also break dependencies on partial defs and undef uses.
 249   void processDefs(MachineInstr *);
 250
 251   /// Utility function for isSafeToMoveForwards/Backwards.
 252   template<typename Iterator>
 253   bool isSafeToMove(MachineInstr *From, MachineInstr *To) const;
 254
 255   /// Return whether removing this instruction will have no effect on the
 256   /// program, ignoring the possible effects on some instructions, returning
 257   /// the redundant use-def chain.
 258   bool isSafeToRemove(MachineInstr *MI, InstSet &Visited,
 259                       InstSet &ToRemove, InstSet &Ignore) const;
 260
 261   /// Provides the MI, from the given block, corresponding to the Id or a
 262   /// nullptr if the id does not refer to the block.
 263   MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId) const;
 264
 265   /// Provides the instruction of the closest reaching def instruction of
 266   /// PhysReg that reaches MI, relative to the begining of MI's basic block.
 267   MachineInstr *getReachingLocalMIDef(MachineInstr *MI, int PhysReg) const;
 268 };
 269
 270 } // namespace llvm
 271
 272 #endif // LLVM_CODEGEN_REACHINGDEFSANALYSIS_H