This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Deduce "returned" argument attribute
ClosedPublic

Authored by jdoerfert on Mar 28 2019, 12:04 AM.

Details

Summary

Deduce the "returned" argument attribute by collecting all potentially
returned values.

Note: Not only the unique return value, if any, can be used by
subsequent attributes but also the set of all potentially returned
values as well as the mapping from returned values to return
instructions that they originate from.

Change in statistics (-stats) for LLVM-TS + Spec2006, totaling ~19% more "returned" arguments.

  ADDED: attributor                   NumAttributesManifested                  n/a ->        637
  ADDED: attributor                   NumAttributesValidFixpoint               n/a ->      25545
  ADDED: attributor                   NumFnArgumentReturned                    n/a ->        637
  ADDED: attributor                   NumFnKnownReturns                        n/a ->      25545
  ADDED: attributor                   NumFnUniqueReturned                      n/a ->      14118
CHANGED: deadargelim                  NumRetValsEliminated                     470 ->        449 (    -4.468%)
REMOVED: functionattrs                NumReturned                              535 ->        n/a
CHANGED: indvars                      NumElimIdentity                          138 ->        164 (   +18.841%)

Event Timeline

jdoerfert created this revision.Mar 28 2019, 12:04 AM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptMar 28 2019, 12:05 AM
jdoerfert updated this revision to Diff 192738.Mar 28 2019, 4:39 PM

Fix the last bug exposed by llvm-test-suite & SPEC2006

jdoerfert updated this revision to Diff 192916.Mar 29 2019, 2:44 PM

Minor updates

xbolva00 added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
384

Maybe enum here ?
So you could call indicateFixpoint(Fixpoint::optimistic) ?

Or maybe even better, indicateOptimisticFixpoint()?

jdoerfert edited the summary of this revision. (Show Details)Apr 1 2019, 8:07 AM
jdoerfert marked an inline comment as done.
jdoerfert added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
384

Good points. I'll probably go with the second, most explicit, solution. I'll update (all) the source files soon.

jdoerfert updated this revision to Diff 193115.Apr 1 2019, 9:54 AM

Minor changes

sanjoy removed a reviewer: sanjoy.Apr 1 2019, 11:05 AM
fhahn added a subscriber: fhahn.Apr 12 2019, 3:14 AM
jdoerfert marked an inline comment as done.Apr 15 2019, 10:05 AM
jdoerfert added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
441

This should probably call llvm_unreachable with a message instead of returning -1.

jdoerfert updated this revision to Diff 199114.May 10 2019, 6:09 PM

Rebase on newest Attributor design

jdoerfert updated this revision to Diff 203741.Jun 9 2019, 8:58 AM

Update to new Attributor design and more tests

jdoerfert marked an inline comment as done.Jun 9 2019, 8:59 AM
jdoerfert edited the summary of this revision. (Show Details)Jun 9 2019, 9:00 AM
jdoerfert updated this revision to Diff 203742.Jun 9 2019, 9:04 AM

Cleanup leftover arguments

CHANGED: build-libcalls NumNoUnwind 4526 -> 3382 ( -25.276%)

Why did the number of nounwinds drop?

llvm/lib/Transforms/IPO/Attributor.cpp
115

Typo in "gerneric", should be "generic".

127

LLVM generally has a preference for not recursing like this, it means that the amount of stack space we need depends on the input IR and it's hard for a user of llvm as a library to foresee or handle an out of stack condition.

Common practice is to structure it as a loop like:

SmallVector<Value *, 32> Worklist;
SmallSet<Value *> Visited;
Worklist.push_back(V);
do {
  Value *V = Worklist.pop_back_val();
  if (!Visited.insert(V).second)
    continue;
  V = V->stripPointerCasts();
  // ...
} while (!Worklist.empty());

Also, consider having some sort of loop iteration limit as a safety value against runaway compile time.

133

Offhand, I think placing this after the CS check is incorrect. I haven't tried it out, but I expect the testcase that triggers infinite loop to look something like this:

define i32 @test(i32 %A) {
entry:
  ret i32 0
unreachableblock:
  %B = call i32 @test(i32 %B)
  ret i32 %B
}

which should pass the verifier and trigger an infinite loop if you call gernericValueTraversal on %B.

Also, if you really need a callback and not just a SmallSet named Visited, I'd suggest calling the callback immediately before adding each value to the Worklist (or as written not, call it on each value before recursing).

jdoerfert marked 2 inline comments as done.Jun 9 2019, 1:22 PM

Thanks for looking at this. I'll update the patch asap

CHANGED: build-libcalls NumNoUnwind 4526 -> 3382 ( -25.276%)

Why did the number of nounwinds drop?

I haven't looked into this but my initial guess would be that we removed code due to the "returned" information for which we then did not add nounwind. To be honest, I don't see how else it should have happened.

llvm/lib/Transforms/IPO/Attributor.cpp
127

Though there is not really stack space needed I see your point. I'll rewrite the recursion.

133

The test cases above passes just fine but again I see your point. I will add that one and the one below which breaks as you predicted. I'll rewrite the whole traversal.

declare i32 @test2(i32 returned %A);
define i32 @test(i32 %A) {
entry:
  ret i32 %A
unreachableblock:
  %B = call i32 @test2(i32 %B)
  ret i32 %B
}
jdoerfert updated this revision to Diff 203818.Jun 10 2019, 7:21 AM

Use worklist instead of recursion, add tests

jdoerfert updated this revision to Diff 203819.Jun 10 2019, 7:22 AM
jdoerfert marked 2 inline comments as done.

Fix Typo

jdoerfert edited the summary of this revision. (Show Details)Jun 10 2019, 12:41 PM

CHANGED: build-libcalls NumNoUnwind 4526 -> 3382 ( -25.276%)

Why did the number of nounwinds drop?

I rerun the experiment with and without this commit. The numbers are the same as before except that there is no difference in NumNoUnwind. I don't know if I used a different baseline or if there was another problem (e.g., concurrency related) but I don't think this patch does affect the NumNoUnwind number at all.

Btw. I only report statistics that changed more than 1% as there seem to be some minimal variations all the time.

Update tests

jdoerfert updated this revision to Diff 204626.Jun 13 2019, 2:26 PM

Simplify the interface

uenoku added a subscriber: uenoku.Jun 20 2019, 6:22 AM
jdoerfert updated this revision to Diff 207924.Jul 3 2019, 4:47 PM

Rebase (tests will be run later today)

ninja check-all passed

jdoerfert marked an inline comment as done.Jul 5 2019, 10:26 AM
hfinkel accepted this revision.Jul 5 2019, 8:29 PM

LGTM

clang/test/CodeGenOpenCL/as_type.cl
3

I recommend leaving the Clang tests along. Clang tests that run the optimizer don't follow out best practices and, while end-to-end testing is valuable, I don't think that we should encourage general optimizer testing here.

This revision is now accepted and ready to land.Jul 5 2019, 8:29 PM
This revision was automatically updated to reflect the committed changes.