X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineBasicBlock.cpp;h=64134ce59e954fdd85fc3f01d0f3db0af729066f;hb=651d85c2f20563b33a330dfadf746169bf290eca;hp=4d1370aed9827230e372df060405881a31d61894;hpb=dfbbf6e0232315b79805f13baab06828de24e558;p=oota-llvm.git diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 4d1370aed98..64134ce59e9 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -14,10 +14,16 @@ #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 @@ -33,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; @@ -125,51 +143,28 @@ 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, const TargetRegisterInfo *TRI = 0) { - if (!RegNo || TargetRegisterInfo::isPhysicalRegister(RegNo)) { + if (RegNo != 0 && TargetRegisterInfo::isPhysicalRegister(RegNo)) { if (TRI) os << " %" << TRI->get(RegNo).Name; else - os << " %mreg(" << RegNo << ")"; + os << " %physreg" << RegNo; } else 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) { @@ -178,19 +173,23 @@ void MachineBasicBlock::print(raw_ostream &OS) const { return; } - const BasicBlock *LBB = getBasicBlock(); + if (Alignment) { OS << "Alignment " << Alignment << "\n"; } + + OS << "BB#" << getNumber() << ": "; + + const char *Comma = ""; + if (const BasicBlock *LBB = getBasicBlock()) { + OS << Comma << "derived from LLVM BB "; + WriteAsOperand(OS, LBB, /*PrintType=*/false); + Comma = ", "; + } + if (isLandingPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; } + if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; } OS << '\n'; - if (LBB) OS << LBB->getName() << ": "; - OS << (const void*)this - << ", LLVM BB @" << (const void*) LBB << ", ID#" << getNumber(); - if (Alignment) OS << ", Alignment " << Alignment; - if (isLandingPad()) OS << ", EH LANDING PAD"; - if (hasAddressTaken()) OS << ", ADDRESS TAKEN"; - OS << ":\n"; const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo(); if (!livein_empty()) { - OS << "Live Ins:"; + OS << " Live Ins:"; for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) OutputReg(OS, *I, TRI); OS << '\n'; @@ -199,7 +198,7 @@ void MachineBasicBlock::print(raw_ostream &OS) const { if (!pred_empty()) { OS << " Predecessors according to CFG:"; for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI) - OS << ' ' << *PI << " (#" << (*PI)->getNumber() << ')'; + OS << " BB#" << (*PI)->getNumber(); OS << '\n'; } @@ -212,7 +211,7 @@ void MachineBasicBlock::print(raw_ostream &OS) const { if (!succ_empty()) { OS << " Successors according to CFG:"; for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) - OS << ' ' << *SI << " (#" << (*SI)->getNumber() << ')'; + OS << " BB#" << (*SI)->getNumber(); OS << '\n'; } } @@ -237,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); @@ -288,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, @@ -334,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; @@ -366,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. @@ -384,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(); +} +