//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "strongphielim"
+#include "PHIEliminationUtils.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/Support/ErrorHandling.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Support/Debug.h"
using namespace llvm;
namespace {
virtual void getAnalysisUsage(AnalysisUsage&) const;
bool runOnMachineFunction(MachineFunction&);
+
+ private:
+ void InsertCopiesForPHI(MachineInstr*, MachineBasicBlock*);
+
+ MachineRegisterInfo* MRI;
+ const TargetInstrInfo* TII;
+ LiveIntervals* LI;
+
+ typedef DenseSet<std::pair<MachineBasicBlock*, unsigned> > CopySet;
+ CopySet InsertedCopies;
};
} // namespace
MachineFunctionPass::getAnalysisUsage(AU);
}
-bool StrongPHIElimination::runOnMachineFunction(MachineFunction& Fn) {
- llvm_unreachable("Strong phi elimination is not implemented");
+static MachineOperand* findLastUse(MachineBasicBlock* MBB, unsigned Reg) {
+ // FIXME: This only needs to check from the first terminator, as only the
+ // first terminator can use a virtual register.
+ for (MachineBasicBlock::reverse_iterator RI = MBB->rbegin(); ; ++RI) {
+ assert (RI != MBB->rend());
+ MachineInstr* MI = &*RI;
+
+ for (MachineInstr::mop_iterator OI = MI->operands_begin(),
+ OE = MI->operands_end(); OI != OE; ++OI) {
+ MachineOperand& MO = *OI;
+ if (MO.isReg() && MO.isUse() && MO.getReg() == Reg)
+ return &MO;
+ }
+ }
+ return NULL;
+}
+
+bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
+ MRI = &MF.getRegInfo();
+ TII = MF.getTarget().getInstrInfo();
+ LI = &getAnalysis<LiveIntervals>();
+
+ // Insert copies for all PHI source and destination registers.
+ for (MachineFunction::iterator I = MF.begin(), E = MF.end();
+ I != E; ++I) {
+ for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
+ BBI != BBE && BBI->isPHI(); ++BBI) {
+ InsertCopiesForPHI(BBI, I);
+ }
+ }
+
+ // Adjust the live intervals of all PHI source registers to handle the case
+ // where the PHIs in successor blocks were the only later uses of the source
+ // register.
+ for (CopySet::iterator I = InsertedCopies.begin(), E = InsertedCopies.end();
+ I != E; ++I) {
+ MachineBasicBlock* MBB = I->first;
+ unsigned SrcReg = I->second;
+ LiveInterval& SrcLI = LI->getInterval(SrcReg);
+
+ bool isLiveOut = false;
+ for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
+ SE = MBB->succ_end(); SI != SE; ++SI) {
+ if (SrcLI.liveAt(LI->getMBBStartIdx(*SI))) {
+ isLiveOut = true;
+ break;
+ }
+ }
+
+ if (isLiveOut)
+ continue;
+
+ MachineOperand* LastUse = findLastUse(MBB, SrcReg);
+ assert(LastUse);
+ SrcLI.removeRange(LI->getInstructionIndex(LastUse->getParent()).getDefIndex(),
+ LI->getMBBEndIdx(MBB));
+ LastUse->setIsKill(true);
+ }
+
+ // Remove all PHI instructions from the function.
+ bool Changed = false;
+ for (MachineFunction::iterator I = MF.begin(), E = MF.end();
+ I != E; ++I) {
+ MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
+ while (BBI != BBE && BBI->isPHI()) {
+ MachineInstr* PHI = BBI;
+ ++BBI;
+ LI->RemoveMachineInstrFromMaps(PHI);
+ PHI->eraseFromParent();
+ Changed = true;
+ }
+ }
+
+ LI->renumber();
+ MF.verify(this);
+
+ InsertedCopies.clear();
+
+ return Changed;
+}
+
+void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
+ MachineBasicBlock* MBB) {
+ assert(PHI->isPHI());
+ unsigned DestReg = PHI->getOperand(0).getReg();
+
+ const TargetRegisterClass* RC = MRI->getRegClass(DestReg);
+ unsigned CopyReg = MRI->createVirtualRegister(RC);
+
+ MachineInstr* CopyInstr = BuildMI(*MBB,
+ MBB->SkipPHIsAndLabels(MBB->begin()),
+ PHI->getDebugLoc(),
+ TII->get(TargetOpcode::COPY),
+ DestReg).addReg(CopyReg);
+ LI->InsertMachineInstrInMaps(CopyInstr);
+ CopyInstr->getOperand(1).setIsKill(true);
+
+ // Add the region from the beginning of MBB to the copy instruction to
+ // CopyReg's live interval, and give the VNInfo the phidef flag.
+ LiveInterval& CopyLI = LI->getOrCreateInterval(CopyReg);
+ SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
+ SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
+ VNInfo* CopyVNI = CopyLI.getNextValue(MBBStartIndex,
+ CopyInstr,
+ LI->getVNInfoAllocator());
+ CopyVNI->setIsPHIDef(true);
+ CopyLI.addRange(LiveRange(MBBStartIndex,
+ DestCopyIndex.getDefIndex(),
+ CopyVNI));
+
+ // Adjust DestReg's live interval to adjust for its new definition at
+ // CopyInstr.
+ LiveInterval& DestLI = LI->getOrCreateInterval(DestReg);
+ SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
+ DestLI.removeRange(PHIIndex.getDefIndex(), DestCopyIndex.getDefIndex());
+
+ VNInfo* DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex());
+ assert(DestVNI);
+ DestVNI->def = DestCopyIndex.getDefIndex();
+
+ SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
+ for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
+ MachineOperand& SrcMO = PHI->getOperand(i);
+ unsigned SrcReg = SrcMO.getReg();
+ unsigned SrcSubReg = SrcMO.getSubReg();
+
+ assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
+ "Machine PHI Operands must all be virtual registers!");
+
+ // If source is defined by an implicit def, there is no need to insert a
+ // copy.
+ // FIXME: For some reason, if LiveIntervals is run prior to PHI elimination
+ // implcit defs have no defining instruction. Is this expected?
+ MachineInstr* DefMI = MRI->getVRegDef(SrcReg);
+ if (!DefMI)
+ continue;
+
+ MachineBasicBlock* PredBB = PHI->getOperand(i + 1).getMBB();
+
+ // A copy may have already been inserted in the predecessor in the case of a
+ // block with multiple incoming edges.
+ if (!MBBsInsertedInto.insert(PredBB))
+ continue;
+
+ MachineBasicBlock::iterator
+ CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
+ MachineInstr* CopyInstr = BuildMI(*PredBB,
+ CopyInsertPoint,
+ PHI->getDebugLoc(),
+ TII->get(TargetOpcode::COPY),
+ CopyReg).addReg(SrcReg, 0, SrcSubReg);
+ LI->InsertMachineInstrInMaps(CopyInstr);
+
+ // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
+ // the newly added range.
+ LI->addLiveRangeToEndOfBlock(CopyReg, CopyInstr);
+ InsertedCopies.insert(std::make_pair(PredBB, SrcReg));
+
+ // If SrcReg is not live beyond the PHI, trim its interval so that it is no
+ // longer live-in to MBB. Note that SrcReg may appear in other PHIs that are
+ // processed later, but this is still correct to do at this point because we
+ // never rely on LiveIntervals being correct while inserting copies.
+ // FIXME: Should this just count uses at PHIs like the normal PHIElimination
+ // pass does?
+ LiveInterval& SrcLI = LI->getInterval(SrcReg);
+ SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
+ SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
+ SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
+ if (SrcLI.liveAt(MBBStartIndex) && SrcLI.expiredAt(NextInstrIndex))
+ SrcLI.removeRange(MBBStartIndex, PHIIndex, true);
+ }
}
projects / oota-llvm.git / blobdiff