llvm dev - Mar 2017 - Structurizing multi-exit regions

Hi,

I'm trying to solve a problem from StructurizeCFG not actually handling 
regions with multiple exits. Sample IR attached.

StructurizeCFG doesn't touch this function, exiting early on the 
isTopLevelRegion check. SIAnnotateControlFlow then gets confused and 
ends up inserting an if into one of the blocks, and the matching end.cf 
into one of the return/unreachable blocks. The input to the end.cf is 
then not dominated by the condition which fails the verifier.

I'm not sure exactly about how to go about fixing this. I see a few options:

- Try to make the annotator aware of multi exit regions and insert the 
necessary phis for the input mask values for the end.cf calls. This 
seems undesirable and I'm not sure works in all cases.

- Make StructurizeCFG duplicate blocks to get simple regions. Is there 
already code to do this somewhere? CodeExtractor seems to do something 
similar, but not quite the same. Can this be done in the region pass, or 
does StructurizeCFG need to be converted to a function pass? RegionInfo 
mentions support for "extended" regions with multiple exits, but I
don't
think this helps any here.

-Matt

-------------- next part --------------
; RUN: opt -S -structurizecfg -si-annotate-control-flow %s

target datalayout =
"e-p:32:32-p1:64:64-p2:64:64-p3:32:32-p4:64:64-p5:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64"
target triple = "amdgcn-amd-amdhsa-opencl"

; Function Attrs: nounwind
define amdgpu_kernel void @multi_divergent_region_exit(i32 addrspace(1)*
nocapture %arg0, i32 addrspace(1)* nocapture %arg1, i32 addrspace(1)* nocapture
%arg2) #0 {
entry:
  %tmp = tail call i32 @llvm.amdgcn.workitem.id.x() #1
  %tmp1 = add i32 0, %tmp
  %tmp2 = zext i32 %tmp1 to i64
  %tmp3 = add i64 0, %tmp2
  %tmp4 = shl i64 %tmp3, 32
  %tmp5 = ashr exact i64 %tmp4, 32
  %tmp6 = getelementptr inbounds i32, i32 addrspace(1)* %arg0, i64 %tmp5
  %tmp7 = load i32, i32 addrspace(1)* %tmp6, align 4
  %tmp8 = sext i32 %tmp7 to i64
  %tmp9 = getelementptr inbounds i32, i32 addrspace(1)* %arg1, i64 %tmp8
  %tmp10 = load i32, i32 addrspace(1)* %tmp9, align 4
  %tmp13 = zext i32 %tmp10 to i64
  %tmp14 = getelementptr inbounds i32, i32 addrspace(1)* %arg2, i64 %tmp13
  %tmp16 = load i32, i32 addrspace(1)* %tmp14, align 16
  %Pivot = icmp slt i32 %tmp16, 2
  br i1 %Pivot, label %LeafBlock, label %LeafBlock1

LeafBlock:                                        ; preds = %entry
  %SwitchLeaf = icmp eq i32 %tmp16, 1
  br i1 %SwitchLeaf, label %unreachable0, label %unreachable1

LeafBlock1:                                       ; preds = %entry
  %SwitchLeaf2 = icmp eq i32 %tmp16, 2
  br i1 %SwitchLeaf2, label %unreachable0, label %unreachable1

unreachable0:                                     ; preds = %LeafBlock,
%LeafBlock1
  store volatile i32 9, i32 addrspace(1)* undef
  unreachable

unreachable1:                                     ; preds = %LeafBlock,
%LeafBlock1
  store volatile i32 17, i32 addrspace(3)* undef
  unreachable
}

; Function Attrs: nounwind readnone
declare i32 @llvm.amdgcn.workitem.id.x() #1

attributes #0 = { nounwind }
attributes #1 = { nounwind readnone }

On Wed, Mar 1, 2017 at 5:39 PM, Matt Arsenault via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi,
>
> I'm trying to solve a problem from StructurizeCFG not actually handling
> regions with multiple exits.

SEME or MEME or both?

> Sample IR attached.
>
This is an example that just exhibits undefined behavior.
Is there one that doesn't?
IE if i change the unreachables to ret something, is that still an example
of something you care about?
>
> StructurizeCFG doesn't touch this function, exiting early on the
> isTopLevelRegion check.

FWIW: I'm not sure it should care whether it's a top level region, only
whether it's SESE, SEME, etc.

> SIAnnotateControlFlow then gets confused and ends up inserting an if into
> one of the blocks, and the matching end.cf into one of the
> return/unreachable blocks. The input to the end.cf is then not dominated
> by the condition which fails the verifier.
>
> I'm not sure exactly about how to go about fixing this. I see a few
> options:
>
> - Try to make the annotator aware of multi exit regions and insert the
> necessary phis for the input mask values for the end.cf calls. This seems
> undesirable and I'm not sure works in all cases.
>
It's possible to always find a unique entering/exiting condition for any of
the multiple-entrance/exit, and to transform it into a bunch of SESE
regions.
see, e.g,
https://net.cs.uni-bonn.de/fileadmin/ag/martini/Staff/yakdan/dream_ndss2015.pdf


>
> - Make StructurizeCFG duplicate blocks to get simple regions. Is there
> already code to do this somewhere? CodeExtractor seems to do something
> similar, but not quite the same. Can this be done in the region pass, or
> does StructurizeCFG need to be converted to a function pass? RegionInfo
> mentions support for "extended" regions with multiple exits, but
I don't
> think this helps any here.

This also would work.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170301/29a492c4/attachment-0001.html>

> On Mar 1, 2017, at 18:31, Daniel Berlin via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> 
> 
> On Wed, Mar 1, 2017 at 5:39 PM, Matt Arsenault via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> Hi,
> 
> I'm trying to solve a problem from StructurizeCFG not actually handling
regions with multiple exits.
> 
> SEME or MEME or both?
SEME. I don’t think I need to worry about MEME.


>  
> Sample IR attached.
> 
> This is an example that just exhibits undefined behavior.
> Is there one that doesn't?
> IE if i change the unreachables to ret something, is that still an example
of something you care about?
Yes, changing to ret also has the same problem. It just happens bugpoint found
the unreachable case in the original problem

-Matt
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170301/35d38036/attachment.html>

Hi Matt,

one prerequisite for the algorithm is that each function has exactly one 
entry and one exit node.

If I remember correctly there was a LLVM pass called mergereturn or 
something like that which made sure that you have at most one ret 
instruction for each function.

Using that used to be a prerequisite for running the transformation, but 
that obviously won't work for unreachable instructions.

The only doable approach I can see is to make the annotator able to 
handle those. Otherwise you could also have a BB existing a function 
using ret and another one running into an unreachable.

Regards,
Christian.

Am 02.03.2017 um 02:39 schrieb Matt Arsenault:
> Hi,
>
> I'm trying to solve a problem from StructurizeCFG not actually 
> handling regions with multiple exits. Sample IR attached.
>
> StructurizeCFG doesn't touch this function, exiting early on the 
> isTopLevelRegion check. SIAnnotateControlFlow then gets confused and 
> ends up inserting an if into one of the blocks, and the matching 
> end.cf into one of the return/unreachable blocks. The input to the 
> end.cf is then not dominated by the condition which fails the verifier.
>
> I'm not sure exactly about how to go about fixing this. I see a few 
> options:
>
> - Try to make the annotator aware of multi exit regions and insert the 
> necessary phis for the input mask values for the end.cf calls. This 
> seems undesirable and I'm not sure works in all cases.
>
> - Make StructurizeCFG duplicate blocks to get simple regions. Is there 
> already code to do this somewhere? CodeExtractor seems to do something 
> similar, but not quite the same. Can this be done in the region pass, 
> or does StructurizeCFG need to be converted to a function pass? 
> RegionInfo mentions support for "extended" regions with multiple 
> exits, but I don't think this helps any here.
>
> -Matt
>

FWIW, now that postdom is fixed, all the possible "returns/exits" of
the
function should be direct children of the virtual exit node in the post-dom
tree.

Thus, the following would work to detect whether each block is a real
return or not:

  for (auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {
    auto *BB = PDTChild->getBlock();
    auto &Info = BlockInfo[BB];
    // Real function return
    if (isa<ReturnInst>(Info.Terminator)) {
      DEBUG(dbgs() << "post-dom root child is a return: "
<< BB->getName()
                   << '\n';);
      continue;
    }
    // PDTChild is something else, like a no-return or infinite loop
  }


You could also just  insert a br i1 false <merged function return>,
<existing infinite loop branch> to have a single exit.
Until you simplify the cfg, it would work.


On Thu, Mar 2, 2017 at 8:08 AM, Christian König via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi Matt,
>
> one prerequisite for the algorithm is that each function has exactly one
> entry and one exit node.
>
> If I remember correctly there was a LLVM pass called mergereturn or
> something like that which made sure that you have at most one ret
> instruction for each function.
>
> Using that used to be a prerequisite for running the transformation, but
> that obviously won't work for unreachable instructions.
>
> The only doable approach I can see is to make the annotator able to handle
> those. Otherwise you could also have a BB existing a function using ret and
> another one running into an unreachable.
>
> Regards,
> Christian.
>
>
> Am 02.03.2017 um 02:39 schrieb Matt Arsenault:
>
>> Hi,
>>
>> I'm trying to solve a problem from StructurizeCFG not actually
handling
>> regions with multiple exits. Sample IR attached.
>>
>> StructurizeCFG doesn't touch this function, exiting early on the
>> isTopLevelRegion check. SIAnnotateControlFlow then gets confused and
ends
>> up inserting an if into one of the blocks, and the matching end.cf into
>> one of the return/unreachable blocks. The input to the end.cf is then
>> not dominated by the condition which fails the verifier.
>>
>> I'm not sure exactly about how to go about fixing this. I see a few
>> options:
>>
>> - Try to make the annotator aware of multi exit regions and insert the
>> necessary phis for the input mask values for the end.cf calls. This
>> seems undesirable and I'm not sure works in all cases.
>>
>> - Make StructurizeCFG duplicate blocks to get simple regions. Is there
>> already code to do this somewhere? CodeExtractor seems to do something
>> similar, but not quite the same. Can this be done in the region pass,
or
>> does StructurizeCFG need to be converted to a function pass? RegionInfo
>> mentions support for "extended" regions with multiple exits,
but I don't
>> think this helps any here.
>>
>> -Matt
>>
>>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170302/6883c56e/attachment.html>

On 03/02/2017 08:08 AM, Christian König wrote:
> Hi Matt,
>
> one prerequisite for the algorithm is that each function has exactly 
> one entry and one exit node.
>
> If I remember correctly there was a LLVM pass called mergereturn or 
> something like that which made sure that you have at most one ret 
> instruction for each function.
>
> Using that used to be a prerequisite for running the transformation, 
> but that obviously won't work for unreachable instructions.
>
> The only doable approach I can see is to make the annotator able to 
> handle those. Otherwise you could also have a BB existing a function 
> using ret and another one running into an unreachable.
>
> Regards,
> Christian. 
Thanks, I didn't know about mergereturn. Running that first seems to 
practically solve the problem. It does also merge unreachables, so 
that's OK too. If one branch is unreachable, and the other is return I 
still see the same problem like you mentioned.

-Matt