[Attributor] AAReachability : use isPotentiallyReachable in isKnownReachable

[okura]

Summary

isKnownReachable had only interface (always returns true).
Changed it to call isPotentiallyReachable.
This change enables deductions of other Abstract Attributes depending on AAReachability to use reachability information obtained from CFG, and it can make them stronger.

[okura]

add and modify tests

[uenoku]

Thank you for working on this! Please add isKnownReachable change.

[jdoerfert]

llvm/test/Transforms/Attributor/noalias.ll

424 ↗

(On Diff #250462)

I love how this all comes together ;)

[okura]

I'm sorry for my mistake. I uploaded two disjoint patches separately.
I added all of the changes.

[uenoku]

Please upload full context of the diff (diff -U999999)

[okura]

I'm sorry. added full context diff.

[jdoerfert]

In D76210#1923884, @okura wrote:

I'm sorry. added full context diff.

No worries. I still have the feeling something is missing in this diff. Make sure to squash the commits locally or diff against the proper baseline.

[uenoku]

void use(int *);
__attribute__((noinline)) static void f1(int * restrict p, int c1, int c2) {
  if (c1) {
    use(p);
  }
  if (!c2) {
    use(p);
  }
}
void f2(int * restrict p, int c) { f1(p, c, c); }

Could you add this example to test?
In this case, c1 and c2 are always same. Because of flow sensitivity, the first callsite is not reachable to the second callsite. So %p is noalias at both callsites. It can't be deduced with isPotentiallyReachable so please add FIXME tag.

[okura]

I added a suggested test.
I squashed all commits to one commit and got diff by git diff -U999999 HEAD^ (including commit for a new test)

[okura]

In D76210#1923892, @jdoerfert wrote:

In D76210#1923884, @okura wrote:

I'm sorry. added full context diff.

No worries. I still have the feeling something is missing in this diff. Make sure to squash the commits locally or diff against the proper baseline.

I squashed 2 commits and got diff. But that makes no difference from the previous diff. Therefore the latest diff may be still inappropriate. If so, please notify me.

[okura]

In D76210#1923914, @uenoku wrote:

void use(int *);
__attribute__((noinline)) static void f1(int * restrict p, int c1, int c2) {
  if (c1) {
    use(p);
  }
  if (!c2) {
    use(p);
  }
}
void f2(int * restrict p, int c) { f1(p, c, c); }

Could you add this example to test?
In this case, c1 and c2 are always same. Because of flow sensitivity, the first callsite is not reachable to the second callsite. So %p is noalias at both callsites. It can't be deduced with isPotentiallyReachable so please add FIXME tag.

This makes sense to me, thank you for your suggestion. I added a slightly different test.
If function use does not make any alias of p (such as only_store in test), noalias can be deduced with the current implementation. But if we impose any constraints on use, noalias should not be deduced.
Therefore, I add a test corresponding to the following C program.

__attribute__((noinline)) static void test16_sub(int * restrict p, int c1, int c2) {
  if (c1) {
    only_store(p);
    make_alias(p);
  }
  if (!c2) {
    only_store(p);
  }
}
void test16_caller(int * restrict p, int c) {
  test16_sub(p, c, c);
}

Like as your test, %p is noalias at both calllsites of only_store. But it is currently not deduced for the second callsite.

[uenoku]

llvm/test/Transforms/Attributor/noalias.ll

410 ↗

(On Diff #250536)

Please add CHECK-LABEL to function definitions just for testing purposes.

[jdoerfert]

There are two issues with a isPotentiallyReachable approach, not to say we cannot make it work. What we need is 1) use liveness information from AAIsDead 2) caching of the results. We can do that in follow up patches though.

[okura]

llvm/test/Transforms/Attributor/noalias.ll

410 ↗

(On Diff #250536)

Do I have to add CHECK-LABEL to all function definitions?

[okura]

In D76210#1929521, @jdoerfert wrote:

There are two issues with a isPotentiallyReachable approach, not to say we cannot make it work. What we need is 1) use liveness information from AAIsDead 2) caching of the results. We can do that in follow up patches though.

I understand the issues. I will try to settle them.

[uenoku]

llvm/test/Transforms/Attributor/noalias.ll

410 ↗

(On Diff #250536)

No, only to functions with tests.

[okura]

add some CHECK-LABEL directive

[jdoerfert]

I think we should merge this and work on the issues in a follow up. LGTM.

[jdoerfert]

Can you please rebase this, doesn't apply cleanly anymore. Sorry for the wait. @uenoku @sstefan1 you can also commit Attributor patches for other people ;)

[jdoerfert]

Nevermind, I merged it.

[jroelofs]

llvm/test/Transforms/Attributor/noalias.ll

460 ↗

(On Diff #255090)

@okura @jdoerfert This diff added some checks with missing FileCheck colons, which silently hide the fact that these checks don't match the tool output.

Mind taking a look at this fixup patch? https://gist.github.com/jroelofs/f03ae725c6b9a5c80f9f187b80642f79

[okura]

llvm/test/Transforms/Attributor/noalias.ll

460 ↗

(On Diff #255090)

That is my terrible mistake. I am sorry and thank you for the patch.
I confirmed it passes the test and It looks good to me.

[jroelofs]

llvm/test/Transforms/Attributor/noalias.ll

460 ↗

(On Diff #255090)

no worries, thanks for having a look!

6c9d52885deaddebe7c228392be20948f413a22f

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

 
 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/CallSite.h"
struct AAReachability : public StateWrapper<BooleanState, AbstractAttribute>,
                         public IRPosition {
   AAReachability(const IRPosition &IRP) : IRPosition(IRP) {}
 
   /// Returns true if 'From' instruction is assumed to reach, 'To' instruction.
   /// Users should provide two positions they are interested in, and the class
   /// determines (and caches) reachability.
   bool isAssumedReachable(const Instruction *From,
                           const Instruction *To) const {
-    return true;
+    return isPotentiallyReachable(From,To);
   }
 
   /// Returns true if 'From' instruction is known to reach, 'To' instruction.
   /// Users should provide two positions they are interested in, and the class
   /// determines (and caches) reachability.
   bool isKnownReachable(const Instruction *From, const Instruction *To) const {
-    return true;
+    return isPotentiallyReachable(From,To);
   }
 
   /// Return an IR position, see struct IRPosition.
   const IRPosition &getIRPosition() const override { return *this; }
 
   /// Create an abstract attribute view for the position \p IRP.
   static AAReachability &createForPosition(const IRPosition &IRP,
                                            Attributor &A);