Hi,
Is there anyway I can coerce LLVM into performing the following
transformation?
%1 = icmp eq i32 %flag, 1
%2 = select i1 %1, %foo* %data, %struct.cell_t* null
%3 = icmp eq %foo* %2, null
br i1 %3, label %failure, label %success
Into:
%1 = icmp eq i32 %flag, 1
br i1 %1, label %success, label %failure
With %data substituted for %2 in %success and its successors, and null
for %2 in %failure. The way that code generation deals with the select
means that this is actually making a small but noticeable difference to
performance due to the number of branches involved.
As way of justification, the code in question essentially comes from a C
function similar to:
foo *check_for_data() {
if(flag == FULL) {
return data;
} else {
return NULL;
}
}
which is called by code that branches on whether the result is NULL.
After inlining and other optimisation passes I'm getting code like that
above.
Best,
Pete
On 5 February 2014 04:37, Pete Calvert <prc33 at cam.ac.uk> wrote:> Hi, > > Is there anyway I can coerce LLVM into performing the following > transformation? > > %1 = icmp eq i32 %flag, 1 > %2 = select i1 %1, %foo* %data, %struct.cell_t* null > %3 = icmp eq %foo* %2, null > br i1 %3, label %failure, label %success > > Into: > > %1 = icmp eq i32 %flag, 1 > br i1 %1, label %success, label %failure > > With %data substituted for %2 in %success and its successors, and null for > %2 in %failure. The way that code generation deals with the select means > that this is actually making a small but noticeable difference to > performance due to the number of branches involved. >I think the first step in optimization here is to be able to convert: %1 = icmp eq i32 %flag, 1 %2 = select i1 %1, %foo* %data, %struct.cell_t* null %3 = icmp eq %foo* %2, null br i1 %3, label %failure, label %success to %1 = icmp eq i32 %flag, 1 %2 = select i1 %1, %foo* %data, %struct.cell_t* null %3 = icmp eq i32 %flag, 1 br i1 %3, label %failure, label %success This would then permit instruction %2 to move down past the br. This could also be achieved, in the short term, by changing your source code to base the if after return on "flag" instead of the returned value being NULL.
But what happens if %data is null? Can LLVM prove that it isn't? On Wed, Feb 5, 2014 at 7:12 PM, James Courtier-Dutton < james.dutton at gmail.com> wrote:> On 5 February 2014 04:37, Pete Calvert <prc33 at cam.ac.uk> wrote: > > Hi, > > > > Is there anyway I can coerce LLVM into performing the following > > transformation? > > > > %1 = icmp eq i32 %flag, 1 > > %2 = select i1 %1, %foo* %data, %struct.cell_t* null > > %3 = icmp eq %foo* %2, null > > br i1 %3, label %failure, label %success > > > > Into: > > > > %1 = icmp eq i32 %flag, 1 > > br i1 %1, label %success, label %failure > > > > With %data substituted for %2 in %success and its successors, and null > for > > %2 in %failure. The way that code generation deals with the select means > > that this is actually making a small but noticeable difference to > > performance due to the number of branches involved. > > > > I think the first step in optimization here is to be able to convert: > %1 = icmp eq i32 %flag, 1 > %2 = select i1 %1, %foo* %data, %struct.cell_t* null > %3 = icmp eq %foo* %2, null > br i1 %3, label %failure, label %success > > to > %1 = icmp eq i32 %flag, 1 > %2 = select i1 %1, %foo* %data, %struct.cell_t* null > %3 = icmp eq i32 %flag, 1 > br i1 %3, label %failure, label %success > > This would then permit instruction %2 to move down past the br. > This could also be achieved, in the short term, by changing your > source code to base the if after return on "flag" instead of the > returned value being NULL. > _______________________________________________ > 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/20140205/c620105a/attachment.html>
On 4 February 2014 23:37, Pete Calvert <prc33 at cam.ac.uk> wrote:> Hi, > > Is there anyway I can coerce LLVM into performing the following > transformation? > > %1 = icmp eq i32 %flag, 1 > %2 = select i1 %1, %foo* %data, %struct.cell_t* null > %3 = icmp eq %foo* %2, null > br i1 %3, label %failure, label %success >It seems something that GVN should be able to handle if expressed with branches instead of select. Unfortunately it currently doesn't :-( It is a long project, but one way to fix this might be to extend (rewrite?) GVN PRE (pr13307, pr10254) and then make GVN handle selects too (on way to fix pr13590 and hopefully your example). Cheers, Rafael
On 2014-02-05 23:32, Rafael Espíndola wrote:> On 4 February 2014 23:37, Pete Calvert <prc33 at cam.ac.uk> wrote: >> Hi, >> >> Is there anyway I can coerce LLVM into performing the following >> transformation? >> >> %1 = icmp eq i32 %flag, 1 >> %2 = select i1 %1, %foo* %data, %foo* null >> %3 = icmp eq %foo* %2, null >> br i1 %3, label %failure, label %success >> > > It seems something that GVN should be able to handle if expressed with > branches instead of select. Unfortunately it currently doesn't :-( > > It is a long project, but one way to fix this might be to extend > (rewrite?) GVN PRE (pr13307, pr10254) and then make GVN handle selects > too (on way to fix pr13590 and hopefully your example).I'm not at all familiar with the LLVM internals (just with the Ocaml bindings for generating IR), but could try and help out with this if there was agreement on how it needs doing / someone gave me a pointer in the right direction. I guess this case is the most tricky of the ones you listed since it relies on knowledge that %data is not null. I've filed this as a bug (#18754). Pete