This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Remove trivially empty lifetime start/end ranges.
ClosedPublic

Authored by aadg on Sep 30 2015, 12:54 PM.

Details

Summary

Some passes may open up opportunities for optimizations, leaving empty
lifetime start/end ranges. For example, with the following code:

void foo(char *, char *);
void bar(int Size, bool flag) {
  for (int i = 0; i < Size; ++i) {
    char text[1];
    char buff[1];
    if (flag)
      foo(text, buff); // BBFoo
  }
}

the loop unswitch pass will create 2 versions of the loop, one with
flag==true, and the other one with flag==false, but always leaving
the BBFoo basic block, with lifetime ranges covering the scope of the for
loop. Simplify CFG will then remove BBFoo in the case where flag==false,
but will leave the lifetime markers.

This patch teaches InstCombine to remove trivially empty lifetime marker
ranges, that is ranges ending right after they were started (ignoring
debug info in the range).

This fixes PR24598: excessive compile time after r234581.

Diff Detail

Event Timeline

aadg updated this revision to Diff 36141.Sep 30 2015, 12:54 PM
aadg retitled this revision from to [InstCombine] Remove trivially empty lifetime start/end ranges..
aadg updated this object.
aadg added a reviewer: reames.
aadg added a subscriber: llvm-commits.

LGTM otherwise

test/Transforms/InstCombine/lifetime.ll
2

It is probably better to just check the 6 occurrences with a single RUN command.

chandlerc accepted this revision.Sep 30 2015, 9:37 PM
chandlerc added a reviewer: chandlerc.
chandlerc added a subscriber: chandlerc.

LGTM with the fixes suggested inline.

I wonder if we should do something more aggressive to kill pointless lifetime ranges though. This handles the trivial case but non-trivial cases might be very interesting.

For example, even non-strictly-nested ranges won't be caught by this.

lib/Transforms/InstCombine/InstCombineCalls.cpp
1398

These should be loop variables.

test/Transforms/InstCombine/lifetime.ll
2

This already is checked by the FileCheck line. I think this can just be deleted.

This revision is now accepted and ready to land.Sep 30 2015, 9:37 PM
aadg added a comment.Oct 1 2015, 1:24 AM

I intended to catch another trivially empty ranges in a follow-up patch: the non strictly nested ones you refer to. The goal was to quickly fix an issue (PR24598), then improve the lifetime markers cleanup.

I think we should teach this cleanup to address less trivial cases, especially the one where the start dominates the end (garanteed by design) and the end post-dominate the start and the alloca is not used in between. I think this would catch lots of cases. But that's for another patch.

And the loop unroller probably needs to learn how not to mess to badly with the lifetime markers :).

Thanks for the reviews !

I'll fix and push this patch.

lib/Transforms/InstCombine/InstCombineCalls.cpp
1398

I agree on the principle, but BI needs to be incremented before entering the loop.

test/Transforms/InstCombine/lifetime.ll
2

Those 2 RUN lines were a very clumsy way of making sure the "if" basic block has been emptied, and the "else" was not modified. One RUN line is enough indeed, and I will add 2 checks:

CHECK: if:
CHECK-NEXT: br label %fin
This revision was automatically updated to reflect the committed changes.