Hi all,
consider the following input:
int y;
void foo(int * restrict x)
{
if (x == &y)
(*x)++;
(*x)++;
}
The clang codegen gives the argument of foo the noalias attribute and
GVN will optimise the condition to false.
When discussing this on IRC, Chandler suggested that Clang shouldn't be
creating the noalias attribute here, i.e. do alias interference. I'm not
sure he is correct, but this is subtle enough to warrant some discussion
before filling a PR.
Joerg
Sorry, I was wrong. On further consideration, I think Clang is correct here.
1) (*x) is an lvalue based on the pointer 'x' and is modified in the
function, so the restrict qualifier actually governs the set of addresses
viable...
2) The expression 'y' is an lvalue expression AFAICT in the C99 standard,
is not based on the pointer 'x', and thus cannot access the same object
which x points to.
Thus, clang is correct to optimize the condition to false I think...
As Joerg pointed out in IRC, 'y' is an lvalue, but we do not use it to
access the object it designates, we only use it to compute the address, and
thus restrict should have no bearing on it. That would in turn make Clang's
optimization incorrect and also seems likely to make 'noalias' essentially
useless for modeling restrict. =/
From: "Chandler Carruth" <chandlerc@google.com>
To: "clang-dev Developers" <cfe-dev@cs.uiuc.edu>
Sent: Tuesday, December 11, 2012 5:17:43 AM
Subject: Re: [cfe-dev] no-alias generated as result of restrict function argumentsHi all,
consider the following input:int y;
void foo(int * restrict x)
{
if (x == &y)
(*x)++;
(*x)++;
}The clang codegen gives the argument of foo the noalias attribute and
GVN will optimise the condition to false.When discussing this on IRC, Chandler suggested that Clang shouldn't
be
creating the noalias attribute here, i.e. do alias interference. I'm
not
sure he is correct, but this is subtle enough to warrant some
discussion
before filling a PR.Sorry, I was wrong. On further consideration, I think Clang is
correct here.1) (*x) is an lvalue based on the pointer 'x' and is modified in the
function, so the restrict qualifier actually governs the set of
addresses viable...
2) The expression 'y' is an lvalue expression AFAICT in the C99
standard, is not based on the pointer 'x', and thus cannot access
the same object which x points to.Thus, clang is correct to optimize the condition to false I think...
As Joerg pointed out in IRC, 'y' is an lvalue, but we do not use it
to access the object it designates, we only use it to compute the
address, and thus restrict should have no bearing on it. That would
in turn make Clang's optimization incorrect and also seems likely to
make 'noalias' essentially useless for modeling restrict. =/
Does it really make it useless, or can we just not use it for computing icmp results on pointer values?
-Hal
This. I'm not sure why we're using noalias to optimize icmps in the
first place; we don't generally optimize icmps based on alias analysis
results, and the rules in LangRef don't appear to allow it.
-Eli
Looking a bit deeper, the issue is ultimately that isIdentifiedObject is
true if NoAlias is specified for the argument. There is a comment at the
beginning of AliasAnalysis.h that NoAlias doesn't imply inequal
pointers.
One of the uses in BasicAliasAnalysis.cpp seems also questionable
("Constant pointers can't alias with non-const isIdentifiedObject objects")
in this light. What does constant pointer in this context mean? Is that
assumption violated if I explicitly cast away const and pass the result
to a function with NoAlias argument?
I think the required changes for correctness of C restrict would be:
Two identified objects do not alias, if they are both NoAlias arguments
or both are not NoAlias arguments. If one of the identified objects is a
NoAlias argument and the context in question considers the referenced
object, they don't alias. For the purpose of pointer comparision, they
are may be equal.
Joerg
As Joerg pointed out in IRC, 'y' is an lvalue, but we do not use it to
access the object it designates, we only use it to compute the address, and
thus restrict should have no bearing on it. That would in turn make Clang's
optimization incorrect and also seems likely to make 'noalias' essentially
useless for modeling restrict. =/Looking a bit deeper, the issue is ultimately that isIdentifiedObject is
true if NoAlias is specified for the argument. There is a comment at the
beginning of AliasAnalysis.h that NoAlias doesn't imply inequal
pointers.One of the uses in BasicAliasAnalysis.cpp seems also questionable
("Constant pointers can't alias with non-const isIdentifiedObject objects")
in this light. What does constant pointer in this context mean?
It means the pointer value itself satisfies isa<Constant>.
Is that
assumption violated if I explicitly cast away const and pass the result
to a function with NoAlias argument?
Not immediately, no. It means that you can't access the constant
pointer's pointee directly within the noalias argument's scope. Access
to that object must go through the noalias argument.
Restrict on a pointer loosely means "All accesses to my pointee(s) in
my scope must go through me". It doesn't mean "I'm the only pointer
value in the program which points to my pointee(s)"; in fact, that
would be an unusable definition. Consequently, pointers that aren't
used to access objects aren't constrained by restrict rules.
Dan
The original issue is that clang maps restrict on function arguments to
NoAlias and that makes compares against the address of global variables
false. Minimal test case:
@y = external global i32
define zeroext i1 @t(i32* noalias %x) nounwind uwtable readnone {
entry:
%cmp = icmp eq i32* %x, @y
ret i1 %cmp
}
Joerg
The bug here isn't in clang's use of noalias or in BasicAliasAnalysis'
implementation of noalias; it's in the code that's optimizing the
icmp.
Dan
I am just saying that the comments in BasicAliasAnalysis makes me wonder
if it has the same kind of problem.
Joerg
And I am answering with an explanation of why the BasicAliasAnalysis
code in question does not have this same kind of problem. A NoAlias
response from AliasAnalysis isn't intended to imply inequality of
pointers, so there's no inherent problem with saying NoAlias for
pointers which can be equal. For the same reason, this is why using
AliasAnalysis information in instcombine/simplify to simplify pointer
comparisons is a bug.
Dan
+1
This is precisely one of the differences between pointer analysis and
alias analysis.
Let's come back to this. The attached patch decouples InstSimplify from
the alias analysis and provides the conservative logic for when pointers
are not equal. The only really problematic part would be InlineCost.cc,
since that could try to replace NoAlias/ByVal arguments with allocas in
the same function. For the moment, the inline cost estimation doesn't
use the SimplifyICmpInst interface and there are other parts that need
to be carefully validated before it can. It doesn't look too bad to add
an explicit argument whether interprocedural analysis is being done and
restrict the tests for that, but I am leaving this out as it is
currently unnecessary.
I am also not doing any simplification for NoAlias calls. Unlike alias
analysis, I can think of valid use cases for malloc/free/malloc
conditions where the results of the two mallocs is equal and correct
prediction of the result is desirable.
Joerg
icmp-ptr.diff (7.23 KB)
Let's take the version with the cleanup from IRC. *sigh* Dealing with
too many copies.
Joerg
icmp-ptr.diff (6.87 KB)
One of InstructionSimplify's strengths is that it is simple. Having
constraints where its users have to know which calls are safe in which
contexts would make it tricky. Having a flag you pass in to tell it
what kind of context you're calling it from would complicate it. And,
we've had numerous (on and off-list) emails just to understand the
problem to the extent that we do now, and I'm still not fully
convinced we understand it fully.
How important is this optimization? Do you have real-world code where
it matters?
Intuitively, it seems that the kind of pointer comparisons you're
aiming at would be uncommon. Code authors can avoid them for the same
reason that you think the compiler can eliminate them (except that a
code author typically doesn't have to worry about their own code being
pathological, while the optimizer does). I'm aware that code can often
look pretty surprising after macro expansion and inlining, but anyone
choosing to add restrict to their pointers is obliged to be fairly
careful about how such pointers are used.
Dan
How important is this optimization? Do you have real-world code where
it matters?
There are at least quite a few test cases that hit this optimisation.
My main concern here is getting correct code, which isn't true ATM.
I would expect list handling code and a number of other cases to be well
optimisable in this regard.
Intuitively, it seems that the kind of pointer comparisons you're
aiming at would be uncommon.
The NoAlias arguments are the least specific case, but most likely the
one case that is critical. I don't have a strong position on including
them.
Code authors can avoid them for the same
reason that you think the compiler can eliminate them (except that a
code author typically doesn't have to worry about their own code being
pathological, while the optimizer does). I'm aware that code can often
look pretty surprising after macro expansion and inlining, but anyone
choosing to add restrict to their pointers is obliged to be fairly
careful about how such pointers are used.
The only reason we are discussing this complications is because Inline
Cost Estimation might at some point in the future want to use this
infrastructure across function boundaries. Even then, the worst case
would be a bad cost estimate, so it might be acceptable.
Joerg