[LAA] Handle forked pointers with add/sub instructions

[huntergr]

Summary

Handle cases where a forked pointer has an add or sub instruction before reaching a select.

Tests were precommitted in rG0a715c114686

[paulwalker-arm]

I'm not hugely familiar with this code but I can see you're following the same idiom as used for Instruction::GetElementPtr which is just a special type of add so this patch looks good to me. Please remember to run clang-format before landing the patch.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

930–931

This looks to break the 80 character line length rules.

[fhahn]

LGTM, thanks! Please format the diff with clang-format before committing.

It would probably be also good to add at least one test where the pointer bounds are expanded (e.g. with LV) and the ops require freezing.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

827

Are you planning to support additional bin-ops in the future here? Or could this be moved to the scope in the corresponding switch case?

927

Not directly related to this patch, but given that we return after the switch it might be simpler to follow if we would just return instead of break in the switch?

[huntergr]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

827

I plan to support multiply in a future patch; it seems to need a little more work that add and sub.

Though there's plenty of codebases which can benefit from this work, one of the main cases we considered is https://github.com/HydroBench/Hydro/ -- specifically the loops in riemann.c

There's a few other problems I need to deal with for hydro (openmp runtime functions not being annotated by default, lack of vectorization using masked functions) before I can finish off the rest of this work. But there's at least a few more operations to add to this switch statement -- multiplies as mentioned above, zero and sign extends, and phis used for non-SAR purposes in the loop (e.g. if-then)

927

Yes, I'll add that in a follow-on patch along with the extra test.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

findForkedSCEVs(ScalarEvolution *SE, const Loop *L, Value *Ptr,
   }
 
   Depth--;
 
   auto UndefPoisonCheck = [](std::pair<const SCEV *, bool> S) -> bool {
     return S.second;
   };
 
+  auto GetBinOpExpr = [&SE](unsigned Opcode, const SCEV* L, const SCEV* R) {
+    switch (Opcode) {
+    case Instruction::Add:
+      return SE->getAddExpr(L, R);
+    case Instruction::Sub:
+      return SE->getMinusSCEV(L, R);
+    default:
+      llvm_unreachable("Unexpected binary operator when walking ForkedPtrs");
+    }
+  };
+
   Instruction *I = cast<Instruction>(Ptr);
   unsigned Opcode = I->getOpcode();
   switch (Opcode) {
   case Instruction::GetElementPtr: {
     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
     Type *SourceTy = GEP->getSourceElementType();
     // We only handle base + single offset GEPs here for now.
     // Not dealing with preexisting gathers yet, so no vectors.
case Instruction::Select: {
     if (ChildScevs.size() == 2) {
       ScevList.push_back(ChildScevs[0]);
       ScevList.push_back(ChildScevs[1]);
     } else
       ScevList.push_back(
           std::make_pair(Scev, !isGuaranteedNotToBeUndefOrPoison(Ptr)));
     break;
   }
+  case Instruction::Add:
+  case Instruction::Sub: {
+    SmallVector<std::pair<const SCEV*, bool>> LScevs;
+    SmallVector<std::pair<const SCEV*, bool>> RScevs;
+    findForkedSCEVs(SE, L, I->getOperand(0), LScevs, Depth);
+    findForkedSCEVs(SE, L, I->getOperand(1), RScevs, Depth);
+
+    // See if we need to freeze our fork...
+    bool NeedsFreeze = any_of(LScevs, UndefPoisonCheck) ||
+                       any_of(RScevs, UndefPoisonCheck);
+
+    // Check that we only have a single fork, on either the left or right side.
+    // Copy the SCEV across for the one without a fork in order to generate
+    // the full SCEV for both sides of the BinOp.
+    if (LScevs.size() == 2 && RScevs.size() == 1)
+      RScevs.push_back(RScevs[0]);
+    else if (RScevs.size() == 2 && LScevs.size() == 1)
+      LScevs.push_back(LScevs[0]);
+    else {
+      ScevList.push_back(std::make_pair(Scev, NeedsFreeze));
+      break;
+    }
+
+    ScevList.push_back(std::make_pair(GetBinOpExpr(Opcode, LScevs[0].first, RScevs[0].first), NeedsFreeze));
+    ScevList.push_back(std::make_pair(GetBinOpExpr(Opcode, LScevs[1].first, RScevs[1].first), NeedsFreeze));
+    break;
+  }
   default:
     // Just return the current SCEV if we haven't handled the instruction yet.
     LLVM_DEBUG(dbgs() << "ForkedPtr unhandled instruction: " << *I << "\n");
     ScevList.push_back(
         std::make_pair(Scev, !isGuaranteedNotToBeUndefOrPoison(Ptr)));
     break;
   }
 

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

for.body:                                         ; preds = %entry, %for.body
   %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
   store float %2, ptr %arrayidx5, align 4
   %exitcond.not = icmp eq i64 %indvars.iv.next, 100
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 }
 
 ; CHECK-LABEL: function 'forked_ptrs_add_to_offset'
 ; CHECK-NEXT:  for.body:
-; CHECK-NEXT:    Report: cannot identify array bounds
+; CHECK-NEXT:    Memory dependences are safe with run-time checks
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:    Run-time memory checks:
+; CHECK-NEXT:    Check 0:
+; CHECK-NEXT:      Comparing group ([[G1:.+]]):
+; CHECK-NEXT:        %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
+; CHECK-NEXT:      Against group ([[G2:.+]]):
+; CHECK-NEXT:        %arrayidx = getelementptr inbounds i32, ptr %Preds, i64 %indvars.iv
+; CHECK-NEXT:    Check 1:
+; CHECK-NEXT:      Comparing group ([[G1:.+]]):
+; CHECK-NEXT:        %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
+; CHECK-NEXT:      Against group ([[G3:.+]]):
+; CHECK-NEXT:        %arrayidx3 = getelementptr inbounds float, ptr %Base, i64 %offset
+; CHECK-NEXT:        %arrayidx3 = getelementptr inbounds float, ptr %Base, i64 %offset
 ; CHECK-NEXT:    Grouped accesses:
+; CHECK-NEXT:      Group [[G1]]:
+; CHECK-NEXT:        (Low: %Dest High: (400 + %Dest))
+; CHECK-NEXT:          Member: {%Dest,+,4}<nuw><%for.body>
+; CHECK-NEXT:      Group [[G2]]:
+; CHECK-NEXT:        (Low: %Preds High: (400 + %Preds))
+; CHECK-NEXT:          Member: {%Preds,+,4}<nuw><%for.body>
+; CHECK-NEXT:      Group [[G3]]:
+; CHECK-NEXT:        (Low: ((4 * %extra_offset) + %Base) High: (404 + (4 * %extra_offset) + %Base))
+; CHECK-NEXT:          Member: {(4 + (4 * %extra_offset) + %Base),+,4}<%for.body>
+; CHECK-NEXT:          Member: {((4 * %extra_offset) + %Base),+,4}<%for.body>
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Expressions re-written:
 
 define dso_local void @forked_ptrs_add_to_offset(ptr nocapture readonly %Base, ptr nocapture %Dest, ptr nocapture readonly %Preds, i64 %extra_offset) {
 entry:
for.body:                                         ; preds = %entry, %for.body
   %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
   store float %1, ptr %arrayidx5, align 4
   %exitcond.not = icmp eq i64 %indvars.iv.next, 100
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 }
 
 ; CHECK-LABEL: function 'forked_ptrs_sub_from_offset'
 ; CHECK-NEXT:  for.body:
-; CHECK-NEXT:    Report: cannot identify array bounds
+; CHECK-NEXT:    Memory dependences are safe with run-time checks
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:    Run-time memory checks:
+; CHECK-NEXT:    Check 0:
+; CHECK-NEXT:      Comparing group ([[G1:.+]]):
+; CHECK-NEXT:        %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
+; CHECK-NEXT:      Against group ([[G2:.+]]):
+; CHECK-NEXT:        %arrayidx = getelementptr inbounds i32, ptr %Preds, i64 %indvars.iv
+; CHECK-NEXT:    Check 1:
+; CHECK-NEXT:      Comparing group ([[G1]]):
+; CHECK-NEXT:        %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
+; CHECK-NEXT:      Against group ([[G3:.+]]):
+; CHECK-NEXT:        %arrayidx3 = getelementptr inbounds float, ptr %Base, i64 %offset
+; CHECK-NEXT:        %arrayidx3 = getelementptr inbounds float, ptr %Base, i64 %offset
 ; CHECK-NEXT:    Grouped accesses:
+; CHECK-NEXT:      Group [[G1]]:
+; CHECK-NEXT:        (Low: %Dest High: (400 + %Dest))
+; CHECK-NEXT:          Member: {%Dest,+,4}<nuw><%for.body>
+; CHECK-NEXT:      Group [[G2]]:
+; CHECK-NEXT:        (Low: %Preds High: (400 + %Preds))
+; CHECK-NEXT:          Member: {%Preds,+,4}<nuw><%for.body>
+; CHECK-NEXT:      Group [[G3]]:
+; CHECK-NEXT:        (Low: ((-4 * %extra_offset) + %Base) High: (404 + (-4 * %extra_offset) + %Base))
+; CHECK-NEXT:          Member: {(4 + (-4 * %extra_offset) + %Base),+,4}<%for.body>
+; CHECK-NEXT:          Member: {((-4 * %extra_offset) + %Base),+,4}<%for.body>
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Expressions re-written:
 
 define dso_local void @forked_ptrs_sub_from_offset(ptr nocapture readonly %Base, ptr nocapture %Dest, ptr nocapture readonly %Preds, i64 %extra_offset) {
 entry:
for.body:                                         ; preds = %entry, %for.body
   %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
   store float %1, ptr %arrayidx5, align 4
   %exitcond.not = icmp eq i64 %indvars.iv.next, 100
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 }
 
 ; CHECK-LABEL: function 'forked_ptrs_add_sub_offset'
 ; CHECK-NEXT:  for.body:
-; CHECK-NEXT:    Report: cannot identify array bounds
+; CHECK-NEXT:    Memory dependences are safe with run-time checks
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:    Run-time memory checks:
+; CHECK-NEXT:    Check 0:
+; CHECK-NEXT:      Comparing group ([[G1:.+]]):
+; CHECK-NEXT:        %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
+; CHECK-NEXT:      Against group ([[G2:.+]]):
+; CHECK-NEXT:        %arrayidx = getelementptr inbounds i32, ptr %Preds, i64 %indvars.iv
+; CHECK-NEXT:    Check 1:
+; CHECK-NEXT:      Comparing group ([[G1:.+]]):
+; CHECK-NEXT:        %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
+; CHECK-NEXT:      Against group ([[G3:.+]]):
+; CHECK-NEXT:        %arrayidx3 = getelementptr inbounds float, ptr %Base, i64 %offset
+; CHECK-NEXT:        %arrayidx3 = getelementptr inbounds float, ptr %Base, i64 %offset
 ; CHECK-NEXT:    Grouped accesses:
+; CHECK-NEXT:      Group [[G1:.+]]:
+; CHECK-NEXT:        (Low: %Dest High: (400 + %Dest))
+; CHECK-NEXT:          Member: {%Dest,+,4}<nuw><%for.body>
+; CHECK-NEXT:      Group [[G2]]:
+; CHECK-NEXT:        (Low: %Preds High: (400 + %Preds))
+; CHECK-NEXT:          Member: {%Preds,+,4}<nuw><%for.body>
+; CHECK-NEXT:      Group [[G3]]:
+; CHECK-NEXT:        (Low: ((4 * %to_add) + (-4 * %to_sub) + %Base) High: (404 + (4 * %to_add) + (-4 * %to_sub) + %Base))
+; CHECK-NEXT:          Member: {(4 + (4 * %to_add) + (-4 * %to_sub) + %Base),+,4}<%for.body>
+; CHECK-NEXT:          Member: {((4 * %to_add) + (-4 * %to_sub) + %Base),+,4}<%for.body>
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Expressions re-written:
 
 define dso_local void @forked_ptrs_add_sub_offset(ptr nocapture readonly %Base, ptr nocapture %Dest, ptr nocapture readonly %Preds, i64 %to_add, i64 %to_sub) {
 entry: