1 //===- LowerSetJmp.cpp - Code pertaining to lowering set/long jumps -------===//
3 // This file implements the lowering of setjmp and longjmp to use the
4 // LLVM invoke instruction as necessary.
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.
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.
20 //===----------------------------------------------------------------------===//
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 //===----------------------------------------------------------------------===//
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/InstIterator.h"
36 #include "llvm/Support/InstVisitor.h"
37 #include "Support/Statistic.h"
38 #include "Support/StringExtras.h"
39 #include "Support/VectorExtras.h"
44 Statistic<> LongJmpsTransformed("lowersetjmp",
45 "Number of longjmps transformed");
46 Statistic<> SetJmpsTransformed("lowersetjmp",
47 "Number of setjmps transformed");
49 //===--------------------------------------------------------------------===//
50 // LowerSetJmp pass implementation. This is subclassed from the "Pass"
51 // class because it works on a module as a whole, not a function at a
54 class LowerSetJmp : public Pass,
55 public InstVisitor<LowerSetJmp> {
56 // LLVM library functions...
57 Function* InitSJMap; // __llvm_sjljeh_init_setjmpmap
58 Function* DestroySJMap; // __llvm_sjljeh_destroy_setjmpmap
59 Function* AddSJToMap; // __llvm_sjljeh_add_setjmp_to_map
60 Function* ThrowLongJmp; // __llvm_sjljeh_throw_longjmp
61 Function* TryCatchLJ; // __llvm_sjljeh_try_catching_longjmp_exception
62 Function* IsLJException; // __llvm_sjljeh_is_longjmp_exception
63 Function* GetLJValue; // __llvm_sjljeh_get_longjmp_value
65 typedef std::pair<SwitchInst*, CallInst*> SwitchValuePair;
67 // The setjmp map is going to hold information about which setjmps
68 // were called (each setjmp gets its own number) and with which
69 // buffer it was called.
70 std::map<Function*, AllocaInst*> SJMap;
72 // The rethrow basic block map holds the basic block to branch to if
73 // the exception isn't handled in the current function and needs to
75 std::map<const Function*, BasicBlock*> RethrowBBMap;
77 // The preliminary basic block map holds a basic block that grabs the
78 // exception and determines if it's handled by the current function.
79 std::map<const Function*, BasicBlock*> PrelimBBMap;
81 // The switch/value map holds a switch inst/call inst pair. The
82 // switch inst controls which handler (if any) gets called and the
83 // value is the value returned to that handler by the call to
84 // __llvm_sjljeh_get_longjmp_value.
85 std::map<const Function*, SwitchValuePair> SwitchValMap;
87 // A map of which setjmps we've seen so far in a function.
88 std::map<const Function*, unsigned> SetJmpIDMap;
90 AllocaInst* GetSetJmpMap(Function* Func);
91 BasicBlock* GetRethrowBB(Function* Func);
92 SwitchValuePair GetSJSwitch(Function* Func, BasicBlock* Rethrow);
94 void TransformLongJmpCall(CallInst* Inst);
95 void TransformSetJmpCall(CallInst* Inst);
97 bool IsTransformableFunction(const std::string& Name);
99 void visitCallInst(CallInst& CI);
100 void visitInvokeInst(InvokeInst& II);
101 void visitReturnInst(ReturnInst& RI);
102 void visitUnwindInst(UnwindInst& UI);
105 bool doInitialization(Module& M);
108 RegisterOpt<LowerSetJmp> X("lowersetjmp", "Lower Set Jump");
109 } // end anonymous namespace
111 // run - Run the transformation on the program. We grab the function
112 // prototypes for longjmp and setjmp. If they are used in the program,
113 // then we can go directly to the places they're at and transform them.
114 bool LowerSetJmp::run(Module& M)
116 bool Changed = false;
118 // These are what the functions are called.
119 Function* SetJmp = M.getNamedFunction("llvm.setjmp");
120 Function* LongJmp = M.getNamedFunction("llvm.longjmp");
122 // This program doesn't have longjmp and setjmp calls.
123 if ((!LongJmp || LongJmp->use_empty()) &&
124 (!SetJmp || SetJmp->use_empty())) return false;
126 // Initialize some values and functions we'll need to transform the
127 // setjmp/longjmp functions.
131 while (!SetJmp->use_empty()) {
132 assert(isa<CallInst>(SetJmp->use_back()) &&
133 "User of setjmp intrinsic not a call?");
134 TransformSetJmpCall(cast<CallInst>(SetJmp->use_back()));
139 while (!LongJmp->use_empty()) {
140 assert(isa<CallInst>(LongJmp->use_back()) &&
141 "User of longjmp intrinsic not a call?");
142 TransformLongJmpCall(cast<CallInst>(LongJmp->use_back()));
146 // Now go through the affected functions and convert calls and invokes
148 for (std::map<Function*, AllocaInst*>::iterator
149 B = SJMap.begin(), E = SJMap.end(); B != E; ++B) {
150 Function* F = B->first;
151 for (Function::iterator BB = F->begin(), BE = F->end(); BB != BE; ++BB)
152 for (BasicBlock::iterator IB = BB->begin(), IE = BB->end(); IB != IE; ) {
154 if (IB != BB->end() && IB->getParent() != BB)
155 break; // The next instruction got moved to a different block!
160 RethrowBBMap.clear();
162 SwitchValMap.clear();
168 // doInitialization - For the lower long/setjmp pass, this ensures that a
169 // module contains a declaration for the intrisic functions we are going
170 // to call to convert longjmp and setjmp calls.
172 // This function is always successful, unless it isn't.
173 bool LowerSetJmp::doInitialization(Module& M)
175 const Type *SBPTy = PointerType::get(Type::SByteTy);
176 const Type *SBPPTy = PointerType::get(SBPTy);
178 // N.B. See llvm/runtime/GCCLibraries/libexception/SJLJ-Exception.h for
179 // a description of the following library functions.
181 // void __llvm_sjljeh_init_setjmpmap(void**)
182 InitSJMap = M.getOrInsertFunction("__llvm_sjljeh_init_setjmpmap",
183 Type::VoidTy, SBPPTy, 0);
184 // void __llvm_sjljeh_destroy_setjmpmap(void**)
185 DestroySJMap = M.getOrInsertFunction("__llvm_sjljeh_destroy_setjmpmap",
186 Type::VoidTy, SBPPTy, 0);
188 // void __llvm_sjljeh_add_setjmp_to_map(void**, void*, unsigned)
189 AddSJToMap = M.getOrInsertFunction("__llvm_sjljeh_add_setjmp_to_map",
190 Type::VoidTy, SBPPTy, SBPTy,
193 // void __llvm_sjljeh_throw_longjmp(int*, int)
194 ThrowLongJmp = M.getOrInsertFunction("__llvm_sjljeh_throw_longjmp",
195 Type::VoidTy, SBPTy, Type::IntTy, 0);
197 // unsigned __llvm_sjljeh_try_catching_longjmp_exception(void **)
199 M.getOrInsertFunction("__llvm_sjljeh_try_catching_longjmp_exception",
200 Type::UIntTy, SBPPTy, 0);
202 // bool __llvm_sjljeh_is_longjmp_exception()
203 IsLJException = M.getOrInsertFunction("__llvm_sjljeh_is_longjmp_exception",
206 // int __llvm_sjljeh_get_longjmp_value()
207 GetLJValue = M.getOrInsertFunction("__llvm_sjljeh_get_longjmp_value",
212 // IsTransformableFunction - Return true if the function name isn't one
213 // of the ones we don't want transformed. Currently, don't transform any
214 // "llvm.{setjmp,longjmp}" functions and none of the setjmp/longjmp error
215 // handling functions (beginning with __llvm_sjljeh_...they don't throw
217 bool LowerSetJmp::IsTransformableFunction(const std::string& Name)
219 std::string SJLJEh("__llvm_sjljeh");
221 if (Name.size() > SJLJEh.size()) {
222 std::string N(Name.begin(), Name.begin() + SJLJEh.size());
229 // TransformLongJmpCall - Transform a longjmp call into a call to the
230 // internal __llvm_sjljeh_throw_longjmp function. It then takes care of
231 // throwing the exception for us.
232 void LowerSetJmp::TransformLongJmpCall(CallInst* Inst)
234 const Type* SBPTy = PointerType::get(Type::SByteTy);
236 // Create the call to "__llvm_sjljeh_throw_longjmp". This takes the
237 // same parameters as "longjmp", except that the buffer is cast to a
238 // char*. It returns "void", so it doesn't need to replace any of
239 // Inst's uses and doesn't get a name.
240 CastInst* CI = new CastInst(Inst->getOperand(1), SBPTy, "LJBuf", Inst);
241 new CallInst(ThrowLongJmp, make_vector<Value*>(CI, Inst->getOperand(2), 0),
244 SwitchValuePair& SVP = SwitchValMap[Inst->getParent()->getParent()];
246 // If the function has a setjmp call in it (they are transformed first)
247 // we should branch to the basic block that determines if this longjmp
248 // is applicable here. Otherwise, issue an unwind.
250 new BranchInst(SVP.first->getParent(), Inst);
252 new UnwindInst(Inst);
254 // Remove all insts after the branch/unwind inst.
255 Inst->getParent()->getInstList().erase(Inst,
256 Inst->getParent()->getInstList().end());
258 ++LongJmpsTransformed;
261 // GetSetJmpMap - Retrieve (create and initialize, if necessary) the
262 // setjmp map. This map is going to hold information about which setjmps
263 // were called (each setjmp gets its own number) and with which buffer it
264 // was called. There can be only one!
265 AllocaInst* LowerSetJmp::GetSetJmpMap(Function* Func)
267 if (SJMap[Func]) return SJMap[Func];
269 // Insert the setjmp map initialization before the first instruction in
271 Instruction* Inst = Func->getEntryNode().begin();
272 assert(Inst && "Couldn't find even ONE instruction in entry block!");
274 // Fill in the alloca and call to initialize the SJ map.
275 const Type *SBPTy = PointerType::get(Type::SByteTy);
276 AllocaInst* Map = new AllocaInst(SBPTy, 0, "SJMap", Inst);
277 new CallInst(InitSJMap, make_vector<Value*>(Map, 0), "", Inst);
278 return SJMap[Func] = Map;
281 // GetRethrowBB - Only one rethrow basic block is needed per function.
282 // If this is a longjmp exception but not handled in this block, this BB
283 // performs the rethrow.
284 BasicBlock* LowerSetJmp::GetRethrowBB(Function* Func)
286 if (RethrowBBMap[Func]) return RethrowBBMap[Func];
288 // The basic block we're going to jump to if we need to rethrow the
290 BasicBlock* Rethrow = new BasicBlock("RethrowExcept", Func);
291 BasicBlock::InstListType& RethrowBlkIL = Rethrow->getInstList();
293 // Fill in the "Rethrow" BB with a call to rethrow the exception. This
294 // is the last instruction in the BB since at this point the runtime
295 // should exit this function and go to the next function.
296 RethrowBlkIL.push_back(new UnwindInst());
297 return RethrowBBMap[Func] = Rethrow;
300 // GetSJSwitch - Return the switch statement that controls which handler
301 // (if any) gets called and the value returned to that handler.
302 LowerSetJmp::SwitchValuePair LowerSetJmp::GetSJSwitch(Function* Func,
305 if (SwitchValMap[Func].first) return SwitchValMap[Func];
307 BasicBlock* LongJmpPre = new BasicBlock("LongJmpBlkPre", Func);
308 BasicBlock::InstListType& LongJmpPreIL = LongJmpPre->getInstList();
310 // Keep track of the preliminary basic block for some of the other
312 PrelimBBMap[Func] = LongJmpPre;
314 // Grab the exception.
316 CallInst(IsLJException, std::vector<Value*>(), "IsLJExcept");
317 LongJmpPreIL.push_back(Cond);
319 // The "decision basic block" gets the number associated with the
320 // setjmp call returning to switch on and the value returned by
322 BasicBlock* DecisionBB = new BasicBlock("LJDecisionBB", Func);
323 BasicBlock::InstListType& DecisionBBIL = DecisionBB->getInstList();
325 LongJmpPreIL.push_back(new BranchInst(DecisionBB, Rethrow, Cond));
327 // Fill in the "decision" basic block.
328 CallInst* LJVal = new CallInst(GetLJValue, std::vector<Value*>(), "LJVal");
329 DecisionBBIL.push_back(LJVal);
330 CallInst* SJNum = new
331 CallInst(TryCatchLJ, make_vector<Value*>(GetSetJmpMap(Func), 0), "SJNum");
332 DecisionBBIL.push_back(SJNum);
334 SwitchInst* SI = new SwitchInst(SJNum, Rethrow);
335 DecisionBBIL.push_back(SI);
336 return SwitchValMap[Func] = SwitchValuePair(SI, LJVal);
339 // TransformSetJmpCall - The setjmp call is a bit trickier to transform.
340 // We're going to convert all setjmp calls to nops. Then all "call" and
341 // "invoke" instructions in the function are converted to "invoke" where
342 // the "except" branch is used when returning from a longjmp call.
343 void LowerSetJmp::TransformSetJmpCall(CallInst* Inst)
345 BasicBlock* ABlock = Inst->getParent();
346 Function* Func = ABlock->getParent();
348 // Add this setjmp to the setjmp map.
349 const Type* SBPTy = PointerType::get(Type::SByteTy);
350 CastInst* BufPtr = new CastInst(Inst->getOperand(1), SBPTy, "SBJmpBuf", Inst);
351 new CallInst(AddSJToMap,
352 make_vector<Value*>(GetSetJmpMap(Func), BufPtr,
353 ConstantUInt::get(Type::UIntTy,
354 SetJmpIDMap[Func]++), 0),
357 // FIXME: This is a nasty piece of code. We want the jump buffer to
358 // dominate all uses. However, we're doing unnatural things to the CFG
359 // which cause this dominance to be lost. The only way to guarantee we
360 // get it back is to place where the jump buffer is being allocated
361 // into the entry block. That's what this code does. The alloca for the
362 // jump buffer is followed by a getelementptr call.
363 if (GetElementPtrInst* GEP = dyn_cast<GetElementPtrInst>(Inst->getOperand(1)))
364 if (GEP->use_size() > 1) {
365 if (AllocaInst* AI = dyn_cast<AllocaInst>(GEP->getPointerOperand())) {
366 BasicBlock& Entry = Func->getEntryNode();
367 BasicBlock::InstListType& EntryIL = Entry.getInstList();
369 Instruction* NewAI = AI->clone();
370 Instruction* NewGEP = GEP->clone();
371 NewAI->setName(AI->getName());
372 NewGEP->setName(GEP->getName());
373 EntryIL.push_front(NewGEP);
374 EntryIL.push_front(NewAI);
375 GEP->replaceAllUsesWith(NewGEP);
376 AI->replaceAllUsesWith(NewAI);
380 // Change the setjmp call into a branch statement. We'll remove the
381 // setjmp call in a little bit. No worries.
382 BasicBlock* SetJmpContBlock = ABlock->splitBasicBlock(Inst);
383 assert(SetJmpContBlock && "Couldn't split setjmp BB!!");
385 SetJmpContBlock->setName("SetJmpContBlock");
387 // Reposition the split BB in the BB list to make things tidier.
388 Func->getBasicBlockList().remove(SetJmpContBlock);
389 Func->getBasicBlockList().insert(++Function::iterator(ABlock),
392 // This PHI node will be in the new block created from the
393 // splitBasicBlock call.
394 PHINode* PHI = new PHINode(Type::IntTy, "SetJmpReturn", Inst);
396 // Coming from a call to setjmp, the return is 0.
397 PHI->addIncoming(ConstantInt::getNullValue(Type::IntTy), ABlock);
399 // Add the case for this setjmp's number...
400 SwitchValuePair SVP = GetSJSwitch(Func, GetRethrowBB(Func));
401 SVP.first->addCase(ConstantUInt::get(Type::UIntTy, SetJmpIDMap[Func] - 1),
404 // Value coming from the handling of the exception.
405 PHI->addIncoming(SVP.second, SVP.second->getParent());
407 // Replace all uses of this instruction with the PHI node created by
408 // the eradication of setjmp.
409 Inst->replaceAllUsesWith(PHI);
410 Inst->getParent()->getInstList().erase(Inst);
412 ++SetJmpsTransformed;
415 // visitCallInst - This converts all LLVM call instructions into invoke
416 // instructions. The except part of the invoke goes to the "LongJmpBlkPre"
417 // that grabs the exception and proceeds to determine if it's a longjmp
419 void LowerSetJmp::visitCallInst(CallInst& CI)
421 if (CI.getCalledFunction())
422 if (!IsTransformableFunction(CI.getCalledFunction()->getName()) ||
423 CI.getCalledFunction()->isIntrinsic()) return;
425 BasicBlock* OldBB = CI.getParent();
426 BasicBlock* NewBB = OldBB->splitBasicBlock(CI);
427 assert(NewBB && "Couldn't split BB of \"call\" instruction!!");
428 NewBB->setName("Call2Invoke");
430 // Reposition the split BB in the BB list to make things tidier.
431 Function* Func = OldBB->getParent();
432 Func->getBasicBlockList().remove(NewBB);
433 Func->getBasicBlockList().insert(++Function::iterator(OldBB), NewBB);
435 // Construct the new "invoke" instruction.
436 TerminatorInst* Term = OldBB->getTerminator();
437 std::vector<Value*> Params(CI.op_begin() + 1, CI.op_end());
439 InvokeInst(CI.getCalledValue(), NewBB, PrelimBBMap[Func],
440 Params, CI.getName(), Term);
442 // Replace the old call inst with the invoke inst and remove the call.
443 CI.replaceAllUsesWith(II);
444 CI.getParent()->getInstList().erase(&CI);
446 // The old terminator is useless now that we have the invoke inst.
447 Term->getParent()->getInstList().erase(Term);
450 // visitInvokeInst - Converting the "invoke" instruction is fairly
451 // straight-forward. The old exception part is replaced by a query asking
452 // if this is a longjmp exception. If it is, then it goes to the longjmp
453 // exception blocks. Otherwise, control is passed the old exception.
454 void LowerSetJmp::visitInvokeInst(InvokeInst& II)
456 if (II.getCalledFunction())
457 if (!IsTransformableFunction(II.getCalledFunction()->getName()) ||
458 II.getCalledFunction()->isIntrinsic()) return;
460 Function* Func = II.getParent()->getParent();
462 BasicBlock* NormalBB = II.getNormalDest();
463 BasicBlock* ExceptBB = II.getExceptionalDest();
465 BasicBlock* NewExceptBB = new BasicBlock("InvokeExcept", Func);
466 BasicBlock::InstListType& InstList = NewExceptBB->getInstList();
468 // If this is a longjmp exception, then branch to the preliminary BB of
469 // the longjmp exception handling. Otherwise, go to the old exception.
470 CallInst* IsLJExcept = new
471 CallInst(IsLJException, std::vector<Value*>(), "IsLJExcept");
472 InstList.push_back(IsLJExcept);
474 BranchInst* BR = new BranchInst(PrelimBBMap[Func], ExceptBB, IsLJExcept);
475 InstList.push_back(BR);
477 II.setExceptionalDest(NewExceptBB);
480 // visitReturnInst - We want to destroy the setjmp map upon exit from the
482 void LowerSetJmp::visitReturnInst(ReturnInst& RI)
484 Function* Func = RI.getParent()->getParent();
485 new CallInst(DestroySJMap, make_vector<Value*>(GetSetJmpMap(Func), 0),
489 // visitUnwindInst - We want to destroy the setjmp map upon exit from the
491 void LowerSetJmp::visitUnwindInst(UnwindInst& UI)
493 Function* Func = UI.getParent()->getParent();
494 new CallInst(DestroySJMap, make_vector<Value*>(GetSetJmpMap(Func), 0),
498 Pass* createLowerSetJmpPass()
500 return new LowerSetJmp();