[IVDescriptors] Make pointer inductions compatible with opaque pointers

[nikic]

Summary

Store the used element type in the InductionDescriptor. For typed pointers, it remains the pointer element type. For opaque pointers, we always use an i8 element type, such that the step is a simple offset.

A previous version of this patch instead tried to guess the element type from the induction GEP, but this is not reliable, as the GEP may be hidden (see @both in iv_outside_user.ll).

[aeubanks]

I'm not familiar with this code, but looks fine overall with one nit

llvm/lib/Analysis/IVDescriptors.cpp

984

should this be (IK == IK_PtrInduction) == (ElementType != nullptr)?

[nikic]

Adjust assertion.

[nikic]

llvm/lib/Analysis/IVDescriptors.cpp

984

I feel like that's a bit hard to understand. What do you think about the new version that spells out the two possibilities explicitly?

[a.elovikov]

The main alternative I see here is to use different logic for opaque pointers and always base them off an i8 element type

Can we do that based on the fact the we can't deduce the element type from GEP step instruction (e.g. if there is no obvious one)?

llvm/lib/Analysis/IVDescriptors.cpp

1271

Would it work if we'd have a chain of geps with different srcElementTypes? E.g. something like

%ptr = phi [ %from.preheader ], [ ptr.next ]
%gep = getelementptr i16, %ptr, 1
%ptr.next = getelementptr i32, %gep, 1

The step isn't even representable in multiples of i32 in that scenario.

[aeubanks]

not too familiar with this code, but seems ok

llvm/lib/Analysis/IVDescriptors.cpp

1279

this is already checked by the verifier

[a.elovikov]

llvm/lib/Analysis/IVDescriptors.cpp

1271

@aeubanks , why can't this happen? Or, if it can, why isn't it an issue?

[aeubanks]

llvm/lib/Analysis/IVDescriptors.cpp

1271

I'm not super familiar with this code, but it looks like each InductionDescriptor describes a single induction. So each GEP would have its own InductionDescriptor?

[nikic]

Always use i8 element type for opaque pointers. I've come around to the idea that with opaque pointers, we should always use i8 GEPs for constant offsets. While in this particular case we can actually make a fairly good guess at a reasonable type to use, this is not possible in other cases, and for canonicalization reasons it's best to use the same approach everywhere.

[aeubanks]

can we make everything use i8 now? that'd be one less thing to worry about during the migration step

[nikic]

In D104795#2973572, @aeubanks wrote:

can we make everything use i8 now? that'd be one less thing to worry about during the migration step

Without opaque pointers, that would require inserting a bitcast before and after every GEP (unless it already happens to work on an i8 pointer). It's possible, but I don't think it makes sense with typed pointers.

[aeubanks]

I don't see any i8 geps in the test, is that expected?

llvm/include/llvm/Analysis/IVDescriptors.h

360

add TODO that this will no longer be necessary after opaque pointers

[nikic]

In D104795#2976118, @aeubanks wrote:

I don't see any i8 geps in the test, is that expected?

The test currently just checks that we don't crash. To perform vectorization the GEPs need to be inbounds, which requires opaque pointer support in LAA first.

[nikic]

Add TODO

[aeubanks]

lg

llvm/include/llvm/Analysis/IVDescriptors.h

public:
   }
 
   /// Returns binary opcode of the induction operator.
   Instruction::BinaryOps getInductionOpcode() const {
     return InductionBinOp ? InductionBinOp->getOpcode()
                           : Instruction::BinaryOpsEnd;
   }
 
+  Type *getElementType() const {
+    assert(IK == IK_PtrInduction && "Only pointer induction has element type");
+    return ElementType;
+  }
+
   /// Returns a reference to the type cast instructions in the induction
   /// update chain, that are redundant when guarded with a runtime
   /// SCEV overflow check.
   const SmallVectorImpl<Instruction *> &getCastInsts() const {
     return RedundantCasts;
   }
 
 private:
   /// Private constructor - used by \c isInductionPHI.
   InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
                       BinaryOperator *InductionBinOp = nullptr,
+                      Type *ElementType = nullptr,
                       SmallVectorImpl<Instruction *> *Casts = nullptr);
 
   /// Start value.
   TrackingVH<Value> StartValue;
   /// Induction kind.
   InductionKind IK = IK_NoInduction;
   /// Step value.
   const SCEV *Step = nullptr;
   // Instruction that advances induction variable.
   BinaryOperator *InductionBinOp = nullptr;
+  // Element type for pointer induction variables.
+  // TODO: This can be dropped once support for typed pointers is removed.
+  Type *ElementType = nullptr;
   // Instructions used for type-casts of the induction variable,
   // that are redundant when guarded with a runtime SCEV overflow check.
   SmallVector<Instruction *, 2> RedundantCasts;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_IVDESCRIPTORS_H

llvm/lib/Analysis/IVDescriptors.cpp

RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const {
   }
 
   ReductionOperations.push_back(Cur);
   return ReductionOperations;
 }
 
 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
                                          const SCEV *Step, BinaryOperator *BOp,
+                                         Type *ElementType,
                                          SmallVectorImpl<Instruction *> *Casts)
-    : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
+    : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp),
+      ElementType(ElementType) {
   assert(IK != IK_NoInduction && "Not an induction");
 
   // Start value type should match the induction kind and the value
   // itself should not be null.
   assert(StartValue && "StartValue is null");
   assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
          "StartValue is not a pointer for pointer induction");
   assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
          "StartValue is not an integer for integer induction");
 
   // Check the Step Value. It should be non-zero integer value.
   assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
          "Step value is zero");
 
   assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
          "Step value should be constant for pointer induction");
   assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
          "StepValue is not an integer");
 
   assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
          "StepValue is not FP for FpInduction");
   assert((IK != IK_FpInduction ||
           (InductionBinOp &&
            (InductionBinOp->getOpcode() == Instruction::FAdd ||
             InductionBinOp->getOpcode() == Instruction::FSub))) &&
          "Binary opcode should be specified for FP induction");
 
+  if (IK == IK_PtrInduction)
+    assert(ElementType && "Pointer induction must have element type");
+  else
+    assert(!ElementType && "Non-pointer induction cannot have element type");
+
   if (Casts) {
     for (auto &Inst : *Casts) {
       RedundantCasts.push_back(Inst);
     }
   }
 }
 
 ConstantInt *InductionDescriptor::getConstIntStepValue() const {
bool InductionDescriptor::isInductionPHI(
   }
 
   Value *StartValue =
       Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
 
   BasicBlock *Latch = AR->getLoop()->getLoopLatch();
   if (!Latch)
     return false;
-  BinaryOperator *BOp =
-      dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
 
   const SCEV *Step = AR->getStepRecurrence(*SE);
   // Calculate the pointer stride and check if it is consecutive.
   // The stride may be a constant or a loop invariant integer value.
   const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
   if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
     return false;
 
   if (PhiTy->isIntegerTy()) {
+    BinaryOperator *BOp =
+        dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
     D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
-                            CastsToIgnore);
+                            /* ElementType */ nullptr, CastsToIgnore);
     return true;
   }
 
   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
   // Pointer induction should be a constant.
   if (!ConstStep)
     return false;
 
-  ConstantInt *CV = ConstStep->getValue();
-  Type *PointerElementType = PhiTy->getPointerElementType();
-  // The pointer stride cannot be determined if the pointer element type is not
-  // sized.
-  if (!PointerElementType->isSized())
+  // Always use i8 element type for opaque pointer inductions.
+  PointerType *PtrTy = cast<PointerType>(PhiTy);
+  Type *ElementType = PtrTy->isOpaque() ? Type::getInt8Ty(PtrTy->getContext())
+                                        : PtrTy->getElementType();
+  if (!ElementType->isSized())
     return false;
 
+  ConstantInt *CV = ConstStep->getValue();
   const DataLayout &DL = Phi->getModule()->getDataLayout();
-  int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
+  int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(ElementType));
   if (!Size)
     return false;
 
   int64_t CVSize = CV->getSExtValue();
   if (CVSize % Size)
     return false;
   auto *StepValue =
       SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
-  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp);
+  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue,
+                          /* BinOp */ nullptr, ElementType);
   return true;
 }

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

case InductionDescriptor::IK_IntInduction: {
     auto *Offset = CreateMul(
         Index, Exp.expandCodeFor(Step, Index->getType(), GetInsertPoint()));
     return CreateAdd(StartValue, Offset);
   }
   case InductionDescriptor::IK_PtrInduction: {
     assert(isa<SCEVConstant>(Step) &&
            "Expected constant step for pointer induction");
     return B.CreateGEP(
-        StartValue->getType()->getPointerElementType(), StartValue,
+        ID.getElementType(), StartValue,
         CreateMul(Index,
                   Exp.expandCodeFor(Step, Index->getType()->getScalarType(),
                                     GetInsertPoint())));
   }
   case InductionDescriptor::IK_FpInduction: {
     assert(!isa<VectorType>(Index->getType()) &&
            "Vector indices not supported for FP inductions yet");
     assert(Step->getType()->isFloatingPointTy() && "Expected FP Step value");
case InductionDescriptor::IK_PtrInduction: {
     const SCEV *ScalarStep = II.getStep();
     SCEVExpander Exp(*PSE.getSE(), DL, "induction");
     Value *ScalarStepValue =
         Exp.expandCodeFor(ScalarStep, PhiType, InductionLoc);
     Value *RuntimeVF = getRuntimeVF(Builder, PhiType, VF);
     Value *NumUnrolledElems =
         Builder.CreateMul(RuntimeVF, ConstantInt::get(PhiType, State.UF));
     Value *InductionGEP = GetElementPtrInst::Create(
-        ScStValueType->getPointerElementType(), NewPointerPhi,
+        II.getElementType(), NewPointerPhi,
         Builder.CreateMul(ScalarStepValue, NumUnrolledElems), "ptr.ind",
         InductionLoc);
     NewPointerPhi->addIncoming(InductionGEP, LoopLatch);
 
     // Create UF many actual address geps that use the pointer
     // phi as base and a vectorized version of the step value
     // (<step*0, ..., step*N>) as offset.
     for (unsigned Part = 0; Part < State.UF; ++Part) {
       Type *VecPhiType = VectorType::get(PhiType, State.VF);
       Value *StartOffsetScalar =
           Builder.CreateMul(RuntimeVF, ConstantInt::get(PhiType, Part));
       Value *StartOffset =
           Builder.CreateVectorSplat(State.VF, StartOffsetScalar);
       // Create a vector of consecutive numbers from zero to VF.
       StartOffset =
           Builder.CreateAdd(StartOffset, Builder.CreateStepVector(VecPhiType));
 
       Value *GEP = Builder.CreateGEP(
-          ScStValueType->getPointerElementType(), NewPointerPhi,
+          II.getElementType(), NewPointerPhi,
           Builder.CreateMul(
               StartOffset, Builder.CreateVectorSplat(State.VF, ScalarStepValue),
               "vector.gep"));
       State.set(PhiR, GEP, Part);
     }
   }
   }
 }

llvm/test/Transforms/LoopVectorize/opaque-ptr.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -loop-vectorize -force-vector-width=2 < %s | FileCheck %s
+
+; TODO: This still crashes with inbounds on the GEPs.
+define void @test(ptr %p1.start, ptr %p2.start, ptr %p1.end) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[P1:%.*]] = phi ptr [ [[P1_START:%.*]], [[ENTRY:%.*]] ], [ [[P1_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[P2:%.*]] = phi ptr [ [[P2_START:%.*]], [[ENTRY]] ], [ [[P2_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[P1_VAL:%.*]] = load float, ptr [[P1]], align 4
+; CHECK-NEXT:    [[P2_VAL:%.*]] = load float, ptr [[P2]], align 4
+; CHECK-NEXT:    [[SUM:%.*]] = fadd float [[P1_VAL]], [[P2_VAL]]
+; CHECK-NEXT:    store float [[SUM]], ptr [[P1]], align 4
+; CHECK-NEXT:    [[P1_NEXT]] = getelementptr float, ptr [[P1]], i64 1
+; CHECK-NEXT:    [[P2_NEXT]] = getelementptr float, ptr [[P2]], i64 1
+; CHECK-NEXT:    [[C:%.*]] = icmp ne ptr [[P1_NEXT]], [[P1_END:%.*]]
+; CHECK-NEXT:    br i1 [[C]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %p1 = phi ptr [ %p1.start, %entry ], [ %p1.next, %loop ]
+  %p2 = phi ptr [ %p2.start, %entry ], [ %p2.next, %loop ]
+  %p1.val = load float, ptr %p1
+  %p2.val = load float, ptr %p2
+  %sum = fadd float %p1.val, %p2.val
+  store float %sum, ptr %p1
+  %p1.next = getelementptr float, ptr %p1, i64 1
+  %p2.next = getelementptr float, ptr %p2, i64 1
+  %c = icmp ne ptr %p1.next, %p1.end
+  br i1 %c, label %loop, label %exit
+
+exit:
+  ret void
+}