[Polly] Add invalidation of the loop SCEVs after merge block generation

[mbdharan]

Summary

The SCEVs of loops surrounding the escape users of a merge blocks are forgotten, so that loop trip counts based on old values can revoked.

This fixes https://bugs.llvm.org//show_bug.cgi?id=32536

[Meinersbur]

Hi Baranidharan,

thank you for the patch. Could you please add a test case as well (e.g. the .ll file from llvm.org/PR32536, minimized as far as possible and a CHECK:-line for something that is relevant. e.g. that the %num.0 = phi i32 [ %add, %for.body15 ], [ 0, %for.cond13.pre_entry_bb ] is in the right position)

lib/CodeGen/BlockGenerators.cpp

784 ↗

(On Diff #98999)

Please add a newline before.

[mbdharan]

Add changes to reflect the comments.

[Meinersbur]

Hi Baranidharan,

the patch LGTM. An explanation into the doxygen of invalidateScalarEvolution about the added code and why it is there (like you explained in the summary) would be nice.

Do you have commit rights? If not, I'd commit for you.

lib/CodeGen/BlockGenerators.cpp

862 ↗

(On Diff #99758)

Nit: Dot at the end of sentence.

[mbdharan]

Hi @Meinersbur, Updated the diff to according comments.

I don't have commit rights, so you'd have to commit for me.

polly/trunk/include/polly/CodeGen/BlockGenerators.h

protected:
   ///
   /// @param BB The basic block code for which code has been generated.
   /// @param BBMap A local map from old to new instructions.
   void removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap);
 
   /// Invalidate the scalar evolution expressions for a scop.
   ///
   /// This function invalidates the scalar evolution results for all
-  /// instructions that are part of a given scop. This is necessary to ensure
-  /// that later scops do not obtain scalar evolution expressions that reference
+  /// instructions that are part of a given scop, and the loops
+  /// surrounding the users of merge blocks. This is necessary to ensure that
+  /// later scops do not obtain scalar evolution expressions that reference
   /// values that earlier dominated the later scop, but have been moved in the
   /// conditional part of an earlier scop and consequently do not any more
   /// dominate the later scop.
   ///
   /// @param S The scop to invalidate.
   void invalidateScalarEvolution(Scop &S);
 };
 

polly/trunk/lib/CodeGen/BlockGenerators.cpp

else if (Stmt.isBlockStmt())
       for (auto &Inst : *Stmt.getBasicBlock())
         SE.forgetValue(&Inst);
     else if (Stmt.isRegionStmt())
       for (auto *BB : Stmt.getRegion()->blocks())
         for (auto &Inst : *BB)
           SE.forgetValue(&Inst);
     else
       llvm_unreachable("Unexpected statement type found");
+
+  // Invalidate SCEV of loops surrounding the EscapeUsers.
+  for (const auto &EscapeMapping : EscapeMap) {
+    const EscapeUserVectorTy &EscapeUsers = EscapeMapping.second.second;
+    for (Instruction *EUser : EscapeUsers) {
+      if (Loop *L = LI.getLoopFor(EUser->getParent()))
+        while (L) {
+          SE.forgetLoop(L);
+          L = L->getParentLoop();
+        }
+    }
+  }
 }
 
 void BlockGenerator::finalizeSCoP(Scop &S) {
   findOutsideUsers(S);
   createScalarInitialization(S);
   createExitPHINodeMerges(S);
   createScalarFinalization(S);
   invalidateScalarEvolution(S);

polly/trunk/test/Isl/CodeGen/two-scops-in-row-invalidate-scevs.ll

+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+;
+; CHECK-LABEL: for.cond:
+; CHECK:         %num.0 = phi i32 [ %add, %for.body15 ], [ 0, %for.cond.pre_entry_bb ]
+; CHECK:         br i1 false, label %for.body15, label %for.end22
+
+; CHECK-LABEL: polly.merge_new_and_old:
+; CHECK:         %num.0.merge = phi i32 [ %num.0.final_reload, %polly.exiting ], [ %num.0, %for.end22 ]
+; CHECK:         br label %for.end44
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @func(i32* %p) {
+entry:
+  %counters = alloca [64 x i32], align 16
+  %lenCounters = alloca [17 x i32], align 16
+  br label %for.cond
+
+for.cond:                                       ; preds = %for.body15, %for.cond
+  %num.0 = phi i32 [ 0, %entry ], [ %add, %for.body15 ]
+  br i1 false, label %for.body15, label %for.end22
+
+for.body15:                                       ; preds = %for.cond
+  %arrayidx17 = getelementptr inbounds [64 x i32], [64 x i32]* %counters, i64 0, i64 0
+  %0 = load i32, i32* %arrayidx17, align 4
+  %add = add i32 %num.0, %0
+  br label %for.cond
+
+for.end22:                                        ; preds = %for.cond
+  br label %for.end44
+
+for.end44:                                        ; preds = %for.end22
+  br i1 undef, label %if.then50, label %if.end67
+
+if.then50:                                        ; preds = %for.end44
+  br label %cleanup
+
+if.end67:                                         ; preds = %for.end44
+  br label %do.body
+
+do.body:                                          ; preds = %cond.end109, %if.end67
+  %e.0 = phi i32 [ 0, %if.end67 ], [ %inc128, %cond.end109 ]
+  br label %cond.end109
+
+cond.end109:                                      ; preds = %do.body
+  %idxprom122 = zext i32 %e.0 to i64
+  %arrayidx123 = getelementptr inbounds i32, i32* %p, i64 %idxprom122
+  %inc128 = add i32 %e.0, 1
+  %sub129 = sub i32 %num.0, %inc128
+  %cmp130 = icmp ugt i32 %sub129, 1
+  br i1 %cmp130, label %do.body, label %do.end
+
+do.end:                                           ; preds = %cond.end109
+  %1 = load i32, i32* %arrayidx123, align 4
+  %arrayidx142 = getelementptr inbounds [17 x i32], [17 x i32]* %lenCounters, i64 0, i64 1
+  store i32 2, i32* %arrayidx142, align 4
+  br label %for.cond201
+
+for.cond201:                                      ; preds = %for.body204, %do.end
+  br i1 undef, label %for.body204, label %for.end214
+
+for.body204:                                      ; preds = %for.cond201
+  br label %for.cond201
+
+for.end214:                                       ; preds = %for.cond201
+  br label %cleanup
+
+cleanup:                                          ; preds = %for.end214, %if.then50
+  ret void
+}