This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Deduce dereferenceable based on accessed bytes map
ClosedPublic

Authored by uenoku on Nov 26 2019, 5:25 AM.

Details

Summary

This patch introduces the deduction based on load/store instructions whose pointer operand is a non-inbounds GEP instruction.
For example if we have,

void f(int *u){
 u[0] = 0;
 u[1] = 1;
 u[2] = 2;
}

then u must be dereferenceable(12).

This patch is inspired by D64258

Diff Detail

Event Timeline

uenoku created this revision.Nov 26 2019, 5:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 26 2019, 5:25 AM

Please rebase/update with additional tests after:
rG2bd252ea8941

And what is the plan for enabling Attributor by default? Are there any known bugs?

And I think Attributor needs to run before InstCombine and after InstCombine too. InstCombine infers a lot of derefereceable attrs for libcalls but there is no pass to propagate info futher into function signature, etc.

There's also a question about whether this proposed Attributor functionality obsoletes:
D37579

lebedev.ri added a subscriber: lebedev.ri.EditedNov 26 2019, 6:38 AM

There's also a question about whether this proposed Attributor functionality obsoletes:
D37579

Not in it's present state, no.
There's an upcoming RFC from @jdoerfert that will be aiming to improve that problem.

After reading though the tests it looks to me like this works just fine. I still didn't quite understand why there is a std::max. Could you elaborate on that?


There's also a question about whether this proposed Attributor functionality obsoletes:
D37579

Not in it's present state, no.

Correct, I answered in the thread now as wellh.

There's an upcoming RFC from @jdoerfert that will be aiming to improve that problem.

No pressure, ...

And I think Attributor needs to run before InstCombine and after InstCombine too. InstCombine infers a lot of derefereceable attrs for libcalls but there is no pass to propagate info futher into function signature, etc.

It needs to be (also) a CG-SCC pass. Working on that part right now.

Please rebase/update with additional tests after: rG2bd252ea8941

Yes. We have to figure out the test situation though. I think we need to copy all test used by the Attributor into a dedicted forlder. @uenoku @sstefan1 if one of you wants to start doing that, please let me know :)

And what is the plan for enabling Attributor by default? Are there any known bugs?

Not at the time of the Dev meeting. The roadmap I made up right now:

  • Make it an CG-SCC pass and run it in the inliner loop.
  • Introduce a switch that determines what values we initially look at (the seeding phase) to limit compile time (which was not bad!).
  • Redo my testing and fixing of new/exposed bugs.
  • Send and RFC telling people to please run their tests with the Attributor.
  • Enable it by default

Help with any of the steps is always appreciated, the first one I think I've got though.

llvm/include/llvm/Transforms/IPO/Attributor.h
1829

Could we do uint64_t?

1842

This confuses me. Do we handle "holes" correctly? Do we have a test for holes?

I mean

int *A = ...
A[ 0] = 2
A[10] = 1

should not result in deref(40) if the geps are not inbounds.

1885

Why std::max? I thought the map holds <offset, size> entries.

llvm/test/Transforms/FunctionAttrs/align.ll
372

This is due to the special case with offset 0, correct? If so, commit that special case and these test changes on their own. LGTM on that part.

llvm/test/Transforms/InferFunctionAttrs/dereferenceable.ll
222

Here do the "hole" test start. I see.

uenoku marked 5 inline comments as done.Nov 26 2019, 11:27 PM

Yes. We have to figure out the test situation though. I think we need to copy all test used by the Attributor into a dedicted forlder. @uenoku @sstefan1 if one of you wants to start doing that, please let me know :)

I can work on this. You mean that copy all test in Transforms/FunctionAttrs/, Transforms/InferFunctionAttrs/ to some directory(something like Transforms/Attributor, right? What about ArgumentPromotion or something like that?

llvm/include/llvm/Transforms/IPO/Attributor.h
1842
int f(int *A){
   *A = 0;
   *(A+2) = 2;
   *(A+1) = 1;
   *(A+10) = 10;
}

In that case, AccessedBytesMap is {0:4, 4:4, 8:4, 40:4}. AccessedBytesMap is std::map so it is iterated in accending order on key(Offset).
So KnownBytes will be updated like this:

AccessKnownBytes
(0, 4)0 -> 4
(4, 4)4 -> 8
(8, 4)8 -> 12
(40, 4)12 (break)
1885

I want to handle these cases:

void f(int *A){
  double *B = (double*)A; 
  *B = 0.0;
  *A = 0;
}
void g(int *A){
  double *B = (double*)A; 
  *A = 0;
  *B = 0.0;
}
llvm/test/Transforms/FunctionAttrs/align.ll
372

Yes. I'll commit separately.

jdoerfert accepted this revision.EditedNov 26 2019, 11:32 PM

LGTM with two requests inlined.

Yes. We have to figure out the test situation though. I think we need to copy all test used by the Attributor into a dedicted forlder. @uenoku @sstefan1 if one of you wants to start doing that, please let me know :)

I can work on this. You mean that copy all test in Transforms/FunctionAttrs/, Transforms/InferFunctionAttrs/ to some directory(something like Transforms/Attributor, right? What about ArgumentPromotion or something like that?

Yes, that is what I mean. Start with the ones that run the Attributor right now, or which should run the Attributor right now.

llvm/include/llvm/Transforms/IPO/Attributor.h
1842

This was too smart for me. Can you put this example as a comment into or above computeKnownDerefBytesFromAccessedMap please? I know I'll forget it again.

1885

Makes sense! I think I was just tired and didn't read the code properly. Can you add this as a test case?

This revision is now accepted and ready to land.Nov 26 2019, 11:32 PM
uenoku marked 2 inline comments as done.Nov 26 2019, 11:47 PM
uenoku added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
1829

<int64_t, uint64_t> is fine but <uint64_t, uint64_t> is not good considering minus offset.

1885

OK, I'll add it.

uenoku updated this revision to Diff 231263.Nov 27 2019, 8:08 AM

Rebase and address comments.

uenoku marked an inline comment as done.Nov 27 2019, 8:51 AM
uenoku added inline comments.
llvm/test/Transforms/InferFunctionAttrs/dereferenceable.ll
260

It will be fixed in D70789

uenoku updated this revision to Diff 231287.Nov 27 2019, 9:36 AM

Add test

This revision was automatically updated to reflect the committed changes.