| //==--- llvm/CodeGen/ReachingDefAnalysis.h - Reaching Def Analysis -*- C++ -*---==// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| /// \file Reaching Defs Analysis pass. |
| /// |
| /// This pass tracks for each instruction what is the "closest" reaching def of |
| /// a given register. It is used by BreakFalseDeps (for clearance calculation) |
| /// and ExecutionDomainFix (for arbitrating conflicting domains). |
| /// |
| /// Note that this is different from the usual definition notion of liveness. |
| /// The CPU doesn't care whether or not we consider a register killed. |
| /// |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CODEGEN_REACHINGDEFANALYSIS_H |
| #define LLVM_CODEGEN_REACHINGDEFANALYSIS_H |
| |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/ADT/TinyPtrVector.h" |
| #include "llvm/CodeGen/LoopTraversal.h" |
| #include "llvm/CodeGen/MachineFunctionPass.h" |
| #include "llvm/InitializePasses.h" |
| |
| namespace llvm { |
| |
| class MachineBasicBlock; |
| class MachineInstr; |
| |
| /// Thin wrapper around "int" used to store reaching definitions, |
| /// using an encoding that makes it compatible with TinyPtrVector. |
| /// The 0th LSB is forced zero (and will be used for pointer union tagging), |
| /// The 1st LSB is forced one (to make sure the value is non-zero). |
| class ReachingDef { |
| uintptr_t Encoded; |
| friend struct PointerLikeTypeTraits<ReachingDef>; |
| explicit ReachingDef(uintptr_t Encoded) : Encoded(Encoded) {} |
| |
| public: |
| ReachingDef(std::nullptr_t) : Encoded(0) {} |
| ReachingDef(int Instr) : Encoded(((uintptr_t) Instr << 2) | 2) {} |
| operator int() const { return ((int) Encoded) >> 2; } |
| }; |
| |
| template<> |
| struct PointerLikeTypeTraits<ReachingDef> { |
| static constexpr int NumLowBitsAvailable = 1; |
| |
| static inline void *getAsVoidPointer(const ReachingDef &RD) { |
| return reinterpret_cast<void *>(RD.Encoded); |
| } |
| |
| static inline ReachingDef getFromVoidPointer(void *P) { |
| return ReachingDef(reinterpret_cast<uintptr_t>(P)); |
| } |
| |
| static inline ReachingDef getFromVoidPointer(const void *P) { |
| return ReachingDef(reinterpret_cast<uintptr_t>(P)); |
| } |
| }; |
| |
| /// This class provides the reaching def analysis. |
| class ReachingDefAnalysis : public MachineFunctionPass { |
| private: |
| MachineFunction *MF; |
| const TargetRegisterInfo *TRI; |
| LoopTraversal::TraversalOrder TraversedMBBOrder; |
| unsigned NumRegUnits; |
| /// Instruction that defined each register, relative to the beginning of the |
| /// current basic block. When a LiveRegsDefInfo is used to represent a |
| /// live-out register, this value is relative to the end of the basic block, |
| /// so it will be a negative number. |
| using LiveRegsDefInfo = std::vector<int>; |
| LiveRegsDefInfo LiveRegs; |
| |
| /// Keeps clearance information for all registers. Note that this |
| /// is different from the usual definition notion of liveness. The CPU |
| /// doesn't care whether or not we consider a register killed. |
| using OutRegsInfoMap = SmallVector<LiveRegsDefInfo, 4>; |
| OutRegsInfoMap MBBOutRegsInfos; |
| |
| /// Current instruction number. |
| /// The first instruction in each basic block is 0. |
| int CurInstr; |
| |
| /// Maps instructions to their instruction Ids, relative to the beginning of |
| /// their basic blocks. |
| DenseMap<MachineInstr *, int> InstIds; |
| |
| /// All reaching defs of a given RegUnit for a given MBB. |
| using MBBRegUnitDefs = TinyPtrVector<ReachingDef>; |
| /// All reaching defs of all reg units for a given MBB |
| using MBBDefsInfo = std::vector<MBBRegUnitDefs>; |
| /// All reaching defs of all reg units for a all MBBs |
| using MBBReachingDefsInfo = SmallVector<MBBDefsInfo, 4>; |
| MBBReachingDefsInfo MBBReachingDefs; |
| |
| /// Default values are 'nothing happened a long time ago'. |
| const int ReachingDefDefaultVal = -(1 << 20); |
| |
| using InstSet = SmallPtrSetImpl<MachineInstr*>; |
| using BlockSet = SmallPtrSetImpl<MachineBasicBlock*>; |
| |
| public: |
| static char ID; // Pass identification, replacement for typeid |
| |
| ReachingDefAnalysis() : MachineFunctionPass(ID) { |
| initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry()); |
| } |
| void releaseMemory() override; |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| AU.setPreservesAll(); |
| MachineFunctionPass::getAnalysisUsage(AU); |
| } |
| |
| bool runOnMachineFunction(MachineFunction &MF) override; |
| |
| MachineFunctionProperties getRequiredProperties() const override { |
| return MachineFunctionProperties().set( |
| MachineFunctionProperties::Property::NoVRegs).set( |
| MachineFunctionProperties::Property::TracksLiveness); |
| } |
| |
| /// Re-run the analysis. |
| void reset(); |
| |
| /// Initialize data structures. |
| void init(); |
| |
| /// Traverse the machine function, mapping definitions. |
| void traverse(); |
| |
| /// Provides the instruction id of the closest reaching def instruction of |
| /// PhysReg that reaches MI, relative to the begining of MI's basic block. |
| int getReachingDef(MachineInstr *MI, MCRegister PhysReg) const; |
| |
| /// Return whether A and B use the same def of PhysReg. |
| bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, |
| MCRegister PhysReg) const; |
| |
| /// Return whether the reaching def for MI also is live out of its parent |
| /// block. |
| bool isReachingDefLiveOut(MachineInstr *MI, MCRegister PhysReg) const; |
| |
| /// Return the local MI that produces the live out value for PhysReg, or |
| /// nullptr for a non-live out or non-local def. |
| MachineInstr *getLocalLiveOutMIDef(MachineBasicBlock *MBB, |
| MCRegister PhysReg) const; |
| |
| /// If a single MachineInstr creates the reaching definition, then return it. |
| /// Otherwise return null. |
| MachineInstr *getUniqueReachingMIDef(MachineInstr *MI, |
| MCRegister PhysReg) const; |
| |
| /// If a single MachineInstr creates the reaching definition, for MIs operand |
| /// at Idx, then return it. Otherwise return null. |
| MachineInstr *getMIOperand(MachineInstr *MI, unsigned Idx) const; |
| |
| /// If a single MachineInstr creates the reaching definition, for MIs MO, |
| /// then return it. Otherwise return null. |
| MachineInstr *getMIOperand(MachineInstr *MI, MachineOperand &MO) const; |
| |
| /// Provide whether the register has been defined in the same basic block as, |
| /// and before, MI. |
| bool hasLocalDefBefore(MachineInstr *MI, MCRegister PhysReg) const; |
| |
| /// Return whether the given register is used after MI, whether it's a local |
| /// use or a live out. |
| bool isRegUsedAfter(MachineInstr *MI, MCRegister PhysReg) const; |
| |
| /// Return whether the given register is defined after MI. |
| bool isRegDefinedAfter(MachineInstr *MI, MCRegister PhysReg) const; |
| |
| /// Provides the clearance - the number of instructions since the closest |
| /// reaching def instuction of PhysReg that reaches MI. |
| int getClearance(MachineInstr *MI, MCRegister PhysReg) const; |
| |
| /// Provides the uses, in the same block as MI, of register that MI defines. |
| /// This does not consider live-outs. |
| void getReachingLocalUses(MachineInstr *MI, MCRegister PhysReg, |
| InstSet &Uses) const; |
| |
| /// Search MBB for a definition of PhysReg and insert it into Defs. If no |
| /// definition is found, recursively search the predecessor blocks for them. |
| void getLiveOuts(MachineBasicBlock *MBB, MCRegister PhysReg, InstSet &Defs, |
| BlockSet &VisitedBBs) const; |
| void getLiveOuts(MachineBasicBlock *MBB, MCRegister PhysReg, |
| InstSet &Defs) const; |
| |
| /// For the given block, collect the instructions that use the live-in |
| /// value of the provided register. Return whether the value is still |
| /// live on exit. |
| bool getLiveInUses(MachineBasicBlock *MBB, MCRegister PhysReg, |
| InstSet &Uses) const; |
| |
| /// Collect the users of the value stored in PhysReg, which is defined |
| /// by MI. |
| void getGlobalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const; |
| |
| /// Collect all possible definitions of the value stored in PhysReg, which is |
| /// used by MI. |
| void getGlobalReachingDefs(MachineInstr *MI, MCRegister PhysReg, |
| InstSet &Defs) const; |
| |
| /// Return whether From can be moved forwards to just before To. |
| bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const; |
| |
| /// Return whether From can be moved backwards to just after To. |
| bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const; |
| |
| /// Assuming MI is dead, recursively search the incoming operands which are |
| /// killed by MI and collect those that would become dead. |
| void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const; |
| |
| /// Return whether removing this instruction will have no effect on the |
| /// program, returning the redundant use-def chain. |
| bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const; |
| |
| /// Return whether removing this instruction will have no effect on the |
| /// program, ignoring the possible effects on some instructions, returning |
| /// the redundant use-def chain. |
| bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove, |
| InstSet &Ignore) const; |
| |
| /// Return whether a MachineInstr could be inserted at MI and safely define |
| /// the given register without affecting the program. |
| bool isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg) const; |
| |
| /// Return whether a MachineInstr could be inserted at MI and safely define |
| /// the given register without affecting the program, ignoring any effects |
| /// on the provided instructions. |
| bool isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg, |
| InstSet &Ignore) const; |
| |
| private: |
| /// Set up LiveRegs by merging predecessor live-out values. |
| void enterBasicBlock(MachineBasicBlock *MBB); |
| |
| /// Update live-out values. |
| void leaveBasicBlock(MachineBasicBlock *MBB); |
| |
| /// Process he given basic block. |
| void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); |
| |
| /// Process block that is part of a loop again. |
| void reprocessBasicBlock(MachineBasicBlock *MBB); |
| |
| /// Update def-ages for registers defined by MI. |
| /// Also break dependencies on partial defs and undef uses. |
| void processDefs(MachineInstr *); |
| |
| /// Utility function for isSafeToMoveForwards/Backwards. |
| template<typename Iterator> |
| bool isSafeToMove(MachineInstr *From, MachineInstr *To) const; |
| |
| /// Return whether removing this instruction will have no effect on the |
| /// program, ignoring the possible effects on some instructions, returning |
| /// the redundant use-def chain. |
| bool isSafeToRemove(MachineInstr *MI, InstSet &Visited, |
| InstSet &ToRemove, InstSet &Ignore) const; |
| |
| /// Provides the MI, from the given block, corresponding to the Id or a |
| /// nullptr if the id does not refer to the block. |
| MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId) const; |
| |
| /// Provides the instruction of the closest reaching def instruction of |
| /// PhysReg that reaches MI, relative to the begining of MI's basic block. |
| MachineInstr *getReachingLocalMIDef(MachineInstr *MI, |
| MCRegister PhysReg) const; |
| }; |
| |
| } // namespace llvm |
| |
| #endif // LLVM_CODEGEN_REACHINGDEFANALYSIS_H |