#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);
}
-/// InsertNewPHI - Insert an empty PHI 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 PHI instruction.
static
-MachineInstr *InsertNewPHI(MachineBasicBlock *BB, const TargetRegisterClass *RC,
- MachineRegisterInfo *MRI, const TargetInstrInfo *TII) {
+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.
+static
+MachineInstr *InsertNewDef(unsigned Opcode,
+ MachineBasicBlock *BB, MachineBasicBlock::iterator I,
+ const TargetRegisterClass *RC,
+ MachineRegisterInfo *MRI, const TargetInstrInfo *TII) {
unsigned NewVR = MRI->createVirtualRegister(RC);
- return BuildMI(*BB, BB->front(), BB->front().getDebugLoc(),
- TII->get(TargetInstrInfo::PHI), 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);
-
- if (BB->pred_empty())
- llvm_unreachable("Unreachable block!");
+ 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(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 = InsertNewPHI(BB, 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 = InsertNewPHI(BB, VRC, MRI, TII);
+ 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;
return NewVR;
}
- if (BB->pred_empty())
- llvm_unreachable("Unreachable block!");
+ // 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()) {
+ // 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
/// this block is involved in a loop, a no-entry PHI node will have been
/// inserted as InsertedVal. Otherwise, we'll still have the null we inserted
/// above.
- unsigned InsertedVal = AvailableVals[BB];
+ unsigned &InsertedVal = AvailableVals[BB];
// If all the predecessor values are the same then we don't need to insert a
// PHI. This is the simple and common case.
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();
- } else {
- InsertedVal = SingularValue;
}
+ InsertedVal = SingularValue;
+
// Drop the entries we added in IncomingPredInfo to restore the stack.
IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry,
IncomingPredInfo.end());
// Otherwise, we do need a PHI: insert one now if we don't already have one.
MachineInstr *InsertedPHI;
if (InsertedVal == 0) {
- InsertedPHI = InsertNewPHI(BB, VRC, MRI, TII);
+ 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 = MRI->getVRegDef(InsertedVal);
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);
}
return InsertedVal;
-
}
projects / oota-llvm.git / blobdiff