Use frequency info to guide Loop Invariant Code Motion.

[danielcdh]

Summary

If an instruction's frequency is smaller than preheader, it will harm performance to hoist the instruction to the preheader.

[mcrosier]

Do you have any performance data to back your claim?

lib/Transforms/Scalar/LICM.cpp

347

This could be simplified to:

bool ShouldHoist = BFI->getBlockFreq(BB) >= BFI->getBlockFreq(CurLoop->getLoopPreheader();

and should probably be places inside the if (!inSubLoop(BB, CurLoop, LI)) scope. I.e.,

if (!inSubLoop(BB, CurLoop, LI)) {
  bool ShouldHoist = BFI->getBlockFreq(BB) >= BFI->getBlockFreq(CurLoop->getLoopPreheader();
  for (...)
    ...
}

test/Other/pass-pipelines.ll

40

I may be missing something here, but is this test even relevant to this patch?

[mcrosier]

test/Other/pass-pipelines.ll

40

I guess this just shows the BPA/BFA is being added to the pipeline? We also need a test in test/Transforms/LICM..

[davidxl]

A test case should be added to demonstrate the issue.

test/Other/pass-pipelines.ll

40

BPI is required by BFI

[danielcdh]

Add a unittest to cover the added logic.

[davidxl]

The test case can be further simplified .. (e.g, by disabing licm with O2 -emit-llvm -S). Also make x a local variable and just test 'g', let function return x.

[danielcdh]

reduce the unittest.

[davidxl]

lib/Transforms/Scalar/LICM.cpp

353–355

Better to do this:

if (ShouldHoist && !inSubLoop(BB, CurLoop, LI))

Chad's suggestion of doing

ShouldHoist = BFI->getBlockFreq(BB) >= .. is also good.

[danielcdh]

lib/Transforms/Scalar/LICM.cpp

353–355

Updated with Chad's suggestion. But I cannot move the ShouldHoist check outside the loop because there is still constant folding opportunities inside the loop.

[danielcdh]

Move ShouldHoist inside the branch.

[junbuml]

include/llvm/Transforms/Utils/LoopUtils.h

369–377

Please update the comment.

lib/Transforms/Scalar/LICM.cpp

353–356

I agree that we still need to perform constant folding even when ShouldHoist is false?

[danielcdh]

update comment

[danielcdh]

lib/Transforms/Scalar/LICM.cpp

353–356

yes

[davidxl]

My concern is that static prediction can certainly get it wrong leading to performance regression. I suggest only check this when real profile data is available.

[hfinkel]

In D19950#425274, @davidxl wrote:

My concern is that static prediction can certainly get it wrong leading to performance regression. I suggest only check this when real profile data is available.

Why is this any more of a concern here vs. anywhere else we use static heuristics for block frequencies? I'd think that any problems in this regard should be corrected by making our static heuristics more conservative (i.e. weaker), no?

[davidxl]

Static prediction has been conservative in estimating loop trip count -- it produces something like 30ish iterations. If the a very hot loop has a big if-then-else (or switch), it is very likely to mark many bbs' to be colder than the loop header. Turning on this for static prediction really depends on the false rate. It seems to be this can get wrong pretty easily for very hot loops (which is also the most important thing to optimize for).

[hfinkel]

In D19950#425285, @davidxl wrote:

Static prediction has been conservative in estimating loop trip count -- it produces something like 30ish iterations. If the a very hot loop has a big if-then-else (or switch), it is very likely to mark many bbs' to be colder than the loop header. Turning on this for static prediction really depends on the false rate. It seems to be this can get wrong pretty easily for very hot loops (which is also the most important thing to optimize for).

This is a good point. There's no universal conservative choice (assuming a small trip count is conservative in some cases, and assuming a large trip count is conservative in other cases).

[hfinkel]

In D19950#425286, @hfinkel wrote:

In D19950#425285, @davidxl wrote:

Static prediction has been conservative in estimating loop trip count -- it produces something like 30ish iterations. If the a very hot loop has a big if-then-else (or switch), it is very likely to mark many bbs' to be colder than the loop header. Turning on this for static prediction really depends on the false rate. It seems to be this can get wrong pretty easily for very hot loops (which is also the most important thing to optimize for).

This is a good point. There's no universal conservative choice (assuming a small trip count is conservative in some cases, and assuming a large trip count is conservative in other cases).

Would it be better (and practical) if there were some way for the BFI client to specify which kind of 'conservative' is desired?

Also, why are we doing this instead of sinking later (in CGP or similar)? LICM can expose optimization opportunities, plus represents a code pattern the user might input manually. Sinking later seems more robust.

[danielcdh]

In D19950#425287, @hfinkel wrote:

In D19950#425286, @hfinkel wrote:

In D19950#425285, @davidxl wrote:

Static prediction has been conservative in estimating loop trip count -- it produces something like 30ish iterations. If the a very hot loop has a big if-then-else (or switch), it is very likely to mark many bbs' to be colder than the loop header. Turning on this for static prediction really depends on the false rate. It seems to be this can get wrong pretty easily for very hot loops (which is also the most important thing to optimize for).

This is a good point. There's no universal conservative choice (assuming a small trip count is conservative in some cases, and assuming a large trip count is conservative in other cases).

Would it be better (and practical) if there were some way for the BFI client to specify which kind of 'conservative' is desired?

Also, why are we doing this instead of sinking later (in CGP or similar)? LICM can expose optimization opportunities, plus represents a code pattern the user might input manually. Sinking later seems more robust.

I looked at CGP pass, looks like it's handling the sinking case-by-case (e.g. there is separate routine to handle sinking of load, gep, etc. I'm afraid this would miss opportunities. Additionally, the file-level comment of CGP pass says "This works around limitations in it's basic-block-at-a-time approach. It should eventually be removed."

I'm not quite clear why it helps to move code out of loop early and later sink it inside. Could you give an example or some more context?

Thanks,
Dehao

[danielcdh]

New implementation:

https://reviews.llvm.org/D22778

include/llvm/Transforms/Utils/LoopUtils.h

 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 
 namespace llvm {
 class AliasSet;
 class AliasSetTracker;
 class AssumptionCache;
 class BasicBlock;
+class BlockFrequencyInfo;
 class DataLayout;
 class DominatorTree;
 class Loop;
 class LoopInfo;
 class Pass;
 class PredicatedScalarEvolution;
 class PredIteratorCache;
 class ScalarEvolution;

 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 /// instructions of the loop and loop safety information as arguments.
 /// It returns changed status.
 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
                 LICMSafetyInfo *);
 
 /// \brief Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
-/// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
+/// Takes DomTreeNode, AliasAnalysis, LoopInfo, BlockFrequencyInfo,
+/// DominatorTree, DataLayout,
 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 /// loop and loop safety information as arguments. It returns changed status.
-bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
-                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                 LICMSafetyInfo *);
+bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *,
+                 BlockFrequencyInfo *, DominatorTree *, TargetLibraryInfo *,
+                 Loop *, AliasSetTracker *, LICMSafetyInfo *);
 
 /// \brief Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
 /// AliasSet information for all instructions of the loop and loop safety
 /// information as arguments. It returns changed status.

lib/Transforms/Scalar/LICM.cpp

 //     the SSAUpdater to construct the appropriate SSA form for the value.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/ScalarEvolution.h"
struct LICM : public LoopPass {
   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 
   /// This transformation requires natural loop information & requires that
   /// loop preheaders be inserted into the CFG...
   ///
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.addRequired<BlockFrequencyInfoWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 
   using llvm::Pass::doFinalization;
 
   bool doFinalization() override {
     assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets");
     return false;
   }
 
 private:
   AliasAnalysis *AA; // Current AliasAnalysis information
   LoopInfo *LI;      // Current LoopInfo
   DominatorTree *DT; // Dominator Tree for the current Loop.
+  BlockFrequencyInfo *BFI;
 
   TargetLibraryInfo *TLI; // TargetLibraryInfo for constant folding.
 
   // State that is updated as we process loops.
   bool Changed;            // Set to true when we change anything.
   BasicBlock *Preheader;   // The preheader block of the current loop...
   Loop *CurLoop;           // The current loop we are working on...
   AliasSetTracker *CurAST; // AliasSet information for the current loop...
private:
   AliasSetTracker *collectAliasInfoForLoop(Loop *L);
 };
 }
 
 char LICM::ID = 0;
 INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false)
 
 Pass *llvm::createLICMPass() { return new LICM(); }
 
 /// Hoist expressions out of the specified loop. Note, alias info for inner
 /// loop is not preserved so it is not a good idea to run LICM multiple
 /// times on one loop.
 ///
 bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
   if (skipLoop(L))
     return false;
 
   Changed = false;
 
   // Get our Loop and Alias Analysis information...
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
 
   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
   CurAST = collectAliasInfoForLoop(L);
 
   CurLoop = L;
bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
   // that we are guaranteed to see definitions before we see uses.  This allows
   // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
   //
   if (L->hasDedicatedExits())
     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop,
                           CurAST, &SafetyInfo);
   if (Preheader)
-    Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI,
+    Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, BFI, DT, TLI,
                            CurLoop, CurAST, &SafetyInfo);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
   if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
     SmallVector<BasicBlock *, 8> ExitBlocks;
     SmallVector<Instruction *, 8> InsertPts;
     PredIteratorCache PIC;

 }
 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 ///
 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
-                       DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
+                       BlockFrequencyInfo *BFI, DominatorTree *DT,
+                       TargetLibraryInfo *TLI, Loop *CurLoop,
                        AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
          CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
          "Unexpected input to hoistRegion");
 
   BasicBlock *BB = N->getBlock();
 
   // If this subregion is not in the top level loop at all, exit.
   if (!CurLoop->contains(BB))
     return false;
 
   // Only need to process the contents of this block if it is not part of a
   // subloop (which would already have been processed).
   bool Changed = false;
-  if (!inSubLoop(BB, CurLoop, LI))
+  if (!inSubLoop(BB, CurLoop, LI)) {
+    bool ShouldHoist =
+        BFI->getBlockFreq(BB) >= BFI->getBlockFreq(CurLoop->getLoopPreheader());
     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
       Instruction &I = *II++;
       // Try constant folding this instruction.  If all the operands are
       // constants, it is technically hoistable, but it would be better to just
       // fold it.
       if (Constant *C = ConstantFoldInstruction(
               &I, I.getModule()->getDataLayout(), TLI)) {
         DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C << '\n');
         CurAST->copyValue(&I, C);
         CurAST->deleteValue(&I);
         I.replaceAllUsesWith(C);
         I.eraseFromParent();
         continue;
       }
+      if (!ShouldHoist)
+        continue;
 
       // Try hoisting the instruction out to the preheader.  We can only do this
       // if all of the operands of the instruction are loop invariant and if it
       // is safe to hoist the instruction.
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
           isSafeToExecuteUnconditionally(
               I, DT, TLI, CurLoop, SafetyInfo,
               CurLoop->getLoopPreheader()->getTerminator()))
         Changed |= hoist(I, DT, CurLoop, SafetyInfo);
     }
+  }
 
   const std::vector<DomTreeNode *> &Children = N->getChildren();
   for (DomTreeNode *Child : Children)
-    Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
+    Changed |=
+        hoistRegion(Child, AA, LI, BFI, DT, TLI, CurLoop, CurAST, SafetyInfo);
   return Changed;
 }
 
 /// Computes loop safety information, checks loop body & header
 /// for the possibility of may throw exception.
 ///
 void llvm::computeLICMSafetyInfo(LICMSafetyInfo *SafetyInfo, Loop *CurLoop) {
   assert(CurLoop != nullptr && "CurLoop cant be null");

test/Other/pass-pipelines.ll

 ; CHECK-O2-NEXT: Remove unused exception handling info
 ; CHECK-O2-NEXT: Function Integration/Inlining
 ; CHECK-O2-NEXT: Deduce function attributes
 ; Next up is the main function pass pipeline. It shouldn't be split up and
 ; should contain the main loop pass pipeline as well.
 ; CHECK-O2-NEXT: FunctionPass Manager
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Loop Pass Manager
+; CHECK-O2: Branch Probability Analysis
+; CHECK-O2: Block Frequency Analysis
+; CHECK-O2: Loop Pass Manager
+; CHECK-O2: Loop Invariant Code Motion
+; CHECK-O2: Loop Pass Manager
+; CHECK-O2: Unswitch loops
 ; CHECK-O2-NOT: Manager
 ; FIXME: We shouldn't be pulling out to simplify-cfg and instcombine and
 ; causing new loop pass managers.
 ; CHECK-O2: Simplify the CFG
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Combine redundant instructions
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Loop Pass Manager

test/Transforms/LICM/not-hoist-low-freq.ll

+; RUN: opt -S -licm < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Original source code:
+; int g;
+; int foo(int p, int x) {
+;   for (int i = 0; i != x; i++)
+;     if (__builtin_expect(i == p, 0)) {
+;       x += g; x *= g;
+;     }
+;   return x;
+; }
+;
+; Load of global value g should not be hoisted to preheader.
+
+@g = global i32 0, align 4
+
+; Function Attrs: norecurse nounwind readonly uwtable
+define i32 @_Z3fooii(i32, i32) #0 {
+  %3 = icmp eq i32 %1, 0
+  br i1 %3, label %._crit_edge, label %.lr.ph.preheader
+
+.lr.ph.preheader:                                 ; preds = %2
+  br label %.lr.ph
+
+.lr.ph:                                           ; preds = %.lr.ph.preheader, %9
+  %.03 = phi i32 [ %8, %.combine ], [ 0, %.lr.ph.preheader ]
+  %.012 = phi i32 [ %.1, %.combine ], [ %1, %.lr.ph.preheader ]
+  %4 = icmp eq i32 %.03, %0
+  br i1 %4, label %.then, label %.combine, !prof !1
+
+.then:                                            ; preds = %.lr.ph
+  %5 = load i32, i32* @g, align 4, !tbaa !2
+  %6 = add nsw i32 %5, %.012
+  %7 = mul nsw i32 %6, %5
+  br label %.combine
+
+; CHECK: .then:
+; CHECK: load i32, i32* @g
+; CHECK: br label %.combine
+
+.combine:                                         ; preds = %.lr.ph, %.then
+  %.1 = phi i32 [ %7, %.then ], [ %.012, %.lr.ph ]
+  %8 = add nuw nsw i32 %.03, 1
+  %9 = icmp eq i32 %8, %.1
+  br i1 %9, label %._crit_edge.loopexit, label %.lr.ph
+
+._crit_edge.loopexit:                             ; preds = %.combine
+  %.1.lcssa = phi i32 [ %.1, %.combine ]
+  br label %._crit_edge
+
+._crit_edge:                                      ; preds = %._crit_edge.loopexit, %2
+  %.01.lcssa = phi i32 [ 0, %2 ], [ %.1.lcssa, %._crit_edge.loopexit ]
+  ret i32 %.01.lcssa
+}
+
+attributes #0 = { norecurse nounwind readonly uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 3.9.0 (trunk 268689)"}
+!1 = !{!"branch_weights", i32 1, i32 2000}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C++ TBAA"}