I'm hitting a strange pointer aliasing "bug". Here is a test case :
/* SOURCE CODE */
#define little_list_size 8
class LittleList1 {
public:
int _length;
double _data[ little_list_size ];
LittleList1( int length )
{
_length = length;
for( int i=0; i<length; i++ )
_data[i] = 0;
}
};
class LittleList2 {
public:
int _length;
double _data[ little_list_size ];
LittleList2( int length )
{
_length = length;
for( int i=0; i<_length; i++ )
_data[i] = 0;
}
};
int func1()
{
LittleList1 l(4);
return l._length;
}
int func2()
{
LittleList2 l(4);
return l._length;
}
/* END SOURCE CODE */
The only difference between the 2 classes is in the constructor, in the line :
for( int i=0; i<_length; i++ )
One has "length" which is a function parameter, the other has "_length" which is the class member which was initialized in the same constructor.
Now let's compile and optimize :
llvm-g++ -emit-llvm -Winline -O3 -Iinclude -c test2.cpp -o test2.bc
opt -S -O3 -print-alias-sets -count-aa test2.bc
Result :
%struct.LittleList1 = type { i32, [8 x double] }
There are essentially two ways to "solve" this issue: one is
type-based alias analysis, i.e. assuming "double" and "int" don't
alias; LLVM doesn't implement this at the moment. The other is to
attempt to analyze the loop and prove that %indvar.i is never
negative; LLVM doesn't implement anything like this at the moment
either.
-Eli
There are essentially two ways to "solve" this issue: one is
type-based alias analysis, i.e. assuming "double" and "int" don't
alias; LLVM doesn't implement this at the moment. The other is to
attempt to analyze the loop and prove that %indvar.i is never
negative; LLVM doesn't implement anything like this at the moment
either.
-Eli
Actually I think it's much simpler than that...
http://llvm.org/releases/1.3/docs/AliasAnalysis.html#basic-aa
it says says "Different fields of a structure do not alias."
This is the case here : we have two different fields of a struct however it mistakenly thinks they alias.
Consider a case like the following:
struct X { int a; int b[10]; };
int f(struct X* a) { a->b[-1] = 1; return a->a; }
This is technically illegal code, but various programs depend on
constructs like this working.
-Eli
Those programs are buggy and should be fixed.
Consider a case like the following:
struct X { int a; int b[10]; };
int f(struct X* a) { a->b[-1] = 1; return a->a; }
This is technically illegal code, but various programs depend on
constructs like this working.
Actually if you want to do bit-casting in C the usual way is to very carefully use an union which informs the compiler that there will be aliasing...
Those programs are buggy and should be fixed.
Totally agree. Making such ugly things work means lots of optimizations can't be performed.
I wonder if llvm intentionnally generates this spurious alias (to make badly written code work) or is it just the optimizer not being smart enough yet ?...
Consider a case like the following:
struct X { int a; int b[10]; };
int f(struct X* a) { a->b[-1] = 1; return a->a; }
This is technically illegal code, but various programs depend on
constructs like this working.
Actually if you want to do bit-casting in C the usual way is to very carefully use an union which informs the compiler that there will be aliasing...
Quite right. Unfortunately, Eli is correct that there is a large codebase out there that uses less friendly idioms. It's getting better over time as people fix the issues (perhaps wishful thinking on my part), but it is still a "gotcha" we need to be aware of and consider when we make more aggressive optimizations.
Making such ugly things work means lots of optimizations can't be performed.
Exactly. To elaborate on my probably-too-curt initial response, I believe that optimizations should not be constrained by non-comformant code. That said, I also believe we should be as friendly as we can in helping people find and fix these issues. Tracking down a bug like that in user code is an absolute nightmare. Specifically, we should issue good diagnostics for problems of this sort, from the compiler and/or from the static analyzer, whenever possible.
I wonder if llvm intentionnally generates this spurious alias (to make badly written code work) or is it just the optimizer not being smart enough yet ?...
I'm not 100% sure, but I suspect it's the latter.
-Jim
Makes sense. It would really make sense to conditionalize all this on
an option like gcc's -fstrict-aliasing. As far as I know the Linux
kernel still needs this option to be turned off.
Andrew.
I don't know if it's illegal, but this is how libstdc++'s string
implementation finds its header data. std::string stores a pointer
directly to the character data (making subscripting slightly faster),
and then subtracts the size of the header when it needs to do any
bookkeeping.
Do you have a reference to the standard that makes it undefined?
Do you have a reference to the standard that makes it undefined?
I'm second this question. I tried to find anything banning calculating
address of one field from address of another in the standard some time
ago, but could not find it.
There are essentially two ways to "solve" this issue: one is
type-based alias analysis, i.e. assuming "double" and "int" don't
alias; LLVM doesn't implement this at the moment. The other is to
attempt to analyze the loop and prove that %indvar.i is never
negative; LLVM doesn't implement anything like this at the moment
either.
-Eli
Actually I think it's much simpler than that...
http://llvm.org/releases/1.3/docs/AliasAnalysis.html#basic-aa
it says says "Different fields of a structure do not alias."
This is the case here : we have two different fields of a struct however it
mistakenly thinks they alias.
Consider a case like the following:
struct X { int a; int b[10]; };
int f(struct X* a) { a->b[-1] = 1; return a->a; }
This is technically illegal code, but various programs depend on
constructs like this working.
I don't know if it's illegal, but this is how libstdc++'s string
implementation finds its header data. std::string stores a pointer
directly to the character data (making subscripting slightly faster),
and then subtracts the size of the header when it needs to do any
bookkeeping.
Character types are special: they can alias everything. if this weren't
the case you couldn't write malloc().
Do you have a reference to the standard that makes it undefined?
Several places, but 6.3.2.3 of C99 is the most important: it lists all
the legal pointer conversions.
Andrew.
Do you have a reference to the standard that makes it undefined?
I'm second this question. I tried to find anything banning calculating
address of one field from address of another in the standard some time
ago, but could not find it.
In the currect C++0x FCD, 5.7/5:
"When an expression that has integral type is added to or subtracted
from a pointer, the result has the type of the pointer operand.
If the pointer operand points to an element of an array object, and
the array is large enough, the result points to an element offset
from the original element such that the difference of the subscripts
of the resulting and original array elements equals the integral
expression. In other words, if the expression P points to the i-th
element of an array object, the expressions (P)+N (equivalently,
N+(P)) and (P)-N (where N has the value n) point to, respectively,
the i + n-th and i − n-th elements of the array object, provided
they exist. Moreover, if the expression P points to the last element
of an array object, the expression (P)+1 points one past the last
element of the array object, and if the expression Q points one past
the last element of an array object, the expression (Q)-1 points to
the last element of the array object. If both the pointer operand
and the result point to elements of the same array object, or one
past the last element of the array object, the evaluation shall not
produce an overflow; otherwise, the behavior is undefined."
(Note in particular the last phrase, and recall that subscripting is defined in terms of pointer arithmetic.)
Daveed
The better reference is 6.5.6p7-8, about pointer addition:
For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.
If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.
John.
So the proper way to compute the header's address is
_Rep* _M_rep(char* data) {
return reinterpret_cast<_Rep*>(intptr_t(data) - sizeof(_Rep));
}
as opposed to the
_Rep* _M_rep(char* data) {
return &(reinterpret_cast<_Rep*>(data)[-1]);
}
that gcc-4.2 through gcc-4.4 use (I didn't check others). Although,
since the _Rep object is not an element of an array, and '(_Rep*)data'
points one-past-the-end, a -1 subscript actually looks legal.
But even if it's illegal, this only affects the "inbounds" qualifier
on the GEP, not the aliasing rules, which the original question was
about. I think the version that adjusts the pointer through intptr_t
obeys all the aliasing rules.
Exactly. To elaborate on my probably-too-curt initial response, I believe that optimizations should not be constrained by non-comformant code.
The example I chose (LittleList class) was not really innocent : this kind of initialization in a constructor is quite common. Suppose we have a class for short vectors (there is one in LLVM), in this case we expect the compiler to "do the right thing", when the length is a known constant that means inline the constructor, unroll the loop, and basically turn it into something that looks like an intrinsic memset(). Doesn't happen because of the aliasing... GCC figures it out though.
helping people find and fix these issues. Tracking down a bug like that in user code is an absolute nightmare. Specifically, we should issue good diagnostics for problems of this sort, from the compiler and/or from the static analyzer, whenever possible.
Warnings are useful.
Note that if in a struct { int32 length, double data[10] } "data" can alias "length", why can't it alias the rest of the stack, or even the entire memory space ? If the compiler supposes that out of bounds accesses are "legal" on data we might as well deactivate alias analysis for the whole program...
It would also be cool to be able to tell the compiler that 2 pointers don't alias (or that they do). __restrict only works on function arguments which makes it a lot less useful...
FYI,
the case below can be folded with -scev-aa -licm,
to hoist this->_length on former loop.
class LittleList2X {
public:
int _length;
double _data[8];
LittleList2X( int length )
{
_length = length;
int i = 0;
#if 1
for( ; i<_length && i <= 0x1FFFFFFE; i++ )
_data[i] = 0;
#endif
for( ; i<_length; i++ )
_data[i] = 0;
}
};
Rationale: the pass ScalarEvolution discovers range of &_data[i] must be finite.
(impossible when i >= 0x1FFFFFFF on p:32 target)
...Takumi
John, David,
That's not the whole story, though. For example, 6.7.2.1/13 of C99
allows a conversion between a pointer to struct and it's first member
and also specifies that members of the struct are laid out in the
order of declaration. To derive pointer to one field from another it's
sufficient to 1) cast pointer to a struct to a pointer to array of
chars 2) perform arithmetics as per 6.5.6 3) cast the pointer to
pointer to a field. I have not found paragraphs explicitly allowing or
denying 1 and 3, however there are many hints -- offsetof macro, which
would have no use otherwise; 6.2.6/4, which allows to copy any object
into array of chars; aliasing rules of 6.5, which allow accessing any
object through char*.
On the original subject -- in this example, isn't it guaranteed that
_length and _data[i] do not alias? i is non-negative (if it's unsigned
-- by definition, if it's signed -- because signed overflow is
undefined behaviour), so &_data[i] >= &_data > &_length.
Eugene
Hello Eugene,
The underlying problem here is that your reasoning below follows
C rules, while BasicAA and other LLVM passes must follow
LLVM IR rules, which are different in this area. In LLVM IR, memory
has no types. Translating from C to LLVM IR does not preserve
this information.
In addition to being the reason BasicAA can't reason about array
bounds and struct members as you describe, it's also the reason
BasicAA can't do type-based alias analysis.
The expected solution for type-based alias analysis uses
metadata to describe additional guarantees that C makes. In a
similar manner, metadata could perhaps be used to describe C
array bounds and struct member rules.
This overall design has tradeoffs; there are advantages as well
as disadvantages.
Dan
Hi Dan,
Are you referring to my reasoning for why _length and _data[i] do not
alias? I don't think this needs TBAA or any "strict" aliasing rules.
All that sufficient is 1) assumption about struct layout:
offsetof(_length) < offsetof(_data) 2) assumption that i >= 0.
My understanding is that 1) is guaranteed by llvm rules and 2) by C
rules, however I'm not sure how to express C rules in llvm IR. For
signed types "nsw" flag on arithmetic seems close, if I understand the
description of trap values. For unsigned types arithmetic is fine, but
we probably need "unsigned" flag in getelementptr to signal that
offset is treated as unsigned.
In fact, as Takumi pointed out, if you add an extra comparison to
ensure 2) SCEV can already optimize the loop.
Or am I missing something?
Eugene
Hi Dan,
Are you referring to my reasoning for why _length and _data[i] do not
alias?
No, I was referring to the discussion of C99 6.7.2.1, 6.5.6,
6.2.6, and so on.
I don't think this needs TBAA or any "strict" aliasing rules.
All that sufficient is 1) assumption about struct layout:
offsetof(_length) < offsetof(_data) 2) assumption that i >= 0.
My understanding is that 1) is guaranteed by llvm rules and 2) by C
rules, however I'm not sure how to express C rules in llvm IR. For
signed types "nsw" flag on arithmetic seems close, if I understand the
description of trap values.
Right; this is the second of the two approaches Eli originally
suggested. For this approach, the IR is already sufficient to
allow the optimizer to prove that i >=0 and to subsequently prove
that the relevant pointers don't alias.
BasicAA doesn't have any logic related to proving either
i >= 0, or that _length and _data don't alias even if
it somehow knew i >= 0. It could be taught both of those
things, if someone were interested.
SCEV-AA does have logic related to proving that i >= 0, but
it happens to fail in this testcase; I haven't investigated it
in detail. It also has logic for proving that _length and _data
don't alias if i >= 0. However, SCEV-AA is not enabled by default.
For unsigned types arithmetic is fine, but
we probably need "unsigned" flag in getelementptr to signal that
offset is treated as unsigned.
In fact, as Takumi pointed out, if you add an extra comparison to
ensure 2) SCEV can already optimize the loop.
Or am I missing something?
With that extra comparison, SCEV-AA succeeds in proving that
i >=0, and this shows it can do everything else from there.
Dan