path: root/lib/Transforms/ExprTypeConvert.cpp

//===- ExprTypeConvert.cpp - Code to change an LLVM Expr Type ---------------=//
//
// This file implements the part of level raising that checks to see if it is
// possible to coerce an entire expression tree into a different type.  If
// convertable, other routines from this file will do the conversion.
//
//===----------------------------------------------------------------------===//

#include "TransformInternals.h"
#include "llvm/Method.h"
#include "llvm/iOther.h"
#include "llvm/iPHINode.h"
#include "llvm/iMemory.h"
#include "llvm/ConstantVals.h"
#include "llvm/Optimizations/ConstantHandling.h"
#include "llvm/Optimizations/DCE.h"
#include "llvm/Analysis/Expressions.h"
#include "Support/STLExtras.h"
#include <map>
#include <algorithm>

#include "llvm/Assembly/Writer.h"

//#define DEBUG_EXPR_CONVERT 1

static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
                                     ValueTypeCache &ConvertedTypes);

static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
                                 ValueMapCache &VMC);

// AllIndicesZero - Return true if all of the indices of the specified memory
// access instruction are zero, indicating an effectively nil offset to the 
// pointer value.
//
static bool AllIndicesZero(const MemAccessInst *MAI) {
  for (User::const_op_iterator S = MAI->idx_begin(), E = MAI->idx_end();
       S != E; ++S)
    if (!isa<Constant>(*S) || !cast<Constant>(*S)->isNullValue())
      return false;
  return true;
}

static unsigned getBaseTypeSize(const Type *Ty) {
  if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty))
    if (ATy->isUnsized())
      return getBaseTypeSize(ATy->getElementType());
  return TD.getTypeSize(Ty);
}


// Peephole Malloc instructions: we take a look at the use chain of the
// malloc instruction, and try to find out if the following conditions hold:
//   1. The malloc is of the form: 'malloc [sbyte], uint <constant>'
//   2. The only users of the malloc are cast & add instructions
//   3. Of the cast instructions, there is only one destination pointer type
//      [RTy] where the size of the pointed to object is equal to the number
//      of bytes allocated.
//
// If these conditions hold, we convert the malloc to allocate an [RTy]
// element.  TODO: This comment is out of date WRT arrays
//
static bool MallocConvertableToType(MallocInst *MI, const Type *Ty,
                                    ValueTypeCache &CTMap) {
  if (!MI->isArrayAllocation() ||            // No array allocation?
      !isa<PointerType>(Ty)) return false;   // Malloc always returns pointers

  // Deal with the type to allocate, not the pointer type...
  Ty = cast<PointerType>(Ty)->getElementType();

  // Analyze the number of bytes allocated...
  analysis::ExprType Expr = analysis::ClassifyExpression(MI->getArraySize());

  // Must have a scale or offset to analyze it...
  if (!Expr.Offset && !Expr.Scale) return false;

  if (Expr.Offset && (Expr.Scale || Expr.Var)) {
    // This is wierd, shouldn't happen, but if it does, I wanna know about it!
    cerr << "LevelRaise.cpp: Crazy allocation detected!\n";
    return false;    
  }

  // Get the number of bytes allocated...
  int SizeVal = getConstantValue(Expr.Offset ? Expr.Offset : Expr.Scale);
  if (SizeVal <= 0) {
    cerr << "malloc of a negative number???\n";
    return false;
  }
  unsigned Size = (unsigned)SizeVal;
  unsigned ReqTypeSize = getBaseTypeSize(Ty);

  // Does the size of the allocated type match the number of bytes
  // allocated?
  //
  if (ReqTypeSize == Size)
    return true;

  // If not, it's possible that an array of constant size is being allocated.
  // In this case, the Size will be a multiple of the data size.
  //
  if (!Expr.Offset) return false;  // Offset must be set, not scale...

#if 1
  return false;
#else   // THIS CAN ONLY BE RUN VERY LATE, after several passes to make sure
        // things are adequately raised!
  // See if the allocated amount is a multiple of the type size...
  if (Size/ReqTypeSize*ReqTypeSize != Size)
    return false;   // Nope.

  // Unfortunately things tend to be powers of two, so there may be
  // many false hits.  We don't want to optimistically assume that we
  // have the right type on the first try, so scan the use list of the
  // malloc instruction, looking for the cast to the biggest type...
  //
  for (Value::use_iterator I = MI->use_begin(), E = MI->use_end(); I != E; ++I)
    if (CastInst *CI = dyn_cast<CastInst>(*I))
      if (const PointerType *PT