+using std::cerr;
+
+static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
+ ValueTypeCache &ConvertedTypes);
+
+static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
+ ValueMapCache &VMC);
+
+// 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 (!isa<PointerType>(Ty)) return false; // Malloc always returns pointers
+
+ // Deal with the type to allocate, not the pointer type...
+ Ty = cast<PointerType>(Ty)->getElementType();
+ if (!Ty->isSized()) return false; // Can only alloc something with a size
+
+ // Analyze the number of bytes allocated...
+ ExprType Expr = ClassifyExpression(MI->getArraySize());
+
+ // Get information about the base datatype being allocated, before & after
+ int ReqTypeSize = TD.getTypeSize(Ty);
+ unsigned OldTypeSize = TD.getTypeSize(MI->getType()->getElementType());
+
+ // Must have a scale or offset to analyze it...
+ if (!Expr.Offset && !Expr.Scale && OldTypeSize == 1) return false;
+
+ // Get the offset and scale of the allocation...
+ int64_t OffsetVal = Expr.Offset ? getConstantValue(Expr.Offset) : 0;
+ int64_t ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) :(Expr.Var != 0);
+
+ // The old type might not be of unit size, take old size into consideration
+ // here...
+ int64_t Offset = OffsetVal * OldTypeSize;
+ int64_t Scale = ScaleVal * OldTypeSize;
+
+ // In order to be successful, both the scale and the offset must be a multiple
+ // of the requested data type's size.
+ //
+ if (Offset/ReqTypeSize*ReqTypeSize != Offset ||
+ Scale/ReqTypeSize*ReqTypeSize != Scale)
+ return false; // Nope.
+
+ return true;
+}
+
+static Instruction *ConvertMallocToType(MallocInst *MI, const Type *Ty,
+ const std::string &Name,
+ ValueMapCache &VMC){
+ BasicBlock *BB = MI->getParent();
+ BasicBlock::iterator It = BB->end();
+
+ // Analyze the number of bytes allocated...
+ ExprType Expr = ClassifyExpression(MI->getArraySize());
+
+ const PointerType *AllocTy = cast<PointerType>(Ty);
+ const Type *ElType = AllocTy->getElementType();
+
+ unsigned DataSize = TD.getTypeSize(ElType);
+ unsigned OldTypeSize = TD.getTypeSize(MI->getType()->getElementType());
+
+ // Get the offset and scale coefficients that we are allocating...
+ int64_t OffsetVal = (Expr.Offset ? getConstantValue(Expr.Offset) : 0);
+ int64_t ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) : (Expr.Var !=0);
+
+ // The old type might not be of unit size, take old size into consideration
+ // here...
+ unsigned Offset = (uint64_t)OffsetVal * OldTypeSize / DataSize;
+ unsigned Scale = (uint64_t)ScaleVal * OldTypeSize / DataSize;
+
+ // Locate the malloc instruction, because we may be inserting instructions
+ It = MI;
+
+ // If we have a scale, apply it first...
+ if (Expr.Var) {
+ // Expr.Var is not neccesarily unsigned right now, insert a cast now.
+ if (Expr.Var->getType() != Type::UIntTy)
+ Expr.Var = new CastInst(Expr.Var, Type::UIntTy,
+ Expr.Var->getName()+"-uint", It);
+
+ if (Scale != 1)
+ Expr.Var = BinaryOperator::create(Instruction::Mul, Expr.Var,
+ ConstantUInt::get(Type::UIntTy, Scale),
+ Expr.Var->getName()+"-scl", It);
+
+ } else {
+ // If we are not scaling anything, just make the offset be the "var"...
+ Expr.Var = ConstantUInt::get(Type::UIntTy, Offset);
+ Offset = 0; Scale = 1;
+ }
+
+ // If we have an offset now, add it in...
+ if (Offset != 0) {
+ assert(Expr.Var && "Var must be nonnull by now!");
+ Expr.Var = BinaryOperator::create(Instruction::Add, Expr.Var,
+ ConstantUInt::get(Type::UIntTy, Offset),
+ Expr.Var->getName()+"-off", It);
+ }
+
+ assert(AllocTy == Ty);
+ return new MallocInst(AllocTy->getElementType(), Expr.Var, Name);
+}