lib/Transforms/IPO/LowerSetJmp.cpp

   1 //===- LowerSetJmp.cpp - Code pertaining to lowering set/long jumps -------===//
   2 //
   3 //  This file implements the lowering of setjmp and longjmp to use the
   4 //  LLVM invoke and unwind instructions as necessary.
   5 //
   6 //  Lowering of longjmp is fairly trivial. We replace the call with a
   7 //  call to the LLVM library function "__llvm_sjljeh_throw_longjmp()".
   8 //  This unwinds the stack for us calling all of the destructors for
   9 //  objects allocated on the stack.
  10 //
  11 //  At a setjmp call, the basic block is split and the setjmp removed.
  12 //  The calls in a function that have a setjmp are converted to invoke
  13 //  where the except part checks to see if it's a longjmp exception and,
  14 //  if so, if it's handled in the function. If it is, then it gets the
  15 //  value returned by the longjmp and goes to where the basic block was
  16 //  split. Invoke instructions are handled in a similar fashion with the
  17 //  original except block being executed if it isn't a longjmp except
  18 //  that is handled by that function.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 //===----------------------------------------------------------------------===//
  23 // FIXME: This pass doesn't deal with PHI statements just yet. That is,
  24 // we expect this to occur before SSAification is done. This would seem
  25 // to make sense, but in general, it might be a good idea to make this
  26 // pass invokable via the "opt" command at will.
  27 //===----------------------------------------------------------------------===//
  28
  29 #include "llvm/Constants.h"
  30 #include "llvm/DerivedTypes.h"
  31 #include "llvm/Instructions.h"
  32 #include "llvm/Intrinsics.h"
  33 #include "llvm/Module.h"
  34 #include "llvm/Pass.h"
  35 #include "llvm/Support/CFG.h"
  36 #include "llvm/Support/InstVisitor.h"
  37 #include "Support/DepthFirstIterator.h"
  38 #include "Support/Statistic.h"
  39 #include "Support/StringExtras.h"
  40 #include "Support/VectorExtras.h"
  41
  42 namespace {
  43   Statistic<> LongJmpsTransformed("lowersetjmp",
  44                                   "Number of longjmps transformed");
  45   Statistic<> SetJmpsTransformed("lowersetjmp",
  46                                  "Number of setjmps transformed");
  47
  48   //===--------------------------------------------------------------------===//
  49   // LowerSetJmp pass implementation. This is subclassed from the "Pass"
  50   // class because it works on a module as a whole, not a function at a
  51   // time.
  52
  53   class LowerSetJmp : public Pass,
  54                       public InstVisitor<LowerSetJmp> {
  55     // LLVM library functions...
  56     Function* InitSJMap;        // __llvm_sjljeh_init_setjmpmap
  57     Function* DestroySJMap;     // __llvm_sjljeh_destroy_setjmpmap
  58     Function* AddSJToMap;       // __llvm_sjljeh_add_setjmp_to_map
  59     Function* ThrowLongJmp;     // __llvm_sjljeh_throw_longjmp
  60     Function* TryCatchLJ;       // __llvm_sjljeh_try_catching_longjmp_exception
  61     Function* IsLJException;    // __llvm_sjljeh_is_longjmp_exception
  62     Function* GetLJValue;       // __llvm_sjljeh_get_longjmp_value
  63
  64     typedef std::pair<SwitchInst*, CallInst*> SwitchValuePair;
  65
  66     // Keep track of those basic blocks reachable via a depth-first search of
  67     // the CFG from a setjmp call. We only need to transform those "call" and
  68     // "invoke" instructions that are reachable from the setjmp call site.
  69     std::set<BasicBlock*> DFSBlocks;
  70
  71     // The setjmp map is going to hold information about which setjmps
  72     // were called (each setjmp gets its own number) and with which
  73     // buffer it was called.
  74     std::map<Function*, AllocaInst*>            SJMap;
  75
  76     // The rethrow basic block map holds the basic block to branch to if
  77     // the exception isn't handled in the current function and needs to
  78     // be rethrown.
  79     std::map<const Function*, BasicBlock*>      RethrowBBMap;
  80
  81     // The preliminary basic block map holds a basic block that grabs the
  82     // exception and determines if it's handled by the current function.
  83     std::map<const Function*, BasicBlock*>      PrelimBBMap;
  84
  85     // The switch/value map holds a switch inst/call inst pair. The
  86     // switch inst controls which handler (if any) gets called and the
  87     // value is the value returned to that handler by the call to
  88     // __llvm_sjljeh_get_longjmp_value.
  89     std::map<const Function*, SwitchValuePair>  SwitchValMap;
  90
  91     // A map of which setjmps we've seen so far in a function.
  92     std::map<const Function*, unsigned>         SetJmpIDMap;
  93
  94     AllocaInst*     GetSetJmpMap(Function* Func);
  95     BasicBlock*     GetRethrowBB(Function* Func);
  96     SwitchValuePair GetSJSwitch(Function* Func, BasicBlock* Rethrow);
  97
  98     void TransformLongJmpCall(CallInst* Inst);
  99     void TransformSetJmpCall(CallInst* Inst);
 100
 101     bool IsTransformableFunction(const std::string& Name);
 102   public:
 103     void visitCallInst(CallInst& CI);
 104     void visitInvokeInst(InvokeInst& II);
 105     void visitReturnInst(ReturnInst& RI);
 106     void visitUnwindInst(UnwindInst& UI);
 107
 108     bool run(Module& M);
 109     bool doInitialization(Module& M);
 110   };
 111
 112   RegisterOpt<LowerSetJmp> X("lowersetjmp", "Lower Set Jump");
 113 } // end anonymous namespace
 114
 115 // run - Run the transformation on the program. We grab the function
 116 // prototypes for longjmp and setjmp. If they are used in the program,
 117 // then we can go directly to the places they're at and transform them.
 118 bool LowerSetJmp::run(Module& M)
 119 {
 120   bool Changed = false;
 121
 122   // These are what the functions are called.
 123   Function* SetJmp = M.getNamedFunction("llvm.setjmp");
 124   Function* LongJmp = M.getNamedFunction("llvm.longjmp");
 125
 126   // This program doesn't have longjmp and setjmp calls.
 127   if ((!LongJmp || LongJmp->use_empty()) &&
 128         (!SetJmp || SetJmp->use_empty())) return false;
 129
 130   // Initialize some values and functions we'll need to transform the
 131   // setjmp/longjmp functions.
 132   doInitialization(M);
 133
 134   if (SetJmp) {
 135     std::set<BasicBlock*> BBSet;
 136
 137     for (Value::use_iterator B = SetJmp->use_begin(), E = SetJmp->use_end();
 138          B != E; ++B) {
 139       Instruction* I = cast<Instruction>(*B);
 140       BasicBlock* BB = I->getParent();
 141       Function* Func = BB->getParent();
 142       DFSBlocks.insert(df_begin(BB), df_end(BB));
 143     }
 144
 145     while (!SetJmp->use_empty()) {
 146       assert(isa<CallInst>(SetJmp->use_back()) &&
 147              "User of setjmp intrinsic not a call?");
 148       TransformSetJmpCall(cast<CallInst>(SetJmp->use_back()));
 149       Changed = true;
 150     }
 151   }
 152
 153   if (LongJmp)
 154     while (!LongJmp->use_empty()) {
 155       assert(isa<CallInst>(LongJmp->use_back()) &&
 156              "User of longjmp intrinsic not a call?");
 157       TransformLongJmpCall(cast<CallInst>(LongJmp->use_back()));
 158       Changed = true;
 159     }
 160
 161   // Now go through the affected functions and convert calls and invokes
 162   // to new invokes...
 163   for (std::map<Function*, AllocaInst*>::iterator
 164       B = SJMap.begin(), E = SJMap.end(); B != E; ++B) {
 165     Function* F = B->first;
 166     for (Function::iterator BB = F->begin(), BE = F->end(); BB != BE; ++BB)
 167       for (BasicBlock::iterator IB = BB->begin(), IE = BB->end(); IB != IE; ) {
 168         visit(*IB++);
 169         if (IB != BB->end() && IB->getParent() != BB)
 170           break;  // The next instruction got moved to a different block!
 171       }
 172   }
 173
 174   DFSBlocks.clear();
 175   SJMap.clear();
 176   RethrowBBMap.clear();
 177   PrelimBBMap.clear();
 178   SwitchValMap.clear();
 179   SetJmpIDMap.clear();
 180
 181   return Changed;
 182 }
 183
 184 // doInitialization - For the lower long/setjmp pass, this ensures that a
 185 // module contains a declaration for the intrisic functions we are going
 186 // to call to convert longjmp and setjmp calls.
 187 //
 188 // This function is always successful, unless it isn't.
 189 bool LowerSetJmp::doInitialization(Module& M)
 190 {
 191   const Type *SBPTy = PointerType::get(Type::SByteTy);
 192   const Type *SBPPTy = PointerType::get(SBPTy);
 193
 194   // N.B. See llvm/runtime/GCCLibraries/libexception/SJLJ-Exception.h for
 195   // a description of the following library functions.
 196
 197   // void __llvm_sjljeh_init_setjmpmap(void**)
 198   InitSJMap = M.getOrInsertFunction("__llvm_sjljeh_init_setjmpmap",
 199                                     Type::VoidTy, SBPPTy, 0);
 200   // void __llvm_sjljeh_destroy_setjmpmap(void**)
 201   DestroySJMap = M.getOrInsertFunction("__llvm_sjljeh_destroy_setjmpmap",
 202                                        Type::VoidTy, SBPPTy, 0);
 203
 204   // void __llvm_sjljeh_add_setjmp_to_map(void**, void*, unsigned)
 205   AddSJToMap = M.getOrInsertFunction("__llvm_sjljeh_add_setjmp_to_map",
 206                                      Type::VoidTy, SBPPTy, SBPTy,
 207                                      Type::UIntTy, 0);
 208
 209   // void __llvm_sjljeh_throw_longjmp(int*, int)
 210   ThrowLongJmp = M.getOrInsertFunction("__llvm_sjljeh_throw_longjmp",
 211                                        Type::VoidTy, SBPTy, Type::IntTy, 0);
 212
 213   // unsigned __llvm_sjljeh_try_catching_longjmp_exception(void **)
 214   TryCatchLJ =
 215     M.getOrInsertFunction("__llvm_sjljeh_try_catching_longjmp_exception",
 216                           Type::UIntTy, SBPPTy, 0);
 217
 218   // bool __llvm_sjljeh_is_longjmp_exception()
 219   IsLJException = M.getOrInsertFunction("__llvm_sjljeh_is_longjmp_exception",
 220                                         Type::BoolTy, 0);
 221
 222   // int __llvm_sjljeh_get_longjmp_value()
 223   GetLJValue = M.getOrInsertFunction("__llvm_sjljeh_get_longjmp_value",
 224                                      Type::IntTy, 0);
 225   return true;
 226 }
 227
 228 // IsTransformableFunction - Return true if the function name isn't one
 229 // of the ones we don't want transformed. Currently, don't transform any
 230 // "llvm.{setjmp,longjmp}" functions and none of the setjmp/longjmp error
 231 // handling functions (beginning with __llvm_sjljeh_...they don't throw
 232 // exceptions).
 233 bool LowerSetJmp::IsTransformableFunction(const std::string& Name)
 234 {
 235   std::string SJLJEh("__llvm_sjljeh");
 236
 237   if (Name.size() > SJLJEh.size())
 238     return std::string(Name.begin(), Name.begin() + SJLJEh.size()) != SJLJEh;
 239
 240   return true;
 241 }
 242
 243 // TransformLongJmpCall - Transform a longjmp call into a call to the
 244 // internal __llvm_sjljeh_throw_longjmp function. It then takes care of
 245 // throwing the exception for us.
 246 void LowerSetJmp::TransformLongJmpCall(CallInst* Inst)
 247 {
 248   const Type* SBPTy = PointerType::get(Type::SByteTy);
 249
 250   // Create the call to "__llvm_sjljeh_throw_longjmp". This takes the
 251   // same parameters as "longjmp", except that the buffer is cast to a
 252   // char*. It returns "void", so it doesn't need to replace any of
 253   // Inst's uses and doesn't get a name.
 254   CastInst* CI = new CastInst(Inst->getOperand(1), SBPTy, "LJBuf", Inst);
 255   new CallInst(ThrowLongJmp, make_vector<Value*>(CI, Inst->getOperand(2), 0),
 256                "", Inst);
 257
 258   SwitchValuePair& SVP = SwitchValMap[Inst->getParent()->getParent()];
 259
 260   // If the function has a setjmp call in it (they are transformed first)
 261   // we should branch to the basic block that determines if this longjmp
 262   // is applicable here. Otherwise, issue an unwind.
 263   if (SVP.first)
 264     new BranchInst(SVP.first->getParent(), Inst);
 265   else
 266     new UnwindInst(Inst);
 267
 268   // Remove all insts after the branch/unwind inst.
 269   Inst->getParent()->getInstList().erase(Inst,
 270                                        Inst->getParent()->getInstList().end());
 271
 272   ++LongJmpsTransformed;
 273 }
 274
 275 // GetSetJmpMap - Retrieve (create and initialize, if necessary) the
 276 // setjmp map. This map is going to hold information about which setjmps
 277 // were called (each setjmp gets its own number) and with which buffer it
 278 // was called. There can be only one!
 279 AllocaInst* LowerSetJmp::GetSetJmpMap(Function* Func)
 280 {
 281   if (SJMap[Func]) return SJMap[Func];
 282
 283   // Insert the setjmp map initialization before the first instruction in
 284   // the function.
 285   Instruction* Inst = Func->getEntryBlock().begin();
 286   assert(Inst && "Couldn't find even ONE instruction in entry block!");
 287
 288   // Fill in the alloca and call to initialize the SJ map.
 289   const Type *SBPTy = PointerType::get(Type::SByteTy);
 290   AllocaInst* Map = new AllocaInst(SBPTy, 0, "SJMap", Inst);
 291   new CallInst(InitSJMap, make_vector<Value*>(Map, 0), "", Inst);
 292   return SJMap[Func] = Map;
 293 }
 294
 295 // GetRethrowBB - Only one rethrow basic block is needed per function.
 296 // If this is a longjmp exception but not handled in this block, this BB
 297 // performs the rethrow.
 298 BasicBlock* LowerSetJmp::GetRethrowBB(Function* Func)
 299 {
 300   if (RethrowBBMap[Func]) return RethrowBBMap[Func];
 301
 302   // The basic block we're going to jump to if we need to rethrow the
 303   // exception.
 304   BasicBlock* Rethrow = new BasicBlock("RethrowExcept", Func);
 305   BasicBlock::InstListType& RethrowBlkIL = Rethrow->getInstList();
 306
 307   // Fill in the "Rethrow" BB with a call to rethrow the exception. This
 308   // is the last instruction in the BB since at this point the runtime
 309   // should exit this function and go to the next function.
 310   RethrowBlkIL.push_back(new UnwindInst());
 311   return RethrowBBMap[Func] = Rethrow;
 312 }
 313
 314 // GetSJSwitch - Return the switch statement that controls which handler
 315 // (if any) gets called and the value returned to that handler.
 316 LowerSetJmp::SwitchValuePair LowerSetJmp::GetSJSwitch(Function* Func,
 317                                                       BasicBlock* Rethrow)
 318 {
 319   if (SwitchValMap[Func].first) return SwitchValMap[Func];
 320
 321   BasicBlock* LongJmpPre = new BasicBlock("LongJmpBlkPre", Func);
 322   BasicBlock::InstListType& LongJmpPreIL = LongJmpPre->getInstList();
 323
 324   // Keep track of the preliminary basic block for some of the other
 325   // transformations.
 326   PrelimBBMap[Func] = LongJmpPre;
 327
 328   // Grab the exception.
 329   CallInst* Cond = new
 330     CallInst(IsLJException, std::vector<Value*>(), "IsLJExcept");
 331   LongJmpPreIL.push_back(Cond);
 332
 333   // The "decision basic block" gets the number associated with the
 334   // setjmp call returning to switch on and the value returned by
 335   // longjmp.
 336   BasicBlock* DecisionBB = new BasicBlock("LJDecisionBB", Func);
 337   BasicBlock::InstListType& DecisionBBIL = DecisionBB->getInstList();
 338
 339   LongJmpPreIL.push_back(new BranchInst(DecisionBB, Rethrow, Cond));
 340
 341   // Fill in the "decision" basic block.
 342   CallInst* LJVal = new CallInst(GetLJValue, std::vector<Value*>(), "LJVal");
 343   DecisionBBIL.push_back(LJVal);
 344   CallInst* SJNum = new
 345     CallInst(TryCatchLJ, make_vector<Value*>(GetSetJmpMap(Func), 0), "SJNum");
 346   DecisionBBIL.push_back(SJNum);
 347
 348   SwitchInst* SI = new SwitchInst(SJNum, Rethrow);
 349   DecisionBBIL.push_back(SI);
 350   return SwitchValMap[Func] = SwitchValuePair(SI, LJVal);
 351 }
 352
 353 // TransformSetJmpCall - The setjmp call is a bit trickier to transform.
 354 // We're going to convert all setjmp calls to nops. Then all "call" and
 355 // "invoke" instructions in the function are converted to "invoke" where
 356 // the "except" branch is used when returning from a longjmp call.
 357 void LowerSetJmp::TransformSetJmpCall(CallInst* Inst)
 358 {
 359   BasicBlock* ABlock = Inst->getParent();
 360   Function* Func = ABlock->getParent();
 361
 362   // Add this setjmp to the setjmp map.
 363   const Type* SBPTy = PointerType::get(Type::SByteTy);
 364   CastInst* BufPtr = new CastInst(Inst->getOperand(1), SBPTy, "SBJmpBuf", Inst);
 365   new CallInst(AddSJToMap,
 366                make_vector<Value*>(GetSetJmpMap(Func), BufPtr,
 367                                    ConstantUInt::get(Type::UIntTy,
 368                                                      SetJmpIDMap[Func]++), 0),
 369                "", Inst);
 370
 371   // Change the setjmp call into a branch statement. We'll remove the
 372   // setjmp call in a little bit. No worries.
 373   BasicBlock* SetJmpContBlock = ABlock->splitBasicBlock(Inst);
 374   assert(SetJmpContBlock && "Couldn't split setjmp BB!!");
 375
 376   SetJmpContBlock->setName("SetJmpContBlock");
 377
 378   // Reposition the split BB in the BB list to make things tidier.
 379   Func->getBasicBlockList().remove(SetJmpContBlock);
 380   Func->getBasicBlockList().insert(++Function::iterator(ABlock),
 381                                    SetJmpContBlock);
 382
 383   // This PHI node will be in the new block created from the
 384   // splitBasicBlock call.
 385   PHINode* PHI = new PHINode(Type::IntTy, "SetJmpReturn", Inst);
 386
 387   // Coming from a call to setjmp, the return is 0.
 388   PHI->addIncoming(ConstantInt::getNullValue(Type::IntTy), ABlock);
 389
 390   // Add the case for this setjmp's number...
 391   SwitchValuePair SVP = GetSJSwitch(Func, GetRethrowBB(Func));
 392   SVP.first->addCase(ConstantUInt::get(Type::UIntTy, SetJmpIDMap[Func] - 1),
 393                      SetJmpContBlock);
 394
 395   // Value coming from the handling of the exception.
 396   PHI->addIncoming(SVP.second, SVP.second->getParent());
 397
 398   // Replace all uses of this instruction with the PHI node created by
 399   // the eradication of setjmp.
 400   Inst->replaceAllUsesWith(PHI);
 401   Inst->getParent()->getInstList().erase(Inst);
 402
 403   ++SetJmpsTransformed;
 404 }
 405
 406 // visitCallInst - This converts all LLVM call instructions into invoke
 407 // instructions. The except part of the invoke goes to the "LongJmpBlkPre"
 408 // that grabs the exception and proceeds to determine if it's a longjmp
 409 // exception or not.
 410 void LowerSetJmp::visitCallInst(CallInst& CI)
 411 {
 412   if (CI.getCalledFunction())
 413     if (!IsTransformableFunction(CI.getCalledFunction()->getName()) ||
 414         CI.getCalledFunction()->isIntrinsic()) return;
 415
 416   BasicBlock* OldBB = CI.getParent();
 417   Function* Func = OldBB->getParent();
 418
 419   // If not reachable from a setjmp call, don't transform.
 420   if (!DFSBlocks.count(OldBB)) return;
 421
 422   BasicBlock* NewBB = OldBB->splitBasicBlock(CI);
 423   assert(NewBB && "Couldn't split BB of \"call\" instruction!!");
 424   NewBB->setName("Call2Invoke");
 425
 426   // Reposition the split BB in the BB list to make things tidier.
 427   Func->getBasicBlockList().remove(NewBB);
 428   Func->getBasicBlockList().insert(++Function::iterator(OldBB), NewBB);
 429
 430   // Construct the new "invoke" instruction.
 431   TerminatorInst* Term = OldBB->getTerminator();
 432   std::vector<Value*> Params(CI.op_begin() + 1, CI.op_end());
 433   InvokeInst* II = new
 434     InvokeInst(CI.getCalledValue(), NewBB, PrelimBBMap[Func],
 435                Params, CI.getName(), Term);
 436
 437   // Replace the old call inst with the invoke inst and remove the call.
 438   CI.replaceAllUsesWith(II);
 439   CI.getParent()->getInstList().erase(&CI);
 440
 441   // The old terminator is useless now that we have the invoke inst.
 442   Term->getParent()->getInstList().erase(Term);
 443 }
 444
 445 // visitInvokeInst - Converting the "invoke" instruction is fairly
 446 // straight-forward. The old exception part is replaced by a query asking
 447 // if this is a longjmp exception. If it is, then it goes to the longjmp
 448 // exception blocks. Otherwise, control is passed the old exception.
 449 void LowerSetJmp::visitInvokeInst(InvokeInst& II)
 450 {
 451   if (II.getCalledFunction())
 452     if (!IsTransformableFunction(II.getCalledFunction()->getName()) ||
 453         II.getCalledFunction()->isIntrinsic()) return;
 454
 455   BasicBlock* BB = II.getParent();
 456   Function* Func = BB->getParent();
 457
 458   // If not reachable from a setjmp call, don't transform.
 459   if (!DFSBlocks.count(BB)) return;
 460
 461   BasicBlock* NormalBB = II.getNormalDest();
 462   BasicBlock* ExceptBB = II.getExceptionalDest();
 463
 464   BasicBlock* NewExceptBB = new BasicBlock("InvokeExcept", Func);
 465   BasicBlock::InstListType& InstList = NewExceptBB->getInstList();
 466
 467   // If this is a longjmp exception, then branch to the preliminary BB of
 468   // the longjmp exception handling. Otherwise, go to the old exception.
 469   CallInst* IsLJExcept = new
 470     CallInst(IsLJException, std::vector<Value*>(), "IsLJExcept");
 471   InstList.push_back(IsLJExcept);
 472
 473   BranchInst* BR = new BranchInst(PrelimBBMap[Func], ExceptBB, IsLJExcept);
 474   InstList.push_back(BR);
 475
 476   II.setExceptionalDest(NewExceptBB);
 477 }
 478
 479 // visitReturnInst - We want to destroy the setjmp map upon exit from the
 480 // function.
 481 void LowerSetJmp::visitReturnInst(ReturnInst& RI)
 482 {
 483   Function* Func = RI.getParent()->getParent();
 484   new CallInst(DestroySJMap, make_vector<Value*>(GetSetJmpMap(Func), 0),
 485                "", &RI);
 486 }
 487
 488 // visitUnwindInst - We want to destroy the setjmp map upon exit from the
 489 // function.
 490 void LowerSetJmp::visitUnwindInst(UnwindInst& UI)
 491 {
 492   Function* Func = UI.getParent()->getParent();
 493   new CallInst(DestroySJMap, make_vector<Value*>(GetSetJmpMap(Func), 0),
 494                "", &UI);
 495 }
 496
 497 Pass* createLowerSetJmpPass()
 498 {
 499   return new LowerSetJmp();
 500 }