From patchwork Thu Dec 8 15:10:30 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 130185 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 154A91007D1 for ; Fri, 9 Dec 2011 02:11:07 +1100 (EST) Received: (qmail 1458 invoked by alias); 8 Dec 2011 15:11:01 -0000 Received: (qmail 1445 invoked by uid 22791); 8 Dec 2011 15:10:57 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, TW_CP, TW_TM X-Spam-Check-By: sourceware.org Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 08 Dec 2011 15:10:42 +0000 Received: from svr-orw-exc-10.mgc.mentorg.com ([147.34.98.58]) by relay1.mentorg.com with esmtp id 1RYfcO-0003wi-88 from Tom_deVries@mentor.com ; Thu, 08 Dec 2011 07:10:40 -0800 Received: from SVR-IES-FEM-01.mgc.mentorg.com ([137.202.0.104]) by SVR-ORW-EXC-10.mgc.mentorg.com with Microsoft SMTPSVC(6.0.3790.4675); Thu, 8 Dec 2011 07:10:10 -0800 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-01.mgc.mentorg.com (137.202.0.104) with Microsoft SMTP Server id 14.1.289.1; Thu, 8 Dec 2011 15:10:37 +0000 Message-ID: <4EE0D366.1070303@mentor.com> Date: Thu, 8 Dec 2011 16:10:30 +0100 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.23) Gecko/20110922 Lightning/1.0b2 Thunderbird/3.1.15 MIME-Version: 1.0 To: Richard Guenther CC: Jakub Jelinek , "gcc-patches@gcc.gnu.org" , "Kuvyrkov, Maxim" Subject: Re: [PATCH, PR43814] Assume function arguments of pointer type are aligned. References: <4E787543.1090009@codesourcery.com> <20110924094059.GW2687@tyan-ft48-01.lab.bos.redhat.com> <4EA6AA02.6010301@mentor.com> In-Reply-To: Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org On 26/10/11 12:19, Richard Guenther wrote: > On Tue, Oct 25, 2011 at 2:22 PM, Tom de Vries wrote: >> On 09/24/2011 01:42 PM, Richard Guenther wrote: >>> On Sat, Sep 24, 2011 at 11:40 AM, Jakub Jelinek 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 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" } } */