[LoopFlatten] Simplify loops so that the pass can operate on unsimplified loops.

[stelios-arm]

Summary

The loop flattening pass requires loops to be in simplified form. If the
loops are not in simplified form, the pass cannot operate. This patch
simplifies all loops before flattening. As a result, all loops will be
simplified regardless of whether anything ends up being flattened.

This change was inspired by observing a certain loop that was not flatten
because the loops were not in simplified form. This loop is added as a
test to verify that it is now flattened.

[dmgreen]

It looks like Loop Flattening required LCSSA too. Can we make sure it runs formLCSSARecursively as well?

[fhahn]

As a result, all loops will be simplified regardless of whether anything ends up being flattened.

Not sure if we should simplify loops where there's nothing to flatten, e.g. loops that are not nested?

llvm/test/Transforms/LoopFlatten/loop-flatten-simplify-cfg.ll

6

Personally I do not think this line here is helpful. Options change, the bisect limit can change and so on, making it unlikely that the IR can be reproduced in a few years....

The IR test itself could be a bit simplified to make it slightly easier to read (e.g. use the same sized type for all values, so no extra zext/sext are needed.

That way, there should be no need to add a C reference, because the IR is already quite simple.

[stelios-arm]

@dmgreen Will do.

@fhahn Makes sense. I will change it to simplify loops that contain inner loops.

Thanks for the comments!

llvm/test/Transforms/LoopFlatten/loop-flatten-simplify-cfg.ll

6

I see, I will update the test as suggested. Thanks!

[stelios-arm]

Addressed the comments.

[dmgreen]

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

689

Maybe use if (L->isInnermost()) continue;?
That would keep the indentation down too, which llvm usually prefers.

[stelios-arm]

Addressed the comment of @dmgreen.

[dmgreen]

Thanks. LGTM

[fhahn]

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

692

Would it not be more natural to do that directly in the main loop in Flatten() rather than duplicating the loop?

[stelios-arm]

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

692

Oh yes, I missed that.

[dmgreen]

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

692

I'm not sure that's better. It would mean that the old pass manager duplicates the simplification/lcssa forming that it has already done through the pass dependencies. Put here it is only called once for the entire loop nest.

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

 PreservedAnalyses LoopFlattenPass::run(Function &F,
                                        FunctionAnalysisManager &AM) {
   auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
   auto *LI = &AM.getResult<LoopAnalysis>(F);
   auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
   auto *AC = &AM.getResult<AssumptionAnalysis>(F);
   auto *TTI = &AM.getResult<TargetIRAnalysis>(F);
 
-  if (!Flatten(DT, LI, SE, AC, TTI))
+  bool Changed = false;
+
+  // The loop flattening pass requires loops to be
+  // in simplified form, and also needs LCSSA. Running
+  // this pass will simplify all loops that contain inner loops,
+  // regardless of whether anything ends up being flattened.
+  for (const auto &L : *LI) {
+    if (L->isInnermost())
+      continue;
+    Changed |=
+        simplifyLoop(L, DT, LI, SE, AC, nullptr, false /* PreserveLCSSA */);
+    Changed |= formLCSSARecursively(*L, *DT, LI, SE);
+  }
+
+  Changed |= Flatten(DT, LI, SE, AC, TTI);
+
+  if (!Changed)
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();
 }
 
 namespace {
 class LoopFlattenLegacyPass : public FunctionPass {
 public:

llvm/test/Transforms/LoopFlatten/loop-flatten-simplify-cfg.ll

+;; This test was created to ensure that the LoopFlatten pass can
+;; operate on loops that are not in simplified form before applying the pass.
+
+; RUN: opt < %s -S -loop-flatten  -simplifycfg -verify-loop-info -verify-dom-info -verify-scev -verify | FileCheck %s
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+
+define void @test(i64 %N, i64* %A, i64 %val) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[N:%.*]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[FOR_END:%.*]], label [[FOR_COND_PREHEADER_PREHEADER:%.*]]
+; CHECK:       for.cond.preheader.preheader:
+; CHECK-NEXT:    [[FLATTEN_TRIPCOUNT:%.*]] = mul i64 [[N]], [[N]]
+; CHECK-NEXT:    br label [[FOR_COND_PREHEADER:%.*]]
+; CHECK:       for.cond.preheader:
+; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[INC6:%.*]], [[FOR_COND_PREHEADER]] ], [ 0, [[FOR_COND_PREHEADER_PREHEADER]] ]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[I]], [[N]]
+; CHECK-NEXT:    [[ADD:%.*]] = add i64 0, [[MUL]]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[A:%.*]], i64 [[I]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i64, i64* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[ADD4:%.*]] = add nsw i64 [[TMP0]], [[VAL:%.*]]
+; CHECK-NEXT:    store i64 [[ADD4]], i64* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[INC:%.*]] = add nuw nsw i64 0, 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[INC]], [[N]]
+; CHECK-NEXT:    [[INC6]] = add nuw nsw i64 [[I]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[INC6]], [[FLATTEN_TRIPCOUNT]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_COND_PREHEADER]], label [[FOR_END]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp.not = icmp eq i64 %N, 0
+  br i1 %cmp.not, label %for.end, label %for.cond.preheader
+
+for.cond.preheader:
+  %i= phi i64 [ %inc6, %for.cond.for.inc_crit_edge ], [ 0, %entry ]
+  %mul = mul i64 %i, %N
+  br label %for.body
+
+for.body:
+  %j = phi i64 [ 0, %for.cond.preheader ], [ %inc, %for.body ]
+  %add = add i64 %j, %mul
+  %arrayidx = getelementptr inbounds i64, i64* %A, i64 %add
+  %0 = load i64, i64* %arrayidx, align 4
+  %add4 = add nsw i64 %0, %val
+  store i64 %add4, i64* %arrayidx, align 4
+  %inc = add nuw nsw i64 %j, 1
+  %cmp2 = icmp ult i64 %inc, %N
+  br i1 %cmp2, label %for.body, label %for.cond.for.inc_crit_edge
+
+for.cond.for.inc_crit_edge:
+  %inc6 = add nuw nsw i64 %i, 1
+  %cmp = icmp ult i64 %inc6, %N
+  br i1 %cmp, label %for.cond.preheader, label %for.end
+
+for.end:
+  ret void
+}