question about enabling cfl-aa and collecting a57 numbers

Project Infrastructure LLVM Dev List Archives
1

Hi folks,

Moving the discussion to llvm.dev.

None of the changes we talked earlier help.

Find attached the C source code that you can use to reproduce the issue.

clang --target=aarch64-linux-gnu -c -mcpu=cortex-a57 -Ofast -fno-math-errno test.c -S -o test.s -mllvm -debug-only=licm
LICM hoisting to while.body.lr.ph: %21 = load double** %arrayidx8, align 8, !tbaa !5
LICM hoisting to while.body.lr.ph: %arrayidx72 = getelementptr inbounds double* %11, i64 1
LICM hoisting to while.body.lr.ph: %arrayidx81 = getelementptr inbounds double* %11, i64 2
LICM hoisting to for.body.lr.ph: %2 = ptrtoint i32* %Index to i64

clang --target=aarch64-linux-gnu -c -mcpu=cortex-a57 -Ofast -fno-math-errno test.c -S -o test-cflaa.s -mllvm -use-cfl-aa -mllvm -debug-only=licm
LICM hoisting to for.body.lr.ph: %2 = ptrtoint i32* %Index to i64

Why CFL AA cannot allow hoisting this out: %21 = load double** %arrayidx8, align 8, !tbaa !5

Which leads to this extra load in assembly code: ldr x14, [x4, x9, lsl #3]

Thanks!
Ana.

test.c (582 Bytes)

2

Anything other than noalias or mustalias should be getting passed down the stack, so either that is not happening or CFL aa is giving better answers and something does worse with those better answers. I’ll take a look this evening

3

Can you send me actual LLVM IR or a preprocessed source from using -E?
I don’t have a machine handy that has headers that target that arch.

4

This is caused by CFLAA returning PartialAlias for a query that BasicAA can prove is NoAlias.

I’ve attached a patch that fixes it, but truthfully, chaining seems somewhat badly designed IMHO.

It should let you pass along the result you’ve gotten so far, so that you don’t have CFLAA get PartialAlias, chain, and have BasicAA get MayAlias.

(IE it should let it work strictly down the hierarchy).

Note that this patch breaks the CFLAliasAnalysis tests because it no longer returns PartialAlias in some cases it is expecting it.

I don’t have time ATM to fix chaining completely, so if someone wants to shepherd this patch through, that would be appreciated.

cflaafix.diff (1.46 KB)

5

This is caused by CFLAA returning PartialAlias for a query that BasicAA
can prove is NoAlias.

One of them is wrong. Which one?

I'm not sure from your description that this is a chaining issue.
PartialAlias doesn't chain and isn't supposed to, it's a final answer just
like NoAlias and MustAlias are. You return partial alias when you have
proven that the accesses are overlapping, meaning that it is proven to
neither be no alias nor must alias.

Nick

I've attached a patch that fixes it, but truthfully, chaining seems

6

This is caused by CFLAA returning PartialAlias for a query that BasicAA
can prove is NoAlias.

One of them is wrong. Which one?

CFL-AA.

Right now it checks whether two things come out to be the same stratified
info and have the same index, and if so, returns PartialAlias. This is
wrong, because it never knows why two things got unified, only that they
did.

Therefore, the current check it does where it returns PartialAlias seems
wrong.

George, why does it return PartialAlias?

IMHO, you can't ever prove any kind of must-alias or partialalias info with
CFL-AA, unless i'm missing something.

I'm not sure from your description that this is a chaining issue.
PartialAlias doesn't chain and isn't supposed to, it's a final answer just
like NoAlias and MustAlias are. You return partial alias when you have
proven that the accesses are overlapping, meaning that it is proven to
neither be no alias nor must alias.

Well, it's still chaining wrong, because it did not change on MayAlias, but
you are right that it is not the issue i identified :slight_smile:

Anyway, updated patch attached.

cflaafix.diff (824 Bytes)

7

Someone asked what I meant by this, so, two things:
First, CFL-AA does not know whether the statements it processes will ever
be executed or where they occur in the function.. The results also do not
depend on the order in which statements are processed.

So even if it only sees one assignment and nothing else, and unifies those
two variable, the result is no different whether the assignment is in a
branch or whether it is the only statement in the function.

IE

int *a;
int *b;

a = b

and

if (c)
  a = b

should produce the same pointer-analysis result with CFL-AA (and all flow +
path -insensitive analysis).

If these are the only pointer assigning statements in the function, the
first is must-alias, the second is may-alias.
Because it cannot distinguish these two, IMHO, it can never return
must-alias (or partialalias).

Second, the process of pointer info unification is not and should not be
related to the process of assignments in practice (and thus, even if you
could distinguish the above, the fact that it believes two pointers
equivalent does not make them must-alias).

Variables may get unified because we lack info and it's the conservatively
safe thing to do, or even because we are trying to lower the time bounds
and decide losing precision is okay.

In short, unless i'm missing something drastic, i can't see how CFL-AA can
ever produce must-alias or partial-alias info.

8

Inline

  • George

It shouldn’t – unless I misinterpreted an earlier discussion, I was under the impression that we were testing with that line updated to return MayAlias. We do need to update that in LLVM though; thanks for the fix.

Agreed.

9

Yeah, it was this (which you mentioned) and the fact that if query() returned MayAlias in alias(), we did not delegate there either.

I had assumed the PartialAlias was intentional because you have a test for it explicitly test/Analysis/CFLAliasAnalysis/must-and-partial.ll

Note that i actually agree that those cases in must-and-partial are partialalias/etc.
You may even be able to prove them in CFL-AA if you had “never touched arguments in this set”, “never touched globals in this set”, and all variables in the set were SSA variables.
But otherwise, …

For example, you are also adding edges between arguments.

So in this case:

; Function Attrs: nounwind
define void @test(double*** nocapture readonly %A, i32* nocapture readonly %Index) #0 {
entry:
br i1 undef, label %for.body.lr.ph, label %for.end

for.body.lr.ph: ; preds = %entry
br label %for.body

for.body: ; preds = %for.body, %for.body.lr.ph
%arrayidx22 = getelementptr inbounds double* %Index, i64 2
%0 = load double* %arrayidx22, align 8, !tbaa !1
%arrayidx25 = getelementptr inbounds double* %A, i64 2
%1 = load double* %arrayidx25, align 8, !tbaa !1
%mul26 = fmul double %0, %1
br i1 undef, label %for.end, label %for.body

for.end: ; preds = %for.body, %entry
ret void
}

It believes %Index PartialAlias %A, which is clearly wrong :slight_smile:

If you have any time to do the work necessary to make partialalias work for the other cases, let me know.
Otherwise, i’d say we disable it and XFAIL the testcases for now.

10

Daniel, your patch does not apply cleanly. Are you on the tip?

The code I see there is no line    if (QueryResult == MayAlias|| QueryResult == PartialAlias) to be removed.

Thanks,

Ana.

11

Oh, sorry, i didn’t rebase it when i changed the fix, you would have had to apply the first on top of the second.

Here is one against HEAD

cflaafix.diff (1.74 KB)

12

Returning PartialAlias if SetA.Index == SetB.Index was an artifact of the assumption that we would be queried last. Clearly, this assumption is now incorrect — I should have at least explicitly noted this in the code; it was my mistake. :slight_smile:

XFAIL for now SGTM — I start classes again next week, and am booked until then, so I’ll see what I can get done once I reach college. (I’ll have quite a bit more free time than last semester)

So that we’re clear, for your code, CFLAA should (now) output %A MayAlias %Index. It will respond with this for either of the following reasons:

  • The StratifiedSets themselves are {%mul26, %1, %0} “below” {%arrayidx22, %arrayidx25, %A, %Index}.
    The fmul causes the union between the (previously separate) {%1} “below" {%arrayidx25, %A}, and {%0} “below” {%arrayidx22, %Index} sets.
  • %A and %Index are both arguments, and the following code compiles/has defined behavior with -fno-strict-aliasing:
    void* ptr = new double[3];
    test((double***)ptr, (int*)ptr))
    // (A potential future improvement, naturally, would be to make use of the noalias attribute on args.)
13

Daniel, don’t we need to fix the order of invoking alias analyses in lib/Transforms/IPO/PassManagerBuilder.cpp as well?

Your patch fixed the order in lib/CodeGen/Passes.cpp and the delegation code in lib/Analysis/CFLAliasAnalysis.cpp.

Thanks,

Ana.

14

From: "Ana Pazos" <apazos@codeaurora.org>
To: "Daniel Berlin" <dberlin@dberlin.org>
Cc: "George Burgess IV" <george.burgess.iv@gmail.com>, "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>,
"Jiangning Liu" <Jiangning.Liu@arm.com>
Sent: Thursday, January 15, 2015 1:33:57 PM
Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

Daniel, don’t we need to fix the order of invoking alias analyses in
lib/Transforms/IPO/PassManagerBuilder.cpp as well?

Your patch fixed the order in lib/CodeGen/Passes.cpp and the
delegation code in lib/Analysis/CFLAliasAnalysis.cpp.

Yes, the order in lib/CodeGen/Passes.cpp and lib/Transforms/IPO/PassManagerBuilder.cpp should be kept consistent.

-Hal

15

Yes.
I’ve attached an updated patch that does the following:

  1. Fixes the partialalias of globals/arguments

  2. Enables partialalias for cases where nothing has been unified to a global/argument

  3. Fixes that select was unifying the condition to the other pieces (the condition does not need to be processed :P). This was causing unnecessary aliasing.

  4. Adds a regression test to must-and-partial

  5. Fixes the pass ordering

  6. Does not alias non-pointer arguments to random things :slight_smile:

  7. Fixes the CFL test cases that break with above.

cflaafix.diff (6.07 KB)

16

Yes.
I've attached an updated patch that does the following:

1. Fixes the partialalias of globals/arguments
2. Enables partialalias for cases where nothing has been unified to a
global/argument
3. Fixes that select was unifying the condition to the other pieces (the
condition does not need to be processed :P). This was causing unnecessary
aliasing.

Consider this:

void *p = ...;
uintptr_t i = p;
uintptr_t j = 0;
for (int a = 0; a < sizeof(uintptr_t); ++a) {
  j = i >> (sizeof(uintptr_t) - a - 1) ? 1 : 0;
  j <<= 1;
}
void *q = j;

alias(p, q) isn't NoAlias. (Okay, it kinda is in C++, but not in the
equivalent LLVM IR. Please don't make me rewrite my example in LLVM IR.)

Nick

17

Yes.
I've attached an updated patch that does the following:

1. Fixes the partialalias of globals/arguments
2. Enables partialalias for cases where nothing has been unified to a
global/argument
3. Fixes that select was unifying the condition to the other pieces (the
condition does not need to be processed :P). This was causing unnecessary
aliasing.

Consider this:

void *p = ...;
uintptr_t i = p;
uintptr_t j = 0;
for (int a = 0; a < sizeof(uintptr_t); ++a) {
  j = i >> (sizeof(uintptr_t) - a - 1) ? 1 : 0;
  j <<= 1;
}
void *q = j;

alias(p, q) isn't NoAlias. (Okay, it kinda is in C++, but not in the
equivalent LLVM IR. Please don't make me rewrite my example in LLVM IR.)

Agreed :slight_smile:

But after chatting with you, i think we both agree that this change does
not affect.
I probably should not have said "the condition does not need to be
processed". It would be more accurate to say "the reference to a condition
in a select instruction, by itself, does not cause aliasing"

What happens now is:

given %4 = select %1, %2, %3

we do
aliasset(%4) += %1
aliasset(%4) += %2
aliasset(%4) += %3

The first one is unnecessary.
There can be no alias caused simply because it is referenced in condition
of the select.

We still need to process what %1 refers to (and we do).

To make this empirical, in your example, we get the right answer in CFL-AA.

Interestingly, i'll point out that basic-aa says:
  NoAlias: i8* %p, i8** %q
  NoAlias: i8** %p.addr, i8** %q

(I translated your case as best i can :P)

So you may want to implement it for real if you think it's supposed to be
handled right in basic-aa, because I don't believe it is :slight_smile:

18

Okay, overnight i ran a ton of tests on this patch, and it seems right.
Nick, Hal, can you review it?

I’ve reattached it for simplicity

cflaafix.diff (6.2 KB)

19

I’m pretty sure I had the ordering of the passes backwards. The previous ordering is correct. Sorry for the confusion.

The last alias analysis created is the first one queried. It delegates to the previous alias analysis created. At least, that is my reading of this (very confusing) code.

The most frustrating aspect of this is that it means the delegation behavior of CFL shouldn’t have mattered at all because BasicAA ran first… However BasicAA does do its own caching, so who knows.

20

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:

cflaafix.diff (4.74 KB)