//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "machine-sink"
#include "llvm/CodeGen/Passes.h"
-#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/MachineDominators.h"
-#include "llvm/CodeGen/MachineLoopInfo.h"
-#include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Target/TargetRegisterInfo.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetMachine.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetRegisterInfo.h"
using namespace llvm;
+#define DEBUG_TYPE "machine-sink"
+
static cl::opt<bool>
SplitEdges("machine-sink-split",
cl::desc("Split critical edges during machine sinking"),
MachineDominatorTree *DT; // Machine dominator tree
MachineLoopInfo *LI;
AliasAnalysis *AA;
- BitVector AllocatableSet; // Which physregs are allocatable?
// Remember which edges have been considered for breaking.
SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8>
initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
}
- virtual bool runOnMachineFunction(MachineFunction &MF);
+ bool runOnMachineFunction(MachineFunction &MF) override;
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
MachineFunctionPass::getAnalysisUsage(AU);
AU.addRequired<AliasAnalysis>();
AU.addPreserved<MachineLoopInfo>();
}
- virtual void releaseMemory() {
+ void releaseMemory() override {
CEBCandidates.clear();
}
} // end anonymous namespace
char MachineSinking::ID = 0;
+char &llvm::MachineSinkingID = MachineSinking::ID;
INITIALIZE_PASS_BEGIN(MachineSinking, "machine-sink",
"Machine code sinking", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_END(MachineSinking, "machine-sink",
"Machine code sinking", false, false)
-FunctionPass *llvm::createMachineSinkingPass() { return new MachineSinking(); }
-
bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI,
MachineBasicBlock *MBB) {
if (!MI->isCopy())
// Predecessors according to CFG: BB#0 BB#1
// %reg16386<def> = PHI %reg16434, <BB#0>, %reg16385, <BB#1>
BreakPHIEdge = true;
- for (MachineRegisterInfo::use_nodbg_iterator
- I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end();
- I != E; ++I) {
- MachineInstr *UseInst = &*I;
+ for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
+ MachineInstr *UseInst = MO.getParent();
+ unsigned OpNo = &MO - &UseInst->getOperand(0);
MachineBasicBlock *UseBlock = UseInst->getParent();
if (!(UseBlock == MBB && UseInst->isPHI() &&
- UseInst->getOperand(I.getOperandNo()+1).getMBB() == DefMBB)) {
+ UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) {
BreakPHIEdge = false;
break;
}
if (BreakPHIEdge)
return true;
- for (MachineRegisterInfo::use_nodbg_iterator
- I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end();
- I != E; ++I) {
+ for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
// Determine the block of the use.
- MachineInstr *UseInst = &*I;
+ MachineInstr *UseInst = MO.getParent();
+ unsigned OpNo = &MO - &UseInst->getOperand(0);
MachineBasicBlock *UseBlock = UseInst->getParent();
if (UseInst->isPHI()) {
// PHI nodes use the operand in the predecessor block, not the block with
// the PHI.
- UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB();
+ UseBlock = UseInst->getOperand(OpNo+1).getMBB();
} else if (UseBlock == DefMBB) {
LocalUse = true;
return false;
}
bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
+ if (skipOptnoneFunction(*MF.getFunction()))
+ return false;
+
DEBUG(dbgs() << "******** Machine Sinking ********\n");
const TargetMachine &TM = MF.getTarget();
DT = &getAnalysis<MachineDominatorTree>();
LI = &getAnalysis<MachineLoopInfo>();
AA = &getAnalysis<AliasAnalysis>();
- AllocatableSet = TRI->getAllocatableSet(MF);
bool EverMadeChange = false;
// to be sunk then it's probably worth it.
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
- if (!MO.isReg()) continue;
+ if (!MO.isReg() || !MO.isUse())
+ continue;
unsigned Reg = MO.getReg();
- if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg))
+ if (Reg == 0)
continue;
- if (MRI->hasOneNonDBGUse(Reg))
- return true;
+
+ // We don't move live definitions of physical registers,
+ // so sinking their uses won't enable any opportunities.
+ if (TargetRegisterInfo::isPhysicalRegister(Reg))
+ continue;
+
+ // If this instruction is the only user of a virtual register,
+ // check if breaking the edge will enable sinking
+ // both this instruction and the defining instruction.
+ if (MRI->hasOneNonDBGUse(Reg)) {
+ // If the definition resides in same MBB,
+ // claim it's likely we can sink these together.
+ // If definition resides elsewhere, we aren't
+ // blocking it from being sunk so don't break the edge.
+ MachineInstr *DefMI = MRI->getVRegDef(Reg);
+ if (DefMI->getParent() == MI->getParent())
+ return true;
+ }
}
return false;
MachineBasicBlock *ToBB,
bool BreakPHIEdge) {
if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
- return 0;
+ return nullptr;
// Avoid breaking back edge. From == To means backedge for single BB loop.
if (!SplitEdges || FromBB == ToBB)
- return 0;
+ return nullptr;
// Check for backedges of more "complex" loops.
if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
LI->isLoopHeader(ToBB))
- return 0;
+ return nullptr;
// It's not always legal to break critical edges and sink the computation
// to the edge.
if (*PI == FromBB)
continue;
if (!DT->dominates(ToBB, *PI))
- return 0;
+ return nullptr;
}
}
/// collectDebgValues - Scan instructions following MI and collect any
/// matching DBG_VALUEs.
static void collectDebugValues(MachineInstr *MI,
- SmallVector<MachineInstr *, 2> & DbgValues) {
+ SmallVectorImpl<MachineInstr *> &DbgValues) {
DbgValues.clear();
if (!MI->getOperand(0).isReg())
return;
// Check if only use in post dominated block is PHI instruction.
bool NonPHIUse = false;
- for (MachineRegisterInfo::use_nodbg_iterator
- I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end();
- I != E; ++I) {
- MachineInstr *UseInst = &*I;
- MachineBasicBlock *UseBlock = UseInst->getParent();
- if (UseBlock == SuccToSinkTo && !UseInst->isPHI())
+ for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
+ MachineBasicBlock *UseBlock = UseInst.getParent();
+ if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
NonPHIUse = true;
}
if (!NonPHIUse)
// SuccToSinkTo - This is the successor to sink this instruction to, once we
// decide.
- MachineBasicBlock *SuccToSinkTo = 0;
+ MachineBasicBlock *SuccToSinkTo = nullptr;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg()) continue; // Ignore non-register operands.
// and we can freely move its uses. Alternatively, if it's allocatable,
// it could get allocated to something with a def during allocation.
if (!MRI->isConstantPhysReg(Reg, *MBB->getParent()))
- return NULL;
+ return nullptr;
} else if (!MO.isDead()) {
// A def that isn't dead. We can't move it.
- return NULL;
+ return nullptr;
}
} else {
// Virtual register uses are always safe to sink.
// If it's not safe to move defs of the register class, then abort.
if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
- return NULL;
+ return nullptr;
// FIXME: This picks a successor to sink into based on having one
// successor that dominates all the uses. However, there are cases where
bool LocalUse = false;
if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
BreakPHIEdge, LocalUse))
- return NULL;
+ return nullptr;
continue;
}
// Otherwise, we should look at all the successors and decide which one
// we should sink to.
- for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
- E = MBB->succ_end(); SI != E; ++SI) {
+ // We give successors with smaller loop depth higher priority.
+ SmallVector<MachineBasicBlock*, 4> Succs(MBB->succ_begin(), MBB->succ_end());
+ // Sort Successors according to their loop depth.
+ std::stable_sort(
+ Succs.begin(), Succs.end(),
+ [this](const MachineBasicBlock *LHS, const MachineBasicBlock *RHS) {
+ return LI->getLoopDepth(LHS) < LI->getLoopDepth(RHS);
+ });
+ for (SmallVectorImpl<MachineBasicBlock *>::iterator SI = Succs.begin(),
+ E = Succs.end(); SI != E; ++SI) {
MachineBasicBlock *SuccBlock = *SI;
bool LocalUse = false;
if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
}
if (LocalUse)
// Def is used locally, it's never safe to move this def.
- return NULL;
+ return nullptr;
}
// If we couldn't find a block to sink to, ignore this instruction.
- if (SuccToSinkTo == 0)
- return NULL;
- else if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo))
- return NULL;
+ if (!SuccToSinkTo)
+ return nullptr;
+ if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo))
+ return nullptr;
}
}
// It is not possible to sink an instruction into its own block. This can
// happen with loops.
if (MBB == SuccToSinkTo)
- return NULL;
+ return nullptr;
// It's not safe to sink instructions to EH landing pad. Control flow into
// landing pad is implicitly defined.
if (SuccToSinkTo && SuccToSinkTo->isLandingPad())
- return NULL;
+ return nullptr;
return SuccToSinkTo;
}
MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge);
// If there are no outputs, it must have side-effects.
- if (SuccToSinkTo == 0)
+ if (!SuccToSinkTo)
return false;
DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo);
- // If the block has multiple predecessors, this would introduce computation on
- // a path that it doesn't already exist. We could split the critical edge,
- // but for now we just punt.
+ // If the block has multiple predecessors, this is a critical edge.
+ // Decide if we can sink along it or need to break the edge.
if (SuccToSinkTo->pred_size() > 1) {
// We cannot sink a load across a critical edge - there may be stores in
// other code paths.
++MachineBasicBlock::iterator(MI));
// Move debug values.
- for (SmallVector<MachineInstr *, 2>::iterator DBI = DbgValuesToSink.begin(),
+ for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) {
MachineInstr *DbgMI = *DBI;
SuccToSinkTo->splice(InsertPos, ParentBlock, DbgMI,