aptos-core [Compiler V2] Control flow graph simplification

Description

Implements a stackless bytecode pipeline control_flow_simplifier which simplifies the control flow graph in the following ways:

Eliminates branch or jump to jump: Any empty block

L1: goto L2 where L1 != L2

is removed, and any block jumping to L1 will jump to L2 directly

 goto L1
 => (the => here means the instruction above will be replaced by the instruction below)
 goto L2

if ... goto L1 else ...
=>
if ... goto L2 else ...

if ... goto ... else L1
=>
if ... goto ... else L2

Removes edges where the source has only one successor and the target has only one predecessor: If there is block
```
BB1: xx
     goto L2
```
and block
```
BB2: L2
     yy
```
which has only one predecessor BB1. Then we move BB2 to the end of BB1 so that BB1 becomes
```
BB1: xx
     yy
```
and BB2 is removed.
Removes all jumps to the next instruction: Whenever we have
```
goto L;
L;
```
replace it by simply
```
L;
```
Replaces branch to same target by jump: Whenever we have
```
if ... goto L else goto L
```
replace it by simply
```
goto L
```

Structure of the code

The module control_flow_graph_simplifier.rs includes a

/// Control flow graph that owns the code for transformation
///
/// To do a control flow graph based transformation:
/// 1. construct a `ControlFlowGraphCodeGenerator` from the code,
/// 2. perform the transformation on the `ControlFlowGraphCodeGenerator`
/// 3. generate the code back from the `ControlFlowGraphCodeGenerator`
struct ControlFlowGraphCodeGenerator

and two such CFG based transformations

/// Transformation state for transformation 1 in the module doc
struct EmptyBlockRemover(ControlFlowGraphCodeGenerator);

/// Transformation state for transformation 2 in the module doc
struct RedundantJumpRemover(pub ControlFlowGraphCodeGenerator);

Transformation 3 is implicitly done when converting code to and from ControlFlowGraphCodeGenerator.

A top-level bytecode pipeline does all the transformation (including transformation 4)

/// Simplifies the control flow graph as described in the module doc
pub struct ControlFlowGraphSimplifier {}

Simple experiment

I printed the length of the code before and after the transformation during transactional tests, showing that before the transformation there were 37507 stackless bytecode processed and 32176 after, i.e., reducing the size of the code by 14.21%. The rate is 13.77% if we only enable empty block remover.

Type of Change

[x] New feature
[ ] Bug fix
[ ] Breaking change
[x] Performance improvement
[ ] Refactoring
[ ] Dependency update
[ ] Documentation update
[ ] Tests

Which Components or Systems Does This Change Impact?

[ ] Validator Node
[ ] Full Node (API, Indexer, etc.)
[x] Move/Aptos Virtual Machine
[ ] Aptos Framework
[ ] Aptos CLI/SDK
[ ] Developer Infrastructure
[ ] Other (specify)

Test Plan

Passed all existing unit & transactional tests.

Jan 22 '24 10:01 fEst1ck

⏱️ 10h 52m total CI duration on this PR

Job	Cumulative Duration	Recent Runs
rust-unit-tests	2h 37m	⬜ 🟩 🟩 🟩 🟥 (+1 more)
rust-move-unit-coverage	2h 18m	⬜ 🟩 🟩 🟩 🟩 (+1 more)
windows-build	2h 8m	🟩 🟩 🟩 🟩 🟩 (+1 more)
rust-move-tests	1h 18m	🟥 🟩
run-tests-main-branch	45m	🟩 🟩 🟩 🟥 🟥 (+6 more)
rust-lints	39m	⬜ 🟩 🟩 🟩 🟩 (+1 more)
check	29m	🟥 🟥 🟥 🟩 🟥 (+3 more)
general-lints	16m	🟩 🟩 🟩 🟩 🟩 (+1 more)
check-dynamic-deps	13m	🟩 🟩 🟩 🟩 🟩 (+1 more)
semgrep/ci	3m	🟩 🟩 🟩 🟩 🟩 (+1 more)
file_change_determinator	2m	🟩 🟩 🟩 🟩 🟩 (+6 more)
file_change_determinator	1m	🟩 🟩 🟩 🟩 🟩 (+1 more)
permission-check	43s	🟩 🟩 🟩 🟩 🟩 (+7 more)
permission-check	42s	🟩 🟩 🟩 🟩 🟩 (+7 more)
permission-check	40s	🟩 🟩 🟩 🟩 🟩 (+7 more)
permission-check	33s	🟩 🟩 🟩 🟩 🟩 (+7 more)

🚨 2 jobs on the last run were significantly faster/slower than expected

Job	Duration	vs 7d avg	Delta
windows-build	31m	19m
rust-lints	10m	8m

_{settings ⋅ feedback ⋅ docs ⋅ learn more about trunk.io}

Jan 22 '24 10:01 trunk-io[bot]

Codecov Report

Attention: Patch coverage is 99.10913% with 4 lines in your changes missing coverage. Please review.

Project coverage is 59.6%. Comparing base (362b812) to head (43092f3). Report is 16 commits behind head on main.

Files	Patch %	Lines
...r-v2/src/pipeline/control_flow_graph_simplifier.rs	99.4%	2 Missing :warning:
...model/bytecode/src/stackless_control_flow_graph.rs	96.0%	2 Missing :warning:

Additional details and impacted files

@@            Coverage Diff            @@
##             main   #11725     +/-   ##
=========================================
+ Coverage    59.4%    59.6%   +0.2%     
=========================================
  Files         838      839      +1     
  Lines      204392   205492   +1100     
=========================================
+ Hits       121562   122659   +1097     
- Misses      82830    82833      +3

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

Jan 23 '24 09:01 codecov[bot]

Can we add a small test case or 2 showing critical edges and what happens with them? Some of the break/continue loop tests probably should show critical edges.

Jan 24 '24 22:01 brmataptos

@fEst1ck Your PR description currently says (for "removes edges where the source has only one successor and the target has only one predecessor"):

    BB1: ...
         goto L2
    ...
    BB2: L2 (no other goto L2)
         ...
    =>
    BB1: BB1 content
         BB2 content
         goto L2

This would be an incorrect transformation: the goto L2 at the end of transformed code is not needed. Is the following what you intended to convey, perhaps?

BB1: xx
     goto L2
yy
BB2: L2 (no other goto L2)
     zz

=>

BB1: xx
     zz

edit: even this transformation is not always correct, eg, if yy contains a label L3 and there is a goto L3 somewhere.

Jan 25 '24 14:01 vineethk

@fEst1ck the PR description currently says, for "removes all jumps to the next instruction": goto L; L removed

Perhaps you meant: goto L; L => L? That is, only goto L is removed, not the label?

Jan 25 '24 15:01 vineethk

@vineethk The documentation is wrong. It should be

Removes edges where the source has only one successor and the target has only one predecessor

BB1: xx
     goto L2
// BB1 BB2 don't have to be consecutive in the code
BB2: L2 (no other goto L2)
     yy
=>
BB1: xx
     yy

Removes all jumps to the next instruction": goto L; L removed

Perhaps you meant: goto L; L => L? That is, only goto L is removed, not the label?

Yes.

Jan 25 '24 18:01 fEst1ck

Can we add a small test case or 2 showing critical edges and what happens with them? Some of the break/continue loop tests probably should show critical edges.

The bytecode generator seems to be generating extra empty blocks already. For instance, if we have

while (...) {
    if (...) { break; }
}

Consider the false branch of the branch instruction of the loop condition. The incoming block ends with loop condition branch, so has 2 successors; the outgoing block, which is the end of the while loop, also has 2 predecessors, one the false branch of the loop condition, another from the break. So this should be a critical edge.

I checked the generated CFG, the break doesn't goto the end of of the loop, but goto an extra empty block before jumping to the end of the loop.

But just for testing the critical edge processor, I can clear the empty blocks first, which will create lots of critical edges. I've add a todo for this. @brmataptos

Jan 25 '24 18:01 fEst1ck

@vineethk The documentation is wrong. It should be

Removes edges where the source has only one successor and the target has only one predecessor
BB1: xx
     goto L2
// BB1 BB2 don't have to be consecutive in the code
BB2: L2 (no other goto L2)
     yy
=>
BB1: xx
     yy

I think this specification is incomplete and therefore incorrect. For example, there may be code just before BB2: L2 that falls through to L2 in the original code (but there is no explicit goto L2, so it satisfies the conditions for the transformation). But this behavior is not retained in the transformed code.

Jan 25 '24 19:01 vineethk

I set the PR to draft temporarily since I'm adding more documentation, which facilitates code review.

Jan 25 '24 19:01 fEst1ck

Please mark this PR as non-draft if you consider it ready for general review.

Jan 26 '24 04:01 wrwg

All comments addressed. PTAL @vineethk @brmataptos

Jan 29 '24 09:01 fEst1ck

@brmataptos @wrwg @vineethk The PR has been refactored and ready for review now.

May 15 '24 16:05 fEst1ck

All comments addressed. PTAL @brmataptos @rahxephon89

May 23 '24 09:05 fEst1ck

This issue is stale because it has been open 45 days with no activity. Remove the stale label, comment or push a commit - otherwise this will be closed in 15 days.

Aug 12 '24 01:08 github-actions[bot]

Thanks for the comments. All addressed. PTAL! @vineethk

Aug 23 '24 06:08 fEst1ck

@vineethk All comments addressed. PTAL

Aug 28 '24 07:08 fEst1ck