X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineBasicBlock.cpp;h=64134ce59e954fdd85fc3f01d0f3db0af729066f;hb=651d85c2f20563b33a330dfadf746169bf290eca;hp=7fbdb128fd405c5defe926abdb078998245e0d6a;hpb=0ba90f3e34b826b039bdfece1415ef032c4ad3f5;p=oota-llvm.git diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 7fbdb128fd4..64134ce59e9 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -14,13 +14,18 @@ #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/BasicBlock.h" #include "llvm/CodeGen/MachineFunction.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetData.h" #include "llvm/Target/TargetInstrDesc.h" +#include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Assembly/Writer.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/Support/Debug.h" #include "llvm/Support/LeakDetector.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Assembly/Writer.h" #include using namespace llvm; @@ -34,6 +39,18 @@ MachineBasicBlock::~MachineBasicBlock() { LeakDetector::removeGarbageObject(this); } +/// getSymbol - Return the MCSymbol for this basic block. +/// +MCSymbol *MachineBasicBlock::getSymbol(MCContext &Ctx) const { + SmallString<60> Name; + const MachineFunction *MF = getParent(); + raw_svector_ostream(Name) + << MF->getTarget().getMCAsmInfo()->getPrivateGlobalPrefix() << "BB" + << MF->getFunctionNumber() << '_' << getNumber(); + return Ctx.GetOrCreateSymbol(Name.str()); +} + + raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { MBB.print(OS); return OS; @@ -126,38 +143,8 @@ MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { return I; } -/// isOnlyReachableViaFallthough - Return true if this basic block has -/// exactly one predecessor and the control transfer mechanism between -/// the predecessor and this block is a fall-through. -bool MachineBasicBlock::isOnlyReachableByFallthrough() const { - // If this is a landing pad, it isn't a fall through. If it has no preds, - // then nothing falls through to it. - if (isLandingPad() || pred_empty()) - return false; - - // If there isn't exactly one predecessor, it can't be a fall through. - const_pred_iterator PI = pred_begin(), PI2 = PI; - ++PI2; - if (PI2 != pred_end()) - return false; - - // The predecessor has to be immediately before this block. - const MachineBasicBlock *Pred = *PI; - - if (!Pred->isLayoutSuccessor(this)) - return false; - - // If the block is completely empty, then it definitely does fall through. - if (Pred->empty()) - return true; - - // Otherwise, check the last instruction. - const MachineInstr &LastInst = Pred->back(); - return !LastInst.getDesc().isBarrier(); -} - void MachineBasicBlock::dump() const { - print(errs()); + print(dbgs()); } static inline void OutputReg(raw_ostream &os, unsigned RegNo, @@ -171,6 +158,13 @@ static inline void OutputReg(raw_ostream &os, unsigned RegNo, os << " %reg" << RegNo; } +StringRef MachineBasicBlock::getName() const { + if (const BasicBlock *LBB = getBasicBlock()) + return LBB->getName(); + else + return "(null)"; +} + void MachineBasicBlock::print(raw_ostream &OS) const { const MachineFunction *MF = getParent(); if (!MF) { @@ -242,6 +236,64 @@ void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { getParent()->splice(++BBI, this); } +void MachineBasicBlock::updateTerminator() { + const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); + // A block with no successors has no concerns with fall-through edges. + if (this->succ_empty()) return; + + MachineBasicBlock *TBB = 0, *FBB = 0; + SmallVector Cond; + bool B = TII->AnalyzeBranch(*this, TBB, FBB, Cond); + (void) B; + assert(!B && "UpdateTerminators requires analyzable predecessors!"); + if (Cond.empty()) { + if (TBB) { + // The block has an unconditional branch. If its successor is now + // its layout successor, delete the branch. + if (isLayoutSuccessor(TBB)) + TII->RemoveBranch(*this); + } else { + // The block has an unconditional fallthrough. If its successor is not + // its layout successor, insert a branch. + TBB = *succ_begin(); + if (!isLayoutSuccessor(TBB)) + TII->InsertBranch(*this, TBB, 0, Cond); + } + } else { + if (FBB) { + // The block has a non-fallthrough conditional branch. If one of its + // successors is its layout successor, rewrite it to a fallthrough + // conditional branch. + if (isLayoutSuccessor(TBB)) { + if (TII->ReverseBranchCondition(Cond)) + return; + TII->RemoveBranch(*this); + TII->InsertBranch(*this, FBB, 0, Cond); + } else if (isLayoutSuccessor(FBB)) { + TII->RemoveBranch(*this); + TII->InsertBranch(*this, TBB, 0, Cond); + } + } else { + // The block has a fallthrough conditional branch. + MachineBasicBlock *MBBA = *succ_begin(); + MachineBasicBlock *MBBB = *llvm::next(succ_begin()); + if (MBBA == TBB) std::swap(MBBB, MBBA); + if (isLayoutSuccessor(TBB)) { + if (TII->ReverseBranchCondition(Cond)) { + // We can't reverse the condition, add an unconditional branch. + Cond.clear(); + TII->InsertBranch(*this, MBBA, 0, Cond); + return; + } + TII->RemoveBranch(*this); + TII->InsertBranch(*this, MBBA, 0, Cond); + } else if (!isLayoutSuccessor(MBBA)) { + TII->RemoveBranch(*this); + TII->InsertBranch(*this, TBB, MBBA, Cond); + } + } + } +} void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) { Successors.push_back(succ); @@ -293,7 +345,52 @@ bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { MachineFunction::const_iterator I(this); - return next(I) == MachineFunction::const_iterator(MBB); + return llvm::next(I) == MachineFunction::const_iterator(MBB); +} + +bool MachineBasicBlock::canFallThrough() { + MachineFunction::iterator Fallthrough = this; + ++Fallthrough; + // If FallthroughBlock is off the end of the function, it can't fall through. + if (Fallthrough == getParent()->end()) + return false; + + // If FallthroughBlock isn't a successor, no fallthrough is possible. + if (!isSuccessor(Fallthrough)) + return false; + + // Analyze the branches, if any, at the end of the block. + MachineBasicBlock *TBB = 0, *FBB = 0; + SmallVector Cond; + const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); + if (TII->AnalyzeBranch(*this, TBB, FBB, Cond)) { + // If we couldn't analyze the branch, examine the last instruction. + // If the block doesn't end in a known control barrier, assume fallthrough + // is possible. The isPredicable check is needed because this code can be + // called during IfConversion, where an instruction which is normally a + // Barrier is predicated and thus no longer an actual control barrier. This + // is over-conservative though, because if an instruction isn't actually + // predicated we could still treat it like a barrier. + return empty() || !back().getDesc().isBarrier() || + back().getDesc().isPredicable(); + } + + // If there is no branch, control always falls through. + if (TBB == 0) return true; + + // If there is some explicit branch to the fallthrough block, it can obviously + // reach, even though the branch should get folded to fall through implicitly. + if (MachineFunction::iterator(TBB) == Fallthrough || + MachineFunction::iterator(FBB) == Fallthrough) + return true; + + // If it's an unconditional branch to some block not the fall through, it + // doesn't fall through. + if (Cond.empty()) return false; + + // Otherwise, if it is conditional and has no explicit false block, it falls + // through. + return FBB == 0; } /// removeFromParent - This method unlinks 'this' from the containing function, @@ -339,29 +436,45 @@ void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the /// CFG to be inserted. If we have proven that MBB can only branch to DestA and -/// DestB, remove any other MBB successors from the CFG. DestA and DestB can -/// be null. +/// DestB, remove any other MBB successors from the CFG. DestA and DestB can be +/// null. +/// /// Besides DestA and DestB, retain other edges leading to LandingPads /// (currently there can be only one; we don't check or require that here). /// Note it is possible that DestA and/or DestB are LandingPads. bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, MachineBasicBlock *DestB, bool isCond) { + // The values of DestA and DestB frequently come from a call to the + // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial + // values from there. + // + // 1. If both DestA and DestB are null, then the block ends with no branches + // (it falls through to its successor). + // 2. If DestA is set, DestB is null, and isCond is false, then the block ends + // with only an unconditional branch. + // 3. If DestA is set, DestB is null, and isCond is true, then the block ends + // with a conditional branch that falls through to a successor (DestB). + // 4. If DestA and DestB is set and isCond is true, then the block ends with a + // conditional branch followed by an unconditional branch. DestA is the + // 'true' destination and DestB is the 'false' destination. + bool MadeChange = false; bool AddedFallThrough = false; - MachineFunction::iterator FallThru = next(MachineFunction::iterator(this)); + MachineFunction::iterator FallThru = + llvm::next(MachineFunction::iterator(this)); - // If this block ends with a conditional branch that falls through to its - // successor, set DestB as the successor. if (isCond) { + // If this block ends with a conditional branch that falls through to its + // successor, set DestB as the successor. if (DestB == 0 && FallThru != getParent()->end()) { DestB = FallThru; AddedFallThrough = true; } } else { // If this is an unconditional branch with no explicit dest, it must just be - // a fallthrough into DestB. + // a fallthrough into DestA. if (DestA == 0 && FallThru != getParent()->end()) { DestA = FallThru; AddedFallThrough = true; @@ -371,17 +484,15 @@ bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, MachineBasicBlock::succ_iterator SI = succ_begin(); MachineBasicBlock *OrigDestA = DestA, *OrigDestB = DestB; while (SI != succ_end()) { - if (*SI == DestA && DestA == DestB) { - DestA = DestB = 0; - ++SI; - } else if (*SI == DestA) { + const MachineBasicBlock *MBB = *SI; + if (MBB == DestA) { DestA = 0; ++SI; - } else if (*SI == DestB) { + } else if (MBB == DestB) { DestB = 0; ++SI; - } else if ((*SI)->isLandingPad() && - *SI!=OrigDestA && *SI!=OrigDestB) { + } else if (MBB->isLandingPad() && + MBB != OrigDestA && MBB != OrigDestB) { ++SI; } else { // Otherwise, this is a superfluous edge, remove it. @@ -389,11 +500,34 @@ bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, MadeChange = true; } } - if (!AddedFallThrough) { - assert(DestA == 0 && DestB == 0 && - "MachineCFG is missing edges!"); - } else if (isCond) { + + if (!AddedFallThrough) + assert(DestA == 0 && DestB == 0 && "MachineCFG is missing edges!"); + else if (isCond) assert(DestA == 0 && "MachineCFG is missing edges!"); - } + return MadeChange; } + +/// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping +/// any DBG_VALUE instructions. Return UnknownLoc if there is none. +DebugLoc +MachineBasicBlock::findDebugLoc(MachineBasicBlock::iterator &MBBI) { + DebugLoc DL; + MachineBasicBlock::iterator E = end(); + if (MBBI != E) { + // Skip debug declarations, we don't want a DebugLoc from them. + MachineBasicBlock::iterator MBBI2 = MBBI; + while (MBBI2 != E && MBBI2->isDebugValue()) + MBBI2++; + if (MBBI2 != E) + DL = MBBI2->getDebugLoc(); + } + return DL; +} + +void llvm::WriteAsOperand(raw_ostream &OS, const MachineBasicBlock *MBB, + bool t) { + OS << "BB#" << MBB->getNumber(); +} +