[LoopRotation] Allow loop header duplication if vectorization is forced

[fhahn]

Summary

-Oz normally does not allow loop header duplication so this loop wouldn't be
vectorized. However the vectorization pragma should override this and allow
for loop rotation.

rdar://problem/49281061

[fhahn]

This makes sense to me, given that loops with bottom checks are a precondition for LV. I think it would be good to also update the section about llvm.loop.vectorize.enable in LangRef to say it might also enable transformations like LoopRotate, in preparation for LV.

In case LV fails to vectorize the loop, it might be a bit surprising the loop has been rotated. But the way things are structured at the moment, there's nothing we can do about that (we cannot tell in LoopRotate if LV will be able to vectorize). By documenting that behavior, we can push the responsibility for that to the user. Maybe a remark in LoopRotate would be helpful to indicate that we only rotated because of the metadata.

Also adding Michael, as he worked on loop related metadata recently.

lib/Transforms/Scalar/LoopRotation.cpp

119

Might be worth a comment why isForcedVectorize overrides the behavior here.

test/Transforms/LoopVectorize/AArch64/Oz-and-forced-vectorize.ll

1

Could you limit the test case to running loop-rotate? The tests for LV should already be sufficient to check the transformed case. (same for second test)

59

All metadata except this one can be stripped I think. (same for second test)

[anemet]

In D59832#1444244, @fhahn wrote:

This makes sense to me, given that loops with bottom checks are a precondition for LV. I think it would be good to also update the section about llvm.loop.vectorize.enable in LangRef to say it might also enable transformations like LoopRotate, in preparation for LV.

In case LV fails to vectorize the loop, it might be a bit surprising the loop has been rotated. But the way things are structured at the moment, there's nothing we can do about that (we cannot tell in LoopRotate if LV will be able to vectorize). By documenting that behavior, we can push the responsibility for that to the user. Maybe a remark in LoopRotate would be helpful to indicate that we only rotated because of the metadata.

I think the picture is even simpler in this case. The user has asked for an optimization. If we can't deliver we issue a warning (-Wpass-failed). So the user has sufficient information to see that something went wrong. But yes a loop rotation remark makes sense! especially mentioning that we did it in preparation for forced vectorization.

Also adding Michael, as he worked on loop related metadata recently.

test/Transforms/LoopVectorize/AArch64/Oz-and-forced-vectorize.ll

1

I don't think so. There is no other way to get sizelevel=2 activated for opt. You either run the entire -Oz pipeline or you run specific tests with sizelevel=0.

59

I kept it in to get the *warning* with proper line info for failed user-requested optimization. I can drop if you don't think that is useful. I liked it because it completely captured the user experience that this test came from.

I can check for the actual diagnostics to make this less subtle.

[fhahn]

test/Transforms/LoopVectorize/AArch64/Oz-and-forced-vectorize.ll

1

Argh, that's unfortunate :( . I thought it just respects the minsize attribute.......

[Meinersbur]

This might be a more general problem, other passes might expect a normalized form as well, such as UnrollAndJam and LoopDistribute.

For LoopVectorizer, I am somewhat surprised. It calls simplifyLoop itself (instead of relying on LoopSimplifyPass). Could the same be done for LoopRotation?

lib/Transforms/Scalar/LoopRotation.cpp

60

Consider using hasVectorizeTransformation in LoopUtils.h. I added it to make determining whether a pragma is added consistent between passes.

test/Transforms/LoopVectorize/AArch64/Oz-and-unforced-vectorize.ll

3–4

There is no llvm.loop.vectorize.enable metadata here, so without -vectorize-loops option, it would not be vectorized anyway.

27

I don't think we need to regression-test that we do not vectorize. If LoopVectorize one day manages to vectorize unrotated loop, it's a good thing, not a regression.

Btw, since it's the same content, you could instead add another RUN: line to the other test.

[fhahn]

In D59832#1444555, @Meinersbur wrote:

This might be a more general problem, other passes might expect a normalized form as well, such as UnrollAndJam and LoopDistribute.

For LoopVectorizer, I am somewhat surprised. It calls simplifyLoop itself (instead of relying on LoopSimplifyPass). Could the same be done for LoopRotation?

I guess it could, but the underlying problem is still the same: as things are currently structured, we have to rotate before we know if vectorization is legal and cannot go back if it is not. Potentially, VPlan allows this sort of thing, by doing those transforms on a separate representation (VPlan IR)

[anemet]

In D59832#1444555, @Meinersbur wrote:

This might be a more general problem, other passes might expect a normalized form as well, such as UnrollAndJam and LoopDistribute.

For LoopVectorizer, I am somewhat surprised. It calls simplifyLoop itself (instead of relying on LoopSimplifyPass). Could the same be done for LoopRotation?

It felt that the decision belonged to LoopRotate. We make a profitability decision there (for -Oz loop rotate is a bad trade-off) which is inaccurate.

If you feel strongly about this I can explore rotating the loop in the vectorizer when I have a bit more time.

lib/Transforms/Scalar/LoopRotation.cpp

60

Nice, I didn't know about this. BTW, LoopDistribute was not updated to use hasDistributeTransformation.

test/Transforms/LoopVectorize/AArch64/Oz-and-unforced-vectorize.ll

27

I don't think we need to regression-test that we do not vectorize. If LoopVectorize one day manages to vectorize unrotated loop, it's a good thing, not a regression.

I like to have the negative tests as well but if you want I'll remove it.

Btw, since it's the same content, you could instead add another RUN: line to the other test.

Well, it's not the same content since it's missing the the forced-vectorize metadata. But perhaps I am not understanding the point you're trying to make.

[anemet]

lib/Transforms/Scalar/LoopRotation.cpp

60

@Meinersbur I am actually confused whether I should be checking for Enable or ForcedByUser. We only set Enable and not Forced if the vectorization width is requested via a pragma but I think that is an even stronger enforcement of vectorization. What is the logic here?

[Meinersbur]

In D59832#1444678, @anemet wrote:

If you feel strongly about this I can explore rotating the loop in the vectorizer when I have a bit more time.

No, this would go beyond fixing a bug.

lib/Transforms/Scalar/LoopRotation.cpp

60

I only changed UnrollAndJam to use it for now. How these decisions are made is surprisingly subtle and e.g. in case of LoopVectorizeHints, integrated within other decisions. I was not brave enough to put up reviews for this and risking changing behavior without a need. But I would be happy if new code uses it.

test/Transforms/LoopVectorize/AArch64/Oz-and-unforced-vectorize.ll

27

I like to have the negative tests as well but if you want I'll remove it.

I don't like them; they are fragile, require maintenance and check-llvm takes longer.

Well, it's not the same content since it's missing the the forced-vectorize metadata.

I was assuming the missing llvm.loop.vectorize.enable metadata was a mistake. Without it, LoopVectorize won't do anything, even if it could vectorize the loop (There is a difference in how clang and opt initialize the PassManagerBuilder).

An excellent example of how fragile this kind of test is.

[fhahn]

I'm taking this over, after checking with @anemet offline.

[fhahn]

Rebased, updated to use hasVectorizeTransformation as suggested, removed negative test (existing loop rotation tests should cover that already) and removed unnecessary dbg & tbaa metadata from test.

Ping :)

[jdoerfert]

Looks reasonable to me, on nit. Someone else?

llvm/lib/Transforms/Scalar/LoopRotation.cpp

123 ↗

(On Diff #300612)

Nit: Can we make this a standalone variable, they are free ;)

[lebedev.ri]

In D59832#2353599, @jdoerfert wrote:

Looks reasonable to me, on nit. Someone else?

Seems fine to me too.

[Meinersbur]

LGTM.

There is an inline comment on the previous diff that I think was never submitted; It does not apply to the latest diff as it already uses TM_ForcedByUser. I don't delete is since is might still be interesting.

lib/Transforms/Scalar/LoopRotation.cpp

60

ForcedByUser follows llvm.loop.vectorize.enable, i.e. whether #pragma clang loop vectorize(enable) is present. Other metadata such as llvm.loop.vectorize.width logically are only used in case the vectorizer decides to transform a loop, without explicitly enabling it. Other passes like LoopUnroll and LoopUnrollAndJam enable themselves even if only llvm.loop.unroll.count is present.

LoopVectorizationHints::getForce() only checks the llvm.loop.vectorize.enable setting to override heuristicts, so I suggest to use ForcedByUser.

This is what I mean by "subtle".

[fhahn]

lib/Transforms/Scalar/LoopRotation.cpp

60

That's an excellent point. I think after D66290 Clang also generates vectorize.enable when just the width pragma is specified, so for code generated by clang, this issue should not exist now, but may for other frontends.

119

I added a variable similar to what we have in the new pm version in the committed patch,

[fhahn]

Thanks!

[Meinersbur]

lib/Transforms/Scalar/LoopRotation.cpp

60

Yes, some consistency would be nice. IMHO that vectorize_width implicitly forces vectorization is a front-end interpretation. vectorize.width without vectorize.enable has a valid interpretation "if you are vectorizing, use this SIMD width".

lib/Transforms/Scalar/LoopRotation.cpp

if (!Changed)
     return PreservedAnalyses::all();
 
   if (AR.MSSA && VerifyMemorySSA)
     AR.MSSA->verifyMemorySSA();
 
   return getLoopPassPreservedAnalyses();
 }
 
+static bool isForcedVectorize(Loop *L) {
+  Optional<const MDOperand *> Value =
+      findStringMetadataForLoop(L, "llvm.loop.vectorize.enable");
+  if (!Value)
+    return false;
+
+  const MDOperand *Op = *Value;
+  assert(Op && mdconst::hasa<ConstantInt>(*Op) && "invalid metadata");
+  return mdconst::extract<ConstantInt>(*Op)->getZExtValue();
+}
+
 namespace {
 
 class LoopRotateLegacyPass : public LoopPass {
   unsigned MaxHeaderSize;
 
 public:
   static char ID; // Pass ID, replacement for typeid
   LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1) : LoopPass(ID) {
bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     auto *SE = SEWP ? &SEWP->getSE() : nullptr;
     const SimplifyQuery SQ = getBestSimplifyQuery(*this, F);
     Optional<MemorySSAUpdater> MSSAU;
     if (EnableMSSALoopDependency) {
       MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
       MSSAU = MemorySSAUpdater(MSSA);
     }
-    return LoopRotation(L, LI, TTI, AC, DT, SE,
-                        MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, SQ,
-                        false, MaxHeaderSize, false);
+
+    return LoopRotation(
+        L, LI, TTI, AC, DT, SE, MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
+        SQ, false,
+        isForcedVectorize(L) ? DefaultRotationThreshold : MaxHeaderSize, false);
   }
 };
 }
 
 char LoopRotateLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)

test/Transforms/LoopVectorize/AArch64/Oz-and-forced-vectorize.ll

+; RUN: opt -Oz -S < %s | FileCheck %s
+
+; If vectorization is forced then -Oz should be overriden to disable loop
+; header duplication in loop rotation.
+
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+target triple = "arm64-apple-ios5.0.0"
+
+define void @foo(float* noalias nocapture %ptrA, float* noalias nocapture readonly %ptrB, i64 %size) {
+entry:
+  br label %for.cond, !dbg !10
+
+for.cond:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ], !dbg !11
+  %exitcond = icmp eq i64 %indvars.iv, %size, !dbg !12
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body, !dbg !13
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  ret void, !dbg !14
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds float, float* %ptrB, i64 %indvars.iv, !dbg !15
+  %0 = load float, float* %arrayidx, align 4, !dbg !15, !tbaa !16
+  %arrayidx2 = getelementptr inbounds float, float* %ptrA, i64 %indvars.iv, !dbg !20
+  %1 = load float, float* %arrayidx2, align 4, !dbg !21, !tbaa !16
+  %mul3 = fmul float %0, %1, !dbg !21
+; CHECK: fmul <4 x float>
+  store float %mul3, float* %arrayidx2, align 4, !dbg !21, !tbaa !16
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1, !dbg !22
+  br label %for.cond, !dbg !13, !llvm.loop !23
+}
+
+!llvm.module.flags = !{!3, !4, !5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: NoDebug, enums: !2, nameTableKind: GNU)
+!1 = !DIFile(filename: "/tmp/s.c", directory: "/tmp")
+!2 = !{}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = !{i32 1, !"wchar_size", i32 4}
+!5 = !{i32 7, !"PIC Level", i32 2}
+!7 = distinct !DISubprogram(name: "foo", scope: !8, file: !8, line: 3, type: !9, scopeLine: 5, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!8 = !DIFile(filename: "/tmp/s.c", directory: "")
+!9 = !DISubroutineType(types: !2)
+!10 = !DILocation(line: 13, column: 14, scope: !7)
+!11 = !DILocation(line: 0, scope: !7)
+!12 = !DILocation(line: 13, column: 36, scope: !7)
+!13 = !DILocation(line: 13, column: 9, scope: !7)
+!14 = !DILocation(line: 18, column: 1, scope: !7)
+!15 = !DILocation(line: 15, column: 33, scope: !7)
+!16 = !{!17, !17, i64 0}
+!17 = !{!"float", !18, i64 0}
+!18 = !{!"omnipotent char", !19, i64 0}
+!19 = !{!"Simple C/C++ TBAA"}
+!20 = !DILocation(line: 15, column: 13, scope: !7)
+!21 = !DILocation(line: 15, column: 30, scope: !7)
+!22 = !DILocation(line: 13, column: 44, scope: !7)
+!23 = distinct !{!23, !13, !24, !25}
+!24 = !DILocation(line: 16, column: 9, scope: !7)
+!25 = !{!"llvm.loop.vectorize.enable", i1 true}

test/Transforms/LoopVectorize/AArch64/Oz-and-unforced-vectorize.ll

+; RUN: opt -Oz -S < %s | FileCheck %s
+
+; -Oz does not allow for loop header duplication so we can't vectorize this.
+; See Oz-and-unforced-vectorize.ll.
+
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+target triple = "arm64-apple-ios5.0.0"
+
+define void @foo(float* noalias nocapture %ptrA, float* noalias nocapture readonly %ptrB, i64 %size) {
+entry:
+  br label %for.cond, !dbg !10
+
+for.cond:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ], !dbg !11
+  %exitcond = icmp eq i64 %indvars.iv, %size, !dbg !12
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body, !dbg !13
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  ret void, !dbg !14
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds float, float* %ptrB, i64 %indvars.iv, !dbg !15
+  %0 = load float, float* %arrayidx, align 4, !dbg !15, !tbaa !16
+  %arrayidx2 = getelementptr inbounds float, float* %ptrA, i64 %indvars.iv, !dbg !20
+  %1 = load float, float* %arrayidx2, align 4, !dbg !21, !tbaa !16
+  %mul3 = fmul float %0, %1, !dbg !21
+; CHECK-NOT: fmul <4 x float>
+  store float %mul3, float* %arrayidx2, align 4, !dbg !21, !tbaa !16
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1, !dbg !22
+  br label %for.cond, !dbg !13, !llvm.loop !23
+}
+
+!llvm.module.flags = !{!3, !4, !5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: NoDebug, enums: !2, nameTableKind: GNU)
+!1 = !DIFile(filename: "/tmp/s.c", directory: "/tmp")
+!2 = !{}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = !{i32 1, !"wchar_size", i32 4}
+!5 = !{i32 7, !"PIC Level", i32 2}
+!7 = distinct !DISubprogram(name: "foo", scope: !8, file: !8, line: 3, type: !9, scopeLine: 5, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!8 = !DIFile(filename: "/tmp/s.c", directory: "")
+!9 = !DISubroutineType(types: !2)
+!10 = !DILocation(line: 13, column: 14, scope: !7)
+!11 = !DILocation(line: 0, scope: !7)
+!12 = !DILocation(line: 13, column: 36, scope: !7)
+!13 = !DILocation(line: 13, column: 9, scope: !7)
+!14 = !DILocation(line: 18, column: 1, scope: !7)
+!15 = !DILocation(line: 15, column: 33, scope: !7)
+!16 = !{!17, !17, i64 0}
+!17 = !{!"float", !18, i64 0}
+!18 = !{!"omnipotent char", !19, i64 0}
+!19 = !{!"Simple C/C++ TBAA"}
+!20 = !DILocation(line: 15, column: 13, scope: !7)
+!21 = !DILocation(line: 15, column: 30, scope: !7)
+!22 = !DILocation(line: 13, column: 44, scope: !7)
+!23 = distinct !{!23, !13, !24}
+!24 = !DILocation(line: 16, column: 9, scope: !7)