Potential SimplifyCFG optimization; hammock to diamond transformation

Message: 6
Date: Tue, 6 Aug 2013 10:46:19 -0400
From: Chad Rosier <chad.rosier@gmail.com>
To: llvmdev <llvmdev@cs.uiuc.edu>
Subject: [LLVMdev] Potential SimplifyCFG optimization; hammock to
diamond transformation
Message-ID:
<CAMo3wbR6x1wBzb17=GrkERV7kvzx2RdpuheFzyxkQEs3BBvKaw@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@illinois.edu
http://llvm.org

Message: 6
Date: Tue, 6 Aug 2013 10:46:19 -0400
From: Chad Rosier <chad.rosier@gmail.com>
To: llvmdev <llvmdev@cs.uiuc.edu>

Subject: [LLVMdev] Potential SimplifyCFG optimization; hammock to
diamond transformation

Message-ID:
<CAMo3wbR6x1wBzb17=GrkERV7kvzx2RdpuheFzyxkQEs3BBvKaw@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.