1 //===- LowerSetJmp.cpp - Code pertaining to lowering set/long jumps -------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // 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 #define DEBUG_TYPE "lowersetjmp"
37 #include "llvm/Transforms/IPO.h"
38 #include "llvm/Constants.h"
39 #include "llvm/DerivedTypes.h"
40 #include "llvm/Instructions.h"
41 #include "llvm/Intrinsics.h"
42 #include "llvm/LLVMContext.h"
43 #include "llvm/Module.h"
44 #include "llvm/Pass.h"
45 #include "llvm/Support/CallSite.h"
46 #include "llvm/Support/CFG.h"
47 #include "llvm/Support/InstVisitor.h"
48 #include "llvm/Transforms/Utils/Local.h"
49 #include "llvm/ADT/DepthFirstIterator.h"
50 #include "llvm/ADT/Statistic.h"
54 STATISTIC(LongJmpsTransformed
, "Number of longjmps transformed");
55 STATISTIC(SetJmpsTransformed
, "Number of setjmps transformed");
56 STATISTIC(CallsTransformed
, "Number of calls invokified");
57 STATISTIC(InvokesTransformed
, "Number of invokes modified");
60 //===--------------------------------------------------------------------===//
61 // LowerSetJmp pass implementation.
62 class LowerSetJmp
: public ModulePass
, public InstVisitor
<LowerSetJmp
> {
63 // LLVM library functions...
64 Constant
*InitSJMap
; // __llvm_sjljeh_init_setjmpmap
65 Constant
*DestroySJMap
; // __llvm_sjljeh_destroy_setjmpmap
66 Constant
*AddSJToMap
; // __llvm_sjljeh_add_setjmp_to_map
67 Constant
*ThrowLongJmp
; // __llvm_sjljeh_throw_longjmp
68 Constant
*TryCatchLJ
; // __llvm_sjljeh_try_catching_longjmp_exception
69 Constant
*IsLJException
; // __llvm_sjljeh_is_longjmp_exception
70 Constant
*GetLJValue
; // __llvm_sjljeh_get_longjmp_value
72 typedef std::pair
<SwitchInst
*, CallInst
*> SwitchValuePair
;
74 // Keep track of those basic blocks reachable via a depth-first search of
75 // the CFG from a setjmp call. We only need to transform those "call" and
76 // "invoke" instructions that are reachable from the setjmp call site.
77 std::set
<BasicBlock
*> DFSBlocks
;
79 // The setjmp map is going to hold information about which setjmps
80 // were called (each setjmp gets its own number) and with which
81 // buffer it was called.
82 std::map
<Function
*, AllocaInst
*> SJMap
;
84 // The rethrow basic block map holds the basic block to branch to if
85 // the exception isn't handled in the current function and needs to
87 std::map
<const Function
*, BasicBlock
*> RethrowBBMap
;
89 // The preliminary basic block map holds a basic block that grabs the
90 // exception and determines if it's handled by the current function.
91 std::map
<const Function
*, BasicBlock
*> PrelimBBMap
;
93 // The switch/value map holds a switch inst/call inst pair. The
94 // switch inst controls which handler (if any) gets called and the
95 // value is the value returned to that handler by the call to
96 // __llvm_sjljeh_get_longjmp_value.
97 std::map
<const Function
*, SwitchValuePair
> SwitchValMap
;
99 // A map of which setjmps we've seen so far in a function.
100 std::map
<const Function
*, unsigned> SetJmpIDMap
;
102 AllocaInst
* GetSetJmpMap(Function
* Func
);
103 BasicBlock
* GetRethrowBB(Function
* Func
);
104 SwitchValuePair
GetSJSwitch(Function
* Func
, BasicBlock
* Rethrow
);
106 void TransformLongJmpCall(CallInst
* Inst
);
107 void TransformSetJmpCall(CallInst
* Inst
);
109 bool IsTransformableFunction(StringRef Name
);
111 static char ID
; // Pass identification, replacement for typeid
112 LowerSetJmp() : ModulePass(ID
) {}
114 void visitCallInst(CallInst
& CI
);
115 void visitInvokeInst(InvokeInst
& II
);
116 void visitReturnInst(ReturnInst
& RI
);
117 void visitUnwindInst(UnwindInst
& UI
);
119 bool runOnModule(Module
& M
);
120 bool doInitialization(Module
& M
);
122 } // end anonymous namespace
124 char LowerSetJmp::ID
= 0;
125 INITIALIZE_PASS(LowerSetJmp
, "lowersetjmp", "Lower Set Jump", false, false);
127 // run - Run the transformation on the program. We grab the function
128 // prototypes for longjmp and setjmp. If they are used in the program,
129 // then we can go directly to the places they're at and transform them.
130 bool LowerSetJmp::runOnModule(Module
& M
) {
131 bool Changed
= false;
133 // These are what the functions are called.
134 Function
* SetJmp
= M
.getFunction("llvm.setjmp");
135 Function
* LongJmp
= M
.getFunction("llvm.longjmp");
137 // This program doesn't have longjmp and setjmp calls.
138 if ((!LongJmp
|| LongJmp
->use_empty()) &&
139 (!SetJmp
|| SetJmp
->use_empty())) return false;
141 // Initialize some values and functions we'll need to transform the
142 // setjmp/longjmp functions.
146 for (Value::use_iterator B
= SetJmp
->use_begin(), E
= SetJmp
->use_end();
148 BasicBlock
* BB
= cast
<Instruction
>(*B
)->getParent();
149 for (df_ext_iterator
<BasicBlock
*> I
= df_ext_begin(BB
, DFSBlocks
),
150 E
= df_ext_end(BB
, DFSBlocks
); I
!= E
; ++I
)
154 while (!SetJmp
->use_empty()) {
155 assert(isa
<CallInst
>(SetJmp
->use_back()) &&
156 "User of setjmp intrinsic not a call?");
157 TransformSetJmpCall(cast
<CallInst
>(SetJmp
->use_back()));
163 while (!LongJmp
->use_empty()) {
164 assert(isa
<CallInst
>(LongJmp
->use_back()) &&
165 "User of longjmp intrinsic not a call?");
166 TransformLongJmpCall(cast
<CallInst
>(LongJmp
->use_back()));
170 // Now go through the affected functions and convert calls and invokes
172 for (std::map
<Function
*, AllocaInst
*>::iterator
173 B
= SJMap
.begin(), E
= SJMap
.end(); B
!= E
; ++B
) {
174 Function
* F
= B
->first
;
175 for (Function::iterator BB
= F
->begin(), BE
= F
->end(); BB
!= BE
; ++BB
)
176 for (BasicBlock::iterator IB
= BB
->begin(), IE
= BB
->end(); IB
!= IE
; ) {
178 if (IB
!= BB
->end() && IB
->getParent() != BB
)
179 break; // The next instruction got moved to a different block!
185 RethrowBBMap
.clear();
187 SwitchValMap
.clear();
193 // doInitialization - For the lower long/setjmp pass, this ensures that a
194 // module contains a declaration for the intrisic functions we are going
195 // to call to convert longjmp and setjmp calls.
197 // This function is always successful, unless it isn't.
198 bool LowerSetJmp::doInitialization(Module
& M
)
200 const Type
*SBPTy
= Type::getInt8PtrTy(M
.getContext());
201 const Type
*SBPPTy
= PointerType::getUnqual(SBPTy
);
203 // N.B. See llvm/runtime/GCCLibraries/libexception/SJLJ-Exception.h for
204 // a description of the following library functions.
206 // void __llvm_sjljeh_init_setjmpmap(void**)
207 InitSJMap
= M
.getOrInsertFunction("__llvm_sjljeh_init_setjmpmap",
208 Type::getVoidTy(M
.getContext()),
210 // void __llvm_sjljeh_destroy_setjmpmap(void**)
211 DestroySJMap
= M
.getOrInsertFunction("__llvm_sjljeh_destroy_setjmpmap",
212 Type::getVoidTy(M
.getContext()),
215 // void __llvm_sjljeh_add_setjmp_to_map(void**, void*, unsigned)
216 AddSJToMap
= M
.getOrInsertFunction("__llvm_sjljeh_add_setjmp_to_map",
217 Type::getVoidTy(M
.getContext()),
219 Type::getInt32Ty(M
.getContext()),
222 // void __llvm_sjljeh_throw_longjmp(int*, int)
223 ThrowLongJmp
= M
.getOrInsertFunction("__llvm_sjljeh_throw_longjmp",
224 Type::getVoidTy(M
.getContext()), SBPTy
,
225 Type::getInt32Ty(M
.getContext()),
228 // unsigned __llvm_sjljeh_try_catching_longjmp_exception(void **)
230 M
.getOrInsertFunction("__llvm_sjljeh_try_catching_longjmp_exception",
231 Type::getInt32Ty(M
.getContext()), SBPPTy
, (Type
*)0);
233 // bool __llvm_sjljeh_is_longjmp_exception()
234 IsLJException
= M
.getOrInsertFunction("__llvm_sjljeh_is_longjmp_exception",
235 Type::getInt1Ty(M
.getContext()),
238 // int __llvm_sjljeh_get_longjmp_value()
239 GetLJValue
= M
.getOrInsertFunction("__llvm_sjljeh_get_longjmp_value",
240 Type::getInt32Ty(M
.getContext()),
245 // IsTransformableFunction - Return true if the function name isn't one
246 // of the ones we don't want transformed. Currently, don't transform any
247 // "llvm.{setjmp,longjmp}" functions and none of the setjmp/longjmp error
248 // handling functions (beginning with __llvm_sjljeh_...they don't throw
250 bool LowerSetJmp::IsTransformableFunction(StringRef Name
) {
251 return !Name
.startswith("__llvm_sjljeh_");
254 // TransformLongJmpCall - Transform a longjmp call into a call to the
255 // internal __llvm_sjljeh_throw_longjmp function. It then takes care of
256 // throwing the exception for us.
257 void LowerSetJmp::TransformLongJmpCall(CallInst
* Inst
)
259 const Type
* SBPTy
= Type::getInt8PtrTy(Inst
->getContext());
261 // Create the call to "__llvm_sjljeh_throw_longjmp". This takes the
262 // same parameters as "longjmp", except that the buffer is cast to a
263 // char*. It returns "void", so it doesn't need to replace any of
264 // Inst's uses and doesn't get a name.
266 new BitCastInst(Inst
->getArgOperand(0), SBPTy
, "LJBuf", Inst
);
267 Value
*Args
[] = { CI
, Inst
->getArgOperand(1) };
268 CallInst::Create(ThrowLongJmp
, Args
, Args
+ 2, "", Inst
);
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 BranchInst::Create(SVP
.first
->getParent(), Inst
);
278 new UnwindInst(Inst
->getContext(), Inst
);
280 // Remove all insts after the branch/unwind inst. Go from back to front to
281 // avoid replaceAllUsesWith if possible.
282 BasicBlock
*BB
= Inst
->getParent();
283 Instruction
*Removed
;
285 Removed
= &BB
->back();
286 // If the removed instructions have any users, replace them now.
287 if (!Removed
->use_empty())
288 Removed
->replaceAllUsesWith(UndefValue::get(Removed
->getType()));
289 Removed
->eraseFromParent();
290 } while (Removed
!= Inst
);
292 ++LongJmpsTransformed
;
295 // GetSetJmpMap - Retrieve (create and initialize, if necessary) the
296 // setjmp map. This map is going to hold information about which setjmps
297 // were called (each setjmp gets its own number) and with which buffer it
298 // was called. There can be only one!
299 AllocaInst
* LowerSetJmp::GetSetJmpMap(Function
* Func
)
301 if (SJMap
[Func
]) return SJMap
[Func
];
303 // Insert the setjmp map initialization before the first instruction in
305 Instruction
* Inst
= Func
->getEntryBlock().begin();
306 assert(Inst
&& "Couldn't find even ONE instruction in entry block!");
308 // Fill in the alloca and call to initialize the SJ map.
310 Type::getInt8PtrTy(Func
->getContext());
311 AllocaInst
* Map
= new AllocaInst(SBPTy
, 0, "SJMap", Inst
);
312 CallInst::Create(InitSJMap
, Map
, "", Inst
);
313 return SJMap
[Func
] = Map
;
316 // GetRethrowBB - Only one rethrow basic block is needed per function.
317 // If this is a longjmp exception but not handled in this block, this BB
318 // performs the rethrow.
319 BasicBlock
* LowerSetJmp::GetRethrowBB(Function
* Func
)
321 if (RethrowBBMap
[Func
]) return RethrowBBMap
[Func
];
323 // The basic block we're going to jump to if we need to rethrow the
325 BasicBlock
* Rethrow
=
326 BasicBlock::Create(Func
->getContext(), "RethrowExcept", Func
);
328 // Fill in the "Rethrow" BB with a call to rethrow the exception. This
329 // is the last instruction in the BB since at this point the runtime
330 // should exit this function and go to the next function.
331 new UnwindInst(Func
->getContext(), Rethrow
);
332 return RethrowBBMap
[Func
] = Rethrow
;
335 // GetSJSwitch - Return the switch statement that controls which handler
336 // (if any) gets called and the value returned to that handler.
337 LowerSetJmp::SwitchValuePair
LowerSetJmp::GetSJSwitch(Function
* Func
,
340 if (SwitchValMap
[Func
].first
) return SwitchValMap
[Func
];
342 BasicBlock
* LongJmpPre
=
343 BasicBlock::Create(Func
->getContext(), "LongJmpBlkPre", Func
);
345 // Keep track of the preliminary basic block for some of the other
347 PrelimBBMap
[Func
] = LongJmpPre
;
349 // Grab the exception.
350 CallInst
* Cond
= CallInst::Create(IsLJException
, "IsLJExcept", LongJmpPre
);
352 // The "decision basic block" gets the number associated with the
353 // setjmp call returning to switch on and the value returned by
355 BasicBlock
* DecisionBB
=
356 BasicBlock::Create(Func
->getContext(), "LJDecisionBB", Func
);
358 BranchInst::Create(DecisionBB
, Rethrow
, Cond
, LongJmpPre
);
360 // Fill in the "decision" basic block.
361 CallInst
* LJVal
= CallInst::Create(GetLJValue
, "LJVal", DecisionBB
);
362 CallInst
* SJNum
= CallInst::Create(TryCatchLJ
, GetSetJmpMap(Func
), "SJNum",
365 SwitchInst
* SI
= SwitchInst::Create(SJNum
, Rethrow
, 0, DecisionBB
);
366 return SwitchValMap
[Func
] = SwitchValuePair(SI
, LJVal
);
369 // TransformSetJmpCall - The setjmp call is a bit trickier to transform.
370 // We're going to convert all setjmp calls to nops. Then all "call" and
371 // "invoke" instructions in the function are converted to "invoke" where
372 // the "except" branch is used when returning from a longjmp call.
373 void LowerSetJmp::TransformSetJmpCall(CallInst
* Inst
)
375 BasicBlock
* ABlock
= Inst
->getParent();
376 Function
* Func
= ABlock
->getParent();
378 // Add this setjmp to the setjmp map.
380 Type::getInt8PtrTy(Inst
->getContext());
382 new BitCastInst(Inst
->getArgOperand(0), SBPTy
, "SBJmpBuf", Inst
);
384 GetSetJmpMap(Func
), BufPtr
,
385 ConstantInt::get(Type::getInt32Ty(Inst
->getContext()), SetJmpIDMap
[Func
]++)
387 CallInst::Create(AddSJToMap
, Args
, Args
+ 3, "", Inst
);
389 // We are guaranteed that there are no values live across basic blocks
390 // (because we are "not in SSA form" yet), but there can still be values live
391 // in basic blocks. Because of this, splitting the setjmp block can cause
392 // values above the setjmp to not dominate uses which are after the setjmp
393 // call. For all of these occasions, we must spill the value to the stack.
395 std::set
<Instruction
*> InstrsAfterCall
;
397 // The call is probably very close to the end of the basic block, for the
398 // common usage pattern of: 'if (setjmp(...))', so keep track of the
399 // instructions after the call.
400 for (BasicBlock::iterator I
= ++BasicBlock::iterator(Inst
), E
= ABlock
->end();
402 InstrsAfterCall
.insert(I
);
404 for (BasicBlock::iterator II
= ABlock
->begin();
405 II
!= BasicBlock::iterator(Inst
); ++II
)
406 // Loop over all of the uses of instruction. If any of them are after the
407 // call, "spill" the value to the stack.
408 for (Value::use_iterator UI
= II
->use_begin(), E
= II
->use_end();
411 if (cast
<Instruction
>(U
)->getParent() != ABlock
||
412 InstrsAfterCall
.count(cast
<Instruction
>(U
))) {
413 DemoteRegToStack(*II
);
417 InstrsAfterCall
.clear();
419 // Change the setjmp call into a branch statement. We'll remove the
420 // setjmp call in a little bit. No worries.
421 BasicBlock
* SetJmpContBlock
= ABlock
->splitBasicBlock(Inst
);
422 assert(SetJmpContBlock
&& "Couldn't split setjmp BB!!");
424 SetJmpContBlock
->setName(ABlock
->getName()+"SetJmpCont");
426 // Add the SetJmpContBlock to the set of blocks reachable from a setjmp.
427 DFSBlocks
.insert(SetJmpContBlock
);
429 // This PHI node will be in the new block created from the
430 // splitBasicBlock call.
431 PHINode
* PHI
= PHINode::Create(Type::getInt32Ty(Inst
->getContext()),
432 "SetJmpReturn", Inst
);
434 // Coming from a call to setjmp, the return is 0.
435 PHI
->addIncoming(Constant::getNullValue(Type::getInt32Ty(Inst
->getContext())),
438 // Add the case for this setjmp's number...
439 SwitchValuePair SVP
= GetSJSwitch(Func
, GetRethrowBB(Func
));
440 SVP
.first
->addCase(ConstantInt::get(Type::getInt32Ty(Inst
->getContext()),
441 SetJmpIDMap
[Func
] - 1),
444 // Value coming from the handling of the exception.
445 PHI
->addIncoming(SVP
.second
, SVP
.second
->getParent());
447 // Replace all uses of this instruction with the PHI node created by
448 // the eradication of setjmp.
449 Inst
->replaceAllUsesWith(PHI
);
450 Inst
->eraseFromParent();
452 ++SetJmpsTransformed
;
455 // visitCallInst - This converts all LLVM call instructions into invoke
456 // instructions. The except part of the invoke goes to the "LongJmpBlkPre"
457 // that grabs the exception and proceeds to determine if it's a longjmp
459 void LowerSetJmp::visitCallInst(CallInst
& CI
)
461 if (CI
.getCalledFunction())
462 if (!IsTransformableFunction(CI
.getCalledFunction()->getName()) ||
463 CI
.getCalledFunction()->isIntrinsic()) return;
465 BasicBlock
* OldBB
= CI
.getParent();
467 // If not reachable from a setjmp call, don't transform.
468 if (!DFSBlocks
.count(OldBB
)) return;
470 BasicBlock
* NewBB
= OldBB
->splitBasicBlock(CI
);
471 assert(NewBB
&& "Couldn't split BB of \"call\" instruction!!");
472 DFSBlocks
.insert(NewBB
);
473 NewBB
->setName("Call2Invoke");
475 Function
* Func
= OldBB
->getParent();
477 // Construct the new "invoke" instruction.
478 TerminatorInst
* Term
= OldBB
->getTerminator();
480 std::vector
<Value
*> Params(CS
.arg_begin(), CS
.arg_end());
482 InvokeInst::Create(CI
.getCalledValue(), NewBB
, PrelimBBMap
[Func
],
483 Params
.begin(), Params
.end(), CI
.getName(), Term
);
484 II
->setCallingConv(CI
.getCallingConv());
485 II
->setAttributes(CI
.getAttributes());
487 // Replace the old call inst with the invoke inst and remove the call.
488 CI
.replaceAllUsesWith(II
);
489 CI
.eraseFromParent();
491 // The old terminator is useless now that we have the invoke inst.
492 Term
->eraseFromParent();
496 // visitInvokeInst - Converting the "invoke" instruction is fairly
497 // straight-forward. The old exception part is replaced by a query asking
498 // if this is a longjmp exception. If it is, then it goes to the longjmp
499 // exception blocks. Otherwise, control is passed the old exception.
500 void LowerSetJmp::visitInvokeInst(InvokeInst
& II
)
502 if (II
.getCalledFunction())
503 if (!IsTransformableFunction(II
.getCalledFunction()->getName()) ||
504 II
.getCalledFunction()->isIntrinsic()) return;
506 BasicBlock
* BB
= II
.getParent();
508 // If not reachable from a setjmp call, don't transform.
509 if (!DFSBlocks
.count(BB
)) return;
511 BasicBlock
* ExceptBB
= II
.getUnwindDest();
513 Function
* Func
= BB
->getParent();
514 BasicBlock
* NewExceptBB
= BasicBlock::Create(II
.getContext(),
515 "InvokeExcept", Func
);
517 // If this is a longjmp exception, then branch to the preliminary BB of
518 // the longjmp exception handling. Otherwise, go to the old exception.
519 CallInst
* IsLJExcept
= CallInst::Create(IsLJException
, "IsLJExcept",
522 BranchInst::Create(PrelimBBMap
[Func
], ExceptBB
, IsLJExcept
, NewExceptBB
);
524 II
.setUnwindDest(NewExceptBB
);
525 ++InvokesTransformed
;
528 // visitReturnInst - We want to destroy the setjmp map upon exit from the
530 void LowerSetJmp::visitReturnInst(ReturnInst
&RI
) {
531 Function
* Func
= RI
.getParent()->getParent();
532 CallInst::Create(DestroySJMap
, GetSetJmpMap(Func
), "", &RI
);
535 // visitUnwindInst - We want to destroy the setjmp map upon exit from the
537 void LowerSetJmp::visitUnwindInst(UnwindInst
&UI
) {
538 Function
* Func
= UI
.getParent()->getParent();
539 CallInst::Create(DestroySJMap
, GetSetJmpMap(Func
), "", &UI
);
542 ModulePass
*llvm::createLowerSetJmpPass() {
543 return new LowerSetJmp();