Chad Rosier

2013-Aug-06 14:46 UTC

### [LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation

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? Chad -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130806/68c360f0/attachment.html>

David Tweed

2013-Aug-06 15:03 UTC

### [LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation

Hi, I imagine this optimization is for FP math stuff that doesn't involve functions which might set errno (or when we've specified we don't care about that)? Cheers, Dave From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Chad Rosier Sent: 06 August 2013 15:46 To: llvmdev Subject: [LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation 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? Chad -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130806/a32d1486/attachment.html>

Mark Lacey

2013-Aug-06 17:42 UTC

### [LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation

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

Chad Rosier

2013-Aug-06 18:05 UTC

### [LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation

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>

### Reasonably Related Threads

- [LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation
- [LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation
- [LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation
- [LLVMdev] Potential SimplifyCFG optimization; hammock to diamond transformation
- [LLVMdev] Convert fdiv - X/Y -> X*1/Y