path: root/lib/Transforms/IPO/LowerSetJmp.cpp

//===- LowerSetJmp.cpp - Code pertaining to lowering set/long jumps -------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file implements the lowering of setjmp and longjmp to use the
//  LLVM invoke and unwind instructions as necessary.
//
//  Lowering of longjmp is fairly trivial. We replace the call with a
//  call to the LLVM library function "__llvm_sjljeh_throw_longjmp()".
//  This unwinds the stack for us calling all of the destructors for
//  objects allocated on the stack.
//
//  At a setjmp call, the basic block is split and the setjmp removed.
//  The calls in a function that have a setjmp are converted to invoke
//  where the except part checks to see if it's a longjmp exception and,
//  if so, if it's handled in the function. If it is, then it gets the
//  value returned by the longjmp and goes to where the basic block was
//  split. Invoke instructions are handled in a similar fashion with the
//  original except block being executed if it isn't a longjmp except
//  that is handled by that function.
//
//===----------------------------------------------------------------------===//

//===----------------------------------------------------------------------===//
// FIXME: This pass doesn't deal with PHI statements just yet. That is,
// we expect this to occur before SSAification is done. This would seem
// to make sense, but in general, it might be a good idea to make this
// pass invokable via the "opt" command at will.
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "lowersetjmp"
#include "llvm/Transforms/IPO.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Intrinsics.h"
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/VectorExtras.h"
#include "llvm/ADT/SmallVector.h"
#include <map>
using namespace llvm;

STATISTIC(LongJmpsTransformed, "Number of longjmps transformed");
STATISTIC(SetJmpsTransformed , "Number of setjmps transformed");
STATISTIC(CallsTransformed   , "Number of calls invokified");
STATISTIC(InvokesTransformed , "Number of invokes modified");

namespace {
  //===--------------------------------------------------------------------===//
  // LowerSetJmp pass implementation.
  class VISIBILITY_HIDDEN LowerSetJmp : public ModulePass,
                      public InstVisitor<LowerSetJmp> {
    // LLVM library functions...
    Constant *InitSJMap;        // __llvm_sjljeh_init_setjmpmap
    Constant *DestroySJMap;     // __llvm_sjljeh_destroy_setjmpmap
    Constant *AddSJToMap;       // __llvm_sjljeh_add_setjmp_to_map
    Constant *ThrowLongJmp;     // __llvm_sjljeh_throw_longjmp
    Constant *TryCatchLJ;       // __llvm_sjljeh_try_catching_longjmp_exception
    Constant *IsLJException;    // __llvm_sjljeh_is_longjmp_exception
    Constant *GetLJValue;       // __llvm_sjljeh_get_longjmp_value

    typedef std::pair<SwitchInst*, CallInst*> SwitchValuePair;

    // Keep track of those basic blocks reachable via a depth-first search of
    // the CFG from a setjmp call. We only need to transform those "call" and
    // "invoke" instructions that are reachable from the setjmp call site.
    std::set<BasicBlock*> DFSBlocks;

    // The setjmp map is going to hold information about which setjmps
    // were called (each setjmp gets its own number) and with which
    // buffer it was called.
    std::map<Function*, AllocaInst*>            SJMap;

    // The rethrow basic block map holds the basic block to branch to if
    // the exception isn't handled in the current function and needs to
    // be rethrown.
    std::map<const Function*, BasicBlock*>      RethrowBBMap;

    // The preliminary basic block map holds a basic block that grabs the
    // exception and determines if it's handled by the current function.
    std::map<const Function*, BasicBlock*>      PrelimBBMap;

    // The switch/value map holds a switch inst/call inst pair. The
    // switch inst controls which handler (if any) gets called and the
    // value is the value returned to that handler by the call to
    // __llvm_sjljeh_get_longjmp_value.
    std::map<const Function*, SwitchValuePair>  SwitchValMap;

    // A map of which setjmps we've seen so far in a function.
    std::map<const Function*, unsigned>         SetJmpIDMap;

    AllocaInst*     GetSetJmpMap(Function* Func);
    BasicBlock*     GetRethrowBB(Function* Func);
    SwitchValuePair GetSJSwitch(Function* Func, BasicBlock* Rethrow);

    void TransformLongJmpCall(CallInst* Inst);
    void TransformSetJmpCall(CallInst* Inst);

    bool IsTransformableFunction(const std::string& Name);
  public:
    static char ID; // Pass identification, replacement for typeid
    LowerSetJmp() : ModulePass(&ID) {}

    void visitCallInst(CallInst& CI);
    void visitInvokeInst(InvokeInst& II);
    void visitReturnInst(ReturnInst& RI);
    void visitUnwindInst(UnwindInst& UI);

    bool runOnModule(Module& M);
    bool doInitialization(Module& M);
  };
} // end anonymous namespace

char LowerSetJmp::ID = 0;
static RegisterPass<LowerSetJmp> X("lowersetjmp", "Lower Set Jump");

// run - Run the transformation on the program. We grab the function
// prototypes for longjmp and setjmp. If they are used in the program,
// then we can go directly to the places they're at and transform them.
bool LowerSetJmp::runOnModule(Module& M) {
  bool Changed = false;

  // These are what the functions are called.
  Function* SetJmp = M.getFunction("llvm.setjmp");
  Function* LongJmp = M.getFunction("llvm.longjmp");

  // This program doesn't have longjmp and setjmp calls.
  if ((!LongJmp || LongJmp->use_empty()) &&
        (!SetJmp || SetJmp->use_empty())) return false;

  // Initialize some values and functions we'll need to transform the
  // setjmp/longjmp functions.
  doInitialization(M);

  if (SetJmp) {
    for (Value::use_iterator B = SetJmp->use_begin(), E = SetJmp->use_end();
         B != E; ++B) {
      BasicBlock* BB = cast<Instruction>(*B)->getParent();
      for (df_ext_iterator<BasicBlock*> I = df_ext_begin(BB, DFSBlocks),
             E = df_ext_end(BB, DFSBlocks); I != E; ++I)
        /* empty */;
    }

    while (!SetJmp->use_empty()) {
      assert(isa<CallInst>(SetJmp->use_back()) &&
             "User of setjmp intrinsic not a call?");
      TransformSetJmpCall(cast<CallInst>(SetJmp->use_back()));
      Changed = true;
    }
  }

  if (LongJmp)
    while (!LongJmp->use_empty()) {
      assert(isa<CallInst>(LongJmp->use_back()) &&
             "User of longjmp intrinsic not a call?");
      TransformLongJmpCall(cast<CallInst>(LongJmp->use_back()));
      Changed = true;
    }

  // Now go through the affected functions and convert calls and invokes
  // to new invokes...
  for (std::map<Function*, AllocaInst*>::iterator
      B = SJMap.begin(), E = SJMap.end(); B != E; ++B) {
    Function* F = B->first;
    for (Function::iterator BB = F->begin(), BE = F->end(); BB != BE; ++BB)
      for (BasicBlock::iterator IB = BB->begin(), IE = BB->end(); IB != IE; ) {
        visit(*IB++);
        if (IB != BB->end() && IB->getParent() != BB)
          break;  // The next instruction got moved to a different block!
      }
  }

  DFSBlocks.clear();
  SJMap.clear();
  RethrowBBMap.clear();
  PrelimBBMap.clear();
  SwitchValMap.clear();
  SetJmpIDMap.clear();

  return Changed;
}

// doInitialization - For the lower long/setjmp pass, this ensures that a
// module contains a declaration for the intrisic functions we are going
// to call to convert longjmp and setjmp calls.
//
// This function is always successful, unless it isn't.
bool LowerSetJmp::doInitialization(Module& M)
{
  const Type *SBPTy = Context->getPointerTypeUnqual(Type::Int8Ty);
  const Type *SBPPTy = Context->getPointerTypeUnqual(SBPTy);

  // N.B. See llvm/runtime/GCCLibraries/libexception/SJLJ-Exception.h for
  // a description of the following library functions.

  // void __llvm_sjljeh_init_setjmpmap(void**)
  InitSJMap = M.getOrInsertFunction("__llvm_sjljeh_init_setjmpmap",
                                    Type::VoidTy, SBPPTy, (Type *)0);
  // void __llvm_sjljeh_destroy_setjmpmap(void**)
  DestroySJMap = M.getOrInsertFunction("__llvm_sjljeh_destroy_setjmpmap",
                                       Type::VoidTy, SBPPTy, (Type *)0);

  // void __llvm_sjljeh_add_setjmp_to_map(void**, void*, unsigned)
  AddSJToMap = M.getOrInsertFunction("__llvm_sjljeh_add_setjmp_to_map",
                                     Type::VoidTy, SBPPTy, SBPTy,
                                     Type