+
+/* Partial definition tracking support. */
+
+struct pd_range
+{
+ HOST_WIDE_INT offset;
+ HOST_WIDE_INT size;
+};
+
+struct pd_data
+{
+ tree rhs;
+ HOST_WIDE_INT offset;
+ HOST_WIDE_INT size;
+};
+
+/* Context for alias walking. */
+
+struct vn_walk_cb_data
+{
+ vn_walk_cb_data (vn_reference_t vr_, tree orig_ref_, tree *last_vuse_ptr_,
+ vn_lookup_kind vn_walk_kind_, bool tbaa_p_)
+ : vr (vr_), last_vuse_ptr (last_vuse_ptr_),
+ vn_walk_kind (vn_walk_kind_), tbaa_p (tbaa_p_), known_ranges (NULL)
+ {
+ ao_ref_init (&orig_ref, orig_ref_);
+ }
+ ~vn_walk_cb_data ();
+ void *push_partial_def (const pd_data& pd, tree, HOST_WIDE_INT);
+
+ vn_reference_t vr;
+ ao_ref orig_ref;
+ tree *last_vuse_ptr;
+ vn_lookup_kind vn_walk_kind;
+ bool tbaa_p;
+
+ /* The VDEFs of partial defs we come along. */
+ auto_vec<pd_data, 2> partial_defs;
+ /* The first defs range to avoid splay tree setup in most cases. */
+ pd_range first_range;
+ tree first_vuse;
+ splay_tree known_ranges;
+ obstack ranges_obstack;
+};
+
+vn_walk_cb_data::~vn_walk_cb_data ()
+{
+ if (known_ranges)
+ {
+ splay_tree_delete (known_ranges);
+ obstack_free (&ranges_obstack, NULL);
+ }
+}
+
+/* pd_range splay-tree helpers. */
+
+static int
+pd_range_compare (splay_tree_key offset1p, splay_tree_key offset2p)
+{
+ HOST_WIDE_INT offset1 = *(HOST_WIDE_INT *)offset1p;
+ HOST_WIDE_INT offset2 = *(HOST_WIDE_INT *)offset2p;
+ if (offset1 < offset2)
+ return -1;
+ else if (offset1 > offset2)
+ return 1;
+ return 0;
+}
+
+static void *
+pd_tree_alloc (int size, void *data_)
+{
+ vn_walk_cb_data *data = (vn_walk_cb_data *)data_;
+ return obstack_alloc (&data->ranges_obstack, size);
+}
+
+static void
+pd_tree_dealloc (void *, void *)
+{
+}
+
+/* Push PD to the vector of partial definitions returning a
+ value when we are ready to combine things with VUSE and MAXSIZEI,
+ NULL when we want to continue looking for partial defs or -1
+ on failure. */
+
+void *
+vn_walk_cb_data::push_partial_def (const pd_data &pd, tree vuse,
+ HOST_WIDE_INT maxsizei)
+{
+ if (partial_defs.is_empty ())
+ {
+ partial_defs.safe_push (pd);
+ first_range.offset = pd.offset;
+ first_range.size = pd.size;
+ first_vuse = vuse;
+ last_vuse_ptr = NULL;
+ /* Continue looking for partial defs. */
+ return NULL;
+ }
+
+ if (!known_ranges)
+ {
+ /* ??? Optimize the case where the 2nd partial def completes things. */
+ gcc_obstack_init (&ranges_obstack);
+ known_ranges = splay_tree_new_with_allocator (pd_range_compare, 0, 0,
+ pd_tree_alloc,
+ pd_tree_dealloc, this);
+ splay_tree_insert (known_ranges,
+ (splay_tree_key)&first_range.offset,
+ (splay_tree_value)&first_range);
+ }
+
+ pd_range newr = { pd.offset, pd.size };
+ splay_tree_node n;
+ pd_range *r;
+ /* Lookup the predecessor of offset + 1 and see if we need to merge. */
+ HOST_WIDE_INT loffset = newr.offset + 1;
+ if ((n = splay_tree_predecessor (known_ranges, (splay_tree_key)&loffset))
+ && ((r = (pd_range *)n->value), true)
+ && ranges_known_overlap_p (r->offset, r->size + 1,
+ newr.offset, newr.size))
+ {
+ /* Ignore partial defs already covered. */
+ if (known_subrange_p (newr.offset, newr.size, r->offset, r->size))
+ return NULL;
+ r->size = MAX (r->offset + r->size, newr.offset + newr.size) - r->offset;
+ }
+ else
+ {
+ /* newr.offset wasn't covered yet, insert the range. */
+ r = XOBNEW (&ranges_obstack, pd_range);
+ *r = newr;
+ splay_tree_insert (known_ranges, (splay_tree_key)&r->offset,
+ (splay_tree_value)r);
+ }
+ /* Merge r which now contains newr and is a member of the splay tree with
+ adjacent overlapping ranges. */
+ pd_range *rafter;
+ while ((n = splay_tree_successor (known_ranges, (splay_tree_key)&r->offset))
+ && ((rafter = (pd_range *)n->value), true)
+ && ranges_known_overlap_p (r->offset, r->size + 1,
+ rafter->offset, rafter->size))
+ {
+ r->size = MAX (r->offset + r->size,
+ rafter->offset + rafter->size) - r->offset;
+ splay_tree_remove (known_ranges, (splay_tree_key)&rafter->offset);
+ }
+ partial_defs.safe_push (pd);
+
+ /* Now we have merged newr into the range tree. When we have covered
+ [offseti, sizei] then the tree will contain exactly one node which has
+ the desired properties and it will be 'r'. */
+ if (!known_subrange_p (0, maxsizei / BITS_PER_UNIT, r->offset, r->size))
+ /* Continue looking for partial defs. */
+ return NULL;
+
+ /* Now simply native encode all partial defs in reverse order. */
+ unsigned ndefs = partial_defs.length ();
+ /* We support up to 512-bit values (for V8DFmode). */
+ unsigned char buffer[64];
+ int len;
+
+ while (!partial_defs.is_empty ())
+ {
+ pd_data pd = partial_defs.pop ();
+ if (TREE_CODE (pd.rhs) == CONSTRUCTOR)
+ /* Empty CONSTRUCTOR. */
+ memset (buffer + MAX (0, pd.offset),
+ 0, MIN ((HOST_WIDE_INT)sizeof (buffer) - MAX (0, pd.offset),
+ pd.size + MIN (0, pd.offset)));
+ else
+ {
+ unsigned pad = 0;
+ if (BYTES_BIG_ENDIAN
+ && is_a <scalar_mode> (TYPE_MODE (TREE_TYPE (pd.rhs))))
+ {
+ /* On big-endian the padding is at the 'front' so just skip
+ the initial bytes. */
+ fixed_size_mode mode
+ = as_a <fixed_size_mode> (TYPE_MODE (TREE_TYPE (pd.rhs)));
+ pad = GET_MODE_SIZE (mode) - pd.size;
+ }
+ len = native_encode_expr (pd.rhs, buffer + MAX (0, pd.offset),
+ sizeof (buffer) - MAX (0, pd.offset),
+ MAX (0, -pd.offset) + pad);
+ if (len <= 0 || len < (pd.size - MAX (0, -pd.offset)))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Failed to encode %u "
+ "partial definitions\n", ndefs);
+ return (void *)-1;
+ }
+ }
+ }
+
+ tree type = vr->type;
+ /* Make sure to interpret in a type that has a range covering the whole
+ access size. */
+ if (INTEGRAL_TYPE_P (vr->type) && maxsizei != TYPE_PRECISION (vr->type))
+ type = build_nonstandard_integer_type (maxsizei, TYPE_UNSIGNED (type));
+ tree val = native_interpret_expr (type, buffer, maxsizei / BITS_PER_UNIT);
+ /* If we chop off bits because the types precision doesn't match the memory
+ access size this is ok when optimizing reads but not when called from
+ the DSE code during elimination. */
+ if (val && type != vr->type)
+ {
+ if (! int_fits_type_p (val, vr->type))
+ val = NULL_TREE;
+ else
+ val = fold_convert (vr->type, val);
+ }
+
+ if (val)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Successfully combined %u partial definitions\n", ndefs);
+ return vn_reference_lookup_or_insert_for_pieces
+ (first_vuse, vr->set, vr->type, vr->operands, val);
+ }
+ else
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Failed to interpret %u encoded partial definitions\n", ndefs);
+ return (void *)-1;
+ }
+}
+