path: root/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp

//===- ReplacePtrsWithInts.cpp - Convert pointer values to integer values--===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass strips out aggregate pointer types and replaces them with
// the integer type iPTR, which is i32 for PNaCl (though this pass
// will allow iPTR to be i64 if the DataLayout specifies 64-bit
// pointers).
//
// The pass converts IR to the following normal form:
//
// All inttoptr and ptrtoint instructions use the same integer size
// (iPTR), so they do not implicitly truncate or zero-extend.
//
// alloca always has the result type i8*.
//
// Pointer types only appear in the following instructions:
//  * loads and stores:  the pointer operand is a NormalizedPtr.
//  * function calls:  the function operand is a NormalizedPtr.
//  * intrinsic calls:  any pointer arguments are NormalizedPtrs.
//  * alloca
//  * bitcast and inttoptr:  only used as part of a NormalizedPtr.
//  * ptrtoint:  the operand is an InherentPtr.
//
// Where an InherentPtr is defined as a pointer value that is:
//  * an alloca;
//  * a GlobalValue (a function or global variable); or
//  * an intrinsic call.
//
// And a NormalizedPtr is defined as a pointer value that is:
//  * an inttoptr instruction;
//  * an InherentPtr; or
//  * a bitcast of an InherentPtr.
//
// This pass currently strips out lifetime markers (that is, calls to
// the llvm.lifetime.start/end intrinsics) and invariant markers
// (calls to llvm.invariant.start/end).
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/NaCl.h"

using namespace llvm;

namespace {
  // This is a ModulePass because the pass must recreate functions in
  // order to change their argument and return types.
  struct ReplacePtrsWithInts : public ModulePass {
    static char ID; // Pass identification, replacement for typeid
    ReplacePtrsWithInts() : ModulePass(ID) {
      initializeReplacePtrsWithIntsPass(*PassRegistry::getPassRegistry());
    }

    virtual bool runOnModule(Module &M);
  };

  // FunctionConverter stores the state for mapping old instructions
  // (of pointer type) to converted instructions (of integer type)
  // within a function, and provides methods for doing the conversion.
  class FunctionConverter {
    // Int type that pointer types are to be replaced with, typically i32.
    Type *IntPtrType;

    struct RewrittenVal {
      RewrittenVal(): Placeholder(NULL), NewIntVal(NULL) {}
      Value *Placeholder;
      Value *NewIntVal;
    };
    // Maps from old values (of pointer type) to converted values (of
    // IntPtrType type).
    DenseMap<Value *, RewrittenVal> RewriteMap;

  public:
    FunctionConverter(Type *IntPtrType) : IntPtrType(IntPtrType) {}

    // Returns the normalized version of the given type, converting
    // pointer types to IntPtrType.
    Type *convertType(Type *Ty);
    // Returns the normalized version of the given function type by
    // normalizing the function's argument types.
    FunctionType *convertFuncType(FunctionType *FTy);

    // Records that 'To' is the normalized version of 'From'.  If 'To'
    // is not of pointer type, no type conversion is required, so this
    // can take the short cut of replacing 'To' with 'From'.
    void recordConverted(Value *From, Value *To);
    void recordConvertedAndErase(Instruction *From, Value *To);

    // Returns Val with no-op casts (those that convert between
    // IntPtrType and pointer types) stripped off.
    Value *stripNoopCasts(Value *Val);

    // Returns the normalized version of the given value.
    //
    // If the conversion of Val has been deferred, this returns a
    // placeholder object, which will later be replaceAllUsesWith'd to
    // the final value.  Since replaceAllUsesWith does not work on
    // references by metadata nodes, this can be bypassed using
    // BypassPlaceholder to get the real converted value, assuming it
    // is available.
    Value *convert(Value *Val, bool BypassPlaceholder = false);
    // Returns the NormalizedPtr form of the given pointer value.
    // Inserts conversion instructions at InsertPt.
    Value *convertBackToPtr(Value *Val, Instruction *InsertPt);
    // Returns the NormalizedPtr form of the given function pointer.
    // Inserts conversion instructions at InsertPt.
    Value *convertFunctionPtr(Value *Callee, Instruction *InsertPt);
    // Converts an instruction without recreating it, by wrapping its
    // operands and result.
    void convertInPlace(Instruction *Inst);

    void eraseReplacedInstructions();

    // List of instructions whose deletion has been deferred.
    SmallVector<Instruction *, 20> ToErase;
  };
}

Type *FunctionConverter::convertType(Type *Ty) {
  if (Ty->isPointerTy())
    return IntPtrType;
  return Ty;
}

FunctionType *FunctionConverter::convertFuncType(FunctionType *FTy) {
  SmallVector<Type *, 8> ArgTypes;
  for (FunctionType::param_iterator ArgTy = FTy->param_begin(),
           E = FTy->param_end(); ArgTy != E; ++ArgTy) {
    ArgTypes.push_back(convertType(*ArgTy));
  }
  return FunctionType::get(convertType(FTy->getReturnType()), ArgTypes,
                           FTy->isVarArg());
}

void FunctionConverter::recordConverted(Value *From, Value *To) {
  if (!From->getType()->isPointerTy()) {
    From->replaceAllUsesWith(To);
    return;
  }
  RewrittenVal *RV = &RewriteMap[From];
  assert(!RV->NewIntVal);
  RV->NewIntVal = To;
}

void FunctionConverter::recordConvertedAndErase(Instruction *From, Value *To) {
  recordConverted(From, To);
  // There may still be references to this value, so defer deleting it.
  ToErase.push_back(From);
}

Value *FunctionConverter::stripNoopCasts(Value *Val) {
  SmallPtrSet<Value *, 4> Visited;
  for (;;) {
    if (!Visited.insert(Val)) {
      // It is possible to get a circular reference in unreachable
      // basic blocks.  Handle this case for completeness.
      return UndefValue::get(Val->getType());
    }
    if (CastInst *Cast = dyn_cast<CastInst>(Val)) {
      Value *Src = Cast->getOperand(0);
      if ((isa<BitCastInst>(Cast) && Cast->getType()->isPointerTy()) ||
          (isa<PtrToIntInst>(Cast) && Cast->getType() == IntPtrType) ||
          (isa<IntToPtrInst>(Cast) && Src->getType() == IntPtrType)) {
        Val = Src;
        continue;
      }
    }
    return Val;
  }
}

Value *FunctionConverter::convert(Value *Val, bool BypassPlaceholder) {
  Val = stripNoopCasts(Val);
  if (!Val->getType()->isPointerTy())
    return Val;
  if (Constant *C = dyn_cast<Constant>(Val))
    return ConstantExpr::getPtrToInt(C, IntPtrType);
  RewrittenVal *RV = &RewriteMap[Val];
  if (BypassPlaceholder) {
    assert(RV->NewIntVal);
    return RV->NewIntVal;
  }
  if (!RV->Placeholder)
    RV->Placeholder = new Argument(convertType(Val->getType()));
  return RV->Placeholder;
}

Value *FunctionConverter::convertBackToPtr(Value *Val, Instruction *InsertPt) {
  Type *NewTy =
    convertType(Val->getType()->getPointerElementType())->getPointerTo();
  return new IntToPtrInst(convert(Val), NewTy, "", InsertPt);
}

Value *FunctionConverter::convertFunctionPtr(Value *Callee,
                                             Instruction *InsertPt) {
  FunctionType *FuncType = cast<FunctionType>(
      Callee->getType()->getPointerElementType());
  return new IntToPtrInst(convert(Callee),
                          convertFuncType(FuncType)->getPointerTo(),
                          "", InsertPt);
}

static bool ShouldLeaveAlone(Value *V) {
  if (Function *F = dyn_cast<Function>(V))
    return F->isIntrinsic();
  if (isa<InlineAsm>(