This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Deduction based on path exploration
ClosedPublic

Authored by uenoku on Aug 1 2019, 10:37 AM.

Details

Summary

This patch introduces the propagation of known information based on path exploration.
For example,

int u(int c, int *p){
  if(c) {
     return *p;
  } else {
     return *p + 1;
  }
}

An argument p is dereferenced whatever c's value is.

For an instruction CtxI, we accumulate branch instructions in the must-be-executed-context of CtxI and then, we take the conjunction of the successors' known state.

Diff Detail

Event Timeline

uenoku created this revision.Aug 1 2019, 10:37 AM
Herald added a project: Restricted Project. · View Herald Transcript
uenoku updated this revision to Diff 212919.Aug 1 2019, 3:47 PM

Fix typo.

I only reviewed the MustExecute parts as the Attributor part probably needs a rebase. I think this is needed and I'll be more responsive this time.

llvm/include/llvm/Analysis/MustExecute.h
509

Newline before and comment describing this struct and its use briefly.

525

I would not call it Multiplicative/Additive identity, nor Top/Bottom. I would stick to the Attributor spellings of "best/worst state". The others are overloaded too often (IMHO).

543

If you keep pointer values, this is shorter: if (AState *State = MemoizeResult.lookup(PPBegin)) return *State;

566

I think I would prefer that we first explore range completely and only collect branch instructions. If range was not enough to cause stopExplore to trigger, we start exploring branches. The reason is that range information is "better" than child information as it holds without the need to explore a second path. We should also have a parameter to limit the search.

568

Is it wise to store the address of the local object AS here? Maybe we need the map to own the state.

uenoku updated this revision to Diff 246412.Feb 25 2020, 4:29 AM
uenoku retitled this revision from [Attributor][MustExec] Deduce dereferenceable and nonnull attribute by exploring path to [Attributor] Deduction based on path exploration.
uenoku edited the summary of this revision. (Show Details)
uenoku added a reviewer: baziotis.

Rebased. I simply use AbstractState to accumulate the known information.

That's very interesting, I hope I'll have time to come back with a better review.

llvm/lib/Transforms/IPO/Attributor.cpp
1050–1051

This UsesInChild I think is not used anywhere. Probably put there since something has to be passed to the function. Can we do something to avoid inserting to it and deleting in every loop? (If I haven't missed something)

Thanks for resurrecting this patch. This gives us really interesting opportunities as we can already see with the nonnull and deref changes :)
I will need to look over everything, maybe next week (I'm on travel again). A first comment inlined though.

llvm/include/llvm/Analysis/MustExecute.h
473

My first impression is that we might want to shift the burden of collecting instructions to the user and just do the iterating here. The benefit is that we could use the return of Pred to indicate that we want to stop. I think we want to have a way to stop the search of the context if we don't expect to find better results anymore.

uenoku updated this revision to Diff 246645.Feb 26 2020, 1:09 AM

Address comments

uenoku marked 2 inline comments as done.Feb 26 2020, 1:11 AM
uenoku added inline comments.
llvm/include/llvm/Analysis/MustExecute.h
473

Addressed.

llvm/lib/Transforms/IPO/Attributor.cpp
1050–1051

Yes, that's right.

baziotis added inline comments.Feb 26 2020, 1:38 AM
llvm/lib/Transforms/IPO/Attributor.cpp
1050–1051

Thanks for addressing this. I think it still isn't used though right? i.e. With your update, it seems you can just remove UsesInChild declaration completely.

uenoku marked an inline comment as done.Feb 26 2020, 2:21 AM
uenoku added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
1050–1051

Oh, I forgot to remove it ;)

jdoerfert added inline comments.Feb 27 2020, 10:12 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
1342

We need Documentation for this.

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

Can you explain the NOTE further and why we cannot make it "right"?


Do you really want to delete UsesInChild or do you want to use it in the followUsesInContext call such that Uses is not modifed here.

baziotis added inline comments.Feb 27 2020, 10:24 AM
llvm/lib/Transforms/IPO/Attributor.cpp
1062

Do you really want to delete UsesInChild or do you want to use it in the followUsesInContext call such that Uses is not modifed here.

Hmm, that was my initial assumption as well:

Probably put there since something has to be passed to the function

but I thought I was wrong.

uenoku updated this revision to Diff 247161.Feb 27 2020, 6:56 PM
uenoku marked an inline comment as done.

Simplify implementation.

uenoku added inline comments.Feb 27 2020, 6:59 PM
llvm/lib/Transforms/IPO/Attributor.cpp
1062

Can you explain the NOTE further and why we cannot make it "right"?

I didn't have a brain;) I have implemented in a simpler way so NOTE is removed.

Do you really want to delete UsesInChild or do you want to use it in the followUsesInContext call such that Uses is not modifed here.

I want to modify Uses in followUsesInContext so I'm fine with removing UsesInChild.

I have not convinced myself that this covers the recursive case properly, maybe that was never the intend though. Can we have a test like this:

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
      *ptr = 4;
  }
}

and maybe also

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);
  }
}
llvm/lib/Transforms/IPO/Attributor.cpp
1032

I don't get the comment. What are the two indices of ChildState and why is the second ChildState "out-of-sync"?

uenoku updated this revision to Diff 248911.Mar 7 2020, 1:32 AM

Fix comment and add test.

uenoku marked an inline comment as done.Mar 7 2020, 1:36 AM

I have not convinced myself that this covers the recursive case properly, maybe that was never the intend though. Can we have a test like this:

Yes, recursive branches are not handled in this patch to simplify. I'll add on a later patch.

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

It was broken. Sorry for the confusion.

jdoerfert accepted this revision.Mar 8 2020, 2:27 PM

LGTM. We need a recursive lookup that tracks paths up to a given depth next.

This revision is now accepted and ready to land.Mar 8 2020, 2:27 PM
This revision was automatically updated to reflect the committed changes.