<div dir="ltr"><div>SimplifyCFG has some code for doing some merging. For example SinkCommonCodeFromPredecessors</div><br clear="all"><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature">~Craig</div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, May 29, 2019 at 11:58 AM Michael Kruse via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Am Mi., 29. Mai 2019 um 13:31 Uhr schrieb Shawn Landden via llvm-dev<br>
<<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>:<br>
><br>
> On Wed, May 29, 2019 at 10:49 AM David Jones via llvm-dev<br>
> <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
> ><br>
> > Under certain circumstances, my compiler outputs basic blocks having the same function:<br>
> ><br>
> > bb_97:                                            ; preds = %bb_1<br>
> >   %476 = getelementptr inbounds %LMtop.I0.ARType, %LMtop.I0.ARType* %0, i64 0, i32 6<br>
> >   %477 = bitcast i8** %476 to %LBstd.Cprocess.CRType**<br>
> >   %478 = load %LBstd.Cprocess.CRType*, %LBstd.Cprocess.CRType** %477, align 8<br>
> >   %479 = getelementptr inbounds %LBstd.Cprocess.CRType, %LBstd.Cprocess.CRType* %478, i64 0, i32 3<br>
> >   %480 = bitcast i8** %479 to %LMtop.I0.ARType**<br>
> >   store %LMtop.I0.ARType* %0, %LMtop.I0.ARType** %480, align 8<br>
> >   br label %bb_106<br>
> ><br>
> > bb_98:                                            ; preds = %bb_1<br>
> >   %481 = getelementptr inbounds %LMtop.I0.ARType, %LMtop.I0.ARType* %0, i64 0, i32 6<br>
> >   %482 = bitcast i8** %481 to %LBstd.Cprocess.CRType**<br>
> >   %483 = load %LBstd.Cprocess.CRType*, %LBstd.Cprocess.CRType** %482, align 8<br>
> >   %484 = getelementptr inbounds %LBstd.Cprocess.CRType, %LBstd.Cprocess.CRType* %483, i64 0, i32 3<br>
> >   %485 = bitcast i8** %484 to %LMtop.I0.ARType**<br>
> >   store %LMtop.I0.ARType* %0, %LMtop.I0.ARType** %485, align 8<br>
> >   br label %bb_106<br>
> ><br>
> > These blocks have provably the same function - the instructions of one correspond perfectly to instructions in the other.<br>
> ><br>
> > I would have expected some optimization to detect this, and merge the blocks by forwarding all jumps to one, to jump to the other.<br>
> ><br>
> > I notice a "merge functions" pass, which does this if two functions can be proven to have identical effect.<br>
> ><br>
> > Is there a pass that merges blocks? Is it enabled by default?  If so, then is there something non-obvious in the code that would be defeating this optimization?<br>
> I see two problems here (neither unsolvable): 1) I believe the<br>
> register allocator is working over a full function, and for this merge<br>
> the registers and stack/frame offsets have to be the same. 2) if the<br>
> block very small the icache might not work as well, and on some arches<br>
> long jumps are more expensive than short jumps and require trunks.<br>
<br>
I understand this request differently. This is on LLVM-IR, so register<br>
allocation would happen on the merged block. I-Cache utilization<br>
should improve since there is less code in the merged blocked compared<br>
to the two original blocks.<br>
<br>
I could imagine an algorithm that checks whether the two blocks are<br>
isomorphic and have the same jump targets. Then merge the two blocks<br>
(including adding PHIs if the blocks have different predecessors) by<br>
RAUW one block with this other.<br>
<br>
In the example, both blocks have the same predecessor, i.e. it will be<br>
a conditional branch. In this case the transformation (after having<br>
determined that the blocks are isomorphic) would change it to an<br>
unconditional branch to one of the blocks. The other one becomes dead<br>
code.<br>
<br>
The question is, whether the improvement justifies the additional cost<br>
of identifying isomorphic blocks.<br>
<br>
Michael<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>