[LV] Fix scalar cost for tail predicated loops

[dmgreen]

Summary

When it comes to the scalar cost of any predicated block, the loop vectorizer by default regards this predication as a sign that it is looking at an if-conversion and divides the scalar cost of the block by 2, assuming it would only be executed half the time. This however makes no sense if the predication has been introduced to tail predicate the loop.

[fhahn]

Can you add the test separately and then just have the diff of the cost-model change in this patch?

llvm/test/Transforms/LoopVectorize/ARM/scalar-block-cost.ll

1

Are the lines actually auto-generated? Looks like they are just a subset of the debug output?

8

nit: are dse_local, no capture, read none local_unnamed_addr actually needed?

103

are all those attributes needed? can you limit them to the minimum required?

[anwel]

Thanks for the suggestions, I cleaned up the test so it looks a bit nicer now.

llvm/test/Transforms/LoopVectorize/ARM/scalar-block-cost.ll

1

That's true. A dumb copy-paste mistake, sorry about that and thanks for catching.

8

Not really, no.

103

I can, only the target-features are needed.

[samparker]

@dmgreen Since Anna is no longer with us, are you going to commander this?

[dmgreen]

Yep, that's the plan. It will need a number of other patches though. I think one for adding a cost to predicated blocks is important, along with the one for costing masked loads more correctly under MVE.

[samparker]

Okay, cheers.

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5930

might be worth adding a note here that we do intentionally not use LoopVectorizationCostModel::blockNeedsPredication, this also returns true if predication is required due to folding the tail by masking.

[dmgreen]

Thanks. We need to be careful with this as it has the potential to cause some regressions, especially as we here (in MVE land) make heavy use of predication nowadays. I am working through some of the details.

[skatkov]

@dmgreen While I'm not sure this patch is a real root cause of the loop vectorizer crash https://bugs.llvm.org/show_bug.cgi?id=48564 but revert of this patch eliminates the crash.
I would appreciate if you could look into the bug.

[dmgreen]

Will do. I expected some fallout from this one.

Thanks for the report. Ill try and take a look.

[skatkov]

In D86452#2465622, @dmgreen wrote:

Will do. I expected some fallout from this one.

Thanks for the report. Ill try and take a look.

Thanks a lot!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

for (Instruction &I : BB->instructionsWithoutDebug()) {
                         << " for VF " << VF << " For instruction: " << I
                         << '\n');
     }
 
     // If we are vectorizing a predicated block, it will have been
     // if-converted. This means that the block's instructions (aside from
     // stores and instructions that may divide by zero) will now be
     // unconditionally executed. For the scalar case, we may not always execute
-    // the predicated block. Thus, scale the block's cost by the probability of
-    // executing it.
-    if (VF == 1 && blockNeedsPredication(BB))
+    // the predicated block, if it is an if-else block. Thus, scale the block's
+    // cost by the probability of executing it.
+    if (VF == 1 && Legal->blockNeedsPredication(BB))
       BlockCost.first /= getReciprocalPredBlockProb();
 
     Cost.first += BlockCost.first;
     Cost.second |= BlockCost.second;
   }
 
   return Cost;
 }

llvm/test/Transforms/LoopVectorize/ARM/scalar-block-cost.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -loop-vectorize -debug-only=loop-vectorize -enable-arm-maskedgatscat -tail-predication=force-enabled -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK-COST,CHECK-COST-2
+; REQUIRES: asserts
+
+target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv8.1m.main-none-none-eabi"
+
+define dso_local void @pred_loop(i32* noalias nocapture readnone %off, i32* noalias nocapture readonly %data, i32* noalias nocapture %dst, i32 %n) local_unnamed_addr #0 {
+
+; CHECK-COST: LV: Found an estimated cost of 0 for VF 1 For instruction:   %i.09 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ]
+; CHECK-COST-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %add = add nuw nsw i32 %i.09, 1
+; CHECK-COST-NEXT: LV: Found an estimated cost of 0 for VF 1 For instruction:   %arrayidx = getelementptr inbounds i32, i32* %data, i32 %add
+; CHECK-COST-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %0 = load i32, i32* %arrayidx, align 4
+; CHECK-COST-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %add1 = add nsw i32 %0, 5
+; CHECK-COST-NEXT: LV: Found an estimated cost of 0 for VF 1 For instruction:   %arrayidx2 = getelementptr inbounds i32, i32* %dst, i32 %i.09
+; CHECK-COST-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   store i32 %add1, i32* %arrayidx2, align 4
+; CHECK-COST-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %exitcond.not = icmp eq i32 %add, %n
+; CHECK-COST-NEXT: LV: Found an estimated cost of 0 for VF 1 For instruction:   br i1 %exitcond.not, label %exit.loopexit, label %for.body
+; CHECK-COST-NEXT: LV: Scalar loop costs: 5.
+
+entry:
+  %cmp8 = icmp sgt i32 %n, 0
+  br i1 %cmp8, label %for.body, label %exit
+
+exit:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.09 = phi i32 [ %add, %for.body ], [ 0, %entry ]
+  %add = add nuw nsw i32 %i.09, 1
+  %arrayidx = getelementptr inbounds i32, i32* %data, i32 %add
+  %0 = load i32, i32* %arrayidx, align 4
+  %add1 = add nsw i32 %0, 5
+  %arrayidx2 = getelementptr inbounds i32, i32* %dst, i32 %i.09
+  store i32 %add1, i32* %arrayidx2, align 4
+  %exitcond.not = icmp eq i32 %add, %n
+  br i1 %exitcond.not, label %exit, label %for.body
+}
+
+define dso_local i32 @if_convert(i32* nocapture %a, i32* nocapture %b, i32 %start, i32 %end) local_unnamed_addr #0 {
+
+; CHECK-COST-2: LV: Found an estimated cost of 0 for VF 1 For instruction:   %i.032 = phi i32 [ %inc, %if.end ], [ %start, %for.body.preheader ]
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 0 for VF 1 For instruction:   %arrayidx = getelementptr inbounds i32, i32* %a, i32 %i.032
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %0 = load i32, i32* %arrayidx, align 4
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 0 for VF 1 For instruction:   %arrayidx2 = getelementptr inbounds i32, i32* %b, i32 %i.032
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %1 = load i32, i32* %arrayidx2, align 4
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %cmp3 = icmp sgt i32 %0, %1
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 0 for VF 1 For instruction:   br i1 %cmp3, label %if.then, label %if.end
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %mul = mul nsw i32 %0, 5
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %add = add nsw i32 %mul, 3
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 0 for VF 1 For instruction:   %factor = shl i32 %add, 1
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %sub = sub i32 %0, %1
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %add7 = add i32 %sub, %factor
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   store i32 %add7, i32* %arrayidx2, align 4
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 0 for VF 1 For instruction:   br label %if.end
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 0 for VF 1 For instruction:   %k.0 = phi i32 [ %add, %if.then ], [ %0, %for.body ]
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   store i32 %k.0, i32* %arrayidx, align 4
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %inc = add nsw i32 %i.032, 1
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 1 for VF 1 For instruction:   %exitcond.not = icmp eq i32 %inc, %end
+; CHECK-COST-2-NEXT: LV: Found an estimated cost of 0 for VF 1 For instruction:   br i1 %exitcond.not, label %for.cond.cleanup.loopexit, label %for.body
+; CHECK-COST-2-NEXT: LV: Scalar loop costs: 8.
+
+entry:
+  %cmp31 = icmp slt i32 %start, %end
+  br i1 %cmp31, label %for.body.preheader, label %for.cond.cleanup
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.cond.cleanup.loopexit:                        ; preds = %if.end
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
+  ret i32 undef
+
+for.body:                                         ; preds = %for.body.preheader, %if.end
+  %i.032 = phi i32 [ %inc, %if.end ], [ %start, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i32 %i.032
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %b, i32 %i.032
+  %1 = load i32, i32* %arrayidx2, align 4
+  %cmp3 = icmp sgt i32 %0, %1
+  br i1 %cmp3, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body
+  %mul = mul nsw i32 %0, 5
+  %add = add nsw i32 %mul, 3
+  %factor = shl i32 %add, 1
+  %sub = sub i32 %0, %1
+  %add7 = add i32 %sub, %factor
+  store i32 %add7, i32* %arrayidx2, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.body
+  %k.0 = phi i32 [ %add, %if.then ], [ %0, %for.body ]
+  store i32 %k.0, i32* %arrayidx, align 4
+  %inc = add nsw i32 %i.032, 1
+  %exitcond.not = icmp eq i32 %inc, %end
+  br i1 %exitcond.not, label %for.cond.cleanup.loopexit, label %for.body
+}
+
+
+attributes #0 = { nofree norecurse nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="true" "no-jump-tables"="false" "no-nans-fp-math"="true" "no-signed-zeros-fp-math"="true" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="generic" "target-features"="+armv8.1-m.main,+dsp,+fp-armv8d16sp,+fp16,+fullfp16,+hwdiv,+lob,+mve,+mve.fp,+ras,+strict-align,+thumb-mode,+vfp2sp,+vfp3d16sp,+vfp4d16sp" "unsafe-fp-math"="true" "use-soft-float"="false" }