Graphics Reference
In-Depth Information
Aliasing presents quite a problem for C/C++ compilers. When compilers are unable
to deduce that two pointers cannot alias each other, they must conservatively assume
aliasing is present. This assumption can impede certain optimizations, leaving code
with unnecessary load and store instructions that bloat both code and slots in function
stack frames, thus indirectly impacting on code and data cache efficiency. These loads
and stores also hinder instruction reordering and loop unrolling, causing instruction
stalling.
In contrast, a language such as FORTRAN 77 specifies that no two identifiers
will be considered as aliasing each other unless they are declared as such in an
EQUIVALENCE
declaration. It therefore does not suffer from this aliasing problem at
all. To illustrate the problem, consider the following code for transforming a point by
a3
×
3 matrix.
void TransformPoint(Point *pOut, Matrix &m, Point &in)
{
pOut-
>
x = m[0][0] * in.x + m[0][1] * in.y + m[0][2] * in.z;
pOut-
>
y = m[1][0] * in.x + m[1][1] * in.y + m[1][2] * in.z;
pOut-
>
z = m[2][0] * in.x + m[2][1] * in.y + m[2][2] * in.z;
}
The compiler has no higher-level knowledge of the intended function of the code.
It therefore does not know that the programmer must have intended for
pOut
and
in
not to alias each other (or the code would not correctly be implementing a transfor-
mation, in that
pOut
is written to before
in
is fully used). As such, the compiler must
assume
pOut
and
in
might reference the same structure.
Faced with the previous code, most compilers generate code that loads
in.x
,
in.y
,
and
in.z
three times each, for a total of nine times. A really clever compiler using
type-based alias analysis (as discussed later) would know that
pOut-
>
x
could only
alias
in.x
and
pOut-
>
y
only
in.y
, and therefore only have to perform two reloads,
for a total of five loads. Ideally though, the fields of
in
should be loaded once each.
In general, unless the compiler can prove that aliasing is not possible, it must
assume it is present. Unfortunately, proving that aliasing is not taking place is difficult.
For the compiler to assume aliasing is present when in fact it is not is bad. It causes
variables to be fetched from memory when they are already present in a register, or
stored to memory when holding the value in a register would have sufficed. Worse,
failure to remove an unnecessary store can have a cascading effect. It may make it
seem like other aliasing is present, thereby stopping the compiler from removing
unnecessary memory accesses, which in turn can stop it from removing other ones,
and so on.
It should be pointed out that declaring the input variables as
const
is not a solution
to the aliasing problem. For example, declaring
m
as
const Matrix &m
just says that
the memory area occupied by
m
is constant with respect to accesses through
m
, not
that the memory area is constant in general. Thus, the memory area could still be
