llvm dev - Aug 2013 - [LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation

Message: 6
Date: Tue, 6 Aug 2013 10:46:19 -0400
From: Chad Rosier <chad.rosier at gmail.com<mailto:chad.rosier at
gmail.com>>
To: llvmdev <llvmdev at cs.uiuc.edu<mailto:llvmdev at cs.uiuc.edu>>
Subject: [LLVMdev] Potential SimplifyCFG optimization; hammock to
diamond transformation
Message-ID:
<CAMo3wbR6x1wBzb17=GrkERV7kvzx2RdpuheFzyxkQEs3BBvKaw at
mail.gmail.com<mailto:CAMo3wbR6x1wBzb17=GrkERV7kvzx2RdpuheFzyxkQEs3BBvKaw at
mail.gmail.com>>
Content-Type: text/plain; charset="iso-8859-1"

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:

I believe what you're proposing would be accomplished by PRE, since the
stores to a, b and c are partially redundant, and once those are
"placed" by PRE, the FP math would then get placed as you want as
well.


{
 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?

SSAPRE existed in LLVM but has been removed.  PRE is one of those optimizations
that are simply more efficient and also sometimes more effective as a bitvector
dataflow optimization than as an SSA algorithm.


 If not, would the SimplifyCFG pass be
an appropriate home for such an optimization?

If done there, it is likely to only handle special cases like the above.  My
guess is that it is better done as a code motion pass than a SimplifyCFG
extension.



Chad


--Vikram Adve
Professor, Department of Computer Science
University of Illinois at Urbana-Champaign
vadve at illinois.edu<mailto:vadve at illinois.edu>
http://llvm.org

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130806/cae5ffcd/attachment.html>

On Tue, Aug 6, 2013 at 1:42 PM, Adve, Vikram Sadanand <vadve at
illinois.edu>wrote:
>  Message: 6
> Date: Tue, 6 Aug 2013 10:46:19 -0400
> From: Chad Rosier <chad.rosier at gmail.com>
> To: llvmdev <llvmdev at cs.uiuc.edu>
>
> Subject: [LLVMdev] Potential SimplifyCFG optimization; hammock to
> diamond transformation
> Message-ID:
> <CAMo3wbR6x1wBzb17=GrkERV7kvzx2RdpuheFzyxkQEs3BBvKaw at
mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
>
>
> 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:
>
>
>  I believe what you're proposing would be accomplished by PRE, since
the
> stores to a, b and c are partially redundant, and once those are
"placed"
> by PRE, the FP math would then get placed as you want as well.
>

Yes, that makes perfect sense.

>
> {
>  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?
>
>
>  SSAPRE existed in LLVM but has been removed.  PRE is one of those
> optimizations that are simply more efficient and also sometimes more
> effective as a bitvector dataflow optimization than as an SSA algorithm.
>
Good to know.

>
>  If not, would the SimplifyCFG pass be
> an appropriate home for such an optimization?
>
>
>  If done there, it is likely to only handle special cases like the above.
>  My guess is that it is better done as a code motion pass than a
> SimplifyCFG extension.
>
Thanks for the feedback, Prof. Vikram.  You have been very helpful.

Chad
>
>
>
>      --Vikram Adve
> Professor, Department of Computer Science
> University of Illinois at Urbana-Champaign
> vadve at illinois.edu
> http://llvm.org
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130806/7c61472e/attachment.html>