This was found by reducing a miscompilation of embench's picojpeg. The graph we end up with looks like this:
The control constants were originally inside the inner gamma, but were pushed put by the NodePush pass.
When we query the region predication tracer about the highlighted origin region and target region, it responds false, which is wrong. The class correctly sees that the predicate to the lower gamma must be 1, and goes through the graph to see what values the inputs that may end up as the predicate may have. I have written the set of possible values in red for each input.
The class also creates a set of possible values assigned to the predicate per region. This per region set is not the union of all the inputs in the region, or the region results, but rather the first input in the region that finishes its set. The set for the origin region ends up being {0}, since the first input that finishes its set of possible values is the leftmost input to the inner gamma.
The fix for this is to take the union of all inputs (or all region results) in the region when determining what values the region can provide for the predicate.
While thinking about the fix for the above case, I started to consider cases like the one shown here:
When asked about the highlighted target region and origin region, the predicate tracer is going to respond false. It sees that the predicate of the lowest gamma must be 1. When tracing the possible origins of the predicate, tracing will reach the origin region, in which the only possible value is 0. However, if the middle gamma evaluates the rightmost subregion, it does not matter that the origin region produces a 0. It is still possible for control flow to go from the origin to the target region.
Before we consider doing lots of funky logic for handling thins, I am wondering how common situations like the one above really are. For example, if it is rare for a gamma to take control values as entry variables, we can work around the above issue by simply never tracing out of gamma nodes.
Whenever I have seen control typed values being routed into gammas, it has been because of NodePushOut hoisting control constants. If we tell NodePushOut to not move control constants, how many situations are left where control inputs are routed into gammas as entry variables?
I'll make a PR for fixing the first part of this issue, and then see if anything is still going wrong.
FYI @caleridas @phate
This was found by reducing a miscompilation of embench's picojpeg. The graph we end up with looks like this:
The control constants were originally inside the inner gamma, but were pushed put by the
NodePushpass.When we query the region predication tracer about the highlighted origin region and target region, it responds
false, which is wrong. The class correctly sees that the predicate to the lower gamma must be 1, and goes through the graph to see what values the inputs that may end up as the predicate may have. I have written the set of possible values in red for each input.The class also creates a set of possible values assigned to the predicate per region. This per region set is not the union of all the inputs in the region, or the region results, but rather the first input in the region that finishes its set. The set for the
origin regionends up being {0}, since the first input that finishes its set of possible values is the leftmost input to the inner gamma.The fix for this is to take the union of all inputs (or all region results) in the region when determining what values the region can provide for the predicate.
While thinking about the fix for the above case, I started to consider cases like the one shown here:
When asked about the highlighted target region and origin region, the predicate tracer is going to respond
false. It sees that the predicate of the lowest gamma must be 1. When tracing the possible origins of the predicate, tracing will reach the origin region, in which the only possible value is 0. However, if the middle gamma evaluates the rightmost subregion, it does not matter that the origin region produces a 0. It is still possible for control flow to go from the origin to the target region.Before we consider doing lots of funky logic for handling thins, I am wondering how common situations like the one above really are. For example, if it is rare for a gamma to take control values as entry variables, we can work around the above issue by simply never tracing out of gamma nodes.
Whenever I have seen control typed values being routed into gammas, it has been because of NodePushOut hoisting control constants. If we tell NodePushOut to not move control constants, how many situations are left where control inputs are routed into gammas as entry variables?
I'll make a PR for fixing the first part of this issue, and then see if anything is still going wrong.
FYI @caleridas @phate