#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/PtrUseVisitor.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
/// \brief Construct the slices of a particular alloca.
AllocaSlices(const DataLayout &DL, AllocaInst &AI);
- /// \brief Whether we determined during the trivial analysis of the alloca
- /// that it was immediately promotable with mem2reg.
- bool isAllocaPromotable() const { return IsAllocaPromotable; }
-
- /// \brief A list of directly stored values when \c isAllocaPromotable is
- /// true.
- ///
- /// The contents are undefined if the alloca is not trivially promotable.
- /// This is used to detect other allocas which should be iterated on when
- /// doing direct promotion.
- ArrayRef<Value *> getStoredValues() const { return StoredValues; }
-
/// \brief Test whether a pointer to the allocation escapes our analysis.
///
/// If this is true, the slices are never fully built and should be
void printUse(raw_ostream &OS, const_iterator I,
StringRef Indent = " ") const;
void print(raw_ostream &OS) const;
- void LLVM_ATTRIBUTE_NOINLINE LLVM_ATTRIBUTE_USED dump(const_iterator I) const;
- void LLVM_ATTRIBUTE_NOINLINE LLVM_ATTRIBUTE_USED dump() const;
+ void dump(const_iterator I) const;
+ void dump() const;
#endif
private:
class SliceBuilder;
friend class AllocaSlices::SliceBuilder;
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
/// \brief Handle to alloca instruction to simplify method interfaces.
AllocaInst &AI;
-
- /// \brief A flag indicating if the alloca is trivially promotable.
- ///
- /// While walking the alloca's uses we track when the uses exceed what
- /// mem2reg can trivially handle. This essentially should match the logic in
- /// \c isAllocaPromotable but re-using the existing walk of the pointer uses.
- bool IsAllocaPromotable;
-
- /// \brief Storage for stored values.
- ///
- /// Only used while the alloca is trivially promotable.
- SmallVector<Value *, 8> StoredValues;
+#endif
/// \brief The instruction responsible for this alloca not having a known set
/// of slices.
SmallPtrSet<Instruction *, 4> VisitedDeadInsts;
public:
- SliceBuilder(const DataLayout &DL, AllocaSlices &S)
+ SliceBuilder(const DataLayout &DL, AllocaInst &AI, AllocaSlices &S)
: PtrUseVisitor<SliceBuilder>(DL),
- AllocSize(DL.getTypeAllocSize(S.AI.getAllocatedType())), S(S) {}
+ AllocSize(DL.getTypeAllocSize(AI.getAllocatedType())), S(S) {}
private:
void markAsDead(Instruction &I) {
if (GEPI.use_empty())
return markAsDead(GEPI);
- // FIXME: mem2reg shouldn't care about the nature of the GEP, but instead
- // the offsets of the loads. Until then, we short-circuit here for the
- // promotable case.
- if (GEPI.hasAllZeroIndices())
- return Base::enqueueUsers(GEPI);
-
- // Otherwise, there is something in the GEP, so we disable mem2reg and
- // accumulate it.
- S.IsAllocaPromotable = false;
return Base::visitGetElementPtrInst(GEPI);
}
bool IsSplittable =
Ty->isIntegerTy() && !IsVolatile && Offset == 0 && Size >= AllocSize;
- // mem2reg can only promote non-volatile loads and stores which exactly
- // load the alloca (no offset and the right type).
- if (IsVolatile || Offset != 0 || Ty != S.AI.getAllocatedType())
- S.IsAllocaPromotable = false;
- if (S.IsAllocaPromotable)
- assert(Offset == 0);
-
insertUse(I, Offset, Size, IsSplittable);
}
return markAsDead(SI);
}
- if (S.IsAllocaPromotable)
- S.StoredValues.push_back(ValOp);
-
assert((!SI.isSimple() || ValOp->getType()->isSingleValueType()) &&
"All simple FCA stores should have been pre-split");
handleLoadOrStore(ValOp->getType(), SI, Offset, Size, SI.isVolatile());
if (!IsOffsetKnown)
return PI.setAborted(&II);
- S.IsAllocaPromotable = false;
-
insertUse(II, Offset,
Length ? Length->getLimitedValue()
: AllocSize - Offset.getLimitedValue(),
if (!IsOffsetKnown)
return PI.setAborted(&II);
- S.IsAllocaPromotable = false;
-
uint64_t RawOffset = Offset.getLimitedValue();
uint64_t Size = Length ? Length->getLimitedValue()
: AllocSize - RawOffset;
return;
}
- S.IsAllocaPromotable = false;
-
Base::visitIntrinsicInst(II);
}
return;
}
- S.IsAllocaPromotable = false;
-
insertUse(PN, Offset, PHISize);
}
if (SI.use_empty())
return markAsDead(SI);
if (Value *Result = foldSelectInst(SI)) {
- if (Result == *U) {
+ if (Result == *U)
// If the result of the constant fold will be the pointer, recurse
// through the select as if we had RAUW'ed it.
enqueueUsers(SI);
-
- // FIXME: mem2reg should support this pattern, but it doesn't.
- S.IsAllocaPromotable = false;
- } else {
+ else
// Otherwise the operand to the select is dead, and we can replace it
// with undef.
S.DeadOperands.push_back(U);
- }
return;
}
return;
}
- S.IsAllocaPromotable = false;
-
insertUse(SI, Offset, SelectSize);
}
};
AllocaSlices::AllocaSlices(const DataLayout &DL, AllocaInst &AI)
- : AI(AI), IsAllocaPromotable(true), PointerEscapingInstr(0) {
- SliceBuilder PB(DL, *this);
+ :
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+ AI(AI),
+#endif
+ PointerEscapingInstr(0) {
+ SliceBuilder PB(DL, AI, *this);
SliceBuilder::PtrInfo PtrI = PB.visitPtr(AI);
if (PtrI.isEscaped() || PtrI.isAborted()) {
// FIXME: We should sink the escape vs. abort info into the caller nicely,
print(OS, I);
}
-void AllocaSlices::dump(const_iterator I) const { print(dbgs(), I); }
-void AllocaSlices::dump() const { print(dbgs()); }
+LLVM_DUMP_METHOD void AllocaSlices::dump(const_iterator I) const {
+ print(dbgs(), I);
+}
+LLVM_DUMP_METHOD void AllocaSlices::dump() const { print(dbgs()); }
#endif // !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
AllocaSlices::const_iterator E,
uint64_t EndOffset) {
Type *Ty = 0;
+ bool IgnoreNonIntegralTypes = false;
for (AllocaSlices::const_iterator I = B; I != E; ++I) {
Use *U = I->getUse();
if (isa<IntrinsicInst>(*U->getUser()))
continue;
Type *UserTy = 0;
- if (LoadInst *LI = dyn_cast<LoadInst>(U->getUser()))
+ if (LoadInst *LI = dyn_cast<LoadInst>(U->getUser())) {
UserTy = LI->getType();
- else if (StoreInst *SI = dyn_cast<StoreInst>(U->getUser()))
+ } else if (StoreInst *SI = dyn_cast<StoreInst>(U->getUser())) {
UserTy = SI->getValueOperand()->getType();
- else
- return 0; // Bail if we have weird uses.
+ } else {
+ IgnoreNonIntegralTypes = true; // Give up on anything but an iN type.
+ continue;
+ }
if (IntegerType *ITy = dyn_cast<IntegerType>(UserTy)) {
// If the type is larger than the partition, skip it. We only encounter
// this for split integer operations where we want to use the type of the
- // entity causing the split.
- if (ITy->getBitWidth() / 8 > (EndOffset - B->beginOffset()))
+ // entity causing the split. Also skip if the type is not a byte width
+ // multiple.
+ if (ITy->getBitWidth() % 8 != 0 ||
+ ITy->getBitWidth() / 8 > (EndOffset - B->beginOffset()))
continue;
// If we have found an integer type use covering the alloca, use that
- // regardless of the other types, as integers are often used for a
- // "bucket
- // of bits" type.
+ // regardless of the other types, as integers are often used for
+ // a "bucket of bits" type.
+ //
+ // NB: This *must* be the only return from inside the loop so that the
+ // order of slices doesn't impact the computed type.
return ITy;
+ } else if (IgnoreNonIntegralTypes) {
+ continue;
}
if (Ty && Ty != UserTy)
- return 0;
+ IgnoreNonIntegralTypes = true; // Give up on anything but an iN type.
Ty = UserTy;
}
if (!NewTy->isSingleValueType() || !OldTy->isSingleValueType())
return false;
+ // We can convert pointers to integers and vice-versa. Same for vectors
+ // of pointers and integers.
+ OldTy = OldTy->getScalarType();
+ NewTy = NewTy->getScalarType();
if (NewTy->isPointerTy() || OldTy->isPointerTy()) {
if (NewTy->isPointerTy() && OldTy->isPointerTy())
return true;
/// inttoptr, and ptrtoint casts. Use the \c canConvertValue predicate to test
/// two types for viability with this routine.
static Value *convertValue(const DataLayout &DL, IRBuilderTy &IRB, Value *V,
- Type *Ty) {
- assert(canConvertValue(DL, V->getType(), Ty) &&
- "Value not convertable to type");
- if (V->getType() == Ty)
+ Type *NewTy) {
+ Type *OldTy = V->getType();
+ assert(canConvertValue(DL, OldTy, NewTy) && "Value not convertable to type");
+
+ if (OldTy == NewTy)
return V;
- if (IntegerType *OldITy = dyn_cast<IntegerType>(V->getType()))
- if (IntegerType *NewITy = dyn_cast<IntegerType>(Ty))
+
+ if (IntegerType *OldITy = dyn_cast<IntegerType>(OldTy))
+ if (IntegerType *NewITy = dyn_cast<IntegerType>(NewTy))
if (NewITy->getBitWidth() > OldITy->getBitWidth())
return IRB.CreateZExt(V, NewITy);
- if (V->getType()->isIntegerTy() && Ty->isPointerTy())
- return IRB.CreateIntToPtr(V, Ty);
- if (V->getType()->isPointerTy() && Ty->isIntegerTy())
- return IRB.CreatePtrToInt(V, Ty);
- return IRB.CreateBitCast(V, Ty);
+ // See if we need inttoptr for this type pair. A cast involving both scalars
+ // and vectors requires and additional bitcast.
+ if (OldTy->getScalarType()->isIntegerTy() &&
+ NewTy->getScalarType()->isPointerTy()) {
+ // Expand <2 x i32> to i8* --> <2 x i32> to i64 to i8*
+ if (OldTy->isVectorTy() && !NewTy->isVectorTy())
+ return IRB.CreateIntToPtr(IRB.CreateBitCast(V, DL.getIntPtrType(NewTy)),
+ NewTy);
+
+ // Expand i128 to <2 x i8*> --> i128 to <2 x i64> to <2 x i8*>
+ if (!OldTy->isVectorTy() && NewTy->isVectorTy())
+ return IRB.CreateIntToPtr(IRB.CreateBitCast(V, DL.getIntPtrType(NewTy)),
+ NewTy);
+
+ return IRB.CreateIntToPtr(V, NewTy);
+ }
+
+ // See if we need ptrtoint for this type pair. A cast involving both scalars
+ // and vectors requires and additional bitcast.
+ if (OldTy->getScalarType()->isPointerTy() &&
+ NewTy->getScalarType()->isIntegerTy()) {
+ // Expand <2 x i8*> to i128 --> <2 x i8*> to <2 x i64> to i128
+ if (OldTy->isVectorTy() && !NewTy->isVectorTy())
+ return IRB.CreateBitCast(IRB.CreatePtrToInt(V, DL.getIntPtrType(OldTy)),
+ NewTy);
+
+ // Expand i8* to <2 x i32> --> i8* to i64 to <2 x i32>
+ if (!OldTy->isVectorTy() && NewTy->isVectorTy())
+ return IRB.CreateBitCast(IRB.CreatePtrToInt(V, DL.getIntPtrType(OldTy)),
+ NewTy);
+
+ return IRB.CreatePtrToInt(V, NewTy);
+ }
+
+ return IRB.CreateBitCast(V, NewTy);
}
/// \brief Test whether the given slice use can be promoted to a vector.
if (S.begin() == S.end())
return Changed;
- // Trivially promotable, don't go through the splitting and rewriting.
- if (S.isAllocaPromotable()) {
- DEBUG(dbgs() << " Directly promoting alloca: " << AI << "\n");
- PromotableAllocas.push_back(&AI);
-
- // Walk through the stored values quickly here to handle directly
- // promotable allocas that require iterating on other allocas.
- ArrayRef<Value *> StoredValues = S.getStoredValues();
- for (ArrayRef<Value *>::iterator SVI = StoredValues.begin(),
- SVE = StoredValues.end();
- SVI != SVE; ++SVI)
- if ((*SVI)->getType()->isPointerTy())
- if (AllocaInst *SAI =
- dyn_cast<AllocaInst>((*SVI)->stripInBoundsOffsets()))
- PostPromotionWorklist.insert(SAI);
- return true;
- }
-
Changed |= splitAlloca(AI, S);
DEBUG(dbgs() << " Speculating PHIs\n");
if (DT && !ForceSSAUpdater) {
DEBUG(dbgs() << "Promoting allocas with mem2reg...\n");
- PromoteMemToReg(PromotableAllocas, *DT, DL);
+ PromoteMemToReg(PromotableAllocas, *DT);
PromotableAllocas.clear();
return true;
}