[LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation

[Mark Lacey]

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