Skip to content

IncrementalCompact: fix display of basic block boundaries.#47043

Merged
maleadt merged 1 commit intomasterfrom
tb/ircompact_bbs
Oct 4, 2022
Merged

IncrementalCompact: fix display of basic block boundaries.#47043
maleadt merged 1 commit intomasterfrom
tb/ircompact_bbs

Conversation

@maleadt
Copy link
Copy Markdown
Member

@maleadt maleadt commented Oct 4, 2022

Fixes #46424 again, as the first attempt in #46644 was insufficient.

The problem with CFGs during incremental compaction is that the basic block boundaries are not properly determined until after compaction. We rely on finish_current_bb! to finalize a bb, but that only triggers when we've seen all the statements in a block. That's a problem when displaying part of a compacted block, resulting in an incorrect bb_idx and display breaking down:

# at some point during compaction

compact_cfg = CFG with 3 blocks:
  bb 1 (stmts 1:3) → bb 3, 2
  bb 2 (stmt 4)
  bb 3 (stmt 5)

91 1 ─ %1 = Base.add_int(_2, 42)::Int64                                 │╻ +
92 │        identity(1)::Int64 (inserted)                               │╻ ==
   └──      identity(2)::Int64 (inserted)                               │
   2 ─      identity(3)::Int64 (inserted)                               │
   3 ─      (%1 === 1)::Bool                                            │
──────────────────────────────────────────────────────────────────────────────
   !!! ─      goto #3 if not %2                                         │
   !!! ─      return 1                                                  │
   !!! ─      return 2                                                  │

# finish_current_bb! hasn't triggered yet, so `result_bbs` isn't updated,
# but we have already inserted 3 nodes!


# this is corrected at the next iteration when we encounter the terminator

compact_cfg = CFG with 3 blocks:
  bb 1 (stmts 1:6) → bb 3, 2
  bb 2 (stmts 7:4)
  bb 3 (stmt 5)

91 1 ─ %1 = Base.add_int(_2, 42)::Int64                                 │╻ +
92 │        identity(1)::Int64                                          │╻ ==
   │        identity(2)::Int64                                          │
   │        identity(3)::Int64                                          │
   │   %5 = (%1 === 1)::Bool                                            │
   └── %6 = goto #3 if not %5                                           !
──────────────────────────────────────────────────────────────────────────────
   2 ─      return 1                                                    │
   3 ─      return 2                                                    │

Similarly, finish_current_bb! also updates the start statement index of the next basic block. That's a problem when the boundary of the compacted and uncompacted nodes is at the boundary of two basic blocks, because we then call show_ir_stmts with a CFG where the current active block has a broken statement range (the start is an index into result_bbs, while the end is still an index into the original instruction stream).

# at some point during compaction (notice the stmt range 7:4)

cfg = compact.ir.cfg = CFG with 3 blocks:
  bb 1 (stmts 1:6) → bb 3, 2
  bb 2 (stmts 7:4)
  bb 3 (stmt 5)

91 1 ─ %1 = Base.add_int(_2, 42)::Int64                                 │╻ +
92 │        identity(1)::Int64                                          │╻ ==
   │        identity(2)::Int64                                          │
   │        identity(3)::Int64                                          │
   │   %5 = (%1 === 1)::Bool                                            │
   └── %6 = goto #3 if not %5                                           !
──────────────────────────────────────────────────────────────────────────────
   │        return 1                                                    │
   │        return 2                                                    │

# notice the lack of block reoprting, despite bb_idx correctly being set to 2


# this is corrected during the next iteration:

cfg = compact.ir.cfg = CFG with 3 blocks:
  bb 1 (stmts 1:6) → bb 3, 2
  bb 2 (stmt 7)
  bb 3 (stmts 8:5)

91 1 ─ %1 = Base.add_int(_2, 42)::Int64                                 │╻ +
92 │        identity(1)::Int64                                          │╻ ==
   │        identity(2)::Int64                                          │
   │        identity(3)::Int64                                          │
   │   %5 = (%1 === 1)::Bool                                            │
   └── %6 = goto #3 if not %5                                           !
   2 ─      return 1                                                    !
──────────────────────────────────────────────────────────────────────────────
   │        return 2                                                    │

# but now of course the same happens for bb 3

I don't particularly like the patching-up of CFGs in show_ir, but the alternative (changing how finalize_current_bb! works and is invoked) seemed like a way more riskier change.

@maleadt maleadt added display and printing Aesthetics and correctness of printed representations of objects. compiler:optimizer Optimization passes (mostly in base/compiler/ssair/) labels Oct 4, 2022
@maleadt maleadt requested a review from Keno October 4, 2022 11:54
Keno
Keno approved these changes Oct 4, 2022
View reviewed changes
Copy link
Copy Markdown
Member

@Keno Keno left a comment

Choose a reason for hiding this comment

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

Good enough for now, I think. To my mind, the most important thing here is to get in test cases for all the interesting cases, so we have a spec for what should happen next time we take a pick refactor to this.

@maleadt maleadt merged commit 81c7220 into master Oct 4, 2022
@maleadt maleadt deleted the tb/ircompact_bbs branch October 4, 2022 20:04
@maleadt
Copy link
Copy Markdown
Member Author

maleadt commented Oct 4, 2022 •
edited
Loading

OK. I didn't want to start out with substantial changes as I'm not very familiar with this code yet, but feel free to suggest things to refactor.

Keno added a commit that referenced this pull request Oct 12, 2022
@Keno
irshow: Fix CFG display with directly inserted new nodes
c7dbe7f 
Slight fix to #47043 for the case where nodes where inserted using
`insert_node_here!`.
Keno added a commit that referenced this pull request Oct 12, 2022
@Keno
irshow: Fix CFG display with directly inserted new nodes
a905514 
Slight fix to #47043 for the case where nodes where inserted using
`insert_node_here!`.
@Keno Keno mentioned this pull request Oct 12, 2022
Merged
DilumAluthge pushed a commit that referenced this pull request Oct 13, 2022
@Keno @DilumAluthge
irshow: Fix CFG display with directly inserted new nodes
97325da 
Slight fix to #47043 for the case where nodes where inserted using
`insert_node_here!`.
aviatesk pushed a commit that referenced this pull request Oct 13, 2022
@Keno
irshow: Fix CFG display with directly inserted new nodes (#47135)
08d5b0d 
Slight fix to #47043 for the case where nodes where inserted using
`insert_node_here!`.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@Keno Keno Keno approved these changes

Assignees

No one assigned

Labels

compiler:optimizer Optimization passes (mostly in base/compiler/ssair/) display and printing Aesthetics and correctness of printed representations of objects.

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

show(::IncrementalCompact) reports incorrect basic blocks

2 participants

@maleadt @Keno