LLVM API Documentation

DwarfEHPrepare.cpp

Go to the documentation of this file.
00001 //===-- DwarfEHPrepare - Prepare exception handling for code generation ---===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass mulches exception handling code into a form adapted to code
00011 // generation.  Required if using dwarf exception handling.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "dwarfehprepare"
00016 #include "llvm/ADT/Statistic.h"
00017 #include "llvm/Analysis/Dominators.h"
00018 #include "llvm/CodeGen/Passes.h"
00019 #include "llvm/Function.h"
00020 #include "llvm/Instructions.h"
00021 #include "llvm/IntrinsicInst.h"
00022 #include "llvm/Module.h"
00023 #include "llvm/Pass.h"
00024 #include "llvm/Support/Compiler.h"
00025 #include "llvm/Target/TargetLowering.h"
00026 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00027 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
00028 using namespace llvm;
00029 
00030 STATISTIC(NumLandingPadsSplit,     "Number of landing pads split");
00031 STATISTIC(NumUnwindsLowered,       "Number of unwind instructions lowered");
00032 STATISTIC(NumExceptionValuesMoved, "Number of eh.exception calls moved");
00033 STATISTIC(NumStackTempsIntroduced, "Number of stack temporaries introduced");
00034 
00035 namespace {
00036   class VISIBILITY_HIDDEN DwarfEHPrepare : public FunctionPass {
00037     const TargetLowering *TLI;
00038     bool CompileFast;
00039 
00040     // The eh.exception intrinsic.
00041     Function *ExceptionValueIntrinsic;
00042 
00043     // _Unwind_Resume or the target equivalent.
00044     Constant *RewindFunction;
00045 
00046     // Dominator info is used when turning stack temporaries into registers.
00047     DominatorTree *DT;
00048     DominanceFrontier *DF;
00049 
00050     // The function we are running on.
00051     Function *F;
00052 
00053     // The landing pads for this function.
00054     typedef SmallPtrSet<BasicBlock*, 8> BBSet;
00055     BBSet LandingPads;
00056 
00057     // Stack temporary used to hold eh.exception values.
00058     AllocaInst *ExceptionValueVar;
00059 
00060     bool NormalizeLandingPads();
00061     bool LowerUnwinds();
00062     bool MoveExceptionValueCalls();
00063     bool FinishStackTemporaries();
00064     bool PromoteStackTemporaries();
00065 
00066     Instruction *CreateExceptionValueCall(BasicBlock *BB);
00067     Instruction *CreateValueLoad(BasicBlock *BB);
00068 
00069     /// CreateReadOfExceptionValue - Return the result of the eh.exception
00070     /// intrinsic by calling the intrinsic if in a landing pad, or loading
00071     /// it from the exception value variable otherwise.
00072     Instruction *CreateReadOfExceptionValue(BasicBlock *BB) {
00073       return LandingPads.count(BB) ?
00074         CreateExceptionValueCall(BB) : CreateValueLoad(BB);
00075     }
00076 
00077   public:
00078     static char ID; // Pass identification, replacement for typeid.
00079     DwarfEHPrepare(const TargetLowering *tli, bool fast) :
00080       FunctionPass(&ID), TLI(tli), CompileFast(fast),
00081       ExceptionValueIntrinsic(0), RewindFunction(0) {}
00082 
00083     virtual bool runOnFunction(Function &Fn);
00084 
00085     // getAnalysisUsage - We need dominance frontiers for memory promotion.
00086     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00087       if (!CompileFast)
00088         AU.addRequired<DominatorTree>();
00089       AU.addPreserved<DominatorTree>();
00090       if (!CompileFast)
00091         AU.addRequired<DominanceFrontier>();
00092       AU.addPreserved<DominanceFrontier>();
00093     }
00094 
00095     const char *getPassName() const {
00096       return "Exception handling preparation";
00097     }
00098 
00099   };
00100 } // end anonymous namespace
00101 
00102 char DwarfEHPrepare::ID = 0;
00103 
00104 FunctionPass *llvm::createDwarfEHPass(const TargetLowering *tli, bool fast) {
00105   return new DwarfEHPrepare(tli, fast);
00106 }
00107 
00108 /// NormalizeLandingPads - Normalize and discover landing pads, noting them
00109 /// in the LandingPads set.  A landing pad is normal if the only CFG edges
00110 /// that end at it are unwind edges from invoke instructions.
00111 /// Abnormal landing pads are fixed up by redirecting all unwind edges to
00112 /// a new basic block which falls through to the original.
00113 bool DwarfEHPrepare::NormalizeLandingPads() {
00114   bool Changed = false;
00115 
00116   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
00117     TerminatorInst *TI = I->getTerminator();
00118     if (!isa<InvokeInst>(TI))
00119       continue;
00120     BasicBlock *LPad = TI->getSuccessor(1);
00121     // Skip landing pads that have already been normalized.
00122     if (LandingPads.count(LPad))
00123       continue;
00124 
00125     // Check that only invoke unwind edges end at the landing pad.
00126     bool OnlyUnwoundTo = true;
00127     for (pred_iterator PI = pred_begin(LPad), PE = pred_end(LPad);
00128          PI != PE; ++PI) {
00129       TerminatorInst *PT = (*PI)->getTerminator();
00130       if (!isa<InvokeInst>(PT) || LPad == PT->getSuccessor(0)) {
00131         OnlyUnwoundTo = false;
00132         break;
00133       }
00134     }
00135     if (OnlyUnwoundTo) {
00136       // Only unwind edges lead to the landing pad.  Remember the landing pad.
00137       LandingPads.insert(LPad);
00138       continue;
00139     }
00140 
00141     // At least one normal edge ends at the landing pad.  Redirect the unwind
00142     // edges to a new basic block which falls through into this one.
00143 
00144     // Create the new basic block.
00145     BasicBlock *NewBB = BasicBlock::Create(F->getContext(),
00146                                            LPad->getName() + "_unwind_edge");
00147 
00148     // Insert it into the function right before the original landing pad.
00149     LPad->getParent()->getBasicBlockList().insert(LPad, NewBB);
00150 
00151     // Redirect unwind edges from the original landing pad to NewBB.
00152     for (pred_iterator PI = pred_begin(LPad), PE = pred_end(LPad); PI != PE; ) {
00153       TerminatorInst *PT = (*PI++)->getTerminator();
00154       if (isa<InvokeInst>(PT) && PT->getSuccessor(1) == LPad)
00155         // Unwind to the new block.
00156         PT->setSuccessor(1, NewBB);
00157     }
00158 
00159     // If there are any PHI nodes in LPad, we need to update them so that they
00160     // merge incoming values from NewBB instead.
00161     for (BasicBlock::iterator II = LPad->begin(); isa<PHINode>(II); ++II) {
00162       PHINode *PN = cast<PHINode>(II);
00163       pred_iterator PB = pred_begin(NewBB), PE = pred_end(NewBB);
00164 
00165       // Check to see if all of the values coming in via unwind edges are the
00166       // same.  If so, we don't need to create a new PHI node.
00167       Value *InVal = PN->getIncomingValueForBlock(*PB);
00168       for (pred_iterator PI = PB; PI != PE; ++PI) {
00169         if (PI != PB && InVal != PN->getIncomingValueForBlock(*PI)) {
00170           InVal = 0;
00171           break;
00172         }
00173       }
00174 
00175       if (InVal == 0) {
00176         // Different unwind edges have different values.  Create a new PHI node
00177         // in NewBB.
00178         PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".unwind",
00179                                          NewBB);
00180         // Add an entry for each unwind edge, using the value from the old PHI.
00181         for (pred_iterator PI = PB; PI != PE; ++PI)
00182           NewPN->addIncoming(PN->getIncomingValueForBlock(*PI), *PI);
00183 
00184         // Now use this new PHI as the common incoming value for NewBB in PN.
00185         InVal = NewPN;
00186       }
00187 
00188       // Revector exactly one entry in the PHI node to come from NewBB
00189       // and delete all other entries that come from unwind edges.  If
00190       // there are both normal and unwind edges from the same predecessor,
00191       // this leaves an entry for the normal edge.
00192       for (pred_iterator PI = PB; PI != PE; ++PI)
00193         PN->removeIncomingValue(*PI);
00194       PN->addIncoming(InVal, NewBB);
00195     }
00196 
00197     // Add a fallthrough from NewBB to the original landing pad.
00198     BranchInst::Create(LPad, NewBB);
00199 
00200     // Now update DominatorTree and DominanceFrontier analysis information.
00201     if (DT)
00202       DT->splitBlock(NewBB);
00203     if (DF)
00204       DF->splitBlock(NewBB);
00205 
00206     // Remember the newly constructed landing pad.  The original landing pad
00207     // LPad is no longer a landing pad now that all unwind edges have been
00208     // revectored to NewBB.
00209     LandingPads.insert(NewBB);
00210     ++NumLandingPadsSplit;
00211     Changed = true;
00212   }
00213 
00214   return Changed;
00215 }
00216 
00217 /// LowerUnwinds - Turn unwind instructions into calls to _Unwind_Resume,
00218 /// rethrowing any previously caught exception.  This will crash horribly
00219 /// at runtime if there is no such exception: using unwind to throw a new
00220 /// exception is currently not supported.
00221 bool DwarfEHPrepare::LowerUnwinds() {
00222   bool Changed = false;
00223 
00224   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
00225     TerminatorInst *TI = I->getTerminator();
00226     if (!isa<UnwindInst>(TI))
00227       continue;
00228 
00229     // Replace the unwind instruction with a call to _Unwind_Resume (or the
00230     // appropriate target equivalent) followed by an UnreachableInst.
00231 
00232     // Find the rewind function if we didn't already.
00233     if (!RewindFunction) {
00234       std::vector<const Type*> Params(1,
00235                      PointerType::getUnqual(Type::getInt8Ty(TI->getContext())));
00236       FunctionType *FTy = FunctionType::get(Type::getVoidTy(TI->getContext()),
00237                                             Params, false);
00238       const char *RewindName = TLI->getLibcallName(RTLIB::UNWIND_RESUME);
00239       RewindFunction = F->getParent()->getOrInsertFunction(RewindName, FTy);
00240     }
00241 
00242     // Create the call...
00243     CallInst::Create(RewindFunction, CreateReadOfExceptionValue(I), "", TI);
00244     // ...followed by an UnreachableInst.
00245     new UnreachableInst(TI->getContext(), TI);
00246 
00247     // Nuke the unwind instruction.
00248     TI->eraseFromParent();
00249     ++NumUnwindsLowered;
00250     Changed = true;
00251   }
00252 
00253   return Changed;
00254 }
00255 
00256 /// MoveExceptionValueCalls - Ensure that eh.exception is only ever called from
00257 /// landing pads by replacing calls outside of landing pads with loads from a
00258 /// stack temporary.  Move eh.exception calls inside landing pads to the start
00259 /// of the landing pad (optional, but may make things simpler for later passes).
00260 bool DwarfEHPrepare::MoveExceptionValueCalls() {
00261   // If the eh.exception intrinsic is not declared in the module then there is
00262   // nothing to do.  Speed up compilation by checking for this common case.
00263   if (!ExceptionValueIntrinsic &&
00264       !F->getParent()->getFunction(Intrinsic::getName(Intrinsic::eh_exception)))
00265     return false;
00266 
00267   bool Changed = false;
00268 
00269   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
00270     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
00271       if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
00272         if (CI->getIntrinsicID() == Intrinsic::eh_exception) {
00273           if (!CI->use_empty()) {
00274             Value *ExceptionValue = CreateReadOfExceptionValue(BB);
00275             if (CI == ExceptionValue) {
00276               // The call was at the start of a landing pad - leave it alone.
00277               assert(LandingPads.count(BB) &&
00278                      "Created eh.exception call outside landing pad!");
00279               continue;
00280             }
00281             CI->replaceAllUsesWith(ExceptionValue);
00282           }
00283           CI->eraseFromParent();
00284           ++NumExceptionValuesMoved;
00285           Changed = true;
00286         }
00287   }
00288 
00289   return Changed;
00290 }
00291 
00292 /// FinishStackTemporaries - If we introduced a stack variable to hold the
00293 /// exception value then initialize it in each landing pad.
00294 bool DwarfEHPrepare::FinishStackTemporaries() {
00295   if (!ExceptionValueVar)
00296     // Nothing to do.
00297     return false;
00298 
00299   bool Changed = false;
00300 
00301   // Make sure that there is a store of the exception value at the start of
00302   // each landing pad.
00303   for (BBSet::iterator LI = LandingPads.begin(), LE = LandingPads.end();
00304        LI != LE; ++LI) {
00305     Instruction *ExceptionValue = CreateReadOfExceptionValue(*LI);
00306     Instruction *Store = new StoreInst(ExceptionValue, ExceptionValueVar);
00307     Store->insertAfter(ExceptionValue);
00308     Changed = true;
00309   }
00310 
00311   return Changed;
00312 }
00313 
00314 /// PromoteStackTemporaries - Turn any stack temporaries we introduced into
00315 /// registers if possible.
00316 bool DwarfEHPrepare::PromoteStackTemporaries() {
00317   if (ExceptionValueVar && DT && DF && isAllocaPromotable(ExceptionValueVar)) {
00318     // Turn the exception temporary into registers and phi nodes if possible.
00319     std::vector<AllocaInst*> Allocas(1, ExceptionValueVar);
00320     PromoteMemToReg(Allocas, *DT, *DF, ExceptionValueVar->getContext());
00321     return true;
00322   }
00323   return false;
00324 }
00325 
00326 /// CreateExceptionValueCall - Insert a call to the eh.exception intrinsic at
00327 /// the start of the basic block (unless there already is one, in which case
00328 /// the existing call is returned).
00329 Instruction *DwarfEHPrepare::CreateExceptionValueCall(BasicBlock *BB) {
00330   Instruction *Start = BB->getFirstNonPHI();
00331   // Is this a call to eh.exception?
00332   if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(Start))
00333     if (CI->getIntrinsicID() == Intrinsic::eh_exception)
00334       // Reuse the existing call.
00335       return Start;
00336 
00337   // Find the eh.exception intrinsic if we didn't already.
00338   if (!ExceptionValueIntrinsic)
00339     ExceptionValueIntrinsic = Intrinsic::getDeclaration(F->getParent(),
00340                                                        Intrinsic::eh_exception);
00341 
00342   // Create the call.
00343   return CallInst::Create(ExceptionValueIntrinsic, "eh.value.call", Start);
00344 }
00345 
00346 /// CreateValueLoad - Insert a load of the exception value stack variable
00347 /// (creating it if necessary) at the start of the basic block (unless
00348 /// there already is a load, in which case the existing load is returned).
00349 Instruction *DwarfEHPrepare::CreateValueLoad(BasicBlock *BB) {
00350   Instruction *Start = BB->getFirstNonPHI();
00351   // Is this a load of the exception temporary?
00352   if (ExceptionValueVar)
00353     if (LoadInst* LI = dyn_cast<LoadInst>(Start))
00354       if (LI->getPointerOperand() == ExceptionValueVar)
00355         // Reuse the existing load.
00356         return Start;
00357 
00358   // Create the temporary if we didn't already.
00359   if (!ExceptionValueVar) {
00360     ExceptionValueVar = new AllocaInst(PointerType::getUnqual(
00361            Type::getInt8Ty(BB->getContext())), "eh.value", F->begin()->begin());
00362     ++NumStackTempsIntroduced;
00363   }
00364 
00365   // Load the value.
00366   return new LoadInst(ExceptionValueVar, "eh.value.load", Start);
00367 }
00368 
00369 bool DwarfEHPrepare::runOnFunction(Function &Fn) {
00370   bool Changed = false;
00371 
00372   // Initialize internal state.
00373   DT = getAnalysisIfAvailable<DominatorTree>();
00374   DF = getAnalysisIfAvailable<DominanceFrontier>();
00375   ExceptionValueVar = 0;
00376   F = &Fn;
00377 
00378   // Ensure that only unwind edges end at landing pads (a landing pad is a
00379   // basic block where an invoke unwind edge ends).
00380   Changed |= NormalizeLandingPads();
00381 
00382   // Turn unwind instructions into libcalls.
00383   Changed |= LowerUnwinds();
00384 
00385   // TODO: Move eh.selector calls to landing pads and combine them.
00386 
00387   // Move eh.exception calls to landing pads.
00388   Changed |= MoveExceptionValueCalls();
00389 
00390   // Initialize any stack temporaries we introduced.
00391   Changed |= FinishStackTemporaries();
00392 
00393   // Turn any stack temporaries into registers if possible.
00394   if (!CompileFast)
00395     Changed |= PromoteStackTemporaries();
00396 
00397   LandingPads.clear();
00398 
00399   return Changed;
00400 }