LLVM API Documentation
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 }