conditional flow resulting in "Instruction does not dominate all uses!"

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

conditional flow resulting in "Instruction does not dominate all uses!"

edA-qa mort-ora-y
I've having a bit of a problem generating output that doesn't result in
the "Instruction does not dominate all uses!". In my code it relates to
exception handling and how I generate the blocks. I understand exactly
why I get the message, but I'm unsure of how I can structure things to
avoid the problem.

In a rough pseudo-code, my blocks look like this:

entry:
        store 0, return_path
        result = invoke func to defer_block unwind landing

landing:
        landingpad
        store 1, return_path
        br defer_block

defer_block:
        stuff
        switch return_path, next_step [
                0, next_step
                1, rethrow
        ]

next_step:
        val = load result  ; error here


Structually the `next_step` has multiple preceding blocks, one of which
doesnt' define `result`. That results in the error. However, based on
the switching value `return_path` there is no way we can arrive at
`next_step` unless result has actually been set. Is there some way I can
tell LLVM this? Somehow just say "trust me", on the understanding that
it would be totally undefined if we arrive at `next_step` without result
being set?

I know one generic approach, which I've started implementing, but I'm
not sure it is a good solution. Instead of using results directly I
always store in a local variable:

        result = alloca result_type
        tmp = invoke func to store_block unwind landing

store_block:
        store tmp, result
        br defer_block

...

next_step:
        val = load result

Here result would just be undefined if we arrive at `next_step` without
having gone through `store_block`. It works, but my guess is that I'm
hiding some valuable information from the optimizers.


--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: conditional flow resulting in "Instruction does not dominate all uses!"

Henrique Santos-2
You could try placing a phi node at "defer_block" with incoming value "result"
when the incoming block is "entry", and do the same for "null" and "landing".
Then, instead of loading "result", you load the value given by the newly
created phi. That seems like the easiest solution.

H.


On Sun, Nov 3, 2013 at 4:21 AM, edA-qa mort-ora-y <[hidden email]> wrote:
I've having a bit of a problem generating output that doesn't result in
the "Instruction does not dominate all uses!". In my code it relates to
exception handling and how I generate the blocks. I understand exactly
why I get the message, but I'm unsure of how I can structure things to
avoid the problem.

In a rough pseudo-code, my blocks look like this:

entry:
        store 0, return_path
        result = invoke func to defer_block unwind landing

landing:
        landingpad
        store 1, return_path
        br defer_block

defer_block:
        stuff
        switch return_path, next_step [
                0, next_step
                1, rethrow
        ]

next_step:
        val = load result  ; error here


Structually the `next_step` has multiple preceding blocks, one of which
doesnt' define `result`. That results in the error. However, based on
the switching value `return_path` there is no way we can arrive at
`next_step` unless result has actually been set. Is there some way I can
tell LLVM this? Somehow just say "trust me", on the understanding that
it would be totally undefined if we arrive at `next_step` without result
being set?

I know one generic approach, which I've started implementing, but I'm
not sure it is a good solution. Instead of using results directly I
always store in a local variable:

        result = alloca result_type
        tmp = invoke func to store_block unwind landing

store_block:
        store tmp, result
        br defer_block

...

next_step:
        val = load result

Here result would just be undefined if we arrive at `next_step` without
having gone through `store_block`. It works, but my guess is that I'm
hiding some valuable information from the optimizers.


--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: conditional flow resulting in "Instruction does not dominate all uses!"

edA-qa mort-ora-y
In reply to this post by edA-qa mort-ora-y
On 03/11/13 12:16, Henrique Santos wrote:
> You could try placing a phi node at "defer_block" with incoming value
> "result"
> when the incoming block is "entry", and do the same for "null" and
> "landing".
> Then, instead of loading "result", you load the value given by the newly
> created phi. That seems like the easiest solution.

I looked at doing this. It isn't easy however since the landingpad can
be shared by several invoke points (as does the defer/following blocks).
If I could figure out how to combine it together then the phi might make
sense.

I created the same situation in C++ and got clang to generate LLVM-IR.
It appears they are using local variables (alloca) for this situation.


--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: conditional flow resulting in "Instruction does not dominate all uses!"

Henrique Santos-2
But the incoming value from the landing pad will always be null, won't it?
If so, just iterate through the predecessors and add the terminator as the
incoming value if it's an invoke instruction and add the null value it's not.
Won't that work?


On Mon, Nov 4, 2013 at 2:22 AM, edA-qa mort-ora-y <[hidden email]> wrote:
On 03/11/13 12:16, Henrique Santos wrote:
> You could try placing a phi node at "defer_block" with incoming value
> "result"
> when the incoming block is "entry", and do the same for "null" and
> "landing".
> Then, instead of loading "result", you load the value given by the newly
> created phi. That seems like the easiest solution.

I looked at doing this. It isn't easy however since the landingpad can
be shared by several invoke points (as does the defer/following blocks).
If I could figure out how to combine it together then the phi might make
sense.

I created the same situation in C++ and got clang to generate LLVM-IR.
It appears they are using local variables (alloca) for this situation.


--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: conditional flow resulting in "Instruction does not dominate all uses!"

Rafael Espíndola
On 4 November 2013 02:31, Henrique Santos
<[hidden email]> wrote:
> But the incoming value from the landing pad will always be null, won't it?
> If so, just iterate through the predecessors and add the terminator as the
> incoming value if it's an invoke instruction and add the null value it's
> not.
> Won't that work?
>


Note that the return value of an invoke is defined on the *edge* of
the successful return. So you cannot have a path to a use that goes
through the exception instead. In your example you have:

landing -> defer_block -> next_step.

This Is a static property, so this code in invalid even if dynamically
this path is never taken.

Cheers,
Rafael
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: conditional flow resulting in "Instruction does not dominate all uses!"

Henrique Santos-2
Well, what I had in mind was actually something like the following:

entry:
  result0 = invoke func0 to defer_block unwind landing0

landing0:
  landingpad
  result1 = invoke func1 to defer_block unwind landing1

landing1:
  landingpad
  br defer_block

defer_block:
  result = phi [ result0, entry ], [ result1, landing0 ], [ null, landing1 ]
  ...

This doesn't have landing pads with multiple predecessors like he said,
but I don't think that would make much difference.
The "defer block", however, is the target of multiple invokes.
I hope this makes sense. : )

H.




On Mon, Nov 4, 2013 at 1:54 PM, Rafael Espíndola <[hidden email]> wrote:
On 4 November 2013 02:31, Henrique Santos
<[hidden email]> wrote:
> But the incoming value from the landing pad will always be null, won't it?
> If so, just iterate through the predecessors and add the terminator as the
> incoming value if it's an invoke instruction and add the null value it's
> not.
> Won't that work?
>


Note that the return value of an invoke is defined on the *edge* of
the successful return. So you cannot have a path to a use that goes
through the exception instead. In your example you have:

landing -> defer_block -> next_step.

This Is a static property, so this code in invalid even if dynamically
this path is never taken.

Cheers,
Rafael


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: conditional flow resulting in "Instruction does not dominate all uses!"

Rafael Espíndola
On 4 November 2013 08:19, Henrique Santos
<[hidden email]> wrote:

> Well, what I had in mind was actually something like the following:
>
> entry:
>   result0 = invoke func0 to defer_block unwind landing0
>
> landing0:
>   landingpad
>   result1 = invoke func1 to defer_block unwind landing1
>
> landing1:
>   landingpad
>   br defer_block
>
> defer_block:
>   result = phi [ result0, entry ], [ result1, landing0 ], [ null, landing1 ]
>   ...
>
> This doesn't have landing pads with multiple predecessors like he said,
> but I don't think that would make much difference.
> The "defer block", however, is the target of multiple invokes.
> I hope this makes sense. : )

It does. Do we produce an error/assert in this case?

Cheers,
Rafael
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: conditional flow resulting in "Instruction does not dominate all uses!"

Henrique Santos-2
If you're talking about the IR, then I don't think so.
It seems like perfectly valid.

H.


On Mon, Nov 4, 2013 at 2:25 PM, Rafael Espíndola <[hidden email]> wrote:
On 4 November 2013 08:19, Henrique Santos
<[hidden email]> wrote:
> Well, what I had in mind was actually something like the following:
>
> entry:
>   result0 = invoke func0 to defer_block unwind landing0
>
> landing0:
>   landingpad
>   result1 = invoke func1 to defer_block unwind landing1
>
> landing1:
>   landingpad
>   br defer_block
>
> defer_block:
>   result = phi [ result0, entry ], [ result1, landing0 ], [ null, landing1 ]
>   ...
>
> This doesn't have landing pads with multiple predecessors like he said,
> but I don't think that would make much difference.
> The "defer block", however, is the target of multiple invokes.
> I hope this makes sense. : )

It does. Do we produce an error/assert in this case?

Cheers,
Rafael


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: conditional flow resulting in "Instruction does not dominate all uses!"

Rafael Espíndola
On 4 November 2013 08:32, Henrique Santos
<[hidden email]> wrote:
> If you're talking about the IR, then I don't think so.
> It seems like perfectly valid.

I agree.


Cheers,
Rafael
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: conditional flow resulting in "Instruction does not dominate all uses!"

edA-qa mort-ora-y
In reply to this post by Henrique Santos-2
On 04/11/13 11:31, Henrique Santos wrote:
> But the incoming value from the landing pad will always be null, won't it?
> If so, just iterate through the predecessors and add the terminator as the
> incoming value if it's an invoke instruction and add the null value it's
> not.
> Won't that work?

I never thought of that option. I could do post-processing and simply
add the missing predecessors to the PHI statement. I'd use undefined
instead of null however. I'm not sure if it is a simple thing to
experiment with however. My example was nice in clean, but in reality
that result value is used at some arbitrary place later in the code --
it isn't clear (from my compiler's viewpoint) where the values come
together in a phi. But the idea makes sense, so I'll see if I can use it
somehow.

The other option I've toyed with before was actually creating distinct
landing pad paths. I just duplicated all the deferred code, once into
the normal path, once into the exception path. I'm still too far away
from a version where I can test if this is helpful. It's certainly more
code, but the non-exception path and can be heavily optimized then.

Thanks.



--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev