//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "phielim"
#include "llvm/CodeGen/Passes.h"
#include "PHIEliminationUtils.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.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/TargetSubtargetInfo.h"
#include <algorithm>
using namespace llvm;
+#define DEBUG_TYPE "phielim"
+
static cl::opt<bool>
DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
cl::Hidden, cl::desc("Disable critical edge splitting "
"during PHI elimination"));
+static cl::opt<bool>
+SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
+ cl::Hidden, cl::desc("Split all critical edges during "
+ "PHI elimination"));
+
+static cl::opt<bool> NoPhiElimLiveOutEarlyExit(
+ "no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden,
+ cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));
+
namespace {
class PHIElimination : public MachineFunctionPass {
MachineRegisterInfo *MRI; // Machine register information
initializePHIEliminationPass(*PassRegistry::getPassRegistry());
}
- virtual bool runOnMachineFunction(MachineFunction &Fn);
- virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+ bool runOnMachineFunction(MachineFunction &Fn) override;
+ void getAnalysisUsage(AnalysisUsage &AU) const override;
private:
/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
///
bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
void LowerPHINode(MachineBasicBlock &MBB,
- MachineBasicBlock::iterator AfterPHIsIt);
+ MachineBasicBlock::iterator LastPHIIt);
/// analyzePHINodes - Gather information about the PHI nodes in
/// here. In particular, we want to map the number of uses of a virtual
bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,
MachineLoopInfo *MLI);
+ // These functions are temporary abstractions around LiveVariables and
+ // LiveIntervals, so they can go away when LiveVariables does.
+ bool isLiveIn(unsigned Reg, const MachineBasicBlock *MBB);
+ bool isLiveOutPastPHIs(unsigned Reg, const MachineBasicBlock *MBB);
+
typedef std::pair<unsigned, unsigned> BBVRegPair;
typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse;
void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<LiveVariables>();
+ AU.addPreserved<SlotIndexes>();
AU.addPreserved<LiveIntervals>();
AU.addPreserved<MachineDominatorTree>();
AU.addPreserved<MachineLoopInfo>();
// Split critical edges to help the coalescer. This does not yet support
// updating LiveIntervals, so we disable it.
- if (!DisableEdgeSplitting && LV && !LIS) {
+ if (!DisableEdgeSplitting && (LV || LIS)) {
MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
- for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
- Changed |= SplitPHIEdges(MF, *I, MLI);
+ for (auto &MBB : MF)
+ Changed |= SplitPHIEdges(MF, MBB, MLI);
}
// Populate VRegPHIUseCount
analyzePHINodes(MF);
// Eliminate PHI instructions by inserting copies into predecessor blocks.
- for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
- Changed |= EliminatePHINodes(MF, *I);
+ for (auto &MBB : MF)
+ Changed |= EliminatePHINodes(MF, MBB);
// Remove dead IMPLICIT_DEF instructions.
- for (SmallPtrSet<MachineInstr*, 4>::iterator I = ImpDefs.begin(),
- E = ImpDefs.end(); I != E; ++I) {
- MachineInstr *DefMI = *I;
+ for (MachineInstr *DefMI : ImpDefs) {
unsigned DefReg = DefMI->getOperand(0).getReg();
if (MRI->use_nodbg_empty(DefReg)) {
if (LIS)
// Clean up the lowered PHI instructions.
for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end();
I != E; ++I) {
- if (LIS)
- LIS->RemoveMachineInstrFromMaps(I->first);
+ if (LIS)
+ LIS->RemoveMachineInstrFromMaps(I->first);
MF.DeleteMachineInstr(I->first);
}
ImpDefs.clear();
VRegPHIUseCount.clear();
- if (LIS)
- MF.verify(this, "After PHI elimination");
-
return Changed;
}
// Get an iterator to the first instruction after the last PHI node (this may
// also be the end of the basic block).
- MachineBasicBlock::iterator AfterPHIsIt = MBB.SkipPHIsAndLabels(MBB.begin());
+ MachineBasicBlock::iterator LastPHIIt =
+ std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
while (MBB.front().isPHI())
- LowerPHINode(MBB, AfterPHIsIt);
+ LowerPHINode(MBB, LastPHIIt);
return true;
}
/// This includes registers with no defs.
static bool isImplicitlyDefined(unsigned VirtReg,
const MachineRegisterInfo *MRI) {
- for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(VirtReg),
- DE = MRI->def_end(); DI != DE; ++DI)
- if (!DI->isImplicitDef())
+ for (MachineInstr &DI : MRI->def_instructions(VirtReg))
+ if (!DI.isImplicitDef())
return false;
return true;
}
/// LowerPHINode - Lower the PHI node at the top of the specified block,
///
void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
- MachineBasicBlock::iterator AfterPHIsIt) {
+ MachineBasicBlock::iterator LastPHIIt) {
++NumLowered;
+
+ MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);
+
// Unlink the PHI node from the basic block, but don't delete the PHI yet.
MachineInstr *MPhi = MBB.remove(MBB.begin());
// Insert a register to register copy at the top of the current block (but
// after any remaining phi nodes) which copies the new incoming register
// into the phi node destination.
- const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
+ const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
if (isSourceDefinedByImplicitDef(MPhi, MRI))
// If all sources of a PHI node are implicit_def, just emit an
// implicit_def instead of a copy.
// Update live variable information if there is any.
if (LV) {
- MachineInstr *PHICopy = prior(AfterPHIsIt);
+ MachineInstr *PHICopy = std::prev(AfterPHIsIt);
if (IncomingReg) {
LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
// Update LiveIntervals for the new copy or implicit def.
if (LIS) {
- MachineInstr *NewInstr = prior(AfterPHIsIt);
- LIS->InsertMachineInstrInMaps(NewInstr);
+ MachineInstr *NewInstr = std::prev(AfterPHIsIt);
+ SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(NewInstr);
SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
- SlotIndex DestCopyIndex = LIS->getInstructionIndex(NewInstr);
if (IncomingReg) {
// Add the region from the beginning of MBB to the copy instruction to
// IncomingReg's live interval.
- LiveInterval &IncomingLI = LIS->getOrCreateInterval(IncomingReg);
+ LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
if (!IncomingVNI)
IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
LIS->getVNInfoAllocator());
- IncomingLI.addRange(LiveRange(MBBStartIndex,
- DestCopyIndex.getRegSlot(),
- IncomingVNI));
+ IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
+ DestCopyIndex.getRegSlot(),
+ IncomingVNI));
}
- LiveInterval &DestLI = LIS->getOrCreateInterval(DestReg);
- if (NewInstr->getOperand(0).isDead()) {
+ LiveInterval &DestLI = LIS->getInterval(DestReg);
+ assert(DestLI.begin() != DestLI.end() &&
+ "PHIs should have nonempty LiveIntervals.");
+ if (DestLI.endIndex().isDead()) {
// A dead PHI's live range begins and ends at the start of the MBB, but
// the lowered copy, which will still be dead, needs to begin and end at
// the copy instruction.
VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
assert(OrigDestVNI && "PHI destination should be live at block entry.");
- DestLI.removeRange(MBBStartIndex, MBBStartIndex.getDeadSlot());
+ DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
LIS->getVNInfoAllocator());
DestLI.removeValNo(OrigDestVNI);
} else {
// Otherwise, remove the region from the beginning of MBB to the copy
// instruction from DestReg's live interval.
- DestLI.removeRange(MBBStartIndex, DestCopyIndex.getRegSlot());
+ DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
assert(DestVNI && "PHI destination should be live at its definition.");
DestVNI->def = DestCopyIndex.getRegSlot();
// Check to make sure we haven't already emitted the copy for this block.
// This can happen because PHI nodes may have multiple entries for the same
// basic block.
- if (!MBBsInsertedInto.insert(&opBlock))
+ if (!MBBsInsertedInto.insert(&opBlock).second)
continue; // If the copy has already been emitted, we're done.
// Find a safe location to insert the copy, this may be the first terminator
findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
// Insert the copy.
- MachineInstr *NewSrcInstr = 0;
+ MachineInstr *NewSrcInstr = nullptr;
if (!reusedIncoming && IncomingReg) {
if (SrcUndef) {
// The source register is undefined, so there is no need for a real
}
} else {
// We just inserted this copy.
- KillInst = prior(InsertPos);
+ KillInst = std::prev(InsertPos);
}
}
assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
if (LIS) {
if (NewSrcInstr) {
LIS->InsertMachineInstrInMaps(NewSrcInstr);
- LIS->addLiveRangeToEndOfBlock(IncomingReg, NewSrcInstr);
+ LIS->addSegmentToEndOfBlock(IncomingReg, NewSrcInstr);
}
if (!SrcUndef &&
bool isLiveOut = false;
for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(),
SE = opBlock.succ_end(); SI != SE; ++SI) {
- if (SrcLI.liveAt(LIS->getMBBStartIdx(*SI))) {
+ SlotIndex startIdx = LIS->getMBBStartIdx(*SI);
+ VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
+
+ // Definitions by other PHIs are not truly live-in for our purposes.
+ if (VNI && VNI->def != startIdx) {
isLiveOut = true;
break;
}
}
} else {
// We just inserted this copy.
- KillInst = prior(InsertPos);
+ KillInst = std::prev(InsertPos);
}
}
assert(KillInst->readsRegister(SrcReg) &&
"Cannot find kill instruction");
SlotIndex LastUseIndex = LIS->getInstructionIndex(KillInst);
- SrcLI.removeRange(LastUseIndex.getRegSlot(),
- LIS->getMBBEndIdx(&opBlock));
+ SrcLI.removeSegment(LastUseIndex.getRegSlot(),
+ LIS->getMBBEndIdx(&opBlock));
}
}
}
/// used later to determine when the vreg is killed in the BB.
///
void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
- for (MachineFunction::const_iterator I = MF.begin(), E = MF.end();
- I != E; ++I)
- for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
- BBI != BBE && BBI->isPHI(); ++BBI)
- for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
- ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(),
- BBI->getOperand(i).getReg())];
+ for (const auto &MBB : MF)
+ for (const auto &BBI : MBB) {
+ if (!BBI.isPHI())
+ break;
+ for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
+ ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
+ BBI.getOperand(i).getReg())];
+ }
}
bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
MachineBasicBlock &MBB,
MachineLoopInfo *MLI) {
- if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad())
+ if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
return false; // Quick exit for basic blocks without PHIs.
- const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : 0;
+ const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
bool Changed = false;
// Avoid splitting backedges of loops. It would introduce small
// out-of-line blocks into the loop which is very bad for code placement.
- if (PreMBB == &MBB)
+ if (PreMBB == &MBB && !SplitAllCriticalEdges)
continue;
- const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : 0;
- if (IsLoopHeader && PreLoop == CurLoop)
+ const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
+ if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
continue;
// LV doesn't consider a phi use live-out, so isLiveOut only returns true
// there is a risk it may not be coalesced away.
//
// If the copy would be a kill, there is no need to split the edge.
- if (!LV->isLiveOut(Reg, *PreMBB))
+ bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
+ if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
continue;
-
- DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#"
- << PreMBB->getNumber() << " -> BB#" << MBB.getNumber()
- << ": " << *BBI);
+ if (ShouldSplit) {
+ DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#"
+ << PreMBB->getNumber() << " -> BB#" << MBB.getNumber()
+ << ": " << *BBI);
+ }
// If Reg is not live-in to MBB, it means it must be live-in to some
// other PreMBB successor, and we can avoid the interference by splitting
// is likely to be left after coalescing. If we are looking at a loop
// exiting edge, split it so we won't insert code in the loop, otherwise
// don't bother.
- bool ShouldSplit = !LV->isLiveIn(Reg, MBB);
+ ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
// Check for a loop exiting edge.
if (!ShouldSplit && CurLoop != PreLoop) {
// Split unless this edge is entering CurLoop from an outer loop.
ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
}
- if (!ShouldSplit)
+ if (!ShouldSplit && !SplitAllCriticalEdges)
continue;
if (!PreMBB->SplitCriticalEdge(&MBB, this)) {
- DEBUG(dbgs() << "Failed to split ciritcal edge.\n");
+ DEBUG(dbgs() << "Failed to split critical edge.\n");
continue;
}
Changed = true;
}
return Changed;
}
+
+bool PHIElimination::isLiveIn(unsigned Reg, const MachineBasicBlock *MBB) {
+ assert((LV || LIS) &&
+ "isLiveIn() requires either LiveVariables or LiveIntervals");
+ if (LIS)
+ return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
+ else
+ return LV->isLiveIn(Reg, *MBB);
+}
+
+bool PHIElimination::isLiveOutPastPHIs(unsigned Reg,
+ const MachineBasicBlock *MBB) {
+ assert((LV || LIS) &&
+ "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
+ // LiveVariables considers uses in PHIs to be in the predecessor basic block,
+ // so that a register used only in a PHI is not live out of the block. In
+ // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
+ // in the predecessor basic block, so that a register used only in a PHI is live
+ // out of the block.
+ if (LIS) {
+ const LiveInterval &LI = LIS->getInterval(Reg);
+ for (const MachineBasicBlock *SI : MBB->successors())
+ if (LI.liveAt(LIS->getMBBStartIdx(SI)))
+ return true;
+ return false;
+ } else {
+ return LV->isLiveOut(Reg, *MBB);
+ }
+}
projects / oota-llvm.git / blobdiff