Fix comment for consistency sake.
[llvm/avr.git] / lib / Transforms / IPO / LowerSetJmp.cpp
blob5dff47aa81e18af7973efc452bff8c5a905fd98a
1 //===- LowerSetJmp.cpp - Code pertaining to lowering set/long jumps -------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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/Compiler.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"
51 #include "llvm/ADT/StringExtras.h"
52 #include "llvm/ADT/VectorExtras.h"
53 #include "llvm/ADT/SmallVector.h"
54 #include <map>
55 using namespace llvm;
57 STATISTIC(LongJmpsTransformed, "Number of longjmps transformed");
58 STATISTIC(SetJmpsTransformed , "Number of setjmps transformed");
59 STATISTIC(CallsTransformed , "Number of calls invokified");
60 STATISTIC(InvokesTransformed , "Number of invokes modified");
62 namespace {
63 //===--------------------------------------------------------------------===//
64 // LowerSetJmp pass implementation.
65 class VISIBILITY_HIDDEN LowerSetJmp : public ModulePass,
66 public InstVisitor<LowerSetJmp> {
67 // LLVM library functions...
68 Constant *InitSJMap; // __llvm_sjljeh_init_setjmpmap
69 Constant *DestroySJMap; // __llvm_sjljeh_destroy_setjmpmap
70 Constant *AddSJToMap; // __llvm_sjljeh_add_setjmp_to_map
71 Constant *ThrowLongJmp; // __llvm_sjljeh_throw_longjmp
72 Constant *TryCatchLJ; // __llvm_sjljeh_try_catching_longjmp_exception
73 Constant *IsLJException; // __llvm_sjljeh_is_longjmp_exception
74 Constant *GetLJValue; // __llvm_sjljeh_get_longjmp_value
76 typedef std::pair<SwitchInst*, CallInst*> SwitchValuePair;
78 // Keep track of those basic blocks reachable via a depth-first search of
79 // the CFG from a setjmp call. We only need to transform those "call" and
80 // "invoke" instructions that are reachable from the setjmp call site.
81 std::set<BasicBlock*> DFSBlocks;
83 // The setjmp map is going to hold information about which setjmps
84 // were called (each setjmp gets its own number) and with which
85 // buffer it was called.
86 std::map<Function*, AllocaInst*> SJMap;
88 // The rethrow basic block map holds the basic block to branch to if
89 // the exception isn't handled in the current function and needs to
90 // be rethrown.
91 std::map<const Function*, BasicBlock*> RethrowBBMap;
93 // The preliminary basic block map holds a basic block that grabs the
94 // exception and determines if it's handled by the current function.
95 std::map<const Function*, BasicBlock*> PrelimBBMap;
97 // The switch/value map holds a switch inst/call inst pair. The
98 // switch inst controls which handler (if any) gets called and the
99 // value is the value returned to that handler by the call to
100 // __llvm_sjljeh_get_longjmp_value.
101 std::map<const Function*, SwitchValuePair> SwitchValMap;
103 // A map of which setjmps we've seen so far in a function.
104 std::map<const Function*, unsigned> SetJmpIDMap;
106 AllocaInst* GetSetJmpMap(Function* Func);
107 BasicBlock* GetRethrowBB(Function* Func);
108 SwitchValuePair GetSJSwitch(Function* Func, BasicBlock* Rethrow);
110 void TransformLongJmpCall(CallInst* Inst);
111 void TransformSetJmpCall(CallInst* Inst);
113 bool IsTransformableFunction(const std::string& Name);
114 public:
115 static char ID; // Pass identification, replacement for typeid
116 LowerSetJmp() : ModulePass(&ID) {}
118 void visitCallInst(CallInst& CI);
119 void visitInvokeInst(InvokeInst& II);
120 void visitReturnInst(ReturnInst& RI);
121 void visitUnwindInst(UnwindInst& UI);
123 bool runOnModule(Module& M);
124 bool doInitialization(Module& M);
126 } // end anonymous namespace
128 char LowerSetJmp::ID = 0;
129 static RegisterPass<LowerSetJmp> X("lowersetjmp", "Lower Set Jump");
131 // run - Run the transformation on the program. We grab the function
132 // prototypes for longjmp and setjmp. If they are used in the program,
133 // then we can go directly to the places they're at and transform them.
134 bool LowerSetJmp::runOnModule(Module& M) {
135 bool Changed = false;
137 // These are what the functions are called.
138 Function* SetJmp = M.getFunction("llvm.setjmp");
139 Function* LongJmp = M.getFunction("llvm.longjmp");
141 // This program doesn't have longjmp and setjmp calls.
142 if ((!LongJmp || LongJmp->use_empty()) &&
143 (!SetJmp || SetJmp->use_empty())) return false;
145 // Initialize some values and functions we'll need to transform the
146 // setjmp/longjmp functions.
147 doInitialization(M);
149 if (SetJmp) {
150 for (Value::use_iterator B = SetJmp->use_begin(), E = SetJmp->use_end();
151 B != E; ++B) {
152 BasicBlock* BB = cast<Instruction>(*B)->getParent();
153 for (df_ext_iterator<BasicBlock*> I = df_ext_begin(BB, DFSBlocks),
154 E = df_ext_end(BB, DFSBlocks); I != E; ++I)
155 /* empty */;
158 while (!SetJmp->use_empty()) {
159 assert(isa<CallInst>(SetJmp->use_back()) &&
160 "User of setjmp intrinsic not a call?");
161 TransformSetJmpCall(cast<CallInst>(SetJmp->use_back()));
162 Changed = true;
166 if (LongJmp)
167 while (!LongJmp->use_empty()) {
168 assert(isa<CallInst>(LongJmp->use_back()) &&
169 "User of longjmp intrinsic not a call?");
170 TransformLongJmpCall(cast<CallInst>(LongJmp->use_back()));
171 Changed = true;
174 // Now go through the affected functions and convert calls and invokes
175 // to new invokes...
176 for (std::map<Function*, AllocaInst*>::iterator
177 B = SJMap.begin(), E = SJMap.end(); B != E; ++B) {
178 Function* F = B->first;
179 for (Function::iterator BB = F->begin(), BE = F->end(); BB != BE; ++BB)
180 for (BasicBlock::iterator IB = BB->begin(), IE = BB->end(); IB != IE; ) {
181 visit(*IB++);
182 if (IB != BB->end() && IB->getParent() != BB)
183 break; // The next instruction got moved to a different block!
187 DFSBlocks.clear();
188 SJMap.clear();
189 RethrowBBMap.clear();
190 PrelimBBMap.clear();
191 SwitchValMap.clear();
192 SetJmpIDMap.clear();
194 return Changed;
197 // doInitialization - For the lower long/setjmp pass, this ensures that a
198 // module contains a declaration for the intrisic functions we are going
199 // to call to convert longjmp and setjmp calls.
201 // This function is always successful, unless it isn't.
202 bool LowerSetJmp::doInitialization(Module& M)
204 const Type *SBPTy = PointerType::getUnqual(Type::getInt8Ty(M.getContext()));
205 const Type *SBPPTy = PointerType::getUnqual(SBPTy);
207 // N.B. See llvm/runtime/GCCLibraries/libexception/SJLJ-Exception.h for
208 // a description of the following library functions.
210 // void __llvm_sjljeh_init_setjmpmap(void**)
211 InitSJMap = M.getOrInsertFunction("__llvm_sjljeh_init_setjmpmap",
212 Type::getVoidTy(M.getContext()),
213 SBPPTy, (Type *)0);
214 // void __llvm_sjljeh_destroy_setjmpmap(void**)
215 DestroySJMap = M.getOrInsertFunction("__llvm_sjljeh_destroy_setjmpmap",
216 Type::getVoidTy(M.getContext()),
217 SBPPTy, (Type *)0);
219 // void __llvm_sjljeh_add_setjmp_to_map(void**, void*, unsigned)
220 AddSJToMap = M.getOrInsertFunction("__llvm_sjljeh_add_setjmp_to_map",
221 Type::getVoidTy(M.getContext()),
222 SBPPTy, SBPTy,
223 Type::getInt32Ty(M.getContext()),
224 (Type *)0);
226 // void __llvm_sjljeh_throw_longjmp(int*, int)
227 ThrowLongJmp = M.getOrInsertFunction("__llvm_sjljeh_throw_longjmp",
228 Type::getVoidTy(M.getContext()), SBPTy,
229 Type::getInt32Ty(M.getContext()),
230 (Type *)0);
232 // unsigned __llvm_sjljeh_try_catching_longjmp_exception(void **)
233 TryCatchLJ =
234 M.getOrInsertFunction("__llvm_sjljeh_try_catching_longjmp_exception",
235 Type::getInt32Ty(M.getContext()), SBPPTy, (Type *)0);
237 // bool __llvm_sjljeh_is_longjmp_exception()
238 IsLJException = M.getOrInsertFunction("__llvm_sjljeh_is_longjmp_exception",
239 Type::getInt1Ty(M.getContext()),
240 (Type *)0);
242 // int __llvm_sjljeh_get_longjmp_value()
243 GetLJValue = M.getOrInsertFunction("__llvm_sjljeh_get_longjmp_value",
244 Type::getInt32Ty(M.getContext()),
245 (Type *)0);
246 return true;
249 // IsTransformableFunction - Return true if the function name isn't one
250 // of the ones we don't want transformed. Currently, don't transform any
251 // "llvm.{setjmp,longjmp}" functions and none of the setjmp/longjmp error
252 // handling functions (beginning with __llvm_sjljeh_...they don't throw
253 // exceptions).
254 bool LowerSetJmp::IsTransformableFunction(const std::string& Name) {
255 std::string SJLJEh("__llvm_sjljeh");
257 if (Name.size() > SJLJEh.size())
258 return std::string(Name.begin(), Name.begin() + SJLJEh.size()) != SJLJEh;
260 return true;
263 // TransformLongJmpCall - Transform a longjmp call into a call to the
264 // internal __llvm_sjljeh_throw_longjmp function. It then takes care of
265 // throwing the exception for us.
266 void LowerSetJmp::TransformLongJmpCall(CallInst* Inst)
268 const Type* SBPTy =
269 PointerType::getUnqual(Type::getInt8Ty(Inst->getContext()));
271 // Create the call to "__llvm_sjljeh_throw_longjmp". This takes the
272 // same parameters as "longjmp", except that the buffer is cast to a
273 // char*. It returns "void", so it doesn't need to replace any of
274 // Inst's uses and doesn't get a name.
275 CastInst* CI =
276 new BitCastInst(Inst->getOperand(1), SBPTy, "LJBuf", Inst);
277 SmallVector<Value *, 2> Args;
278 Args.push_back(CI);
279 Args.push_back(Inst->getOperand(2));
280 CallInst::Create(ThrowLongJmp, Args.begin(), Args.end(), "", Inst);
282 SwitchValuePair& SVP = SwitchValMap[Inst->getParent()->getParent()];
284 // If the function has a setjmp call in it (they are transformed first)
285 // we should branch to the basic block that determines if this longjmp
286 // is applicable here. Otherwise, issue an unwind.
287 if (SVP.first)
288 BranchInst::Create(SVP.first->getParent(), Inst);
289 else
290 new UnwindInst(Inst->getContext(), Inst);
292 // Remove all insts after the branch/unwind inst. Go from back to front to
293 // avoid replaceAllUsesWith if possible.
294 BasicBlock *BB = Inst->getParent();
295 Instruction *Removed;
296 do {
297 Removed = &BB->back();
298 // If the removed instructions have any users, replace them now.
299 if (!Removed->use_empty())
300 Removed->replaceAllUsesWith(UndefValue::get(Removed->getType()));
301 Removed->eraseFromParent();
302 } while (Removed != Inst);
304 ++LongJmpsTransformed;
307 // GetSetJmpMap - Retrieve (create and initialize, if necessary) the
308 // setjmp map. This map is going to hold information about which setjmps
309 // were called (each setjmp gets its own number) and with which buffer it
310 // was called. There can be only one!
311 AllocaInst* LowerSetJmp::GetSetJmpMap(Function* Func)
313 if (SJMap[Func]) return SJMap[Func];
315 // Insert the setjmp map initialization before the first instruction in
316 // the function.
317 Instruction* Inst = Func->getEntryBlock().begin();
318 assert(Inst && "Couldn't find even ONE instruction in entry block!");
320 // Fill in the alloca and call to initialize the SJ map.
321 const Type *SBPTy =
322 PointerType::getUnqual(Type::getInt8Ty(Func->getContext()));
323 AllocaInst* Map = new AllocaInst(SBPTy, 0, "SJMap", Inst);
324 CallInst::Create(InitSJMap, Map, "", Inst);
325 return SJMap[Func] = Map;
328 // GetRethrowBB - Only one rethrow basic block is needed per function.
329 // If this is a longjmp exception but not handled in this block, this BB
330 // performs the rethrow.
331 BasicBlock* LowerSetJmp::GetRethrowBB(Function* Func)
333 if (RethrowBBMap[Func]) return RethrowBBMap[Func];
335 // The basic block we're going to jump to if we need to rethrow the
336 // exception.
337 BasicBlock* Rethrow =
338 BasicBlock::Create(Func->getContext(), "RethrowExcept", Func);
340 // Fill in the "Rethrow" BB with a call to rethrow the exception. This
341 // is the last instruction in the BB since at this point the runtime
342 // should exit this function and go to the next function.
343 new UnwindInst(Func->getContext(), Rethrow);
344 return RethrowBBMap[Func] = Rethrow;
347 // GetSJSwitch - Return the switch statement that controls which handler
348 // (if any) gets called and the value returned to that handler.
349 LowerSetJmp::SwitchValuePair LowerSetJmp::GetSJSwitch(Function* Func,
350 BasicBlock* Rethrow)
352 if (SwitchValMap[Func].first) return SwitchValMap[Func];
354 BasicBlock* LongJmpPre =
355 BasicBlock::Create(Func->getContext(), "LongJmpBlkPre", Func);
357 // Keep track of the preliminary basic block for some of the other
358 // transformations.
359 PrelimBBMap[Func] = LongJmpPre;
361 // Grab the exception.
362 CallInst* Cond = CallInst::Create(IsLJException, "IsLJExcept", LongJmpPre);
364 // The "decision basic block" gets the number associated with the
365 // setjmp call returning to switch on and the value returned by
366 // longjmp.
367 BasicBlock* DecisionBB =
368 BasicBlock::Create(Func->getContext(), "LJDecisionBB", Func);
370 BranchInst::Create(DecisionBB, Rethrow, Cond, LongJmpPre);
372 // Fill in the "decision" basic block.
373 CallInst* LJVal = CallInst::Create(GetLJValue, "LJVal", DecisionBB);
374 CallInst* SJNum = CallInst::Create(TryCatchLJ, GetSetJmpMap(Func), "SJNum",
375 DecisionBB);
377 SwitchInst* SI = SwitchInst::Create(SJNum, Rethrow, 0, DecisionBB);
378 return SwitchValMap[Func] = SwitchValuePair(SI, LJVal);
381 // TransformSetJmpCall - The setjmp call is a bit trickier to transform.
382 // We're going to convert all setjmp calls to nops. Then all "call" and
383 // "invoke" instructions in the function are converted to "invoke" where
384 // the "except" branch is used when returning from a longjmp call.
385 void LowerSetJmp::TransformSetJmpCall(CallInst* Inst)
387 BasicBlock* ABlock = Inst->getParent();
388 Function* Func = ABlock->getParent();
390 // Add this setjmp to the setjmp map.
391 const Type* SBPTy =
392 PointerType::getUnqual(Type::getInt8Ty(Inst->getContext()));
393 CastInst* BufPtr =
394 new BitCastInst(Inst->getOperand(1), SBPTy, "SBJmpBuf", Inst);
395 std::vector<Value*> Args =
396 make_vector<Value*>(GetSetJmpMap(Func), BufPtr,
397 ConstantInt::get(Type::getInt32Ty(Inst->getContext()),
398 SetJmpIDMap[Func]++), 0);
399 CallInst::Create(AddSJToMap, Args.begin(), Args.end(), "", Inst);
401 // We are guaranteed that there are no values live across basic blocks
402 // (because we are "not in SSA form" yet), but there can still be values live
403 // in basic blocks. Because of this, splitting the setjmp block can cause
404 // values above the setjmp to not dominate uses which are after the setjmp
405 // call. For all of these occasions, we must spill the value to the stack.
407 std::set<Instruction*> InstrsAfterCall;
409 // The call is probably very close to the end of the basic block, for the
410 // common usage pattern of: 'if (setjmp(...))', so keep track of the
411 // instructions after the call.
412 for (BasicBlock::iterator I = ++BasicBlock::iterator(Inst), E = ABlock->end();
413 I != E; ++I)
414 InstrsAfterCall.insert(I);
416 for (BasicBlock::iterator II = ABlock->begin();
417 II != BasicBlock::iterator(Inst); ++II)
418 // Loop over all of the uses of instruction. If any of them are after the
419 // call, "spill" the value to the stack.
420 for (Value::use_iterator UI = II->use_begin(), E = II->use_end();
421 UI != E; ++UI)
422 if (cast<Instruction>(*UI)->getParent() != ABlock ||
423 InstrsAfterCall.count(cast<Instruction>(*UI))) {
424 DemoteRegToStack(*II);
425 break;
427 InstrsAfterCall.clear();
429 // Change the setjmp call into a branch statement. We'll remove the
430 // setjmp call in a little bit. No worries.
431 BasicBlock* SetJmpContBlock = ABlock->splitBasicBlock(Inst);
432 assert(SetJmpContBlock && "Couldn't split setjmp BB!!");
434 SetJmpContBlock->setName(ABlock->getName()+"SetJmpCont");
436 // Add the SetJmpContBlock to the set of blocks reachable from a setjmp.
437 DFSBlocks.insert(SetJmpContBlock);
439 // This PHI node will be in the new block created from the
440 // splitBasicBlock call.
441 PHINode* PHI = PHINode::Create(Type::getInt32Ty(Inst->getContext()),
442 "SetJmpReturn", Inst);
444 // Coming from a call to setjmp, the return is 0.
445 PHI->addIncoming(Constant::getNullValue(Type::getInt32Ty(Inst->getContext())),
446 ABlock);
448 // Add the case for this setjmp's number...
449 SwitchValuePair SVP = GetSJSwitch(Func, GetRethrowBB(Func));
450 SVP.first->addCase(ConstantInt::get(Type::getInt32Ty(Inst->getContext()),
451 SetJmpIDMap[Func] - 1),
452 SetJmpContBlock);
454 // Value coming from the handling of the exception.
455 PHI->addIncoming(SVP.second, SVP.second->getParent());
457 // Replace all uses of this instruction with the PHI node created by
458 // the eradication of setjmp.
459 Inst->replaceAllUsesWith(PHI);
460 Inst->eraseFromParent();
462 ++SetJmpsTransformed;
465 // visitCallInst - This converts all LLVM call instructions into invoke
466 // instructions. The except part of the invoke goes to the "LongJmpBlkPre"
467 // that grabs the exception and proceeds to determine if it's a longjmp
468 // exception or not.
469 void LowerSetJmp::visitCallInst(CallInst& CI)
471 if (CI.getCalledFunction())
472 if (!IsTransformableFunction(CI.getCalledFunction()->getName()) ||
473 CI.getCalledFunction()->isIntrinsic()) return;
475 BasicBlock* OldBB = CI.getParent();
477 // If not reachable from a setjmp call, don't transform.
478 if (!DFSBlocks.count(OldBB)) return;
480 BasicBlock* NewBB = OldBB->splitBasicBlock(CI);
481 assert(NewBB && "Couldn't split BB of \"call\" instruction!!");
482 DFSBlocks.insert(NewBB);
483 NewBB->setName("Call2Invoke");
485 Function* Func = OldBB->getParent();
487 // Construct the new "invoke" instruction.
488 TerminatorInst* Term = OldBB->getTerminator();
489 std::vector<Value*> Params(CI.op_begin() + 1, CI.op_end());
490 InvokeInst* II =
491 InvokeInst::Create(CI.getCalledValue(), NewBB, PrelimBBMap[Func],
492 Params.begin(), Params.end(), CI.getName(), Term);
493 II->setCallingConv(CI.getCallingConv());
494 II->setAttributes(CI.getAttributes());
496 // Replace the old call inst with the invoke inst and remove the call.
497 CI.replaceAllUsesWith(II);
498 CI.eraseFromParent();
500 // The old terminator is useless now that we have the invoke inst.
501 Term->eraseFromParent();
502 ++CallsTransformed;
505 // visitInvokeInst - Converting the "invoke" instruction is fairly
506 // straight-forward. The old exception part is replaced by a query asking
507 // if this is a longjmp exception. If it is, then it goes to the longjmp
508 // exception blocks. Otherwise, control is passed the old exception.
509 void LowerSetJmp::visitInvokeInst(InvokeInst& II)
511 if (II.getCalledFunction())
512 if (!IsTransformableFunction(II.getCalledFunction()->getName()) ||
513 II.getCalledFunction()->isIntrinsic()) return;
515 BasicBlock* BB = II.getParent();
517 // If not reachable from a setjmp call, don't transform.
518 if (!DFSBlocks.count(BB)) return;
520 BasicBlock* ExceptBB = II.getUnwindDest();
522 Function* Func = BB->getParent();
523 BasicBlock* NewExceptBB = BasicBlock::Create(II.getContext(),
524 "InvokeExcept", Func);
526 // If this is a longjmp exception, then branch to the preliminary BB of
527 // the longjmp exception handling. Otherwise, go to the old exception.
528 CallInst* IsLJExcept = CallInst::Create(IsLJException, "IsLJExcept",
529 NewExceptBB);
531 BranchInst::Create(PrelimBBMap[Func], ExceptBB, IsLJExcept, NewExceptBB);
533 II.setUnwindDest(NewExceptBB);
534 ++InvokesTransformed;
537 // visitReturnInst - We want to destroy the setjmp map upon exit from the
538 // function.
539 void LowerSetJmp::visitReturnInst(ReturnInst &RI) {
540 Function* Func = RI.getParent()->getParent();
541 CallInst::Create(DestroySJMap, GetSetJmpMap(Func), "", &RI);
544 // visitUnwindInst - We want to destroy the setjmp map upon exit from the
545 // function.
546 void LowerSetJmp::visitUnwindInst(UnwindInst &UI) {
547 Function* Func = UI.getParent()->getParent();
548 CallInst::Create(DestroySJMap, GetSetJmpMap(Func), "", &UI);
551 ModulePass *llvm::createLowerSetJmpPass() {
552 return new LowerSetJmp();