//==--- 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