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

Flaws in escape analysis may result in incorrect optimization #6152

Closed
IGI-111 opened this issue Jun 20, 2024 · 2 comments · Fixed by #6175
Closed

Flaws in escape analysis may result in incorrect optimization #6152

IGI-111 opened this issue Jun 20, 2024 · 2 comments · Fixed by #6175
Assignees
Labels
audit-report Related to the audit report bug Something isn't working compiler: ir IRgen and sway-ir including optimization passes compiler: optimization IR Optimization Passes P: high Should be looked at if there are no critical issues left

Comments

@IGI-111
Copy link
Contributor

IGI-111 commented Jun 20, 2024

Several passes rely on the escape_analysis here. Unfortunately, we've noticed flaws within the implementation which could lead to incorrect optimization. Taking dce as example, due to imprecise symbol tracking, the attached PoC script would be incorrectly optimized, and the store in main will be removed. The immediate cause seems to be load / store / escape symbol resolve ignoring the Incomplete tag of ReferredSymbols (1) / (2) / (3), but it is also reasonable to attribute this to incorrect instruction effect modeling. An easy fix would be making all optimizations more conservative (e.g. give up when escaped symbol is Incomplete), however, this might limit the effectiveness of optimization passes. Notably, instruction modeling is a complex topic which has been a major source of bugs in compilers (e.g. v8 jit), and even one incorrect effect modeling would lead to failure of the entire algorithm. While the ir instruction set is a lot more limited in sway, it would still be really difficult for us to guarantee correctness if algorithm is not sufficiently conservative.

@IGI-111 IGI-111 added bug Something isn't working compiler: ir IRgen and sway-ir including optimization passes compiler: optimization IR Optimization Passes P: high Should be looked at if there are no critical issues left labels Jun 20, 2024
@ironcev
Copy link
Member

ironcev commented Jun 20, 2024

The sample PoC script in which the store gets erroneously optimized away.

script {
  fn main() -> u64 {
    local u64 S

    entry():
    br block0()

    block0():
    c0 = const u64 123
    p = get_local ptr u64, S
    store c0 to p
    p_d = cast_ptr p to ptr u8
    p_val = ptr_to_int p_d to u64
    p_val_aug = add p_val, c0
    p_val_res = sub p_val_aug, c0
    res = call test(p_val_res)
    ret u64 res
  }

  fn test(arg: u64) -> u64 {
    entry(arg: u64):
    br block0(arg)

    block0(arg: ptr u64):
    v0 = load arg
    ret u64 v0
  }
}

@ironcev
Copy link
Member

ironcev commented Jun 20, 2024

Related to #5924.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
audit-report Related to the audit report bug Something isn't working compiler: ir IRgen and sway-ir including optimization passes compiler: optimization IR Optimization Passes P: high Should be looked at if there are no critical issues left
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants