WIP: Re-fold basic-block split edges in regalloc#950
WIP: Re-fold basic-block split edges in regalloc#950sstangl wants to merge 3 commits intobytecodealliance:masterfrom sstangl:branch-splitting-folding
Conversation
|
@sstangl: [..] it's possible that I could update the bforest to support deletion [..] Just to note .. it seems at least moderately likely that I'll have to get my head around the bforest machinery as part of my (so far ineffective) attempts to reduce CL's run time. If that happens, I could maybe hack up the changes you need. |
|
Just as an aside, could you please git rebase on top of master? This PR includes many unrelated commits, making it hard to see what's going on. |
TODO: It would be better to avoid recomputing the liveness. FIXME: I commented-out the binemit/relaxation.rs code that does folding.
|
Unfortunately it applies to nbp's "branch-splitting" branch, not to master. I deleted all the commits that are between "branch-splitting" and the changes I made. This patch won't actually compile, because it depends on |
|
I am going to merge the branch-splitting branch soon. Otherwise, you could target the branch-splitting branch on my repository to reduce the diff, my branch recently merged from master and should not have a larger diff. |
nbp
left a comment
There was a problem hiding this comment.
I am much more in favor of keeping branch folding of empty blocks, even if this has to be restricted to cases where there is no branch parameter first than making it a special phased tied to branch splitting.
This graph transformation is useful even when branch splitting is not used.
| domtree: &mut DominatorTree, | ||
| topo: &mut TopoOrder, | ||
| ) { | ||
| ) -> Vec<Ebb> { |
There was a problem hiding this comment.
Looking at the rest of the Cranelift phases, usually it seems that these values are provided at a &mut as argument of the run command instead of returned from the run function. Then the clear function of the register allocator is used to clean the content of the vector, to be reused without reallocation for the next compiled function.
| // Pass: undo branch splitting where the inserted blocks were not | ||
| // used by the register allocator. | ||
| #[cfg(feature = "basic-blocks")] | ||
| branch_folding::run(func, cfg, domtree, new_blocks); |
There was a problem hiding this comment.
I still think this belongs to the branch relaxation part of the code. Doing so as part of the branch relaxation would avoid recomputing the liveness information.
| // Pass the ebb_jump_params in the parent_jump_params. | ||
| // No rewriting is needed, because the edge ebb is parameterless. | ||
| debug_assert!(_parent_jump_params.len() == 0); | ||
| debug_assert!(func.dfg.num_ebb_params(ebb) == 0); |
There was a problem hiding this comment.
From my understanding this is the only thing to be added to the version which is currently merged. Just excluding any blocks with parameters would avoid the issue we have with folding empty branches without even looking at the branch splitting case.
|
Close the pull-request as it is replaced by #972. |
This patch unregresses the extra jumps in the codegen introduced by basic-block branch splitting.
This is a simpler version of the fold-redundant-branches code that is much easier to get correct. The issue with the previous pass was that some ebbs were functioning as phi nodes in the CFG, and those blocks were not actually redundant. This patch only considers blocks that were added specifically by regalloc (in nbp's branch-splitting patch), therefore none of the blocks are effective phis, and they're formed predictably.
This is a WIP patch. If this looks good, I'll muddle through data structures to clean it up. In particular, deleting an ebb means that we need to update the Liveness struct -- currently, it just recomputes the entire data structure, but it's possible that I could update the bforest to support deletion. Although with trees, that's fairly error-prone.
At this point, just soliciting comments.