Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Codegen] Control Flow Detection Generates Infinite Goto-Loop with Continue #1586

Open
phschaad opened this issue Jun 10, 2024 · 2 comments · May be fixed by #1676
Open

[Codegen] Control Flow Detection Generates Infinite Goto-Loop with Continue #1586

phschaad opened this issue Jun 10, 2024 · 2 comments · May be fixed by #1676
Labels
bug Something isn't working codegen critical This is urgent and / or affects many systems or people

Comments

@phschaad
Copy link
Collaborator

When generating code for an SDFG with a single for loop containing a continue statement, codegen generates an infinite loop by inserting a wrongful goto in place of a continue statement.
The behavior occurs with Python 3.7, automatic simplification disabled, and control flow detection enabled (as is the default).

A minimal example SDFG that exposes the issue is shown here:
image

The following code is generated:

void __program_test_for_continue_internal(test_for_continue_state_t*__state, int * __restrict__ A)
{
    long long i;
    for (i = 0; (i < 10); i = i+1) {
        if (((i % 2) == 0)) {
            if (false) {
            }
            __state_0_s_6:;
        }
        {
            {
                int o1;
                ///////////////////
                // Tasklet code (assign)
                o1 = i;
                ///////////////////
                A[i] = o1;
            }
        }
        goto __state_0_s_6;
    }
}

Evidently, the goto to label __state_0_s_6 causes an infinite loop. The expected behavior would be that:

  • Either a continue is generated in place of the label __state_0_s_6
  • or the position of the label and the goto statements is inverted.

The issue can be reproduced by running the test found here: https://github.com/spcl/dace/blob/cfg_detection_infinite_loop_bug/tests/control_flow_test.py#L351

Note:
This is a blocking issue for one of the final Loops PRs as it causes a single test to hang: #1475

@phschaad phschaad added bug Something isn't working codegen critical This is urgent and / or affects many systems or people labels Jun 10, 2024
github-merge-queue bot pushed a commit that referenced this issue Jun 26, 2024
This PR lets the Python and Fortran frontends (optionally) generate
`LoopRegion`s for DaCe programs. This forms the third core element of
the [plan to make loops first class citizens of
SDFGs](https://github.com/orgs/spcl/projects/10).

This PR is fully backwards compatible. `LoopRegion`s are always
generated from new Python DaCe programs, and the legacy way of
constructing a while / for loop is gone to remove complexity. To provide
backwards compatibility, these `LoopRegion`s are by default immediately
inlined into a traditional single level state machine loop as soon as
program parsing is completed, before simplification and / or validation.
However, an optional boolean parameter `use_experimental_cfg_blocks` can
be set to True when declaring a DaCe program in Python to enable their
use, which skips this inlining step.

Example use:
```Python
import dace
import numpy

N = dace.symbol('N')

@dace.program(use_experimental_cfg_blocks=True):
def mat_mult(A: dace.float64[N, N], B: dace.float64[N, N]):
    return A @ B

# OR:
mat_mult.use_experimental_cfg_blocks = True
sdfg = mat_mult.to_sdfg()
```

The Fortran frontend similarly only utilizes `LoopRegions` if an
additional parameter `use_experimenatl_cfg_blocks` is passed to the
parser together with the program.

Many passes and transformations (including in simplify) do not yet have
the capability of handling the new, hierarchical SDFGs. To not break the
pipeline and to provide backwards compatibility, a new decorator
`@single_level_sdfg_only` has been added, which can be (and has been)
placed over any pass or transformation that is not compatible with the
new style SDFGs. Passes annotated with this decorator are skipped in all
pipelines where they occur and instead generate warnings that they were
skipped due to compatibility issues.

For more information on `LoopRegion`s please refer to the [PR that
introduced them](#1407).

**Important Note about disabled tests:**
Certain Python frontend loop tests have been disabled. Specifically,
this concerns tests where either the loop structure (using
continue/break) or other conditional statements cause the generation of
control flow that looks irregular before the simplification pass is
applied. The reason being that the frontend generates branches with one
branch condition being set to constant `False` when generating continue
/ break / return, or while/for-else clauses. These branches are
trivially removed during simplification, but not running simplification
(as part of our CI does) leads to irregular control flow which is
handled poorly by our codegen-time control flow detection. This error
has so far gone unnoticed in these tests because of sheer luck, but is
now exposed through a ever so slightly different state machine being
generated by control flow region and loop inlining.

The goal is for a subsequent PR to completely adapt codegen to make use
of the control flow region constructs, thereby fixing this issue and
re-enabling the tests. For more information about the issue, see #635
and #1586.

Linked to:
https://github.com/orgs/spcl/projects/10/views/4?pane=issue&itemId=42047238
and
https://github.com/orgs/spcl/projects/10/views/4?pane=issue&itemId=42151188
github-merge-queue bot pushed a commit that referenced this issue Jul 5, 2024
This PR adapts code generation to make use of hierarchical control flow
regions, and by extension `LoopRegion`s. This forms the fourth core
element of the [plan to make loops first class citizens of
SDFGs](https://github.com/orgs/spcl/projects/10) and marks the last
element in the architecture.

By extending codegen with the capability of handling hierarchical
control flow graphs and SDFGs, a myriad of complexities that come with
control flow detection are circumvented, which currently lead to
significant issues for certain SDFGs (e.g., #635 and #1586). Making use
of control flow regions such as `LoopRegion`s instead allows codegen to
be much less 'smart' and behave more akin to a lookup table that decides
what code to generate for what SDFG element, making it significantly
less error prone.
@tbennun
Copy link
Collaborator

tbennun commented Oct 29, 2024

@phschaad still an issue?

@phschaad
Copy link
Collaborator Author

With #1676, this is no longer an issue.

@phschaad phschaad linked a pull request Oct 29, 2024 that will close this issue
12 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working codegen critical This is urgent and / or affects many systems or people
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants