Skip to content
This repository was archived by the owner on Oct 31, 2025. It is now read-only.

New structurizer: now with ∞% more φ!#287

Merged
mergify[bot] merged 1 commit intoEmbarkStudios:mainfrom
LykenSol:new-structurizer
Dec 2, 2020
Merged

New structurizer: now with ∞% more φ!#287
mergify[bot] merged 1 commit intoEmbarkStudios:mainfrom
LykenSol:new-structurizer

Conversation

@eddyb
Copy link
Copy Markdown
Contributor

@eddyb eddyb commented Nov 30, 2020

Not sure this is ready, but it seems to handle everything I've thrown at it.

In an effort to test it, I came up with this silly example:

(click to open example code + graph rendering)
pub fn marker() {}

pub fn shortcircuit_and(a: bool, b: bool) {
    if a && b {
        marker();
    }
}

pub fn nested_while_loop(a: bool, b: bool) {
    while a {
        let mut i = 0;
        loop {
            marker();
            match i {
                0 | 1 | 2 | 4 => {}
                5 => break,
                _ => continue,
            }
            marker();
            i += 1;
        }
        if a & b {
            break;
        }
        if a | b {
            return;
        }
        while b {
            marker();
        }
    }
}

I was inspired by the loop-specific solution of "threading all exits through one break (with a tag indicating which to take when outside the loop)" and tried to extend it to handle non-structural acyclic branches as well - the result is this PR.

You can see all the OpPhis, which are used to decide whether a "deferred exit" executes, when it's finally "fully accounted for" (or "owned"? not sure what the best terminology is) by a "region".

Most of the implementation is a SEME -> SESE propagation (with the aforementioned "deferred exits"), which is then used to handle both acyclic and cyclic "regions".

@eddyb eddyb requested review from VZout and khyperia November 30, 2020 13:53
Copy link
Copy Markdown
Contributor

@khyperia khyperia left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I do not believe I am qualified to review new_structurizer.rs, nor am I going to try to other than a quick glance-over, because wow okay that's a lot of algorithm. Other than that, though, I think this is good to merge! (not hitting the approve button because mergify scares me)

assert_eq!(func.blocks[0].label_id().unwrap(), entry_label);
}

// FIXME(eddyb) use `Either`, `Cow`, and/or `SmallVec`.
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

👍 ✅ 🆗 💯

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Either<Cow, SmallVec>

Copy link
Copy Markdown
Member

@VZout VZout left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I assume cargo test was successful. Seems way better than my code& algorithm. Haven't ran spirv-cfg to see if I can see any weird things.

@eddyb eddyb marked this pull request as ready for review December 2, 2020 10:32
// fixed, a further underlying issue gets triggered instead, which is that the current structurizer
// doesn't handle this case. Remove `#[ignore]` once fixed.
#[test]
#[ignore]
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

heck yee, love yeeting #[ignore]s

@mergify mergify bot merged commit e02bead into EmbarkStudios:main Dec 2, 2020
@eddyb eddyb deleted the new-structurizer branch December 2, 2020 11:05
@khyperia khyperia mentioned this pull request Dec 2, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants