[LoopRotate] Use UnrolledInstAnalyzer to account for simplifications in hoisted header. (WIP)

[fhahn]

Summary

This is still work in progress, as the interface for
UnrolledInstAnalyzer needs improving and also the code-size impact is
all over the place (see results for X86 -Oz -flto). Presumably the issue
is that rotating more loops exposes more loops to other loop
optimizations, which do not respect -Oz properly. For example, in the
attached test case, the loop in test2 will get fully unrolled.

Program master patch diff
test-suite...ing-flt/Equivalencing-flt.test 17144 21240 23.9%
test-suite...ing-dbl/Equivalencing-dbl.test 21240 17144 -19.3%
test-suite...pps-C/SimpleMOC/SimpleMOC.test 26256 22160 -15.6%
test-suite...cations/hexxagon/hexxagon.test 29916 25772 -13.9%
test-suite...langs-C/football/football.test 40320 44416 10.2%
test-suite...abench/jpeg/jpeg-6a/cjpeg.test 69648 73784 5.9%
test-suite...ce/Benchmarks/PAQ8p/paq8p.test 89404 93500 4.6%
test-suite...INT95/132.ijpeg/132.ijpeg.test 96772 100972 4.3%
test-suite...000/186.crafty/186.crafty.test 176188 180452 2.4%
test-suite...nsumer-lame/consumer-lame.test 189016 185032 -2.1%
test-suite...ications/JM/ldecod/ldecod.test 254648 249680 -2.0%
test-suite...ProxyApps-C++/CLAMR/CLAMR.test 244976 240696 -1.7%
test-suite...006/447.dealII/447.dealII.test 609760 603200 -1.1%
test-suite...nch/pcompress2/pcompress2.test 14500 14652 1.0%
test-suite...Rodinia/backprop/backprop.test 12828 12932 0.8%

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/LoopUnrollAnalyzer.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DebugInfoMetadata.h"
if (Metrics.notDuplicatable) {
       return false;
     }
     if (Metrics.convergent) {
       LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "
                            "instructions: ";
                  L->dump());
       return false;
     }
-    if (Metrics.NumInsts > MaxHeaderSize)
+
+    // We track the simplification of each instruction in each iteration. We use
+    // this to recursively merge costs into the unrolled cost on-demand so that
+    // we don't count the cost of any dead code. This is essentially a map from
+    // <instruction, int> to <bool, bool>, but stored as a densely packed
+    // struct.
+    DenseSet<UnrolledInstState, UnrolledInstStateKeyInfo> InstCostMap;
+    //
+    // The estimated cost of the unrolled form of the loop. We try to estimate
+    // this by simplifying as much as we can while computing the estimate.
+    unsigned UnrolledCost = 0;
+
+    // We also track the estimated dynamic (that is, actually executed) cost in
+    // the rolled form. This helps identify cases when the savings from
+    // unrolling aren't just exposing dead control flows, but actual reduced
+    // dynamic instructions due to the simplifications which we expect to occur
+    // after unrolling.
+    unsigned RolledDynamicCost = 0;
+
+    DenseMap<Value *, Constant *> SimplifiedValues;
+
+    UnrolledInstAnalyzer Analyzer(0, SimplifiedValues, EphValues, InstCostMap,
+                                  RolledDynamicCost, UnrolledCost,
+                                  MaxHeaderSize, *SE, *TTI, L);
+    if (!Analyzer.visitBB(*OrigHeader))
+      return false;
+
+    Analyzer.AddCostRecursively(*OrigHeader->getTerminator(), 0);
+    if (UnrolledCost > MaxHeaderSize + 1)
       return false;
   }
 
   // Now, this loop is suitable for rotation.
   BasicBlock *OrigPreheader = L->getLoopPreheader();
 
   // If the loop could not be converted to canonical form, it must have an
   // indirectbr in it, just give up.

llvm/test/Transforms/LoopRotate/oz-disable.ll

 ; REQUIRES: asserts
 ; RUN: opt < %s -S -Os -debug -debug-only=loop-rotate 2>&1 | FileCheck %s -check-prefix=OS
 ; RUN: opt < %s -S -Oz -debug -debug-only=loop-rotate 2>&1 | FileCheck %s -check-prefix=OZ
 
-; Loop should be rotated for -Os but not for -Oz.
-; OS: rotating Loop at depth 1
-; OZ-NOT: rotating Loop at depth 1
-
 @e = global i32 10
 
 declare void @use(i32)
 
+; Loop should be rotated for -Os but not for -Oz, as not all instructions in
+; the header are free.
+
+; OS: LoopRotation: rotating Loop at depth 1 containing: %loop<header><exiting>,%loop.fin<latch>
+; OS-NEXT: LoopRotation: into Loop at depth 1 containing: %loop.fin<header><latch><exiting>
+
+; OZ-NOT: LoopRotation: rotating Loop at depth 1 containing: %loop<header><exiting>,%loop.fin<latch>
+; OZ-NOT: LoopRotation: into Loop at depth 1 containing: %loop.fin<header><latch><exiting>
 define void @test() {
 entry:
   %end = load i32, i32* @e
   br label %loop
 
 loop:
   %n.phi = phi i32 [ %n, %loop.fin ], [ 0, %entry ]
   %cond = icmp eq i32 %n.phi, %end
   br i1 %cond, label %exit, label %loop.fin
 
 loop.fin:
   %n = add i32 %n.phi, 1
   call void @use(i32 %n)
   br label %loop
 
 exit:
   ret void
 }
+
+; Loop should be rotated for both -Os and -Oz, as all instructions in the header
+; are free.
+
+; OS-NEXT: LoopRotation: rotating Loop at depth 1 containing: %loop2<header><exiting>,%loop2.fin<latch>
+; OS-NEXT: LoopRotation: into Loop at depth 1 containing: %loop2.fin<header><latch><exiting>
+
+; OZ: LoopRotation: rotating Loop at d
+; OZ-NEXT: LoopRotation: into Loop at depth 1 containing: %loop2.fin<header><latch><exiting>
+define void @test2() {
+entry:
+  br label %loop2
+
+loop2:
+  %n.phi = phi i32 [ %n, %loop2.fin ], [ 0, %entry ]
+  %cond = icmp eq i32 %n.phi, 15
+  br i1 %cond, label %exit, label %loop2.fin
+
+loop2.fin:
+  %n = add i32 %n.phi, 1
+  call void @use(i32 %n)
+  br label %loop2
+
+exit:
+  ret void
+}