[LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation

[Chad Rosier]

Thanks, Mark.  I will give the paper a look.

On Tue, Aug 6, 2013 at 1:42 PM, Mark Lacey <mark.lacey at apple.com> wrote:

> Hi Chad,
>
> On Aug 6, 2013, at 7:46 AM, Chad Rosier <chad.rosier at gmail.com> wrote:
>
> > All,
> > I have some code that looks like the following:
> >
> > {
> >   double a, b, c;
> >   for (...) {
> >     ...
> >     a = lots of FP math;
> >     b = lots of FP math;
> >     c = lots of FP math;
> >     if (cond) {
> >       a = 0.0;
> >       b = 0.1;
> >       c = 0.2;
> >     }
> >    ...
> >   }
> > }
> >
> > Could we not convert the hammock into a diamond and move the initial
> computation of a, b, and c into the else block.  Something like this:
> >
> > {
> >   double a, b, c;
> >   for (...) {
> >     ...
> >     if (cond) {
> >       a = 0.0;
> >       b = 0.1;
> >       c = 0.2;
> >     } else {
> >       a = lots of FP math;
> >       b = lots of FP math;
> >       c = lots of FP math;
> >     }
> >    ...
> >   }
> > }
> >
> > Does a similar optimization exist?  If not, would the SimplifyCFG pass
> be an appropriate home for such an optimization?
>
> I am not sure if something similar exists in LLVM today. The optimization
> you are looking for is called partial dead code elimination (PDE).
>
> I do not think SimplifyCFG would be a great place to put this as that is
> primarily about cleaning up control flow. I think it deserves its own pass.
>
> The most general formulation would result in sinking instructions,
> including loads (and possibly some other side-effecting instructions when
> safe to do so), along with potentially duplicating code when the results
> are dead on some paths below the definition, but not all.
>
> It seems like you could do a simpler formulation that just splits critical
> edges, and then moves instructions that have no side effects and have only
> a single use, to just before to the use (in this case it would be just
> prior to the phi in the new block created when splitting edges). You would
> also need to be careful not to sink code into loops - you would instead
> want to sink it below code that guards the loop, but not actually into the
> loop.
>
> Here is one paper I am aware of that appears to have an SSA-based
> formulation of PDE. I have not read this as it is behind a paywall:
>   http://rd.springer.com/chapter/10.1007%2F3-540-48294-6_12
>
> Mark
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130806/844869f2/attachment.html>