[MBP] Move a latch block with conditional exit and multi predecessors to top of loop

[Carrot]

Summary

Current findBestLoopTop can find and move one kind of block to top, a latch block has one successor. Another common case is:

• a latch block
• it has two successors, one is loop header, another is exit
• it has more than one predecessors

If it is below one of its predecessors P, only P can fall through to it, all other predecessors need a jump to it, and another conditional jump to loop header. If it is moved before loop header, all its predecessors jump to it, then fall through to loop header. So all its predecessors except P can reduce one taken branch.

[davidxl]

Please add a few new test cases first.

[Carrot]

Add a new test case.

[davidxl]

test/CodeGen/X86/move_latch_to_loop_top.ll

39

This is not the optimal rotation for the loop. The optimal rotation should be

true
latch
header
false

in which case there is one more fall through from true to latch.

I think the enhancement should shoot for getting the optimal layout.

[Carrot]

Add more code to iteratively find new block that can be moved before old loop top block, and reduce taken branches. Now it can layout the test case optimally as David commented.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1758–1827

BottomBlock --> bottom block BB

1759

the following case.

1768

Add some arrows in the graph and explain more in text why it is not beneficial

1792

Add more comment about the intention of this method:

The method checks if the reduced taken branches is less than increased taken branch (to the exit block when rotation happens). If yes, it returns true.

1888

It makes assumption that there is an existing fall through to the exit bb. If not, it is always beneficial to rotate.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1822

--> and it has more than one predecessors.

1833

Add comment that the reduced taken branches will be compared with the increased taken branch to the loop exit block.

1872

Why is this check needed?

test/CodeGen/X86/move_latch_to_loop_top.ll

75

perhaps draw a diagram here.

[Carrot]

lib/CodeGen/MachineBlockPlacement.cpp

1872

Only two patterns are handled, none of the cases has more than 2 successors.

1888

Yes.
But layout the loop body and rotate loop occur after this function, it is difficult to guess which BB will be put at the bottom of the loop. So to be conservative, assume the current candidate BB can be layout at the bottom, and fall through to the exit bb.

[Carrot]

Update the patch to the current code base, also make two improvements:

• Do more precise cost analysis based on the increased number of fallthrough.
• Also enable findBestLoopTop when profile information is available.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1849

Move this checked into the caller function

1880

This check is not necessary. See example at https://reviews.llvm.org/F8921829

If B6 is selected as the new loop top, the fall through frequencies can be increased from 99 to 150.

[davidxl]

For all the test cases update, please also validate if they make sense or not if possible.

lib/CodeGen/MachineBlockPlacement.cpp

1764

This part looks complete. Are all the paths covered by some tests?

1874

The logic looks correct. Are all cases covered by tests?

1876

The comment should be fixed.

1899

more generally, you want largest pred edge frequency to be smaller than the new back edge frequency.

1901

The 'else' here seems wrong. It needs to fall through to do the same check.

[Carrot]

lib/CodeGen/MachineBlockPlacement.cpp

1764

New tests added.

1874

A lot of existing test cases are impacted by this patch, and this function is intensively tested by those test cases.

1880

You are right. This code was used as heuristic when I didn't quantitatively compute the number of fallthrough. Now that we have more precise cost model, it should be removed.

1899

Again it is a heuristic before FallThroughGains is implemented. Now it can be removed.

[Carrot]

Some analysis of the test case changes.

test/CodeGen/AArch64/neg-imm.ll
The control flow graph looks like:

    entry
      |
      V
-->for.body
|     |\
|     | \
|     |  \
|     | if.then3
|     |  /
|     | /
|     |/
---for.inc
      |
      V
for.cond.cleanup

The original layout is:

entry
for.body
if.then3
for.inc
for.cond.cleanup

For each loop iteration there are two taken branches.

The new layout is:

entry
for.inc
for.body
if.then3
for.cond.cleanup

For each loop iterations there is one taken branch.

test/CodeGen/AMDGPU/optimize-negated-cond.ll
The control flow of function @negated_cond_dominated_blocks is:

  bb
   |
   V
  bb4 <--
  /\    |
 /  \   |
bb5 bb6 |
 \  /   |
  \/    |
  bb7 ---
   |
   V
  bb3

The original layout is:

bb
bb4
bb6
bb5
bb7
bb3

For each loop iteration there are two taken branches.

New layout is

bb
bb6
bb7
bb4
bb5
bb3

For each loop iterations there is one taken branch.

test/CodeGen/Hexagon/redundant-branching2.ll
It is also diamond shaped loop,

   |
  b3 <--
  /\   |
 /  \  |
b4  b5 |
 \  /  |
  \/   |
  b6----
   |

Original layout is

b3
b4
b5
b6

New layout is

b5
b6
b3
b4

The new layout can reduce 1 taken branch per iteration.

test/CodeGen/X86/widen_arith-*.ll
The control flow graph is:

    entry
      |
      V
-->forcond ---
|     |      |
|     V      |
---forbody   |
             |
             V
         afterfor

Original layout is:

entry
forbody
forcond
afterfor

New layout is:

entry
forcond
forbody
afterfor

It shouldn't have performance impact, but the new layout is more natrual, more readable.

[davidxl]

lgtm.

Warning. With static profiling, the layout strategy based on the 'precise' cost model may be off. If for some reason this causes issues later, the change should be guarded with 'hasProfile' check.

[samparker]

Do you have any benchmark numbers to show that this is generally profitable? From our downstream testing, it is not clear that this change is beneficial.

[Carrot]

In D43256#1545519, @samparker wrote:

Do you have any benchmark numbers to show that this is generally profitable? From our downstream testing, it is not clear that this change is beneficial.

We got performance improvement in our internal search benchmark.

[ebrevnov]

This change causes 35% regression on very simple loop which is hot part of our internal micro benchmark.
This loop takes 99% of total execution time and has reasonably large number of iterations.
All measurements were performed on Intel(R) Xeon(R) CPU E3-1240 v5 @ 3.50GHz.

Here is the loop in question before the change:

25.41  | 0x30020e20:   c5fa10 vmovss    12(%rcx,%rsi,4), %xmm0
  5.12  | 0x30020e26:   c5f82e vucomiss    %xmm0, %xmm0
  0.61  | 0x30020e2a:   7a1d   jp    29                              ; 0x30020e49
  0.61  | 0x30020e2c:   c5fa10 vmovss    12(%rax,%rsi,4), %xmm2
 28.07 | 0x30020e32:   c5f82e vucomiss    %xmm1, %xmm0
  4.10  | 0x30020e36:   7506   jne    6                              ; 0x30020e3e
           | 0x30020e38:   0f8bd0 jnp    720                            ; 0x3002110e
  0.41  | 0x30020e3e:   c5fac2 vcmpless    %xmm2, %xmm0, %xmm3
  0.41  | 0x30020e43:   c4e369 vblendvps    %xmm3, %xmm0, %xmm2, %xmm0
 35.04 | 0x30020e49:   c5fa11 vmovss    %xmm0, 12(%rdx,%rsi,4)
  0.20  | 0x30020e4f:   48ffc6 incq    %rsi
           | 0x30020e52:   4839de cmpq    %rbx, %rsi
           | 0x30020e55:   72c9   jb    -55                             ; 0x30020e20

After the change:

          | 0x30020a40:   c5fa11 vmovss    %xmm0, 12(%rdx,%rsi,4)
          | 0x 30020a46:   48ffc6 incq    %rsi
27.25 | 0x 30020a49:   4839de cmpq    %rbx, %rsi
          | 0x30020a4c:   0f836e jae    -146                           ; 0x300209c0
          | 0x30020a52:   c5fa10 vmovss    12(%rcx,%rsi,4), %xmm0
          | 0x30020a58:   c5f82e vucomiss    %xmm0, %xmm0
          | 0x30020a5c:   7ae2   jp    -30                             ; 0x30020a40
27.46 | 0x30020a5e:   c5fa10 vmovss    12(%rax,%rsi,4), %xmm2
          | 0x30020a64:   c5f82e vucomiss    %xmm1, %xmm0
          | 0x30020a68:   7506   jne    6                              ; 0x30020a70
          | 0x30020a6a:   0f8bfd jnp    509                            ; 0x30020c6d
          | 0x30020a70:   c5fac2 vcmpless    %xmm2, %xmm0, %xmm3
23.36 | 0x30020a75:   c4e369 vblendvps    %xmm3, %xmm0, %xmm2, %xmm0
21.93 | 0x30020a7b:   ebc3   jmp    -61                            ; 0x30020a40

So far I don't have full understanding why that causes 35% slow down.
One note is that by minimizing number of taken branches we actually increase number of branch instruction in the loop what increases code size.
Moreover we increase number of branch instructions executed at runtime for old fall-through path and don't decrease it for all over paths.
While these two facts may negatively affect performance they don't explain 35% slowdown. Something more complicated happens behind the scene.

This example shows that this optimization is not always beneficial and requires more complicated profitability heuristic.

Any ideas?

[xbolva00]

Can you provide benchmark results from "public" ones like SPEC or LLVM test-suite? I think this should be mandatory to land performance critical patches (always provide results from SPEC/test suite).

If think it is not enough to land critical patches just because "we see an improvement in the internal benchmark" - either open source your benchmark or if not, please provide data from test-suite.

[xbolva00]

(should be probably reverted from 9.0 branch)

@hans

[davidxl]

Is the test case slow down with PGO or not? Also do you have branch misprediction perf data? (large slowdowns like this is usually triggered by side effect like this). Is there a trimmed down version to demonstrate the issue?

[ebrevnov]

In D43256#1591704, @davidxl wrote:

Is the test case slow down with PGO or not?

No, it's not PGO.

Also do you have branch misprediction perf data? (large slowdowns like this is usually triggered by side effect like this).

I do. There is no any branch/data/instruction miss predictions. LSD works 100% in both cases as well. Even after regression CPI is 0.3. That means we are execution bounded. If I run the benchmark under perf scores change a little and there is 19% difference instead of original 35%. About half of slowdown (8.3%) comes from increased path length due to extra jump instruction. Rest comes from CPI increase by 10%. I'm checking different hypotheses what could cause that but no success so far.

Is there a trimmed down version to demonstrate the issue?

It is a simple loop consequently reading floating points (non NANs) from two array and writing minimum value to a third array:

for (int i = 0; i < 320000; i++) {
   c[i] = min(a[i], b[i]);
}

[davidxl]

carrot, can you help looking into this? The cost model should look into extra direct jumps introduced as well.

[Carrot]

Evgeniy, could you try to build your code with FDO? The layout code is based on profile information, if that is not available, the static estimated profile information is used. Since the loaded values are not NaN, there should be no branch from loop header to latch, but the estimated profile gives it a non trivial value, so the latch is moved before header, and one taken branch is reduced in the NaN path. I think the static profile estimation can be enhanced to treat a floating point number as not a NaN, or as a NaN only with a very small possibility.

I tried to reproduce your result with

clang++ -O2 -c d43256.cc -save-temps

#include<algorithm>

#define N 320000

float a[N];
float b[N];
float c[N];

using namespace std;

void foo(int M) {

for (int i = 0; i < M; i++) {
 c[i] = min(a[i], b[i]);
}

}

But I got totally different code sequence. Could you help to give more complete reproduce steps?
Thanks a lot!

[hans]

In D43256#1591204, @xbolva00 wrote:

(should be probably reverted from 9.0 branch)

@hans

Thanks for the heads up; I'll keep an eye on this.

I'd prefer to see this either reverted or fixed on trunk, and then merge that to the 9.0 branch.

[ebrevnov]

Here is a C++ equivalent of my original code (which is actually java application) for you to reproduce.

clang++ -c -O2 floatmin.cpp -march=skylake

extern float a[];
extern float b[];
extern float c[];

bool foo(int M, bool flag) {
  for (int i = 0; i < M; i++) {
    float x = a[i];
    float y = b[i];
    float min;
    if (x != x) {
      min = x;   // a is NaN
    }
    else if (y == 0.0f) {
      goto fail;
    }
    else {
     min = (x <= y) ? x : y;
    }
    c[i] = min;
  }

  return true;
fail:
  return false;
}

With C++ reproducer I can measure about 9% slowdown only. In this case CPI is identical (for the original test case I still don't know root cause of CPI difference) and all slowdown comes from increased path length due to one extra jump.

With this reproducer on hands you can gather profile data if needed. But that's a separate story. I don't think we can afford such a regression when profile is not available.
You probably could assume worst case if profile is not available but I believe it won't help in this and root cause is that heuristic just doesn't take extra jump into account.

[Carrot]

Thanks for the test case, I can reproduce it now.

As I suspected, the problem is in BranchProbabilityAnalysis. For floating point unorder comparison, it estimates the probability as 12/32. While for loop exit, the probability is 3.1%. With these probability numbers, move the latch before header is beneficial. Unfortunately there is never NaN in the input.

Even for a normal program, the NaN possibility is extremely rare, we should give a much smaller number for the unordered comparison.

[Carrot]

ebrevnov, with following patch the test case can be layout correctly. Can you try it with your actual code?

Index: BranchProbabilityInfo.cpp

• BranchProbabilityInfo.cpp (revision 366821)

+++ BranchProbabilityInfo.cpp (working copy)
@@ -118,6 +118,12 @@
static const uint32_t FPH_TAKEN_WEIGHT = 20;
static const uint32_t FPH_NONTAKEN_WEIGHT = 12;

+/ This is the probability for an ordered floating point comparison.
+static const uint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1;
+/ This is the probability for an unordered floating point comparison, it means
+/ one or two of the operands are NaN, it should be extremely rare.
+static const uint32_t FPH_UNO_WEIGHT = 1;
+
/ Invoke-terminating normal branch taken weight
/
/ This is the weight for branching to the normal destination of an invoke
@@ -778,6 +784,8 @@

if (!FCmp)
  return false;

+ uint32_t TakenWeight = FPH_TAKEN_WEIGHT;
+ uint32_t NontakenWeight = FPH_NONTAKEN_WEIGHT;

bool isProb;
if (FCmp->isEquality()) {
  // f1 == f2 -> Unlikely

@@ -786,9 +794,13 @@

} else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
  // !isnan -> Likely
  isProb = true;

+ TakenWeight = FPH_ORD_WEIGHT;
+ NontakenWeight = FPH_UNO_WEIGHT;

} else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
  // isnan -> Unlikely
  isProb = false;

+ TakenWeight = FPH_ORD_WEIGHT;
+ NontakenWeight = FPH_UNO_WEIGHT;

} else {
  return false;
}

@@ -798,8 +810,7 @@

if (!isProb)
  std::swap(TakenIdx, NonTakenIdx);

• BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
• FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);

+ BranchProbability TakenProb(TakenWeight, TakenWeight + NontakenWeight);

setEdgeProbability(BB, TakenIdx, TakenProb);
setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
return true;

[ebrevnov]

Hi @Carrot,

I checked your patch on original test case and it does resolve the issue. Unfortunately, we have 4 other test cases regressed from 1% to 5%. Bad news is that we don't have sources for these cases. At glance they don't involve operations with floats. So that is not a surprise they are not affected. I can continue investigation and try to provide short reproducer if needed. My fear here is that original change touches very wide class of cases and we won't be able to fix all of them one by one (or it will take too much time). Can we think of a more realistic approach to deal with regressions?

Thanks
Evgeniy

[lebedev.ri]

Is this reverted (at least from 9.0, @hans) yet?

[hans]

In D43256#1600951, @lebedev.ri wrote:

Is this reverted (at least from 9.0, @hans) yet?

No. The preferred approach is to resolve on trunk first (reverting or fixing) and then merging that to the release branch.

It sounds like there is still discussion ongoing here. Perhaps it should be reverted on trunk in the meantime?

[davidxl]

I suspect other affected cases are due to bad static profile data too.

For now, I think the best way forward is to enable this transformation only when real profile data is available.

[Carrot]

@ebrevnov, it's better to provide a reproducer. Otherwise I can't analyze the problem that impacts your code. Four is not a big number.

[hans]

In D43256#1550842, @Carrot wrote:

In D43256#1545519, @samparker wrote:

Do you have any benchmark numbers to show that this is generally profitable? From our downstream testing, it is not clear that this change is beneficial.

We got performance improvement in our internal search benchmark.

How does this transformation impact the benchmark when not using profile data?

[Carrot]

In D43256#1602841, @hans wrote:

In D43256#1550842, @Carrot wrote:

In D43256#1545519, @samparker wrote:

Do you have any benchmark numbers to show that this is generally profitable? From our downstream testing, it is not clear that this change is beneficial.

We got performance improvement in our internal search benchmark.

How does this transformation impact the benchmark when not using profile data?

Benchmark is running, will report the result once it is finished.

[Carrot]

In D43256#1602841, @hans wrote:

In D43256#1550842, @Carrot wrote:

In D43256#1545519, @samparker wrote:

Do you have any benchmark numbers to show that this is generally profitable? From our downstream testing, it is not clear that this change is beneficial.

We got performance improvement in our internal search benchmark.

How does this transformation impact the benchmark when not using profile data?

In plain mode we also got performance improvement, the speedup is a little smaller than FDO Mode.

[ebrevnov]

In D43256#1601744, @Carrot wrote:

@ebrevnov, it's better to provide a reproducer. Otherwise I can't analyze the problem that impacts your code. Four is not a big number.

Four is not big, but who knows how many other cases will arise. I was looking to another case with ~%5 regression. As I mentioned, sources are not available for this case and I was not able to identify anything special just looking into assembler. As in previous case we have one extra jump which accounts for about 3.5% instructions of the loop. Here is an assembler for the loop after optimization:

23001bf40:   4c8975 movq    %r14, -72(%rbp)
23001bf44:   4c894d movq    %r9, -48(%rbp)
23001bf48:   48894d movq    %rcx, -56(%rbp)
23001bf4c:   4c8945 movq    %r8, -64(%rbp)
23001bf50:   48895d movq    %rbx, -80(%rbp)
23001bf54:   4889cf movq    %rcx, %rdi
23001bf57:   90     nop
23001bf58:   e863f1 callq    -69277                       ; 0x3000b0c0
23001bf5d:   4c8b75 movq    -72(%rbp), %r14
23001bf61:   488b4d movq    -56(%rbp), %rcx
23001bf65:   4c8b4d movq    -48(%rbp), %r9
23001bf69:   4c8b45 movq    -64(%rbp), %r8
23001bf6d:   48ffc3 incq    %rbx
23001bf70:   410fb6 movzbl    148(%r9), %eax
23001bf78:   84c0   testb    %al, %al
23001bf7a:   7572   jne    114                            ; 0x3001bfee
23001bf7c:   498b04 movq    (%r12), %rax
23001bf80:   498b55 movq    (%r13), %rdx
23001bf84:   4885c2 testq    %rax, %rdx
23001bf87:   751b   jne    27                             ; 0x3001bfa4
23001bf89:   488b78 movq    16(%rax), %rdi
23001bf8d:   4885fa testq    %rdi, %rdx
23001bf90:   7526   jne    38                             ; 0x3001bfb8
23001bf92:   f64708 testb    $1, 8(%rdi)            ; 0x3001bfd4
23001bf96:   be5f49 movl    $346463, %esi
23001bf9b:   74a3   je    -93                             ; 0x3001bf40
23001bf9d:   be8b10 movl    $4235, %esi
23001bfa2:   eb9c   jmp    -100                           ; 0x3001bf40

Thanks
Evgeniy

[ebrevnov]

In D43256#1604069, @Carrot wrote:

In D43256#1602841, @hans wrote:

In D43256#1550842, @Carrot wrote:

In D43256#1545519, @samparker wrote:

Do you have any benchmark numbers to show that this is generally profitable? From our downstream testing, it is not clear that this change is beneficial.

We got performance improvement in our internal search benchmark.

How does this transformation impact the benchmark when not using profile data?

In plain mode we also got performance improvement, the speedup is a little smaller than FDO Mode.

I have a general question/comment. By now it's more or less evident that benefit of optimization heavily depends on correctness of profile information. That means in general case there is no way to reason about its effectiveness. Thus I believe it should be turned off if there is no profile.

[Carrot]

In D43256#1605737, @ebrevnov wrote:

In D43256#1604069, @Carrot wrote:

In D43256#1602841, @hans wrote:

In D43256#1550842, @Carrot wrote:

In D43256#1545519, @samparker wrote:

Do you have any benchmark numbers to show that this is generally profitable? From our downstream testing, it is not clear that this change is beneficial.

We got performance improvement in our internal search benchmark.

How does this transformation impact the benchmark when not using profile data?

In plain mode we also got performance improvement, the speedup is a little smaller than FDO Mode.

I have a general question/comment. By now it's more or less evident that benefit of optimization heavily depends on correctness of profile information. That means in general case there is no way to reason about its effectiveness. Thus I believe it should be turned off if there is no profile.

The optimization decision is based on profile information, if a real profile is not available, the statically estimated profile information (generated by BranchProbabilityInfo.cpp) is used. So if an unreasonable probability is generated as in your first case, or if an user program has untypical run time behavior than BPI expected, it may make bad decision.
Since you have strong concern about the optimization without real profile information, I will restore the old behavior if no real profile information is available.

[ebrevnov]

In D43256#1606387, @Carrot wrote:

In D43256#1605737, @ebrevnov wrote:

In D43256#1604069, @Carrot wrote:

In D43256#1602841, @hans wrote:

In D43256#1550842, @Carrot wrote:

In D43256#1545519, @samparker wrote:

Do you have any benchmark numbers to show that this is generally profitable? From our downstream testing, it is not clear that this change is beneficial.

We got performance improvement in our internal search benchmark.

How does this transformation impact the benchmark when not using profile data?

In plain mode we also got performance improvement, the speedup is a little smaller than FDO Mode.

I have a general question/comment. By now it's more or less evident that benefit of optimization heavily depends on correctness of profile information. That means in general case there is no way to reason about its effectiveness. Thus I believe it should be turned off if there is no profile.

The optimization decision is based on profile information, if a real profile is not available, the statically estimated profile information (generated by BranchProbabilityInfo.cpp) is used. So if an unreasonable probability is generated as in your first case, or if an user program has untypical run time behavior than BPI expected, it may make bad decision.
Since you have strong concern about the optimization without real profile information, I will restore the old behavior if no real profile information is available.

I would suggest putting the optimization under an option and disable it by default for now. Once all problems are resolved we can change the default. What do you think?

[ebrevnov]

In D43256#1606387, @Carrot wrote:

In D43256#1605737, @ebrevnov wrote:

In D43256#1604069, @Carrot wrote:

In D43256#1602841, @hans wrote:

In D43256#1550842, @Carrot wrote:

In D43256#1545519, @samparker wrote:

Do you have any benchmark numbers to show that this is generally profitable? From our downstream testing, it is not clear that this change is beneficial.

We got performance improvement in our internal search benchmark.

How does this transformation impact the benchmark when not using profile data?

In plain mode we also got performance improvement, the speedup is a little smaller than FDO Mode.

I have a general question/comment. By now it's more or less evident that benefit of optimization heavily depends on correctness of profile information. That means in general case there is no way to reason about its effectiveness. Thus I believe it should be turned off if there is no profile.

The optimization decision is based on profile information, if a real profile is not available, the statically estimated profile information (generated by BranchProbabilityInfo.cpp) is used. So if an unreasonable probability is generated as in your first case, or if an user program has untypical run time behavior than BPI expected, it may make bad decision.
Since you have strong concern about the optimization without real profile information, I will restore the old behavior if no real profile information is available.

I took a deeper look at the second failing case and found something interesting. In fact, there is a profile information for the loop but it's incomplete. For example there is a profile data for the method entry, loop back edge and some other branches in the loop. Only two branches doesn't have profile. (You may wonder how it's possible. Original application is java program where profile typically available but may be unavailable for inlined methods). I think your heuristic makes wrong decision due to absence of profile for these two branches which were generated from one select instruction over boolean variable. In most cases you really can't statically estimate if boolean is false or true.

I think we need to be conservative and don't account for potential benefit from branches with out representative profile.

Thanks
Evgeniy

[Carrot]

In D43256#1607733, @ebrevnov wrote:

I would suggest putting the optimization under an option and disable it by default for now. Once all problems are resolved we can change the default. What do you think?

After restore to original behavior in plain mode, you can use -force-precise-rotation-cost=true to use this more aggressive loop layout.

[hans]

In D43256#1608459, @Carrot wrote:

In D43256#1607733, @ebrevnov wrote:

I would suggest putting the optimization under an option and disable it by default for now. Once all problems are resolved we can change the default. What do you think?

After restore to original behavior in plain mode, you can use -force-precise-rotation-cost=true to use this more aggressive loop layout.

Is there a patch in progress for restoring to the original behaviour in non-profile mode? It would be nice if we could get this resolved soon.

[Carrot]

In D43256#1609742, @hans wrote:

In D43256#1608459, @Carrot wrote:

In D43256#1607733, @ebrevnov wrote:

I would suggest putting the optimization under an option and disable it by default for now. Once all problems are resolved we can change the default. What do you think?

After restore to original behavior in plain mode, you can use -force-precise-rotation-cost=true to use this more aggressive loop layout.

Is there a patch in progress for restoring to the original behaviour in non-profile mode? It would be nice if we could get this resolved soon.

Yes, some new added or modified test cases after this patch need to be adjusted. The new patch can be ready tomorrow.

[Carrot]

Patch https://reviews.llvm.org/D65673 for restoring the original layout in plain mode.

[• hjagasia]

We are also seeing this patch slow down one of our internal benchmarks and speed up another one on the Qualcomm Hexagon target.
In both cases the static estimated profile is used - and the static profile is representative. In both cases D43256 basically lays outs executed hot code closer together improving cache utilization. However in both cases we see critical path length and the number of jumps in the critical path increase. So a precise cost model is a good idea. We spent some time analyzing why one benchmark got worse - we can see more mispredicts - but there may be more going on under the hood.
The other benchmark that speeds up - we see the new layout lowers pressure on an internal branch target hardware resource - the critical loop has a lot of calls that have already increased pressure on that resource.
We dont have sources for these benchmarks.

We have verified that D65673 restores the old behavior on the benchmark that got worse and throwing the flag -force-precise-rotation-cost=true helps us keep the improvement on the other one.

[Carrot]

@hjagasia, thank you for the verification.

[hans]

In D43256#1612903, @Carrot wrote:

Patch https://reviews.llvm.org/D65673 for restoring the original layout in plain mode.

I see that this was committed in r368339. I will merge that to the release branch once it's baked in trunk for a little while.

[hans]

In D43256#1622622, @hans wrote:

In D43256#1612903, @Carrot wrote:

Patch https://reviews.llvm.org/D65673 for restoring the original layout in plain mode.

I see that this was committed in r368339. I will merge that to the release branch once it's baked in trunk for a little while.

That was reverted in r368579 since it broke the Chromium build.

@Carrot: Can you please prioritize this so we can get it fixed in time for the LLVM 9 release?

[• hjagasia]

@Carrot: Any update on this? We have slow downs on our benchmarks because of this as mentioned earlier.

[xbolva00]

@hans this patch should be reverted from 9.0 I think so rc3 is “fixed”.

[hans]

In D43256#1639810, @xbolva00 wrote:

@hans this patch should be reverted from 9.0 I think so rc3 is “fixed”.

I'd rather see the fix land on trunk first (reverting on the branch is also not trivial, there are merge conflicts in several test files). From the discussion at http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20190819/686087.html, it should be ready to go in again.

[xbolva00]

Ok, thanks! I didnt know there is a working fix.

[Carrot]

In D43256#1641056, @hans wrote:

In D43256#1639810, @xbolva00 wrote:

@hans this patch should be reverted from 9.0 I think so rc3 is “fixed”.

I'd rather see the fix land on trunk first (reverting on the branch is also not trivial, there are merge conflicts in several test files). From the discussion at http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20190819/686087.html, it should be ready to go in again.

It is committed as r369664.

[hans]

In D43256#1641893, @Carrot wrote:

In D43256#1641056, @hans wrote:

In D43256#1639810, @xbolva00 wrote:

@hans this patch should be reverted from 9.0 I think so rc3 is “fixed”.

I'd rather see the fix land on trunk first (reverting on the branch is also not trivial, there are merge conflicts in several test files). From the discussion at http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20190819/686087.html, it should be ready to go in again.

It is committed as r369664.

I see there is a follow-up comment on the commit email saying it fails in the verifier.

I think at this point, we're too close to the llvm 9 release to take this. Hopefully it can get fixed and stabilized on trunk, and then be merged to llvm 9.0.1.

[xbolva00]

Maybe not worth to revert it even from 9.0.1

This commit (see below) says that disabling this new feature regressed many benchmarks. So probably it is okay to leave it as is, possibly tune heuristic a bit.

Anyway, in static profile some code perf improves, some regresses - but if this patch improves a lot of code, we shouldn’t disable it because some people have few regressions..)

https://reviews.llvm.org/rGf9f81289e6864ca3f09df16bad0ffc3ca58c3162#684441

[GalZohar]

Hi,
Seems like this is supposed to increase the average number of fallthrough in a case of simple nested loops, however it seems to also increase the total number of branch instructions both in and outside the outer loop.
In our target this seems to do more harm than good as increasing the number of branches is significantly more harmful than having more conditional taken branches.
Instead of a conditional branch that is usually taken and jumps from end to start of outer loop, we have an unconditional branch that jumps from the end of the inner loop to the end of the outer loop, which then conditionally jumps out of the outer loop or falls through to the next iteration of the outer loop.
This increases the total number of executed branch instructions by 1.

Did I understand this correctly?

Is there a way to tweak this optimization to avoid generating additional branches? Or would this mean completely disabling it for targets that don't benefit from additional fallthroughs when it comes at the cost of additional branches?

Thanks

[Carrot]

@GalZohar, the various layout algorithms in MachineBlockPlacement mainly consider the number of fall-throughs and dynamic number of branch instructions (usually they are consistent) according to branch probabilities. So you can try to build your application with profiling. Or you can compile this file with -Os since the improvement in this patch is disabled with -Os.

[GalZohar]

In D43256#2480636, @Carrot wrote:

@GalZohar, the various layout algorithms in MachineBlockPlacement mainly consider the number of fall-throughs and dynamic number of branch instructions (usually they are consistent) according to branch probabilities. So you can try to build your application with profiling. Or you can compile this file with -Os since the improvement in this patch is disabled with -Os.

In the simple example I have the number of branches executed when running the most common control flow path is increased by 1 due to this transformation.
Seems like in nested loops, where the outer-loop latch is moved to fall through into the outer-loop head, then the inner loop needs an additional exit branch, which increases the number of dynamic branches by 1 for every outer-loop iteration that also executes the inner loop. Is this intentional?
Disabling this completely degrades performance in some more complex examples where the total number of branches is not increased and therefore this optimization is beneficial. I would prefer to keep this when the number of branches isn't increased but skip it otherwise, like the nested loop example above.
I'm not sure how profiling would help my situation, as it seems like the number of branches may be increased regardless of block frequency values, as there's 1 path that executes an extra branch instruction.

[Carrot]

@GalZohar, without a testcase I can't say what's the problem.

It is not intentional to increase the number of branches of any particular path. All of the algorithms are driven by branch probabilities. If you didn't collect profiling, llvm guesses a probability for each branch, it's reasonable for most code. But it's not rare that the guessed probability is different from actual probability, it may not result in a good layout.

So I strongly suggest you try profiling build. MBP is one of the passes that get most performance improvement from profiling.

[GalZohar]

In D43256#2487302, @Carrot wrote:

@GalZohar, without a testcase I can't say what's the problem.

It is not intentional to increase the number of branches of any particular path. All of the algorithms are driven by branch probabilities. If you didn't collect profiling, llvm guesses a probability for each branch, it's reasonable for most code. But it's not rare that the guessed probability is different from actual probability, it may not result in a good layout.

So I strongly suggest you try profiling build. MBP is one of the passes that get most performance improvement from profiling.

While we hope to eventually support profiling builds, we must also optimize in the best way possible without profiling.
We have a very simple case where profiling shouldn't be needed. I think this would be the optimal layout:

BB1 (Entry) -> BB2, BB5
BB2 -> BB3, BB4
BB3 -> BB3, BB4
BB4 ->BB2, BB5
BB5 (Exit)

This way all blocks (except exit) have a single branch instruction.
With this optimization BB4 is moved before BB2, which results in an additional branch from BB3 to BB4 which wasn't needed before (BB3 had only a single branch, and will now need 2). All other blocks still have a single branch after. BB1 also gets an additional branch instruction, but that is acceptable as it's outside the loop.

Is this something that is intentional or is something broken with the frequencies? Assuming this is intended, I still don't understand how this transformation is good regardless of frequencies, assuming number of branches is always more important than number of fallthroughs.

[Carrot]

@GalZohar, thanks for the example, now I understand your problem. The new layout does increase the number of executed branches for the path BB2->BB3->BB4->BB2. Unfortunately most of the current MBP algorithms don't consider this factor. When considering the number of fall through only, the new layout has more fall through and less taken branch.

Since the number of executed branches does has performance impact on your target, so welcome to enhance MBP to include this factor on related targets.

[GalZohar]

In D43256#2494925, @Carrot wrote:

@GalZohar, thanks for the example, now I understand your problem. The new layout does increase the number of executed branches for the path BB2->BB3->BB4->BB2. Unfortunately most of the current MBP algorithms don't consider this factor. When considering the number of fall through only, the new layout has more fall through and less taken branch.

Since the number of executed branches does has performance impact on your target, so welcome to enhance MBP to include this factor on related targets.

Is this a general problem with MBP then? I haven't noticed it before this optimization, but maybe it was just luck or not investigating the right examples. I'm trying to understand where is the best place to fix it, and if it's even feasible.

[Carrot]

Is this a general problem with MBP then? I haven't noticed it before this optimization, but maybe it was just luck or not investigating the right examples. I'm trying to understand where is the best place to fix it, and if it's even feasible.

Mostly, there is only one function considering extra jump instruction rotateLoopWithProfile, but it is not called by default.

lib/CodeGen/MachineBlockPlacement.cpp

#endif
   /// present in the set will be added to the worklist. If nullptr
   /// is provided, no filtering occurs.
   void fillWorkLists(const MachineBasicBlock *MBB,
                      SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
                      const BlockFilterSet *BlockFilter);
 
   void buildChain(const MachineBasicBlock *BB, BlockChain &Chain,
                   BlockFilterSet *BlockFilter = nullptr);
+  bool canMoveBottomBlockToTop(const MachineBasicBlock *BottomBlock,
+                               const MachineBasicBlock *OldTop);
+  bool hasRarePredecessors(const MachineBasicBlock *Latch,
+                           const MachineBasicBlock *Exit);
+  MachineBasicBlock *findBestLoopTopHelper(MachineBasicBlock *OldTop,
+      const MachineLoop &L, const BlockFilterSet &LoopBlockSet);
   MachineBasicBlock *findBestLoopTop(
       const MachineLoop &L, const BlockFilterSet &LoopBlockSet);
   MachineBasicBlock *findBestLoopExit(
       const MachineLoop &L, const BlockFilterSet &LoopBlockSet);
   BlockFilterSet collectLoopBlockSet(const MachineLoop &L);
   void buildLoopChains(const MachineLoop &L);
   void rotateLoop(
       BlockChain &LoopChain, const MachineBasicBlock *ExitingBB,
while (true) {
     Chain.merge(BestSucc, &SuccChain);
     BB = *std::prev(Chain.end());
   }
 
   DEBUG(dbgs() << "Finished forming chain for header block "
                << getBlockName(*Chain.begin()) << "\n");
 }
 
-/// \brief Find the best loop top block for layout.
+// If bottom of block BB has only one successor OldTop, in most cases it is
+// profitable to move it before OldTop, except the following case:
+//
+//     -->OldTop<-
+//     |    .    |
+//     |    .    |
+//     |    .    |
+//     ---Pred   |
+//          |    |
+//         BB-----
+//
+// If BB is moved before OldTop, Pred needs a taken branch to BB, and it can't
+// layout the other successor below it, so it can't reduce taken branch.
+// In this case we keep its original layout.
+bool
+MachineBlockPlacement::canMoveBottomBlockToTop(
+    const MachineBasicBlock *BottomBlock,
+    const MachineBasicBlock *OldTop) {
+  if (BottomBlock->pred_size() != 1)
+    return true;
+  MachineBasicBlock *Pred = *BottomBlock->pred_begin();
+  if (Pred->succ_size() != 2)
+    return true;
+
+  MachineBasicBlock *OtherBB = *Pred->succ_begin();
+  if (OtherBB == BottomBlock)
+    OtherBB = *Pred->succ_rbegin();
+  if (OtherBB == OldTop)
+    return false;
+
+  return true;
+}
+
+// Check if the latch block has rarer predecessors than exit block.
+// The rare predecessors is defined as the total predecessor frequency minus
+// the max predecessor frequency. It is the number of reduced taken branches
+// when move the latch to the top of loop.
+// In other words, this method checks if the reduced taken branches is less
+// than increased taken branch (to the exit block when rotation happens).
+// If yes, it returns true.
+bool
+MachineBlockPlacement::hasRarePredecessors(const MachineBasicBlock *Latch,
+                                           const MachineBasicBlock *Exit)
+{
+  BlockFrequency MaxPredFreq;
+  BlockFrequency TotalPredFreq;
+  for (MachineBasicBlock *Pred : Latch->predecessors()) {
+    BlockFrequency PredFreq = MBFI->getBlockFreq(Pred);
+    TotalPredFreq += PredFreq;
+    if (PredFreq > MaxPredFreq)
+      MaxPredFreq = PredFreq;
+  }
+  BlockFrequency ReducedBranches = TotalPredFreq - MaxPredFreq;
+  BlockFrequency ExitFreq = MBFI->getBlockFreq(Exit);
+  return ReducedBranches < ExitFreq;
+}
+
+/// \brief Helper function of findBestLoopTop. Find the best loop top block
+/// from predecessors of old top.
+///
+/// Look for a block which is strictly better than the old top for laying
+/// out before the old top of the loop. This looks for only two patterns:
+///
+///     1. a block has only one successor, the old loop top
+///
+///        Because such a block will always result in an unconditional jump,
+///        rotating it in front of the old top is always profitable.
+///
+///     2. a block has two successors, one is old top, another is exit
+///        and it has more than one predecessors
 ///
-/// Look for a block which is strictly better than the loop header for laying
-/// out at the top of the loop. This looks for one and only one pattern:
-/// a latch block with no conditional exit. This block will cause a conditional
-/// jump around it or will be the bottom of the loop if we lay it out in place,
-/// but if it it doesn't end up at the bottom of the loop for any reason,
-/// rotation alone won't fix it. Because such a block will always result in an
-/// unconditional jump (for the backedge) rotating it in front of the loop
-/// header is always profitable.
+///        If it is below one of its predecessors P, only P can fall through to
+///        it, all other predecessors need a jump to it, and another conditional
+///        jump to loop header. If it is moved before loop header, all its
+///        predecessors jump to it, then fall through to loop header. So all its
+///        predecessors except P can reduce one taken branch.
+///        At the same time, move it before old top increases the taken branch
+///        to loop exit block, so the reduced taken branch will be compared with
+///        the increased taken branch to the loop exit block.
 MachineBasicBlock *
-MachineBlockPlacement::findBestLoopTop(const MachineLoop &L,
-                                       const BlockFilterSet &LoopBlockSet) {
+MachineBlockPlacement::findBestLoopTopHelper(
+    MachineBasicBlock *OldTop,
+    const MachineLoop &L,
   // Placing the latch block before the header may introduce an extra branch
   // that skips this block the first time the loop is executed, which we want
   // to avoid when optimising for size.
   // FIXME: in theory there is a case that does not introduce a new branch,
   // i.e. when the layout predecessor does not fallthrough to the loop header.
   // In practice this never happens though: there always seems to be a preheader
   // that can fallthrough and that is also placed before the header.
   if (F->getFunction().optForSize())
-    return L.getHeader();
+    return OldTop;
 
   // Check that the header hasn't been fused with a preheader block due to
   // crazy branches. If it has, we need to start with the header at the top to
   // prevent pulling the preheader into the loop body.
-  BlockChain &HeaderChain = *BlockToChain[L.getHeader()];
+  BlockChain &HeaderChain = *BlockToChain[OldTop];
   if (!LoopBlockSet.count(*HeaderChain.begin()))
-    return L.getHeader();
+    return OldTop;
 
-  DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(L.getHeader())
+  DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(OldTop)
                << "\n");
 
   BlockFrequency BestPredFreq;
   MachineBasicBlock *BestPred = nullptr;
-  for (MachineBasicBlock *Pred : L.getHeader()->predecessors()) {
+  for (MachineBasicBlock *Pred : OldTop->predecessors()) {
     if (!LoopBlockSet.count(Pred))
       continue;
+    if (Pred == L.getHeader())
+      continue;
     DEBUG(dbgs() << "    header pred: " << getBlockName(Pred) << ", has "
                  << Pred->succ_size() << " successors, ";
           MBFI->printBlockFreq(dbgs(), Pred) << " freq\n");
-    if (Pred->succ_size() > 1)
+    if (Pred->succ_size() > 2)
+      continue;
+
+    if (Pred->succ_size() == 2) {
+      // The candidate should have an exit edge.
+      MachineBasicBlock *OutBB = *Pred->succ_begin();
+      if (OutBB == OldTop)
+        OutBB = *Pred->succ_rbegin();
+      if (LoopBlockSet.count(OutBB))
+        continue;
+
+      // It must have more than 1 predecessors.
+      if (Pred->pred_size() == 1)
+        continue;
+
+      // Move the candidate to top must reduce taken branches.
+      if (hasRarePredecessors(Pred, OutBB))
+        continue;
+    } else
+      // OldTop is the only successor of Pred.
+      if (!canMoveBottomBlockToTop(Pred, OldTop))
         continue;
 
     BlockFrequency PredFreq = MBFI->getBlockFreq(Pred);
     if (!BestPred || PredFreq > BestPredFreq ||
         (!(PredFreq < BestPredFreq) &&
-         Pred->isLayoutSuccessor(L.getHeader()))) {
+         Pred->isLayoutSuccessor(OldTop))) {
       BestPred = Pred;
       BestPredFreq = PredFreq;
     }
   }
 
   // If no direct predecessor is fine, just use the loop header.
   if (!BestPred) {
     DEBUG(dbgs() << "    final top unchanged\n");
-    return L.getHeader();
+    return OldTop;
   }
 
   // Walk backwards through any straight line of predecessors.
   while (BestPred->pred_size() == 1 &&
          (*BestPred->pred_begin())->succ_size() == 1 &&
          *BestPred->pred_begin() != L.getHeader())
     BestPred = *BestPred->pred_begin();
 
   DEBUG(dbgs() << "    final top: " << getBlockName(BestPred) << "\n");
   return BestPred;
 }
 
+/// \brief Find the best loop top block for layout.
+///
+/// This function iteratively calls findBestLoopTopHelper, until no new better
+/// BB can be found.
+MachineBasicBlock *
+MachineBlockPlacement::findBestLoopTop(const MachineLoop &L,
+                                       const BlockFilterSet &LoopBlockSet) {
+  MachineBasicBlock *OldTop = nullptr;
+  MachineBasicBlock *NewTop = L.getHeader();
+  while (NewTop != OldTop) {
+    OldTop = NewTop;
+    NewTop = findBestLoopTopHelper(OldTop, L, LoopBlockSet);
+    if (NewTop != OldTop)
+      ComputedEdges[NewTop] = { OldTop, false };
+  }
+  return NewTop;
+}
+
 /// \brief Find the best loop exiting block for layout.
 ///
 /// This routine implements the logic to analyze the loop looking for the best
 /// block to layout at the top of the loop. Typically this is done to maximize
 /// fallthrough opportunities.
 MachineBasicBlock *
 MachineBlockPlacement::findBestLoopExit(const MachineLoop &L,
                                         const BlockFilterSet &LoopBlockSet) {

test/CodeGen/AArch64/neg-imm.ll

-; RUN: llc -mtriple=aarch64-linux-gnu -verify-machineinstrs -o - %s | FileCheck %s
+; RUN: llc -mtriple=aarch64-linux-gnu -verify-machineinstrs -disable-block-placement -o - %s | FileCheck %s
 ; LSR used to pick a sub-optimal solution due to the target responding
 ; conservatively to isLegalAddImmediate for negative values.
 
 declare void @foo(i32)
 
 define void @test(i32 %px) {
 ; CHECK_LABEL: test:
 ; CHECK_LABEL: %entry

test/CodeGen/AArch64/tailmerging_in_mbp.ll

 ; RUN: llc <%s -mtriple=aarch64-eabi -verify-machine-dom-info | FileCheck %s
 
 ; CHECK-LABEL: test:
-; CHECK:       LBB0_7:
-; CHECK:         b.hi 
-; CHECK-NEXT:    b  
+; CHECK-LABEL: %cond.false12.i
+; CHECK:         b.gt 
 ; CHECK-NEXT:  LBB0_8:
 ; CHECK-NEXT:    mov   x8, x9
 ; CHECK-NEXT:  LBB0_9:
 define i64 @test(i64 %n, i64* %a, i64* %b, i64* %c, i64* %d, i64* %e, i64* %f) {
 entry:
   %cmp28 = icmp sgt i64 %n, 1
   br i1 %cmp28, label %for.body, label %for.end
 

test/CodeGen/AMDGPU/collapse-endcf.ll

 bb.end:                                           ; preds = %bb.then, %bb
   call void @llvm.amdgcn.s.barrier()
   ret void
 }
 
 ; Make sure scc liveness is updated if sor_b64 is removed
 ; GCN-LABEL: {{^}}scc_liveness:
 
+; GCN: %bb10
+; GCN: s_or_b64 exec, exec, s{{\[[0-9]+:[0-9]+\]}}
+; GCN: s_andn2_b64
+; GCN-NEXT: s_cbranch_execz
+
 ; GCN: [[BB1_LOOP:BB[0-9]+_[0-9]+]]:
 ; GCN: s_andn2_b64 exec, exec,
 ; GCN-NEXT: s_cbranch_execnz [[BB1_LOOP]]
 
 ; GCN: buffer_load_dword v{{[0-9]+}}, v{{[0-9]+}}, s{{\[[0-9]+:[0-9]+\]}}, s{{[0-9]+}} offen
 ; GCN: s_and_b64 exec, exec, vcc
 
 ; GCN-NOT: s_or_b64 exec, exec
 
 ; GCN: s_or_b64 exec, exec, s{{\[[0-9]+:[0-9]+\]}}
-; GCN: s_andn2_b64
-; GCN-NEXT: s_cbranch_execnz
-
-; GCN: s_or_b64 exec, exec, s{{\[[0-9]+:[0-9]+\]}}
 ; GCN: buffer_store_dword
 ; GCN: buffer_store_dword
 ; GCN: buffer_store_dword
 ; GCN: buffer_store_dword
 ; GCN: s_setpc_b64
 define void @scc_liveness(i32 %arg) local_unnamed_addr #0 {
 bb:
   br label %bb1

test/CodeGen/AMDGPU/global_smrd_cfg.ll

 ; RUN: llc -mtriple amdgcn--amdhsa -mcpu=fiji -amdgpu-scalarize-global-loads=true -verify-machineinstrs  < %s | FileCheck %s
 
-; CHECK-LABEL: %bb11
+; CHECK-LABEL: %bb22
 
-; Load from %arg in a Loop body has alias store
+; Load from %arg has alias store in Loop
 
 ; CHECK: flat_load_dword
 
-; CHECK-LABEL: %bb20
-; CHECK: flat_store_dword
+; #####################################################################
+
+; Load from %arg1 has no-alias store in Loop - arg1[i+1] never alias arg1[i]
+
+; CHECK: s_load_dword
 
 ; #####################################################################
 
-; CHECK-LABEL: %bb22
+; CHECK-LABEL: %bb11
 
-; Load from %arg has alias store in Loop
+; Load from %arg in a Loop body has alias store
 
 ; CHECK: flat_load_dword
 
-; #####################################################################
-
-; Load from %arg1 has no-alias store in Loop - arg1[i+1] never alias arg1[i]
+; CHECK-LABEL: %bb20
 
-; CHECK: s_load_dword
+; CHECK: flat_store_dword
 
 define amdgpu_kernel void @cfg(i32 addrspace(1)* nocapture readonly %arg, i32 addrspace(1)* nocapture %arg1, i32 %arg2) #0 {
 bb:
   %tmp = sext i32 %arg2 to i64
   %tmp3 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i64 %tmp
   %tmp4 = load i32, i32 addrspace(1)* %tmp3, align 4, !tbaa !0
   %tmp5 = icmp sgt i32 %tmp4, 0
   br i1 %tmp5, label %bb6, label %bb8

test/CodeGen/AMDGPU/hoist-cond.ll

-; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck %s
+; RUN: llc -march=amdgcn -verify-machineinstrs -disable-block-placement < %s | FileCheck %s
 
 ; Check that invariant compare is hoisted out of the loop.
 ; At the same time condition shall not be serialized into a VGPR and deserialized later
 ; using another v_cmp + v_cndmask, but used directly in s_and_saveexec_b64.
 
 ; CHECK: v_cmp_{{..}}_u32_e{{32|64}} [[COND:s\[[0-9]+:[0-9]+\]|vcc]]
 ; CHECK: BB0_1:
 ; CHECK-NOT: v_cmp

test/CodeGen/AMDGPU/loop_break.ll

 ; RUN: opt -mtriple=amdgcn-- -S -structurizecfg -si-annotate-control-flow %s | FileCheck -check-prefix=OPT %s
-; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
+; RUN: llc -march=amdgcn -verify-machineinstrs -disable-block-placement < %s | FileCheck -check-prefix=GCN %s
 
 ; Uses llvm.amdgcn.break
 
 ; OPT-LABEL: @break_loop(
 ; OPT: bb1:
 ; OPT: call i64 @llvm.amdgcn.break(i64
 ; OPT-NEXT: br i1 %cmp0, label %bb4, label %Flow
 

test/CodeGen/AMDGPU/madmk.ll

define amdgpu_kernel void @madmk_add_inline_imm_f32(float addrspace(1)* noalias %out, float addrspace(1)* noalias %in) nounwind {
 
   %mul = fmul float %a, 10.0
   %madmk = fadd float %mul, 2.0
   store float %madmk, float addrspace(1)* %out.gep, align 4
   ret void
 }
 
 ; SI-LABEL: {{^}}kill_madmk_verifier_error:
+; SI: s_or_b64
 ; SI: s_xor_b64
 ; SI: v_mac_f32_e32 {{v[0-9]+}}, 0x472aee8c, {{v[0-9]+}}
-; SI: s_or_b64
 define amdgpu_kernel void @kill_madmk_verifier_error() nounwind {
 bb:
   br label %bb2
 
 bb1:                                              ; preds = %bb2
   ret void
 
 bb2:                                              ; preds = %bb6, %bb

test/CodeGen/AMDGPU/multilevel-break.ll

 ; RUN: opt -S -mtriple=amdgcn-- -structurizecfg -si-annotate-control-flow < %s | FileCheck -check-prefix=OPT %s
-; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
+; RUN: llc -march=amdgcn -verify-machineinstrs -disable-block-placement < %s | FileCheck -check-prefix=GCN %s
 
 ; OPT-LABEL: {{^}}define amdgpu_vs void @multi_else_break(
 ; OPT: main_body:
 ; OPT: LOOP.outer:
 ; OPT: LOOP:
 ; OPT:     [[if:%[0-9]+]] = call { i1, i64 } @llvm.amdgcn.if(
 ; OPT:     [[if_exec:%[0-9]+]] = extractvalue { i1, i64 } [[if]], 1
 ;

test/CodeGen/AMDGPU/valu-i1.ll

-; RUN: llc -march=amdgcn -verify-machineinstrs -enable-misched -asm-verbose < %s | FileCheck -check-prefix=SI %s
+; RUN: llc -march=amdgcn -verify-machineinstrs -enable-misched -asm-verbose -disable-block-placement < %s | FileCheck -check-prefix=SI %s
 
 declare i32 @llvm.amdgcn.workitem.id.x() nounwind readnone
 
 ; SI-LABEL: {{^}}test_if:
 ; Make sure the i1 values created by the cfg structurizer pass are
 ; moved using VALU instructions
 
 

test/CodeGen/ARM/code-placement.ll

 ; rdar://8117827
 define i32 @t2(i32 %passes, i32* nocapture %src, i32 %size) nounwind readonly {
 entry:
 ; CHECK-LABEL: t2:
   %0 = icmp eq i32 %passes, 0                     ; <i1> [#uses=1]
   br i1 %0, label %bb5, label %bb.nph15
 
 bb1:                                              ; preds = %bb2.preheader, %bb1
+; CHECK: LBB1_[[BB3:.]]: @ %bb3
 ; CHECK: LBB1_[[PREHDR:.]]: @ %bb2.preheader
-; CHECK: blt LBB1_[[BB3:.]]
+; CHECK: blt LBB1_[[BB3]]
   %indvar = phi i32 [ %indvar.next, %bb1 ], [ 0, %bb2.preheader ] ; <i32> [#uses=2]
   %sum.08 = phi i32 [ %2, %bb1 ], [ %sum.110, %bb2.preheader ] ; <i32> [#uses=1]
   %tmp17 = sub i32 %i.07, %indvar                 ; <i32> [#uses=1]
   %scevgep = getelementptr i32, i32* %src, i32 %tmp17  ; <i32*> [#uses=1]
   %1 = load i32, i32* %scevgep, align 4                ; <i32> [#uses=1]
   %2 = add nsw i32 %1, %sum.08                    ; <i32> [#uses=2]
   %indvar.next = add i32 %indvar, 1               ; <i32> [#uses=2]
   %exitcond = icmp eq i32 %indvar.next, %size     ; <i1> [#uses=1]
   br i1 %exitcond, label %bb3, label %bb1
 
 bb3:                                              ; preds = %bb1, %bb2.preheader
 ; CHECK: LBB1_[[BB1:.]]: @ %bb1
 ; CHECK: bne LBB1_[[BB1]]
-; CHECK: LBB1_[[BB3]]: @ %bb3
   %sum.0.lcssa = phi i32 [ %sum.110, %bb2.preheader ], [ %2, %bb1 ] ; <i32> [#uses=2]
   %3 = add i32 %pass.011, 1                       ; <i32> [#uses=2]
   %exitcond18 = icmp eq i32 %3, %passes           ; <i1> [#uses=1]
   br i1 %exitcond18, label %bb5, label %bb2.preheader
 
 bb.nph15:                                         ; preds = %entry
   %i.07 = add i32 %size, -1                       ; <i32> [#uses=2]
   %4 = icmp sgt i32 %i.07, -1                     ; <i1> [#uses=1]

test/CodeGen/ARM/swifterror.ll

 ; CHECK-APPLE: mov [[CODE:r[0-9]+]], r0
 ; swifterror is kept in a register
 ; CHECK-APPLE: cmp [[CODE]], #0
 ; CHECK-APPLE: beq
 ; CHECK-APPLE: mov r0, #16
 ; CHECK-APPLE: malloc
 ; CHECK-APPLE: mov r8, r0
 ; CHECK-APPLE: strb r{{.*}}, [r8, #8]
-; CHECK-APPLE: ble
+; CHECK-APPLE: b
 
 ; CHECK-O0-LABEL: foo_loop:
 ; CHECK-O0: mov r{{.*}}, r8
 ; CHECK-O0: cmp r{{.*}}, #0
 ; CHECK-O0: beq
 ; CHECK-O0-DAG: movw r{{.*}}, #1
 ; CHECK-O0-DAG: mov r{{.*}}, #16
 ; CHECK-O0: malloc

test/CodeGen/PowerPC/cmp_elimination.ll

 if.end:
   ret void
 }
 
 ; partially redundant case
 define void @func28(i32 signext %a) {
 ; CHECK-LABEL: @func28
 ; CHECK: cmplwi  [[REG1:[0-9]+]], [[REG2:[0-9]+]]
-; CHECK: .[[LABEL1:[A-Z0-9_]+]]:
+; CHECK: .[[LABEL2:[A-Z0-9_]+]]:
+; CHECK: cmpwi   [[REG1]], [[REG2]]
+; CHECK: ble     0, .[[LABEL1:[A-Z0-9_]+]]
 ; CHECK-NOT: cmp
-; CHECK: bne   0, .[[LABEL2:[A-Z0-9_]+]]
+; CHECK: bne     0, .[[LABEL2]]
 ; CHECK: bl dummy1
-; CHECK: .[[LABEL2]]:
-; CHECK: cmpwi   [[REG1]], [[REG2]]
-; CHECK: bgt   0, .[[LABEL1]]
+; CHECK: b .[[LABEL2]]
+; CHECK: .[[LABEL1]]:
 ; CHECK: blr
 entry:
   br label %do.body
 
 do.body:
   %a.addr.0 = phi i32 [ %a, %entry ], [ %call, %if.end ]
   %cmp = icmp eq i32 %a.addr.0, 0
   br i1 %cmp, label %if.then, label %if.end

test/CodeGen/PowerPC/licm-remat.ll

 
 define linkonce_odr void @ZN6snappyDecompressor_(%"class.snappy::SnappyDecompressor"* %this, %"class.snappy::SnappyIOVecWriter"* %writer) {
 ; CHECK-LABEL: ZN6snappyDecompressor_:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK:       addis 3, 2, _ZN6snappy8internalL8wordmaskE@toc@ha
 ; CHECK-DAG:   addi 25, 3, _ZN6snappy8internalL8wordmaskE@toc@l
 ; CHECK-DAG:   addis 5, 2, _ZN6snappy8internalL10char_tableE@toc@ha
 ; CHECK-DAG:   addi 24, 5, _ZN6snappy8internalL10char_tableE@toc@l
-; CHECK:       b .LBB0_2
-; CHECK:       .LBB0_2: # %for.cond
+; CHECK:       b .[[LABEL1:[A-Z0-9_]+]]
+; CHECK:       .[[LABEL1]]: # %for.cond
 ; CHECK-NOT:   addis {{[0-9]+}}, 2, _ZN6snappy8internalL8wordmaskE@toc@ha
 ; CHECK-NOT:   addis {{[0-9]+}}, 2, _ZN6snappy8internalL10char_tableE@toc@ha
 ; CHECK:       bctrl
 entry:
   %ip_limit_ = getelementptr inbounds %"class.snappy::SnappyDecompressor", %"class.snappy::SnappyDecompressor"* %this, i64 0, i32 2
   %0 = bitcast i8** %ip_limit_ to i64*
   %curr_iov_index_.i = getelementptr inbounds %"class.snappy::SnappyIOVecWriter", %"class.snappy::SnappyIOVecWriter"* %writer, i64 0, i32 2
   %curr_iov_written_.i = getelementptr inbounds %"class.snappy::SnappyIOVecWriter", %"class.snappy::SnappyIOVecWriter"* %writer, i64 0, i32 3

test/CodeGen/SystemZ/atomicrmw-minmax-01.ll

 ; Test 8-bit atomic min/max operations.
 ;
-; RUN: llc < %s -mtriple=s390x-linux-gnu | FileCheck %s
-; RUN: llc < %s -mtriple=s390x-linux-gnu | FileCheck %s -check-prefix=CHECK-SHIFT1
-; RUN: llc < %s -mtriple=s390x-linux-gnu | FileCheck %s -check-prefix=CHECK-SHIFT2
+; RUN: llc < %s -mtriple=s390x-linux-gnu -disable-block-placement | FileCheck %s
+; RUN: llc < %s -mtriple=s390x-linux-gnu -disable-block-placement | FileCheck %s -check-prefix=CHECK-SHIFT1
+; RUN: llc < %s -mtriple=s390x-linux-gnu -disable-block-placement | FileCheck %s -check-prefix=CHECK-SHIFT2
 
 ; Check signed minimum.
 ; - CHECK is for the main loop.
 ; - CHECK-SHIFT1 makes sure that the negated shift count used by the second
 ;   RLL is set up correctly.  The negation is independent of the NILL and L
 ;   tested in CHECK.
 ; - CHECK-SHIFT2 makes sure that %b is shifted into the high part of the word
 ;   before being used, and that the low bits are set to 1.  This sequence is

test/CodeGen/SystemZ/atomicrmw-minmax-02.ll

 ; Test 8-bit atomic min/max operations.
 ;
-; RUN: llc < %s -mtriple=s390x-linux-gnu | FileCheck %s
-; RUN: llc < %s -mtriple=s390x-linux-gnu | FileCheck %s -check-prefix=CHECK-SHIFT1
-; RUN: llc < %s -mtriple=s390x-linux-gnu | FileCheck %s -check-prefix=CHECK-SHIFT2
+; RUN: llc < %s -mtriple=s390x-linux-gnu -disable-block-placement | FileCheck %s
+; RUN: llc < %s -mtriple=s390x-linux-gnu -disable-block-placement | FileCheck %s -check-prefix=CHECK-SHIFT1
+; RUN: llc < %s -mtriple=s390x-linux-gnu -disable-block-placement | FileCheck %s -check-prefix=CHECK-SHIFT2
 
 ; Check signed minimum.
 ; - CHECK is for the main loop.
 ; - CHECK-SHIFT1 makes sure that the negated shift count used by the second
 ;   RLL is set up correctly.  The negation is independent of the NILL and L
 ;   tested in CHECK.
 ; - CHECK-SHIFT2 makes sure that %b is shifted into the high part of the word
 ;   before being used, and that the low bits are set to 1.  This sequence is

test/CodeGen/SystemZ/loop-01.ll

 ; Test loop tuning.
 ;
-; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z10 | FileCheck %s
-; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z13 \
+; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z10 -disable-block-placement | FileCheck %s
+; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z13 -disable-block-placement \
 ; RUN:  | FileCheck %s -check-prefix=CHECK -check-prefix=CHECK-Z13
 
 ; Test that strength reduction is applied to addresses with a scale factor,
 ; but that indexed addressing can still be used.
 define void @f1(i32 *%dest, i32 %a) {
 ; CHECK-LABEL: f1:
 ; CHECK-NOT: sllg
 ; CHECK: st %r3, 400({{%r[1-5],%r[1-5]}})

test/CodeGen/SystemZ/loop-02.ll

 ; Test BRCTH.
 
 ; RUN: llc < %s -verify-machineinstrs -mtriple=s390x-linux-gnu -mcpu=z196 \
-; RUN:   -no-integrated-as | FileCheck %s
+; RUN:   -no-integrated-as -disable-block-placement | FileCheck %s
 
 ; Test a loop that should be converted into dbr form and then use BRCTH.
 define void @f2(i32 *%src, i32 *%dest) {
 ; CHECK-LABEL: f2:
 ; CHECK: blah [[REG:%r[0-5]]]
 ; CHECK: [[LABEL:\.[^:]*]]:{{.*}} %loop
 ; CHECK: brcth [[REG]], [[LABEL]]
 ; CHECK: br %r14

test/CodeGen/SystemZ/swifterror.ll

-; RUN: llc < %s -mtriple=s390x-linux-gnu| FileCheck %s
-; RUN: llc < %s -O0 -mtriple=s390x-linux-gnu | FileCheck --check-prefix=CHECK-O0 %s
+; RUN: llc < %s -mtriple=s390x-linux-gnu -disable-block-placement | FileCheck %s
+; RUN: llc < %s -O0 -mtriple=s390x-linux-gnu -disable-block-placement | FileCheck --check-prefix=CHECK-O0 %s
 
 declare i8* @malloc(i64)
 declare void @free(i8*)
 %swift_error = type {i64, i8}
 
 ; This tests the basic usage of a swifterror parameter. "foo" is the function
 ; that takes a swifterror parameter and "caller" is the caller of "foo".
 define float @foo(%swift_error** swifterror %error_ptr_ref) {

test/CodeGen/X86/2009-02-26-MachineLICMBug.ll

 ; CHECK:       ## %bb.0: ## %entry
 ; CHECK-NEXT:    pushq %r14
 ; CHECK-NEXT:    pushq %rbx
 ; CHECK-NEXT:    pushq %rax
 ; CHECK-NEXT:    movq %rsi, %r14
 ; CHECK-NEXT:    movq %rdi, %rbx
 ; CHECK-NEXT:    orq $2097152, %r14 ## imm = 0x200000
 ; CHECK-NEXT:    andl $15728640, %r14d ## imm = 0xF00000
-; CHECK-NEXT:    jmp LBB0_1
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  LBB0_3: ## %bb.i
-; CHECK-NEXT:    ## in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    movd {{.*#+}} xmm0 = mem[0],zero,zero,zero
-; CHECK-NEXT:    pinsrd $1, 4, %xmm0
-; CHECK-NEXT:    pinsrd $2, 8, %xmm0
-; CHECK-NEXT:    movdqa %xmm0, %xmm1
-; CHECK-NEXT:    pblendw {{.*#+}} xmm1 = xmm1[0],mem[1],xmm1[2],mem[3],xmm1[4],mem[5],xmm1[6],mem[7]
-; CHECK-NEXT:    psrld $16, %xmm0
-; CHECK-NEXT:    pblendw {{.*#+}} xmm0 = xmm0[0],mem[1],xmm0[2],mem[3],xmm0[4],mem[5],xmm0[6],mem[7]
-; CHECK-NEXT:    addps {{.*}}(%rip), %xmm0
-; CHECK-NEXT:    addps %xmm1, %xmm0
-; CHECK-NEXT:    movaps %xmm0, 0
 ; CHECK-NEXT:  LBB0_1: ## %bb4
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    callq _xxGetOffsetForCode
 ; CHECK-NEXT:    xorl %esi, %esi
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    movq %rbx, %rdi
 ; CHECK-NEXT:    callq _xxCalculateMidType
 ; CHECK-NEXT:    cmpl $1, %eax
 ; CHECK-NEXT:    jne LBB0_1
 ; CHECK-NEXT:  ## %bb.2: ## %bb26
 ; CHECK-NEXT:    ## in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    cmpq $1048576, %r14 ## imm = 0x100000
 ; CHECK-NEXT:    jne LBB0_1
-; CHECK-NEXT:    jmp LBB0_3
+; CHECK-NEXT:  ## %bb.3: ## %bb.i
+; CHECK-NEXT:    ## in Loop: Header=BB0_1 Depth=1
+; CHECK-NEXT:    movd {{.*#+}} xmm0 = mem[0],zero,zero,zero
+; CHECK-NEXT:    pinsrd $1, 4, %xmm0
+; CHECK-NEXT:    pinsrd $2, 8, %xmm0
+; CHECK-NEXT:    movdqa %xmm0, %xmm1
+; CHECK-NEXT:    pblendw {{.*#+}} xmm1 = xmm1[0],mem[1],xmm1[2],mem[3],xmm1[4],mem[5],xmm1[6],mem[7]
+; CHECK-NEXT:    psrld $16, %xmm0
+; CHECK-NEXT:    pblendw {{.*#+}} xmm0 = xmm0[0],mem[1],xmm0[2],mem[3],xmm0[4],mem[5],xmm0[6],mem[7]
+; CHECK-NEXT:    addps {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    addps %xmm1, %xmm0
+; CHECK-NEXT:    movaps %xmm0, 0
+; CHECK-NEXT:    jmp LBB0_1
 entry:
   br label %bb4
 
 bb4:    ; preds = %bb.i, %bb26, %bb4, %entry
 
   %0 = call i32 (...) @xxGetOffsetForCode(i32 undef) nounwind    ; <i32> [#uses=0]
   %ins = or i64 %p, 2097152   ; <i64> [#uses=1]
   %1 = call i32 (...) @xxCalculateMidType(%struct.Key* %desc, i32 0) nounwind    ; <i32> [#uses=1]

test/CodeGen/X86/avx-cmp.ll

 ; CHECK-LABEL: render:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    pushq %rbx
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB2_6
 ; CHECK-NEXT:  # %bb.1: # %for.cond5.preheader
 ; CHECK-NEXT:    xorl %ebx, %ebx
-; CHECK-NEXT:    jmp .LBB2_2
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB2_5: # %if.then
-; CHECK-NEXT:    # in Loop: Header=BB2_2 Depth=1
-; CHECK-NEXT:    callq scale
 ; CHECK-NEXT:  .LBB2_2: # %for.cond5
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    testb %bl, %bl
 ; CHECK-NEXT:    jne .LBB2_2
 ; CHECK-NEXT:  # %bb.3: # %for.cond5
 ; CHECK-NEXT:    # in Loop: Header=BB2_2 Depth=1
 ; CHECK-NEXT:    testb %bl, %bl
 ; CHECK-NEXT:    je .LBB2_2
 ; CHECK-NEXT:  # %bb.4: # %for.body33
 ; CHECK-NEXT:    # in Loop: Header=BB2_2 Depth=1
 ; CHECK-NEXT:    vucomisd {{\.LCPI.*}}, %xmm0
 ; CHECK-NEXT:    jne .LBB2_5
-; CHECK-NEXT:    jp .LBB2_5
+; CHECK-NEXT:    jnp .LBB2_2
+; CHECK-NEXT:  .LBB2_5: # %if.then
+; CHECK-NEXT:   # in Loop: Header=BB2_2 Depth=1
+; CHECK-NEXT:    callq   scale
 ; CHECK-NEXT:    jmp .LBB2_2
 ; CHECK-NEXT:  .LBB2_6: # %for.end52
 ; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    retq
 entry:
   br i1 undef, label %for.cond5, label %for.end52
 
 for.cond5:

test/CodeGen/X86/avx512-i1test.ll

 ; CHECK:       # %bb.0: # %L_10
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    je .LBB0_1
 ; CHECK-NEXT:  # %bb.4: # %L_30
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB0_1: # %bb56
 ; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    jmp .LBB0_2
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB0_3: # %bb35
-; CHECK-NEXT:    # in Loop: Header=BB0_2 Depth=1
-; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:  .LBB0_2: # %bb33
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB0_2
-; CHECK-NEXT:    jmp .LBB0_3
+; CHECK-NEXT:  # %bb.3: # %bb35
+; CHECK-NEXT:    # in Loop: Header=BB0_2 Depth=1
+; CHECK-NEXT:    testb %al, %al
+; CHECK-NEXT:    jmp .LBB0_2
 bb1:
   br i1 undef, label %L_10, label %L_10
 
 L_10:                                             ; preds = %bb1, %bb1
   br i1 undef, label %L_30, label %bb56
 
 bb56:                                             ; preds = %L_10
   br label %bb33

test/CodeGen/X86/block-placement.ll

body3:
   %next = add i32 %iv, 1
   %exitcond = icmp eq i32 %next, %i
   br i1 %exitcond, label %exit, label %body1
 
 exit:
   ret i32 %sum
 }
 
-!0 = !{!"branch_weights", i32 4, i32 64}
+!0 = !{!"branch_weights", i32 1, i32 64}
 
 define i32 @test_loop_early_exits(i32 %i, i32* %a) {
 ; Check that we sink early exit blocks out of loop bodies.
 ; CHECK-LABEL: test_loop_early_exits:
 ; CHECK: %entry
 ; CHECK: %body1
 ; CHECK: %body2
 ; CHECK: %body3

 ; CHECK: %if.else
 ; CHECK: %if.end10
 ; Second rotated loop top
 ; CHECK: .p2align
 ; CHECK: %if.then24
 ; CHECK: %while.cond.outer
 ; Third rotated loop top
 ; CHECK: .p2align
+; CHECK: %if.end20
 ; CHECK: %while.cond
 ; CHECK: %while.body
 ; CHECK: %land.lhs.true
 ; CHECK: %if.then19
-; CHECK: %if.end20
 ; CHECK: %if.then8
 ; CHECK: ret
 
 entry:
   %shr = ashr i32 %n, 1
   %add = add nsw i32 %shr, 1
   %arrayidx3 = getelementptr inbounds double, double* %ra, i64 1
   br label %for.cond

test/CodeGen/X86/branch_instruction_and_target_split_perf_nops.mir

 #       result >>= 7; break;
 #       case 5:
 #       result = result * 16 | ~result; break;
 #     }
 #   }
 #   return result;
 # }
 #
-# CHECK:       49:       eb 4a   jmp     74 <switchCase+0x95>
-# CHECK:       57:       eb 3c   jmp     60 <switchCase+0x95>
-# CHECK:       65:       eb 2e   jmp     46 <switchCase+0x95>
-# CHECK:       73:       eb 20   jmp     32 <switchCase+0x95>
-# CHECK:       81:       eb 12   jmp     18 <switchCase+0x95>
-# CHECK:       93:       7f 8b   jg      -117 <switchCase+0x20>
+# CHECK:       22:       eb 72   jmp     114 <switchCase+0x96>
+# CHECK:       5e:       eb 36   jmp      54 <switchCase+0x96>
+# CHECK:       6c:       eb 28   jmp      40 <switchCase+0x96>
+# CHECK:       7a:       eb 1a   jmp      26 <switchCase+0x96>
+# CHECK:       88:       eb 0c   jmp      12 <switchCase+0x96>
+# CHECK:       94:       7f a3   jg      -93 <switchCase+0x39>
 
 # Test 2:
 #
 # Source C code:
 # 
 # int ifElse(int z) {
 #   int w = 0;
 #   while(1) {
 #     if(x < 0)
 #       w++;
 #     else if(y > 0)
 #       w--;
 #     else if((x & y) == 3)
 #       w*=2;
 #     else if ((x | y) == 18)
 #       w += 2;
 #     else if ((y ^ x) == 154)
 #       w -= 3;
 #     else if(((y ^ x) & 1) != 0)
 #       break;
 #   }
 #   return w;
 # }
 #
-# CHECK:       129:       eb 13   jmp     19 <ifElse+0x7e>
-# CHECK:       12e:       eb a0   jmp     -96 <ifElse+0x10>
-# CHECK:       132:       eb 9c   jmp     -100 <ifElse+0x10>
-# CHECK:       137:       eb 97   jmp     -105 <ifElse+0x10>
-# CHECK:       13c:       eb 92   jmp     -110 <ifElse+0x10>
+# CHECK:       129:       eb 41   jmp       65 <ifElse+0xac>
+# CHECK:       137:       eb 92   jmp     -110 <ifElse+0xb>
+# CHECK:       144:       eb 85   jmp     -123 <ifElse+0xb>
+# CHECK:       152:       e9 74 ff ff ff   jmp     -140 <ifElse+0xb>
+# CHECK:       167:       e9 5f ff ff ff   jmp     -161 <ifElse+0xb>
 --- |
   ; ModuleID = 'D:\iusers\opaparo\dev_test\branch_instruction_and_target_split_perf_nops.ll'
   source_filename = "D:\5C\5Ciusers\5C\5Copaparo\5C\5Cdev_test\5C\5Cbranch_instruction_and_target_split_perf_nops.c"
   target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
   target triple = "x86_64-pc-windows-msvc19.0.24210"
   
   @x = common global i32 0, align 4
   @y = common global i32 0, align 4

test/CodeGen/X86/code_placement_ignore_succ_in_inner_loop.ll

 ; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux < %s | FileCheck %s
 
 define void @foo() {
-; Test that when determining the edge probability from a node in an inner loop
-; to a node in an outer loop, the weights on edges in the inner loop should be
-; ignored if we are building the chain for the outer loop.
+; After moving the latch to the top of loop, there is no fall through from the
+; latch to outer loop.
 ;
 ; CHECK-LABEL: foo:
-; CHECK: callq c
 ; CHECK: callq b
+; CHECK: callq c
 
 entry:
   %call = call zeroext i1 @a()
   br i1 %call, label %if.then, label %if.else, !prof !1
 
 if.then:
   %call1 = call zeroext i1 @a()
   br i1 %call1, label %while.body, label %if.end.1, !prof !1

test/CodeGen/X86/code_placement_loop_rotation2.ll

 ; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux < %s | FileCheck %s
 ; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux -precise-rotation-cost < %s | FileCheck %s -check-prefix=CHECK-PROFILE
 
 define void @foo() {
 ; Test a nested loop case when profile data is not available.
 ;
 ; CHECK-LABEL: foo:
+; CHECK: callq h
 ; CHECK: callq b
-; CHECK: callq c
-; CHECK: callq d
+; CHECK: callq g
 ; CHECK: callq e
 ; CHECK: callq f
-; CHECK: callq g
-; CHECK: callq h
+; CHECK: callq c
+; CHECK: callq d
 
 entry:
   br label %header
 
 header:
   call void @b()
   %call = call zeroext i1 @a()
   br i1 %call, label %if.then, label %if.else, !prof !2

test/CodeGen/X86/move_latch_to_loop_top.ll

+; RUN: llc  -mcpu=corei7 -mtriple=x86_64-linux < %s | FileCheck %s
+
+; The block latch should be moved before header.
+;CHECK-LABEL: test1:
+;CHECK:       %latch
+;CHECK:       %header
+;CHECK:       %false
+define i32 @test1(i32* %p) {
+entry:
+  br label %header
+
+header:
+  %x1 = phi i64 [0, %entry], [%x2, %latch]
+  %count1 = phi i32 [0, %entry], [%count4, %latch]
+  %0 = ptrtoint i32* %p to i64
+  %1 = add i64 %0, %x1
+  %2 = inttoptr i64 %1 to i32*
+  %data = load i32, i32* %2
+  %3 = icmp eq i32 %data, 0
+  br i1 %3, label %latch, label %false
+
+false:
+  %count2 = add i32 %count1, 1
+  br label %latch
+
+latch:
+  %count4 = phi i32 [%count2, %false], [%count1, %header]
+  %x2 = add i64 %x1, 1
+  %4 = icmp eq i64 %x2, 100
+  br i1 %4, label %exit, label %header
+
+exit:
+  ret i32 %count4
+}
+
+; The block latch and one of false/true should be moved before header.
+;CHECK-LABEL: test2:
+;CHECK:       %false
+;CHECK:       %latch
+;CHECK:       %header
+;CHECK:       %true
+define i32 @test2(i32* %p) {
+entry:
+  br label %header
+
+header:
+  %x1 = phi i64 [0, %entry], [%x2, %latch]
+  %count1 = phi i32 [0, %entry], [%count4, %latch]
+  %0 = ptrtoint i32* %p to i64
+  %1 = add i64 %0, %x1
+  %2 = inttoptr i64 %1 to i32*
+  %data = load i32, i32* %2
+  %3 = icmp eq i32 %data, 0
+  br i1 %3, label %true, label %false
+
+false:
+  %count2 = add i32 %count1, 1
+  br label %latch
+
+true:
+  %count3 = add i32 %count1, 2
+  br label %latch
+
+latch:
+  %count4 = phi i32 [%count2, %false], [%count3, %true]
+  %x2 = add i64 %x1, 1
+  %4 = icmp eq i64 %x2, 100
+  br i1 %4, label %exit, label %header
+
+exit:
+  ret i32 %count4
+}
+
+; More blocks can be moved before header.
+;            header <------------
+;              /\               |
+;             /  \              |
+;            /    \             |
+;           /      \            |
+;          /        \           |
+;        true      false        |
+;         /\         /\         |
+;        /  \       /  \        |
+;       /    \     /    \       |
+;    true3 false3 /      \      |
+;      \    /   true2  false2   |
+;       \  /      \      /      |
+;        \/        \    /       |
+;      endif3       \  /        |
+;         \          \/         |
+;          \       endif2       |
+;           \        /          |
+;            \      /           |
+;             \    /            |
+;              \  /             |
+;               \/              |
+;              latch-------------
+;                |
+;                |
+;              exit
+;
+; Blocks true3,endif3,latch should be moved before header.
+;
+;CHECK-LABEL: test3:
+;CHECK:       %true3
+;CHECK:       %endif3
+;CHECK:       %latch
+;CHECK:       %header
+;CHECK:       %false
+define i32 @test3(i32* %p) {
+entry:
+  br label %header
+
+header:
+  %x1 = phi i64 [0, %entry], [%x2, %latch]
+  %count1 = phi i32 [0, %entry], [%count12, %latch]
+  %0 = ptrtoint i32* %p to i64
+  %1 = add i64 %0, %x1
+  %2 = inttoptr i64 %1 to i32*
+  %data = load i32, i32* %2
+  %3 = icmp eq i32 %data, 0
+  br i1 %3, label %true, label %false
+
+false:
+  %count2 = add i32 %count1, 1
+  %cond = icmp sgt i32 %count2, 10
+  br i1 %cond, label %true2, label %false2
+
+false2:
+  %count3 = and i32 %count2, 7
+  br label %endif2
+
+true2:
+  %count4 = mul i32 %count2, 3
+  br label %endif2
+
+endif2:
+  %count5 = phi i32 [%count3, %false2], [%count4, %true2]
+  %count6 = sub i32 %count5, 5
+  br label %latch
+
+true:
+  %count7 = add i32 %count1, 2
+  %cond2 = icmp slt i32 %count7, 20
+  br i1 %cond2, label %true3, label %false3
+
+false3:
+  %count8 = or i32 %count7, 3
+  br label %endif3
+
+true3:
+  %count9 = xor i32 %count7, 55
+  br label %endif3
+
+endif3:
+  %count10 = phi i32 [%count8, %false3], [%count9, %true3]
+  %count11 = add i32 %count10, 3
+  br label %latch
+
+latch:
+  %count12 = phi i32 [%count6, %endif2], [%count11, %endif3]
+  %x2 = add i64 %x1, 1
+  %4 = icmp eq i64 %x2, 100
+  br i1 %4, label %exit, label %header
+
+exit:
+  ret i32 %count12
+}
+
+; The exit block has higher frequency than false block, so latch block should
+; fall through to exit block.
+;CHECK-LABEL: test4:
+;CHECK:       %false
+;CHECK:       %header
+;CHECK:       %true
+;CHECK:       %latch
+;CHECK:       %exit
+define i32 @test4(i32 %t, i32* %p) {
+entry:
+  br label %header
+
+header:
+  %x1 = phi i64 [0, %entry], [%x2, %latch]
+  %count1 = phi i32 [0, %entry], [%count4, %latch]
+  %0 = ptrtoint i32* %p to i64
+  %1 = add i64 %0, %x1
+  %2 = inttoptr i64 %1 to i32*
+  %data = load i32, i32* %2
+  %3 = icmp eq i32 %data, 0
+  br i1 %3, label %true, label %false, !prof !1
+
+false:
+  %count2 = add i32 %count1, 1
+  br label %latch
+
+true:
+  %count3 = add i32 %count1, 2
+  br label %latch
+
+latch:
+  %count4 = phi i32 [%count2, %false], [%count3, %true]
+  %x2 = add i64 %x1, 1
+  %4 = icmp eq i64 %x2, 100
+  br i1 %4, label %exit, label %header, !prof !2
+
+exit:
+  ret i32 %count4
+}
+
+!1 = !{!"branch_weights", i32 100, i32 1}
+!2 = !{!"branch_weights", i32 16, i32 16}
+
+; If move latch to loop top doesn't reduce taken branch, don't do it.
+;CHECK-LABEL: test5:
+;CHECK:       %entry
+;CHECK:       %header
+;CHECK:       %latch
+define void @test5(i32* %p) {
+entry:
+  br label %header
+
+header:
+  %x1 = phi i64 [0, %entry], [%x1, %header], [%x2, %latch]
+  %0 = ptrtoint i32* %p to i64
+  %1 = add i64 %0, %x1
+  %2 = inttoptr i64 %1 to i32*
+  %data = load i32, i32* %2
+  %3 = icmp eq i32 %data, 0
+  br i1 %3, label %latch, label %header
+
+latch:
+  %x2 = add i64 %x1, 1
+  br label %header
+
+exit:
+  ret void
+}
+

test/CodeGen/X86/pr5145.ll

-; RUN: llc -mtriple=x86_64-- < %s | FileCheck %s
+; RUN: llc -disable-block-placement -mtriple=x86_64-- < %s | FileCheck %s
 @sc8 = external global i8
 
 define void @atomic_maxmin_i8() {
 ; CHECK: atomic_maxmin_i8
   %1 = atomicrmw max  i8* @sc8, i8 5 acquire
 ; CHECK: [[LABEL1:\.?LBB[0-9]+_[0-9]+]]:
 ; CHECK: cmpb
 ; CHECK: jg

test/CodeGen/X86/ragreedy-bug.ll

 ; CHECK-NEXT: testl
 ; CHECK-NEXT: jne
 ; CHECK: cond.true.i.i217
 ; CHECK-NEXT: in Loop
 ; Mem-move
 ; CHECK-NEXT: movl
 ; CHECK-NEXT: andl
 ; CHECK-NEXT: testl
-; CHECK-NEXT: je
+; CHECK-NEXT: jne
 ; CHECK: cond.false.i.i
 ; CHECK: maskrune
 ; CHECK-NEXT: movzbl
 ; CHECK-NEXT: movzbl
 ; CHECK-NEXT: testl
 ; CHECK-NEXT: je
 ; CHECK: cond.false.i.i219
 ; CHECK: maskrune

test/CodeGen/X86/swifterror.ll

-; RUN: llc -verify-machineinstrs < %s -mtriple=x86_64-apple-darwin | FileCheck --check-prefix=CHECK-APPLE %s
-; RUN: llc -verify-machineinstrs -O0 < %s -mtriple=x86_64-apple-darwin | FileCheck --check-prefix=CHECK-O0 %s
-; RUN: llc -verify-machineinstrs < %s -mtriple=i386-apple-darwin | FileCheck --check-prefix=CHECK-i386 %s
+; RUN: llc -verify-machineinstrs < %s -mtriple=x86_64-apple-darwin -disable-block-placement | FileCheck --check-prefix=CHECK-APPLE %s
+; RUN: llc -verify-machineinstrs -O0 < %s -mtriple=x86_64-apple-darwin -disable-block-placement | FileCheck --check-prefix=CHECK-O0 %s
+; RUN: llc -verify-machineinstrs < %s -mtriple=i386-apple-darwin -disable-block-placement | FileCheck --check-prefix=CHECK-i386 %s
 
 declare i8* @malloc(i64)
 declare void @free(i8*)
 %swift_error = type {i64, i8}
 
 ; This tests the basic usage of a swifterror parameter. "foo" is the function
 ; that takes a swifterror parameter and "caller" is the caller of "foo".
 define float @foo(%swift_error** swifterror %error_ptr_ref) {

test/CodeGen/X86/tail-dup-merge-loop-headers.ll

 ; outer_loop_latch, and into shared_preheader, and then removed. This leaves
 ; shared_loop_header as the header of both loops. The end result
 ; is that there are 2 valid loops, and that they share a header. If we re-ran
 ; the loop analysis, it would classify this as a single loop.
 ; So far this is fine as far as layout is concerned.
 ; After layout we tail merge blocks merge_other and merge_predecessor_split.
 ; We do this even though they share only a single instruction, because
 ; merge_predecessor_split falls through to their shared successor:
-; outer_loop_latch.
+; outer_loop_latch. And then outer_loop_latch is moved before shared_loop_header
+; to reduce taken branches.
 ; The rest of the blocks in the function are noise unfortunately. Bugpoint
 ; couldn't shrink the test any further.
 
 ; CHECK-LABEL: loop_shared_header
 ; CHECK: # %entry
 ; CHECK: # %shared_preheader
+; CHECK: # %outer_loop_latch
+; CHECK: # %outer_loop_latch
 ; CHECK: # %shared_loop_header
 ; CHECK: # %inner_loop_body
-; CHECK: # %outer_loop_latch
 ; CHECK: # %merge_predecessor_split
-; CHECK: # %outer_loop_latch
 ; CHECK: # %cleanup
 define i32 @loop_shared_header(i8* %exe, i32 %exesz, i32 %headsize, i32 %min, i32 %wwprva, i32 %e_lfanew, i8* readonly %wwp, i32 %wwpsz, i16 zeroext %sects) local_unnamed_addr #0 {
 entry:
   %0 = load i32, i32* undef, align 4
   %mul = shl nsw i32 %0, 2
   br i1 undef, label %if.end19, label %cleanup
 
 if.end19:                                         ; preds = %entry

test/CodeGen/X86/tail-dup-repeat.ll

 if.end56:                                         ; preds = %for.cond
   br i1 %a2, label %if.then64, label %if.end70
 
 if.then64:                                        ; preds = %if.end56
   store i8 1, i8* %a6, align 1
   br label %dup1
 
 ; CHECK:      # %if.end70
-; CHECK-NEXT: # in Loop:
 ; CHECK-NEXT: movl $12, (%rdx)
 ; CHECK-NEXT: movl $2, (%rcx)
 ; CHECK-NEXT: testl %eax, %eax
 ; CHECK-NEXT: je .[[HEADER]]
 if.end70:                                         ; preds = %if.end56
   store i32 12, i32* %a4, align 8
   br label %dup2
 

test/CodeGen/X86/x86-cmov-converter.ll

-; RUN: llc -mtriple=x86_64-pc-linux -x86-cmov-converter=true -verify-machineinstrs < %s | FileCheck %s
+; RUN: llc -mtriple=x86_64-pc-linux -x86-cmov-converter=true -verify-machineinstrs -disable-block-placement < %s | FileCheck %s
 
 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 ;; This test checks that x86-cmov-converter optimization transform CMOV
 ;; instruction into branches when it is profitable.
 ;; There are 5 cases below:
 ;;   1. CmovInCriticalPath:
 ;;        CMOV depends on the condition and it is in the hot path.
 ;;        Thus, it worths transforming.

test/DebugInfo/X86/dbg-value-transfer-order.ll

 ; We had a bug where the DBG_VALUE instruction for bit_offset would be emitted
 ; at the end of the basic block, long after its actual program point. What's
 ; interesting in this example is that the !range metadata produces an AssertSext
 ; DAG node that gets replaced during ISel. This leads to an unordered SDDbgValue
 ; vector, which has to be sorted by IR order before it is processed in parallel
 ; with the Orders insertion point vector.
 
 ; CHECK-LABEL: f: # @f
+; CHECK: .LBB0_3:
+;        Check that this DEBUG_VALUE comes before the left shift.
+; CHECK:         #DEBUG_VALUE: bit_offset <- $ecx
+; CHECK:         .cv_loc 0 1 8 28                # t.c:8:28
+; CHECK:         movl    $1, %[[reg:[^ ]*]]
+; CHECK:         shll    %cl, %[[reg]]
 ; CHECK: .LBB0_1:                                # %while.body
 ; CHECK:         movl    $32, %ecx
 ; CHECK:         testl   {{.*}}
 ; CHECK:         jne     .LBB0_3
 ; CHECK: # %bb.2:                                 # %if.then
 ; CHECK:         callq   if_then
 ; CHECK:         movl    %eax, %ecx
-; CHECK: .LBB0_3:                                # %if.end
-;        Check that this DEBUG_VALUE comes before the left shift.
-; CHECK:         #DEBUG_VALUE: bit_offset <- $ecx
-; CHECK:         .cv_loc 0 1 8 28                # t.c:8:28
-; CHECK:         movl    $1, %[[reg:[^ ]*]]
-; CHECK:         shll    %cl, %[[reg]]
+; CHECK:         jmp     .LBB0_3
 
 ; ModuleID = 't.c'
 source_filename = "t.c"
 target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-pc-windows-msvc19.0.24215"
 
 ; Function Attrs: nounwind readnone speculatable
 declare void @llvm.dbg.declare(metadata, metadata, metadata) #1