1 //===- LowerSetJmp.cpp - Code pertaining to lowering set/long jumps -------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the lowering of setjmp and longjmp to use the
11 // LLVM invoke and unwind instructions as necessary.
13 // Lowering of longjmp is fairly trivial. We replace the call with a
14 // call to the LLVM library function "__llvm_sjljeh_throw_longjmp()".
15 // This unwinds the stack for us calling all of the destructors for
16 // objects allocated on the stack.
18 // At a setjmp call, the basic block is split and the setjmp removed.
19 // The calls in a function that have a setjmp are converted to invoke
20 // where the except part checks to see if it's a longjmp exception and,
21 // if so, if it's handled in the function. If it is, then it gets the
22 // value returned by the longjmp and goes to where the basic block was
23 // split. Invoke instructions are handled in a similar fashion with the
24 // original except block being executed if it isn't a longjmp except
25 // that is handled by that function.
27 //===----------------------------------------------------------------------===//
29 //===----------------------------------------------------------------------===//
30 // FIXME: This pass doesn't deal with PHI statements just yet. That is,
31 // we expect this to occur before SSAification is done. This would seem
32 // to make sense, but in general, it might be a good idea to make this
33 // pass invokable via the "opt" command at will.
34 //===----------------------------------------------------------------------===//
36 #include "llvm/Transforms/IPO.h"
37 #include "llvm/Constants.h"
38 #include "llvm/DerivedTypes.h"
39 #include "llvm/Instructions.h"
40 #include "llvm/Intrinsics.h"
41 #include "llvm/Module.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/CFG.h"
44 #include "llvm/Support/InstVisitor.h"
45 #include "llvm/Transforms/Utils/Local.h"
46 #include "Support/DepthFirstIterator.h"
47 #include "Support/Statistic.h"
48 #include "Support/StringExtras.h"
49 #include "Support/VectorExtras.h"
53 Statistic<> LongJmpsTransformed("lowersetjmp",
54 "Number of longjmps transformed");
55 Statistic<> SetJmpsTransformed("lowersetjmp",
56 "Number of setjmps transformed");
57 Statistic<> CallsTransformed("lowersetjmp",
58 "Number of calls invokified");
59 Statistic<> InvokesTransformed("lowersetjmp",
60 "Number of invokes modified");
62 //===--------------------------------------------------------------------===//
63 // LowerSetJmp pass implementation. This is subclassed from the "Pass"
64 // class because it works on a module as a whole, not a function at a
67 class LowerSetJmp : public Pass,
68 public InstVisitor<LowerSetJmp> {
69 // LLVM library functions...
70 Function* InitSJMap; // __llvm_sjljeh_init_setjmpmap
71 Function* DestroySJMap; // __llvm_sjljeh_destroy_setjmpmap
72 Function* AddSJToMap; // __llvm_sjljeh_add_setjmp_to_map
73 Function* ThrowLongJmp; // __llvm_sjljeh_throw_longjmp
74 Function* TryCatchLJ; // __llvm_sjljeh_try_catching_longjmp_exception
75 Function* IsLJException; // __llvm_sjljeh_is_longjmp_exception
76 Function* GetLJValue; // __llvm_sjljeh_get_longjmp_value
78 typedef std::pair<SwitchInst*, CallInst*> SwitchValuePair;
80 // Keep track of those basic blocks reachable via a depth-first search of
81 // the CFG from a setjmp call. We only need to transform those "call" and
82 // "invoke" instructions that are reachable from the setjmp call site.
83 std::set<BasicBlock*> DFSBlocks;
85 // The setjmp map is going to hold information about which setjmps
86 // were called (each setjmp gets its own number) and with which
87 // buffer it was called.
88 std::map<Function*, AllocaInst*> SJMap;
90 // The rethrow basic block map holds the basic block to branch to if
91 // the exception isn't handled in the current function and needs to
93 std::map<const Function*, BasicBlock*> RethrowBBMap;
95 // The preliminary basic block map holds a basic block that grabs the
96 // exception and determines if it's handled by the current function.
97 std::map<const Function*, BasicBlock*> PrelimBBMap;
99 // The switch/value map holds a switch inst/call inst pair. The
100 // switch inst controls which handler (if any) gets called and the
101 // value is the value returned to that handler by the call to
102 // __llvm_sjljeh_get_longjmp_value.
103 std::map<const Function*, SwitchValuePair> SwitchValMap;
105 // A map of which setjmps we've seen so far in a function.
106 std::map<const Function*, unsigned> SetJmpIDMap;
108 AllocaInst* GetSetJmpMap(Function* Func);
109 BasicBlock* GetRethrowBB(Function* Func);
110 SwitchValuePair GetSJSwitch(Function* Func, BasicBlock* Rethrow);
112 void TransformLongJmpCall(CallInst* Inst);
113 void TransformSetJmpCall(CallInst* Inst);
115 bool IsTransformableFunction(const std::string& Name);
117 void visitCallInst(CallInst& CI);
118 void visitInvokeInst(InvokeInst& II);
119 void visitReturnInst(ReturnInst& RI);
120 void visitUnwindInst(UnwindInst& UI);
123 bool doInitialization(Module& M);
126 RegisterOpt<LowerSetJmp> X("lowersetjmp", "Lower Set Jump");
127 } // end anonymous namespace
129 // run - Run the transformation on the program. We grab the function
130 // prototypes for longjmp and setjmp. If they are used in the program,
131 // then we can go directly to the places they're at and transform them.
132 bool LowerSetJmp::run(Module& M)
134 bool Changed = false;
136 // These are what the functions are called.
137 Function* SetJmp = M.getNamedFunction("llvm.setjmp");
138 Function* LongJmp = M.getNamedFunction("llvm.longjmp");
140 // This program doesn't have longjmp and setjmp calls.
141 if ((!LongJmp || LongJmp->use_empty()) &&
142 (!SetJmp || SetJmp->use_empty())) return false;
144 // Initialize some values and functions we'll need to transform the
145 // setjmp/longjmp functions.
149 for (Value::use_iterator B = SetJmp->use_begin(), E = SetJmp->use_end();
151 BasicBlock* BB = cast<Instruction>(*B)->getParent();
152 for (df_ext_iterator<BasicBlock*> I = df_ext_begin(BB, DFSBlocks),
153 E = df_ext_end(BB, DFSBlocks); I != E; ++I)
157 while (!SetJmp->use_empty()) {
158 assert(isa<CallInst>(SetJmp->use_back()) &&
159 "User of setjmp intrinsic not a call?");
160 TransformSetJmpCall(cast<CallInst>(SetJmp->use_back()));
166 while (!LongJmp->use_empty()) {
167 assert(isa<CallInst>(LongJmp->use_back()) &&
168 "User of longjmp intrinsic not a call?");
169 TransformLongJmpCall(cast<CallInst>(LongJmp->use_back()));
173 // Now go through the affected functions and convert calls and invokes
175 for (std::map<Function*, AllocaInst*>::iterator
176 B = SJMap.begin(), E = SJMap.end(); B != E; ++B) {
177 Function* F = B->first;
178 for (Function::iterator BB = F->begin(), BE = F->end(); BB != BE; ++BB)
179 for (BasicBlock::iterator IB = BB->begin(), IE = BB->end(); IB != IE; ) {
181 if (IB != BB->end() && IB->getParent() != BB)
182 break; // The next instruction got moved to a different block!
188 RethrowBBMap.clear();
190 SwitchValMap.clear();
196 // doInitialization - For the lower long/setjmp pass, this ensures that a
197 // module contains a declaration for the intrisic functions we are going
198 // to call to convert longjmp and setjmp calls.
200 // This function is always successful, unless it isn't.
201 bool LowerSetJmp::doInitialization(Module& M)
203 const Type *SBPTy = PointerType::get(Type::SByteTy);
204 const Type *SBPPTy = PointerType::get(SBPTy);
206 // N.B. See llvm/runtime/GCCLibraries/libexception/SJLJ-Exception.h for
207 // a description of the following library functions.
209 // void __llvm_sjljeh_init_setjmpmap(void**)
210 InitSJMap = M.getOrInsertFunction("__llvm_sjljeh_init_setjmpmap",
211 Type::VoidTy, SBPPTy, 0);
212 // void __llvm_sjljeh_destroy_setjmpmap(void**)
213 DestroySJMap = M.getOrInsertFunction("__llvm_sjljeh_destroy_setjmpmap",
214 Type::VoidTy, SBPPTy, 0);
216 // void __llvm_sjljeh_add_setjmp_to_map(void**, void*, unsigned)
217 AddSJToMap = M.getOrInsertFunction("__llvm_sjljeh_add_setjmp_to_map",
218 Type::VoidTy, SBPPTy, SBPTy,
221 // void __llvm_sjljeh_throw_longjmp(int*, int)
222 ThrowLongJmp = M.getOrInsertFunction("__llvm_sjljeh_throw_longjmp",
223 Type::VoidTy, SBPTy, Type::IntTy, 0);
225 // unsigned __llvm_sjljeh_try_catching_longjmp_exception(void **)
227 M.getOrInsertFunction("__llvm_sjljeh_try_catching_longjmp_exception",
228 Type::UIntTy, SBPPTy, 0);
230 // bool __llvm_sjljeh_is_longjmp_exception()
231 IsLJException = M.getOrInsertFunction("__llvm_sjljeh_is_longjmp_exception",
234 // int __llvm_sjljeh_get_longjmp_value()
235 GetLJValue = M.getOrInsertFunction("__llvm_sjljeh_get_longjmp_value",
240 // IsTransformableFunction - Return true if the function name isn't one
241 // of the ones we don't want transformed. Currently, don't transform any
242 // "llvm.{setjmp,longjmp}" functions and none of the setjmp/longjmp error
243 // handling functions (beginning with __llvm_sjljeh_...they don't throw
245 bool LowerSetJmp::IsTransformableFunction(const std::string& Name)
247 std::string SJLJEh("__llvm_sjljeh");
249 if (Name.size() > SJLJEh.size())
250 return std::string(Name.begin(), Name.begin() + SJLJEh.size()) != SJLJEh;
255 // TransformLongJmpCall - Transform a longjmp call into a call to the
256 // internal __llvm_sjljeh_throw_longjmp function. It then takes care of
257 // throwing the exception for us.
258 void LowerSetJmp::TransformLongJmpCall(CallInst* Inst)
260 const Type* SBPTy = PointerType::get(Type::SByteTy);
262 // Create the call to "__llvm_sjljeh_throw_longjmp". This takes the
263 // same parameters as "longjmp", except that the buffer is cast to a
264 // char*. It returns "void", so it doesn't need to replace any of
265 // Inst's uses and doesn't get a name.
266 CastInst* CI = new CastInst(Inst->getOperand(1), SBPTy, "LJBuf", Inst);
267 new CallInst(ThrowLongJmp, make_vector<Value*>(CI, Inst->getOperand(2), 0),
270 SwitchValuePair& SVP = SwitchValMap[Inst->getParent()->getParent()];
272 // If the function has a setjmp call in it (they are transformed first)
273 // we should branch to the basic block that determines if this longjmp
274 // is applicable here. Otherwise, issue an unwind.
276 new BranchInst(SVP.first->getParent(), Inst);
278 new UnwindInst(Inst);
280 // Remove all insts after the branch/unwind inst.
281 Inst->getParent()->getInstList().erase(Inst,
282 Inst->getParent()->getInstList().end());
284 ++LongJmpsTransformed;
287 // GetSetJmpMap - Retrieve (create and initialize, if necessary) the
288 // setjmp map. This map is going to hold information about which setjmps
289 // were called (each setjmp gets its own number) and with which buffer it
290 // was called. There can be only one!
291 AllocaInst* LowerSetJmp::GetSetJmpMap(Function* Func)
293 if (SJMap[Func]) return SJMap[Func];
295 // Insert the setjmp map initialization before the first instruction in
297 Instruction* Inst = Func->getEntryBlock().begin();
298 assert(Inst && "Couldn't find even ONE instruction in entry block!");
300 // Fill in the alloca and call to initialize the SJ map.
301 const Type *SBPTy = PointerType::get(Type::SByteTy);
302 AllocaInst* Map = new AllocaInst(SBPTy, 0, "SJMap", Inst);
303 new CallInst(InitSJMap, make_vector<Value*>(Map, 0), "", Inst);
304 return SJMap[Func] = Map;
307 // GetRethrowBB - Only one rethrow basic block is needed per function.
308 // If this is a longjmp exception but not handled in this block, this BB
309 // performs the rethrow.
310 BasicBlock* LowerSetJmp::GetRethrowBB(Function* Func)
312 if (RethrowBBMap[Func]) return RethrowBBMap[Func];
314 // The basic block we're going to jump to if we need to rethrow the
316 BasicBlock* Rethrow = new BasicBlock("RethrowExcept", Func);
318 // Fill in the "Rethrow" BB with a call to rethrow the exception. This
319 // is the last instruction in the BB since at this point the runtime
320 // should exit this function and go to the next function.
321 new UnwindInst(Rethrow);
322 return RethrowBBMap[Func] = Rethrow;
325 // GetSJSwitch - Return the switch statement that controls which handler
326 // (if any) gets called and the value returned to that handler.
327 LowerSetJmp::SwitchValuePair LowerSetJmp::GetSJSwitch(Function* Func,
330 if (SwitchValMap[Func].first) return SwitchValMap[Func];
332 BasicBlock* LongJmpPre = new BasicBlock("LongJmpBlkPre", Func);
333 BasicBlock::InstListType& LongJmpPreIL = LongJmpPre->getInstList();
335 // Keep track of the preliminary basic block for some of the other
337 PrelimBBMap[Func] = LongJmpPre;
339 // Grab the exception.
341 CallInst(IsLJException, std::vector<Value*>(), "IsLJExcept");
342 LongJmpPreIL.push_back(Cond);
344 // The "decision basic block" gets the number associated with the
345 // setjmp call returning to switch on and the value returned by
347 BasicBlock* DecisionBB = new BasicBlock("LJDecisionBB", Func);
348 BasicBlock::InstListType& DecisionBBIL = DecisionBB->getInstList();
350 new BranchInst(DecisionBB, Rethrow, Cond, LongJmpPre);
352 // Fill in the "decision" basic block.
353 CallInst* LJVal = new CallInst(GetLJValue, std::vector<Value*>(), "LJVal");
354 DecisionBBIL.push_back(LJVal);
355 CallInst* SJNum = new
356 CallInst(TryCatchLJ, make_vector<Value*>(GetSetJmpMap(Func), 0), "SJNum");
357 DecisionBBIL.push_back(SJNum);
359 SwitchInst* SI = new SwitchInst(SJNum, Rethrow, DecisionBB);
360 return SwitchValMap[Func] = SwitchValuePair(SI, LJVal);
363 // TransformSetJmpCall - The setjmp call is a bit trickier to transform.
364 // We're going to convert all setjmp calls to nops. Then all "call" and
365 // "invoke" instructions in the function are converted to "invoke" where
366 // the "except" branch is used when returning from a longjmp call.
367 void LowerSetJmp::TransformSetJmpCall(CallInst* Inst)
369 BasicBlock* ABlock = Inst->getParent();
370 Function* Func = ABlock->getParent();
372 // Add this setjmp to the setjmp map.
373 const Type* SBPTy = PointerType::get(Type::SByteTy);
374 CastInst* BufPtr = new CastInst(Inst->getOperand(1), SBPTy, "SBJmpBuf", Inst);
375 new CallInst(AddSJToMap,
376 make_vector<Value*>(GetSetJmpMap(Func), BufPtr,
377 ConstantUInt::get(Type::UIntTy,
378 SetJmpIDMap[Func]++), 0),
381 // We are guaranteed that there are no values live across basic blocks
382 // (because we are "not in SSA form" yet), but there can still be values live
383 // in basic blocks. Because of this, splitting the setjmp block can cause
384 // values above the setjmp to not dominate uses which are after the setjmp
385 // call. For all of these occasions, we must spill the value to the stack.
387 std::set<Instruction*> InstrsAfterCall;
389 // The call is probably very close to the end of the basic block, for the
390 // common usage pattern of: 'if (setjmp(...))', so keep track of the
391 // instructions after the call.
392 for (BasicBlock::iterator I = ++BasicBlock::iterator(Inst), E = ABlock->end();
394 InstrsAfterCall.insert(I);
396 for (BasicBlock::iterator II = ABlock->begin();
397 II != BasicBlock::iterator(Inst); ++II)
398 // Loop over all of the uses of instruction. If any of them are after the
399 // call, "spill" the value to the stack.
400 for (Value::use_iterator UI = II->use_begin(), E = II->use_end();
402 if (cast<Instruction>(*UI)->getParent() != ABlock ||
403 InstrsAfterCall.count(cast<Instruction>(*UI))) {
404 DemoteRegToStack(*II);
407 InstrsAfterCall.clear();
409 // Change the setjmp call into a branch statement. We'll remove the
410 // setjmp call in a little bit. No worries.
411 BasicBlock* SetJmpContBlock = ABlock->splitBasicBlock(Inst);
412 assert(SetJmpContBlock && "Couldn't split setjmp BB!!");
414 SetJmpContBlock->setName("SetJmpContBlock");
416 // This PHI node will be in the new block created from the
417 // splitBasicBlock call.
418 PHINode* PHI = new PHINode(Type::IntTy, "SetJmpReturn", Inst);
420 // Coming from a call to setjmp, the return is 0.
421 PHI->addIncoming(ConstantInt::getNullValue(Type::IntTy), ABlock);
423 // Add the case for this setjmp's number...
424 SwitchValuePair SVP = GetSJSwitch(Func, GetRethrowBB(Func));
425 SVP.first->addCase(ConstantUInt::get(Type::UIntTy, SetJmpIDMap[Func] - 1),
428 // Value coming from the handling of the exception.
429 PHI->addIncoming(SVP.second, SVP.second->getParent());
431 // Replace all uses of this instruction with the PHI node created by
432 // the eradication of setjmp.
433 Inst->replaceAllUsesWith(PHI);
434 Inst->getParent()->getInstList().erase(Inst);
436 ++SetJmpsTransformed;
439 // visitCallInst - This converts all LLVM call instructions into invoke
440 // instructions. The except part of the invoke goes to the "LongJmpBlkPre"
441 // that grabs the exception and proceeds to determine if it's a longjmp
443 void LowerSetJmp::visitCallInst(CallInst& CI)
445 if (CI.getCalledFunction())
446 if (!IsTransformableFunction(CI.getCalledFunction()->getName()) ||
447 CI.getCalledFunction()->isIntrinsic()) return;
449 BasicBlock* OldBB = CI.getParent();
451 // If not reachable from a setjmp call, don't transform.
452 if (!DFSBlocks.count(OldBB)) return;
454 BasicBlock* NewBB = OldBB->splitBasicBlock(CI);
455 assert(NewBB && "Couldn't split BB of \"call\" instruction!!");
456 NewBB->setName("Call2Invoke");
458 Function* Func = OldBB->getParent();
460 // Construct the new "invoke" instruction.
461 TerminatorInst* Term = OldBB->getTerminator();
462 std::vector<Value*> Params(CI.op_begin() + 1, CI.op_end());
464 InvokeInst(CI.getCalledValue(), NewBB, PrelimBBMap[Func],
465 Params, CI.getName(), Term);
467 // Replace the old call inst with the invoke inst and remove the call.
468 CI.replaceAllUsesWith(II);
469 CI.getParent()->getInstList().erase(&CI);
471 // The old terminator is useless now that we have the invoke inst.
472 Term->getParent()->getInstList().erase(Term);
476 // visitInvokeInst - Converting the "invoke" instruction is fairly
477 // straight-forward. The old exception part is replaced by a query asking
478 // if this is a longjmp exception. If it is, then it goes to the longjmp
479 // exception blocks. Otherwise, control is passed the old exception.
480 void LowerSetJmp::visitInvokeInst(InvokeInst& II)
482 if (II.getCalledFunction())
483 if (!IsTransformableFunction(II.getCalledFunction()->getName()) ||
484 II.getCalledFunction()->isIntrinsic()) return;
486 BasicBlock* BB = II.getParent();
488 // If not reachable from a setjmp call, don't transform.
489 if (!DFSBlocks.count(BB)) return;
491 BasicBlock* NormalBB = II.getNormalDest();
492 BasicBlock* ExceptBB = II.getUnwindDest();
494 Function* Func = BB->getParent();
495 BasicBlock* NewExceptBB = new BasicBlock("InvokeExcept", Func);
496 BasicBlock::InstListType& InstList = NewExceptBB->getInstList();
498 // If this is a longjmp exception, then branch to the preliminary BB of
499 // the longjmp exception handling. Otherwise, go to the old exception.
500 CallInst* IsLJExcept = new
501 CallInst(IsLJException, std::vector<Value*>(), "IsLJExcept");
502 InstList.push_back(IsLJExcept);
504 new BranchInst(PrelimBBMap[Func], ExceptBB, IsLJExcept, NewExceptBB);
506 II.setUnwindDest(NewExceptBB);
507 ++InvokesTransformed;
510 // visitReturnInst - We want to destroy the setjmp map upon exit from the
512 void LowerSetJmp::visitReturnInst(ReturnInst& RI)
514 Function* Func = RI.getParent()->getParent();
515 new CallInst(DestroySJMap, make_vector<Value*>(GetSetJmpMap(Func), 0),
519 // visitUnwindInst - We want to destroy the setjmp map upon exit from the
521 void LowerSetJmp::visitUnwindInst(UnwindInst& UI)
523 Function* Func = UI.getParent()->getParent();
524 new CallInst(DestroySJMap, make_vector<Value*>(GetSetJmpMap(Func), 0),
528 Pass* llvm::createLowerSetJmpPass()
530 return new LowerSetJmp();