Update prebuilt Clang to r416183b from Android.
https://android.googlesource.com/platform/prebuilts/clang/host/
linux-x86/+/06a71ddac05c22edb2d10b590e1769b3f8619bef
clang 12.0.5 (based on r416183b) from build 7284624.
Change-Id: I277a316abcf47307562d8b748b84870f31a72866
Signed-off-by: Olivier Deprez <olivier.deprez@arm.com>
diff --git a/linux-x64/clang/include/llvm/CodeGen/ReachingDefAnalysis.h b/linux-x64/clang/include/llvm/CodeGen/ReachingDefAnalysis.h
index a599fb6..bcb48de 100644
--- a/linux-x64/clang/include/llvm/CodeGen/ReachingDefAnalysis.h
+++ b/linux-x64/clang/include/llvm/CodeGen/ReachingDefAnalysis.h
@@ -23,19 +23,54 @@
#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
@@ -54,12 +89,12 @@
/// The first instruction in each basic block is 0.
int CurInstr;
- /// Maps instructions to their instruction Ids, relative to the begining of
+ /// 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 = SmallVector<int, 1>;
+ 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
@@ -69,6 +104,9 @@
/// 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
@@ -86,30 +124,156 @@
MachineFunctionProperties getRequiredProperties() const override {
return MachineFunctionProperties().set(
- MachineFunctionProperties::Property::NoVRegs);
+ 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, int PhysReg);
+ 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, MCPhysReg PhysReg);
+ 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(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
+ void enterBasicBlock(MachineBasicBlock *MBB);
/// Update live-out values.
- void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
+ 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