inttoptr and basicaa

Hi,

I am observing some incorrect behavior in basicaa, wherein two pointers that
basicaa should determine to be MustAlias are ending up NoAlias - the other
extreme :frowning:
I am blaming this on basicaa not handling inttoptr. Here is the relevant IR
snippet.

If we can prove the difference between two pointer values is a
compile-time constant (in this case, zero), we can return
NoAlias/MustAlias/etc. based purely on that. That said, GEP makes
special aliasing guarantees which are impossible to reconstruct from
inttoptr.

-Eli

BasicAA treats it conservatively if used on its own. It will return mayalias for the two pointers.

TBAA operates based on the guarantee that pointers to different types cannot alias (think C’s strict aliasing rules).
Therein lies its power but also its danger, that is, nothing prevents the programmer to write code that violates these rules (That’s why we have -fno-strict-aliasing).

So when basica gives up returning mayalias we query tbaa, which will return - based on strict aliasing rules of our language - noalias.

opt -basicaa -print-alias-sets basicaa.ll -S -o -
Alias Set Tracker: 1 alias sets for 2 pointer values.
AliasSet[0x109808c90, 2] may alias, Mod Pointers: (i64* %sunkaddr4, 18446744073709551615), (i32* %sunkaddr2, 18446744073709551615)

opt -basicaa -tbaa -print-alias-sets basicaa.ll -S -o -
Alias Set Tracker: 2 alias sets for 2 pointer values.
AliasSet[0x112d07cf0, 1] must alias, Mod Pointers: (i64* %sunkaddr4, 18446744073709551615)
AliasSet[0x112d07d40, 1] must alias, Mod Pointers: (i32* %sunkaddr2, 18446744073709551615)

define void @basicaatest(%str* %a) {
%sunkaddr1 = ptrtoint %str* %a to i32
%sunkadd = add i32 %sunkaddr1, 4
%sunkaddr2 = inttoptr i32 %sunkadd to i32*
%sunkaddr3 = ptrtoint %str* %a to i32
%sunkadd2 = add i32 %sunkaddr1, 4
%sunkaddr4 = inttoptr i32 %sunkadd2 to i64*
store i64 1, i64* %sunkaddr4, !tbaa !0
store i32 2, i32* %sunkaddr2, !tbaa !2
ret void
}

!0 = metadata !{metadata !“int64”, metadata !1}
!1 = metadata !{}
!2 = metadata !{metadata !“int32”, metadata !1}

From: llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu]
On Behalf Of Arnold Schwaighofer
Subject: [LLVMdev] inttoptr and basicaa

BasicAA treats it conservatively if used on its own. It will return mayalias
for the two pointers.

TBAA operates based on the guarantee that pointers to different types cannot
alias (think C's strict aliasing rules). Therein lies its power but also its
danger, that is, nothing prevents the programmer to write code that violates
these rules (That's why we have -fno-strict-aliasing).

So when basica gives up returning mayalias we query tbaa, which will return -
based on strict aliasing rules of our language - noalias.

Except... TBAA is called prior to basicaa, when using addInitialAliasAnalysisPasses().

- Chuck

THIS COMMUNICATION MAY CONTAIN CONFIDENTIAL AND/OR OTHERWISE PROPRIETARY MATERIAL and is thus for use only by the intended recipient. If you received this in error, please contact the sender and delete the e-mail and its attachments from all computers.

No, TBBA is added first to the pass manager and as a result BasicAA
will run first - we give it a chance to recognize obviously bad
things. It comes up with mayalias and calls the next analysis (TBAA in
our case) in the chain by calling AliasAnalysis::alias in its
aliasCheck method.

Unfortuntaley, BasicAA does not look through the inttoptr so it does
not recognize that they must-alias. But it is doing nothing wrong by
returning may-alias or querying the next analysis.

Hi,

I am observing some incorrect behavior in basicaa, wherein two pointers that
basicaa should determine to be MustAlias are ending up NoAlias - the other
extreme :frowning:
I am blaming this on basicaa not handling inttoptr. Here is the relevant IR
snippet.

%sunkaddr36 = ptrtoint %struct.BitParams* %bs to i32
%sunkaddr37 = add i32 %sunkaddr36, 16
%sunkaddr38 = inttoptr i32 %sunkaddr37 to i32*

%sunkaddr39 = ptrtoint %struct.BitParams* %bs to i32
%sunkaddr40 = add i32 %sunkaddr39, 16
%sunkaddr41 = inttoptr i32 %sunkaddr40 to i64*

A query to basicaa: alias(%sunkaddr41, 8, %sunkaddr38, 4) results in a
NoAlias return value.
The reason is that nothing inside basicaa processes inttoptr; the fall
through case of using TBAA (int and long long in this case) is executed and
NoAlias is returned as the pointer types are different.

From the perspective of the compiler, this code is making an outrageous demand of the compiler. It’s doing type punning with the pun obscured by casting of pointers to integers. That’s considered extreme.

I have two questions.

  1. Is it safe for basicaa to reason about inttoptr in a manner similar to
    aliasGEP (using decomposeGEPExpression to symbolically evaluate the
    pointer).

GEP’s restrictions make it easier to analyze.

  1. If the answer to the above is no, then shouldn’t basicaa treat the above
    conservatively before it looks at TBAA ?

There’s no absolute answer to this question. C-style TBAA is a gray area by its nature.

On one hand, it might make sense to have BasicAA use PartialAlias here (and relax its definition). That would be a way to say “I don’t know” while still preventing the query from being passed to TBAA.

On the other hand, is this code really worth worrying about, or is the right answer to just compile it with -fno-strict-aliasing? If the code is punning with integer-casted pointers, what other things might it be doing that might cause trouble?

On the third hand, if you are concerned about getting good optimization, it may be worthwhile to look into rewriting the code to avoid inttoptr and ptrtoint, since these may be suppressing other optimizations besides.

Dan