Re: [PATCH] Add a new option "-ftree-bitfield-merge" (patch / doc inside)

[Richard Biener <richard dot guenther at gmail dot com>]

Zoran Jovanovic <Zoran.Jovanovic@imgtec.com> wrote:

>Hello,
>This patch adds new optimization pass that combines several adjacent
>bit field accesses that copy values from one memory location to another
>into single bit field access.
>
>Example:
>
>Original code:
>Â <unnamed-unsigned:3> D.1351;
>Â <unnamed-unsigned:9> D.1350;
>Â <unnamed-unsigned:7> D.1349;
>Â D.1349_2 = p1_1(D)->f1;
>Â p2_3(D)->f1 = D.1349_2;
>Â D.1350_4 = p1_1(D)->f2;
>Â p2_3(D)->f2 = D.1350_4;
>Â D.1351_5 = p1_1(D)->f3;
>Â p2_3(D)->f3 = D.1351_5;
>
>Optimized code:
>Â <unnamed-unsigned:19> D.1358;
>Â D.1358_10 = BIT_FIELD_REF <*p1_1(D), 19, 13>;
>Â BIT_FIELD_REF <*p2_3(D), 19, 13> = D.1358_10;
>
>Algorithm works on basic block level and consists of following 3 major
>steps:
>1. Go trough basic block statements list. If there are statement pairs
>that implement copy of bit field content from one memory location to
>another record statements pointers and other necessary data in
>corresponding data structure.
>2. Identify records that represent adjacent bit field accesses and mark
>them as merged.
>3. Modify trees accordingly.

All this should use BITFIELD_REPRESENTATIVE both to decide what accesses are related and for the lowering. This makes sure to honor the appropriate memory models.

In theory only lowering is necessary and FRE and DSE will do the job of optimizing - also properly accounting for alias issues that Joseph mentions. The lowering and analysis is strongly related to SRA So I don't believe we want a new pass for this.

Richard.

>New command line option "-ftree-bitfield-merge" is introduced.
>
>Tested - passed gcc regression tests.
>
>Changelog -
>
>gcc/ChangeLog:
>2013-07-17 Zoran Jovanovic (zoran.jovanovic@imgtec.com)
>Â * Makefile.in : Added tree-ssa-bitfield-merge.o to OBJS.
>Â * common.opt (ftree-bitfield-merge): New option.
>Â * doc/invoke.texi: Added reference to "-ftree-bitfield-merge".
>Â * dwarf2out.c (field_type): static removed from declaration.
>Â (simple_type_size_in_bits): static removed from declaration.
>Â (field_byte_offset): static removed from declaration.
>Â (field_type): static inline removed from declaration.
>Â * passes.c (init_optimization_passes): pass_bitfield_merge pass
>added.
>Â * testsuite/gcc.dg/tree-ssa/bitfldmrg.c: New test.
>Â * timevar.def : Added TV_TREE_BITFIELD_MERGE.
>Â * tree-pass.h : Added pass_bitfield_merge declaration.
>Â * tree-ssa-bitfield-merge.c : New file.
>
>Patch -
>
>diff --git a/gcc/Makefile.in b/gcc/Makefile.in
>index d5121f3..5cdd6eb 100644
>--- a/gcc/Makefile.in
>+++ b/gcc/Makefile.in
>@@ -1417,6 +1417,7 @@ OBJS = \
>Â	tree-ssa-dom.o \
>Â	tree-ssa-dse.o \
>Â	tree-ssa-forwprop.o \
>+	tree-ssa-bitfield-merge.o \
>Â	tree-ssa-ifcombine.o \
>Â	tree-ssa-live.o \
>Â	tree-ssa-loop-ch.o \
>@@ -2312,6 +2313,11 @@ tree-ssa-forwprop.o : tree-ssa-forwprop.c
>$(CONFIG_H) $(SYSTEM_H) coretypes.h \
>Â Â $(TREE_FLOW_H) $(TREE_PASS_H) $(DIAGNOSTIC_H) \
>Â Â langhooks.h $(FLAGS_H) $(GIMPLE_H) $(GIMPLE_PRETTY_PRINT_H)
>$(EXPR_H) \
>Â Â $(OPTABS_H) tree-ssa-propagate.h
>+tree-ssa-bitfield-merge.o : tree-ssa-forwprop.c $(CONFIG_H)
>$(SYSTEM_H) \
>+ Â coretypes.h $(TM_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) \
>+ Â $(TREE_FLOW_H) $(TREE_PASS_H) $(TREE_DUMP_H) $(DIAGNOSTIC_H)
>$(TIMEVAR_H) \
>+ Â langhooks.h $(FLAGS_H) $(GIMPLE_H) tree-pretty-print.h \
>+ Â gimple-pretty-print.h $(EXPR_H)
>Âtree-ssa-phiprop.o : tree-ssa-phiprop.c $(CONFIG_H) $(SYSTEM_H)
>coretypes.h \
>Â Â $(TM_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) \
>Â Â $(TREE_FLOW_H) $(TREE_PASS_H) $(DIAGNOSTIC_H) \
>@@ -3803,6 +3809,7 @@ GTFILES = $(CPP_ID_DATA_H) $(srcdir)/input.h
>$(srcdir)/coretypes.h \
>Â Â$(srcdir)/ipa-inline.h \
>Â Â$(srcdir)/asan.c \
>Â Â$(srcdir)/tsan.c \
>+ Â$(srcdir)/tree-ssa-bitfield-merge.c \
>Â Â@all_gtfiles@
>Â
>Â# Compute the list of GT header files from the corresponding C
>sources,
>diff --git a/gcc/common.opt b/gcc/common.opt
>index 4c7933e..e0dbc37 100644
>--- a/gcc/common.opt
>+++ b/gcc/common.opt
>@@ -2088,6 +2088,10 @@ ftree-forwprop
>ÂCommon Report Var(flag_tree_forwprop) Init(1) Optimization
>ÂEnable forward propagation on trees
>Â
>+ftree-bitfield-merge
>+Common Report Var(flag_tree_bitfield_merge) Init(0) Optimization
>+Enable bit field merge on trees
>+
>Âftree-fre
>ÂCommon Report Var(flag_tree_fre) Optimization
>ÂEnable Full Redundancy Elimination (FRE) on trees
>diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
>index dd82880..7b671aa 100644
>--- a/gcc/doc/invoke.texi
>+++ b/gcc/doc/invoke.texi
>@@ -409,7 +409,7 @@ Objective-C and Objective-C++ Dialects}.
>Â-fsplit-ivs-in-unroller -fsplit-wide-types -fstack-protector @gol
>Â-fstack-protector-all -fstack-protector-strong -fstrict-aliasing @gol
>Â-fstrict-overflow -fthread-jumps -ftracer -ftree-bit-ccp @gol
>--ftree-builtin-call-dce -ftree-ccp -ftree-ch @gol
>+-ftree-bitfield-merge -ftree-builtin-call-dce -ftree-ccp -ftree-ch
>@gol
>Â-ftree-coalesce-inline-vars -ftree-coalesce-vars -ftree-copy-prop @gol
>Â-ftree-copyrename -ftree-dce -ftree-dominator-opts -ftree-dse @gol
>Â-ftree-forwprop -ftree-fre -ftree-loop-if-convert @gol
>@@ -7582,6 +7582,11 @@ pointer alignment information.
>ÂThis pass only operates on local scalar variables and is enabled by
>default
>Âat @option{-O} and higher. ÂIt requires that @option{-ftree-ccp} is
>enabled.
>Â
>+@item -ftree-bitfield-merge
>+@opindex ftree-bitfield-merge
>+Combines several adjacent bit field accesses that copy values
>+from one memory location to another into single bit field access.
>+
>Â@item -ftree-ccp
>Â@opindex ftree-ccp
>ÂPerform sparse conditional constant propagation (CCP) on trees. ÂThis
>diff --git a/gcc/dwarf2out.c b/gcc/dwarf2out.c
>index f42ad66..a08eede 100644
>--- a/gcc/dwarf2out.c
>+++ b/gcc/dwarf2out.c
>@@ -3100,11 +3100,11 @@ static dw_loc_descr_ref loc_descriptor (rtx,
>enum machine_mode mode,
>Âstatic dw_loc_list_ref loc_list_from_tree (tree, int);
>Âstatic dw_loc_descr_ref loc_descriptor_from_tree (tree, int);
>Âstatic HOST_WIDE_INT ceiling (HOST_WIDE_INT, unsigned int);
>-static tree field_type (const_tree);
>+tree field_type (const_tree);
>Âstatic unsigned int simple_type_align_in_bits (const_tree);
>Âstatic unsigned int simple_decl_align_in_bits (const_tree);
>-static unsigned HOST_WIDE_INT simple_type_size_in_bits (const_tree);
>-static HOST_WIDE_INT field_byte_offset (const_tree);
>+unsigned HOST_WIDE_INT simple_type_size_in_bits (const_tree);
>+HOST_WIDE_INT field_byte_offset (const_tree);
>Âstatic void add_AT_location_description	(dw_die_ref, enum
>dwarf_attribute,
>Â					 dw_loc_list_ref);
>Âstatic void add_data_member_location_attribute (dw_die_ref, tree);
>@@ -10061,7 +10061,7 @@ is_base_type (tree type)
>Â Â else return BITS_PER_WORD if the type actually turns out to be an
>Â Â ERROR_MARK node. Â*/
>Â
>-static inline unsigned HOST_WIDE_INT
>+unsigned HOST_WIDE_INT
>Âsimple_type_size_in_bits (const_tree type)
>Â{
>Â Âif (TREE_CODE (type) == ERROR_MARK)
>@@ -14375,7 +14375,7 @@ ceiling (HOST_WIDE_INT value, unsigned int
>boundary)
>Â Â `integer_type_node' if the given node turns out to be an
>Â Â ERROR_MARK node. Â*/
>Â
>-static inline tree
>+tree
>Âfield_type (const_tree decl)
>Â{
>Â Âtree type;
>@@ -14426,7 +14426,7 @@ round_up_to_align (double_int t, unsigned int
>align)
>Â Â because the offset is actually variable. Â(We can't handle the
>latter case
>Â Â just yet). Â*/
>Â
>-static HOST_WIDE_INT
>+HOST_WIDE_INT
>Âfield_byte_offset (const_tree decl)
>Â{
>Â Âdouble_int object_offset_in_bits;
>diff --git a/gcc/passes.c b/gcc/passes.c
>index c8b03ee..3149adc 100644
>--- a/gcc/passes.c
>+++ b/gcc/passes.c
>@@ -1325,6 +1325,7 @@ init_optimization_passes (void)
>Â	 ÂNEXT_PASS (pass_remove_cgraph_callee_edges);
>Â	 ÂNEXT_PASS (pass_rename_ssa_copies);
>Â	 ÂNEXT_PASS (pass_ccp);
>+	 ÂNEXT_PASS (pass_bitfield_merge);
>Â	 Â/* After CCP we rewrite no longer addressed locals into SSA
>Â	 Â Â form if possible. Â*/
>Â	 ÂNEXT_PASS (pass_forwprop);
>diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitfldmrg.c
>b/gcc/testsuite/gcc.dg/tree-ssa/bitfldmrg.c
>new file mode 100644
>index 0000000..9be6bc9
>--- /dev/null
>+++ b/gcc/testsuite/gcc.dg/tree-ssa/bitfldmrg.c
>@@ -0,0 +1,29 @@
>+/* { dg-do compile } */
>+/* { dg-options "-O2 -ftree-bitfield-merge -fdump-tree-bitfieldmerge"
>} Â*/
>+
>+struct S
>+{
>+ Âunsigned f1:7;
>+ Âunsigned f2:9;
>+ Âunsigned f3:3;
>+ Âunsigned f4:5;
>+ Âunsigned f5:1;
>+ Âunsigned f6:2;
>+};
>+
>+unsigned
>+foo (struct S *p1, struct S *p2, int *ptr)
>+{
>+ Âp2->f1 = p1->f1;
>+ Âp2->f2 = p1->f2;
>+ Âp2->f3 = p1->f3;
>+ Â*ptr = 7;
>+ Âp2->f4 = p1->f4;
>+ Âp2->f5 = p1->f5;
>+ Âp2->f6 = p1->f6;
>+ Âreturn 0;
>+}
>+
>+/* { dg-final { scan-tree-dump "19" "bitfieldmerge" } } */
>+/* { dg-final { scan-tree-dump "8" "bitfieldmerge"} } */
>+/* { dg-final { cleanup-tree-dump "bitfieldmerge" } } */
>diff --git a/gcc/timevar.def b/gcc/timevar.def
>index 44f0eac..d9b1c23 100644
>--- a/gcc/timevar.def
>+++ b/gcc/timevar.def
>@@ -149,6 +149,7 @@ DEFTIMEVAR (TV_TREE_FRE		 Â Â , "tree FRE")
>ÂDEFTIMEVAR (TV_TREE_SINK Â Â Â Â Â Â , "tree code sinking")
>ÂDEFTIMEVAR (TV_TREE_PHIOPT	 Â Â , "tree linearize phis")
>ÂDEFTIMEVAR (TV_TREE_FORWPROP	 Â Â , "tree forward propagate")
>+DEFTIMEVAR (TV_TREE_BITFIELD_MERGE Â , "tree bitfield merge")
>ÂDEFTIMEVAR (TV_TREE_PHIPROP	 Â Â , "tree phiprop")
>ÂDEFTIMEVAR (TV_TREE_DCE		 Â Â , "tree conservative DCE")
>ÂDEFTIMEVAR (TV_TREE_CD_DCE	 Â Â , "tree aggressive DCE")
>diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
>index b8c59a7..59ca028 100644
>--- a/gcc/tree-pass.h
>+++ b/gcc/tree-pass.h
>@@ -337,6 +337,7 @@ extern struct gimple_opt_pass
>pass_warn_function_noreturn;
>Âextern struct gimple_opt_pass pass_cselim;
>Âextern struct gimple_opt_pass pass_phiopt;
>Âextern struct gimple_opt_pass pass_forwprop;
>+extern struct gimple_opt_pass pass_bitfield_merge;
>Âextern struct gimple_opt_pass pass_phiprop;
>Âextern struct gimple_opt_pass pass_tree_ifcombine;
>Âextern struct gimple_opt_pass pass_dse;
>diff --git a/gcc/tree-ssa-bitfield-merge.c
>b/gcc/tree-ssa-bitfield-merge.c
>new file mode 100755
>index 0000000..71f41b3
>--- /dev/null
>+++ b/gcc/tree-ssa-bitfield-merge.c
>@@ -0,0 +1,503 @@
>+/* Forward propagation of expressions for single use variables.
>+ Â Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011
>+ Â Free Software Foundation, Inc.
>+
>+This file is part of GCC.
>+
>+GCC is free software; you can redistribute it and/or modify
>+it under the terms of the GNU General Public License as published by
>+the Free Software Foundation; either version 3, or (at your option)
>+any later version.
>+
>+GCC is distributed in the hope that it will be useful,
>+but WITHOUT ANY WARRANTY; without even the implied warranty of
>+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. ÂSee the
>+GNU General Public License for more details.
>+
>+You should have received a copy of the GNU General Public License
>+along with GCC; see the file COPYING3. ÂIf not see
>+<http://www.gnu.org/licenses/>. Â*/
>+
>+#include "config.h"
>+#include "system.h"
>+#include "coretypes.h"
>+#include "tm.h"
>+#include "tree.h"
>+#include "tm_p.h"
>+#include "basic-block.h"
>+#include "timevar.h"
>+#include "gimple-pretty-print.h"
>+#include "tree-flow.h"
>+#include "tree-pass.h"
>+#include "tree-dump.h"
>+#include "langhooks.h"
>+#include "flags.h"
>+#include "gimple.h"
>+#include "expr.h"
>+#include "ggc.h"
>+
>+tree
>+field_type (const_tree decl);
>+
>+bool
>+expressions_equal_p (tree e1, tree e2);
>+
>+HOST_WIDE_INT
>+field_byte_offset (const_tree decl);
>+
>+unsigned HOST_WIDE_INT
>+simple_type_size_in_bits (const_tree type);
>+
>+/* This pass combines several adjacent bit field accesses that copy
>values
>+ Â from one memory location to another into single bit field access.
>Â*/
>+
>+/* Data for single bit field read/write sequence. Â*/
>+struct GTY (()) bitfield_access_d {
>+ Âgimple load_stmt;		 Â/* Bit field load statement. Â*/
>+ Âgimple store_stmt;		 Â/* Bit field store statement. Â*/
>+ Âunsigned src_offset_bytes;	 Â/* Bit field offset at src in bytes.
>Â*/
>+ Âunsigned src_bit_offset;	 Â/* Bit field offset inside source word.
>Â*/
>+ Âunsigned src_bit_size;	 Â/* Size of bit field in source word. Â*/
>+ Âunsigned dst_offset_bytes;	 Â/* Bit field offset at dst in bytes.
>Â*/
>+ Âunsigned dst_bit_offset;	 Â/* Bit field offset inside destination
>+				 Â Â word. Â*/
>+ Âunsigned dst_bit_size;	 Â/* Size of bit field in destination word.
>Â*/
>+ Âtree src_addr;		 Â/* Address of source memory access. Â*/
>+ Âtree dst_addr;		 Â/* Address of destination memory access. Â*/
>+ Âbool merged;			 Â/* True if access is merged with another
>+				 Â Â one. Â*/
>+ Âbool modified;		 Â/* True if bitfield size is modified. Â*/
>+ Âbool is_barrier;		 Â/* True if access is barrier (call or mem
>+				 Â Â access). Â*/
>+ Âstruct bitfield_access_d *next; /* Access with which this one is
>merged. Â*/
>+};
>+
>+typedef struct bitfield_access_d bitfield_access_o;
>+typedef struct bitfield_access_d *bitfield_access;
>+
>+/* Connecting register with bit field access sequence that defines
>value in
>+ Â that register. Â*/
>+struct GTY (()) bitfield_stmt_access_pair_d
>+{
>+ Âgimple stmt;
>+ Âbitfield_access access;
>+};
>+
>+typedef struct bitfield_stmt_access_pair_d
>bitfield_stmt_access_pair_o;
>+typedef struct bitfield_stmt_access_pair_d *bitfield_stmt_access_pair;
>+
>+static GTY ((param_is (struct bitfield_stmt_access_pair_d)))
>+ Âhtab_t bitfield_stmt_access_htab;
>+
>+/* Hash table callbacks for bitfield_stmt_access_htab. Â*/
>+
>+static hashval_t
>+bitfield_stmt_access_pair_htab_hash (const void *p)
>+{
>+ Âconst struct bitfield_stmt_access_pair_d *entry =
>+ Â Â(const struct bitfield_stmt_access_pair_d *)p;
>+ Âreturn (hashval_t) (uintptr_t) entry->stmt;
>+}
>+
>+static int
>+bitfield_stmt_access_pair_htab_eq (const void *p1, const void *p2)
>+{
>+ Âconst struct bitfield_stmt_access_pair_d *entry1 =
>+ Â Â(const struct bitfield_stmt_access_pair_d *)p1;
>+ Âconst struct bitfield_stmt_access_pair_d *entry2 =
>+ Â Â(const struct bitfield_stmt_access_pair_d *)p2;
>+ Âreturn entry1->stmt == entry2->stmt;
>+}
>+
>+
>+static bool cfg_changed;
>+
>+/* Compare two bit field access records. Â*/
>+
>+static int
>+cmp_access (const void *p1, const void *p2)
>+{
>+ Âconst bitfield_access a1 = (*(const bitfield_access*)p1);
>+ Âconst bitfield_access a2 = (*(const bitfield_access*)p2);
>+
>+ Âif (!expressions_equal_p (a1->src_addr, a1->src_addr))
>+ Â Âreturn a1 - a2;
>+
>+ Âif (!expressions_equal_p (a1->dst_addr, a1->dst_addr))
>+ Â Âreturn a1 - a2;
>+
>+ Âreturn a1->src_bit_offset - a2->src_bit_offset;
>+}
>+
>+/* Create new bit field access structure and add it to given
>bitfield_accesses
>+ Â htab. Â*/
>+static bitfield_access
>+create_and_insert_access (vec<bitfield_access>
>+		 Â Â Â *bitfield_accesses)
>+{
>+ Âbitfield_access access = ggc_alloc_bitfield_access_d ();
>+ Âmemset (access, 0, sizeof (struct bitfield_access_d));
>+ Âbitfield_accesses->safe_push (access);
>+ Âreturn access;
>+}
>+
>+/* Slightly modified add_bit_offset_attribute from dwarf2out.c. Â*/
>+static inline HOST_WIDE_INT
>+get_bit_offset (tree decl)
>+{
>+ ÂHOST_WIDE_INT object_offset_in_bytes = field_byte_offset (decl);
>+ Âtree type = DECL_BIT_FIELD_TYPE (decl);
>+ ÂHOST_WIDE_INT bitpos_int;
>+ ÂHOST_WIDE_INT highest_order_object_bit_offset;
>+ ÂHOST_WIDE_INT highest_order_field_bit_offset;
>+ ÂHOST_WIDE_INT bit_offset;
>+
>+ Â/* Must be a field and a bit field. Â*/
>+ Âgcc_assert (type && TREE_CODE (decl) == FIELD_DECL);
>+ Âif (! host_integerp (bit_position (decl), 0)
>+ Â Â Â|| ! host_integerp (DECL_SIZE (decl), 1))
>+ Â Âreturn -1;
>+
>+ Âbitpos_int = int_bit_position (decl);
>+
>+ Â/* Note that the bit offset is always the distance (in bits) from
>the
>+ Â Â highest-order bit of the "containing object" to the highest-order
>bit of
>+ Â Â the bit-field itself. ÂSince the "high-order end" of any object
>or field
>+ Â Â is different on big-endian and little-endian machines, the
>computation
>+ Â Â below must take account of these differences. Â*/
>+ Âhighest_order_object_bit_offset = object_offset_in_bytes *
>BITS_PER_UNIT;
>+ Âhighest_order_field_bit_offset = bitpos_int;
>+
>+ Âif (! BYTES_BIG_ENDIAN)
>+ Â Â{
>+ Â Â Âhighest_order_field_bit_offset += tree_low_cst (DECL_SIZE
>(decl), 0);
>+ Â Â Âhighest_order_object_bit_offset += simple_type_size_in_bits
>(type);
>+ Â Â}
>+
>+ Âbit_offset
>+ Â Â= (! BYTES_BIG_ENDIAN
>+ Â Â Â ? highest_order_object_bit_offset -
>highest_order_field_bit_offset
>+ Â Â Â : highest_order_field_bit_offset -
>highest_order_object_bit_offset);
>+
>+ Âreturn bit_offset;
>+}
>+
>+/* Slightly modified add_byte_size_attribute from dwarf2out.c. Â*/
>+static inline HOST_WIDE_INT
>+get_byte_size (tree tree_node)
>+{
>+ Âunsigned size;
>+
>+ Âswitch (TREE_CODE (tree_node))
>+ Â Â{
>+ Â Âcase ERROR_MARK:
>+ Â Â Âsize = 0;
>+ Â Â Âbreak;
>+ Â Âcase ENUMERAL_TYPE:
>+ Â Âcase RECORD_TYPE:
>+ Â Âcase UNION_TYPE:
>+ Â Âcase QUAL_UNION_TYPE:
>+ Â Â Âsize = int_size_in_bytes (tree_node);
>+ Â Â Âbreak;
>+ Â Âcase FIELD_DECL:
>+ Â Â Â/* For a data member of a struct or union, the DW_AT_byte_size
>is
>+	 generally given as the number of bytes normally allocated for an
>+	 object of the *declared* type of the member itself. ÂThis is true
>+	 even for bit-fields. Â*/
>+ Â Â Âsize = simple_type_size_in_bits (field_type (tree_node)) /
>BITS_PER_UNIT;
>+ Â Â Âbreak;
>+ Â Âdefault:
>+ Â Â Âgcc_unreachable ();
>+ Â Â}
>+
>+ Âreturn size;
>+}
>+
>+/* Returns size of combined bitfields. Â*/
>+static int
>+get_merged_bit_field_size (bitfield_access access)
>+{
>+ Âbitfield_access tmp_access = access;
>+ Âint size = 0;
>+
>+ Âwhile (tmp_access)
>+ Â{
>+ Â Âsize += tmp_access->src_bit_size;
>+ Â Âtmp_access = tmp_access->next;
>+ Â}
>+ Âreturn size;
>+}
>+
>+/* Adds new pair consisting of statement and bit field access
>structure that
>+ Â contains it. Â*/
>+static bool add_stmt_access_pair (bitfield_access access, gimple stmt)
>+{
>+ Âbitfield_stmt_access_pair new_pair;
>+ Âvoid **slot;
>+ Ânew_pair = ggc_alloc_bitfield_stmt_access_pair_o ();
>+ Ânew_pair->stmt = stmt;
>+ Ânew_pair->access = access;
>+ Âslot = htab_find_slot (bitfield_stmt_access_htab, new_pair, INSERT);
>+ Âif (*slot == HTAB_EMPTY_ENTRY)
>+ Â Â{
>+ Â Â Â*slot = new_pair;
>+ Â Â Âreturn true;
>+ Â Â}
>+ Âreturn false;
>+}
>+
>+/* Main entry point for the bit field merge optimization. Â*/
>+static unsigned int
>+ssa_bitfield_merge (void)
>+{
>+ Âbasic_block bb;
>+ Âunsigned int todoflags = 0;
>+ Âvec<bitfield_access> bitfield_accesses;
>+ Âint ix, iy;
>+ Âbitfield_access access;
>+
>+ Âcfg_changed = false;
>+
>+ ÂFOR_EACH_BB (bb)
>+ Â Â{
>+ Â Â Âgimple_stmt_iterator gsi;
>+ Â Â Âvec<bitfield_access> bitfield_accesses_merge = vNULL;
>+ Â Â Âbitfield_accesses.create (0);
>+
>+ Â Â Âbitfield_stmt_access_htab
>+	= htab_create_ggc (128,
>+			 bitfield_stmt_access_pair_htab_hash,
>+			 bitfield_stmt_access_pair_htab_eq,
>+			 NULL);
>+
>+ Â Â Â/* Identify all bitfield copy sequences in the basic-block. Â*/
>+ Â Â Âfor (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
>+	{
>+	 Âgimple stmt = gsi_stmt (gsi);
>+	 Âtree lhs, rhs;
>+	 Âvoid **slot;
>+	 Âstruct bitfield_stmt_access_pair_d asdata;
>+
>+	 Âif (!is_gimple_assign (stmt))
>+	 Â Â{
>+	 Â Â Âgsi_next (&gsi);
>+	 Â Â Âcontinue;
>+	 Â Â}
>+
>+	 Âlhs = gimple_assign_lhs (stmt);
>+	 Ârhs = gimple_assign_rhs1 (stmt);
>+
>+	 Âif (TREE_CODE (rhs) == COMPONENT_REF)
>+	 Â Â{
>+	 Â Â Âuse_operand_p use;
>+	 Â Â Âgimple use_stmt;
>+	 Â Â Âtree op0 = TREE_OPERAND (rhs, 0);
>+	 Â Â Âtree op1 = TREE_OPERAND (rhs, 1);
>+
>+	 Â Â Âif (TREE_CODE (op1) == FIELD_DECL && DECL_BIT_FIELD_TYPE (op1))
>+		{
>+		 Âif (single_imm_use (lhs, &use, &use_stmt)
>+		 Â Â Â && is_gimple_assign (use_stmt))
>+		 Â Â{
>+		 Â Â Âtree use_lhs = gimple_assign_lhs (use_stmt);
>+		 Â Â Âif (TREE_CODE (use_lhs) == COMPONENT_REF)
>+			{
>+			 Âtree use_op0 = TREE_OPERAND (use_lhs, 0);
>+			 Âtree use_op1 = TREE_OPERAND (use_lhs, 1);
>+			 Âif (TREE_CODE (use_op1) == FIELD_DECL
>+			 Â Â Â&& DECL_BIT_FIELD_TYPE (use_op1))
>+			 Â Â{
>+			 Â Â Â/* Create new bit field access structure. Â*/
>+			 Â Â Âaccess = create_and_insert_access
>+					 (&bitfield_accesses);
>+			 Â Â Â/* Collect access data - load instruction. Â*/
>+			 Â Â Âaccess->src_bit_size = tree_low_cst
>+						 Â Â Â(DECL_SIZE (op1), 1);
>+			 Â Â Âaccess->src_bit_offset = get_bit_offset (op1);
>+			 Â Â Âaccess->src_offset_bytes = get_byte_size (op1);
>+			 Â Â Âaccess->src_addr = op0;
>+			 Â Â Âaccess->load_stmt = gsi_stmt (gsi);
>+			 Â Â Â/* Collect access data - store instruction. Â*/
>+			 Â Â Âaccess->dst_bit_size = tree_low_cst (DECL_SIZE
>+								 Â Â(use_op1),
>+								 Â 1);
>+			 Â Â Âaccess->dst_bit_offset = get_bit_offset
>+							 (use_op1);
>+			 Â Â Âaccess->dst_offset_bytes = get_byte_size
>+							 Â (use_op1);
>+			 Â Â Âaccess->dst_addr = use_op0;
>+			 Â Â Âaccess->store_stmt = use_stmt;
>+			 Â Â Âadd_stmt_access_pair (access, stmt);
>+			 Â Â Âadd_stmt_access_pair (access, use_stmt);
>+			 Â Â}
>+			}
>+		 Â Â}
>+		}
>+	 Â Â}
>+
>+	 Â/* Insert barrier for merging if statement is function call or
>memory
>+	 Â Â access. Â*/
>+	 Âasdata.stmt = stmt;
>+	 Âslot = htab_find_slot (bitfield_stmt_access_htab, &asdata,
>+				 NO_INSERT);
>+	 Âif (!slot && ((gimple_code (stmt) == GIMPLE_CALL)
>+	 Â Â Â|| (gimple_has_mem_ops (stmt))))
>+	 Â Â{
>+	 Â Â Â/* Create new bit field access structure. Â*/
>+	 Â Â Âaccess = create_and_insert_access (&bitfield_accesses);
>+	 Â Â Â/* Mark it as barrier. Â*/
>+	 Â Â Âaccess->is_barrier = true;
>+	 Â Â}
>+
>+	 Âgsi_next (&gsi);
>+	}
>+
>+ Â Â Â/* If there are no at least two accesses go to the next basic
>block. Â*/
>+ Â Â Âif (bitfield_accesses.length () <= 1)
>+	{
>+	 Âbitfield_accesses.release ();
>+	 Âcontinue;
>+	}
>+
>+ Â Â Â/* Find bitfield accesses that can be merged. Â*/
>+ Â Â Âfor (ix = 0; bitfield_accesses.iterate (ix, &access); ix++)
>+	{
>+	 Âbitfield_access head_access;
>+	 Âbitfield_access mrg_access;
>+	 Âbitfield_access prev_access;
>+
>+	 Âif (!bitfield_accesses_merge.exists ())
>+	 Â Âbitfield_accesses_merge.create (0);
>+
>+	 Âbitfield_accesses_merge.safe_push (access);
>+
>+	 Âif (!access->is_barrier
>+	 Â Â Â&& !(access == bitfield_accesses.last ()
>+	 Â Â Â&& !bitfield_accesses_merge.is_empty ()))
>+	 Â Âcontinue;
>+
>+	 Âbitfield_accesses_merge.qsort (cmp_access);
>+
>+	 Âhead_access = NULL;
>+	 Âfor (iy = 0; bitfield_accesses_merge.iterate (iy, &mrg_access);
>iy++)
>+	 Â Â{
>+	 Â Â Âif (head_access
>+		 Â&& expressions_equal_p (head_access->src_addr,
>+					 Âmrg_access->src_addr)
>+		 Â&& expressions_equal_p (head_access->dst_addr,
>+					 Âmrg_access->dst_addr)
>+		 Â&& prev_access->src_offset_bytes
>+		 Â Â == prev_access->src_offset_bytes
>+		 Â&& prev_access->dst_offset_bytes
>+		 Â Â == prev_access->dst_offset_bytes
>+		 Â&& prev_access->src_bit_offset + prev_access->src_bit_size
>+		 Â Â == mrg_access->src_bit_offset
>+		 Â&& prev_access->dst_bit_offset + prev_access->dst_bit_size
>+		 Â Â == mrg_access->dst_bit_offset)
>+		{
>+		 Â/* Merge conditions are satisfied - merge accesses. Â*/
>+		 Âmrg_access->merged = true;
>+		 Âprev_access->next = mrg_access;
>+		 Âhead_access->modified = true;
>+		 Âprev_access = mrg_access;
>+		}
>+	 Â Â Âelse
>+		head_access = prev_access = mrg_access;
>+	 Â Â}
>+	 Âbitfield_accesses_merge.release ();
>+	 Âbitfield_accesses_merge = vNULL;
>+	}
>+
>+ Â Â Â/* Modify generated code. Â*/
>+ Â Â Âfor (ix = 0; bitfield_accesses.iterate (ix, &access); ix++)
>+	{
>+	 Âif (access->merged)
>+	 Â Â{
>+	 Â Â Â/* Access merged - remove instructions. Â*/
>+	 Â Â Âgimple_stmt_iterator tmp_gsi;
>+	 Â Â Âtmp_gsi = gsi_for_stmt (access->load_stmt);
>+	 Â Â Âgsi_remove (&tmp_gsi, true);
>+	 Â Â Âtmp_gsi = gsi_for_stmt (access->store_stmt);
>+	 Â Â Âgsi_remove (&tmp_gsi, true);
>+	 Â Â}
>+	 Âelse if (access->modified)
>+	 Â Â{
>+	 Â Â Â/* Access modified - modify generated code. Â*/
>+	 Â Â Âgimple_stmt_iterator tmp_gsi;
>+	 Â Â Âtree tmp_ssa;
>+	 Â Â Âtree itype = make_node (INTEGER_TYPE);
>+	 Â Â Âtree new_rhs;
>+	 Â Â Âtree new_lhs;
>+	 Â Â Âgimple new_stmt;
>+
>+	 Â Â Â/* Bitfield size changed - modify load statement. Â*/
>+	 Â Â Âaccess->src_bit_size = get_merged_bit_field_size (access);
>+	 Â Â ÂTYPE_PRECISION (itype) = access->src_bit_size;
>+	 Â Â Âfixup_unsigned_type (itype);
>+	 Â Â Âtmp_ssa = make_ssa_name (create_tmp_var (itype, NULL), NULL);
>+	 Â Â Ânew_rhs = build3 (BIT_FIELD_REF, itype, access->src_addr,
>+				build_int_cst (unsigned_type_node,
>+					 Â Â Â access->src_bit_size),
>+				build_int_cst (unsigned_type_node,
>+					 Â Â Â access->src_bit_offset));
>+
>+	 Â Â Âtmp_gsi = gsi_for_stmt (access->load_stmt);
>+	 Â Â Ânew_stmt = gimple_build_assign (tmp_ssa, new_rhs);
>+	 Â Â Âgsi_insert_after (&tmp_gsi, new_stmt, GSI_SAME_STMT);
>+	 Â Â ÂSSA_NAME_DEF_STMT (tmp_ssa) = new_stmt;
>+	 Â Â Âgsi_remove (&tmp_gsi, true);
>+
>+	 Â Â Â/* Bitfield size changed - modify store statement. Â*/
>+	 Â Â Ânew_lhs = build3 (BIT_FIELD_REF, itype, access->dst_addr,
>+				build_int_cst (unsigned_type_node,
>+					 Â Â Â access->src_bit_size),
>+				build_int_cst (unsigned_type_node,
>+					 Â Â Â access->dst_bit_offset));
>+
>+	 Â Â Âtmp_gsi = gsi_for_stmt (access->store_stmt);
>+	 Â Â Ânew_stmt = gimple_build_assign (new_lhs, tmp_ssa);
>+	 Â Â Âgsi_insert_after (&tmp_gsi, new_stmt, GSI_SAME_STMT);
>+	 Â Â Âgsi_remove (&tmp_gsi, true);
>+
>+	 Â Â Âcfg_changed = true;
>+	 Â Â}
>+	}
>+ Â Â Â/* Empty or delete data structures used for basic block. Â*/
>+ Â Â Âhtab_empty (bitfield_stmt_access_htab);
>+ Â Â Âbitfield_accesses.release ();
>+ Â Â}
>+
>+ Âif (cfg_changed)
>+ Â Âtodoflags |= TODO_cleanup_cfg;
>+
>+ Âreturn todoflags;
>+}
>+
>+static bool
>+gate_bitfield_merge (void)
>+{
>+ Âreturn flag_tree_bitfield_merge;
>+}
>+
>+struct gimple_opt_pass pass_bitfield_merge =
>+{
>+ {
>+ ÂGIMPLE_PASS,
>+ Â"bitfieldmerge",		/* name */
>+ ÂOPTGROUP_NONE, Â Â Â Â Â Â Â Â/* optinfo_flags */
>+ Âgate_bitfield_merge,		/* gate */
>+ Âssa_bitfield_merge,		/* execute */
>+ ÂNULL,				/* sub */
>+ ÂNULL,				/* next */
>+ Â0,				/* static_pass_number */
>+ ÂTV_TREE_BITFIELD_MERGE,	/* tv_id */
>+ ÂPROP_cfg | PROP_ssa,		/* properties_required */
>+ Â0,				/* properties_provided */
>+ Â0,				/* properties_destroyed */
>+ Â0,				/* todo_flags_start */
>+ ÂTODO_update_ssa
>+ Â| TODO_verify_ssa		/* todo_flags_finish */
>+ }
>+};
>+
>+#include "gt-tree-ssa-bitfield-merge.h"
>
>
>Regards,
>Zoran Jovanovic