This is an archive of the discontinued LLVM Phabricator instance.

[Attributor][WIP] allow multiple branches in followUsesInMBEC
Needs ReviewPublic

Authored by okura on Jul 14 2020, 4:39 AM.

Details

Summary

This is the next patch of D65593 and D75923.
This patch makes it possible to propagate known state properly even when there are multiple branches.
To do that, this computes state for each context instruction (program point) from states of other program points, and repeat it until a fixpoint is reached.

Diff Detail

Event Timeline

okura created this revision.Jul 14 2020, 4:39 AM
Herald added a reviewer: uenoku. · View Herald Transcript
Herald added a reviewer: homerdin. · View Herald Transcript
Herald added a reviewer: baziotis. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
fhahn added a subscriber: fhahn.Jul 14 2020, 4:56 AM
okura updated this revision to Diff 277875.Jul 14 2020, 9:36 AM
  • fix variable name conflict
  • add document

We need tests for this, I actually expected existing tests to catch the improvement, is that not the case?

llvm/lib/Transforms/IPO/AttributorAttributes.cpp
610

I doubt you want to indicateOptimisticFixpoint() here. The initial (=optimistic) state should be what you want. Indicating a fixpoint and continuing to update the state is not a good idea (= might not work).

Use a proper type not auto above and maybe rename Iter to either It or StateMapIt to be more consistent (I think) with the rest.

okura updated this revision to Diff 279036.Jul 18 2020, 4:41 PM

add changes in existing tests.

jdoerfert added inline comments.Jul 18 2020, 6:25 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
684

Let's include this as part of the patch right away.

llvm/test/Transforms/Attributor/dereferenceable-1.ll
790–791

Remove the fixme ;)

llvm/test/Transforms/Attributor/misc.ll
35 ↗(On Diff #279036)

We didn't derive this because we "didn't want to". There is some logic to avoid explicitly deriving information for the arguments of calls to declarations. I have to think about this.

llvm/test/Transforms/Attributor/noalias.ll
701 ↗(On Diff #279036)

I looks like we lost the align on

; IS__TUNIT_NPM-NEXT:    tail call void @make_alias(i32* nofree writeonly [[P]])

That is odd.

okura updated this revision to Diff 279441.Jul 21 2020, 1:11 AM
  • fix whole logic
  • add documents
okura added a comment.Jul 21 2020, 4:55 AM

I tried to handle the case that we have to initialize states optimistically again and again, but I got stuck.
I probably don't understand the way you expect.
Could you explain how we should update the states in the following specific case?

void foo(int a, int b, int c, int *ptr) {
  if (a) {
    if (b)
      *ptr = 1;
    else
      *ptr = 2;
  } else {
    if (c)
      *ptr = 3;
    else
      foo(1, 1, 1, ptr);
  }
}

I'm confused. What AA are your thinking about? Let's walk through an example with a specific AA.

okura added a comment.Jul 23 2020, 6:14 AM

Sorry for the confusion. I'm thinking about AADereferenceable.
The test above exist in dereferenceable-1.ll as @rec-branch-2.
The method I used in this patch does not currently handle that case (i.e., cannot deduce dereferenceable(4) for argument %ptr).
I think you expect dereferenceable(4) to be propagated to Known state for argument %ptr at the time after initialize (and followUsesInMBEC) is called.
I don't and want to know how to do (for this or follow up patch).

okura updated this revision to Diff 280092.Jul 23 2020, 6:40 AM
  • fix some trivial mistakes
okura updated this revision to Diff 280094.Jul 23 2020, 6:43 AM

Sorry for the confusion. I'm thinking about AADereferenceable.
The test above exist in dereferenceable-1.ll as @rec-branch-2.
The method I used in this patch does not currently handle that case (i.e., cannot deduce dereferenceable(4) for argument %ptr).
I think you expect dereferenceable(4) to be propagated to Known state for argument %ptr at the time after initialize (and followUsesInMBEC) is called.
I don't and want to know how to do (for this or follow up patch).

I see. Let's do it in a follow up. It is not clear to me how that would look as we would basically need to do fixpoint iteration and not simply exploration of known facts. It would need to happen in the update, etc.

Are the attached test changes all that occur?

okura updated this revision to Diff 280716.Jul 26 2020, 4:32 AM
  • change fixpoint iteration to path exploration
okura added a comment.Jul 26 2020, 4:48 AM

Sorry for the confusion. I'm thinking about AADereferenceable.
The test above exist in dereferenceable-1.ll as @rec-branch-2.
The method I used in this patch does not currently handle that case (i.e., cannot deduce dereferenceable(4) for argument %ptr).
I think you expect dereferenceable(4) to be propagated to Known state for argument %ptr at the time after initialize (and followUsesInMBEC) is called.
I don't and want to know how to do (for this or follow up patch).

It is not clear to me how that would look as we would basically need to do fixpoint iteration and not simply exploration of known facts. It would need to happen in the update, etc.

On second thoughts, I think we don't necessarily have to do fixpoint iteration for this task. So I changed the fixpoint iteration to path exploration.

Are the attached test changes all that occur?

Yes. I will add some new tests to reinforce that the path exploration works fine.