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

IR verification error during testing of UnicodePlots.jl #52858

Closed
maleadt opened this issue Jan 11, 2024 · 1 comment · Fixed by #52863
Closed

IR verification error during testing of UnicodePlots.jl #52858

maleadt opened this issue Jan 11, 2024 · 1 comment · Fixed by #52863
Assignees
Labels
bug Indicates an unexpected problem or unintended behavior compiler:optimizer Optimization passes (mostly in base/compiler/ssair/)

Comments

@maleadt
Copy link
Member

maleadt commented Jan 11, 2024

As seen during testing of UnicodePlots.jl with -g2:

Edge 33 of φ node 94 not in predecessor list
216 1 ── %1   = Base.sitofp(Float64, _6)::Float64
    │    %2   = Base.div_float(%1, 4.0)::Float64
217 │    %3   = Base.sitofp(Float64, _7)::Float64
    │    %4   = Base.div_float(%3, 2.0)::Float64
221 │    %5   = Base.div_float(%4, %2)::Float64
225 │    %6   = Base.ceil_llvm(%2)::Float64
    │    %7   = Base.le_float(-9.223372036854776e18, %6)::Bool
    └───        goto #3 if not %7
    2 ── %9   = Base.lt_float(%6, 9.223372036854776e18)::Bool
    └───        goto #4
    3 ──        nothing::Nothing
    4 ┄─ %12  = φ (#2 => %9, #3 => false)::Bool
    └───        goto #7 if not %12
    5 ── %14  = Base.trunc_llvm(%6)::Float64
    │    %15  = Base.sub_float(%6, %14)::Float64
    │    %16  = Base.eq_float(%15, 0.0)::Bool
    │    %17  = Base.and_int(%16, true)::Bool
    │    %18  = Base.and_int(%17, true)::Bool
    └───        goto #7 if not %18
    6 ──        goto #8
    7 ┄─ %21  = invoke Base.InexactError(:Int64::Symbol, Int64::Any, %6::Vararg{Any})::InexactError
    │           Base.throw(%21)::Union{}
    └───        unreachable
    8 ──        goto #9
    9 ──        goto #10
    10 ─        goto #11
226 11 ─ %27  = Base.ceil_llvm(%4)::Float64
    │    %28  = Base.le_float(-9.223372036854776e18, %27)::Bool
    └───        goto #13 if not %28
    12 ─ %30  = Base.lt_float(%27, 9.223372036854776e18)::Bool
    └───        goto #14
    13 ─        nothing::Nothing
    14 ┄ %33  = φ (#12 => %30, #13 => false)::Bool
    └───        goto #17 if not %33
    15 ─ %35  = Base.trunc_llvm(%27)::Float64
    │    %36  = Base.sub_float(%27, %35)::Float64
    │    %37  = Base.eq_float(%36, 0.0)::Bool
    │    %38  = Base.and_int(%37, true)::Bool
    │    %39  = Base.and_int(%38, true)::Bool
    └───        goto #17 if not %39
    16 ─        goto #18
    17 ┄ %42  = invoke Base.InexactError(:Int64::Symbol, Int64::Any, %27::Vararg{Any})::InexactError
    │           Base.throw(%42)::Union{}
    └───        unreachable
    18 ─        goto #19
    19 ─        goto #20
    20 ─        goto #21
229 21 ─ %48  = UnicodePlots.string::Core.Const(string)
    │    %49  = invoke Base.:(var"#string#518")(10::Int64, 1::Int64, %48::typeof(string), _7::Int64)::String
    │    %50  = invoke UnicodePlots.length(%49::String)::Int64
    │    %51  = Base.add_int(_12, _13)::Int64
    │    %52  = Base.add_int(%51, %50)::Int64
    │    %53  = Base.add_int(%52, _3)::Int64
231 │    %54  = invoke UnicodePlots.displaysize()::Tuple{Int64, Int64}
    │    %55  = Base.getfield(%54, 1)::Int64
    │    %56  = Base.getfield(%54, 2)::Int64
232 │    %57  = Base.slt_int(0, _8)::Bool
    └───        goto #23 if not %57
    22 ─        goto #24
    23 ─ %60  = Base.sub_int(%55, _2)::Int64
    24 ┄ %61  = φ (#22 => _8, #23 => %60)::Int64
233 │    %62  = Base.slt_int(0, _9)::Bool
    └───        goto #26 if not %62
    25 ─        goto #27
    26 ─ %65  = Base.sub_int(%56, %53)::Int64
    27 ┄ %66  = φ (#25 => _9, #26 => %65)::Int64
235 │    %67  = (_6 === 0)::Bool
    └───        goto #31 if not %67
    28 ─ %69  = (_7 === 0)::Bool
    └───        goto #30 if not %69
    29 ─ %71  = Core.tuple(0, 0, %66, %61)::Core.PartialStruct(NTuple{4, Int64}, Any[Core.Const(0), Core.Const(0), Int64, Int64])
    └───        return %71
    30 ─        nothing::Nothing
    31 ┄        nothing::Nothing
    32 ─        nothing::Nothing
    33 ─        nothing::Nothing
259 34 ─ %77  = Base.slt_int(0, _11)::Bool
    └───        goto #36 if not %77
260 35 ─ %79  = Base.sitofp(Float64, _11)::Float64
    │    %80  = Base.div_float(%79, %5)::Float64
    │    %81  = Base.sitofp(Float64, %61)::Float64
    │    %82  = Base.sub_float(%80, %81)::Float64
    │    %83  = Base.bitcast(Base.Int64, %82)::Int64
    │    %84  = Base.slt_int(%83, 0)::Bool
    │    %85  = Core.ifelse(%84, %80, %81)::Float64
    │    %86  = Core.ifelse(%84, true, true)::Bool
    │    %87  = Core.ifelse(%84, true, true)::Bool
    │    %88  = Base.ne_float(%80, %80)::Bool
    │    %89  = Base.ne_float(%81, %81)::Bool
    │    %90  = Base.or_int(%88, %89)::Bool
    │    %91  = Core.ifelse(%90, %82, %85)::Float64
    │    %92  = Core.ifelse(%90, true, %86)::Bool
    └─── %93  = Core.ifelse(%90, true, %87)::Bool
263 36 ┄ %94  = φ (#35 => %92, #34 => false, #33 => false)::Bool
    │    %95  = φ (#35 => %93, #34 => false, #33 => false)::Bool
    │    %96  = φ (#35 => %91, #34 => _10, #33 => _10)::Union{Nothing, Float64}
    └───        goto #38 if not _15
    37 ─ %98  = UnicodePlots.ASPECT_RATIO::Core.Const(Base.RefValue{Float64}(1.3333333333333333))
    │    %99  = Base.getfield(%98, :x)::Float64
    └───        goto #39
    38 ─        nothing::Nothing
    39 ┄ %102 = φ (#37 => true, #38 => false)::Bool
    │    %103 = φ (#37 => false, #38 => true)::Bool
    │    %104 = φ (#37 => %99, #38 => 1)::Union{Float64, Int64}
    │    %105 = (Core.Intrinsics.and_int)(%94, %102)::Bool
    └───        goto #41 if not %105
    40 ─ %107 = π (%96, Float64)
    │    %108 = π (%104, Float64)
    │    %109 = Base.div_float(%107, %108)::Float64
    └───        goto #44
    41 ─ %111 = (Core.Intrinsics.and_int)(%95, %103)::Bool
    └───        goto #43 if not %111
    42 ─ %113 = π (%96, Float64)
    │    %114 = π (%104, Int64)
    │    %115 = Base.sitofp(Float64, %114)::Float64
    │    %116 = Base.div_float(%113, %115)::Float64
    └───        goto #44
    43 ─ %118 = (%96 / %104)::Float64
    └───        goto #44
    44 ┄ %120 = φ (#40 => %109, #42 => %116, #43 => %118)::Float64
    │    %121 = Base.rint_llvm(%120)::Float64
    │    %122 = Base.le_float(-9.223372036854776e18, %121)::Bool
    └───        goto #46 if not %122
    45 ─ %124 = Base.lt_float(%121, 9.223372036854776e18)::Bool
    └───        goto #47
    46 ─        nothing::Nothing
    47 ┄ %127 = φ (#45 => %124, #46 => false)::Bool
    └───        goto #50 if not %127
    48 ─ %129 = Base.trunc_llvm(%121)::Float64
    │    %130 = Base.sub_float(%121, %129)::Float64
    │    %131 = Base.eq_float(%130, 0.0)::Bool
    │    %132 = Base.and_int(%131, true)::Bool
    │    %133 = Base.and_int(%132, true)::Bool
    └───        goto #50 if not %133
    49 ─ %135 = Base.fptosi(Int64, %121)::Int64
    └───        goto #51
    50 ┄ %137 = invoke Base.InexactError(:Int64::Symbol, Int64::Any, %121::Vararg{Any})::InexactError
    │           Base.throw(%137)::Union{}
    └───        unreachable
    51 ─        goto #52
    52 ─        goto #53
    53 ─        goto #54
267 54 ─ %143 = Core.tuple(%135, _11, %61, %66)::NTuple{4, Int64}
    └───        return %143
    

Reduced to:

function foo(max_height=0, height=nothing)
    if height === nothing && width > 0
        height = min(1, max_height)
    end
    height / 0
end
foo()
Edge 1 of φ node 8 not in predecessor list
  1 ─       nothing::Nothing
2 2 ─ %2  = Main.width::Any
  │   %3  = (%2 > 0)::Any
  └──       goto #4 if not %3
3 3 ─ %5  = Base.slt_int(_2, 1)::Bool
  │   %6  = Core.ifelse(%5, _2, 1)::Int64
  └── %7  = Core.ifelse(%5, true, true)::Bool
5 4 ┄ %8  = φ (#3 => %7, #2 => false, #1 => false)::Bool
  │   %9  = φ (#3 => %6, #2 => _3, #1 => _3)::Union{Nothing, Int64}
  └──       goto #6 if not %8
  5 ─ %11 = π (%9, Int64)
  │   %12 = Base.sitofp(Float64, %11)::Float64
  │   %13 = Base.div_float(%12, 0.0)::Float64
  └──       goto #7
  6 ─ %15 = (%9 / 0)::Float64
  └──       goto #7
  7 ┄ %17 = φ (#5 => %13, #6 => %15)::Float64
  └──       return %17

Bisected to #51754; cc @Keno. This is a different issue than #52846, and #52853 does not fix it.

@maleadt maleadt added bug Indicates an unexpected problem or unintended behavior compiler:optimizer Optimization passes (mostly in base/compiler/ssair/) labels Jan 11, 2024
@Keno
Copy link
Member

Keno commented Jan 11, 2024

At least in the reproducer this is a bug in CompactPeekIterator. I'll try to fix it.

@Keno Keno self-assigned this Jan 11, 2024
Keno added a commit that referenced this issue Jan 11, 2024
When IncremetnalCompact deletes and edge between blocks, it needs
to go to the target and delete any reference to the edge from
the PhiNodes therein. What happened in #52858, is that we had
a situtation like:

```
# Block n-1
%a Expr(...)
Expr(...) # <- This node is pending at the start of compaction
# Block n
%b PhiNode
```

To do the deletion, we use `CompactPeekIterator`, which gets
a list of original statements and iterates over all the statements
inside the range, including pending ones. However, there is a
semantic confusion about whether to include all all statements
since the previous statement (%a above), or only those statements
that are actually attached to the first instruction (%b above).
This of course doesn't really matter usually unless you're at
a BasicBlock boundary.

For the present case, we really do not want the instructions in
the previous basic block - the iteration of PhiNodes terminates
if it seems a stmt that cannot be in the phi block, so mistakenly
seeing one of those instructions causes it to fail to fix a PhiNode
that it should have, causing #52858.

We fix #52858 by giving the CompactPeekIterator a flag to only
return stmts in the correct basic block. While we're at it, also
fix the condition for what kinds of statements are allowed in the
phi block, as that was clarified more recently than this code
was written.
Keno added a commit that referenced this issue Jan 12, 2024
#52863)

When IncremetnalCompact deletes and edge between blocks, it needs to go
to the target and delete any reference to the edge from the PhiNodes
therein. What happened in #52858, is that we had a situtation like:

```
# Block n-1
%a Expr(...)
Expr(...) # <- This node is pending at the start of compaction
# Block n
%b PhiNode
```

To do the deletion, we use `CompactPeekIterator`, which gets a list of
original statements and iterates over all the statements inside the
range, including pending ones. However, there is a semantic confusion
about whether to include all all statements since the previous statement
(%a above), or only those statements that are actually attached to the
first instruction (%b above). This of course doesn't really matter
usually unless you're at a BasicBlock boundary.

For the present case, we really do not want the instructions in the
previous basic block - the iteration of PhiNodes terminates if it seems
a stmt that cannot be in the phi block, so mistakenly seeing one of
those instructions causes it to fail to fix a PhiNode that it should
have, causing #52858.

We fix #52858 by giving the CompactPeekIterator a flag to only return
stmts in the correct basic block. While we're at it, also fix the
condition for what kinds of statements are allowed in the phi block, as
that was clarified more recently than this code was written.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Indicates an unexpected problem or unintended behavior compiler:optimizer Optimization passes (mostly in base/compiler/ssair/)
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants