#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, I->getDebugLoc(), 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())
- return ~0U; // Sentinel value representing undef.
+ if (BB->pred_empty()) {
+ // Insert an implicit_def to represent an undef value.
+ MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
+ BB, BB->getFirstTerminator(),
+ VRC, MRI, TII);
+ return NewDef->getOperand(0).getReg();
+ }
// Otherwise, we have the hard case. Get the live-in values for each
// predecessor.
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);
- // Insert an implicit_def to represent an undef value.
- MachineInstr *NewDef = InsertNewDef(TargetInstrInfo::IMPLICIT_DEF,
- SourceBB,SourceBB->getFirstTerminator(),
- VRC, MRI, TII);
- NewVR = NewDef->getOperand(0).getReg();
+ NewVR = GetValueAtEndOfBlockInternal(SourceBB);
} else {
NewVR = GetValueInMiddleOfBlock(UseMI->getParent());
- if (NewVR == ~0U) {
- // Insert an implicit_def to represent an undef value.
- MachineInstr *NewDef = InsertNewDef(TargetInstrInfo::IMPLICIT_DEF,
- UseMI->getParent(), UseMI,
- VRC, MRI, TII);
- NewVR = NewDef->getOperand(0).getReg();
- }
}
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;
// If there are no predecessors, then we must have found an unreachable block
// just return 'undef'. Since there are no predecessors, InsertRes must not
// be invalidated.
- if (BB->pred_empty())
- return InsertRes.first->second = ~0U; // Sentinel value representing undef.
+ if (BB->pred_empty()) {
+ // Insert an implicit_def to represent an undef value.
+ MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
+ BB, BB->getFirstTerminator(),
+ VRC, MRI, TII);
+ return InsertRes.first->second = NewDef->getOperand(0).getReg();
+ }
// Okay, the value isn't in the map and we just inserted a null in the entry
// to indicate that we're processing the block. Since we have no idea what
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 {
}
// Fill in all the predecessors of the PHI.
- bool IsUndef = true;
MachineInstrBuilder MIB(InsertedPHI);
for (IncomingPredInfoTy::iterator I =
IncomingPredInfo.begin()+FirstPredInfoEntry,
- E = IncomingPredInfo.end(); I != E; ++I) {
- if (I->second == ~0U)
- continue;
- IsUndef = false;
+ E = IncomingPredInfo.end(); I != E; ++I)
MIB.addReg(I->second).addMBB(I->first);
- }
// Drop the entries we added in IncomingPredInfo to restore the stack.
IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry,
// See if the PHI node can be merged to a single value. This can happen in
// loop cases when we get a PHI of itself and one other value.
- if (IsUndef) {
- InsertedPHI->eraseFromParent();
- InsertedVal = ~0U;
- } else if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {
+ if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {
MRI->replaceRegWith(InsertedVal, ConstVal);
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