Better heuristics for handling arrays
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@1296 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/ExprTypeConvert.cpp b/lib/Transforms/ExprTypeConvert.cpp
index 8379115..f8052b2 100644
--- a/lib/Transforms/ExprTypeConvert.cpp
+++ b/lib/Transforms/ExprTypeConvert.cpp
@@ -95,7 +95,17 @@
// We can convert the expr if the cast destination type is losslessly
// convertable to the requested type.
if (!losslessCastableTypes(Ty, I->getType())) return false;
- break;
+#if 1
+ // We also do not allow conversion of a cast that casts from a ptr to array
+ // of X to a *X. For example: cast [4 x %List *] * %val to %List * *
+ //
+ if (PointerType *SPT = dyn_cast<PointerType>(I->getOperand(0)->getType()))
+ if (PointerType *DPT = dyn_cast<PointerType>(I->getType()))
+ if (ArrayType *AT = dyn_cast<ArrayType>(SPT->getValueType()))
+ if (AT->getElementType() == DPT->getValueType())
+ return false;
+#endif
+ return true;
case Instruction::Add:
case Instruction::Sub:
@@ -395,6 +405,7 @@
//
static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
ValueTypeCache &CTMap) {
+ // TODO: IS THIS A BUG????
if (V->getType() == Ty) return true; // Already the right type?
// Expression type must be holdable in a register.
@@ -409,7 +420,19 @@
assert(I->getOperand(0) == V);
// We can convert the expr if the cast destination type is losslessly
// convertable to the requested type.
- return losslessCastableTypes(Ty, I->getOperand(0)->getType());
+ if (!losslessCastableTypes(Ty, I->getOperand(0)->getType()))
+ return false;
+#if 1
+ // We also do not allow conversion of a cast that casts from a ptr to array
+ // of X to a *X. For example: cast [4 x %List *] * %val to %List * *
+ //
+ if (PointerType *SPT = dyn_cast<PointerType>(I->getOperand(0)->getType()))
+ if (PointerType *DPT = dyn_cast<PointerType>(I->getType()))
+ if (ArrayType *AT = dyn_cast<ArrayType>(SPT->getValueType()))
+ if (AT->getElementType() == DPT->getValueType())
+ return false;
+#endif
+ return true;
case Instruction::Add:
if (V == I->getOperand(0) && isa<CastInst>(I->getOperand(1))) {
diff --git a/lib/Transforms/IPO/SimpleStructMutation.cpp b/lib/Transforms/IPO/SimpleStructMutation.cpp
index 8ec7f4b..c8f8896 100644
--- a/lib/Transforms/IPO/SimpleStructMutation.cpp
+++ b/lib/Transforms/IPO/SimpleStructMutation.cpp
@@ -12,6 +12,8 @@
#include "llvm/Analysis/FindUnsafePointerTypes.h"
#include "llvm/DerivedTypes.h"
+#include "llvm/Assembly/Writer.h"
+
// PruneTypes - Given a type Ty, make sure that neither it, or one of its
// subtypes, occur in TypesToModify.
//
@@ -21,14 +23,20 @@
ProcessedTypes.insert(Ty);
// If the element is in TypesToModify, remove it now...
- if (const StructType *ST = dyn_cast<StructType>(Ty))
+ if (const StructType *ST = dyn_cast<StructType>(Ty)) {
TypesToModify.erase(ST); // This doesn't fail if the element isn't present
+ cerr << "Unable to swap type: " << ST << endl;
+ }
- // Remove all types that this type contains as well...
+ // Remove all types that this type contains as well... do not remove types
+ // that are referenced only through pointers, because we depend on the size of
+ // the pointer, not on what the structure points to.
//
for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
- I != E; ++I)
- PruneTypes(*I, TypesToModify, ProcessedTypes);
+ I != E; ++I) {
+ if (!isa<PointerType>(*I))
+ PruneTypes(*I, TypesToModify, ProcessedTypes);
+ }
}
@@ -54,8 +62,8 @@
const set<const Type *> &UsedTypes = FUT.getTypes();
- // Combine the two sets, weeding out non structure types. Closures should
- // would be nice.
+ // Combine the two sets, weeding out non structure types. Closures in C++
+ // sure would be nice.
set<const StructType*> TypesToModify;
for (set<const Type *>::const_iterator I = UsedTypes.begin(),
E = UsedTypes.end(); I != E; ++I)
@@ -68,8 +76,10 @@
//
set<const Type*> ProcessedTypes;
for (set<PointerType*>::const_iterator I = UnsafePTys.begin(),
- E = UnsafePTys.end(); I != E; ++I)
+ E = UnsafePTys.end(); I != E; ++I) {
+ cerr << "Pruning type: " << *I << endl;
PruneTypes(*I, TypesToModify, ProcessedTypes);
+ }
// Build up a set of structure types that we are going to modify, and
diff --git a/lib/Transforms/LevelRaise.cpp b/lib/Transforms/LevelRaise.cpp
index 03d7acf..dfe92ee 100644
--- a/lib/Transforms/LevelRaise.cpp
+++ b/lib/Transforms/LevelRaise.cpp
@@ -38,6 +38,7 @@
#include "llvm/ConstPoolVals.h"
#include "llvm/Optimizations/ConstantHandling.h"
#include "llvm/Optimizations/DCE.h"
+#include "llvm/Analysis/Expressions.h"
#include <algorithm>
#include "llvm/Assembly/Writer.h"
@@ -57,6 +58,9 @@
#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)
+#define PRINT_PEEPHOLE4(ID, I1, I2, I3, I4) \
+ do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \
+ PRINT_PEEPHOLE(ID, 2, I3); PRINT_PEEPHOLE(ID, 3, I4); } while (0)
// isReinterpretingCast - Return true if the cast instruction specified will
@@ -269,6 +273,174 @@
}
+
+// Peephole optimize the following instructions:
+// %t1 = cast ulong <const int> to {<...>} *
+// %t2 = add {<...>} * %SP, %t1 ;; Constant must be 2nd operand
+//
+// or
+// %t1 = cast {<...>}* %SP to int*
+// %t5 = cast ulong <const int> to int*
+// %t2 = add int* %t1, %t5 ;; int is same size as field
+//
+// Into: %t3 = getelementptr {<...>} * %SP, <element indices>
+// %t2 = cast <eltype> * %t3 to {<...>}*
+//
+static bool PeepholeOptimizeAddCast(BasicBlock *BB, BasicBlock::iterator &BI,
+ Value *AddOp1, CastInst *AddOp2) {
+ Value *OffsetVal = AddOp2->getOperand(0);
+ Value *SrcPtr; // Of type pointer to struct...
+ const StructType *StructTy;
+
+ if ((StructTy = getPointedToStruct(AddOp1->getType()))) {
+ SrcPtr = AddOp1; // Handle the first case...
+ } else if (CastInst *AddOp1c = dyn_cast<CastInst>(AddOp1)) {
+ SrcPtr = AddOp1c->getOperand(0); // Handle the second case...
+ StructTy = getPointedToStruct(SrcPtr->getType());
+ }
+
+ // Only proceed if we have detected all of our conditions successfully...
+ if (!StructTy || !SrcPtr || !OffsetVal->getType()->isIntegral())
+ return false;
+
+ // 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.
+ //
+ analysis::ExprType Expr = analysis::ClassifyExpression(OffsetVal);
+ unsigned Offset = 0, Scale = 1;
+
+ // The expression must either be a constant, or a scaled index to be useful
+ if (!Expr.Offset && !Expr.Scale)
+ return false;
+
+ // Get the offset value if it exists...
+ if (Expr.Offset) {
+ if (ConstPoolSInt *CPSI = dyn_cast<ConstPoolSInt>(Expr.Offset))
+ Offset = (unsigned)CPSI->getValue();
+ else {
+ ConstPoolUInt *CPUI = cast<ConstPoolUInt>(Expr.Offset);
+ Offset = (unsigned)CPUI->getValue();
+ }
+ assert(Offset != 0 && "Expression analysis failure!");
+ }
+
+ // Get the scale value if it exists...
+ if (Expr.Scale) {
+ if (ConstPoolSInt *CPSI = dyn_cast<ConstPoolSInt>(Expr.Scale))
+ Scale = (unsigned)CPSI->getValue();
+ else {
+ ConstPoolUInt *CPUI = cast<ConstPoolUInt>(Expr.Scale);
+ Scale = (unsigned)CPUI->getValue();
+ }
+ assert(Scale != 1 && "Expression analysis failure!");
+ }
+
+ // Check to make sure the offset is not negative or really large, outside the
+ // scope of this structure...
+ //
+ if (Offset >= TD.getTypeSize(StructTy))
+ return false;
+
+ const StructLayout *SL = TD.getStructLayout(StructTy);
+ vector<ConstPoolVal*> Offsets;
+ unsigned ActualOffset = Offset;
+ const Type *ElTy = getStructOffsetType(StructTy, ActualOffset, Offsets);
+
+ if (getPointedToStruct(AddOp1->getType())) { // case 1
+ PRINT_PEEPHOLE2("add-to-gep1:in", AddOp2, *BI);
+ } else {
+ PRINT_PEEPHOLE3("add-to-gep2:in", AddOp1, AddOp2, *BI);
+ }
+
+ GetElementPtrInst *GEP = new GetElementPtrInst(SrcPtr, Offsets);
+ //AddOp2->getName());
+ BI = BB->getInstList().insert(BI, GEP)+1;
+
+ Instruction *AddrSrc = GEP;
+
+ if (const ArrayType *AT = dyn_cast<ArrayType>(ElTy)) {
+ assert((Scale == 1 || Offset == ActualOffset) &&
+ "Cannot handle scaled expression and unused offset in the same "
+ "instruction until after GEP array works!");
+
+ // Check to see if we have bottomed out INSIDE of an array reference..
+ //
+ if (Offset != ActualOffset) {
+ // Insert a cast of the "rest" of the offset to the appropriate
+ // pointer type.
+ CastInst *OffInst =
+ new CastInst(ConstPoolUInt::get(Type::ULongTy,
+ Offset-ActualOffset),
+ GEP->getType());
+ BI = BB->getInstList().insert(BI, OffInst)+1;
+
+ // Now insert an ADD to actually adjust the pointer...
+ Instruction *AddInst =
+ BinaryOperator::create(Instruction::Add, GEP, OffInst);
+ BI = BB->getInstList().insert(BI, AddInst)+1;
+
+ PRINT_PEEPHOLE2("add-to-gep:out1", OffInst, AddInst);
+
+ AddrSrc = AddInst;
+ } else if (Scale != 1) {
+ // If the scale factor occurs, then this means that there is an index into
+ // this element of the array. Check to make sure the scale factor is the
+ // same as the size of the datatype that we are dealing with.
+ //
+ assert(Scale == TD.getTypeSize(AT->getElementType()) &&
+ "Scaling by something other than the array element size!!");
+
+ // TODO: In the future, we will not want to cast the index and scale to
+ // pointer types first. We will want to create a GEP directly here.
+
+ // Now we must actually perform the scaling operation to get an
+ // appropriate value to add in... but the scale has to be done in the
+ // appropriate destination pointer type, so cast the index value now.
+ //
+ // Cast the base index pointer
+ CastInst *IdxValue = new CastInst(Expr.Var, GEP->getType());
+ BI = BB->getInstList().insert(BI, IdxValue)+1;
+
+ // Case the scale amount as well...
+ CastInst *ScaleAmt =
+ new CastInst(ConstPoolUInt::get(Type::ULongTy, Scale), GEP->getType());
+ BI = BB->getInstList().insert(BI, ScaleAmt)+1;
+
+ // Insert the multiply now. Make sure to make the constant the second arg
+ Instruction *ScaledVal =
+ BinaryOperator::create(Instruction::Mul, IdxValue, ScaleAmt);
+ BI = BB->getInstList().insert(BI, ScaledVal)+1;
+
+ // Now insert an ADD to actually adjust the pointer...
+ Instruction *AddInst =
+ BinaryOperator::create(Instruction::Add, GEP, ScaledVal);
+ BI = BB->getInstList().insert(BI, AddInst)+1;
+
+ PRINT_PEEPHOLE4("add-to-gep:out1", IdxValue, ScaleAmt, ScaledVal,
+ AddInst);
+ AddrSrc = AddInst;
+ }
+
+ // Insert a cast of the pointer to array of X to be a pointer to the
+ // element of the array.
+ //
+ // Insert a cast of the "rest" of the offset to the appropriate
+ // pointer type.
+ CastInst *ACI = new CastInst(AddrSrc, AT->getElementType());
+ BI = BB->getInstList().insert(BI, ACI)+1;
+ AddrSrc = ACI;
+
+ } else {
+ assert(Offset == ActualOffset && "GEP to middle of non array!");
+ assert(Scale == 1 && "Scale factor for expr that is not an array idx!");
+ }
+
+ Instruction *NCI = new CastInst(AddrSrc, AddOp1->getType());
+ ReplaceInstWithInst(BB->getInstList(), BI, NCI);
+ PRINT_PEEPHOLE2("add-to-gep:out", GEP, NCI);
+ return true;
+}
+
// Peephole optimize the following instructions:
// %t1 = cast int (uint) * %reg111 to uint (...) *
// %t2 = call uint (...) * %cast111( uint %key )
@@ -578,57 +750,10 @@
} else if (I->getOpcode() == Instruction::Add &&
isa<CastInst>(I->getOperand(1))) {
- // Peephole optimize the following instructions:
- // %t1 = cast ulong <const int> to {<...>} *
- // %t2 = add {<...>} * %SP, %t1 ;; Constant must be 2nd operand
- //
- // or
- // %t1 = cast {<...>}* %SP to int*
- // %t5 = cast ulong <const int> to int*
- // %t2 = add int* %t1, %t5 ;; int is same size as field
- //
- // Into: %t3 = getelementptr {<...>} * %SP, <element indices>
- // %t2 = cast <eltype> * %t3 to {<...>}*
- //
- Value *AddOp1 = I->getOperand(0);
- CastInst *AddOp2 = cast<CastInst>(I->getOperand(1));
- ConstPoolUInt *OffsetV = dyn_cast<ConstPoolUInt>(AddOp2->getOperand(0));
- unsigned Offset = OffsetV ? OffsetV->getValue() : 0;
- Value *SrcPtr; // Of type pointer to struct...
- const StructType *StructTy;
-
- if ((StructTy = getPointedToStruct(AddOp1->getType()))) {
- SrcPtr = AddOp1; // Handle the first case...
- } else if (CastInst *AddOp1c = dyn_cast<CastInst>(AddOp1)) {
- SrcPtr = AddOp1c->getOperand(0); // Handle the second case...
- StructTy = getPointedToStruct(SrcPtr->getType());
- }
-
- // Only proceed if we have detected all of our conditions successfully...
- if (Offset && StructTy && SrcPtr && Offset < TD.getTypeSize(StructTy)) {
- const StructLayout *SL = TD.getStructLayout(StructTy);
- vector<ConstPoolVal*> Offsets;
- unsigned ActualOffset = Offset;
- const Type *ElTy = getStructOffsetType(StructTy, ActualOffset, Offsets);
-
- if (getPointedToStruct(AddOp1->getType())) { // case 1
- PRINT_PEEPHOLE2("add-to-gep1:in", AddOp2, I);
- } else {
- PRINT_PEEPHOLE3("add-to-gep2:in", AddOp1, AddOp2, I);
- }
-
- GetElementPtrInst *GEP = new GetElementPtrInst(SrcPtr, Offsets);
- //AddOp2->getName());
- BI = BB->getInstList().insert(BI, GEP)+1;
-
- assert(Offset-ActualOffset == 0 &&
- "GEP to middle of element not implemented yet!");
-
- ReplaceInstWithInst(BB->getInstList(), BI,
- I = new CastInst(GEP, I->getType()));
- PRINT_PEEPHOLE2("add-to-gep:out", GEP, I);
+ if (PeepholeOptimizeAddCast(BB, BI, I->getOperand(0),
+ cast<CastInst>(I->getOperand(1))))
return true;
- }
+
#endif
}
diff --git a/lib/Transforms/TransformInternals.cpp b/lib/Transforms/TransformInternals.cpp
index ac8181b..6929a5f 100644
--- a/lib/Transforms/TransformInternals.cpp
+++ b/lib/Transforms/TransformInternals.cpp
@@ -102,7 +102,7 @@
const Type *getStructOffsetType(const Type *Ty, unsigned &Offset,
vector<ConstPoolVal*> &Offsets,
bool StopEarly = true) {
- if (!isa<StructType>(Ty) || (Offset == 0 && StopEarly)) {
+ if (!isa<StructType>(Ty) || (Offset == 0 && StopEarly && !Offsets.empty())) {
Offset = 0; // Return the offset that we were able to acheive
return Ty; // Return the leaf type
}