mirror of
https://github.com/RPCS3/llvm-mirror.git
synced 2024-11-22 02:33:06 +01:00
282 lines
11 KiB
C++
282 lines
11 KiB
C++
//==--- 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
|