[IndVars] Preserve LCSSA on inner loops

[sanjoy]

Summary

Currently IndVarSimplify breaks LCSSA on inner loops even though it says
it preserves LCSSA. Fix this by running formLCSSARecursively
explictly on the inner loops.

Fixes PR25578 and PR24804.

There are couple of ways we can make this logic more frugal if needed:

• Inspect only newly inserted / moved instructions for possible LCSSA breakage
• Teach SCEVExpander to not break LCSSA for any loop in the loop nest

Test cases courtesy of David Majnemer and Michael Zolotukhin!

[hfinkel]

LGTM.

lib/Transforms/Scalar/IndVarSimplify.cpp

2185

This does not seem to be documented explicitly anywhere, could you also add some comments in SCEVExpander's header file to this effect as well.

[sanjoy]

Hi Hal,

Thank you for the review.

After taking a closer look I think I've found the two specific things that need to be fixed to have -indvars preserve LCSSA for the entire loop nest. Given that the two fixes are not very invasive, I think brute-forcing LCSSA after -indvars (i.e. this patch) is not the right fix. I have the two new fixes up for review at D15058 and D15059.

The comment I made about SCEVExpander was also misleading -- at least in the breaking test cases, SCEVExpander does not break LCSSA for the inner loops, but it is -indvars that is the problem.

I'm abandoning this revision for now in favor of D15058 and D15059.

lib/Transforms/Scalar/IndVarSimplify.cpp

 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "indvars"
 
 STATISTIC(NumWidened     , "Number of indvars widened");
 STATISTIC(NumReplaced    , "Number of exit values replaced");
 STATISTIC(NumLFTR        , "Number of loop exit tests replaced");
#endif
   // The Rewriter may not be used from this point on.
 
   // Loop-invariant instructions in the preheader that aren't used in the
   // loop may be sunk below the loop to reduce register pressure.
   sinkUnusedInvariants(L);
 
   // Clean up dead instructions.
   Changed |= DeleteDeadPHIs(L->getHeader(), TLI);
+
   // Check a post-condition.
   assert(L->isLCSSAForm(*DT) &&
          "Indvars did not leave the loop in lcssa form!");
 
+  // When expanding add recurrences for loop L, SCEVExpander can break LCSSA for
+  // loops inside it (i.e. L's children).
+  if (Changed)
+    for (Loop *SubLoop : L->getSubLoops())
+      formLCSSARecursively(*SubLoop, *DT, LI, SE);
+
   // Verify that LFTR, and any other change have not interfered with SCEV's
   // ability to compute trip count.
 #ifndef NDEBUG
   if (VerifyIndvars && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
     SE->forgetLoop(L);
     const SCEV *NewBECount = SE->getBackedgeTakenCount(L);
     if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) <
         SE->getTypeSizeInBits(NewBECount->getType()))

test/Transforms/IndVarSimplify/pr24804.ll

+; RUN: opt -indvars -loop-idiom -loop-deletion -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Checking for a crash
+
+define void @f(i32* %a) {
+; CHECK-LABEL: @f(
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %for.cond, %entry
+  %0 = phi i32 [ 0, %entry ], [ %add, %for.inc ], [ %0, %for.cond ]
+  %add = add nsw i32 %0, 1
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
+  br i1 undef, label %for.cond, label %for.inc
+
+for.inc:                                          ; preds = %for.cond
+  br i1 undef, label %for.cond, label %for.end
+
+for.end:                                          ; preds = %for.inc
+  ret void
+}

test/Transforms/IndVarSimplify/pr25578.ll

+; RUN: opt < %s -indvars -S | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+; CHECK-LABEL: @foo
+define void @foo() {
+entry:
+  br label %L1_header
+
+L1_header:
+  br label %L2_header
+
+; CHECK: L2_header:
+; CHECK: %[[INDVAR:.*]] = phi i64
+L2_header:
+  %i = phi i32 [ 0, %L1_header ], [ %i_next, %L2_latch ]
+  %i_prom = sext i32 %i to i64
+  br label %L3_header
+
+; CHECK: L3_header:
+; CHECK: %[[TRUNC:.*]] = trunc i64 %[[INDVAR]] to i32
+L3_header:
+  br i1 undef, label %L3_latch, label %L2_exiting_1
+
+L3_latch:
+  br i1 undef, label %L3_header, label %L2_exiting_2
+
+; CHECK: L2_exiting_1:
+; CHECK: %{{.*}} = phi i32 [ %[[TRUNC]], %L3_header ]
+L2_exiting_1:
+  br i1 undef, label %L2_latch, label %L1_latch
+
+; CHECK: L2_exiting_2:
+; CHECK: %{{.*}} = phi i32 [ %[[TRUNC]], %L3_latch ]
+L2_exiting_2:
+  br i1 undef, label %L2_latch, label %L1_latch
+
+L2_latch:
+  %i_next = add nsw i32 %i, 1
+  br label %L2_header
+
+L1_latch:
+  %i_lcssa = phi i32 [ %i, %L2_exiting_1 ], [ %i, %L2_exiting_2 ]
+  br i1 undef, label %exit, label %L1_header
+
+exit:
+  ret void
+}