On 26/10/11 12:19, Richard Guenther wrote:
> On Tue, Oct 25, 2011 at 2:22 PM, Tom de Vries <[email protected]> wrote:
>> On 09/24/2011 01:42 PM, Richard Guenther wrote:
>>> On Sat, Sep 24, 2011 at 11:40 AM, Jakub Jelinek <[email protected]> wrote:
>>>> On Sat, Sep 24, 2011 at 11:31:25AM +0200, Richard Guenther wrote:
>>>>> In the end I'd probably say the patch is ok without the option (thus
>>>>> turned on by default), but if LC_GLOBAL_LOCALE is part of the
>>>>> glibc ABI then we clearly can't do this.
>>>>
>>>> Yes, LC_GLOBAL_LOCALE is part of glibc ABI. I guess we could only assume
>>>> the alignment if the pointer is actually dereferenced on the statement
>>>> that checks the ABI or in some stmt that dominates the spot where you want
>>>> to check the alignment. It is IMHO quite common to pass arbitrary values
>>>> in pointer types, then cast them back or just compare.
>>>
>>> Yeah (even if technically invoking undefined behavior in C). Checking if
>>> there is a dereference post-dominating function entry with sth like
>>>
>>> FOR_EACH_IMM_USE_STMT (... ptr ...)
>>> if (stmt_post_dominates_entry && contains derefrence of ptr)
>>> alignment = TYPE_ALIGN (...);
>>>
>>> and otherwise not assuming anything about parameter alignment might work.
>>> Be careful to check the alignment of the dereference though,
>>>
>>> typedef int int_unaligned __attribute__((aligned(1)));
>>> int foo (int *p)
>>> {
>>> int_unaligned *q = p;
>>> return *q;
>>> }
>>>
>>> will be MEM[p] but with (well, hopefully ;)) TYPE_ALIGN of TREE_TYPE
>>> (MEM[p])
>>> being 1. And yes, you'd have to look into handled-components as well. I
>>> guess
>>> you'll face similar problems as we do with tree-sra.c
>>> tree_non_mode_aligned_mem_p
>>> (you need to assume eventually misaligned accesses the same way expansion
>>> does for the dereference, otherwise you'll run into issues on
>>> strict-align targets).
>>>
>>> As that de-refrence thing doesn't really fit the CCP propagation you
>>> won't be able
>>> to handle
>>>
>>> int foo (int *p)
>>> {
>>> int *q = (char *)p + 3;
>>> return *q;
>>> }
>>>
>>> and assume q is aligned (and p is misaligned by 1).
>>>
>>> That is, if the definition of a pointer is post-dominated by a derefrence
>>> we could assume proper alignment for that pointer (as opposed to just
>>> special-casing its default definition). Would be certainly interesting to
>>> see what kind of fallout we would get from that ;)
>>>
>>
>> I gave this a try in deduce_alignment_from_dereferences.
>>
>> The fall-out I got from this were unaligned dereferenced pointers in
>> gcc.c-torture/unsorted/*{cmp,set}.c.
>>
>> Bootstrapped and reg-tested on x86_64. Build and reg-tested on MIPS and ARM.
>>
>> Ok for trunk?
>
> Can you not do the get_value_from_alignment split (it doesn't look
> necessary to me) and drop the
>
> @@ -541,10 +550,18 @@ get_value_for_expr (tree expr, bool for_
> if (TREE_CODE (expr) == SSA_NAME)
> {
> val = *get_value (expr);
> - if (for_bits_p
> - && val.lattice_val == CONSTANT
> + if (!for_bits_p)
> + return val;
> +
> + if (val.lattice_val == CONSTANT
> && TREE_CODE (val.value) == ADDR_EXPR)
> val = get_value_from_alignment (val.value);
> + else if (val.lattice_val == VARYING
> + && SSA_NAME_PTR_INFO (expr) != NULL
> + && SSA_NAME_PTR_INFO (expr)->align > 1
> + && SSA_NAME_PTR_INFO (expr)->misalign == 0)
> + val = get_align_value (SSA_NAME_PTR_INFO (expr)->align *
> BITS_PER_UNIT,
> + TREE_TYPE (expr), 0);
> }
>
> hunk? I'm not sure why it is necessary at all - CCP is the only pass
> computing alignment, so it should simply re-compute the info?
>
> Anyway, it looks unrelated to the purpose of the patch in general.
>
I dropped the code in get_value_for_expr, but kept the factoring of
get_align_value out of get_value_from_alignment . This remains necessary in the
new patch since get_align_value is still called from 2 sites:
get_value_from_alignment and deduce_alignment_from_dereference.
> The error reporting in deduce_alignment_from_dereferences is bogus,
> the programs are undefined only at runtime, so you can at most
> issue a warning.
>
Introduced -Wunaligned-pointer-deref.
> + /* Needs to be the successor of entry, for CDI_POST_DOMINATORS. */
> + entry = single_succ (ENTRY_BLOCK_PTR);
> +
> + FOR_EACH_BB (bb)
> + {
> + gimple_stmt_iterator i;
> +
> + if (!dominated_by_p (CDI_POST_DOMINATORS, entry, bb))
> + continue;
>
> if you only consider post-dominators of the entry block then just walk
> them directly (first_dom_son / next_dom_son).
>
> + align = TYPE_ALIGN (TREE_TYPE (memref)) / BITS_PER_UNIT;
> + if (align == 1)
> + continue;
>
I integrated the walking of post-dominators into the bb walk in ccp_initialize.
> I think you want to match what expand thinks of the alignment of this
> memory reference, not just what TYPE_ALIGN says (and yes, that
> needs to be split out somehow, SRA would need this as well).
>
I'm now using get_object_or_type_alignment for MEM_REF.
> + while (TREE_CODE (ptr) == SSA_NAME)
> + {
> + pi = get_ptr_info (ptr);
> + if (pi->misalign != 0)
> + {
> + error ("misaligned pointer dereferenced");
> + break;
> + }
>
> simply looking at pi->misalign is wrong. pi->align may be bigger
> than the align that you computed above, so pi->misalign % align != 0
> would be the right check.
>
This is my slightly more complex misalign check now:
...
+ if ((pi->align < align && misalign % pi->align != pi->misalign)
+ || (pi->align >= align && pi->misalign % align != misalign))
...
> + if (pi->align >= align)
> + break;
> + pi->align = align;
>
> and then set pi->misalign to zero here.
The patch no longer sets pointer info directly, as per your next comment. The
align/misalign is now stored in const_val:
...
+ val = get_align_value (align * BITS_PER_UNIT, TREE_TYPE (ptr),
+ misalign * BITS_PER_UNIT);
+ const_val[SSA_NAME_VERSION (ptr)] = val;
...
> But I would initialize the
> CCP lattice with this, not set SSA_NAME_PTR_INFO, from
> ccp_initialize, that already walks over all blocks and statements.
>
Done.
> + if (gimple_assign_rhs_code (def) == POINTER_PLUS_EXPR)
> + {
> + offset = gimple_assign_rhs2 (def);
> + if (!host_integerp (offset, 0)
> + || tree_low_cst (offset, 0) % align != 0)
> + break;
> +
> + ptr = gimple_assign_rhs1 (def);
>
> properly tracking explicit misalignment would be useful here, but I
> see you are posting a proof-of-concept?
The new patch attempts to keep track of explicit misalignment.
>
> /* Main entry point for SSA Conditional Constant Propagation. */
>
> static unsigned int
> do_ssa_ccp (void)
> {
> + calculate_dominance_info (CDI_POST_DOMINATORS);
> + deduce_alignment_from_dereferences ();
>
> you need to free post-dom info again.
>
Done.
Bootstrapped and reg-tested on x86_64, build and reg-tested on ARM.
Ok for next stage1?
Thanks,
- Tom
2011-12-08 Tom de Vries <[email protected]>
PR target/43814
* expr.c (get_object_or_type_alignment): Remove static.
* expr.h (get_object_or_type_alignment): Declare.
* common.opt (Wunaligned-pointer-deref): New option.
* tree-ssa-ccp.c (expr.h): Include.
(alignment_to_address_transition_p): New function.
(valid_lattice_transition): Allow transition from CONSTANT CONST_INT to
CONSTANT ADDR_EXPR.
(set_lattice_value): Likewise. Ignore transitions from CONSTANT to
UNDEFINED.
(get_align_value): New function, factored out of
get_value_from_alignment.
(get_value_from_alignment): Use get_align_value.
(deduce_alignment_from_dereference): New function.
(ccp_initialize): call deduce_alignment_from_dereference for statements
in block that are post-dominated by the entry block.
(do_ssa_ccp): Calculate and free post-dominance info.
* gcc.target/arm/pr43814-2.c: New test.
* gcc.dg/misalign.c: Same.
* gcc.dg/misalign2.c: Same.
* gcc.dg/analyze-deref.c: Same.
Index: gcc/tree-ssa-ccp.c
===================================================================
--- gcc/tree-ssa-ccp.c (revision 180521)
+++ gcc/tree-ssa-ccp.c (working copy)
@@ -134,6 +134,7 @@ along with GCC; see the file COPYING3.
#include "dbgcnt.h"
#include "gimple-fold.h"
#include "params.h"
+#include "expr.h"
/* Possible lattice values. */
@@ -169,6 +170,7 @@ static prop_value_t *const_val;
static void canonicalize_float_value (prop_value_t *);
static bool ccp_fold_stmt (gimple_stmt_iterator *);
+static prop_value_t get_value_from_alignment (tree);
/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
@@ -391,6 +393,48 @@ canonicalize_float_value (prop_value_t *
}
}
+static bool
+alignment_to_address_transition_p (prop_value_t old_val, prop_value_t new_val,
+ bool warn)
+{
+ prop_value_t align_val;
+ double_int align_offset;
+ bool compat;
+
+ if (!(old_val.lattice_val == CONSTANT
+ && integer_zerop (old_val.value)
+ && new_val.lattice_val == CONSTANT
+ && TREE_CODE (new_val.value) == ADDR_EXPR))
+ return false;
+
+ align_val = get_value_from_alignment (new_val.value);
+ align_offset = tree_to_double_int (align_val.value);
+ gcc_assert (align_val.lattice_val == CONSTANT);
+
+ /* There are 3 possibilities here:
+ - alignment ADDR_EXPR matches alignment old_val. We gain information in
+ the higher bits, and keep the same information in the align bits.
+ - alignment ADDR_EXPR is smaller than alignment old_val. We gain
+ information in the higher bits, but lose information in the align bits.
+ - alignment ADDR_EXPR is greater than alignment old_val. We gain
+ information both in the higher bits and the align bits.
+ Furthermore, we've detected an misaligned pointer dereference. */
+
+ if (warn)
+ {
+ compat = (double_int_zero_p (double_int_and_not (align_offset,
+ old_val.mask))
+ && double_int_equal_p (old_val.mask,
+ double_int_ior (align_val.mask,
+ old_val.mask)));
+ if (!compat)
+ warning (OPT_Wunaligned_pointer_deref,
+ "misaligned pointer dereferenced");
+ }
+
+ return true;
+}
+
/* Return whether the lattice transition is valid. */
static bool
@@ -414,6 +458,10 @@ valid_lattice_transition (prop_value_t o
&& TREE_CODE (new_val.value) == INTEGER_CST)
return true;
+ /* Allow transitioning from ~3 to &x. */
+ if (alignment_to_address_transition_p (old_val, new_val, false))
+ return true;
+
/* Bit-lattices have to agree in the still valid bits. */
if (TREE_CODE (old_val.value) == INTEGER_CST
&& TREE_CODE (new_val.value) == INTEGER_CST)
@@ -438,6 +486,10 @@ set_lattice_value (tree var, prop_value_
canonicalize_float_value (&new_val);
+ if (old_val->lattice_val == CONSTANT
+ && new_val.lattice_val < CONSTANT)
+ return false;
+
/* We have to be careful to not go up the bitwise lattice
represented by the mask.
??? This doesn't seem to be the best place to enforce this. */
@@ -461,7 +513,8 @@ set_lattice_value (tree var, prop_value_
|| (new_val.lattice_val == CONSTANT
&& TREE_CODE (new_val.value) == INTEGER_CST
&& (TREE_CODE (old_val->value) != INTEGER_CST
- || !double_int_equal_p (new_val.mask, old_val->mask))))
+ || !double_int_equal_p (new_val.mask, old_val->mask)))
+ || alignment_to_address_transition_p (*old_val, new_val, true))
{
/* ??? We would like to delay creation of INTEGER_CSTs from
partially constants here. */
@@ -500,20 +553,14 @@ value_to_double_int (prop_value_t val)
return double_int_zero;
}
-/* Return the value for the address expression EXPR based on alignment
- information. */
+/* Return the value for an expr of type TYPE with alignment ALIGN and offset
+ BITPOS relative to the alignment. */
static prop_value_t
-get_value_from_alignment (tree expr)
+get_align_value (unsigned int align, tree type, unsigned HOST_WIDE_INT bitpos)
{
- tree type = TREE_TYPE (expr);
prop_value_t val;
- unsigned HOST_WIDE_INT bitpos;
- unsigned int align;
-
- gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
- align = get_object_alignment_1 (TREE_OPERAND (expr, 0), &bitpos);
val.mask
= double_int_and_not (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
? double_int_mask (TYPE_PRECISION (type))
@@ -529,6 +576,21 @@ get_value_from_alignment (tree expr)
return val;
}
+/* Return the value for the address expression EXPR based on alignment
+ information. */
+
+static prop_value_t
+get_value_from_alignment (tree expr)
+{
+ unsigned int align;
+ unsigned HOST_WIDE_INT bitpos;
+
+ gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
+
+ align = get_object_alignment_1 (TREE_OPERAND (expr, 0), &bitpos);
+ return get_align_value (align, TREE_TYPE (expr), bitpos);
+}
+
/* Return the value for the tree operand EXPR. If FOR_BITS_P is true
return constant bits extracted from alignment information for
invariant addresses. */
@@ -707,25 +769,131 @@ surely_varying_stmt_p (gimple stmt)
return false;
}
+/* Find pointer dereference and init lattice value for that pointer based on
+ alignment, and propagate backward through pointer arithmetic. */
+
+static void
+deduce_alignment_from_dereference (gimple stmt)
+{
+ gimple def;
+ unsigned int align, misalign = 0;
+ tree memref, ptr, offset;
+ HOST_WIDE_INT offset_val;
+ struct ptr_info_def *pi;
+ prop_value_t val;
+
+ if (!is_gimple_assign (stmt))
+ return;
+
+ if (gimple_assign_rhs_code (stmt) == MEM_REF)
+ {
+ memref = gimple_assign_rhs1 (stmt);
+
+ align = get_object_or_type_alignment (memref) / BITS_PER_UNIT;
+ if (align == 1)
+ return;
+
+ offset = TREE_OPERAND (memref, 1);
+ if (!host_integerp (offset, 0))
+ return;
+ offset_val = tree_low_cst (offset, 0);
+ offset_val = offset_val % align;
+ misalign = (align + misalign - offset_val) % align;
+
+ ptr = TREE_OPERAND (memref, 0);
+ }
+ else
+ /* Todo: handle more cases. */
+ return;
+
+ while (true)
+ {
+
+ if (TREE_CODE (ptr) == INTEGER_CST)
+ {
+ if (host_integerp (ptr, 0)
+ && tree_low_cst (ptr, 0) % align != misalign)
+ warning (OPT_Wunaligned_pointer_deref,
+ "misaligned constant pointer dereferenced");
+ return;
+ }
+
+ if (TREE_CODE (ptr) != SSA_NAME)
+ return;
+
+ pi = get_ptr_info (ptr);
+
+ if ((pi->align < align && misalign % pi->align != pi->misalign)
+ || (pi->align >= align && pi->misalign % align != misalign))
+ {
+ warning (OPT_Wunaligned_pointer_deref,
+ "misaligned pointer dereferenced");
+ return;
+ }
+
+ if (pi->align >= align)
+ return;
+
+ val = get_align_value (align * BITS_PER_UNIT, TREE_TYPE (ptr),
+ misalign * BITS_PER_UNIT);
+ const_val[SSA_NAME_VERSION (ptr)] = val;
+
+ if (SSA_NAME_IS_DEFAULT_DEF (ptr))
+ return;
+
+ /* Propagate backwards over pointer arithmetic. */
+ def = SSA_NAME_DEF_STMT (ptr);
+ if (!is_gimple_assign (def))
+ return;
+
+ switch (gimple_assign_rhs_code (def))
+ {
+ case POINTER_PLUS_EXPR:
+ offset = gimple_assign_rhs2 (def);
+ if (!host_integerp (offset, 0))
+ return;
+ offset_val = tree_low_cst (offset, 0);
+ offset_val = offset_val % align;
+ misalign = (align + misalign - offset_val) % align;
+ ptr = gimple_assign_rhs1 (def);
+ break;
+ case INTEGER_CST:
+ case SSA_NAME:
+ ptr = gimple_assign_rhs1 (def);
+ break;
+ default:
+ /* Todo: handle more cases. */
+ return;
+ }
+ }
+}
+
/* Initialize local data structures for CCP. */
static void
ccp_initialize (void)
{
- basic_block bb;
+ basic_block bb, entry;
const_val = XCNEWVEC (prop_value_t, num_ssa_names);
+ /* Needs to be the successor of entry, for CDI_POST_DOMINATORS. */
+ entry = single_succ (ENTRY_BLOCK_PTR);
+
/* Initialize simulation flags for PHI nodes and statements. */
FOR_EACH_BB (bb)
{
gimple_stmt_iterator i;
+ bool post_dom_by_entry = dominated_by_p (CDI_POST_DOMINATORS, entry, bb);
for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
{
gimple stmt = gsi_stmt (i);
bool is_varying;
+ if (post_dom_by_entry)
+ deduce_alignment_from_dereference (stmt);
+
/* If the statement is a control insn, then we do not
want to avoid simulating the statement once. Failure
to do so means that those edges will never get added. */
@@ -2024,7 +2192,9 @@ ccp_visit_stmt (gimple stmt, edge *taken
static unsigned int
do_ssa_ccp (void)
{
+ calculate_dominance_info (CDI_POST_DOMINATORS);
ccp_initialize ();
+ free_dominance_info (CDI_POST_DOMINATORS);
ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
if (ccp_finalize ())
return (TODO_cleanup_cfg | TODO_update_ssa | TODO_remove_unused_locals);
Index: gcc/expr.c
===================================================================
--- gcc/expr.c (revision 180521)
+++ gcc/expr.c (working copy)
@@ -4553,7 +4553,7 @@ get_bit_range (unsigned HOST_WIDE_INT *b
their type, so we optimistically fall back to the alignment of the
type when we cannot compute a misalignment. */
-static unsigned int
+unsigned int
get_object_or_type_alignment (tree exp)
{
unsigned HOST_WIDE_INT misalign;
Index: gcc/expr.h
===================================================================
--- gcc/expr.h (revision 180521)
+++ gcc/expr.h (working copy)
@@ -397,6 +397,10 @@ extern rtx push_block (rtx, int, int);
extern void emit_push_insn (rtx, enum machine_mode, tree, rtx, unsigned int,
int, rtx, int, rtx, rtx, int, rtx);
+/* Return the alignment of the object EXP, also considering its type
+ when we do not know of explicit misalignment. */
+unsigned int get_object_or_type_alignment (tree);
+
/* Expand an assignment that stores the value of FROM into TO. */
extern void expand_assignment (tree, tree, bool);
Index: gcc/common.opt
===================================================================
--- gcc/common.opt (revision 180521)
+++ gcc/common.opt (working copy)
@@ -511,6 +511,10 @@ Wcast-align
Common Var(warn_cast_align) Warning
Warn about pointer casts which increase alignment
+Wunaligned-pointer-deref
+Common Var(warn_unaligned_pointer_deref) Warning
+Warn about unaligned pointers which are unconditionally dereferenced
+
Wcpp
Common Var(warn_cpp) Init(1) Warning
Warn when a #warning directive is encountered
Index: gcc/testsuite/gcc.target/arm/pr43814-2.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.target/arm/pr43814-2.c (revision 0)
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-Os -finline-functions -mno-unaligned-access -fdump-rtl-expand" } */
+
+typedef unsigned int size_t;
+extern void* memcpy (void *, const void *, size_t);
+
+typedef union JValue {
+ void* l;
+} JValue;
+typedef struct Object {
+ int x;
+} Object;
+
+extern __inline__ long long
+dvmGetArgLong (const unsigned int* args, int elem)
+{
+ long long val;
+ memcpy (&val, &args[elem], 8);
+ return val;
+}
+
+void
+Dalvik_sun_misc_Unsafe_getObject (const unsigned int* args, JValue* pResult)
+{
+ Object* obj = (Object*) args[1];
+ long long offset = dvmGetArgLong (args, 2);
+ Object** address = (Object**) (((unsigned char*) obj) + offset);
+ pResult->l = ((void*) *address);
+}
+
+/* { dg-final { scan-rtl-dump-times "memcpy" 0 "expand"} } */
+/* { dg-final { cleanup-tree-dump "expand" } } */
+
Index: gcc/testsuite/gcc.dg/misalign.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/misalign.c (revision 0)
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -Wunaligned-pointer-deref" } */
+
+int *y;
+
+int
+f()
+{
+ int *p = (int*)0x10000001;
+ y = p;
+ return *p;
+}
+
+/* { dg-warning "misaligned constant pointer dereferenced" "" { target *-*-* } 7 } */
+/* { dg-warning "misaligned constant pointer dereferenced" "" { target *-*-* } 12 } */
Index: gcc/testsuite/gcc.dg/misalign2.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/misalign2.c (revision 0)
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -Wunaligned-pointer-deref" } */
+
+short
+foo (void)
+{
+ int a = 0;
+ short *b = (short *) (((char *)&a) + 1);
+ return *b;
+}
+
+/* { dg-warning "misaligned pointer dereferenced" "" { target *-*-* } 10 } */
+
Index: gcc/testsuite/gcc.dg/analyze-deref.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/analyze-deref.c (revision 0)
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ccp1" } */
+
+int y;
+
+unsigned long int
+f (int *p)
+{
+ y = *p;
+ return ((unsigned long int)p) & (sizeof (*p) - 1);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "ccp1"} } */
+/* { dg-final { cleanup-tree-dump "ccp1" } } */
