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/CFG.h"
46 #include "llvm/Support/InstVisitor.h"
47 #include "llvm/Transforms/Utils/Local.h"
48 #include "llvm/ADT/DepthFirstIterator.h"
49 #include "llvm/ADT/Statistic.h"
50 #include "llvm/ADT/StringExtras.h"
51 #include "llvm/ADT/VectorExtras.h"
52 #include "llvm/ADT/SmallVector.h"
56 STATISTIC(LongJmpsTransformed
, "Number of longjmps transformed");
57 STATISTIC(SetJmpsTransformed
, "Number of setjmps transformed");
58 STATISTIC(CallsTransformed
, "Number of calls invokified");
59 STATISTIC(InvokesTransformed
, "Number of invokes modified");
62 //===--------------------------------------------------------------------===//
63 // LowerSetJmp pass implementation.
64 class LowerSetJmp
: public ModulePass
, public InstVisitor
<LowerSetJmp
> {
65 // LLVM library functions...
66 Constant
*InitSJMap
; // __llvm_sjljeh_init_setjmpmap
67 Constant
*DestroySJMap
; // __llvm_sjljeh_destroy_setjmpmap
68 Constant
*AddSJToMap
; // __llvm_sjljeh_add_setjmp_to_map
69 Constant
*ThrowLongJmp
; // __llvm_sjljeh_throw_longjmp
70 Constant
*TryCatchLJ
; // __llvm_sjljeh_try_catching_longjmp_exception
71 Constant
*IsLJException
; // __llvm_sjljeh_is_longjmp_exception
72 Constant
*GetLJValue
; // __llvm_sjljeh_get_longjmp_value
74 typedef std::pair
<SwitchInst
*, CallInst
*> SwitchValuePair
;
76 // Keep track of those basic blocks reachable via a depth-first search of
77 // the CFG from a setjmp call. We only need to transform those "call" and
78 // "invoke" instructions that are reachable from the setjmp call site.
79 std::set
<BasicBlock
*> DFSBlocks
;
81 // The setjmp map is going to hold information about which setjmps
82 // were called (each setjmp gets its own number) and with which
83 // buffer it was called.
84 std::map
<Function
*, AllocaInst
*> SJMap
;
86 // The rethrow basic block map holds the basic block to branch to if
87 // the exception isn't handled in the current function and needs to
89 std::map
<const Function
*, BasicBlock
*> RethrowBBMap
;
91 // The preliminary basic block map holds a basic block that grabs the
92 // exception and determines if it's handled by the current function.
93 std::map
<const Function
*, BasicBlock
*> PrelimBBMap
;
95 // The switch/value map holds a switch inst/call inst pair. The
96 // switch inst controls which handler (if any) gets called and the
97 // value is the value returned to that handler by the call to
98 // __llvm_sjljeh_get_longjmp_value.
99 std::map
<const Function
*, SwitchValuePair
> SwitchValMap
;
101 // A map of which setjmps we've seen so far in a function.
102 std::map
<const Function
*, unsigned> SetJmpIDMap
;
104 AllocaInst
* GetSetJmpMap(Function
* Func
);
105 BasicBlock
* GetRethrowBB(Function
* Func
);
106 SwitchValuePair
GetSJSwitch(Function
* Func
, BasicBlock
* Rethrow
);
108 void TransformLongJmpCall(CallInst
* Inst
);
109 void TransformSetJmpCall(CallInst
* Inst
);
111 bool IsTransformableFunction(const std::string
& Name
);
113 static char ID
; // Pass identification, replacement for typeid
114 LowerSetJmp() : ModulePass(&ID
) {}
116 void visitCallInst(CallInst
& CI
);
117 void visitInvokeInst(InvokeInst
& II
);
118 void visitReturnInst(ReturnInst
& RI
);
119 void visitUnwindInst(UnwindInst
& UI
);
121 bool runOnModule(Module
& M
);
122 bool doInitialization(Module
& M
);
124 } // end anonymous namespace
126 char LowerSetJmp::ID
= 0;
127 static RegisterPass
<LowerSetJmp
> X("lowersetjmp", "Lower Set Jump");
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::runOnModule(Module
& M
) {
133 bool Changed
= false;
135 // These are what the functions are called.
136 Function
* SetJmp
= M
.getFunction("llvm.setjmp");
137 Function
* LongJmp
= M
.getFunction("llvm.longjmp");
139 // This program doesn't have longjmp and setjmp calls.
140 if ((!LongJmp
|| LongJmp
->use_empty()) &&
141 (!SetJmp
|| SetJmp
->use_empty())) return false;
143 // Initialize some values and functions we'll need to transform the
144 // setjmp/longjmp functions.
148 for (Value::use_iterator B
= SetJmp
->use_begin(), E
= SetJmp
->use_end();
150 BasicBlock
* BB
= cast
<Instruction
>(*B
)->getParent();
151 for (df_ext_iterator
<BasicBlock
*> I
= df_ext_begin(BB
, DFSBlocks
),
152 E
= df_ext_end(BB
, DFSBlocks
); I
!= E
; ++I
)
156 while (!SetJmp
->use_empty()) {
157 assert(isa
<CallInst
>(SetJmp
->use_back()) &&
158 "User of setjmp intrinsic not a call?");
159 TransformSetJmpCall(cast
<CallInst
>(SetJmp
->use_back()));
165 while (!LongJmp
->use_empty()) {
166 assert(isa
<CallInst
>(LongJmp
->use_back()) &&
167 "User of longjmp intrinsic not a call?");
168 TransformLongJmpCall(cast
<CallInst
>(LongJmp
->use_back()));
172 // Now go through the affected functions and convert calls and invokes
174 for (std::map
<Function
*, AllocaInst
*>::iterator
175 B
= SJMap
.begin(), E
= SJMap
.end(); B
!= E
; ++B
) {
176 Function
* F
= B
->first
;
177 for (Function::iterator BB
= F
->begin(), BE
= F
->end(); BB
!= BE
; ++BB
)
178 for (BasicBlock::iterator IB
= BB
->begin(), IE
= BB
->end(); IB
!= IE
; ) {
180 if (IB
!= BB
->end() && IB
->getParent() != BB
)
181 break; // The next instruction got moved to a different block!
187 RethrowBBMap
.clear();
189 SwitchValMap
.clear();
195 // doInitialization - For the lower long/setjmp pass, this ensures that a
196 // module contains a declaration for the intrisic functions we are going
197 // to call to convert longjmp and setjmp calls.
199 // This function is always successful, unless it isn't.
200 bool LowerSetJmp::doInitialization(Module
& M
)
202 const Type
*SBPTy
= Type::getInt8PtrTy(M
.getContext());
203 const Type
*SBPPTy
= PointerType::getUnqual(SBPTy
);
205 // N.B. See llvm/runtime/GCCLibraries/libexception/SJLJ-Exception.h for
206 // a description of the following library functions.
208 // void __llvm_sjljeh_init_setjmpmap(void**)
209 InitSJMap
= M
.getOrInsertFunction("__llvm_sjljeh_init_setjmpmap",
210 Type::getVoidTy(M
.getContext()),
212 // void __llvm_sjljeh_destroy_setjmpmap(void**)
213 DestroySJMap
= M
.getOrInsertFunction("__llvm_sjljeh_destroy_setjmpmap",
214 Type::getVoidTy(M
.getContext()),
217 // void __llvm_sjljeh_add_setjmp_to_map(void**, void*, unsigned)
218 AddSJToMap
= M
.getOrInsertFunction("__llvm_sjljeh_add_setjmp_to_map",
219 Type::getVoidTy(M
.getContext()),
221 Type::getInt32Ty(M
.getContext()),
224 // void __llvm_sjljeh_throw_longjmp(int*, int)
225 ThrowLongJmp
= M
.getOrInsertFunction("__llvm_sjljeh_throw_longjmp",
226 Type::getVoidTy(M
.getContext()), SBPTy
,
227 Type::getInt32Ty(M
.getContext()),
230 // unsigned __llvm_sjljeh_try_catching_longjmp_exception(void **)
232 M
.getOrInsertFunction("__llvm_sjljeh_try_catching_longjmp_exception",
233 Type::getInt32Ty(M
.getContext()), SBPPTy
, (Type
*)0);
235 // bool __llvm_sjljeh_is_longjmp_exception()
236 IsLJException
= M
.getOrInsertFunction("__llvm_sjljeh_is_longjmp_exception",
237 Type::getInt1Ty(M
.getContext()),
240 // int __llvm_sjljeh_get_longjmp_value()
241 GetLJValue
= M
.getOrInsertFunction("__llvm_sjljeh_get_longjmp_value",
242 Type::getInt32Ty(M
.getContext()),
247 // IsTransformableFunction - Return true if the function name isn't one
248 // of the ones we don't want transformed. Currently, don't transform any
249 // "llvm.{setjmp,longjmp}" functions and none of the setjmp/longjmp error
250 // handling functions (beginning with __llvm_sjljeh_...they don't throw
252 bool LowerSetJmp::IsTransformableFunction(const std::string
& Name
) {
253 std::string
SJLJEh("__llvm_sjljeh");
255 if (Name
.size() > SJLJEh
.size())
256 return std::string(Name
.begin(), Name
.begin() + SJLJEh
.size()) != SJLJEh
;
261 // TransformLongJmpCall - Transform a longjmp call into a call to the
262 // internal __llvm_sjljeh_throw_longjmp function. It then takes care of
263 // throwing the exception for us.
264 void LowerSetJmp::TransformLongJmpCall(CallInst
* Inst
)
267 Type::getInt8PtrTy(Inst
->getContext());
269 // Create the call to "__llvm_sjljeh_throw_longjmp". This takes the
270 // same parameters as "longjmp", except that the buffer is cast to a
271 // char*. It returns "void", so it doesn't need to replace any of
272 // Inst's uses and doesn't get a name.
274 new BitCastInst(Inst
->getOperand(1), SBPTy
, "LJBuf", Inst
);
275 SmallVector
<Value
*, 2> Args
;
277 Args
.push_back(Inst
->getOperand(2));
278 CallInst::Create(ThrowLongJmp
, Args
.begin(), Args
.end(), "", Inst
);
280 SwitchValuePair
& SVP
= SwitchValMap
[Inst
->getParent()->getParent()];
282 // If the function has a setjmp call in it (they are transformed first)
283 // we should branch to the basic block that determines if this longjmp
284 // is applicable here. Otherwise, issue an unwind.
286 BranchInst::Create(SVP
.first
->getParent(), Inst
);
288 new UnwindInst(Inst
->getContext(), Inst
);
290 // Remove all insts after the branch/unwind inst. Go from back to front to
291 // avoid replaceAllUsesWith if possible.
292 BasicBlock
*BB
= Inst
->getParent();
293 Instruction
*Removed
;
295 Removed
= &BB
->back();
296 // If the removed instructions have any users, replace them now.
297 if (!Removed
->use_empty())
298 Removed
->replaceAllUsesWith(UndefValue::get(Removed
->getType()));
299 Removed
->eraseFromParent();
300 } while (Removed
!= Inst
);
302 ++LongJmpsTransformed
;
305 // GetSetJmpMap - Retrieve (create and initialize, if necessary) the
306 // setjmp map. This map is going to hold information about which setjmps
307 // were called (each setjmp gets its own number) and with which buffer it
308 // was called. There can be only one!
309 AllocaInst
* LowerSetJmp::GetSetJmpMap(Function
* Func
)
311 if (SJMap
[Func
]) return SJMap
[Func
];
313 // Insert the setjmp map initialization before the first instruction in
315 Instruction
* Inst
= Func
->getEntryBlock().begin();
316 assert(Inst
&& "Couldn't find even ONE instruction in entry block!");
318 // Fill in the alloca and call to initialize the SJ map.
320 Type::getInt8PtrTy(Func
->getContext());
321 AllocaInst
* Map
= new AllocaInst(SBPTy
, 0, "SJMap", Inst
);
322 CallInst::Create(InitSJMap
, Map
, "", Inst
);
323 return SJMap
[Func
] = Map
;
326 // GetRethrowBB - Only one rethrow basic block is needed per function.
327 // If this is a longjmp exception but not handled in this block, this BB
328 // performs the rethrow.
329 BasicBlock
* LowerSetJmp::GetRethrowBB(Function
* Func
)
331 if (RethrowBBMap
[Func
]) return RethrowBBMap
[Func
];
333 // The basic block we're going to jump to if we need to rethrow the
335 BasicBlock
* Rethrow
=
336 BasicBlock::Create(Func
->getContext(), "RethrowExcept", Func
);
338 // Fill in the "Rethrow" BB with a call to rethrow the exception. This
339 // is the last instruction in the BB since at this point the runtime
340 // should exit this function and go to the next function.
341 new UnwindInst(Func
->getContext(), Rethrow
);
342 return RethrowBBMap
[Func
] = Rethrow
;
345 // GetSJSwitch - Return the switch statement that controls which handler
346 // (if any) gets called and the value returned to that handler.
347 LowerSetJmp::SwitchValuePair
LowerSetJmp::GetSJSwitch(Function
* Func
,
350 if (SwitchValMap
[Func
].first
) return SwitchValMap
[Func
];
352 BasicBlock
* LongJmpPre
=
353 BasicBlock::Create(Func
->getContext(), "LongJmpBlkPre", Func
);
355 // Keep track of the preliminary basic block for some of the other
357 PrelimBBMap
[Func
] = LongJmpPre
;
359 // Grab the exception.
360 CallInst
* Cond
= CallInst::Create(IsLJException
, "IsLJExcept", LongJmpPre
);
362 // The "decision basic block" gets the number associated with the
363 // setjmp call returning to switch on and the value returned by
365 BasicBlock
* DecisionBB
=
366 BasicBlock::Create(Func
->getContext(), "LJDecisionBB", Func
);
368 BranchInst::Create(DecisionBB
, Rethrow
, Cond
, LongJmpPre
);
370 // Fill in the "decision" basic block.
371 CallInst
* LJVal
= CallInst::Create(GetLJValue
, "LJVal", DecisionBB
);
372 CallInst
* SJNum
= CallInst::Create(TryCatchLJ
, GetSetJmpMap(Func
), "SJNum",
375 SwitchInst
* SI
= SwitchInst::Create(SJNum
, Rethrow
, 0, DecisionBB
);
376 return SwitchValMap
[Func
] = SwitchValuePair(SI
, LJVal
);
379 // TransformSetJmpCall - The setjmp call is a bit trickier to transform.
380 // We're going to convert all setjmp calls to nops. Then all "call" and
381 // "invoke" instructions in the function are converted to "invoke" where
382 // the "except" branch is used when returning from a longjmp call.
383 void LowerSetJmp::TransformSetJmpCall(CallInst
* Inst
)
385 BasicBlock
* ABlock
= Inst
->getParent();
386 Function
* Func
= ABlock
->getParent();
388 // Add this setjmp to the setjmp map.
390 Type::getInt8PtrTy(Inst
->getContext());
392 new BitCastInst(Inst
->getOperand(1), SBPTy
, "SBJmpBuf", Inst
);
393 std::vector
<Value
*> Args
=
394 make_vector
<Value
*>(GetSetJmpMap(Func
), BufPtr
,
395 ConstantInt::get(Type::getInt32Ty(Inst
->getContext()),
396 SetJmpIDMap
[Func
]++), 0);
397 CallInst::Create(AddSJToMap
, Args
.begin(), Args
.end(), "", Inst
);
399 // We are guaranteed that there are no values live across basic blocks
400 // (because we are "not in SSA form" yet), but there can still be values live
401 // in basic blocks. Because of this, splitting the setjmp block can cause
402 // values above the setjmp to not dominate uses which are after the setjmp
403 // call. For all of these occasions, we must spill the value to the stack.
405 std::set
<Instruction
*> InstrsAfterCall
;
407 // The call is probably very close to the end of the basic block, for the
408 // common usage pattern of: 'if (setjmp(...))', so keep track of the
409 // instructions after the call.
410 for (BasicBlock::iterator I
= ++BasicBlock::iterator(Inst
), E
= ABlock
->end();
412 InstrsAfterCall
.insert(I
);
414 for (BasicBlock::iterator II
= ABlock
->begin();
415 II
!= BasicBlock::iterator(Inst
); ++II
)
416 // Loop over all of the uses of instruction. If any of them are after the
417 // call, "spill" the value to the stack.
418 for (Value::use_iterator UI
= II
->use_begin(), E
= II
->use_end();
420 if (cast
<Instruction
>(*UI
)->getParent() != ABlock
||
421 InstrsAfterCall
.count(cast
<Instruction
>(*UI
))) {
422 DemoteRegToStack(*II
);
425 InstrsAfterCall
.clear();
427 // Change the setjmp call into a branch statement. We'll remove the
428 // setjmp call in a little bit. No worries.
429 BasicBlock
* SetJmpContBlock
= ABlock
->splitBasicBlock(Inst
);
430 assert(SetJmpContBlock
&& "Couldn't split setjmp BB!!");
432 SetJmpContBlock
->setName(ABlock
->getName()+"SetJmpCont");
434 // Add the SetJmpContBlock to the set of blocks reachable from a setjmp.
435 DFSBlocks
.insert(SetJmpContBlock
);
437 // This PHI node will be in the new block created from the
438 // splitBasicBlock call.
439 PHINode
* PHI
= PHINode::Create(Type::getInt32Ty(Inst
->getContext()),
440 "SetJmpReturn", Inst
);
442 // Coming from a call to setjmp, the return is 0.
443 PHI
->addIncoming(Constant::getNullValue(Type::getInt32Ty(Inst
->getContext())),
446 // Add the case for this setjmp's number...
447 SwitchValuePair SVP
= GetSJSwitch(Func
, GetRethrowBB(Func
));
448 SVP
.first
->addCase(ConstantInt::get(Type::getInt32Ty(Inst
->getContext()),
449 SetJmpIDMap
[Func
] - 1),
452 // Value coming from the handling of the exception.
453 PHI
->addIncoming(SVP
.second
, SVP
.second
->getParent());
455 // Replace all uses of this instruction with the PHI node created by
456 // the eradication of setjmp.
457 Inst
->replaceAllUsesWith(PHI
);
458 Inst
->eraseFromParent();
460 ++SetJmpsTransformed
;
463 // visitCallInst - This converts all LLVM call instructions into invoke
464 // instructions. The except part of the invoke goes to the "LongJmpBlkPre"
465 // that grabs the exception and proceeds to determine if it's a longjmp
467 void LowerSetJmp::visitCallInst(CallInst
& CI
)
469 if (CI
.getCalledFunction())
470 if (!IsTransformableFunction(CI
.getCalledFunction()->getName()) ||
471 CI
.getCalledFunction()->isIntrinsic()) return;
473 BasicBlock
* OldBB
= CI
.getParent();
475 // If not reachable from a setjmp call, don't transform.
476 if (!DFSBlocks
.count(OldBB
)) return;
478 BasicBlock
* NewBB
= OldBB
->splitBasicBlock(CI
);
479 assert(NewBB
&& "Couldn't split BB of \"call\" instruction!!");
480 DFSBlocks
.insert(NewBB
);
481 NewBB
->setName("Call2Invoke");
483 Function
* Func
= OldBB
->getParent();
485 // Construct the new "invoke" instruction.
486 TerminatorInst
* Term
= OldBB
->getTerminator();
487 std::vector
<Value
*> Params(CI
.op_begin() + 1, CI
.op_end());
489 InvokeInst::Create(CI
.getCalledValue(), NewBB
, PrelimBBMap
[Func
],
490 Params
.begin(), Params
.end(), CI
.getName(), Term
);
491 II
->setCallingConv(CI
.getCallingConv());
492 II
->setAttributes(CI
.getAttributes());
494 // Replace the old call inst with the invoke inst and remove the call.
495 CI
.replaceAllUsesWith(II
);
496 CI
.eraseFromParent();
498 // The old terminator is useless now that we have the invoke inst.
499 Term
->eraseFromParent();
503 // visitInvokeInst - Converting the "invoke" instruction is fairly
504 // straight-forward. The old exception part is replaced by a query asking
505 // if this is a longjmp exception. If it is, then it goes to the longjmp
506 // exception blocks. Otherwise, control is passed the old exception.
507 void LowerSetJmp::visitInvokeInst(InvokeInst
& II
)
509 if (II
.getCalledFunction())
510 if (!IsTransformableFunction(II
.getCalledFunction()->getName()) ||
511 II
.getCalledFunction()->isIntrinsic()) return;
513 BasicBlock
* BB
= II
.getParent();
515 // If not reachable from a setjmp call, don't transform.
516 if (!DFSBlocks
.count(BB
)) return;
518 BasicBlock
* ExceptBB
= II
.getUnwindDest();
520 Function
* Func
= BB
->getParent();
521 BasicBlock
* NewExceptBB
= BasicBlock::Create(II
.getContext(),
522 "InvokeExcept", Func
);
524 // If this is a longjmp exception, then branch to the preliminary BB of
525 // the longjmp exception handling. Otherwise, go to the old exception.
526 CallInst
* IsLJExcept
= CallInst::Create(IsLJException
, "IsLJExcept",
529 BranchInst::Create(PrelimBBMap
[Func
], ExceptBB
, IsLJExcept
, NewExceptBB
);
531 II
.setUnwindDest(NewExceptBB
);
532 ++InvokesTransformed
;
535 // visitReturnInst - We want to destroy the setjmp map upon exit from the
537 void LowerSetJmp::visitReturnInst(ReturnInst
&RI
) {
538 Function
* Func
= RI
.getParent()->getParent();
539 CallInst::Create(DestroySJMap
, GetSetJmpMap(Func
), "", &RI
);
542 // visitUnwindInst - We want to destroy the setjmp map upon exit from the
544 void LowerSetJmp::visitUnwindInst(UnwindInst
&UI
) {
545 Function
* Func
= UI
.getParent()->getParent();
546 CallInst::Create(DestroySJMap
, GetSetJmpMap(Func
), "", &UI
);
549 ModulePass
*llvm::createLowerSetJmpPass() {
550 return new LowerSetJmp();