Enable Loop Sink pass for functions that has profile.

[danielcdh]

Summary

For functions with profile data, we are confident that loop sink will be optimal in sinking code.

[danielcdh]

ping

[hfinkel]

LGTM

lib/Transforms/Scalar/LoopSink.cpp

246 ↗

(On Diff #76430)

Please add a comment here explaining why you're doing this.

[mzolotukhin]

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

650

Can't we schedule this right after LICM?
I think we're placing LoopSinking in a separate instance of loop pass manager - is that what we want?

[davidxl]

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

650

LICM also serves as an IR canonicalization pass that enables other optimization, so loopSinking needs to be a very late IR pass to avoid undoing LICM result too early. Otherwise the logic of loopSinking can be baked into LICM as proposed originally.

[mehdi_amini]

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

650

Can we have a comment here, the PassManagerBuilder is already hard to follow, it'd be great to bake in why passes are there, and why they are where they are.

[mzolotukhin]

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

650

I meant the last invocation of LICM, which is also very late (before createAlignmentFromAssumptionsPass). I don't see any loop pass in between them now. But anyway, I just wanted to make sure this placement is conscious, so if this is the case, I'm ok with it. And as Mehdi said, comments would be helpful here.

[danielcdh]

Comments added:

r286480 | dehao | 2016-11-10 09:42:18 -0800 (Thu, 10 Nov 2016) | 2 lines

Add comments about why we put LoopSink pass at the very late stage.

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

if (!DisableUnrollLoops) {
     // LoopUnroll may generate some redundency to cleanup.
     addInstructionCombiningPass(MPM);
 
     // Runtime unrolling will introduce runtime check in loop prologue. If the
     // unrolled loop is a inner loop, then the prologue will be inside the
     // outer loop. LICM pass can help to promote the runtime check out if the
     // checked value is loop invariant.
     MPM.add(createLICMPass());
-
-    // Get rid of LCSSA nodes.
-    MPM.add(createInstructionSimplifierPass());
-  }
 
   // After vectorization and unrolling, assume intrinsics may tell us more
   // about pointer alignments.
   MPM.add(createAlignmentFromAssumptionsPass());
 
   if (!DisableUnitAtATime) {
     // FIXME: We shouldn't bother with this anymore.
     MPM.add(createStripDeadPrototypesPass()); // Get rid of dead prototypes
 
     // GlobalOpt already deletes dead functions and globals, at -O2 try a
     // late pass of GlobalDCE.  It is capable of deleting dead cycles.
     if (OptLevel > 1) {
       MPM.add(createGlobalDCEPass());         // Remove dead fns and globals.
       MPM.add(createConstantMergePass());     // Merge dup global constants
     }
   }
 
   if (MergeFunctions)
     MPM.add(createMergeFunctionsPass());
 
+  MPM.add(createLoopSinkPass());
+  // Get rid of LCSSA nodes.
+  MPM.add(createInstructionSimplifierPass());
   addExtensionsToPM(EP_OptimizerLast, MPM);
 }
 
 void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
   // Remove unused virtual tables to improve the quality of code generated by
   // whole-program devirtualization and bitset lowering.
   PM.add(createGlobalDCEPass());
 

llvm/trunk/lib/Transforms/Scalar/LoopSink.cpp

 static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI,
                                           DominatorTree &DT,
                                           BlockFrequencyInfo &BFI,
                                           ScalarEvolution *SE) {
   BasicBlock *Preheader = L.getLoopPreheader();
   if (!Preheader)
     return false;
 
+  // Enable LoopSink only when runtime profile is available.
+  // With static profile, the sinking decision may be sub-optimal.
+  if (!Preheader->getParent()->getEntryCount())
+    return false;
+
   const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
   // If there are no basic blocks with lower frequency than the preheader then
   // we can avoid the detailed analysis as we will never find profitable sinking
   // opportunities.
   if (all_of(L.blocks(), [&](const BasicBlock *BB) {
         return BFI.getBlockFreq(BB) > PreheaderFreq;
       }))
     return false;

llvm/trunk/test/Other/pass-pipelines.ll

 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NEXT: Unroll loops
 ; CHECK-O2-NOT: Manager
 ; After vectorization and unrolling we try to do any cleanup of inserted code,
 ; including a run of LICM. This shouldn't run in the same loop pass manager as
 ; the runtime unrolling though.
 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NEXT: Loop Invariant Code Motion
+; CHECK-O2: FunctionPass Manager
+; CHECK-O2: Loop Pass Manager
+; CHECK-O2-NEXT: Loop Sink
 ; CHECK-O2-NOT: Manager
 ;
 ; FIXME: There really shouldn't be another pass manager, especially one that
 ; just builds the domtree. It doesn't even run the verifier.
 ; CHECK-O2: Pass Arguments:
 ; CHECK-O2-NEXT: FunctionPass Manager
 ; CHECK-O2-NEXT: Dominator Tree Construction
 
 define void @foo() {
   ret void
 }

llvm/trunk/test/Transforms/LICM/loopsink.ll

 ; b3: 7
 ; b4: 7
 ; Sink load to b2
 ; CHECK: t1
 ; CHECK: .b2:
 ; CHECK: load i32, i32* @g
 ; CHECK: .b3:
 ; CHECK-NOT:  load i32, i32* @g
-define i32 @t1(i32, i32) #0 {
+define i32 @t1(i32, i32) #0 !prof !0 {
   %3 = icmp eq i32 %1, 0
   br i1 %3, label %.exit, label %.preheader
 
 .preheader:
   %invariant = load i32, i32* @g
   br label %.b1
 
 .b1:

 ; CHECK: .preheader:
 ; CHECK-NOT: load i32, i32* @g
 ; CHECK: .b3:
 ; CHECK: load i32, i32* @g
 ; CHECK: .b4:
 ; CHECK: .b6:
 ; CHECK: load i32, i32* @g
 ; CHECK: .b7:
-define i32 @t2(i32, i32) #0 {
+define i32 @t2(i32, i32) #0 !prof !0 {
   %3 = icmp eq i32 %1, 0
   br i1 %3, label %.exit, label %.preheader
 
 .preheader:
   %invariant = load i32, i32* @g
   br label %.b1
 
 .b1:

 ; b3: 8
 ; b5: 16008
 ; Do not sink load from preheader.
 ; CHECK: t3
 ; CHECK: .preheader:
 ; CHECK: load i32, i32* @g
 ; CHECK: .b1:
 ; CHECK-NOT: load i32, i32* @g
-define i32 @t3(i32, i32) #0 {
+define i32 @t3(i32, i32) #0 !prof !0 {
   %3 = icmp eq i32 %1, 0
   br i1 %3, label %.exit, label %.preheader
 
 .preheader:
   %invariant = load i32, i32* @g
   br label %.b1
 
 .b1:

 
 ; For single-BB loop with <=1 avg trip count, sink load to b1
 ; CHECK: t4
 ; CHECK: .preheader:
 ; CHECK-not: load i32, i32* @g
 ; CHECK: .b1:
 ; CHECK: load i32, i32* @g
 ; CHECK: .exit:
-define i32 @t4(i32, i32) #0 {
+define i32 @t4(i32, i32) #0 !prof !0 {
 .preheader:
   %invariant = load i32, i32* @g
   br label %.b1
 
 .b1:
   %iv = phi i32 [ %t1, %.b1 ], [ 0, %.preheader ]
   %t1 = add nsw i32 %invariant, %iv
   %c1 = icmp sgt i32 %iv, %0

 ; b3: 7
 ; b4: 7
 ; There is alias store in loop, do not sink load
 ; CHECK: t5
 ; CHECK: .preheader:
 ; CHECK: load i32, i32* @g
 ; CHECK: .b1:
 ; CHECK-NOT: load i32, i32* @g
-define i32 @t5(i32, i32*) #0 {
+define i32 @t5(i32, i32*) #0 !prof !0 {
   %3 = icmp eq i32 %0, 0
   br i1 %3, label %.exit, label %.preheader
 
 .preheader:
   %invariant = load i32, i32* @g
   br label %.b1
 
 .b1:
.b7:
   br i1 %c7, label %.b1, label %.exit, !prof !3
 
 .exit:
   ret i32 10
 }
 
 declare i32 @foo()
 
+!0 = !{!"function_entry_count", i64 1}
 !1 = !{!"branch_weights", i32 1, i32 2000}
 !2 = !{!"branch_weights", i32 2000, i32 1}
 !3 = !{!"branch_weights", i32 100, i32 1}

llvm/trunk/test/Transforms/LICM/sink.ll

 ;     }
 ;   return x;
 ; }
 ;
 ; Load of global value g should not be hoisted to preheader.
 
 @g = global i32 0, align 4
 
-define i32 @foo(i32, i32) #0 {
+define i32 @foo(i32, i32) #0 !prof !2 {
   %3 = icmp eq i32 %1, 0
   br i1 %3, label %._crit_edge, label %.lr.ph.preheader
 
 .lr.ph.preheader:
   br label %.lr.ph
 
 ; CHECK-LICM: .lr.ph.preheader:
 ; CHECK-LICM: load i32, i32* @g
._crit_edge.loopexit:
   br label %._crit_edge
 
 ._crit_edge:
   %.01.lcssa = phi i32 [ 0, %2 ], [ %.1.lcssa, %._crit_edge.loopexit ]
   ret i32 %.01.lcssa
 }
 
 !1 = !{!"branch_weights", i32 1, i32 2000}
+!2 = !{!"function_entry_count", i64 1}