[Sink] Use reverse post order in iterative sinking algorithm

[bin.cheng]

Summary

Hi,
The iterative sinking algorithm sinks load instructions step by step, so
it's better to use RPO that helps fast convergence by visiting BB before
its sink successors. Also adds a test showing the behavior change.

Thanks,
bin

llvm/lib/Transforms/Scalar/Sink.cpp

 //===-- Sink.cpp - Code Sinking -------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass moves instructions into successor blocks, when possible, so that
 // they aren't executed on paths where their results aren't needed.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/Sink.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"

 
 static bool iterativelySinkInstructions(Function &F, DominatorTree &DT,
                                         LoopInfo &LI, AAResults &AA) {
   bool MadeChange, EverMadeChange = false;
 
   do {
     MadeChange = false;
     LLVM_DEBUG(dbgs() << "Sinking iteration " << NumSinkIter << "\n");
-    // Process all basic blocks.
-    for (BasicBlock &I : F)
-      MadeChange |= ProcessBlock(I, DT, LI, AA);
+    // Process all basic blocks in RPO for fast convergence.
+    ReversePostOrderTraversal<Function *> RPOT(&F);
+    for (BasicBlock *I : RPOT)
+      MadeChange |= ProcessBlock(*I, DT, LI, AA);
     EverMadeChange |= MadeChange;
     NumSinkIter++;
   } while (MadeChange);
 
   return EverMadeChange;
 }
 
 PreservedAnalyses SinkingPass::run(Function &F, FunctionAnalysisManager &AM) {

llvm/test/Transforms/Sink/reverse-post-order.ll

+; REQUIRES: asserts
+; RUN: opt < %s -passes='sink' -debug-only=sink -S 2>&1 | FileCheck %s
+
+; CHECK-NOT: Sinking iteration 2
+
+%struct.expression = type { i8*, i32 }
+%struct.node = type { i8, i8, i16 }
+%struct.info = type { i8*, i32 }
+
+@.str = private unnamed_addr constant [16 x i8] c"Can't handle %d\00", align 1
+
+; Function Attrs: nounwind uwtable
+define dso_local i8* @foo(%struct.expression* nocapture readonly %expr, %struct.node* nocapture readonly %n, i8* readnone %start, i8* readnone %end, %struct.info* nocapture readonly %info) {
+entry:
+  br label %entry.tmp
+
+while.cond.preheader:                             ; preds = %while.cond.preheader.tmp
+  %flag7 = getelementptr inbounds %struct.info, %struct.info* %info, i64 0, i32 1
+  %cmp520 = icmp ult i8* %start, %end
+  br i1 %cmp520, label %while.body, label %cleanup
+
+while.cond.preheader.tmp:
+  %s.tmp = icmp eq i8* %start, null
+  br i1 %s.tmp, label %cleanup, label %while.cond.preheader
+
+entry.tmp:
+  %flag = getelementptr inbounds %struct.expression, %struct.expression* %expr, i64 0, i32 1
+  %0 = load i32, i32* %flag, align 8
+  %and = and i32 %0, 1
+  %1 = xor i32 %and, 1
+  %type = getelementptr inbounds %struct.node, %struct.node* %n, i64 0, i32 1
+  %tmp.2 = load i8, i8* %type, align 1
+  %cmp3 = icmp eq i8 %tmp.2, 18
+  br i1 %cmp3, label %while.cond.preheader.tmp, label %if.else10
+
+while.body:                                       ; preds = %while.cond.preheader, %if.else
+  %flag1.023 = phi i32 [ %1, %if.else ], [ 1, %while.cond.preheader ]
+  %start.addr.021 = phi i8* [ %incdec.ptr, %if.else ], [ %start, %while.cond.preheader ]
+  %tobool.not = icmp eq i32 %flag1.023, 0
+  br i1 %tobool.not, label %if.else, label %land.lhs.true
+
+land.lhs.true:                                    ; preds = %while.body
+  %tmp.3 = load i32, i32* %flag7, align 8
+  %tobool8.not = icmp eq i32 %tmp.3, 0
+  br i1 %tobool8.not, label %if.else, label %cleanup
+
+if.else:                                          ; preds = %land.lhs.true, %while.body
+  %incdec.ptr = getelementptr inbounds i8, i8* %start.addr.021, i64 1
+  %cmp5 = icmp ult i8* %incdec.ptr, %end
+  br i1 %cmp5, label %while.body, label %cleanup
+
+if.else10:                                        ; preds = %entry
+  %conv2 = zext i8 %tmp.2 to i32
+  tail call void @report_error(i8* getelementptr inbounds ([16 x i8], [16 x i8]* @.str, i64 0, i64 0), i32 %conv2)
+  br label %cleanup
+
+cleanup:                                          ; preds = %land.lhs.true, %if.else, %while.cond.preheader, %if.else10, %while.cond.preheader.tmp
+  %retval.0 = phi i8* [ null, %if.else10 ], [ null, %while.cond.preheader ], [ %start.addr.021, %land.lhs.true ], [ null, %if.else ], [null, %while.cond.preheader.tmp]
+  ret i8* %retval.0
+}
+
+declare dso_local void @report_error(i8*, i32)