[RISC-V] Machine Block Placement generates extra jump instructions that are not cleaned up.

[stefanp-synopsys]

This is a performance issue.
For the following code:

int compute1(int);
int compute2(int);
int test();

int branch(int check1, int check2, int check3, int check4, int in) {
  int doadd = 1;
  if (check1) {
    in = compute1(in);
    doadd = 1; // We do the add.
  } else if (check2) {
    in = compute2(in);
    doadd = test(); // Unknown if we should do the add.
  } else if (check3) {
    in *= 7;
    doadd = 0; // Do not do the add.
  }

  if (doadd)
    in += 5;

  // Do a multiply by 7 here to confuse the compiler.
  if (check4) {
    in *= 7;
  }
  return in;
}

We can compile for RISCV:

clang -O3 -S branch.c -target riscv64-arc-linux-gnu

In the final assembly we end up with basic blocks that look like this:

< ... more code up here ... >
 64 .LBB0_8:                                # %if.end9
 65         slli    a0, a4, 3
 66         subw    a0, a0, a4
 67         bnez    a2, .LBB0_11
 68 # %bb.9:                                # %if.end9
 69         bnez    a2, .LBB0_2
 70         j       .LBB0_12
 71 .LBB0_10:
 72         mv      a0, s1
 73         j       .LBB0_2
 74 .LBB0_11:                               # %if.end9
 75         mv      a4, a0
 76         bnez    a2, .LBB0_2
 77 .LBB0_12:
 78         addiw   a0, a4, 5
 79         j       .LBB0_2

In the above we generate an unconditional jump (line 70) to LBB0_12 and then from there we jump right back out to LBB0_2 after a single instruction. I feel like LBB0_12 should be duplicated into line 70. This would save a jump and only at the cost of a slight code size increase.

There should be a way to clean up situations where we have:

jump A
<...>
A:
<very few instructions, maybe 1 - 3>
jump B 

I'm happy to provide a patch for this but I don't know how to approach the issue because machine block placement runs very late. Should this be an improvement in machine block placement?

[llvmbot]

@llvm/issue-subscribers-backend-risc-v

Author: Stefan Pintilie (stefanp-synopsys)

This is a performance issue. For the following code: ``` int compute1(int); int compute2(int); int test();

int branch(int check1, int check2, int check3, int check4, int in) {
int doadd = 1;
if (check1) {
in = compute1(in);
doadd = 1; // We do the add.
} else if (check2) {
in = compute2(in);
doadd = test(); // Unknown if we should do the add.
} else if (check3) {
in *= 7;
doadd = 0; // Do not do the add.
}

if (doadd)
in += 5;

// Do a multiply by 7 here to confuse the compiler.
if (check4) {
in *= 7;
}
return in;
}

We can compile for RISCV:

clang -O3 -S branch.c -target riscv64-arc-linux-gnu

In the final assembly we end up with basic blocks that look like this:

< ... more code up here ... >
64 .LBB0_8: # %if.end9
65 slli a0, a4, 3
66 subw a0, a0, a4
67 bnez a2, .LBB0_11
68 # %bb.9: # %if.end9
69 bnez a2, .LBB0_2
70 j .LBB0_12
71 .LBB0_10:
72 mv a0, s1
73 j .LBB0_2
74 .LBB0_11: # %if.end9
75 mv a4, a0
76 bnez a2, .LBB0_2
77 .LBB0_12:
78 addiw a0, a4, 5
79 j .LBB0_2

In the above we generate an unconditional jump (line 70) to `LBB0_12` and then from there we jump right back out to `LBB0_2` after a single instruction. I feel like `LBB0_12` should be duplicated into line 70. This would save a jump and only at the cost of a slight code size increase. 

There should be a way to clean up situations where we have:

jump A
<...>
A:
<very few instructions, maybe 1 - 3>
jump B

I'm happy to provide a patch for this but I don't know how to approach the issue because machine block placement runs very late. Should this be an improvement in machine block placement? 
</details>

[topperc]

We've had some patches related to late branch optimization recently. Not sure if they help this case.

#117060
#134760

[stefanp-synopsys]

We've had some patches related to late branch optimization recently. Not sure if they help this case.

#117060 #134760

Thank you. Let me take a look and see if those help.

[stefanp-synopsys]

We've had some patches related to late branch optimization recently. Not sure if they help this case.
#117060 #134760

Thank you. Let me take a look and see if those help.

I have tried both of those patches but unfortunately neither one seems to help.

I am considering trying to add a pass that looks at all of the unconditional branches and then if the block that is branched to is small enough (say no more than 3 instructions?) is gets duplicated into the location of the unconditional branch. However, I feel like there should be something that does that already.

[mikhailramalho]

We've had some patches related to late branch optimization recently. Not sure if they help this case.
#117060 #134760

Thank you. Let me take a look and see if those help.

I have tried both of those patches but unfortunately neither one seems to help.

I am considering trying to add a pass that looks at all of the unconditional branches and then if the block that is branched to is small enough (say no more than 3 instructions?) is gets duplicated into the location of the unconditional branch. However, I feel like there should be something that does that already.

Maybe this could be added to the riscv late opt pass?

[topperc]

We've had some patches related to late branch optimization recently. Not sure if they help this case.
#117060 #134760

Thank you. Let me take a look and see if those help.

I have tried both of those patches but unfortunately neither one seems to help.

I am considering trying to add a pass that looks at all of the unconditional branches and then if the block that is branched to is small enough (say no more than 3 instructions?) is gets duplicated into the location of the unconditional branch. However, I feel like there should be something that does that already.

Is t that what the tail duplicator is supposed to do?

[stefanp-synopsys]

So, yes. This is what the tail duplicator is supposed to do. I realized that this is a bit more complicated than I expected. Here is what I am looking at:

 bb.8.if.end9:
 ; predecessors: %bb.6
   successors: %bb.9(0x30000000), %bb.10(0x50000000); %bb.9(37.50%), %bb.10(62.50%)
   liveins: $x8, $x10, $x12, $x14
   BNE killed renamable $x12, $x0, %bb.10
   PseudoBR %bb.9
 
 bb.7.if.end9:
 ; predecessors: %bb.6
   successors: %bb.9(0x30000000), %bb.10(0x50000000); %bb.9(37.50%), %bb.10(62.50%)
   liveins: $x8, $x10, $x12
   $x14 = ADDI renamable $x10, 0
   BNE killed renamable $x12, $x0, %bb.10

 bb.9:
 ; predecessors: %bb.8, %bb.7
   successors: %bb.10(0x80000000); %bb.10(100.00%)
   liveins: $x8, $x14
   renamable $x10 = ADDIW killed renamable $x14, 5
   PseudoBR %bb.10

What I want to produce is:

 bb.8.if.end9:
 ; predecessors: %bb.6
   successors: %bb.9(0x30000000), %bb.10(0x50000000); %bb.9(37.50%), %bb.10(62.50%)
   liveins: $x8, $x10, $x12, $x14
   BNE killed renamable $x12, $x0, %bb.10

;; Remove the PseudoBR from the above block and fall-through to this one. 
  bb.9.COPY:
 ; predecessors: %bb.8, %bb.7
   successors: %bb.10(0x80000000); %bb.10(100.00%)
   liveins: $x8, $x14
   renamable $x10 = ADDIW killed renamable $x14, 5
   PseudoBR %bb.10

 bb.7.if.end9:
 ; predecessors: %bb.6
   successors: %bb.9(0x30000000), %bb.10(0x50000000); %bb.9(37.50%), %bb.10(62.50%)
   liveins: $x8, $x10, $x12
   $x14 = ADDI renamable $x10, 0
   BNE killed renamable $x12, $x0, %bb.10

 bb.9:
 ; predecessors: %bb.8, %bb.7
   successors: %bb.10(0x80000000); %bb.10(100.00%)
   liveins: $x8, $x14
   renamable $x10 = ADDIW killed renamable $x14, 5
   PseudoBR %bb.10

This was not quite what I said initially and it seems that the tail duplicator does not do this.

[stefanp-synopsys]

The reason we are not doing the duplication is because of this code in canTailDuplicate:

 836   if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
 837     return false;
 838  
 839   if (!PredCond.empty())
 840     return false;

Both of the predecessors of bb.9 have conditions and so the function just returns false. I guess at this point this makes sense.

[stefanp-synopsys]

I'm going to close this issue.
This is more complicated than I originally considered and it is probably not worth putting code in for this specific case.