X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FTransformInternals.cpp;h=7aa5564fbee13b6744b39b4248ad85bcddc1ca91;hb=97f4b664cd8a537cd2bf37b6a9d06a174078e947;hp=6929a5fb3c01d0295dc9f13600eacb75c33a6a2d;hpb=d5b48ca422089a17fa6ba2945d3f8b46fff7d689;p=oota-llvm.git diff --git a/lib/Transforms/TransformInternals.cpp b/lib/Transforms/TransformInternals.cpp index 6929a5fb3c0..7aa5564fbee 100644 --- a/lib/Transforms/TransformInternals.cpp +++ b/lib/Transforms/TransformInternals.cpp @@ -6,85 +6,30 @@ //===----------------------------------------------------------------------===// #include "TransformInternals.h" -#include "llvm/Method.h" #include "llvm/Type.h" -#include "llvm/ConstPoolVals.h" - -// 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. -// -bool losslessCastableTypes(const Type *T1, const Type *T2) { - if (!T1->isPrimitiveType() && !T1->isPointerType()) return false; - if (!T2->isPrimitiveType() && !T2->isPointerType()) 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 - } -} - - -// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) -// with a value, then remove and delete the original instruction. -// -void ReplaceInstWithValue(BasicBlock::InstListType &BIL, - BasicBlock::iterator &BI, Value *V) { - Instruction *I = *BI; - // Replaces all of the uses of the instruction with uses of the value - I->replaceAllUsesWith(V); - - // Remove the unneccesary instruction now... - BIL.remove(BI); - - // Make sure to propogate a name if there is one already... - if (I->hasName() && !V->hasName()) - V->setName(I->getName(), BIL.getParent()->getSymbolTable()); - - // Remove the dead instruction now... - delete I; -} - - -// ReplaceInstWithInst - Replace the instruction specified by BI with the -// instruction specified by I. The original instruction is deleted and BI is -// updated to point to the new instruction. -// -void ReplaceInstWithInst(BasicBlock::InstListType &BIL, - BasicBlock::iterator &BI, Instruction *I) { - assert(I->getParent() == 0 && - "ReplaceInstWithInst: Instruction already inserted into basic block!"); - - // Insert the new instruction into the basic block... - BI = BIL.insert(BI, I)+1; - - // Replace all uses of the old instruction, and delete it. - ReplaceInstWithValue(BIL, BI, I); +#include "llvm/Analysis/Expressions.h" +#include "llvm/Function.h" +#include "llvm/iOther.h" + +static const Type *getStructOffsetStep(const StructType *STy, uint64_t &Offset, + std::vector &Indices, + const TargetData &TD) { + assert(Offset < TD.getTypeSize(STy) && "Offset not in composite!"); + const StructLayout *SL = TD.getStructLayout(STy); - // Reexamine the instruction just inserted next time around the cleanup pass - // loop. - --BI; + // This loop terminates always on a 0 <= i < MemberOffsets.size() + unsigned i; + for (i = 0; i < SL->MemberOffsets.size()-1; ++i) + if (Offset >= SL->MemberOffsets[i] && Offset < SL->MemberOffsets[i+1]) + break; + + assert(Offset >= SL->MemberOffsets[i] && + (i == SL->MemberOffsets.size()-1 || Offset < SL->MemberOffsets[i+1])); + + // Make sure to save the current index... + Indices.push_back(ConstantUInt::get(Type::UByteTy, i)); + Offset = SL->MemberOffsets[i]; + return STy->getContainedType(i); } @@ -100,32 +45,138 @@ void ReplaceInstWithInst(BasicBlock::InstListType &BIL, // false if you want a leaf // const Type *getStructOffsetType(const Type *Ty, unsigned &Offset, - vector &Offsets, - bool StopEarly = true) { - if (!isa(Ty) || (Offset == 0 && StopEarly && !Offsets.empty())) { + std::vector &Indices, + const TargetData &TD, bool StopEarly) { + if (Offset == 0 && StopEarly && !Indices.empty()) + return Ty; // Return the leaf type + + uint64_t ThisOffset; + const Type *NextType; + if (const StructType *STy = dyn_cast(Ty)) { + ThisOffset = Offset; + NextType = getStructOffsetStep(STy, ThisOffset, Indices, TD); + } else if (const ArrayType *ATy = dyn_cast(Ty)) { + assert(Offset == 0 || Offset < TD.getTypeSize(ATy) && + "Offset not in composite!"); + + NextType = ATy->getElementType(); + unsigned ChildSize = TD.getTypeSize(NextType); + Indices.push_back(ConstantSInt::get(Type::LongTy, Offset/ChildSize)); + ThisOffset = (Offset/ChildSize)*ChildSize; + } else { Offset = 0; // Return the offset that we were able to acheive return Ty; // Return the leaf type } - assert(Offset < TD.getTypeSize(Ty) && "Offset not in struct!"); - const StructType *STy = cast(Ty); - const StructLayout *SL = TD.getStructLayout(STy); - - // This loop terminates always on a 0 <= i < MemberOffsets.size() - unsigned i; - for (i = 0; i < SL->MemberOffsets.size()-1; ++i) - if (Offset >= SL->MemberOffsets[i] && Offset < SL->MemberOffsets[i+1]) - break; - - assert(Offset >= SL->MemberOffsets[i] && - (i == SL->MemberOffsets.size()-1 || Offset < SL->MemberOffsets[i+1])); - - // Make sure to save the current index... - Offsets.push_back(ConstPoolUInt::get(Type::UByteTy, i)); - - unsigned SubOffs = Offset - SL->MemberOffsets[i]; - const Type *LeafTy = getStructOffsetType(STy->getElementTypes()[i], SubOffs, - Offsets); - Offset = SL->MemberOffsets[i] + SubOffs; + unsigned SubOffs = Offset - ThisOffset; + const Type *LeafTy = getStructOffsetType(NextType, SubOffs, + Indices, TD, StopEarly); + Offset = ThisOffset + SubOffs; return LeafTy; } + +// ConvertibleToGEP - This function returns true if the specified value V is +// a valid index into a pointer of type Ty. If it is valid, Idx is filled in +// with the values that would be appropriate to make this a getelementptr +// instruction. The type returned is the root type that the GEP would point to +// +const Type *ConvertibleToGEP(const Type *Ty, Value *OffsetVal, + std::vector &Indices, + const TargetData &TD, + BasicBlock::iterator *BI) { + const CompositeType *CompTy = dyn_cast(Ty); + if (CompTy == 0) return 0; + + // See if the cast is of an integer expression that is either a constant, + // or a value scaled by some amount with a possible offset. + // + ExprType Expr = ClassifyExpression(OffsetVal); + + // Get the offset and scale values if they exists... + // A scale of zero with Expr.Var != 0 means a scale of 1. + // + int64_t Offset = Expr.Offset ? getConstantValue(Expr.Offset) : 0; + int64_t Scale = Expr.Scale ? getConstantValue(Expr.Scale) : 0; + + if (Expr.Var && Scale == 0) Scale = 1; // Scale != 0 if Expr.Var != 0 + + // Loop over the Scale and Offset values, filling in the Indices vector for + // our final getelementptr instruction. + // + const Type *NextTy = CompTy; + do { + if (!isa(NextTy)) + return 0; // Type must not be ready for processing... + CompTy = cast(NextTy); + + if (const StructType *StructTy = dyn_cast(CompTy)) { + // Step into the appropriate element of the structure... + uint64_t ActualOffset = (Offset < 0) ? 0 : (uint64_t)Offset; + NextTy = getStructOffsetStep(StructTy, ActualOffset, Indices, TD); + Offset -= ActualOffset; + } else { + const Type *ElTy = cast(CompTy)->getElementType(); + if (!ElTy->isSized() || (isa(CompTy) && !Indices.empty())) + return 0; // Type is unreasonable... escape! + unsigned ElSize = TD.getTypeSize(ElTy); + int64_t ElSizeS = ElSize; + + // See if the user is indexing into a different cell of this array... + if (Scale && (Scale >= ElSizeS || -Scale >= ElSizeS)) { + // A scale n*ElSize might occur if we are not stepping through + // array by one. In this case, we will have to insert math to munge + // the index. + // + int64_t ScaleAmt = Scale/ElSizeS; + if (Scale-ScaleAmt*ElSizeS) + return 0; // Didn't scale by a multiple of element size, bail out + Scale = 0; // Scale is consumed + + int64_t Index = Offset/ElSize; // is zero unless Offset > ElSize + Offset -= Index*ElSize; // Consume part of the offset + + if (BI) { // Generate code? + BasicBlock *BB = (*BI)->getParent(); + if (Expr.Var->getType() != Type::LongTy) + Expr.Var = new CastInst(Expr.Var, Type::LongTy, + Expr.Var->getName()+"-idxcast", *BI); + + if (ScaleAmt && ScaleAmt != 1) { + // If we have to scale up our index, do so now + Value *ScaleAmtVal = ConstantSInt::get(Type::LongTy, ScaleAmt); + Expr.Var = BinaryOperator::create(Instruction::Mul, Expr.Var, + ScaleAmtVal, + Expr.Var->getName()+"-scale",*BI); + } + + if (Index) { // Add an offset to the index + Value *IndexAmt = ConstantSInt::get(Type::LongTy, Index); + Expr.Var = BinaryOperator::create(Instruction::Add, Expr.Var, + IndexAmt, + Expr.Var->getName()+"-offset", + *BI); + } + } + + Indices.push_back(Expr.Var); + Expr.Var = 0; + } else if (Offset >= (int64_t)ElSize || -Offset >= (int64_t)ElSize) { + // Calculate the index that we are entering into the array cell with + uint64_t Index = Offset/ElSize; + Indices.push_back(ConstantSInt::get(Type::LongTy, Index)); + Offset -= (int64_t)(Index*ElSize); // Consume part of the offset + + } else if (isa(CompTy) || Indices.empty()) { + // Must be indexing a small amount into the first cell of the array + // Just index into element zero of the array here. + // + Indices.push_back(ConstantSInt::get(Type::LongTy, 0)); + } else { + return 0; // Hrm. wierd, can't handle this case. Bail + } + NextTy = ElTy; + } + } while (Offset || Scale); // Go until we're done! + + return NextTy; +}