[opaque pointer types] [NFC] Take advantage of get{Source,Result}ElementType when folding GEPs.

[eddyb]

Rebased on top of rL258145.

[mjacob]

I'm stopping reviewing here. Please create a separate patch for the changes in SymbolicallyEvaluateGEP.

include/llvm/Analysis/ConstantFolding.h

50–55

Instead of introducing this function with the implicit requirement of having to provide InstOrCE if Opcode == Instruction::GetElementPtr, this should be made explicit by introducing a function specifically for GEPs (similar to ConstantFoldCompareInstOperands()).

lib/Analysis/ConstantFolding.cpp

729–730

The lack of consistency of parameter names is slightly confusing here. Am I right that ResultTy is the pointer type of the GEP, and SrcTy and ResultElementTy are pointee types?

734

Ptr is always a constant of pointer type, right? I'll remove this check in a separate commit.

[eddyb]

include/llvm/Analysis/ConstantFolding.h

50–55

That's not really possible without introducing a special case at each call site.
Or maybe I can add a function to wrap ConstantFoldInstOperands(I, I->getOpcode(), I->getType(), ...) in the Instruction* case, that seems more plausible.

[mjacob]

include/llvm/Analysis/ConstantFolding.h

50–55

Thinking over this again, I don't like what I proposed in my last comment. Instead, I created the revisions D16378, D16380, D16383 to refactor the API to make this change a bit easier.

[eddyb]

Rebased on top D16383.

[eddyb]

Moved the invocation of SymbolicallyEvaluateGEP and its StructType handling to simplify the patch.

[dblaikie]

lib/Analysis/ConstantFolding.cpp

739

How/why did this get rolled in here?

[mjacob]

LGTM

lib/Analysis/ConstantFolding.cpp

733–736

Actually Ptr can also be a vector of pointers here. I have reverted the commit in which I moved this check to an assertion. When merging / rebasing, make sure to include the isPointerTy() check, but *not* the assertion.

[eddyb]

lib/Analysis/ConstantFolding.cpp

739

I had two calls to SymbolicallyEvaluateGEP at some point and it was easier to have it here than two CastGEPIndices at each site.

IMO CastGEPIndices shouldn't bother creating a GEP ConstantExpression but rather change what Ops in this function points to (if any indices were cast).

[dblaikie]

lib/Analysis/ConstantFolding.cpp

739

Realize that, to speed throughput, I'm looking at these changes /really/ superficially/mechanically. Anything that's more than a very local change for accessing type information slows me down a fair bit & I may not understand it fully. (case in point here - I haven't looked at what this function is trying to do or how it might best do that - just at whether the behavior seems to be preserved by moving around the type information and how it's accessed) :)

So the more you can help me understand anything more complicated than that (or avoid such complications/separate them into pre or post patches), the better.

860

Was this dead code previously?

include/llvm/Analysis/ConstantFolding.h

 namespace llvm {
   class Constant;
   class ConstantExpr;
   class Instruction;
   class DataLayout;
   class TargetLibraryInfo;
   class Function;
   class Type;
+  class Value;
   template<typename T>
   class ArrayRef;
 
 /// ConstantFoldInstruction - Try to constant fold the specified instruction.
 /// If successful, the constant result is returned, if not, null is returned.
 /// Note that this fails if not all of the operands are constant.  Otherwise,
 /// this function can only fail when attempting to fold instructions like loads
 /// and stores, which have no constant expression form.
   Constant *ConstantFoldInstruction(Instruction *I, const DataLayout &DL,
                                     const TargetLibraryInfo *TLI = nullptr);
 
 /// ConstantFoldConstantExpression - Attempt to fold the constant expression
 /// using the specified DataLayout.  If successful, the constant result is
 /// result is returned, if not, null is returned.
   Constant *
   ConstantFoldConstantExpression(const ConstantExpr *CE, const DataLayout &DL,
                                  const TargetLibraryInfo *TLI = nullptr);
 
+  Constant *ConstantFoldInstOperands(const Value *InstOrCE,
+                                     unsigned Opcode, Type *DestTy,
+                                     ArrayRef<Constant *> Ops,
+                                     const DataLayout &DL,
+                                     const TargetLibraryInfo *TLI = nullptr);
+
 /// ConstantFoldInstOperands - Attempt to constant fold an instruction with the
 /// specified operands.  If successful, the constant result is returned, if not,
 /// null is returned.  Note that this function can fail when attempting to
 /// fold instructions like loads and stores, which have no constant expression
 /// form.
 ///
   Constant *ConstantFoldInstOperands(unsigned Opcode, Type *DestTy,
                                      ArrayRef<Constant *> Ops,

lib/Analysis/ConstantFolding.cpp

static Constant *CastGEPIndices(Type *SrcTy, ArrayRef<Constant *> Ops,
                                 Type *ResultTy, const DataLayout &DL,
                                 const TargetLibraryInfo *TLI) {
   Type *IntPtrTy = DL.getIntPtrType(ResultTy);
 
   bool Any = false;
   SmallVector<Constant*, 32> NewIdxs;
   for (unsigned i = 1, e = Ops.size(); i != e; ++i) {
     if ((i == 1 ||
-         !isa<StructType>(GetElementPtrInst::getIndexedType(
-             cast<PointerType>(Ops[0]->getType()->getScalarType())
-                 ->getElementType(),
+         !isa<StructType>(GetElementPtrInst::getIndexedType(SrcTy,
              Ops.slice(1, i - 1)))) &&
         Ops[i]->getType() != IntPtrTy) {
       Any = true;
       NewIdxs.push_back(ConstantExpr::getCast(CastInst::getCastOpcode(Ops[i],
                                                                       true,
                                                                       IntPtrTy,
                                                                       true),
                                               Ops[i], IntPtrTy));
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
     if (Constant *Folded = ConstantFoldConstantExpression(CE, DL, TLI))
       C = Folded;
   }
 
   return C;
 }
 
 /// Strip the pointer casts, but preserve the address space information.
-static Constant* StripPtrCastKeepAS(Constant* Ptr) {
+static Constant* StripPtrCastKeepAS(Constant* Ptr, Type *&SrcTy) {
   assert(Ptr->getType()->isPointerTy() && "Not a pointer type");
   PointerType *OldPtrTy = cast<PointerType>(Ptr->getType());
   Ptr = Ptr->stripPointerCasts();
   PointerType *NewPtrTy = cast<PointerType>(Ptr->getType());
 
+  SrcTy = NewPtrTy->getPointerElementType();
+
   // Preserve the address space number of the pointer.
   if (NewPtrTy->getAddressSpace() != OldPtrTy->getAddressSpace()) {
-    NewPtrTy = NewPtrTy->getElementType()->getPointerTo(
-      OldPtrTy->getAddressSpace());
+    NewPtrTy = SrcTy->getPointerTo(OldPtrTy->getAddressSpace());
     Ptr = ConstantExpr::getPointerCast(Ptr, NewPtrTy);
   }
   return Ptr;
 }
 
 /// If we can symbolically evaluate the GEP constant expression, do so.
 static Constant *SymbolicallyEvaluateGEP(Type *SrcTy, ArrayRef<Constant *> Ops,
-                                         Type *ResultTy, const DataLayout &DL,
+                                         Type *ResultTy, Type *ResultElementTy,
+                                         const DataLayout &DL,
                                          const TargetLibraryInfo *TLI) {
   Constant *Ptr = Ops[0];
-  if (!Ptr->getType()->getPointerElementType()->isSized() ||
-      !Ptr->getType()->isPointerTy())
+  if (!SrcTy->isSized() || !Ptr->getType()->isPointerTy())
     return nullptr;
 
   Type *IntPtrTy = DL.getIntPtrType(Ptr->getType());
-  Type *ResultElementTy = ResultTy->getPointerElementType();
 
   // If this is a constant expr gep that is effectively computing an
   // "offsetof", fold it into 'cast int Size to T*' instead of 'gep 0, 0, 12'
   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
     if (!isa<ConstantInt>(Ops[i])) {
 
       // If this is "gep i8* Ptr, (sub 0, V)", fold this as:
       // "inttoptr (sub (ptrtoint Ptr), V)"
       if (Ops.size() == 2 && ResultElementTy->isIntegerTy(8)) {
         ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[1]);
for (unsigned i = 1, e = Ops.size(); i != e; ++i)
     }
 
   unsigned BitWidth = DL.getTypeSizeInBits(IntPtrTy);
   APInt Offset =
       APInt(BitWidth,
             DL.getIndexedOffset(
                 Ptr->getType(),
                 makeArrayRef((Value * const *)Ops.data() + 1, Ops.size() - 1)));
-  Ptr = StripPtrCastKeepAS(Ptr);
+  Ptr = StripPtrCastKeepAS(Ptr, SrcTy);
 
   // If this is a GEP of a GEP, fold it all into a single GEP.
   while (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) {
     SmallVector<Value *, 4> NestedOps(GEP->op_begin() + 1, GEP->op_end());
 
     // Do not try the incorporate the sub-GEP if some index is not a number.
     bool AllConstantInt = true;
     for (unsigned i = 0, e = NestedOps.size(); i != e; ++i)
       if (!isa<ConstantInt>(NestedOps[i])) {
         AllConstantInt = false;
         break;
       }
     if (!AllConstantInt)
       break;
 
     Ptr = cast<Constant>(GEP->getOperand(0));
     Offset += APInt(BitWidth, DL.getIndexedOffset(Ptr->getType(), NestedOps));
-    Ptr = StripPtrCastKeepAS(Ptr);
+    Ptr = StripPtrCastKeepAS(Ptr, SrcTy);
   }
 
   // If the base value for this address is a literal integer value, fold the
   // getelementptr to the resulting integer value casted to the pointer type.
   APInt BasePtr(BitWidth, 0);
   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
     if (CE->getOpcode() == Instruction::IntToPtr) {
       if (ConstantInt *Base = dyn_cast<ConstantInt>(CE->getOperand(0)))
static Constant *SymbolicallyEvaluateGEP(Type *SrcTy, ArrayRef<Constant *> Ops,
   // we eliminate over-indexing of the notional static type array bounds.
   // This makes it easy to determine if the getelementptr is "inbounds".
   // Also, this helps GlobalOpt do SROA on GlobalVariables.
   Type *Ty = Ptr->getType();
   assert(Ty->isPointerTy() && "Forming regular GEP of non-pointer type");
   SmallVector<Constant *, 32> NewIdxs;
 
   do {
-    if (SequentialType *ATy = dyn_cast<SequentialType>(Ty)) {
-      if (ATy->isPointerTy()) {
+    if (StructType *STy = dyn_cast<StructType>(Ty)) {
+      // If we end up with an offset that isn't valid for this struct type, we
+      // can't re-form this GEP in a regular form, so bail out. The pointer
+      // operand likely went through casts that are necessary to make the GEP
+      // sensible.
+      const StructLayout &SL = *DL.getStructLayout(STy);
+      if (Offset.uge(SL.getSizeInBytes()))
+        break;
+
+      // Determine which field of the struct the offset points into. The
+      // getZExtValue is fine as we've already ensured that the offset is
+      // within the range representable by the StructLayout API.
+      unsigned ElIdx = SL.getElementContainingOffset(Offset.getZExtValue());
+      NewIdxs.push_back(ConstantInt::get(Type::getInt32Ty(Ty->getContext()),
+                                         ElIdx));
+      Offset -= APInt(BitWidth, SL.getElementOffset(ElIdx));
+      Ty = STy->getTypeAtIndex(ElIdx);
+    } else {
+      if (Ty->isPointerTy()) {
         // The only pointer indexing we'll do is on the first index of the GEP.
         if (!NewIdxs.empty())
           break;
 
+        Ty = SrcTy;
+
         // Only handle pointers to sized types, not pointers to functions.
-        if (!ATy->getElementType()->isSized())
+        if (!Ty->isSized())
           return nullptr;
+      } else if (auto *ATy = dyn_cast<SequentialType>(Ty)) {
+        Ty = ATy->getElementType();
+      } else {
+        // We've reached some non-indexable type.
+        break;
       }
 
       // Determine which element of the array the offset points into.
-      APInt ElemSize(BitWidth, DL.getTypeAllocSize(ATy->getElementType()));
+      APInt ElemSize(BitWidth, DL.getTypeAllocSize(Ty));
       if (ElemSize == 0)
         // The element size is 0. This may be [0 x Ty]*, so just use a zero
         // index for this level and proceed to the next level to see if it can
         // accommodate the offset.
         NewIdxs.push_back(ConstantInt::get(IntPtrTy, 0));
       else {
         // The element size is non-zero divide the offset by the element
         // size (rounding down), to compute the index at this level.
         APInt NewIdx = Offset.udiv(ElemSize);
         Offset -= NewIdx * ElemSize;
         NewIdxs.push_back(ConstantInt::get(IntPtrTy, NewIdx));
       }
-      Ty = ATy->getElementType();
-    } else if (StructType *STy = dyn_cast<StructType>(Ty)) {
-      // If we end up with an offset that isn't valid for this struct type, we
-      // can't re-form this GEP in a regular form, so bail out. The pointer
-      // operand likely went through casts that are necessary to make the GEP
-      // sensible.
-      const StructLayout &SL = *DL.getStructLayout(STy);
-      if (Offset.uge(SL.getSizeInBytes()))
-        break;
-
-      // Determine which field of the struct the offset points into. The
-      // getZExtValue is fine as we've already ensured that the offset is
-      // within the range representable by the StructLayout API.
-      unsigned ElIdx = SL.getElementContainingOffset(Offset.getZExtValue());
-      NewIdxs.push_back(ConstantInt::get(Type::getInt32Ty(Ty->getContext()),
-                                         ElIdx));
-      Offset -= APInt(BitWidth, SL.getElementOffset(ElIdx));
-      Ty = STy->getTypeAtIndex(ElIdx);
-    } else {
-      // We've reached some non-indexable type.
-      break;
     }
   } while (Ty != ResultElementTy);
 
   // If we haven't used up the entire offset by descending the static
   // type, then the offset is pointing into the middle of an indivisible
   // member, so we can't simplify it.
   if (Offset != 0)
     return nullptr;
Constant *llvm::ConstantFoldInstruction(Instruction *I, const DataLayout &DL,
   }
 
   if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I)) {
     return ConstantExpr::getExtractValue(
                                     cast<Constant>(EVI->getAggregateOperand()),
                                     EVI->getIndices());
   }
 
-  return ConstantFoldInstOperands(I->getOpcode(), I->getType(), Ops, DL, TLI);
+  return ConstantFoldInstOperands(I, I->getOpcode(), I->getType(), Ops, DL, TLI);
 }
 
 static Constant *
 ConstantFoldConstantExpressionImpl(const ConstantExpr *CE, const DataLayout &DL,
                                    const TargetLibraryInfo *TLI,
                                    SmallPtrSetImpl<ConstantExpr *> &FoldedOps) {
   SmallVector<Constant *, 8> Ops;
   for (User::const_op_iterator i = CE->op_begin(), e = CE->op_end(); i != e;
        ++i) {
     Constant *NewC = cast<Constant>(*i);
     // Recursively fold the ConstantExpr's operands. If we have already folded
     // a ConstantExpr, we don't have to process it again.
     if (ConstantExpr *NewCE = dyn_cast<ConstantExpr>(NewC)) {
       if (FoldedOps.insert(NewCE).second)
         NewC = ConstantFoldConstantExpressionImpl(NewCE, DL, TLI, FoldedOps);
     }
     Ops.push_back(NewC);
   }
 
   if (CE->isCompare())
     return ConstantFoldCompareInstOperands(CE->getPredicate(), Ops[0], Ops[1],
                                            DL, TLI);
-  return ConstantFoldInstOperands(CE->getOpcode(), CE->getType(), Ops, DL, TLI);
+  return ConstantFoldInstOperands(CE, CE->getOpcode(), CE->getType(), Ops, DL, TLI);
 }
 
 /// Attempt to fold the constant expression
 /// using the specified DataLayout.  If successful, the constant result is
 /// result is returned, if not, null is returned.
 Constant *llvm::ConstantFoldConstantExpression(const ConstantExpr *CE,
                                                const DataLayout &DL,
                                                const TargetLibraryInfo *TLI) {

 /// TODO: This function neither utilizes nor preserves nsw/nuw/inbounds/etc
 /// information, due to only being passed an opcode and operands. Constant
 /// folding using this function strips this information.
 ///
 Constant *llvm::ConstantFoldInstOperands(unsigned Opcode, Type *DestTy,
                                          ArrayRef<Constant *> Ops,
                                          const DataLayout &DL,
                                          const TargetLibraryInfo *TLI) {
+  return ConstantFoldInstOperands(nullptr, Opcode, DestTy, Ops, DL, TLI);
+}
+
+Constant *llvm::ConstantFoldInstOperands(const Value *InstOrCE,
+                                         unsigned Opcode, Type *DestTy,
+                                         ArrayRef<Constant *> Ops,
+                                         const DataLayout &DL,
+                                         const TargetLibraryInfo *TLI) {
   // Handle easy binops first.
   if (Instruction::isBinaryOp(Opcode)) {
     if (isa<ConstantExpr>(Ops[0]) || isa<ConstantExpr>(Ops[1])) {
       if (Constant *C = SymbolicallyEvaluateBinop(Opcode, Ops[0], Ops[1], DL))
         return C;
     }
 
     return ConstantExpr::get(Opcode, Ops[0], Ops[1]);
case Instruction::Select:
     return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]);
   case Instruction::ExtractElement:
     return ConstantExpr::getExtractElement(Ops[0], Ops[1]);
   case Instruction::InsertElement:
     return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]);
   case Instruction::ShuffleVector:
     return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]);
   case Instruction::GetElementPtr: {
-    Type *SrcTy = nullptr;
+    assert(InstOrCE && "Missing instruction/constant expression");
+    auto *GEP = cast<GEPOperator>(InstOrCE);
+    Type *SrcTy = GEP->getSourceElementType();
+    Type *DestElemTy = GEP->getResultElementType();
+
     if (Constant *C = CastGEPIndices(SrcTy, Ops, DestTy, DL, TLI))
       return C;
-    if (Constant *C = SymbolicallyEvaluateGEP(SrcTy, Ops, DestTy, DL, TLI))
+    if (Constant *C = SymbolicallyEvaluateGEP(SrcTy, Ops, DestTy, DestElemTy, DL, TLI))
       return C;
 
     return ConstantExpr::getGetElementPtr(SrcTy, Ops[0], Ops.slice(1));
   }
   }
 }
 
 /// Attempt to constant fold a compare

lib/Analysis/InlineCost.cpp

 
 bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) {
   Value *Operand = I.getOperand(0);
   Constant *COp = dyn_cast<Constant>(Operand);
   if (!COp)
     COp = SimplifiedValues.lookup(Operand);
   if (COp) {
     const DataLayout &DL = F.getParent()->getDataLayout();
-    if (Constant *C = ConstantFoldInstOperands(I.getOpcode(), I.getType(),
+    if (Constant *C = ConstantFoldInstOperands(&I, I.getOpcode(), I.getType(),
                                                COp, DL)) {
       SimplifiedValues[&I] = C;
       return true;
     }
   }
 
   // Disable any SROA on the argument to arbitrary unary operators.
   disableSROA(Operand);

lib/Analysis/InstructionSimplify.cpp

if (ConstOps.size() == I->getNumOperands()) {
       if (CmpInst *C = dyn_cast<CmpInst>(I))
         return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0],
                                                ConstOps[1], Q.DL, Q.TLI);
 
       if (LoadInst *LI = dyn_cast<LoadInst>(I))
         if (!LI->isVolatile())
           return ConstantFoldLoadFromConstPtr(ConstOps[0], Q.DL);
 
-      return ConstantFoldInstOperands(I->getOpcode(), I->getType(), ConstOps,
+      return ConstantFoldInstOperands(I, I->getOpcode(), I->getType(), ConstOps,
                                       Q.DL, Q.TLI);
     }
   }
 
   return nullptr;
 }
 
 /// Given operands for a SelectInst, see if we can fold the result.

lib/Analysis/ScalarEvolution.cpp

static Constant *EvaluateExpression(Value *V, const Loop *L,
 
   if (CmpInst *CI = dyn_cast<CmpInst>(I))
     return ConstantFoldCompareInstOperands(CI->getPredicate(), Operands[0],
                                            Operands[1], DL, TLI);
   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
     if (!LI->isVolatile())
       return ConstantFoldLoadFromConstPtr(Operands[0], DL);
   }
-  return ConstantFoldInstOperands(I->getOpcode(), I->getType(), Operands, DL,
+  return ConstantFoldInstOperands(I, I->getOpcode(), I->getType(), Operands, DL,
                                   TLI);
 }
 
 
 // If every incoming value to PN except the one for BB is a specific Constant,
 // return that, else return nullptr.
 static Constant *getOtherIncomingValue(PHINode *PN, BasicBlock *BB) {
   Constant *IncomingVal = nullptr;
if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
           const DataLayout &DL = getDataLayout();
           if (const CmpInst *CI = dyn_cast<CmpInst>(I))
             C = ConstantFoldCompareInstOperands(CI->getPredicate(), Operands[0],
                                                 Operands[1], DL, &TLI);
           else if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
             if (!LI->isVolatile())
               C = ConstantFoldLoadFromConstPtr(Operands[0], DL);
           } else
-            C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), Operands,
+            C = ConstantFoldInstOperands(I, I->getOpcode(), I->getType(), Operands,
                                          DL, &TLI);
           if (!C) return V;
           return getSCEV(C);
         }
       }
     }
 
     // This is some other type of SCEVUnknown, just return it.

lib/Transforms/Utils/SimplifyCFG.cpp

else
       return nullptr;
   }
 
   if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) {
     return ConstantFoldCompareInstOperands(Cmp->getPredicate(), COps[0],
                                            COps[1], DL);
   }
 
-  return ConstantFoldInstOperands(I->getOpcode(), I->getType(), COps, DL);
+  return ConstantFoldInstOperands(I, I->getOpcode(), I->getType(), COps, DL);
 }
 
 /// Try to determine the resulting constant values in phi nodes
 /// at the common destination basic block, *CommonDest, for one of the case
 /// destionations CaseDest corresponding to value CaseVal (0 for the default
 /// case), of a switch instruction SI.
 static bool
 GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest,