DwarfEHPrepare.cpp revision 9adc0abad3c3ed40a268ccbcee0c74cb9e1359fe
1//===-- DwarfEHPrepare - Prepare exception handling for code generation ---===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass mulches exception handling code into a form adapted to code 11// generation. Required if using dwarf exception handling. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "dwarfehprepare" 16#include "llvm/ADT/Statistic.h" 17#include "llvm/Analysis/Dominators.h" 18#include "llvm/CodeGen/Passes.h" 19#include "llvm/Function.h" 20#include "llvm/Instructions.h" 21#include "llvm/IntrinsicInst.h" 22#include "llvm/Module.h" 23#include "llvm/Pass.h" 24#include "llvm/Support/Compiler.h" 25#include "llvm/Target/TargetLowering.h" 26#include "llvm/Transforms/Utils/BasicBlockUtils.h" 27#include "llvm/Transforms/Utils/PromoteMemToReg.h" 28using namespace llvm; 29 30STATISTIC(NumLandingPadsSplit, "Number of landing pads split"); 31STATISTIC(NumUnwindsLowered, "Number of unwind instructions lowered"); 32STATISTIC(NumExceptionValuesMoved, "Number of eh.exception calls moved"); 33STATISTIC(NumStackTempsIntroduced, "Number of stack temporaries introduced"); 34 35namespace { 36 class VISIBILITY_HIDDEN DwarfEHPrepare : public FunctionPass { 37 const TargetLowering *TLI; 38 bool CompileFast; 39 40 // The eh.exception intrinsic. 41 Function *ExceptionValueIntrinsic; 42 43 // _Unwind_Resume or the target equivalent. 44 Constant *RewindFunction; 45 46 // Dominator info is used when turning stack temporaries into registers. 47 DominatorTree *DT; 48 DominanceFrontier *DF; 49 50 // The function we are running on. 51 Function *F; 52 53 // The landing pads for this function. 54 typedef SmallPtrSet<BasicBlock*, 8> BBSet; 55 BBSet LandingPads; 56 57 // Stack temporary used to hold eh.exception values. 58 AllocaInst *ExceptionValueVar; 59 60 bool NormalizeLandingPads(); 61 bool LowerUnwinds(); 62 bool MoveExceptionValueCalls(); 63 bool FinishStackTemporaries(); 64 bool PromoteStackTemporaries(); 65 66 Instruction *CreateExceptionValueCall(BasicBlock *BB); 67 Instruction *CreateValueLoad(BasicBlock *BB); 68 69 /// CreateReadOfExceptionValue - Return the result of the eh.exception 70 /// intrinsic by calling the intrinsic if in a landing pad, or loading 71 /// it from the exception value variable otherwise. 72 Instruction *CreateReadOfExceptionValue(BasicBlock *BB) { 73 return LandingPads.count(BB) ? 74 CreateExceptionValueCall(BB) : CreateValueLoad(BB); 75 } 76 77 public: 78 static char ID; // Pass identification, replacement for typeid. 79 DwarfEHPrepare(const TargetLowering *tli, bool fast) : 80 FunctionPass(&ID), TLI(tli), CompileFast(fast), 81 ExceptionValueIntrinsic(0), RewindFunction(0) {} 82 83 virtual bool runOnFunction(Function &Fn); 84 85 // getAnalysisUsage - We need dominance frontiers for memory promotion. 86 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 87 if (!CompileFast) 88 AU.addRequired<DominatorTree>(); 89 AU.addPreserved<DominatorTree>(); 90 if (!CompileFast) 91 AU.addRequired<DominanceFrontier>(); 92 AU.addPreserved<DominanceFrontier>(); 93 } 94 95 const char *getPassName() const { 96 return "Exception handling preparation"; 97 } 98 99 }; 100} // end anonymous namespace 101 102char DwarfEHPrepare::ID = 0; 103 104FunctionPass *llvm::createDwarfEHPass(const TargetLowering *tli, bool fast) { 105 return new DwarfEHPrepare(tli, fast); 106} 107 108/// NormalizeLandingPads - Normalize and discover landing pads, noting them 109/// in the LandingPads set. A landing pad is normal if the only CFG edges 110/// that end at it are unwind edges from invoke instructions. 111/// Abnormal landing pads are fixed up by redirecting all unwind edges to 112/// a new basic block which falls through to the original. 113bool DwarfEHPrepare::NormalizeLandingPads() { 114 bool Changed = false; 115 116 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 117 TerminatorInst *TI = I->getTerminator(); 118 if (!isa<InvokeInst>(TI)) 119 continue; 120 BasicBlock *LPad = TI->getSuccessor(1); 121 // Skip landing pads that have already been normalized. 122 if (LandingPads.count(LPad)) 123 continue; 124 125 // Check that only invoke unwind edges end at the landing pad. 126 bool OnlyUnwoundTo = true; 127 for (pred_iterator PI = pred_begin(LPad), PE = pred_end(LPad); 128 PI != PE; ++PI) { 129 TerminatorInst *PT = (*PI)->getTerminator(); 130 if (!isa<InvokeInst>(PT) || LPad == PT->getSuccessor(0)) { 131 OnlyUnwoundTo = false; 132 break; 133 } 134 } 135 if (OnlyUnwoundTo) { 136 // Only unwind edges lead to the landing pad. Remember the landing pad. 137 LandingPads.insert(LPad); 138 continue; 139 } 140 141 // At least one normal edge ends at the landing pad. Redirect the unwind 142 // edges to a new basic block which falls through into this one. 143 144 // Create the new basic block. 145 BasicBlock *NewBB = BasicBlock::Create(LPad->getName() + "_unwind_edge"); 146 147 // Insert it into the function right before the original landing pad. 148 LPad->getParent()->getBasicBlockList().insert(LPad, NewBB); 149 150 // Redirect unwind edges from the original landing pad to NewBB. 151 for (pred_iterator PI = pred_begin(LPad), PE = pred_end(LPad); PI != PE; ) { 152 TerminatorInst *PT = (*PI++)->getTerminator(); 153 if (isa<InvokeInst>(PT) && PT->getSuccessor(1) == LPad) 154 // Unwind to the new block. 155 PT->setSuccessor(1, NewBB); 156 } 157 158 // If there are any PHI nodes in LPad, we need to update them so that they 159 // merge incoming values from NewBB instead. 160 for (BasicBlock::iterator II = LPad->begin(); isa<PHINode>(II); ++II) { 161 PHINode *PN = cast<PHINode>(II); 162 pred_iterator PB = pred_begin(NewBB), PE = pred_end(NewBB); 163 164 // Check to see if all of the values coming in via unwind edges are the 165 // same. If so, we don't need to create a new PHI node. 166 Value *InVal = PN->getIncomingValueForBlock(*PB); 167 for (pred_iterator PI = PB; PI != PE; ++PI) { 168 if (PI != PB && InVal != PN->getIncomingValueForBlock(*PI)) { 169 InVal = 0; 170 break; 171 } 172 } 173 174 if (InVal == 0) { 175 // Different unwind edges have different values. Create a new PHI node 176 // in NewBB. 177 PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".unwind", 178 NewBB); 179 // Add an entry for each unwind edge, using the value from the old PHI. 180 for (pred_iterator PI = PB; PI != PE; ++PI) 181 NewPN->addIncoming(PN->getIncomingValueForBlock(*PI), *PI); 182 183 // Now use this new PHI as the common incoming value for NewBB in PN. 184 InVal = NewPN; 185 } 186 187 // Revector exactly one entry in the PHI node to come from NewBB 188 // and delete all other entries that come from unwind edges. If 189 // there are both normal and unwind edges from the same predecessor, 190 // this leaves an entry for the normal edge. 191 for (pred_iterator PI = PB; PI != PE; ++PI) 192 PN->removeIncomingValue(*PI); 193 PN->addIncoming(InVal, NewBB); 194 } 195 196 // Add a fallthrough from NewBB to the original landing pad. 197 BranchInst::Create(LPad, NewBB); 198 199 // Now update DominatorTree and DominanceFrontier analysis information. 200 if (DT) 201 DT->splitBlock(NewBB); 202 if (DF) 203 DF->splitBlock(NewBB); 204 205 // Remember the newly constructed landing pad. The original landing pad 206 // LPad is no longer a landing pad now that all unwind edges have been 207 // revectored to NewBB. 208 LandingPads.insert(NewBB); 209 ++NumLandingPadsSplit; 210 Changed = true; 211 } 212 213 return Changed; 214} 215 216/// LowerUnwinds - Turn unwind instructions into calls to _Unwind_Resume, 217/// rethrowing any previously caught exception. This will crash horribly 218/// at runtime if there is no such exception: using unwind to throw a new 219/// exception is currently not supported. 220bool DwarfEHPrepare::LowerUnwinds() { 221 bool Changed = false; 222 223 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 224 TerminatorInst *TI = I->getTerminator(); 225 if (!isa<UnwindInst>(TI)) 226 continue; 227 228 // Replace the unwind instruction with a call to _Unwind_Resume (or the 229 // appropriate target equivalent) followed by an UnreachableInst. 230 231 // Find the rewind function if we didn't already. 232 if (!RewindFunction) { 233 std::vector<const Type*> Params(1, PointerType::getUnqual(Type::Int8Ty)); 234 FunctionType *FTy = FunctionType::get(Type::VoidTy, Params, false); 235 const char *RewindName = TLI->getLibcallName(RTLIB::UNWIND_RESUME); 236 RewindFunction = F->getParent()->getOrInsertFunction(RewindName, FTy); 237 } 238 239 // Create the call... 240 CallInst::Create(RewindFunction, CreateReadOfExceptionValue(I), "", TI); 241 // ...followed by an UnreachableInst. 242 new UnreachableInst(TI); 243 244 // Nuke the unwind instruction. 245 TI->eraseFromParent(); 246 ++NumUnwindsLowered; 247 Changed = true; 248 } 249 250 return Changed; 251} 252 253/// MoveExceptionValueCalls - Ensure that eh.exception is only ever called from 254/// landing pads by replacing calls outside of landing pads with loads from a 255/// stack temporary. Move eh.exception calls inside landing pads to the start 256/// of the landing pad (optional, but may make things simpler for later passes). 257bool DwarfEHPrepare::MoveExceptionValueCalls() { 258 // If the eh.exception intrinsic is not declared in the module then there is 259 // nothing to do. Speed up compilation by checking for this common case. 260 if (!ExceptionValueIntrinsic && 261 !F->getParent()->getFunction(Intrinsic::getName(Intrinsic::eh_exception))) 262 return false; 263 264 bool Changed = false; 265 266 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 267 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) 268 if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) 269 if (CI->getIntrinsicID() == Intrinsic::eh_exception) { 270 if (!CI->use_empty()) { 271 Value *ExceptionValue = CreateReadOfExceptionValue(BB); 272 if (CI == ExceptionValue) { 273 // The call was at the start of a landing pad - leave it alone. 274 assert(LandingPads.count(BB) && 275 "Created eh.exception call outside landing pad!"); 276 continue; 277 } 278 CI->replaceAllUsesWith(ExceptionValue); 279 } 280 CI->eraseFromParent(); 281 ++NumExceptionValuesMoved; 282 Changed = true; 283 } 284 } 285 286 return Changed; 287} 288 289/// FinishStackTemporaries - If we introduced a stack variable to hold the 290/// exception value then initialize it in each landing pad. 291bool DwarfEHPrepare::FinishStackTemporaries() { 292 if (!ExceptionValueVar) 293 // Nothing to do. 294 return false; 295 296 bool Changed = false; 297 298 // Make sure that there is a store of the exception value at the start of 299 // each landing pad. 300 for (BBSet::iterator LI = LandingPads.begin(), LE = LandingPads.end(); 301 LI != LE; ++LI) { 302 Instruction *ExceptionValue = CreateReadOfExceptionValue(*LI); 303 Instruction *Store = new StoreInst(ExceptionValue, ExceptionValueVar); 304 Store->insertAfter(ExceptionValue); 305 Changed = true; 306 } 307 308 return Changed; 309} 310 311/// PromoteStackTemporaries - Turn any stack temporaries we introduced into 312/// registers if possible. 313bool DwarfEHPrepare::PromoteStackTemporaries() { 314 if (ExceptionValueVar && DT && DF && isAllocaPromotable(ExceptionValueVar)) { 315 // Turn the exception temporary into registers and phi nodes if possible. 316 std::vector<AllocaInst*> Allocas(1, ExceptionValueVar); 317 PromoteMemToReg(Allocas, *DT, *DF, Context); 318 return true; 319 } 320 return false; 321} 322 323/// CreateExceptionValueCall - Insert a call to the eh.exception intrinsic at 324/// the start of the basic block (unless there already is one, in which case 325/// the existing call is returned). 326Instruction *DwarfEHPrepare::CreateExceptionValueCall(BasicBlock *BB) { 327 Instruction *Start = BB->getFirstNonPHI(); 328 // Is this a call to eh.exception? 329 if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(Start)) 330 if (CI->getIntrinsicID() == Intrinsic::eh_exception) 331 // Reuse the existing call. 332 return Start; 333 334 // Find the eh.exception intrinsic if we didn't already. 335 if (!ExceptionValueIntrinsic) 336 ExceptionValueIntrinsic = Intrinsic::getDeclaration(F->getParent(), 337 Intrinsic::eh_exception); 338 339 // Create the call. 340 return CallInst::Create(ExceptionValueIntrinsic, "eh.value.call", Start); 341} 342 343/// CreateValueLoad - Insert a load of the exception value stack variable 344/// (creating it if necessary) at the start of the basic block (unless 345/// there already is a load, in which case the existing load is returned). 346Instruction *DwarfEHPrepare::CreateValueLoad(BasicBlock *BB) { 347 Instruction *Start = BB->getFirstNonPHI(); 348 // Is this a load of the exception temporary? 349 if (ExceptionValueVar) 350 if (LoadInst* LI = dyn_cast<LoadInst>(Start)) 351 if (LI->getPointerOperand() == ExceptionValueVar) 352 // Reuse the existing load. 353 return Start; 354 355 // Create the temporary if we didn't already. 356 if (!ExceptionValueVar) { 357 ExceptionValueVar = new AllocaInst(*Context, 358 PointerType::getUnqual(Type::Int8Ty), 359 "eh.value", F->begin()->begin()); 360 ++NumStackTempsIntroduced; 361 } 362 363 // Load the value. 364 return new LoadInst(ExceptionValueVar, "eh.value.load", Start); 365} 366 367bool DwarfEHPrepare::runOnFunction(Function &Fn) { 368 bool Changed = false; 369 370 // Initialize internal state. 371 DT = getAnalysisIfAvailable<DominatorTree>(); 372 DF = getAnalysisIfAvailable<DominanceFrontier>(); 373 ExceptionValueVar = 0; 374 F = &Fn; 375 376 // Ensure that only unwind edges end at landing pads (a landing pad is a 377 // basic block where an invoke unwind edge ends). 378 Changed |= NormalizeLandingPads(); 379 380 // Turn unwind instructions into libcalls. 381 Changed |= LowerUnwinds(); 382 383 // TODO: Move eh.selector calls to landing pads and combine them. 384 385 // Move eh.exception calls to landing pads. 386 Changed |= MoveExceptionValueCalls(); 387 388 // Initialize any stack temporaries we introduced. 389 Changed |= FinishStackTemporaries(); 390 391 // Turn any stack temporaries into registers if possible. 392 if (!CompileFast) 393 Changed |= PromoteStackTemporaries(); 394 395 LandingPads.clear(); 396 397 return Changed; 398} 399