lib/CodeGen/DwarfEHPrepare.cpp

   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"
  28 using namespace llvm;
  29
  30 STATISTIC(NumLandingPadsSplit,     "Number of landing pads split");
  31 STATISTIC(NumUnwindsLowered,       "Number of unwind instructions lowered");
  32 STATISTIC(NumExceptionValuesMoved, "Number of eh.exception calls moved");
  33 STATISTIC(NumStackTempsIntroduced, "Number of stack temporaries introduced");
  34
  35 namespace {
  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
 102 char DwarfEHPrepare::ID = 0;
 103
 104 FunctionPass *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.
 113 bool 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(F->getContext(),
 146                                            LPad->getName() + "_unwind_edge");
 147
 148     // Insert it into the function right before the original landing pad.
 149     LPad->getParent()->getBasicBlockList().insert(LPad, NewBB);
 150
 151     // Redirect unwind edges from the original landing pad to NewBB.
 152     for (pred_iterator PI = pred_begin(LPad), PE = pred_end(LPad); PI != PE; ) {
 153       TerminatorInst *PT = (*PI++)->getTerminator();
 154       if (isa<InvokeInst>(PT) && PT->getSuccessor(1) == LPad)
 155         // Unwind to the new block.
 156         PT->setSuccessor(1, NewBB);
 157     }
 158
 159     // If there are any PHI nodes in LPad, we need to update them so that they
 160     // merge incoming values from NewBB instead.
 161     for (BasicBlock::iterator II = LPad->begin(); isa<PHINode>(II); ++II) {
 162       PHINode *PN = cast<PHINode>(II);
 163       pred_iterator PB = pred_begin(NewBB), PE = pred_end(NewBB);
 164
 165       // Check to see if all of the values coming in via unwind edges are the
 166       // same.  If so, we don't need to create a new PHI node.
 167       Value *InVal = PN->getIncomingValueForBlock(*PB);
 168       for (pred_iterator PI = PB; PI != PE; ++PI) {
 169         if (PI != PB && InVal != PN->getIncomingValueForBlock(*PI)) {
 170           InVal = 0;
 171           break;
 172         }
 173       }
 174
 175       if (InVal == 0) {
 176         // Different unwind edges have different values.  Create a new PHI node
 177         // in NewBB.
 178         PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".unwind",
 179                                          NewBB);
 180         // Add an entry for each unwind edge, using the value from the old PHI.
 181         for (pred_iterator PI = PB; PI != PE; ++PI)
 182           NewPN->addIncoming(PN->getIncomingValueForBlock(*PI), *PI);
 183
 184         // Now use this new PHI as the common incoming value for NewBB in PN.
 185         InVal = NewPN;
 186       }
 187
 188       // Revector exactly one entry in the PHI node to come from NewBB
 189       // and delete all other entries that come from unwind edges.  If
 190       // there are both normal and unwind edges from the same predecessor,
 191       // this leaves an entry for the normal edge.
 192       for (pred_iterator PI = PB; PI != PE; ++PI)
 193         PN->removeIncomingValue(*PI);
 194       PN->addIncoming(InVal, NewBB);
 195     }
 196
 197     // Add a fallthrough from NewBB to the original landing pad.
 198     BranchInst::Create(LPad, NewBB);
 199
 200     // Now update DominatorTree and DominanceFrontier analysis information.
 201     if (DT)
 202       DT->splitBlock(NewBB);
 203     if (DF)
 204       DF->splitBlock(NewBB);
 205
 206     // Remember the newly constructed landing pad.  The original landing pad
 207     // LPad is no longer a landing pad now that all unwind edges have been
 208     // revectored to NewBB.
 209     LandingPads.insert(NewBB);
 210     ++NumLandingPadsSplit;
 211     Changed = true;
 212   }
 213
 214   return Changed;
 215 }
 216
 217 /// LowerUnwinds - Turn unwind instructions into calls to _Unwind_Resume,
 218 /// rethrowing any previously caught exception.  This will crash horribly
 219 /// at runtime if there is no such exception: using unwind to throw a new
 220 /// exception is currently not supported.
 221 bool DwarfEHPrepare::LowerUnwinds() {
 222   bool Changed = false;
 223
 224   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
 225     TerminatorInst *TI = I->getTerminator();
 226     if (!isa<UnwindInst>(TI))
 227       continue;
 228
 229     // Replace the unwind instruction with a call to _Unwind_Resume (or the
 230     // appropriate target equivalent) followed by an UnreachableInst.
 231
 232     // Find the rewind function if we didn't already.
 233     if (!RewindFunction) {
 234       std::vector<const Type*> Params(1,
 235                      PointerType::getUnqual(Type::getInt8Ty(TI->getContext())));
 236       FunctionType *FTy = FunctionType::get(Type::getVoidTy(TI->getContext()),
 237                                             Params, false);
 238       const char *RewindName = TLI->getLibcallName(RTLIB::UNWIND_RESUME);
 239       RewindFunction = F->getParent()->getOrInsertFunction(RewindName, FTy);
 240     }
 241
 242     // Create the call...
 243     CallInst *CI = CallInst::Create(RewindFunction,
 244                                     CreateReadOfExceptionValue(I), "", TI);
 245     CI->setCallingConv(TLI->getLibcallCallingConv(RTLIB::UNWIND_RESUME));
 246     // ...followed by an UnreachableInst.
 247     new UnreachableInst(TI->getContext(), TI);
 248
 249     // Nuke the unwind instruction.
 250     TI->eraseFromParent();
 251     ++NumUnwindsLowered;
 252     Changed = true;
 253   }
 254
 255   return Changed;
 256 }
 257
 258 /// MoveExceptionValueCalls - Ensure that eh.exception is only ever called from
 259 /// landing pads by replacing calls outside of landing pads with loads from a
 260 /// stack temporary.  Move eh.exception calls inside landing pads to the start
 261 /// of the landing pad (optional, but may make things simpler for later passes).
 262 bool DwarfEHPrepare::MoveExceptionValueCalls() {
 263   // If the eh.exception intrinsic is not declared in the module then there is
 264   // nothing to do.  Speed up compilation by checking for this common case.
 265   if (!ExceptionValueIntrinsic &&
 266       !F->getParent()->getFunction(Intrinsic::getName(Intrinsic::eh_exception)))
 267     return false;
 268
 269   bool Changed = false;
 270
 271   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
 272     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
 273       if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
 274         if (CI->getIntrinsicID() == Intrinsic::eh_exception) {
 275           if (!CI->use_empty()) {
 276             Value *ExceptionValue = CreateReadOfExceptionValue(BB);
 277             if (CI == ExceptionValue) {
 278               // The call was at the start of a landing pad - leave it alone.
 279               assert(LandingPads.count(BB) &&
 280                      "Created eh.exception call outside landing pad!");
 281               continue;
 282             }
 283             CI->replaceAllUsesWith(ExceptionValue);
 284           }
 285           CI->eraseFromParent();
 286           ++NumExceptionValuesMoved;
 287           Changed = true;
 288         }
 289   }
 290
 291   return Changed;
 292 }
 293
 294 /// FinishStackTemporaries - If we introduced a stack variable to hold the
 295 /// exception value then initialize it in each landing pad.
 296 bool DwarfEHPrepare::FinishStackTemporaries() {
 297   if (!ExceptionValueVar)
 298     // Nothing to do.
 299     return false;
 300
 301   bool Changed = false;
 302
 303   // Make sure that there is a store of the exception value at the start of
 304   // each landing pad.
 305   for (BBSet::iterator LI = LandingPads.begin(), LE = LandingPads.end();
 306        LI != LE; ++LI) {
 307     Instruction *ExceptionValue = CreateReadOfExceptionValue(*LI);
 308     Instruction *Store = new StoreInst(ExceptionValue, ExceptionValueVar);
 309     Store->insertAfter(ExceptionValue);
 310     Changed = true;
 311   }
 312
 313   return Changed;
 314 }
 315
 316 /// PromoteStackTemporaries - Turn any stack temporaries we introduced into
 317 /// registers if possible.
 318 bool DwarfEHPrepare::PromoteStackTemporaries() {
 319   if (ExceptionValueVar && DT && DF && isAllocaPromotable(ExceptionValueVar)) {
 320     // Turn the exception temporary into registers and phi nodes if possible.
 321     std::vector<AllocaInst*> Allocas(1, ExceptionValueVar);
 322     PromoteMemToReg(Allocas, *DT, *DF, ExceptionValueVar->getContext());
 323     return true;
 324   }
 325   return false;
 326 }
 327
 328 /// CreateExceptionValueCall - Insert a call to the eh.exception intrinsic at
 329 /// the start of the basic block (unless there already is one, in which case
 330 /// the existing call is returned).
 331 Instruction *DwarfEHPrepare::CreateExceptionValueCall(BasicBlock *BB) {
 332   Instruction *Start = BB->getFirstNonPHI();
 333   // Is this a call to eh.exception?
 334   if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(Start))
 335     if (CI->getIntrinsicID() == Intrinsic::eh_exception)
 336       // Reuse the existing call.
 337       return Start;
 338
 339   // Find the eh.exception intrinsic if we didn't already.
 340   if (!ExceptionValueIntrinsic)
 341     ExceptionValueIntrinsic = Intrinsic::getDeclaration(F->getParent(),
 342                                                        Intrinsic::eh_exception);
 343
 344   // Create the call.
 345   return CallInst::Create(ExceptionValueIntrinsic, "eh.value.call", Start);
 346 }
 347
 348 /// CreateValueLoad - Insert a load of the exception value stack variable
 349 /// (creating it if necessary) at the start of the basic block (unless
 350 /// there already is a load, in which case the existing load is returned).
 351 Instruction *DwarfEHPrepare::CreateValueLoad(BasicBlock *BB) {
 352   Instruction *Start = BB->getFirstNonPHI();
 353   // Is this a load of the exception temporary?
 354   if (ExceptionValueVar)
 355     if (LoadInst* LI = dyn_cast<LoadInst>(Start))
 356       if (LI->getPointerOperand() == ExceptionValueVar)
 357         // Reuse the existing load.
 358         return Start;
 359
 360   // Create the temporary if we didn't already.
 361   if (!ExceptionValueVar) {
 362     ExceptionValueVar = new AllocaInst(PointerType::getUnqual(
 363            Type::getInt8Ty(BB->getContext())), "eh.value", F->begin()->begin());
 364     ++NumStackTempsIntroduced;
 365   }
 366
 367   // Load the value.
 368   return new LoadInst(ExceptionValueVar, "eh.value.load", Start);
 369 }
 370
 371 bool DwarfEHPrepare::runOnFunction(Function &Fn) {
 372   bool Changed = false;
 373
 374   // Initialize internal state.
 375   DT = getAnalysisIfAvailable<DominatorTree>();
 376   DF = getAnalysisIfAvailable<DominanceFrontier>();
 377   ExceptionValueVar = 0;
 378   F = &Fn;
 379
 380   // Ensure that only unwind edges end at landing pads (a landing pad is a
 381   // basic block where an invoke unwind edge ends).
 382   Changed |= NormalizeLandingPads();
 383
 384   // Turn unwind instructions into libcalls.
 385   Changed |= LowerUnwinds();
 386
 387   // TODO: Move eh.selector calls to landing pads and combine them.
 388
 389   // Move eh.exception calls to landing pads.
 390   Changed |= MoveExceptionValueCalls();
 391
 392   // Initialize any stack temporaries we introduced.
 393   Changed |= FinishStackTemporaries();
 394
 395   // Turn any stack temporaries into registers if possible.
 396   if (!CompileFast)
 397     Changed |= PromoteStackTemporaries();
 398
 399   LandingPads.clear();
 400
 401   return Changed;
 402 }