[llvm-dev] Bug in TailDuplicator?

[Verena Beckham via llvm-dev]

Hi,

I think there might be a bug in the tail duplicator (called from 
MachineBlockPlacement in my case), when duplicating a block that 
contains an implicit fall-through.
Suppose you have the following blocks

BB#1:
      Predecessors according to CFG: BB#2
	...
	conditional_branch <BB#3>
      < implicit fall-through to BB#2 >
      Successors according to CFG: BB#2 BB#3

BB#2:
      Predecessors according to CFG: BB#1 BB#0
	...
	unconditional_branch <BB#1>
      Successors according to CFG: BB#1

BB#3:
      Predecessors according to CFG: BB#1
	...

It duplicates BB#1 into BB#2 but misses out the branch that goes back up:

BB#2:
      Predecessors according to CFG: BB#1 BB#0
	<BB#2 instructions>
	<BB#1 instructions>
	conditional_branch <BB#3>
      Successors according to CFG: BB#3

So this is not a loop any more.

Instead, a branch needs to be inserted to replace the implicit 
fall-through in BB#1.

I have attached a patch for this.

(Incidentally, I see a duplication of the statement 
"TII->removeBranch(*PrevBB);" if run after register allocation. I've 
removed this call in the patch as well.)

Unfortunately, I am working on a proprietary target, so cannot provide a 
test case. I have, however, attached a "pseudo mir" which should be 
easily adaptable for a public target.

Maybe this is not a bug, but my function at this stage is not canonical? 
Also, I am not on tip (though I checked the TailDuplicator tip), so it 
is possible this is fixed elsewhere.

Thanks!

-- 
Verena Beckham

Senior Principal Software Engineer, Compilers

Codeplay Software Ltd
Level C, Argyle House, 3 Lady Lawson Street, Edinburgh, EH3 9DR
Tel: 0131 466 0503
Fax: 0131 557 6600
Website: http://www.codeplay.com

This email and any attachments may contain confidential and /or 
privileged information and  is for use  by the addressee only. If you 
are not the intended recipient, please notify Codeplay Software Ltd 
immediately and delete the message from your computer. You may not copy 
or forward it,or use or disclose its contents to any other person. Any 
views or other information in this message which do not relate to our 
business are not authorized by Codeplay software Ltd, nor does this 
message form part of any contract unless so stated.
As internet communications are capable of data corruption Codeplay 
Software Ltd does not accept any responsibility for any changes made to 
this message after it was sent. Please note that Codeplay Software Ltd 
does not accept any liability or responsibility for viruses and it is 
your responsibility to scan any attachments.
Company registered in England and Wales, number: 04567874
Registered office: Regent house, 316 Beulah Hill, London, United 
Kingdom, SE19 3HF

-------------- next part --------------
A non-text attachment was scrubbed...
Name: tailDuplicatorPatch.diff
Type: text/x-patch
Size: 1706 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180516/6696fd59/attachment.bin>
-------------- next part --------------
# RUN: llc -mtriple=XXX -O0 -run-pass block-placement -o - %s | FileCheck %s
--- |
  define void @main(i8* %x) {
  entry:
    ret void
  }
...
---
name:            main
alignment:       5
tracksRegLiveness: true
body:             |
  bb.0:
    successors: %bb.1, %bb.2
    liveins: %r0, %r8

    conditional_branch %r0, 2, %bb.2
    unconditional_branch %bb.1
  
  bb.1:
    successors: %bb.1, %bb.8
  
    conditional_branch %r8, 0, %bb.8
    unconditional_branch %bb.1
  
  bb.2:
    successors: %bb.3, %bb.7
  
    conditional_branch %r8, 88, %bb.7
    unconditional_branch %bb.3
  
  bb.3:
    successors: %bb.4
  
    store %r8, 12, %r8
    unconditional_branch %bb.4
  
  bb.4:
    successors: %bb.5, %bb.6
  
    %r0 = load 4, %r8
    conditional_branch %r8, 0, %bb.6
    unconditional_branch %bb.5
  
  bb.5:
    successors: %bb.4

    ; bb.4 should be duplicated into bb.5
    ; CHECK-LABEL: bb.5:
    ; CHECK: call 9999
    ; CHECK: %r0 = load 4, %r8
    ; Ensure a branch is generated here
    ; CHECK: conditional_branch %r8, 0, %bb.5

    call 9999
    unconditional_branch %bb.4
  
    ; CHECK-NOT: bb.6:
    ; CHECK-NOT: bb.7:

  bb.6:
    successors: %bb.7

    unconditional_branch %bb.7
  
  bb.7:
    successors: %bb.8
  
    unconditional_branch %bb.8
  
  bb.8:
    ; CHECK-LABEL: bb.8:
    return 0
...