From: Owen Anderson Date: Mon, 4 Aug 2008 23:54:43 +0000 (+0000) Subject: - Fix SelectionDAG to generate correct CFGs. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=bd3ba461eb5578a81ba09ff7bd7eb271d1130196 - Fix SelectionDAG to generate correct CFGs. - Add a basic machine-level dead block eliminator. These two have to go together, since many other parts of the code generator are unable to handle the unreachable blocks otherwise created. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54333 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h index d02cfa645dc..e2bed5c2ef9 100644 --- a/include/llvm/CodeGen/LiveVariables.h +++ b/include/llvm/CodeGen/LiveVariables.h @@ -247,10 +247,8 @@ public: assert(Removed && "Register is not defined by this instruction!"); return true; } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - } + + void getAnalysisUsage(AnalysisUsage &AU) const; virtual void releaseMemory() { VirtRegInfo.clear(); diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index dd677fa5b13..412e9e3ad85 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -71,6 +71,10 @@ namespace llvm { /// register allocators. extern const PassInfo *const TwoAddressInstructionPassID; + /// UnreachableMachineBlockElimination pass - This pass removes unreachable + /// machine basic blocks. + extern const PassInfo *const UnreachableMachineBlockElimID; + /// Creates a register allocator as the user specified on the command line. /// FunctionPass *createRegisterAllocator(); diff --git a/include/llvm/Target/TargetOptions.h b/include/llvm/Target/TargetOptions.h index fa739507db0..6c3d88a43cd 100644 --- a/include/llvm/Target/TargetOptions.h +++ b/include/llvm/Target/TargetOptions.h @@ -101,6 +101,11 @@ namespace llvm { /// DisableJumpTables - This flag indicates jump tables should not be /// generated. extern bool DisableJumpTables; + + /// DisableCorrectBranchFolding - This flag indicates whether the instruction + /// selector should take care to update the CFG properly when + /// folding branches. + extern bool DisableCorrectBranchFolding; } // End llvm namespace #endif diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 82016ed5912..dbe650c0af8 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -29,6 +29,7 @@ #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" @@ -43,6 +44,12 @@ using namespace llvm; char LiveVariables::ID = 0; static RegisterPass X("livevars", "Live Variable Analysis"); + +void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredID(UnreachableMachineBlockElimID); + AU.setPreservesAll(); +} + void LiveVariables::VarInfo::dump() const { cerr << " Alive in blocks: "; for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i) diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 196d3bf39d0..6299bc4b851 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -1632,11 +1632,24 @@ void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) { } SDValue BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getControlRoot(), Cond, DAG.getBasicBlock(CB.TrueBB)); - if (CB.FalseBB == NextBlock) + + // If the branch was constant folded, fix up the CFG. + if (BrCond.getOpcode() == ISD::BR) { + if (!DisableCorrectBranchFolding) + CurMBB->removeSuccessor(CB.FalseBB); DAG.setRoot(BrCond); - else - DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond, - DAG.getBasicBlock(CB.FalseBB))); + } else { + // Otherwise, go ahead and insert the false branch. + if (BrCond == getControlRoot()) + if (!DisableCorrectBranchFolding) + CurMBB->removeSuccessor(CB.TrueBB); + + if (CB.FalseBB == NextBlock) + DAG.setRoot(BrCond); + else + DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond, + DAG.getBasicBlock(CB.FalseBB))); + } } /// visitJumpTable - Emit JumpTable node in the current MBB diff --git a/lib/CodeGen/UnreachableBlockElim.cpp b/lib/CodeGen/UnreachableBlockElim.cpp index 3ba920204ac..8286239096a 100644 --- a/lib/CodeGen/UnreachableBlockElim.cpp +++ b/lib/CodeGen/UnreachableBlockElim.cpp @@ -26,8 +26,10 @@ #include "llvm/Function.h" #include "llvm/Pass.h" #include "llvm/Type.h" +#include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Compiler.h" +#include "llvm/Target/TargetInstrInfo.h" #include "llvm/ADT/DepthFirstIterator.h" using namespace llvm; @@ -71,11 +73,93 @@ bool UnreachableBlockElim::runOnFunction(Function &F) { BB->dropAllReferences(); } - if (DeadBlocks.empty()) return false; + // Actually remove the blocks now. + for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) + DeadBlocks[i]->eraseFromParent(); + + return DeadBlocks.size(); +} + + +namespace { + class VISIBILITY_HIDDEN UnreachableMachineBlockElim : + public MachineFunctionPass { + virtual bool runOnMachineFunction(MachineFunction &F); + bool iterateOnFunction(MachineFunction& F); + + public: + static char ID; // Pass identification, replacement for typeid + UnreachableMachineBlockElim() : MachineFunctionPass((intptr_t)&ID) {} + }; +} +char UnreachableMachineBlockElim::ID = 0; + +static RegisterPass +Y("unreachable-mbb-elimination", + "Remove unreachable machine basic blocks"); + +const PassInfo *const llvm::UnreachableMachineBlockElimID = &Y; + +bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) { + bool changed = true; + bool result = false; + + while (changed) { + changed = iterateOnFunction(F); + result |= changed; + } + + if (result) + F.RenumberBlocks(); + + return result; +} + +bool UnreachableMachineBlockElim::iterateOnFunction(MachineFunction &F) { + std::set Reachable; + + // Mark all reachable blocks. + for (df_ext_iterator I = df_ext_begin(&F, Reachable), + E = df_ext_end(&F, Reachable); I != E; ++I) + /* Mark all reachable blocks */; + + // Loop over all dead blocks, remembering them and deleting all instructions + // in them. + std::vector DeadBlocks; + for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) + if (!Reachable.count(I)) { + MachineBasicBlock *BB = I; + DeadBlocks.push_back(BB); + + while (BB->succ_begin() != BB->succ_end()) { + MachineBasicBlock* succ = *BB->succ_begin(); + + MachineBasicBlock::iterator start = succ->begin(); + while (start != succ->end() && + start->getOpcode() == TargetInstrInfo::PHI) { + for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2) + if (start->getOperand(i).isMBB() && + start->getOperand(i).getMBB() == BB) { + start->RemoveOperand(i); + start->RemoveOperand(i-1); + } + + if (start->getNumOperands() == 1) { + MachineInstr* phi = start; + start++; + phi->eraseFromParent(); + } else + start++; + } + + BB->removeSuccessor(BB->succ_begin()); + } + } // Actually remove the blocks now. for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) - F.getBasicBlockList().erase(DeadBlocks[i]); + DeadBlocks[i]->eraseFromParent(); - return true; + return DeadBlocks.size(); } + diff --git a/lib/Target/TargetMachine.cpp b/lib/Target/TargetMachine.cpp index 600a120e867..29167631baa 100644 --- a/lib/Target/TargetMachine.cpp +++ b/lib/Target/TargetMachine.cpp @@ -40,6 +40,7 @@ namespace llvm { bool RealignStack; bool VerboseAsm; bool DisableJumpTables; + bool DisableCorrectBranchFolding; } static cl::opt PrintCode("print-machineinstrs", @@ -163,6 +164,11 @@ DisableSwitchTables(cl::Hidden, "disable-jump-tables", cl::location(DisableJumpTables), cl::init(false)); +static cl::opt +DisableCorrectISelFolding(cl::Hidden, "disable-correct-folding", +cl::desc("Do not perform correct branch folding in the instruction selector."), +cl::location(DisableCorrectBranchFolding), cl::init(false)); + //--------------------------------------------------------------------------- // TargetMachine Class //