g++ and aliasing bools

[Daniel Berlin]

> 
> None the less, I'm happy to provide a sketch.  I will do the version
> without restrict (that was added later) and without the assignment of
> alias sets to structs (Kenner added that later), and without
> type-punning for unions (this is optional under ANSI/ISO C).
> 
> This is from memory; there might be minor mistakes.  Also note that
> the code has changed considerably from my original version, which
> makes it harder to see the structure.
> 
> 1. The C aliasing rules say that if you reference memory using one
>    type, you may not reference it using another types, unless:
> 
>    - The types are signed/unsigned variants of each other.
> 
>    - The types very only in their cv-qualification.
> 
>    - One of them is (possibly cv-qualified) "char"
The void * type, as well, because it says "A type compatible with the 
effective type of the object." and "   [#1] A pointer to void may be 
converted to or from a pointer
        to  any  incomplete  or  object  type.   A  pointer  to  any
        incomplete or object type may be converted to a  pointer  to
        void  and  back again; the result shall compare equal to the
        original pointer." and "  [#2] Conversion of an operand value  to  
a  compatible  type  causes no change to the value or the 
representation." and "[#2] For two pointer types to be compatible, both  
shall  be identically   qualified   and  both  shall  be  pointers  to 
compatible types."
Which seems to imply that the void * type can legally alias anything, 
because it's compatible with everything (though it only appears to have 
all the properties of compatible types, i can't find a specific phrase to 
support that it *is* a compatible type of everything )

Pro64 (I haven't looked at other compilers) seems to agree with me too:

*   C.1: (ANSI Rules)
*
*     An object shall have its stored value accessed only by an lvalue 
that
*     has one of the following types:
*     *) the declared type of the object,
*     *) a qualified version of the declared type of the object,
*     *) a type that is signed or unsigned type corresponding to the 
declared type
*        of the object,
*     *) a type that is signed or unsigned type corresponding to a
*        qualified version of the declared type of the object,
*     *) an aggregrate or union type that includes one of the 
aforementioned types
*        among its members (including, recursively, a member of a 
subaggregate
*        or contained union),
*     *) a character type, or
*     *) a void type.
*
^^^^^^^^^^^^^^^^^^^^^
*     Use the Ragnarok interpretation here.  Objects are aliased if
*     their base types (MTYPES), after stripping off the qualifiers and
*     signed-ness, are equal.  See ANSI C 3.3 and 3.2.2.3.
*
*   C.2: (C Qualifier Rule)
*
*     C.2.1: (restricted pointer)
*       If both memory operations are restricted pointer dereference,
*       they are not aliased if their based pointer are different.
*


> 
> 2. Alias sets have the following semantics:
> 
>    - Two things in the same alias set may alias one another.
> 
>    - Things in two distinct alias sets may alias if one is
>      a "subset" of another, under transitive closure.
> 
>    - All alias sets are a subset of a special alias set
>      called "alias set zero".  (An immediate consequence is
>      that something in alias set zero can alias everything.)
> 
> Let T be the set of all C types.  Let TA be a relation on TxT such
> that (t1, t2) \in TA if and only if t and u may alias.
> 
> Similarly, let S be the set of all alias sets.  Let SA be relation on
> SxS that (s1, s2) \in SA if and only if s1 and s2 may alias.  (Note
> that in the original incarnation, there were no subsets other than
> the fact that everything was a subset of alias set zero, so this
> relation is well-defined statically.)
> 
> What we wish to prove is that C's lang_get_alias_set assigns
> alias sets to type safely.  In particular, let f be
> c_get_alias_set, and then:
> 
> Then, we wish to show that, for all t, u \in T:
> 
>    (t, u) \in TA \implies f(t), f(u)) \in SA
> 
> (We do not need if and only if for correctness.)
> 
> The proof is by induction.  All aggregate types are mapped
> to alias set zero which aliases everything; therefore, we
> need only consider non-aggregate types.  The code says:
> 
>   if (TREE_CODE (t) == INTEGER_TYPE && TREE_UNSIGNED (t))
>     {
>       tree t1 = signed_type (t);
> 
>       return get_alias_set (t1);
>     }
> 
> Therefore, signed and unsigned variants of types get the same alias
> set.
> 
> The code says:
> 
>   t = TYPE_MAIN_VARIANT (t);
>   if (TYPE_P (t) && TYPE_ALIAS_SET_KNOWN_P (t))
>     return TYPE_ALIAS_SET (t);
> 
> Therefore, if a cv-qualified type and its unqualified variant will
> get the same alias set.  By transitivity, so will all cv-qualified
> variants of the type.
> 
> The code says that:
> 
>   /* If this is a char *, the ANSI C standard says it can alias
>      anything.  Note that all references need do this.  */
>   if (TREE_CODE_CLASS (TREE_CODE (t)) == 'r'
>       && TREE_CODE (TREE_TYPE (t)) == INTEGER_TYPE
>       && TYPE_PRECISION (TREE_TYPE (t)) == TYPE_PRECISION (char_type_node))
>     return 0;
> 
> Therefore, "char" is mapped to alias set zero, completing the proof.

What about void * types, we never seem to handle that specifically?



> 
> --
> Mark Mitchell                   mark@codesourcery.com
> CodeSourcery, LLC               http://www.codesourcery.com
>