MachineSSAUpdater.cpp [plain text]
#include "llvm/CodeGen/MachineSSAUpdater.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/AlignOf.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
using namespace llvm;
typedef DenseMap<MachineBasicBlock*, unsigned> AvailableValsTy;
static AvailableValsTy &getAvailableVals(void *AV) {
return *static_cast<AvailableValsTy*>(AV);
}
MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF,
SmallVectorImpl<MachineInstr*> *NewPHI)
: AV(0), InsertedPHIs(NewPHI) {
TII = MF.getTarget().getInstrInfo();
MRI = &MF.getRegInfo();
}
MachineSSAUpdater::~MachineSSAUpdater() {
delete static_cast<AvailableValsTy*>(AV);
}
void MachineSSAUpdater::Initialize(unsigned V) {
if (AV == 0)
AV = new AvailableValsTy();
else
getAvailableVals(AV).clear();
VR = V;
VRC = MRI->getRegClass(VR);
}
bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const {
return getAvailableVals(AV).count(BB);
}
void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) {
getAvailableVals(AV)[BB] = V;
}
unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) {
return GetValueAtEndOfBlockInternal(BB);
}
static
unsigned LookForIdenticalPHI(MachineBasicBlock *BB,
SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> &PredValues) {
if (BB->empty())
return 0;
MachineBasicBlock::iterator I = BB->begin();
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;
}
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, I, DebugLoc(), TII->get(Opcode), NewVR);
}
unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) {
if (!HasValueForBlock(BB))
return GetValueAtEndOfBlockInternal(BB);
if (BB->pred_empty()) {
MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
BB, BB->getFirstTerminator(),
VRC, MRI, TII);
return NewDef->getOperand(0).getReg();
}
SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues;
unsigned SingularValue = 0;
bool isFirstPred = true;
for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
E = BB->pred_end(); PI != E; ++PI) {
MachineBasicBlock *PredBB = *PI;
unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB);
PredValues.push_back(std::make_pair(PredBB, PredVal));
if (isFirstPred) {
SingularValue = PredVal;
isFirstPred = false;
} else if (PredVal != SingularValue)
SingularValue = 0;
}
if (SingularValue != 0)
return SingularValue;
unsigned DupPHI = LookForIdenticalPHI(BB, PredValues);
if (DupPHI)
return DupPHI;
MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin();
MachineInstr *InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB,
Loc, VRC, MRI, TII);
MachineInstrBuilder MIB(InsertedPHI);
for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
MIB.addReg(PredValues[i].second).addMBB(PredValues[i].first);
if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {
InsertedPHI->eraseFromParent();
return ConstVal;
}
if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
return InsertedPHI->getOperand(0).getReg();
}
static
MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI,
MachineOperand *U) {
for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
if (&MI->getOperand(i) == U)
return MI->getOperand(i+1).getMBB();
}
llvm_unreachable("MachineOperand::getParent() failure?");
}
void MachineSSAUpdater::RewriteUse(MachineOperand &U) {
MachineInstr *UseMI = U.getParent();
unsigned NewVR = 0;
if (UseMI->isPHI()) {
MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U);
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;
}
namespace llvm {
template<>
class SSAUpdaterTraits<MachineSSAUpdater> {
public:
typedef MachineBasicBlock BlkT;
typedef unsigned ValT;
typedef MachineInstr PhiT;
typedef MachineBasicBlock::succ_iterator BlkSucc_iterator;
static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
class PHI_iterator {
private:
MachineInstr *PHI;
unsigned idx;
public:
explicit PHI_iterator(MachineInstr *P) : PHI(P), idx(1) {}
PHI_iterator(MachineInstr *P, bool) : PHI(P), idx(PHI->getNumOperands()) {}
PHI_iterator &operator++() { idx += 2; return *this; }
bool operator==(const PHI_iterator& x) const { return idx == x.idx; }
bool operator!=(const PHI_iterator& x) const { return !operator==(x); }
unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); }
MachineBasicBlock *getIncomingBlock() {
return PHI->getOperand(idx+1).getMBB();
}
};
static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
static inline PHI_iterator PHI_end(PhiT *PHI) {
return PHI_iterator(PHI, true);
}
static void FindPredecessorBlocks(MachineBasicBlock *BB,
SmallVectorImpl<MachineBasicBlock*> *Preds){
for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
E = BB->pred_end(); PI != E; ++PI)
Preds->push_back(*PI);
}
static unsigned GetUndefVal(MachineBasicBlock *BB,
MachineSSAUpdater *Updater) {
MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
BB, BB->getFirstTerminator(),
Updater->VRC, Updater->MRI,
Updater->TII);
return NewDef->getOperand(0).getReg();
}
static unsigned CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds,
MachineSSAUpdater *Updater) {
MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin();
MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc,
Updater->VRC, Updater->MRI,
Updater->TII);
return PHI->getOperand(0).getReg();
}
static void AddPHIOperand(MachineInstr *PHI, unsigned Val,
MachineBasicBlock *Pred) {
PHI->addOperand(MachineOperand::CreateReg(Val, false));
PHI->addOperand(MachineOperand::CreateMBB(Pred));
}
static MachineInstr *InstrIsPHI(MachineInstr *I) {
if (I && I->isPHI())
return I;
return 0;
}
static MachineInstr *ValueIsPHI(unsigned Val, MachineSSAUpdater *Updater) {
return InstrIsPHI(Updater->MRI->getVRegDef(Val));
}
static MachineInstr *ValueIsNewPHI(unsigned Val, MachineSSAUpdater *Updater) {
MachineInstr *PHI = ValueIsPHI(Val, Updater);
if (PHI && PHI->getNumOperands() <= 1)
return PHI;
return 0;
}
static unsigned GetPHIValue(MachineInstr *PHI) {
return PHI->getOperand(0).getReg();
}
};
}
unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){
AvailableValsTy &AvailableVals = getAvailableVals(AV);
if (unsigned V = AvailableVals[BB])
return V;
SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
return Impl.GetValue(BB);
}