+// 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;
+}
+
+
+// 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...
+ analysis::ExprType Expr = analysis::ClassifyExpression(MI->getArraySize());
+
+ // Get information about the base datatype being allocated, before & after
+ unsigned 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...
+ int OffsetVal = Expr.Offset ? getConstantValue(Expr.Offset) : 0;
+ int ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) : (Expr.Var ? 1 : 0);
+ if (ScaleVal < 0 || OffsetVal < 0) {
+ cerr << "malloc of a negative number???\n";
+ return false;
+ }
+
+ // The old type might not be of unit size, take old size into consideration
+ // here...
+ unsigned Offset = (unsigned)OffsetVal * OldTypeSize;
+ unsigned Scale = (unsigned)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...
+ analysis::ExprType Expr = analysis::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...
+ int OffsetVal = (Expr.Offset ? getConstantValue(Expr.Offset) : 0);
+ int ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) : (Expr.Var ? 1 : 0);
+
+ // The old type might not be of unit size, take old size into consideration
+ // here...
+ unsigned Offset = (unsigned)OffsetVal * OldTypeSize / DataSize;
+ unsigned Scale = (unsigned)ScaleVal * OldTypeSize / DataSize;
+
+ // Locate the malloc instruction, because we may be inserting instructions
+ It = find(BB->getInstList().begin(), BB->getInstList().end(), 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) {
+ Instruction *CI = new CastInst(Expr.Var, Type::UIntTy);
+ if (Expr.Var->hasName()) CI->setName(Expr.Var->getName()+"-uint");
+ It = BB->getInstList().insert(It, CI)+1;
+ Expr.Var = CI;
+ }
+
+ if (Scale != 1) {
+ Instruction *ScI =
+ BinaryOperator::create(Instruction::Mul, Expr.Var,
+ ConstantUInt::get(Type::UIntTy, Scale));
+ if (Expr.Var->hasName()) ScI->setName(Expr.Var->getName()+"-scl");
+ It = BB->getInstList().insert(It, ScI)+1;
+ Expr.Var = ScI;
+ }
+
+ } 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!");
+
+ Instruction *AddI =
+ BinaryOperator::create(Instruction::Add, Expr.Var,
+ ConstantUInt::get(Type::UIntTy, Offset));
+ if (Expr.Var->hasName()) AddI->setName(Expr.Var->getName()+"-off");
+ It = BB->getInstList().insert(It, AddI)+1;
+ Expr.Var = AddI;
+ }
+
+ Instruction *NewI = new MallocInst(AllocTy, Expr.Var, Name);
+
+ assert(AllocTy == Ty);
+ return NewI;
+}
+