From 229694f0ee630ceabe96a8bd48952f6740f928b2 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Thu, 3 Dec 2009 02:31:43 +0000 Subject: [PATCH] Fill out codegen SSA updater. It's not yet tested. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@90395 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/MachineInstr.h | 5 + include/llvm/CodeGen/MachineSSAUpdater.h | 29 ++- lib/CodeGen/MachineInstr.cpp | 14 ++ lib/CodeGen/MachineSSAUpdater.cpp | 237 ++++++++++++++++++++++- 4 files changed, 270 insertions(+), 15 deletions(-) diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h index c620449401d..87b67d6242d 100644 --- a/include/llvm/CodeGen/MachineInstr.h +++ b/include/llvm/CodeGen/MachineInstr.h @@ -320,6 +320,11 @@ public: /// loads the instruction does are invariant (if it does multiple loads). bool isInvariantLoad(AliasAnalysis *AA) const; + /// isConstantValuePHI - If the specified instruction is a PHI that always + /// merges together the same virtual register, return the register, otherwise + /// return 0. + unsigned isConstantValuePHI() const; + // // Debugging support // diff --git a/include/llvm/CodeGen/MachineSSAUpdater.h b/include/llvm/CodeGen/MachineSSAUpdater.h index a785ab8cfaa..ca8eca82a85 100644 --- a/include/llvm/CodeGen/MachineSSAUpdater.h +++ b/include/llvm/CodeGen/MachineSSAUpdater.h @@ -16,13 +16,18 @@ namespace llvm { class MachineBasicBlock; + class MachineFunction; class MachineInstr; + class MachineOperand; + class MachineRegisterInfo; + class TargetInstrInfo; + class TargetRegisterClass; template class SmallVectorImpl; -/// SSAUpdater - This class updates SSA form for a set of values defined in -/// multiple blocks. This is used when code duplication or another unstructured -/// transformation wants to rewrite a set of uses of one value with uses of a -/// set of values. +/// MachineSSAUpdater - This class updates SSA form for a set of virtual +/// registers defined in multiple blocks. This is used when code duplication +/// or another unstructured transformation wants to rewrite a set of uses of one +/// vreg with uses of a set of vregs. class MachineSSAUpdater { /// AvailableVals - This keeps track of which value to use on a per-block /// basis. When we insert PHI nodes, we keep track of them here. @@ -35,18 +40,28 @@ class MachineSSAUpdater { //std::vector > IncomingPredInfo; void *IPI; + /// VR - Current virtual register whose uses are being updated. + unsigned VR; + + /// VRC - Register class of the current virtual register. + const TargetRegisterClass *VRC; + /// InsertedPHIs - If this is non-null, the MachineSSAUpdater adds all PHI /// nodes that it creates to the vector. SmallVectorImpl *InsertedPHIs; + + const TargetInstrInfo *TII; + MachineRegisterInfo *MRI; public: /// MachineSSAUpdater constructor. If InsertedPHIs is specified, it will be /// filled in with all PHI Nodes created by rewriting. - explicit MachineSSAUpdater(SmallVectorImpl *InsertedPHIs = 0); + explicit MachineSSAUpdater(MachineFunction &MF, + SmallVectorImpl *InsertedPHIs = 0); ~MachineSSAUpdater(); /// Initialize - Reset this object to get ready for a new set of SSA /// updates. - void Initialize(); + void Initialize(unsigned V); /// AddAvailableValue - Indicate that a rewritten value is available at the /// end of the specified block with the specified value. @@ -86,7 +101,7 @@ public: /// will not work if the use is supposed to be rewritten to a value defined in /// the same block as the use, but above it. Any 'AddAvailableValue's added /// for the use's block will be considered to be below it. - void RewriteUse(unsigned &U); + void RewriteUse(MachineOperand &U); private: unsigned GetValueAtEndOfBlockInternal(MachineBasicBlock *BB); diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp index f73a5a36211..ba9be6a8703 100644 --- a/lib/CodeGen/MachineInstr.cpp +++ b/lib/CodeGen/MachineInstr.cpp @@ -1058,6 +1058,20 @@ bool MachineInstr::isInvariantLoad(AliasAnalysis *AA) const { return true; } +/// isConstantValuePHI - If the specified instruction is a PHI that always +/// merges together the same virtual register, return the register, otherwise +/// return 0. +unsigned MachineInstr::isConstantValuePHI() const { + if (getOpcode() != TargetInstrInfo::PHI) + return 0; + + unsigned Reg = getOperand(1).getReg(); + for (unsigned i = 3, e = getNumOperands(); i < e; i += 2) + if (getOperand(i).getReg() != Reg) + return 0; + return Reg; +} + void MachineInstr::dump() const { errs() << " " << *this; } diff --git a/lib/CodeGen/MachineSSAUpdater.cpp b/lib/CodeGen/MachineSSAUpdater.cpp index c0eb170cfbb..bca3ffad583 100644 --- a/lib/CodeGen/MachineSSAUpdater.cpp +++ b/lib/CodeGen/MachineSSAUpdater.cpp @@ -7,16 +7,25 @@ // //===----------------------------------------------------------------------===// // -// This file implements the MachineSSAUpdater class. +// This file implements the MachineSSAUpdater class. It's based on SSAUpdater +// class in lib/Transforms/Utils. // //===----------------------------------------------------------------------===// #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/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; -typedef DenseMap AvailableValsTy; +typedef DenseMap AvailableValsTy; typedef std::vector > IncomingPredInfoTy; @@ -29,8 +38,12 @@ static IncomingPredInfoTy &getIncomingPredInfo(void *IPI) { } -MachineSSAUpdater::MachineSSAUpdater(SmallVectorImpl *NewPHI) - : AV(0), IPI(0), InsertedPHIs(NewPHI) {} +MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF, + SmallVectorImpl *NewPHI) + : AV(0), IPI(0), InsertedPHIs(NewPHI) { + TII = MF.getTarget().getInstrInfo(); + MRI = &MF.getRegInfo(); +} MachineSSAUpdater::~MachineSSAUpdater() { delete &getAvailableVals(AV); @@ -39,7 +52,7 @@ MachineSSAUpdater::~MachineSSAUpdater() { /// Initialize - Reset this object to get ready for a new set of SSA /// updates. ProtoValue is the value used to name PHI nodes. -void MachineSSAUpdater::Initialize() { +void MachineSSAUpdater::Initialize(unsigned V) { if (AV == 0) AV = new AvailableValsTy(); else @@ -49,6 +62,9 @@ void MachineSSAUpdater::Initialize() { IPI = new IncomingPredInfoTy(); else getIncomingPredInfo(IPI).clear(); + + VR = V; + VRC = MRI->getRegClass(VR); } /// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for @@ -69,6 +85,18 @@ unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) { 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 NewVR = MRI->createVirtualRegister(RC); + return BuildMI(*BB, BB->front(), BB->front().getDebugLoc(), + TII->get(TargetInstrInfo::PHI), NewVR); +} + + /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that /// is live in the middle of the specified block. /// @@ -89,14 +117,86 @@ unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) { /// merge the appropriate values, and this value isn't live out of the block. /// unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) { + // 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!"); + + // Otherwise, we have the hard case. Get the live-in values for each + // predecessor. + SmallVector, 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)); + + // Compute SingularValue. + if (isFirstPred) { + SingularValue = PredVal; + isFirstPred = false; + } else if (PredVal != SingularValue) + SingularValue = 0; + } + + // Otherwise, if all the merged values are the same, just use it. + if (SingularValue != 0) + return SingularValue; + + // Otherwise, we do need a PHI: insert one now. + MachineInstr *InsertedPHI = InsertNewPHI(BB, VRC, MRI, TII); + + // Fill in all the predecessors of the PHI. + MachineInstrBuilder MIB(InsertedPHI); + for (unsigned i = 0, e = PredValues.size(); i != e; ++i) + MIB.addReg(PredValues[i].second).addMBB(PredValues[i].first); + + // 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 (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) { + InsertedPHI->eraseFromParent(); + return ConstVal; + } + + // If the client wants to know about all new instructions, tell it. + if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); + + DEBUG(errs() << " 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?"); return 0; } /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, /// which use their value in the corresponding predecessor. -void MachineSSAUpdater::RewriteUse(unsigned &U) { -} +void MachineSSAUpdater::RewriteUse(MachineOperand &U) { + MachineInstr *UseMI = U.getParent(); + unsigned NewVR = 0; + if (UseMI->getOpcode() == TargetInstrInfo::PHI) { + MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U); + NewVR = GetValueAtEndOfBlock(SourceBB); + } else { + NewVR = GetValueInMiddleOfBlock(UseMI->getParent()); + } + U.setReg(NewVR); +} /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry /// for the specified BB and if so, return it. If not, construct SSA form by @@ -104,5 +204,126 @@ void MachineSSAUpdater::RewriteUse(unsigned &U) { /// where the value is available. /// unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){ - return 0; + AvailableValsTy &AvailableVals = getAvailableVals(AV); + + // Query AvailableVals by doing an insertion of null. + std::pair InsertRes = + AvailableVals.insert(std::make_pair(BB, 0)); + + // Handle the case when the insertion fails because we have already seen BB. + if (!InsertRes.second) { + // If the insertion failed, there are two cases. The first case is that the + // value is already available for the specified block. If we get this, just + // return the value. + if (InsertRes.first->second != 0) + return InsertRes.first->second; + + // Otherwise, if the value we find is null, then this is the value is not + // known but it is being computed elsewhere in our recursion. This means + // 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); + unsigned NewVR = NewPHI->getOperand(0).getReg(); + InsertRes.first->second = NewVR; + return NewVR; + } + + if (BB->pred_empty()) + llvm_unreachable("Unreachable block!"); + + // 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 + // value is in this block, we have to recurse through our predecessors. + // + // While we're walking our predecessors, we keep track of them in a vector, + // then insert a PHI node in the end if we actually need one. We could use a + // smallvector here, but that would take a lot of stack space for every level + // of the recursion, just use IncomingPredInfo as an explicit stack. + IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI); + unsigned FirstPredInfoEntry = IncomingPredInfo.size(); + + // As we're walking the predecessors, keep track of whether they are all + // producing the same value. If so, this value will capture it, if not, it + // will get reset to null. We distinguish the no-predecessor case explicitly + // below. + 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); + IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); + + // Compute SingularValue. + if (isFirstPred) { + SingularValue = PredVal; + isFirstPred = false; + } else if (PredVal != SingularValue) + SingularValue = 0; + } + + /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If + /// 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]; + + // If all the predecessor values are the same then we don't need to insert a + // PHI. This is the simple and common case. + if (SingularValue) { + // If a PHI node got inserted, replace it with the singlar value and delete + // it. + if (InsertedVal) { + 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); + OldVal->eraseFromParent(); + } else { + InsertedVal = SingularValue; + } + + // Drop the entries we added in IncomingPredInfo to restore the stack. + IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, + IncomingPredInfo.end()); + return InsertedVal; + } + + + // 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); + InsertedVal = InsertedPHI->getOperand(0).getReg(); + } else { + InsertedPHI = MRI->getVRegDef(InsertedVal); + } + + // Fill in all the predecessors of the PHI. + MachineInstrBuilder MIB(InsertedPHI); + for (IncomingPredInfoTy::iterator I = + IncomingPredInfo.begin()+FirstPredInfoEntry, + 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, + IncomingPredInfo.end()); + + // 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 (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) { + MRI->replaceRegWith(InsertedVal, ConstVal); + InsertedPHI->eraseFromParent(); + InsertedVal = ConstVal; + } else { + DEBUG(errs() << " Inserted PHI: " << *InsertedPHI << "\n"); + + // If the client wants to know about all new instructions, tell it. + if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); + } + + return InsertedVal; + } -- 2.34.1