question about enabling cfl-aa and collecting a57 numbers

A couple of general comments.

There are two types of alias info : analysis based and assertion based. For analysis based alias analysis, the ordering has a slight impact on compiler time. To make the query faster, it is conceivably better to put the one with the highest chances to give definitive answers (NoAlias, MustAlias, PartialMusAlias) first.

Assertion based alias (TypeAA, restrict etc) is a different animal because we want the opportunity to detect user errors ( give warning or correct it). However unless we expect the MayAlias result from downstream alias to be able to override the NoAlias result from TypeAA, it may be ok to just put TypeAA the last in the pipe, i.e., violations of typeAA have already been caught as Must/Partial Aliases in upstream alias info providers (of course, we won’t be able to warn user in this pipeline).

David

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Chandler Carruth" <chandlerc@google.com>
Cc: "George Burgess IV" <george.burgess.iv@gmail.com>, "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>,
"Jiangning Liu" <Jiangning.Liu@arm.com>
Sent: Friday, January 16, 2015 3:35:18 PM
Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

As we chatted about offline, i think we all agree this ordering is
completely and utterly broken
(right now it's BasicAA,ScopedAA, TBAA, CFLAA), and that BasicAA
should really be going last.
But this is also currently deliberate to "support type punning".[1]

But i'm not in for fixing that right now, and it doesn't change that
CFLAA was not delegating properly, and doesn't change how to fix
this CFLAA bug :slight_smile:

Patch updated to revert ordering changes and attached

[1] I know you have some ideas on how to fix this, but actually, I
wonder if it wouldn't be better to move deliberate type punning into
it's own AliasAnalysis, where the behavior will be both obvious and
hopefully written well. Then we can just run that at the top of the
stack. Certainly, your way was easier :slight_smile:

Wouldn't such a pass look a lot like BasicAA, perhaps minus the PHI-speculation bits? I worry that, once SROA, etc. get their hands on strucure accesses, structure-element type punning looks a lot like the general case that BasicAA currently handles.

-Hal

Hi Danny,

   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
   // BasicAliasAnalysis wins if they disagree. This is intended to help
   // support "obvious" type-punning idioms.
- if (UseCFLAA)
- addPass(createCFLAliasAnalysisPass());
   addPass(createTypeBasedAliasAnalysisPass());
   addPass(createScopedNoAliasAAPass());
+ if (UseCFLAA)
+ addPass(createCFLAliasAnalysisPass());
   addPass(createBasicAliasAnalysisPass());

Do we really want to change the order here? I had originally placed it after the metadata-based passes thinking that the compile-time would be better (guessing that the metadata queries would be faster than the CFL queries, so if the metadata could quickly return a NoAlias, then we'd cut out unecessary CFL queries). Perhaps this is an irrelevant effect, but we should have some documented rationale.

; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
-define i8 @test0(i8* %base, i1 %x) {
+define i8 @test0(i1 %x) {
entry:
+ %base = alloca i8, align 4
   %baseplusone = getelementptr i8* %base, i64 1
   br i1 %x, label %red, label %green
red:
@@ -25,8 +26,9 @@ green:
}

why should this return PartialAlias? %ohi does partially overlap, so this correct, but what happens when the overlap is partial or control dependent? I thought you had concluded that CFL should return only NoAlias or MayAlias?

Thanks again,
Hal

From: "Hal Finkel" <hfinkel@anl.gov>
To: "Daniel Berlin" <dberlin@dberlin.org>
Cc: "Jiangning Liu" <Jiangning.Liu@arm.com>, "George Burgess IV" <george.burgess.iv@gmail.com>, "LLVM Developers
Mailing List" <llvmdev@cs.uiuc.edu>
Sent: Saturday, January 17, 2015 2:03:18 AM
Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

Hi Danny,

   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
   // BasicAliasAnalysis wins if they disagree. This is intended to
   help
   // support "obvious" type-punning idioms.
- if (UseCFLAA)
- addPass(createCFLAliasAnalysisPass());
   addPass(createTypeBasedAliasAnalysisPass());
   addPass(createScopedNoAliasAAPass());
+ if (UseCFLAA)
+ addPass(createCFLAliasAnalysisPass());
   addPass(createBasicAliasAnalysisPass());

Do we really want to change the order here? I had originally placed
it after the metadata-based passes thinking that the compile-time
would be better (guessing that the metadata queries would be faster
than the CFL queries, so if the metadata could quickly return a
NoAlias, then we'd cut out unecessary CFL queries). Perhaps this is
an irrelevant effect, but we should have some documented rationale.

Please ignore the above question; I had forgotten that you had posted a newer version of the patch without the ordering change. Only the question below matters...

Thanks again,
Hal

Hi Danny,

// Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
// BasicAliasAnalysis wins if they disagree. This is intended to help
// support “obvious” type-punning idioms.

  • if (UseCFLAA)
  • addPass(createCFLAliasAnalysisPass());
    addPass(createTypeBasedAliasAnalysisPass());
    addPass(createScopedNoAliasAAPass());
  • if (UseCFLAA)
  • addPass(createCFLAliasAnalysisPass());
    addPass(createBasicAliasAnalysisPass());

Do we really want to change the order here? I had originally placed it after the metadata-based passes thinking that the compile-time would be better (guessing that the metadata queries would be faster than the CFL queries, so if the metadata could quickly return a NoAlias, then we’d cut out unecessary CFL queries). Perhaps this is an irrelevant effect, but we should have some documented rationale.

Yeah, this was a mistake (Chandler had suggested it was right earlier, but we were both wrong :P)

; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
-define i8 @test0(i8* %base, i1 %x) {
+define i8 @test0(i1 %x) {
entry:

  • %base = alloca i8, align 4
    %baseplusone = getelementptr i8* %base, i64 1
    br i1 %x, label %red, label %green
    red:
    @@ -25,8 +26,9 @@ green:
    }

why should this return PartialAlias? %ohi does partially overlap, so this correct, but what happens when the overlap is partial or control dependent?

So, after talking with some people offline, they convinced me in SSA form, the name would change in these situations, and the only situations you can get into trouble is with things “based on pointer arguments” (because you have no idea what their initial state is), or “globals” (because they are not in SSA form)
I could not come up with a case otherwise
But i’m welcome to hear if you think this is wrong.

FWIW: I bootstrapped/tested the compiler with an assert that triggered if CFL-AA was going to return PartialAlias and BasicAA would have returned NoAlias, and it did not trigger with this change.

(It would have triggered before this set of changes)

Not proof of course, but it at least tells me it’s not “obviously wrong” :slight_smile:

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Jiangning Liu" <Jiangning.Liu@arm.com>, "George Burgess IV" <george.burgess.iv@gmail.com>, "LLVM Developers
Mailing List" <llvmdev@cs.uiuc.edu>, "Nick Lewycky" <nlewycky@google.com>
Sent: Saturday, January 17, 2015 1:08:10 PM
Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

Hi Danny,

// Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
// BasicAliasAnalysis wins if they disagree. This is intended to help
// support "obvious" type-punning idioms.
- if (UseCFLAA)
- addPass( createCFLAliasAnalysisPass());
addPass( createTypeBasedAliasAnalysisPa ss());
addPass( createScopedNoAliasAAPass());
+ if (UseCFLAA)
+ addPass( createCFLAliasAnalysisPass());
addPass( createBasicAliasAnalysisPass() );

Do we really want to change the order here? I had originally placed
it after the metadata-based passes thinking that the compile-time
would be better (guessing that the metadata queries would be faster
than the CFL queries, so if the metadata could quickly return a
NoAlias, then we'd cut out unecessary CFL queries). Perhaps this is
an irrelevant effect, but we should have some documented rationale.

Yeah, this was a mistake (Chandler had suggested it was right
earlier, but we were both wrong :P)

; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
-define i8 @test0(i8* %base, i1 %x) {
+define i8 @test0(i1 %x) {
entry:
+ %base = alloca i8, align 4
%baseplusone = getelementptr i8* %base, i64 1
br i1 %x, label %red, label %green
red:
@@ -25,8 +26,9 @@ green:
}

why should this return PartialAlias? %ohi does partially overlap, so
this correct, but what happens when the overlap is partial or
control dependent?
So, after talking with some people offline, they convinced me in SSA
form, the name would change in these situations, and the only
situations you can get into trouble is with things "based on pointer
arguments" (because you have no idea what their initial state is),
or "globals" (because they are not in SSA form)
I could not come up with a case otherwise

Okay; that part of the code could really use some more commentary. I'd really appreciate it if you should put these thoughts in written form that could be added as comments.

But i'm welcome to hear if you think this is wrong.

FWIW: I bootstrapped/tested the compiler with an assert that
triggered if CFL-AA was going to return PartialAlias and BasicAA
would have returned NoAlias, and it did not trigger with this
change.

(It would have triggered before this set of changes)

Not proof of course, but it at least tells me it's not "obviously
wrong" :slight_smile:

That's good :slight_smile: -- but, not exactly what I was concerned about. Our general convention has been that PartialAlias is a "strong" result, like MustAlias, but implies that AA has proved that only a partial overlap will occur.

So, in this test case we get the right result:

; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
define i8 @test0(i1 %x) {
entry:
  %base = alloca i8, align 4
  %baseplusone = getelementptr i8* %base, i64 1
  br i1 %x, label %red, label %green
red:
  br label %green
green:
  %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]
  store i8 0, i8* %phi

  %bigbase0 = bitcast i8* %base to i16*
  store i16 -1, i16* %bigbase0

  %loaded = load i8* %phi
  ret i8 %loaded
}

because %phi will have a partial overlap with %bigbase0, the only uncertainty is whether the overlap is with the low byte or the high byte. But if I modify the test to be this:

define i8 @test0x(i1 %x) {
entry:
  %base = alloca i8, align 4
  %baseplustwo = getelementptr i8* %base, i64 2
  br i1 %x, label %red, label %green
red:
  br label %green
green:
  %phi = phi i8* [ %baseplustwo, %red ], [ %base, %entry ]
  store i8 0, i8* %phi

  %bigbase0 = bitcast i8* %base to i16*
  store i16 -1, i16* %bigbase0

  %loaded = load i8* %phi
  ret i8 %loaded
}

I still get this result:
  PartialAlias: i16* %bigbase0, i8* %phi

but now %phi might not overlap %bigbase0 at all (although, when it does, there is a partial overlap), so we should just return MayAlias (perhaps without delegation because this is a definitive result?).

Thanks again,
Hal

From: “Daniel Berlin” <dberlin@dberlin.org>
To: “Hal Finkel” <hfinkel@anl.gov>
Cc: “Jiangning Liu” <Jiangning.Liu@arm.com>, “George Burgess IV” <george.burgess.iv@gmail.com>, “LLVM Developers
Mailing List” <llvmdev@cs.uiuc.edu>, “Nick Lewycky” <nlewycky@google.com>
Sent: Saturday, January 17, 2015 1:08:10 PM
Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

Hi Danny,

// Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
// BasicAliasAnalysis wins if they disagree. This is intended to help
// support “obvious” type-punning idioms.

  • if (UseCFLAA)
  • addPass( createCFLAliasAnalysisPass());
    addPass( createTypeBasedAliasAnalysisPa ss());
    addPass( createScopedNoAliasAAPass());
  • if (UseCFLAA)
  • addPass( createCFLAliasAnalysisPass());
    addPass( createBasicAliasAnalysisPass() );

Do we really want to change the order here? I had originally placed
it after the metadata-based passes thinking that the compile-time
would be better (guessing that the metadata queries would be faster
than the CFL queries, so if the metadata could quickly return a
NoAlias, then we’d cut out unecessary CFL queries). Perhaps this is
an irrelevant effect, but we should have some documented rationale.

Yeah, this was a mistake (Chandler had suggested it was right
earlier, but we were both wrong :P)

; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
-define i8 @test0(i8* %base, i1 %x) {
+define i8 @test0(i1 %x) {
entry:

  • %base = alloca i8, align 4
    %baseplusone = getelementptr i8* %base, i64 1
    br i1 %x, label %red, label %green
    red:
    @@ -25,8 +26,9 @@ green:
    }

why should this return PartialAlias? %ohi does partially overlap, so
this correct, but what happens when the overlap is partial or
control dependent?
So, after talking with some people offline, they convinced me in SSA
form, the name would change in these situations, and the only
situations you can get into trouble is with things “based on pointer
arguments” (because you have no idea what their initial state is),
or “globals” (because they are not in SSA form)
I could not come up with a case otherwise

Okay; that part of the code could really use some more commentary. I’d really appreciate it if you should put these thoughts in written form that could be added as comments.

Will do

But i’m welcome to hear if you think this is wrong.

FWIW: I bootstrapped/tested the compiler with an assert that
triggered if CFL-AA was going to return PartialAlias and BasicAA
would have returned NoAlias, and it did not trigger with this
change.

(It would have triggered before this set of changes)

Not proof of course, but it at least tells me it’s not “obviously
wrong” :slight_smile:

That’s good :slight_smile: – but, not exactly what I was concerned about. Our general convention has been that PartialAlias is a “strong” result, like MustAlias, but implies that AA has proved that only a partial overlap will occur.

So, in this test case we get the right result:

; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
define i8 @test0(i1 %x) {
entry:
%base = alloca i8, align 4
%baseplusone = getelementptr i8* %base, i64 1
br i1 %x, label %red, label %green
red:
br label %green
green:
%phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]
store i8 0, i8* %phi

%bigbase0 = bitcast i8* %base to i16*
store i16 -1, i16* %bigbase0

%loaded = load i8* %phi
ret i8 %loaded
}

because %phi will have a partial overlap with %bigbase0, the only uncertainty is whether the overlap is with the low byte or the high byte. But if I modify the test to be this:

define i8 @test0x(i1 %x) {
entry:
%base = alloca i8, align 4
%baseplustwo = getelementptr i8* %base, i64 2
br i1 %x, label %red, label %green
red:
br label %green
green:
%phi = phi i8* [ %baseplustwo, %red ], [ %base, %entry ]
store i8 0, i8* %phi

%bigbase0 = bitcast i8* %base to i16*
store i16 -1, i16* %bigbase0

%loaded = load i8* %phi
ret i8 %loaded
}

I still get this result:
PartialAlias: i16* %bigbase0, i8* %phi

but now %phi might not overlap %bigbase0 at all (although, when it does, there is a partial overlap), so we should just return MayAlias (perhaps without delegation because this is a definitive result?).

Yeah, i have to do some size checking, let me see if we have the info and i’ll update the patch.

Otherwise, my view is that we should always delegate MayAlias, because we have no idea what order the passes are in or what pass someone has inserted where :slight_smile:

(WIW: I believe the same about everything except MustAlias and NoAlias, but currently we don’t delegate PartialAlias.
We claim PartialAlias is a definitive result, but it really isn’t.
Right now we have TBAA that will give NoAlias results on things other passes claim are PartialAlias, and that result is correct. That’s just in our default, we have no idea what other people do. Even if you ignore TBAA, plenty of other compilers have noalias/mustalias metadata that would have the same effect.

So, I can make all these testcases work, but it’s a little tricky (it involves tracking some things, like GEP byte range, and then checking bases and using getObjectSize, much like BasicAA does).

Because i really don’t want to put that much “not well tested” code in a bugfix, and honestly, i’m not sure we will catch any cases here that BasicAA does not, i’ve attached a change to XFAIL these testcases, and updated the code to return MayAlias.

I will build and test a patch to get these back to PartialAlias, but this patch will at least get us to not be “giving wrong answers”. I will also see if we catch anything with it that BasicAA does not, because if we don’t, it doesn’t seem worth it to me.

Conservative new patch attached.

(Note that i still updated the testcases, because we will never be able to legally return PartialAlias as they were written)

cflaafix.diff (5.67 KB)

Daniel, I see correctness failures with the previous patch in AArch64 spec2006/h264ref and an internal test code we have.

So I think your patch should only have the code fix for the delegation issue.

I will try the new patch you attached and let you know the results.

Thanks,

Ana.

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Jiangning Liu" <Jiangning.Liu@arm.com>, "George Burgess IV" <george.burgess.iv@gmail.com>, "LLVM Developers
Mailing List" <llvmdev@cs.uiuc.edu>, "Nick Lewycky" <nlewycky@google.com>
Sent: Tuesday, January 20, 2015 1:48:44 PM
Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

So, I can make all these testcases work, but it's a little tricky (it
involves tracking some things, like GEP byte range, and then
checking bases and using getObjectSize, much like BasicAA does).

Because i really don't want to put that much "not well tested" code
in a bugfix, and honestly, i'm not sure we will catch any cases here
that BasicAA does not, i've attached a change to XFAIL these
testcases, and updated the code to return MayAlias.

Okay. I think you might as well just update the test cases to want MayAlias, and put a FIXME comment explaining that they could be PartialAlias. As far as I know, there is no code in LLVM that really handles a PartialAlias differently than a MayAlias or MustAlias, and so while there may be some benefit here, I'm not sure it will be worth the effort.

I will build and test a patch to get these back to PartialAlias, but
this patch will at least get us to not be "giving wrong answers". I
will also see if we catch anything with it that BasicAA does not,
because if we don't, it doesn't seem worth it to me.

My guess is that BasicAA will get almost all of the interesting PartialAlias cases, and as I said, we essentially ignore them anyway.

As a side note, there is this one place in lib/Analysis/MemoryDependenceAnalysis.cpp that could use some attention:

#if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads
      // in terms of clobbering loads, but since it does this by looking
      // at the clobbering load directly, it doesn't know about any
      // phi translation that may have happened along the way.

        // If we have a partial alias, then return this as a clobber for the
        // client to handle.
        if (R == AliasAnalysis::PartialAlias)
          return MemDepResult::getClobber(Inst);
#endif

Conservative new patch attached.

(Note that i still updated the testcases, because we will *never* be
able to legally return PartialAlias as they were written)

Yes, sounds good.

-Hal

From: "Ana Pazos" <apazos@codeaurora.org>
To: "Daniel Berlin" <dberlin@dberlin.org>, "Hal Finkel" <hfinkel@anl.gov>
Cc: "Jiangning Liu" <Jiangning.Liu@arm.com>, "George Burgess IV" <george.burgess.iv@gmail.com>, "LLVM Developers
Mailing List" <llvmdev@cs.uiuc.edu>
Sent: Tuesday, January 20, 2015 3:41:06 PM
Subject: RE: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

Daniel, I see correctness failures with the previous patch in AArch64
spec2006/h264ref and an internal test code we have.

So I think your patch should only have the code fix for the
delegation issue.

I will try the new patch you attached and let you know the results.

Ana, Danny, just because I've somewhat lost track of this: Does fixing the delegation issue fix the LICM degradation using the existing pass ordering? Or is something else necessary for that?

Thanks again,
Hal

Outside of the testcase issues the conservative patch should be the minimum set of changes to fix the LICM issues, and it has no pass ordering changes

Yes, fixing the delegation resolved the LICM degradation in the test I shared.
I will collect new perf numbers to see where we are now.
Ana.

Updated testcases to have MayAlias/note issues as FIXME.

cflaafix.diff (6.56 KB)

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Jiangning Liu" <Jiangning.Liu@arm.com>, "George Burgess IV" <george.burgess.iv@gmail.com>, "LLVM Developers
Mailing List" <llvmdev@cs.uiuc.edu>, "Nick Lewycky" <nlewycky@google.com>
Sent: Wednesday, January 21, 2015 1:10:07 PM
Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

Updated testcases to have MayAlias/note issues as FIXME.

Okay, thanks! This LGTM, but we should probably split the delegation fixes from the others and commit as two separate patches (especially because Ana noted some potential miscompiles caused by the other improvements).

Regarding this:

@@ -768,7 +774,10 @@ static Optional<StratifiedAttr> valueToAttrIndex(Value *Val) {
     return AttrGlobalIndex;

   if (auto *Arg = dyn_cast<Argument>(Val))
- if (!Arg->hasNoAliasAttr())
+ // Only pointer arguments should have the argument attribute,
+ // because things can't escape through scalars without us seeing a
+ // cast, and thus, interaction with them doesn't matter.
+ if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy())
       return argNumberToAttrIndex(Arg->getArgNo());
   return NoneType();
}

when we do see the inttoptr case, we add an edge from the source to the destination. If we've not noted potential aliasing of the non-pointer-typed argument, then does this end up looking like a unique global?

Speaking of which, the code has checks for global variables in several places. Do these need to be for globals that are not aliases and don't have weak linkage?

Thanks again,
Hal

From: “Daniel Berlin” <dberlin@dberlin.org>
To: “Hal Finkel” <hfinkel@anl.gov>
Cc: “Jiangning Liu” <Jiangning.Liu@arm.com>, “George Burgess IV” <george.burgess.iv@gmail.com>, “LLVM Developers
Mailing List” <llvmdev@cs.uiuc.edu>, “Nick Lewycky” <nlewycky@google.com>
Sent: Wednesday, January 21, 2015 1:10:07 PM
Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

Updated testcases to have MayAlias/note issues as FIXME.

Okay, thanks! This LGTM, but we should probably split the delegation fixes from the others and commit as two separate patches (especially because Ana noted some potential miscompiles caused by the other improvements).

I think she mentioned the miscompiles due to us returning partialalias. But in any case, i’m happy to, but just to note they are all required to get the LICM issue fixed :slight_smile:

Regarding this:

@@ -768,7 +774,10 @@ static Optional valueToAttrIndex(Value *Val) {
return AttrGlobalIndex;

if (auto *Arg = dyn_cast(Val))

  • if (!Arg->hasNoAliasAttr())
  • // Only pointer arguments should have the argument attribute,
  • // because things can’t escape through scalars without us seeing a
  • // cast, and thus, interaction with them doesn’t matter.
  • if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy())
    return argNumberToAttrIndex(Arg->getArgNo());
    return NoneType();
    }

when we do see the inttoptr case, we add an edge from the source to the destination.

Correct.

If we’ve not noted potential aliasing of the non-pointer-typed argument, then does this end up looking like a unique global?

No. It will end up looking like something that points to nothing.
Even without this change, it will end up looking like something that points to nothing, it will just have an attribute that says “argument”. :slight_smile:

You can come up with cases where even with this attribute set, it will get the wrong answer. It just happens to have code that, through luck, gets the right answer in a lot of cases:

(That is this code:

if (AttrsA.any() && AttrsB.any())
return AliasAnalysis::MayAlias;

)

So there is a bug here, but it’s not caused by this code.

The bug here is that we can’t ever know what happens as the result of inttoptr. We never do math, and the tracking we do is never going to be sufficient to determine the range of possible pointers for an inttoptr in all cases (in theory, it could point to anything anywhere in the program. If we knew the sizes of all objects, and any binary operator performed on it was evaluable, we could do a little better. If we knew the value came from a ptrtoint, we could do better, etc).
Same with ptrtoint.

The result of both of these instructions should start to be “we have no idea what the pointer that comes from inttoptr or goes to ptrtoint points to”, and we should return mayalias for anything that interacts with them.
We don’t do that right now.
We are just hiding it mildly well.

Speaking of which, the code has checks for global variables in several places. Do these need to be for globals that are not aliases and don’t have weak linkage?

It’s more a question of whether they are in SSA form than if they are globals.

It’s effectively using Globals/Arguments as a way to say “don’t know” in some cases, where it should really just say “don’t know”.

There is a bunch of code i now have marked for cleanup and bugfixes around these issues (constant vs global handling, handling of non-pointer values, etc).

As mentioned, the above is necessary to fix the LICM issue (and is correct, even if somewhere else is wrong. For reference, GCC does the identical thing to what i’m saying :P), but i’m happy to move it to a separate fix (that includes fixes for the other argument/unknown related issues) if you like.

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Jiangning Liu" <Jiangning.Liu@arm.com>, "George Burgess IV"
<george.burgess.iv@gmail.com>, "LLVM Developers
Mailing List" <llvmdev@cs.uiuc.edu>, "Nick Lewycky"
<nlewycky@google.com>
Sent: Wednesday, January 21, 2015 3:48:25 PM
Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting
a57 numbers

> From: "Daniel Berlin" < dberlin@dberlin.org >
> To: "Hal Finkel" < hfinkel@anl.gov >
> Cc: "Jiangning Liu" < Jiangning.Liu@arm.com >, "George Burgess IV"
> < george.burgess.iv@gmail.com >, "LLVM Developers
> Mailing List" < llvmdev@cs.uiuc.edu >, "Nick Lewycky" <
> nlewycky@google.com >
> Sent: Wednesday, January 21, 2015 1:10:07 PM
> Subject: Re: [LLVMdev] question about enabling cfl-aa and
> collecting a57 numbers
>
> Updated testcases to have MayAlias/note issues as FIXME.
>

Okay, thanks! This LGTM, but we should probably split the delegation
fixes from the others and commit as two separate patches (especially
because Ana noted some potential miscompiles caused by the other
improvements).

I think she mentioned the miscompiles due to us returning
partialalias. But in any case, i 'm happy to, but just to note they
are all required to get the LICM issue fixed :slight_smile:

Okay, please do that and commit them.

Regarding this:

@@ -768,7 +774,10 @@ static Optional<StratifiedAttr>
valueToAttrIndex(Value *Val) {
return AttrGlobalIndex;

if (auto *Arg = dyn_cast<Argument>(Val))
- if (!Arg->hasNoAliasAttr())
+ // Only pointer arguments should have the argument attribute,
+ // because things can't escape through scalars without us seeing a
+ // cast, and thus, interaction with them doesn't matter.
+ if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy())
return argNumberToAttrIndex(Arg-> getArgNo());
return NoneType();
}

when we do see the inttoptr case, we add an edge from the source to
the destination.

Correct.

If we've not noted potential aliasing of the non-pointer-typed
argument, then does this end up looking like a unique global?

No. It will end up looking like something that points to nothing.
Even without this change, it will end up looking like something that
points to nothing, it will just have an attribute that says
"argument". :slight_smile:

Okay, fair enough.

You can come up with cases where even with this attribute set, it
will get the wrong answer. It just happens to have code that,
through luck, gets the right answer in a lot of cases:

(That is this code:

if (AttrsA.any() && AttrsB.any())
return AliasAnalysis::MayAlias;
)

So there is a bug here, but it's not caused by this code.

The bug here is that we can't ever know what happens as the result of
inttoptr. We never do math, and the tracking we do is never going to
be sufficient to determine the range of possible pointers for an
inttoptr in all cases (in theory, it could point to anything
anywhere in the program. If we knew the sizes of *all* objects, and
any binary operator performed on it was evaluable, we could do a
little better. If we knew the value came from a ptrtoint, we could
do better, etc).
Same with ptrtoint.

The result of both of these instructions should start to be "we have
no idea what the pointer that comes from inttoptr or goes to
ptrtoint points to", and we should return mayalias for anything that
interacts with them.
We don't do that right now.
We are just hiding it mildly well.

Should we be added an edge from the inttoptr to all other pointer values? Is there a better way?

Speaking of which, the code has checks for global variables in
several places. Do these need to be for globals that are not aliases
and don't have weak linkage?

It's more a question of whether they are in SSA form than if they are
globals.

It's effectively using Globals/Arguments as a way to say "don't know"
in some cases, where it should really just say "don't know".

There is a bunch of code i now have marked for cleanup and bugfixes
around these issues (constant vs global handling, handling of
non-pointer values, etc).

Okay, thanks!

As mentioned, the above is necessary to fix the LICM issue (and is
correct, even if somewhere else is wrong. For reference, GCC does
the identical thing to what i'm saying :P), but i'm happy to move it
to a separate fix (that includes fixes for the other
argument/unknown related issues) if you like.

Generically speaking, I'd prefer the fixes to be broken up as much as practical. Please go ahead and commit them.

-Hal

Thanks again,
Hal

>
>
>
>
>
>
> > From: "Daniel Berlin" < dberlin@dberlin.org >
> > To: "Hal Finkel" < hfinkel@anl.gov >
> > Cc: "Jiangning Liu" < Jiangning.Liu@arm.com >, "George Burgess
> > IV"
> > < george.burgess.iv@gmail.com >, "LLVM Developers
> > Mailing List" < llvmdev@cs.uiuc.edu >, "Nick Lewycky" <
> > nlewycky@google.com >
> > Sent: Tuesday, January 20, 2015 1:48:44 PM
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > collecting a57 numbers
> >
> > So, I can make all these testcases work, but it's a little tricky
> > (it
> > involves tracking some things, like GEP byte range, and then
> > checking bases and using getObjectSize, much like BasicAA does).
> >
> >
> > Because i really don't want to put that much "not well tested"
> > code
> > in a bugfix, and honestly, i'm not sure we will catch any cases
> > here
> > that BasicAA does not, i've attached a change to XFAIL these
> > testcases, and updated the code to return MayAlias.
>
> Okay. I think you might as well just update the test cases to want
> MayAlias, and put a FIXME comment explaining that they could be
> PartialAlias. As far as I know, there is no code in LLVM that
> really
> handles a PartialAlias differently than a MayAlias or MustAlias,
> and
> so while there may be some benefit here, I'm not sure it will be
> worth the effort.
>
> >
> > I will build and test a patch to get these back to PartialAlias,
> > but
> > this patch will at least get us to not be "giving wrong answers".
> > I
> > will also see if we catch anything with it that BasicAA does not,
> > because if we don't, it doesn't seem worth it to me.
>
> My guess is that BasicAA will get almost all of the interesting
> PartialAlias cases, and as I said, we essentially ignore them
> anyway.
>
> As a side note, there is this one place in lib/Analysis/
> MemoryDependenceAnalysis.cpp that could use some attention:
>
> #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting
> loads
> // in terms of clobbering loads, but since it does this by looking
> // at the clobbering load directly, it doesn't know about any
> // phi translation that may have happened along the way.
>
> // If we have a partial alias, then return this as a clobber for
> the
> // client to handle.
> if (R == AliasAnalysis::PartialAlias)
> return MemDepResult::getClobber(Inst) ;
> #endif
>
> >
> >
> > Conservative new patch attached.
> >
> >
> >
> > (Note that i still updated the testcases, because we will *never*
> > be
> > able to legally return PartialAlias as they were written)
> >
>
> Yes, sounds good.
>
> -Hal
>
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > From: "Daniel Berlin" < dberlin@dberlin.org >
> > > To: "Hal Finkel" < hfinkel@anl.gov >
> > > Cc: "Jiangning Liu" < Jiangning.Liu@arm.com >, "George Burgess
> > > IV"
> > > < george.burgess.iv@gmail.com >, "LLVM Developers
> > > Mailing List" < llvmdev@cs.uiuc.edu >, "Nick Lewycky" <
> > > nlewycky@google.com >
> > > Sent: Saturday, January 17, 2015 1:08:10 PM
> > > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > > collecting a57 numbers
> > >
> > >
> > >
> > >
> > >
> > >
> > > Hi Danny,
> > >
> > > // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
> > > // BasicAliasAnalysis wins if they disagree. This is intended
> > > to
> > > help
> > > // support "obvious" type-punning idioms.
> > > - if (UseCFLAA)
> > > - addPass( createCFLAliasAnalysisPass());
> > > addPass( createTypeBasedAliasAnalysisPa ss());
> > > addPass( createScopedNoAliasAAPass());
> > > + if (UseCFLAA)
> > > + addPass( createCFLAliasAnalysisPass());
> > > addPass( createBasicAliasAnalysisPass() );
> > >
> > > Do we really want to change the order here? I had originally
> > > placed
> > > it after the metadata-based passes thinking that the
> > > compile-time
> > > would be better (guessing that the metadata queries would be
> > > faster
> > > than the CFL queries, so if the metadata could quickly return a
> > > NoAlias, then we'd cut out unecessary CFL queries). Perhaps
> > > this
> > > is
> > > an irrelevant effect, but we should have some documented
> > > rationale.
> > >
> > >
> > >
> > > Yeah, this was a mistake (Chandler had suggested it was right
> > > earlier, but we were both wrong :P)
> > >
> > >
> > >
> > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
> > > -define i8 @test0(i8* %base, i1 %x) {
> > > +define i8 @test0(i1 %x) {
> > > entry:
> > > + %base = alloca i8, align 4
> > > %baseplusone = getelementptr i8* %base, i64 1
> > > br i1 %x, label %red, label %green
> > > red:
> > > @@ -25,8 +26,9 @@ green:
> > > }
> > >
> > > why should this return PartialAlias? %ohi does partially
> > > overlap,
> > > so
> > > this correct, but what happens when the overlap is partial or
> > > control dependent?
> > > So, after talking with some people offline, they convinced me
> > > in
> > > SSA
> > > form, the name would change in these situations, and the only
> > > situations you can get into trouble is with things "based on
> > > pointer
> > > arguments" (because you have no idea what their initial state
> > > is),
> > > or "globals" (because they are not in SSA form)
> > > I could not come up with a case otherwise
> >
> > Okay; that part of the code could really use some more
> > commentary.
> > I'd really appreciate it if you should put these thoughts in
> > written
> > form that could be added as comments.
> >
> >
> >
> >
> >
> > Will do
> >
> >
> >
> > > But i'm welcome to hear if you think this is wrong.
> > >
> > > FWIW: I bootstrapped/tested the compiler with an assert that
> > > triggered if CFL-AA was going to return PartialAlias and
> > > BasicAA
> > > would have returned NoAlias, and it did not trigger with this
> > > change.
> > >
> > >
> > > (It would have triggered before this set of changes)
> > >
> > > Not proof of course, but it at least tells me it's not
> > > "obviously
> > > wrong" :slight_smile:
> > >
> > >
> >
> > That's good :slight_smile: -- but, not exactly what I was concerned about.
> > Our
> > general convention has been that PartialAlias is a "strong"
> > result,
> > like MustAlias, but implies that AA has proved that only a
> > partial
> > overlap will occur.
> >
> > So, in this test case we get the right result:
> >
> > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
> > define i8 @test0(i1 %x) {
> > entry:
> > %base = alloca i8, align 4
> > %baseplusone = getelementptr i8* %base, i64 1
> > br i1 %x, label %red, label %green
> > red:
> > br label %green
> > green:
> > %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]
> > store i8 0, i8* %phi
> >
> > %bigbase0 = bitcast i8* %base to i16*
> > store i16 -1, i16* %bigbase0
> >
> > %loaded = load i8* %phi
> > ret i8 %loaded
> > }
> >
> > because %phi will have a partial overlap with %bigbase0, the only
> > uncertainty is whether the overlap is with the low byte or the
> > high
> > byte. But if I modify the test to be this:
> >
> > define i8 @test0x(i1 %x) {
> > entry:
> > %base = alloca i8, align 4
> > %baseplustwo = getelementptr i8* %base, i64 2
> > br i1 %x, label %red, label %green
> > red:
> > br label %green
> > green:
> > %phi = phi i8* [ %baseplustwo, %red ], [ %base, %entry ]
> > store i8 0, i8* %phi
> >
> > %bigbase0 = bitcast i8* %base to i16*
> > store i16 -1, i16* %bigbase0
> >
> > %loaded = load i8* %phi
> > ret i8 %loaded
> > }
> >
> > I still get this result:
> > PartialAlias: i16* %bigbase0, i8* %phi
> >
> >
> >
> >
> >
> >
> >
> > but now %phi might not overlap %bigbase0 at all (although, when
> > it
> > does, there is a partial overlap), so we should just return
> > MayAlias
> > (perhaps without delegation because this is a definitive
> > result?).
> >
> >
> >
> >
> > Yeah, i have to do some size checking, let me see if we have the
> > info
> > and i'll update the patch.
> >
> >
> >
> >
> > Otherwise, my view is that we should always delegate MayAlias,
> > because we have no idea what order the passes are in or what pass
> > someone has inserted where :slight_smile:
> >
> >
> > (WIW: I believe the same about everything except MustAlias and
> > NoAlias, but currently we don't delegate PartialAlias.
> > We claim PartialAlias is a definitive result, but it really
> > isn't.
> > Right now we have TBAA that will give NoAlias results on things
> > other
> > passes claim are PartialAlias, and that result is correct. That's
> > just in our default, we have no idea what other people do. Even
> > if
> > you ignore TBAA, plenty of other compilers have noalias/mustalias
> > metadata that would have the same effect.
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>

--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

--

Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

Should we be added an edge from the inttoptr to all other pointer values? Is there a better way?

We should use graph edges, so we can do something better at set build time :slight_smile:

Works for me