From ac30ea2f877ed82911fd1e3fd9f9d86c8072d05f Mon Sep 17 00:00:00 2001 From: Sam Parker Date: Wed, 29 Jan 2020 03:26:11 -0500 Subject: [RDA][ARM] Move functionality into RDA Add several new helpers to RDA: - hasLocalDefBefore - isRegDefinedAfter - isSafeToDefRegAt And move two bits of logic from ARMLowOverheadLoops into RDA: - isSafeToMove - isSafeToRemove Both of these have some wrappers too to make them more convienent to use. Differential Revision: https://reviews.llvm.org/D73460 --- llvm/lib/CodeGen/ReachingDefAnalysis.cpp | 138 +++++++++++++++++++++++++++++++ 1 file changed, 138 insertions(+) (limited to 'llvm/lib/CodeGen/ReachingDefAnalysis.cpp') diff --git a/llvm/lib/CodeGen/ReachingDefAnalysis.cpp b/llvm/lib/CodeGen/ReachingDefAnalysis.cpp index e21df32..4483a85 100644 --- a/llvm/lib/CodeGen/ReachingDefAnalysis.cpp +++ b/llvm/lib/CodeGen/ReachingDefAnalysis.cpp @@ -6,6 +6,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/ADT/SmallSet.h" #include "llvm/CodeGen/LivePhysRegs.h" #include "llvm/CodeGen/ReachingDefAnalysis.h" #include "llvm/CodeGen/TargetRegisterInfo.h" @@ -226,6 +227,11 @@ ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) const { return InstIds.lookup(MI) - getReachingDef(MI, PhysReg); } +bool +ReachingDefAnalysis::hasLocalDefBefore(MachineInstr *MI, int PhysReg) const { + return getReachingDef(MI, PhysReg) >= 0; +} + void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def, int PhysReg, InstSet &Uses) const { MachineBasicBlock *MBB = Def->getParent(); @@ -316,6 +322,18 @@ bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) const { return false; } +bool ReachingDefAnalysis::isRegDefinedAfter(MachineInstr *MI, + int PhysReg) const { + MachineBasicBlock *MBB = MI->getParent(); + if (getReachingDef(MI, PhysReg) != getReachingDef(&MBB->back(), PhysReg)) + return true; + + if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg)) + return Def == getReachingMIDef(MI, PhysReg); + + return false; +} + bool ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const { MachineBasicBlock *MBB = MI->getParent(); @@ -352,3 +370,123 @@ MachineInstr* ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB, return Def < 0 ? nullptr : getInstFromId(MBB, Def); } + +// Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must +// not define a register that is used by any instructions, after and including, +// 'To'. These instructions also must not redefine any of Froms operands. +template +bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From, + MachineInstr *To) const { + if (From->getParent() != To->getParent()) + return false; + + SmallSet Defs; + // First check that From would compute the same value if moved. + for (auto &MO : From->operands()) { + if (!MO.isReg() || MO.isUndef() || !MO.getReg()) + continue; + if (MO.isDef()) + Defs.insert(MO.getReg()); + else if (!hasSameReachingDef(From, To, MO.getReg())) + return false; + } + + // Now walk checking that the rest of the instructions will compute the same + // value. + for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) { + for (auto &MO : I->operands()) + if (MO.isReg() && MO.getReg() && MO.isUse() && Defs.count(MO.getReg())) + return false; + } + return true; +} + +bool ReachingDefAnalysis::isSafeToMoveForwards(MachineInstr *From, + MachineInstr *To) const { + return isSafeToMove(From, To); +} + +bool ReachingDefAnalysis::isSafeToMoveBackwards(MachineInstr *From, + MachineInstr *To) const { + return isSafeToMove(From, To); +} + +bool ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, + InstSet &ToRemove) const { + SmallPtrSet Ignore; + SmallPtrSet Visited; + return isSafeToRemove(MI, Visited, ToRemove, Ignore); +} + +bool +ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &ToRemove, + InstSet &Ignore) const { + SmallPtrSet Visited; + return isSafeToRemove(MI, Visited, ToRemove, Ignore); +} + +bool +ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &Visited, + InstSet &ToRemove, InstSet &Ignore) const { + if (Visited.count(MI) || Ignore.count(MI)) + return true; + else if (MI->mayLoadOrStore() || MI->hasUnmodeledSideEffects() || + MI->isBranch() || MI->isTerminator() || MI->isReturn()) { + // Unless told to ignore the instruction, don't remove anything which has + // side effects. + return false; + } + + Visited.insert(MI); + for (auto &MO : MI->operands()) { + if (!MO.isReg() || MO.isUse() || MO.getReg() == 0) + continue; + + SmallPtrSet Uses; + getGlobalUses(MI, MO.getReg(), Uses); + + for (auto I : Uses) { + if (Ignore.count(I) || ToRemove.count(I)) + continue; + if (!isSafeToRemove(I, Visited, ToRemove, Ignore)) + return false; + } + } + ToRemove.insert(MI); + return true; +} + +bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, + int PhysReg) const { + SmallPtrSet Ignore; + return isSafeToDefRegAt(MI, PhysReg, Ignore); +} + +bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, int PhysReg, + InstSet &Ignore) const { + // Check for any uses of the register after MI. + if (isRegUsedAfter(MI, PhysReg)) { + if (auto *Def = getReachingMIDef(MI, PhysReg)) { + SmallPtrSet Uses; + getReachingLocalUses(Def, PhysReg, Uses); + for (auto *Use : Uses) + if (!Ignore.count(Use)) + return false; + } else + return false; + } + + MachineBasicBlock *MBB = MI->getParent(); + // Check for any defs after MI. + if (isRegDefinedAfter(MI, PhysReg)) { + auto I = MachineBasicBlock::iterator(MI); + for (auto E = MBB->end(); I != E; ++I) { + if (Ignore.count(&*I)) + continue; + for (auto &MO : I->operands()) + if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg) + return false; + } + } + return true; +} -- cgit v1.1