#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
return GetValueAtEndOfBlockInternal(BB);
}
+static
+unsigned LookForIdenticalPHI(MachineBasicBlock *BB,
+ SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> &PredValues) {
+ if (BB->empty())
+ return 0;
+
+ MachineBasicBlock::iterator I = BB->front();
+ if (!I->isPHI())
+ return 0;
+
+ AvailableValsTy AVals;
+ for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
+ AVals[PredValues[i].first] = PredValues[i].second;
+ while (I != BB->end() && I->isPHI()) {
+ bool Same = true;
+ for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) {
+ unsigned SrcReg = I->getOperand(i).getReg();
+ MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB();
+ if (AVals[SrcBB] != SrcReg) {
+ Same = false;
+ break;
+ }
+ }
+ if (Same)
+ return I->getOperand(0).getReg();
+ ++I;
+ }
+ return 0;
+}
+
/// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define
/// a value of the given register class at the start of the specified basic
/// block. It returns the virtual register defined by the instruction.
const TargetRegisterClass *RC,
MachineRegisterInfo *MRI, const TargetInstrInfo *TII) {
unsigned NewVR = MRI->createVirtualRegister(RC);
- return BuildMI(*BB, I, DebugLoc::getUnknownLoc(), TII->get(Opcode), NewVR);
+ return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR);
}
-
/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
/// is live in the middle of the specified block.
///
// If there is no definition of the renamed variable in this block, just use
// GetValueAtEndOfBlock to do our work.
if (!getAvailableVals(AV).count(BB))
- return GetValueAtEndOfBlock(BB);
+ return GetValueAtEndOfBlockInternal(BB);
// If there are no predecessors, just return undef.
if (BB->pred_empty()) {
// Insert an implicit_def to represent an undef value.
- MachineInstr *NewDef = InsertNewDef(TargetInstrInfo::IMPLICIT_DEF,
+ MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
BB, BB->getFirstTerminator(),
VRC, MRI, TII);
return NewDef->getOperand(0).getReg();
if (SingularValue != 0)
return SingularValue;
+ // If an identical PHI is already in BB, just reuse it.
+ unsigned DupPHI = LookForIdenticalPHI(BB, PredValues);
+ if (DupPHI)
+ return DupPHI;
+
// Otherwise, we do need a PHI: insert one now.
- MachineInstr *InsertedPHI = InsertNewDef(TargetInstrInfo::PHI, BB,
- BB->front(), VRC, MRI, TII);
+ MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
+ MachineInstr *InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB,
+ Loc, VRC, MRI, TII);
// Fill in all the predecessors of the PHI.
MachineInstrBuilder MIB(InsertedPHI);
// If the client wants to know about all new instructions, tell it.
if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
- DEBUG(errs() << " Inserted PHI: " << *InsertedPHI << "\n");
+ DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
return InsertedPHI->getOperand(0).getReg();
}
void MachineSSAUpdater::RewriteUse(MachineOperand &U) {
MachineInstr *UseMI = U.getParent();
unsigned NewVR = 0;
- if (UseMI->getOpcode() == TargetInstrInfo::PHI) {
+ if (UseMI->isPHI()) {
MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U);
- NewVR = GetValueAtEndOfBlock(SourceBB);
+ NewVR = GetValueAtEndOfBlockInternal(SourceBB);
} else {
NewVR = GetValueInMiddleOfBlock(UseMI->getParent());
}
U.setReg(NewVR);
}
+void MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) {
+ MRI->replaceRegWith(OldReg, NewReg);
+
+ AvailableValsTy &AvailableVals = getAvailableVals(AV);
+ for (DenseMap<MachineBasicBlock*, unsigned>::iterator
+ I = AvailableVals.begin(), E = AvailableVals.end(); I != E; ++I)
+ if (I->second == OldReg)
+ I->second = NewReg;
+}
+
/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
/// for the specified BB and if so, return it. If not, construct SSA form by
/// walking predecessors inserting PHI nodes as needed until we get to a block
// that we have a cycle. Handle this by inserting a PHI node and returning
// it. When we get back to the first instance of the recursion we will fill
// in the PHI node.
- MachineInstr *NewPHI = InsertNewDef(TargetInstrInfo::PHI, BB, BB->front(),
+ MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
+ MachineInstr *NewPHI = InsertNewDef(TargetOpcode::PHI, BB, Loc,
VRC, MRI,TII);
unsigned NewVR = NewPHI->getOperand(0).getReg();
InsertRes.first->second = NewVR;
// be invalidated.
if (BB->pred_empty()) {
// Insert an implicit_def to represent an undef value.
- MachineInstr *NewDef = InsertNewDef(TargetInstrInfo::IMPLICIT_DEF,
+ MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
BB, BB->getFirstTerminator(),
VRC, MRI, TII);
return InsertRes.first->second = NewDef->getOperand(0).getReg();
MachineInstr *OldVal = MRI->getVRegDef(InsertedVal);
// Be careful about dead loops. These RAUW's also update InsertedVal.
assert(InsertedVal != SingularValue && "Dead loop?");
- MRI->replaceRegWith(InsertedVal, SingularValue);
+ ReplaceRegWith(InsertedVal, SingularValue);
OldVal->eraseFromParent();
}
// Otherwise, we do need a PHI: insert one now if we don't already have one.
MachineInstr *InsertedPHI;
if (InsertedVal == 0) {
- InsertedPHI = InsertNewDef(TargetInstrInfo::PHI, BB, BB->front(),
+ MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
+ InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, Loc,
VRC, MRI, TII);
InsertedVal = InsertedPHI->getOperand(0).getReg();
} else {
InsertedPHI->eraseFromParent();
InsertedVal = ConstVal;
} else {
- DEBUG(errs() << " Inserted PHI: " << *InsertedPHI << "\n");
+ DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
// If the client wants to know about all new instructions, tell it.
if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
projects / oota-llvm.git / blobdiff