[BOLT] Avoid pointless loop rotation

[spupyrev]

Summary

It seems the earlier implementation does not follow the description
in LoopRotationPass.h: It rotates loops even if they are already laid out
correctly. The diff adjusts the behaviour.

Given that the impact of LoopInversionPass is minor, this change won't
yield significant perf differences. Tested on clang-10: there seems to be a
0.1%-0.3% cpu win and a small reduction of branch misses.

Before:
BOLT-INFO: 120 Functions were reordered by LoopInversionPass

After:
BOLT-INFO: 79 Functions were reordered by LoopInversionPass

[yota9]

Hello! Thank you for your patch, I will take a closer look a bit later, that time may you please add the test to repro the issue?

[lebedev.ri]

Test?

[lebedev.ri]

Actually, this is not in llvm/, so ignore me.

[spupyrev]

adding a test

[yota9]

bolt/test/X86/loop-inversion-pass.s

9

Just wondering what is the reason to change reorder-blocks alg here?

[spupyrev]

bolt/test/X86/loop-inversion-pass.s

9

'cache+' and 'ext-tsp' are synonyms; this is different names of the same alg.

I'll let someone else to get rid of 'cache+' altogether at some point )

[yota9]

bolt/lib/Passes/LoopInversionPass.cpp

69

Could you please re-format this "if" condition back how it was and use "else if" for new condition?

[yota9]

bolt/lib/Passes/LoopInversionPass.cpp

69

Don't pay attention to the first part of the comment above, just reformat "else if" please

[Amir]

Can you please retitle to "[BOLT] Avoid pointless loop rotation"?

bolt/test/X86/loop-inversion-pass.s

9

Can you please keep cache+ here? We'll remove cache+ in a follow-up diff.

[spupyrev]

review

@yota9 please let me know if I got your suggestion right.
Also would be great to understand the motivation for the suggested change; I actually
like the earlier version more, as it shows the two conditions symmetrically (but that
might be just a personal preference)

[yota9]

@spupyrev I don't see strict rules about the else/eslse if statement indeed. This is clearly personal preference, I hust don't like the idea of extra nesting where you can go without it. As for my personal experience LLVM tries to eliminate extra nesting where it is possible. But speaking of the new variant - I think you need to add braces for "else if " statement, since in coding style https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements there are some words about the if/else statement to be uniform e.g.

// Use braces for the `if` block to keep it uniform with the else block.
if (isa<FunctionDecl>(D)) {
  handleFunctionDecl(D);
} else {
  // In this else case, it is necessary that we explain the situation with this
  // surprisingly long comment, so it would be unclear without the braces whether
  // the following statement is in the scope of the `if`.
  handleOtherDecl(D);
}

[spupyrev]

In D121921#3396378, @yota9 wrote:

@spupyrev I don't see strict rules about the else/eslse if statement indeed. This is clearly personal preference, I hust don't like the idea of extra nesting where you can go without it. As for my personal experience LLVM tries to eliminate extra nesting where it is possible. But speaking of the new variant - I think you need to add braces for "else if " statement, since in coding style https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements there are some words about the if/else statement to be uniform e.g.

// Use braces for the `if` block to keep it uniform with the else block.
if (isa<FunctionDecl>(D)) {
  handleFunctionDecl(D);
} else {
  // In this else case, it is necessary that we explain the situation with this
  // surprisingly long comment, so it would be unclear without the braces whether
  // the following statement is in the scope of the `if`.
  handleOtherDecl(D);
}

Could you please suggest the code change?

[yota9]

In D121921#3396478, @spupyrev wrote:

In D121921#3396378, @yota9 wrote:

@spupyrev I don't see strict rules about the else/eslse if statement indeed. This is clearly personal preference, I hust don't like the idea of extra nesting where you can go without it. As for my personal experience LLVM tries to eliminate extra nesting where it is possible. But speaking of the new variant - I think you need to add braces for "else if " statement, since in coding style https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements there are some words about the if/else statement to be uniform e.g.

// Use braces for the `if` block to keep it uniform with the else block.
if (isa<FunctionDecl>(D)) {
  handleFunctionDecl(D);
} else {
  // In this else case, it is necessary that we explain the situation with this
  // surprisingly long comment, so it would be unclear without the braces whether
  // the following statement is in the scope of the `if`.
  handleOtherDecl(D);
}

Could you please suggest the code change?

Sure:

 if (LoopCount < ExitCount) {
   if (BBIndex > SuccBBIndex)
     continue;
 } else if (BBIndex < SuccBBIndex) {
   continue;
}

Like this if you don't mind :)

[spupyrev]

reformat

[yota9]

LGTM, thank you for the fix!

[spupyrev]

rebase

bolt/lib/Passes/LoopInversionPass.cpp

if (SuccBB == PredBB && BB != SuccBB && BBIndex != 0 && SuccBBIndex != 0 &&
       BinaryBasicBlock *SecondSucc = nullptr;
       for (BinaryBasicBlock *Succ : SuccBB->successors()) {
         if (Succ != &*BB) {
           SecondSucc = Succ;
           break;
         }
       }
 
-      assert(SecondSucc != nullptr && "Unable to find second BB successor");
-      const uint64_t BBCount = SuccBB->getBranchInfo(*BB).Count;
-      const uint64_t OtherCount = SuccBB->getBranchInfo(*SecondSucc).Count;
-      if ((BBCount < OtherCount) && (BBIndex > SuccBBIndex))
+      assert(SecondSucc != nullptr && "Unable to find a second BB successor");
+      const uint64_t LoopCount = SuccBB->getBranchInfo(*BB).Count;
+      const uint64_t ExitCount = SuccBB->getBranchInfo(*SecondSucc).Count;
+
+      if (LoopCount < ExitCount) {
+        if (BBIndex > SuccBBIndex)
+          continue;
+      } else if (BBIndex < SuccBBIndex) {
         continue;
+      }
 
       IsChanged = true;
       BB->setLayoutIndex(SuccBBIndex);
       SuccBB->setLayoutIndex(BBIndex);
     }
   }
 
   if (IsChanged) {
     BinaryFunction::BasicBlockOrderType NewOrder = BF.getLayout();
     std::sort(NewOrder.begin(), NewOrder.end(),
               [&](BinaryBasicBlock *BB1, BinaryBasicBlock *BB2) {

bolt/test/X86/loop-inversion-pass.s

 # REQUIRES: system-linux
 
 # RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown \
 # RUN:   %s -o %t.o
 # RUN: link_fdata %s %t.o %t.fdata
 # RUN: link_fdata %s %t.o %t.fdata2 "FDATA2"
+# RUN: link_fdata %s %t.o %t.fdata3 "FDATA3"
 # RUN: %clang %cflags %t.o -o %t.exe -Wl,-q
 # RUN: llvm-bolt %t.exe -data %t.fdata -reorder-blocks=cache+ -print-finalized \
 # RUN:    -loop-inversion-opt -o %t.out | FileCheck %s
 # RUN: llvm-bolt %t.exe -data %t.fdata2 -reorder-blocks=cache+ -print-finalized \
 # RUN:    -loop-inversion-opt -o %t.out2 | FileCheck --check-prefix="CHECK2" %s
+# RUN: llvm-bolt %t.exe -data %t.fdata3 -reorder-blocks=none -print-finalized \
+# RUN:    -loop-inversion-opt -o %t.out3 | FileCheck --check-prefix="CHECK3" %s
 
-# The case where loop is used:
+# The case where the loop is used:
 # FDATA: 1 main 2 1 main #.J1# 0 420
 # FDATA: 1 main b 1 main #.Jloop# 0 420
 # FDATA: 1 main b 1 main d 0 1
 # CHECK: BB Layout   : .LBB00, .Ltmp0, .Ltmp1, .LFT0
 
-# The case where loop is unused:
+# The case where the loop is unused:
 # FDATA2: 1 main 2 1 main #.J1# 0 420
 # FDATA2: 1 main b 1 main #.Jloop# 0 1
 # FDATA2: 1 main b 1 main d 0 420
 # CHECK2: BB Layout   : .LBB00, .Ltmp1, .LFT0, .Ltmp0
 
+# The case where the loop does not require rotation:
+# FDATA3: 1 main 2 1 main #.J1# 0 420
+# FDATA3: 1 main b 1 main #.Jloop# 0 420
+# FDATA3: 1 main b 1 main d 0 1
+# CHECK3: BB Layout   : .LBB00, .Ltmp0, .Ltmp1, .LFT0
+
     .text
     .globl main
     .type main, %function
     .size main, .Lend-main
 main:
     xor %eax, %eax
     jmp .J1
 .Jloop:
     inc %rax
 .J1:
     cmp $16, %rax
     jl .Jloop
     retq
 .Lend: