LLVM 2.4 problem? (resend)

[Mike_Stump1]

[...]

Objects are defined like so:

Two pointers of
the same type compare equal if and only if they are both null,
both
point to the same object or function, or both point one past the
end
of the same array.

This means they _must_ compare !=, if they are different objects.

Aha! Thanks for quoting that: It's from an expired standard (1998,
presumably). The 2003 standard has changed the words for that, taking
away the property under discussion (for a different reason -- see Core
Issue 73).

A distinction without a difference. They are trying to word smith this to get it right, however, the underlying semantics are trivial and not in dispute. The part you seem to be missing is kinda fundamental, unless there is linkage, there is no linkage. What linkage means is exactly the notion of if two entities refer to the same object or not, or to put it another way, if two entities have the same address. Pointing off the end of an array doesn't necessarily yield a pointer to an object. It represents a value that can be manipulated to refer to an object, say, with p-1.

I can quote n2461 if you prefer:

Two pointers of the same type compare equal if and only if they are both
null, both point to the same function, or both represent the same address (3.9.2).

A valid value of an object pointer type represents either the address of a byte in memory (1.7) or a null pointer (4.10). If an object of type T is located at an address A, a pointer of type cv T* whose value is the address A is said to point to that object, regardless of how the value was obtained.

Static and automatic storage durations are associated with objects introduced by declarations (3.1) and implicitly cre-
ated by the implementation (12.2).

A declaration (clause 7) introduces names into a translation unit or redeclares names introduced by previous declarations.

An object is a region of storage.

An object is created by a definition (_basic.def_)

Each declaration _creates_ an object. The word create means that each has a region of bytes, distinct from all others.

The changes to address Core issue 73 invalidates your reasoning

No, they don't. I'm describing a fundamental feature of C and C++ that cannot be disputed. The most that can be done is to add a rule that says objects declared with a const type can be merged, meaning that objects with the same value may (implementation defined or unspecified) refer to the address of one of them. A rule like this could be added to C or C++, but has not been to the best of my knowledge.

[David_Vandevoorde1]

[...]

Objects are defined like so:

Two pointers of
the same type compare equal if and only if they are both null,
both
point to the same object or function, or both point one past the
end
of the same array.

This means they _must_ compare !=, if they are different objects.

Aha! Thanks for quoting that: It's from an expired standard (1998,
presumably). The 2003 standard has changed the words for that, taking
away the property under discussion (for a different reason -- see Core
Issue 73).

A distinction without a difference. They are trying to word smith
this to get it right, however, the underlying semantics are trivial
and not in dispute.

On the contrary: Active CWG members disagree on this topic.

The part you seem to be missing is kinda
fundamental, unless there is linkage, there is no linkage. What
linkage means is exactly the notion of if two entities refer to the
same object or not, or to put it another way, if two entities have the
same address.

You're mixing your terms: Linkage is a property of names and types; not entities (and not objects). Furthermore, linkage deals with cross-scope (mostly, cross-TU) correspondences. The question here can arise within a scope.

Pointing off the end of an array doesn't necessarily
yield a pointer to an object. It represents a value that can be
manipulated to refer to an object, say, with p-1.

I can quote n2461 if you prefer:

Two pointers of the same type compare equal if and only if they are both
null, both point to the same function, or both represent the same
address (3.9.2).

A valid value of an object pointer type represents either the address
of a byte in memory (1.7) or a null pointer (4.10). If an object of
type T is located at an address A, a pointer of type cv T* whose value
is the address A is said to point to that object, regardless of how
the value was obtained.

Static and automatic storage durations are associated with objects
introduced by declarations (3.1) and implicitly cre-
ated by the implementation (12.2).

A declaration (clause 7) introduces names into a translation unit or
redeclares names introduced by previous declarations.

An object is a region of storage.

An object is created by a definition (_basic.def_)

basic.def doesn't contain the word "create" nor words to that effect, AFAICT. Furthermore, basic.life 3.8/7 makes it clear that an object may be created on top of another object, and the name of the first object will correctly evaluate to the new object.

So that reasoning doesn't hold.

Each declaration _creates_ an object. The word create means that each
has a region of bytes, distinct from all others.

No.

The changes to address Core issue 73 invalidates your reasoning

No, they don't. I'm describing a fundamental feature of C and C++
that cannot be disputed.

It sure can. In fact it _is_ being disputed.

The most that can be done is to add a rule
that says objects declared with a const type can be merged, meaning
that objects with the same value may (implementation defined or
unspecified) refer to the address of one of them. A rule like this
could be added to C or C++, but has not been to the best of my
knowledge.

The current consensus among CoreWG experts is that the words in the current standard (and those in the current WP) do not require distinct variables and temporaries to have distinct addresses per se. (In most cases, distinct addresses are the only possible implementation, but even without const qualification there are cases that could be implemented with overlapping storage within the standard's words. E.g., if variables are address-exposed but never value-exposed.)

There is currently _no_ CoreWG consensus about whether that situation is intended and/or desirable. The resolution of that is what the new core issue is about.

(I'm not sure what sort of guidance this provides for LLVM behavior.)

  Daveed

[Eli_Friedman1]

I do think however that it's bit dangerous to combine static constants
across compilation units.

GCC does the same things with strings in some cases. You shouldn't
depend on this behavior if you want portable code.

Combining is explicitly allowed for strings in C: 6.5.2.5p8: "String
literals, and compound literals with const-qualified types, need not
designate distinct objects." This isn't allowed for distinct
declarations.

6.5.9p6: "Two pointers compare equal if and only if both are null
pointers, both are pointers to the same object (including a pointer to
an object and a subobject at its beginning) or function, both are
pointers to one past the last element of the same array object, or one
is a pointer to one past the end of one array object and the other is
a pointer to the start of a different array object that happens to
immediately follow the first array object in the address space."

6.2.4: "An object exists, has a constant address, and retains its
last-stored value throughout its lifetime."

6.7: "A definition of an identifier is a declaration for that
identifier that: — for an object, causes storage to be reserved for
that object;"

There isn't any other reasonable interpretation of the standard.

Also, the only semantics that "const" has in C is that writing to an
object with a const-qualified type is illegal.

If you avoid
marking the global variable const, you should have better luck.

Not marking the variable const only makes the problem more obscure.
Testcase in C:

static char x = 1, y = 1;int c() {char* u = &x; char* v = &y; return u
== v;} int d() {return x+y;}

Running this through "llvm-gcc -O0 -emit-llvm -c -x c - -o - | opt
-mem2reg -globalopt -constmerge -instcombine" has precisely the same
effect: c returns 1.

It's conceivable that globalopt+constmerge could do even crazier
stuff. Potential example: suppose we have two mallocs, and store the
allocated pointers into globals. GlobalOpt knows how to turn mallocs
into statically allocated globals. Then suppose there's exactly one
store to each of these mallocs: GlobalOpt knows how to turn these into
constant globals. Then, ConstMerge or the AsmPrinter will actually
merge them, so the computed address ends up being the same.
Therefore, we conclude that malloc(1) == malloc(1) can be true in some
situations! Now, this doesn't actually work because malloc
elimination transformation isn't quite aggressive enough, but making
this work wouldn't require any controversial changes.

This bug actually manifests itself in two places: one is
ConstantMerge, the other is the AsmPrinter. It's non-trivial to fix
because it's really a design bug: we assume that constant==mergeable,
which simply isn't true. There are a few different ways of fixing
this; however, I think the only real option is to add a new
"mergeable" linkage type.

-Eli

[Eli_Friedman1]

> An object is created by a definition (_basic.def_)

basic.def doesn't contain the word "create" nor words to that effect

That should be [intro.object]: "An object is a region of storage. An
object is created by a definition..."

Furthermore, basic.life 3.8/7 makes it clear that an object
may be created on top of another object, and the name of the first
object will correctly evaluate to the new object.

That's irrelevant; for the case with two global chars, both of the
objects are alive at the time in question per [basic.stc.static].
Anyway, I'm 99% sure that's supposed to be referring to user-allocated
memory; the lifetime of an non-user-allocated object is permanently
attached to its scope, so it's already gone before anything could be
allocated on top of it.

The current consensus among CoreWG experts is that the words in the

current standard (and those in the current WP) do not require distinct
variables and temporaries to have distinct addresses per se.

Then what's the alternative model?

-Eli

[Eli_Friedman1]

Ouch, this could be seriously dangerous: following impossible
codepaths can cause very subtle bugs.

-Eli

[Chris_Lattner]

Eli, I don't disagree with you on any specific detail here. I think there are decent solutions to this if anyone cares enough. My only point is that this is an existing problem with other compilers. On darwin, for example, x and y can get the same address, because x and y end up in the 'cstring' section which is coalesced by the linker:

static const char x[] = "foo";
static const char y[] = "foo";
void *X() { return x; }
void *Y() { return y; }

This is clearly invalid, and a well known problem. I agree that neither LLVM nor GCC should not do this, however, noone has cared enough to fix it yet. If anyone cares enough to do so, I'm happy to help discuss various design points: I don't think this is very difficult.

-Chris

[Mike_Stump1]

A distinction without a difference. They are trying to word smith
this to get it right, however, the underlying semantics are trivial
and not in dispute.

On the contrary: Active CWG members disagree on this topic.

My claim would be that the people that wrote the standard knew exactly what it meant in this area. We spent quite a bit of time discussing it.

The part you seem to be missing is kinda
fundamental, unless there is linkage, there is no linkage. What
linkage means is exactly the notion of if two entities refer to the
same object or not, or to put it another way, if two entities have the
same address.

You're mixing your terms: Linkage is a property of names and types;

Yeah, I should have said:

The part you seem to be missing is kinda
fundamental, unless there is linkage, there is no linkage. What
linkage means is exactly the notion of if two names denote the
same object or not, or to put it another way, if two names have the
same address.

but notice, this does change anything unless you want to just argue about my choice of words and not the meat of the topic. Anyway, no, linkage doesn't have to do with types, just names, for example, names of types. Anyway, yes, one cannot hope to understand what a name denotes, without understanding things like linkage. And no, it isn't a mixup:

5 Every name that denotes an entity is introduced by a declaration.

and:

8 An identifier used in more than one translation unit can potentially
   refer to the same entity in these translation units depending on the
   linkage (_basic.link_) of the identifier specified in each translation
   unit.

not entities (and not objects).

By answering the question, do these two names have linkage, we answer the question, do these names refer to the same entity more generally, or in the case at hand, do these names refer to the same object.

Furthermore, linkage deals with cross-scope (mostly, cross-TU) correspondences. The question here can arise
within a scope.

That answer in our case is no, they cannot. You have been shown the wording of the standard that states this. You have not cited anything that contradicts this. You can't win on the:

We do think that a strict reading of the standard allows the optimization

statement without actually having a reason for that view that is backed by the standard. I've not seen that backing.
   I'm trying to change your mind. I'm plan on doing this by identifying the part were we diverge in our reading of the standard. I can't find that point, if you are unwilling to cite it. Given that point, I can then help you understand why your reading is wrong, or, if it isn't, then I can then adopt your view point.

Pointing off the end of an array doesn't necessarily
yield a pointer to an object. It represents a value that can be
manipulated to refer to an object, say, with p-1.

I can quote n2461 if you prefer:

Two pointers of the same type compare equal if and only if they are
both
null, both point to the same function, or both represent the same
address (3.9.2).

A valid value of an object pointer type represents either the address
of a byte in memory (1.7) or a null pointer (4.10). If an object of
type T is located at an address A, a pointer of type cv T* whose value
is the address A is said to point to that object, regardless of how
the value was obtained.

Static and automatic storage durations are associated with objects
introduced by declarations (3.1) and implicitly cre-
ated by the implementation (12.2).

A declaration (clause 7) introduces names into a translation unit or
redeclares names introduced by previous declarations.

An object is a region of storage.

An object is created by a definition (_basic.def_)

basic.def doesn't contain the word "create" nor words to that effect,

You must not have searched the standard for those quotes, as they are easily findable. See 1.8p1 in n2461 for this one.

AFAICT. Furthermore, basic.life 3.8/7 makes it clear that an object
may be created on top of another object, and the name of the first
object will correctly evaluate to the new object.

Yes, this, just in case you don't know why it is there, is because of things like placement new, and things like declaring:

char buf[10000], and then allocating objects out of it and using them. This isn't possible in the confines of the standard, without all the various special case wording that defines exactly what it means.

It is irrelevant to the question at hand. The storage for the objects at hand are guided by:

All objects which neither have dynamic storage duration nor are local have static storage duration. The storage for these
objects shall last for the duration of the program (3.6.2, 3.6.3).

By last, we mean, is allocated and not reused by the compiler or runtime system. Only after the program ends, does the standard allow for the storage to be remained or reused.

So that reasoning doesn't hold.

Try that again. To speed the process, identify where we depart in our reading of the standard. If you just got lost, because you didn't realize that objects are created by definitions, well, that's easy to correct.

Each declaration _creates_ an object. The word create means that each
has a region of bytes, distinct from all others.

No.

Great, a one word reply. Sorry, that doesn't cut it in my book. To win, you have to state what your interpretation is. If your contention is that:

int i;
int j;

i = 1;
j = 2;

printf("%d", i);

can print 2 within the confines of the standard, then I can quickly dismiss you as a quack and we can end the thread. The problem is, I can't tell what your position is. I'm reasonably certain that your position can't be that the above could print 2, and yet, without the understanding that with the declaration of i and j above that this creates an object for each, and that this means that each has a different address, I'm left with you having no possible sane view of the standard. Once you admit that the above _must_ print 1, then all the reasoning you used to figure that out also applies to:

static int i = 1;
static int j = 2;

and likewise to

static const int i = 1;
static const int j = 1;

The only exception, would be some sentence that talked specifically about this case and granted the implementation the latitude to merge them. You've not cited that.

The changes to address Core issue 73 invalidates your reasoning

No, they don't. I'm describing a fundamental feature of C and C++
that cannot be disputed.

It sure can. In fact it _is_ being disputed.

No. It cannot be. You will discover that the standard isn't useful at all if there if there is a dispute, and that means, that the person trying to suggest the standard isn't useful at all, is wrong. We ignore these types of people as lunatics. I'd suspect they are merely talking about changing the standard to permit merging.

The most that can be done is to add a rule
that says objects declared with a const type can be merged, meaning
that objects with the same value may (implementation defined or
unspecified) refer to the address of one of them. A rule like this
could be added to C or C++, but has not been to the best of my
knowledge.

The current consensus among CoreWG experts is that the words in the
current standard (and those in the current WP) do not require distinct
variables

They are wrong. I'm sorry to hear it. It would be a misreading of the standard to think it is not required. I can concede that the wording could be improved.

When things don't have to be distinct we explicitly spelled it out:

   It is unspecified whether such a variable has an address distinct from that of any other object in the program.

to countermand the mandate that would otherwise exist. If that weren't the case, we would have removed the wording as redundant. You can also see evidence of our thinking in wording like:

   --in each definition of D, corresponding names, looked up according to
     _basic.lookup_, shall refer to an entity defined within the defini-
     tion of D, or shall refer to the same entity, after overload resolu-
     tion (_over.match_) and after matching of partial template special-
     ization (_temp.over_), except that a name can refer to a const
     object with internal or no linkage if the object has the same inte-
     gral or enumeration type in all definitions of D, and the object is
     initialized with a constant expression (_expr.const_), and the value
     (but not the address) of the object is used, and the object has the
     same value in all definitions of D; and

as well. Here, because the values are the same, we allow them in an ODR sense. We knew that the address had to be distinct, and so, we don't permit the use of the address.

and temporaries to have distinct addresses per se. (In most
cases, distinct addresses are the only possible implementation, but
even without const qualification there are cases that could be
implemented with overlapping storage within the standard's words.
E.g., if variables are address-exposed but never value-exposed.)

Curiously enough, it is the address-exposed cases that give rise to the requirement they be distinct. If the address isn't exposed, and one can't otherwise tell, then they can be merged. Consuming the address is but one way a person is able to notice that they were merged, and if they can notice it, then the implementation is not able to use the as-if rule.

There is currently _no_ CoreWG consensus about whether that situation is intended and/or desirable.

I can go set them straight, if I thought they were at all in any danger of getting it wrong. They won't. If they want to make things mergable, that would be a change, but a small one. If they did that, you'd notice that they would change the wording to permit merging in the narrow case and to spell out the fact that in all other cases, the objects are distinct, don't overlap and cannot be merged.

[Mike_Stump1]

Actually, we do this on purpose. It is a huge win for us and we don't want to not do this, even if that means not exactly conforming to the standard.

Essentially, we wish the standard had chosen otherwise. gcc handles this choice like this:

@item -fmerge-all-constants
Attempt to merge identical constants and identical variables.

This option implies @option{-fmerge-constants}. In addition to
@option{-fmerge-constants} this considers e.g.@: even constant initialized
arrays or initialized constant variables with integral or floating point
types. Languages like C or C++ require each non-automatic variable to
have distinct location, so using this option will result in non-conforming
behavior.

In reality, we should handle this by setting flag_merge_constants = 2 in darwin.c, and documenting it. All code that does merging should be testing flag_merge_constants and respecting it. People that don't want merging are then free to turn it off. It is this experience that gives rise to the idea that changing the standard to merge would not be a bad idea. If they did this, then we wouldn't even need the flag, well, wouldn't need it except for legacy code. Internally, one would still want it to support previous language standards.

[Eli_Friedman1]

Hmm... so the issue is that it's good for codesize to merge objects
with static duration that are marked in the source as const in
C/ObjC/C++, even when we can't prove it's correct? That sounds
generally reasonable, although it would be mildly surprising for
anyone coding according to the standard.

It doesn't really change the issue, though; we want the merging to be
a front-end option, and we still need a solution which handles
variables that gets marked by the optimizer.

-Eli

[David_Vandevoorde1]

[...]

The current consensus among CoreWG experts is that the words in the

current standard (and those in the current WP) do not require distinct
variables and temporaries to have distinct addresses per se.

Then what's the alternative model?

That if two complete objects can never be distinguished by observing their value, then they may be allocated at the same address.

Note that I don't think that model will have majority support when the issue is discussed (that's just a guess). However, the current words don't seem to make it an invalid model, and there is some suspicion that the changes for Core issue 73 that made it so were not entirely accidental.

  Daveed

[Mike_Stump1]

Hmm... so the issue is that it's good for codesize to merge objects
with static duration that are marked in the source as const in
C/ObjC/C++, even when we can't prove it's correct?

Yes.

That sounds generally reasonable, although it would be mildly surprising for anyone coding according to the standard.

Apparently no. In practice, I've seen one bug report for it in 5 years.

It doesn't really change the issue, though; we want the merging to be
a front-end option, and we still need a solution which handles
variables that gets marked by the optimizer.

I think so. If we could get C/C++ to just bless merging and then just support that and ignore legacy standards and legacy code, we might be able to leave it as is.

[Eli_Friedman1]

The only allowance I can think of that's general enough to allow
everything LLVM knows how to do at the moment is "the result of an
equality comparison between two pointers to objects with distinct base
objects is undefined". (See
http://lists.cs.uiuc.edu/pipermail/llvmdev/2008-October/017769.html
and http://lists.cs.uiuc.edu/pipermail/llvmdev/2008-October/017747.html
for the examples I'm thinking of.) I strongly doubt we can get away
with that.

Here's a more concrete version of the solution I'm proposing: we add a
new optional marking to constant globals, say "mergeable". There are
two reasonable semantics: one is that the result of equality
comparisons of a pointer into this global with a pointer into any
other similarly marked global is undefined. This is actually slightly
more aggressive than what the current standard seems to allow even for
string constants, but it seems reasonable. The more conservative
definition of the semantics is just to say that the compiler chooses
whether any pair of mergeable globals are distinct objects, which is
roughly how the current C99 standard defines string merging.

This has the following effects on current optimizers: constmerge only
merges globals marked mergeable. Only mergeable constants are emitted
into mergeable sections in assembly. If we use the conservative
definition of mergeable, fix any code that assumes distinct globals
don't get merged, like the code that folds equality comparisons
between distinct globals to false. Optionally, add a new optimization
step which marks constants as mergable when their address isn't taken.

-Eli

[Mike_Stump1]

I strongly doubt we can get away with that.

Yeah, we agree on that one. I was just thinking about the const case.

Here's a more concrete version of the solution I'm proposing: we add a
new optional marking to constant globals, say "mergeable". There are
two reasonable semantics: one is that the result of equality
comparisons of a pointer into this global with a pointer into any
other similarly marked global is undefined.

undefined means the code is free to rm -rf /, is this what you meant? I'm against that.

The usual wording is sufficient:

   It is unspecified whether such a variable has an address distinct from that of any other object in the program

to reuse the concept and words from 8.4p8 (n2461). This isn't quite right, but we know what is meant by it. The implementation is free to merge it with any other mergable object.

This has the following effects on current optimizers: constmerge only
merges globals marked mergeable. Only mergeable constants are emitted
into mergeable sections in assembly. If we use the conservative
definition of mergeable, fix any code that assumes distinct globals
don't get merged, like the code that folds equality comparisons
between distinct globals to false. Optionally, add a new optimization
step which marks constants as mergable when their address isn't taken.

Sounds like a plan.

[Eli_Friedman1]

That's an extremely difficult model to deal with, even ignoring that
it might break user code. It isn't too difficult to write a program
where two complete objects can be distinguished by observing their
value if and only if they are allocated at the same address.

-Eli

[Eli_Friedman1]

Okay... works, but there are some strange edge cases; take the
following program:
static const int a = 0, b = &a == &b;
(a and b get used later, including their addresses)

In C mode, the front-end must evaluate &a == &b because complex
expressions in initializers generally can't be trusted to the backend.
However, once it evaluates this, it can't mark either a or b
mergeable; if it did, it would introduce a logical inconsistency with
other code that compared the addresses of a and b.

-Eli

[Tatu_Vaajalahti]

Just to clarify this from the compiler user (me!) perspective:

llvm-gcc with optimizations higher than -O1 has (effectively) -fmerge-all-constants enabled and currently there is no way to disable this behavior.

Is that correct? I think it's just something to be aware of.

[David_Vandevoorde1]

Agreed. Hopefully, the working paper will make that clear relatively soon (unfortunately, the CD balloting period is about to start; that may introduce delays on certain work items).

  Daveed