path: root/lib/Transforms/LevelRaise.cpp

//===- LevelRaise.cpp - Code to change LLVM to higher level -----------------=//
//
// This file implements the 'raising' part of the LevelChange API.  This is
// useful because, in general, it makes the LLVM code terser and easier to
// analyze.  Note that it is good to run DCE after doing this transformation.
//
//  Eliminate silly things in the source that do not effect the level, but do
//  clean up the code:
//    * Casts of casts
//    - getelementptr/load & getelementptr/store are folded into a direct
//      load or store
//    - Convert this code (for both alloca and malloc):
//          %reg110 = shl uint %n, ubyte 2          ;;<uint>
//          %reg108 = alloca ubyte, uint %reg110            ;;<ubyte*>
//          %cast76 = cast ubyte* %reg108 to uint*          ;;<uint*>
//      To: %cast76 = alloca uint, uint %n
//   Convert explicit addressing to use getelementptr instruction where possible
//      - ...
//
//   Convert explicit addressing on pointers to use getelementptr instruction.
//    - If a pointer is used by arithmetic operation, insert an array casted
//      version into the source program, only for the following pointer types:
//        * Method argument pointers
//        - Pointers returned by alloca or malloc
//        - Pointers returned by function calls
//    - If a pointer is indexed with a value scaled by a constant size equal
//      to the element size of the array, the expression is replaced with a
//      getelementptr instruction.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/LevelChange.h"
#include "llvm/Method.h"
#include "llvm/Support/STLExtras.h"
#include "llvm/iOther.h"
#include "llvm/iMemory.h"
#include "llvm/ConstPoolVals.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Optimizations/ConstantHandling.h"
#include "llvm/Optimizations/DCE.h"
#include <map>
#include <algorithm>

#include "llvm/Assembly/Writer.h"

//#define DEBUG_PEEPHOLE_INSTS 1

#ifdef DEBUG_PEEPHOLE_INSTS
#define PRINT_PEEPHOLE(ID, NUM, I)            \
  cerr << "Inst P/H " << ID << "[" << NUM << "] " << I;
#else
#define PRINT_PEEPHOLE(ID, NUM, I)
#endif

#define PRINT_PEEPHOLE1(ID, I1) do { PRINT_PEEPHOLE(ID, 0, I1); } while (0)
#define PRINT_PEEPHOLE2(ID, I1, I2) \
  do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); } while (0)
#define PRINT_PEEPHOLE3(ID, I1, I2, I3) \
  do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \
       PRINT_PEEPHOLE(ID, 2, I3); } while (0)


// TargetData Hack: Eventually we will have annotations given to us by the
// backend so that we know stuff about type size and alignments.  For now
// though, just use this, because it happens to match the model that GCC uses.
//
const TargetData TD("LevelRaise: Should be GCC though!");


// losslessCastableTypes - Return true if the types are bitwise equivalent.
// This predicate returns true if it is possible to cast from one type to
// another without gaining or losing precision, or altering the bits in any way.
//
static bool losslessCastableTypes(const Type *T1, const Type *T2) {
  if (!T1->isPrimitiveType() && !isa<PointerType>(T1)) return false;
  if (!T2->isPrimitiveType() && !isa<PointerType>(T2)) return false;

  if (T1->getPrimitiveID() == T2->getPrimitiveID())
    return true;  // Handles identity cast, and cast of differing pointer types

  // Now we know that they are two differing primitive or pointer types
  switch (T1->getPrimitiveID()) {
  case Type::UByteTyID:   return T2 == Type::SByteTy;
  case Type::SByteTyID:   return T2 == Type::UByteTy;
  case Type::UShortTyID:  return T2 == Type::ShortTy;
  case Type::ShortTyID:   return T2 == Type::UShortTy;
  case Type::UIntTyID:    return T2 == Type::IntTy;
  case Type::IntTyID:     return T2 == Type::UIntTy;
  case Type::ULongTyID:
  case Type::LongTyID:
  case Type::PointerTyID:
    return T2 == Type::ULongTy || T2 == Type::LongTy ||
           T2->getPrimitiveID() == Type::PointerTyID;
  default:
    return false;  // Other types have no identity values
  }
}


// isReinterpretingCast - Return true if the cast instruction specified will
// cause the operand to be "reinterpreted".  A value is reinterpreted if the
// cast instruction would cause the underlying bits to change.
//
static inline bool isReinterpretingCast(const CastInst *CI) {
  return !losslessCastableTypes(CI->getOperand(0)->getType(), CI->getType());
}


// getPointedToStruct - If the argument is a pointer type, and the pointed to
// value is a struct type, return the struct type, else return null.
//
static const StructType