On Fri, May 27, 2011 at 10:54 AM, Jan Hubicka <hubi...@ucw.cz> wrote:
> Hi,
> here is updated patch incorporating the feedback. I now use variant of uleb
> format,
> just do 4 bit chunks instead of 8bit. It works better in my tests and is also
> used
> by LLVM so it must be cool ;)
>
> I also fixed off by one error in filename streaming. While debugging this I
> noticed that bitpack will have random effect when the value passed does not
> fit
> in range (i.e. the bits will end up in next packed values). Adding assert on
> this
> I found one place where we try to pack negative value in it. Fixed by using
> my
> new functions, but wonder what the logic of code is, given that we always
> pack 0 or -1 as alias set.
Yeah, I think diego noticed this as well.
Micha has a point in that everything should be a single bitpack which
suitable points of re-alignment (to also make optimizing the packing
possible). But that's more work and can be done on top of this.
> Bootstrapped/regtested x86_64-linux, OK?
Ok.
Thanks,
Richard.
> * lto-streamer-out.c (lto_string_index): break out from...; offset by 1
> so 0 means NULL string.
> (lto_output_string_with_length): ... here.
> (lto_output_string, output_string_cst, output_identifier): Update
> handling
> of NULL strings.
> (lto_output_location_bitpack): New function.
> (lto_output_location): Use it.
> (lto_output_tree_ref): Use output_record_start.
> (pack_ts_type_common_value_fields): Pack aliagn & alias set in var len
> values.
> * lto-streamer-in.c (string_for_index): Break out from ...; offset
> values by 1.
> (input_string_internal): ... here;
> (input_string_cst, input_identifier, lto_input_string): Update
> handling of NULL strings.
> (lto_input_location_bitpack): New function
> (lto_input_location): Use it.
> (unpack_ts_type_common_value_fields): Pack align & alias in var len
> values.
> * lto-streamer.h (bp_pack_val_len_unsigned, bp_pack_val_len_int,
> bp_unpack_val_len_unsigned, bp_unpack_val_len_int): Declare.
> (bp_pack_value): Sanity check the value range.
> * lto-section-in.c (bp_unpack_val_len_unsigned, bp_unpack_val_len_int):
> New functions.
> * lto-section-out.h (bp_pack_val_len_unsigned, bp_pack_val_len_int):
> New functions.
> Index: lto-streamer-out.c
> ===================================================================
> *** lto-streamer-out.c (revision 174268)
> --- lto-streamer-out.c (working copy)
> *************** destroy_output_block (struct output_bloc
> *** 143,158 ****
> free (ob);
> }
>
> !
> ! /* Output STRING of LEN characters to the string
> ! table in OB. The string might or might not include a trailing '\0'.
> Then put the index onto the INDEX_STREAM. */
>
> ! void
> ! lto_output_string_with_length (struct output_block *ob,
> ! struct lto_output_stream *index_stream,
> ! const char *s,
> ! unsigned int len)
> {
> struct string_slot **slot;
> struct string_slot s_slot;
> --- 143,156 ----
> free (ob);
> }
>
> ! /* Return index used to reference STRING of LEN characters in the string
> table
> ! in OB. The string might or might not include a trailing '\0'.
> Then put the index onto the INDEX_STREAM. */
>
> ! static unsigned
> ! lto_string_index (struct output_block *ob,
> ! const char *s,
> ! unsigned int len)
> {
> struct string_slot **slot;
> struct string_slot s_slot;
> *************** lto_output_string_with_length (struct ou
> *** 164,172 ****
> s_slot.len = len;
> s_slot.slot_num = 0;
>
> - /* Indicate that this is not a NULL string. */
> - lto_output_uleb128_stream (index_stream, 0);
> -
> slot = (struct string_slot **) htab_find_slot (ob->string_hash_table,
> &s_slot, INSERT);
> if (*slot == NULL)
> --- 162,167 ----
> *************** lto_output_string_with_length (struct ou
> *** 180,197 ****
> new_slot->len = len;
> new_slot->slot_num = start;
> *slot = new_slot;
> - lto_output_uleb128_stream (index_stream, start);
> lto_output_uleb128_stream (string_stream, len);
> lto_output_data_stream (string_stream, string, len);
> }
> else
> {
> struct string_slot *old_slot = *slot;
> - lto_output_uleb128_stream (index_stream, old_slot->slot_num);
> free (string);
> }
> }
>
> /* Output the '\0' terminated STRING to the string
> table in OB. Then put the index onto the INDEX_STREAM. */
>
> --- 175,207 ----
> new_slot->len = len;
> new_slot->slot_num = start;
> *slot = new_slot;
> lto_output_uleb128_stream (string_stream, len);
> lto_output_data_stream (string_stream, string, len);
> + return start + 1;
> }
> else
> {
> struct string_slot *old_slot = *slot;
> free (string);
> + return old_slot->slot_num + 1;
> }
> }
>
> +
> + /* Output STRING of LEN characters to the string
> + table in OB. The string might or might not include a trailing '\0'.
> + Then put the index onto the INDEX_STREAM. */
> +
> + void
> + lto_output_string_with_length (struct output_block *ob,
> + struct lto_output_stream *index_stream,
> + const char *s,
> + unsigned int len)
> + {
> + lto_output_uleb128_stream (index_stream,
> + lto_string_index (ob, s, len));
> + }
> +
> /* Output the '\0' terminated STRING to the string
> table in OB. Then put the index onto the INDEX_STREAM. */
>
> *************** lto_output_string (struct output_block *
> *** 204,210 ****
> lto_output_string_with_length (ob, index_stream, string,
> strlen (string) + 1);
> else
> ! lto_output_uleb128_stream (index_stream, 1);
> }
>
>
> --- 214,220 ----
> lto_output_string_with_length (ob, index_stream, string,
> strlen (string) + 1);
> else
> ! lto_output_1_stream (index_stream, 0);
> }
>
>
> *************** output_string_cst (struct output_block *
> *** 221,227 ****
> TREE_STRING_POINTER (string),
> TREE_STRING_LENGTH (string ));
> else
> ! lto_output_uleb128_stream (index_stream, 1);
> }
>
>
> --- 231,237 ----
> TREE_STRING_POINTER (string),
> TREE_STRING_LENGTH (string ));
> else
> ! lto_output_1_stream (index_stream, 0);
> }
>
>
> *************** output_identifier (struct output_block *
> *** 238,246 ****
> IDENTIFIER_POINTER (id),
> IDENTIFIER_LENGTH (id));
> else
> ! lto_output_uleb128_stream (index_stream, 1);
> }
>
> /* Write a zero to the output stream. */
>
> static void
> --- 248,257 ----
> IDENTIFIER_POINTER (id),
> IDENTIFIER_LENGTH (id));
> else
> ! lto_output_1_stream (index_stream, 0);
> }
>
> +
> /* Write a zero to the output stream. */
>
> static void
> *************** pack_ts_type_common_value_fields (struct
> *** 504,511 ****
> bp_pack_value (bp, TYPE_CONTAINS_PLACEHOLDER_INTERNAL (expr), 2);
> bp_pack_value (bp, TYPE_USER_ALIGN (expr), 1);
> bp_pack_value (bp, TYPE_READONLY (expr), 1);
> ! bp_pack_value (bp, TYPE_ALIGN (expr), HOST_BITS_PER_INT);
> ! bp_pack_value (bp, TYPE_ALIAS_SET (expr) == 0 ? 0 : -1,
> HOST_BITS_PER_INT);
> }
>
>
> --- 515,522 ----
> bp_pack_value (bp, TYPE_CONTAINS_PLACEHOLDER_INTERNAL (expr), 2);
> bp_pack_value (bp, TYPE_USER_ALIGN (expr), 1);
> bp_pack_value (bp, TYPE_READONLY (expr), 1);
> ! bp_pack_var_len_unsigned (bp, TYPE_ALIGN (expr));
> ! bp_pack_var_len_int (bp, TYPE_ALIAS_SET (expr) == 0 ? 0 : -1);
> }
>
>
> *************** pack_value_fields (struct bitpack_d *bp,
> *** 587,618 ****
> }
>
>
> ! /* Emit location LOC to output block OB. */
>
> ! static void
> ! lto_output_location (struct output_block *ob, location_t loc)
> {
> expanded_location xloc;
>
> if (loc == UNKNOWN_LOCATION)
> ! {
> ! lto_output_string (ob, ob->main_stream, NULL);
> ! return;
> ! }
>
> xloc = expand_location (loc);
>
> ! lto_output_string (ob, ob->main_stream, xloc.file);
> ! output_sleb128 (ob, xloc.line);
> ! output_sleb128 (ob, xloc.column);
> ! output_sleb128 (ob, xloc.sysp);
> !
> ob->current_file = xloc.file;
> ob->current_line = xloc.line;
> ob->current_col = xloc.column;
> }
>
>
> /* Return true if tree node T is written to various tables. For these
> nodes, we sometimes want to write their phyiscal representation
> (via lto_output_tree), and sometimes we need to emit an index
> --- 598,652 ----
> }
>
>
> ! /* Output info about new location into bitpack BP.
> ! After outputting bitpack, lto_output_location_data has
> ! to be done to output actual data. */
>
> ! static inline void
> ! lto_output_location_bitpack (struct bitpack_d *bp,
> ! struct output_block *ob,
> ! location_t loc)
> {
> expanded_location xloc;
>
> + bp_pack_value (bp, loc == UNKNOWN_LOCATION, 1);
> if (loc == UNKNOWN_LOCATION)
> ! return;
>
> xloc = expand_location (loc);
>
> ! bp_pack_value (bp, ob->current_file != xloc.file, 1);
> ! if (ob->current_file != xloc.file)
> ! bp_pack_var_len_unsigned (bp, lto_string_index (ob,
> ! xloc.file,
> ! strlen (xloc.file) + 1));
> ob->current_file = xloc.file;
> +
> + bp_pack_value (bp, ob->current_line != xloc.line, 1);
> + if (ob->current_line != xloc.line)
> + bp_pack_var_len_unsigned (bp, xloc.line);
> ob->current_line = xloc.line;
> +
> + bp_pack_value (bp, ob->current_col != xloc.column, 1);
> + if (ob->current_col != xloc.column)
> + bp_pack_var_len_unsigned (bp, xloc.column);
> ob->current_col = xloc.column;
> }
>
>
> + /* Emit location LOC to output block OB.
> + When bitpack is handy, it is more space effecient to call
> + lto_output_location_bitpack with existing bitpack. */
> +
> + static void
> + lto_output_location (struct output_block *ob, location_t loc)
> + {
> + struct bitpack_d bp = bitpack_create (ob->main_stream);
> + lto_output_location_bitpack (&bp, ob, loc);
> + lto_output_bitpack (&bp);
> + }
> +
> +
> /* Return true if tree node T is written to various tables. For these
> nodes, we sometimes want to write their phyiscal representation
> (via lto_output_tree), and sometimes we need to emit an index
> *************** lto_output_tree_ref (struct output_block
> *** 642,648 ****
>
> if (expr == NULL_TREE)
> {
> ! output_zero (ob);
> return;
> }
>
> --- 676,682 ----
>
> if (expr == NULL_TREE)
> {
> ! output_record_start (ob, LTO_null);
> return;
> }
>
> Index: lto-streamer-in.c
> ===================================================================
> *** lto-streamer-in.c (revision 174268)
> --- lto-streamer-in.c (working copy)
> *************** eq_string_slot_node (const void *p1, con
> *** 132,150 ****
> IB. Write the length to RLEN. */
>
> static const char *
> ! input_string_internal (struct data_in *data_in, struct lto_input_block *ib,
> ! unsigned int *rlen)
> {
> struct lto_input_block str_tab;
> unsigned int len;
> - unsigned int loc;
> const char *result;
>
> ! /* Read the location of the string from IB. */
> ! loc = lto_input_uleb128 (ib);
>
> /* Get the string stored at location LOC in DATA_IN->STRINGS. */
> ! LTO_INIT_INPUT_BLOCK (str_tab, data_in->strings, loc,
> data_in->strings_len);
> len = lto_input_uleb128 (&str_tab);
> *rlen = len;
>
> --- 132,153 ----
> IB. Write the length to RLEN. */
>
> static const char *
> ! string_for_index (struct data_in *data_in,
> ! unsigned int loc,
> ! unsigned int *rlen)
> {
> struct lto_input_block str_tab;
> unsigned int len;
> const char *result;
>
> ! if (!loc)
> ! {
> ! *rlen = 0;
> ! return NULL;
> ! }
>
> /* Get the string stored at location LOC in DATA_IN->STRINGS. */
> ! LTO_INIT_INPUT_BLOCK (str_tab, data_in->strings, loc - 1,
> data_in->strings_len);
> len = lto_input_uleb128 (&str_tab);
> *rlen = len;
>
> *************** input_string_internal (struct data_in *d
> *** 157,162 ****
> --- 160,176 ----
> }
>
>
> + /* Read a string from the string table in DATA_IN using input block
> + IB. Write the length to RLEN. */
> +
> + static const char *
> + input_string_internal (struct data_in *data_in, struct lto_input_block *ib,
> + unsigned int *rlen)
> + {
> + return string_for_index (data_in, lto_input_uleb128 (ib), rlen);
> + }
> +
> +
> /* Read a STRING_CST from the string table in DATA_IN using input
> block IB. */
>
> *************** input_string_cst (struct data_in *data_i
> *** 165,177 ****
> {
> unsigned int len;
> const char * ptr;
> - unsigned int is_null;
> -
> - is_null = lto_input_uleb128 (ib);
> - if (is_null)
> - return NULL;
>
> ptr = input_string_internal (data_in, ib, &len);
> return build_string (len, ptr);
> }
>
> --- 179,188 ----
> {
> unsigned int len;
> const char * ptr;
>
> ptr = input_string_internal (data_in, ib, &len);
> + if (!ptr)
> + return NULL;
> return build_string (len, ptr);
> }
>
> *************** input_identifier (struct data_in *data_i
> *** 184,196 ****
> {
> unsigned int len;
> const char *ptr;
> - unsigned int is_null;
> -
> - is_null = lto_input_uleb128 (ib);
> - if (is_null)
> - return NULL;
>
> ptr = input_string_internal (data_in, ib, &len);
> return get_identifier_with_length (ptr, len);
> }
>
> --- 195,204 ----
> {
> unsigned int len;
> const char *ptr;
>
> ptr = input_string_internal (data_in, ib, &len);
> + if (!ptr)
> + return NULL;
> return get_identifier_with_length (ptr, len);
> }
>
> *************** lto_input_string (struct data_in *data_i
> *** 215,227 ****
> {
> unsigned int len;
> const char *ptr;
> - unsigned int is_null;
> -
> - is_null = lto_input_uleb128 (ib);
> - if (is_null)
> - return NULL;
>
> ptr = input_string_internal (data_in, ib, &len);
> if (ptr[len - 1] != '\0')
> internal_error ("bytecode stream: found non-null terminated string");
>
> --- 223,232 ----
> {
> unsigned int len;
> const char *ptr;
>
> ptr = input_string_internal (data_in, ib, &len);
> + if (!ptr)
> + return NULL;
> if (ptr[len - 1] != '\0')
> internal_error ("bytecode stream: found non-null terminated string");
>
> *************** clear_line_info (struct data_in *data_in
> *** 284,320 ****
> }
>
>
> ! /* Read a location from input block IB. */
>
> static location_t
> ! lto_input_location (struct lto_input_block *ib, struct data_in *data_in)
> {
> ! expanded_location xloc;
>
> ! xloc.file = lto_input_string (data_in, ib);
> ! if (xloc.file == NULL)
> return UNKNOWN_LOCATION;
>
> ! xloc.file = canon_file_name (xloc.file);
> ! xloc.line = lto_input_sleb128 (ib);
> ! xloc.column = lto_input_sleb128 (ib);
> ! xloc.sysp = lto_input_sleb128 (ib);
>
> ! if (data_in->current_file != xloc.file)
> {
> ! if (data_in->current_file)
> linemap_add (line_table, LC_LEAVE, false, NULL, 0);
>
> ! linemap_add (line_table, LC_ENTER, xloc.sysp, xloc.file, xloc.line);
> }
> ! else if (data_in->current_line != xloc.line)
> ! linemap_line_start (line_table, xloc.line, xloc.column);
>
> - data_in->current_file = xloc.file;
> - data_in->current_line = xloc.line;
> - data_in->current_col = xloc.column;
>
> ! return linemap_position_for_column (line_table, xloc.column);
> }
>
>
> --- 289,345 ----
> }
>
>
> ! /* Read a location bitpack from input block IB. */
>
> static location_t
> ! lto_input_location_bitpack (struct data_in *data_in, struct bitpack_d *bp)
> {
> ! bool file_change, line_change, column_change;
> ! unsigned len;
> ! bool prev_file = data_in->current_file != NULL;
>
> ! if (bp_unpack_value (bp, 1))
> return UNKNOWN_LOCATION;
>
> ! file_change = bp_unpack_value (bp, 1);
> ! if (file_change)
> ! data_in->current_file = canon_file_name
> ! (string_for_index (data_in,
> ! bp_unpack_var_len_unsigned
> (bp),
> ! &len));
> !
> ! line_change = bp_unpack_value (bp, 1);
> ! if (line_change)
> ! data_in->current_line = bp_unpack_var_len_unsigned (bp);
> !
> ! column_change = bp_unpack_value (bp, 1);
> ! if (column_change)
> ! data_in->current_col = bp_unpack_var_len_unsigned (bp);
>
> ! if (file_change)
> {
> ! if (prev_file)
> linemap_add (line_table, LC_LEAVE, false, NULL, 0);
>
> ! linemap_add (line_table, LC_ENTER, false, data_in->current_file,
> ! data_in->current_line);
> }
> ! else if (line_change)
> ! linemap_line_start (line_table, data_in->current_line,
> data_in->current_col);
> !
> ! return linemap_position_for_column (line_table, data_in->current_col);
> ! }
>
>
> ! /* Read a location from input block IB. */
> !
> ! static location_t
> ! lto_input_location (struct lto_input_block *ib, struct data_in *data_in)
> ! {
> ! struct bitpack_d bp;
> !
> ! bp = lto_input_bitpack (ib);
> ! return lto_input_location_bitpack (data_in, &bp);
> }
>
>
> *************** unpack_ts_type_common_value_fields (stru
> *** 1766,1773 ****
> = (unsigned) bp_unpack_value (bp, 2);
> TYPE_USER_ALIGN (expr) = (unsigned) bp_unpack_value (bp, 1);
> TYPE_READONLY (expr) = (unsigned) bp_unpack_value (bp, 1);
> ! TYPE_ALIGN (expr) = (unsigned) bp_unpack_value (bp, HOST_BITS_PER_INT);
> ! TYPE_ALIAS_SET (expr) = bp_unpack_value (bp, HOST_BITS_PER_INT);
> }
>
>
> --- 1791,1798 ----
> = (unsigned) bp_unpack_value (bp, 2);
> TYPE_USER_ALIGN (expr) = (unsigned) bp_unpack_value (bp, 1);
> TYPE_READONLY (expr) = (unsigned) bp_unpack_value (bp, 1);
> ! TYPE_ALIGN (expr) = bp_unpack_var_len_unsigned (bp);
> ! TYPE_ALIAS_SET (expr) = bp_unpack_var_len_int (bp);
> }
>
>
> Index: lto-section-in.c
> ===================================================================
> *** lto-section-in.c (revision 174268)
> --- lto-section-in.c (working copy)
> *************** lto_input_sleb128 (struct lto_input_bloc
> *** 127,132 ****
> --- 127,177 ----
> }
>
>
> + /* Unpack VAL from BP in a variant of uleb format. */
> +
> + unsigned HOST_WIDE_INT
> + bp_unpack_var_len_unsigned (struct bitpack_d *bp)
> + {
> + unsigned HOST_WIDE_INT result = 0;
> + int shift = 0;
> + unsigned HOST_WIDE_INT half_byte;
> +
> + while (true)
> + {
> + half_byte = bp_unpack_value (bp, 4);
> + result |= (half_byte & 0x7) << shift;
> + shift += 3;
> + if ((half_byte & 0x8) == 0)
> + return result;
> + }
> + }
> +
> +
> + /* Unpack VAL from BP in a variant of sleb format. */
> +
> + HOST_WIDE_INT
> + bp_unpack_var_len_int (struct bitpack_d *bp)
> + {
> + HOST_WIDE_INT result = 0;
> + int shift = 0;
> + unsigned HOST_WIDE_INT half_byte;
> +
> + while (true)
> + {
> + half_byte = bp_unpack_value (bp, 4);
> + result |= (half_byte & 0x7) << shift;
> + shift += 3;
> + if ((half_byte & 0x8) == 0)
> + {
> + if ((shift < HOST_BITS_PER_WIDE_INT) && (half_byte & 0x4))
> + result |= - ((HOST_WIDE_INT)1 << shift);
> +
> + return result;
> + }
> + }
> + }
> +
> +
> /* Hooks so that the ipa passes can call into the lto front end to get
> sections. */
>
> Index: lto-section-out.c
> ===================================================================
> *** lto-section-out.c (revision 174268)
> --- lto-section-out.c (working copy)
> *************** lto_output_sleb128_stream (struct lto_ou
> *** 330,335 ****
> --- 330,377 ----
> }
>
>
> + /* Pack WORK into BP in a variant of uleb format. */
> +
> + void
> + bp_pack_var_len_unsigned (struct bitpack_d *bp, unsigned HOST_WIDE_INT work)
> + {
> + do
> + {
> + unsigned int half_byte = (work & 0x7);
> + work >>= 3;
> + if (work != 0)
> + /* More half_bytes to follow. */
> + half_byte |= 0x8;
> +
> + bp_pack_value (bp, half_byte, 4);
> + }
> + while (work != 0);
> + }
> +
> +
> + /* Pack WORK into BP in a variant of sleb format. */
> +
> + void
> + bp_pack_var_len_int (struct bitpack_d *bp, HOST_WIDE_INT work)
> + {
> + int more, half_byte;
> +
> + do
> + {
> + half_byte = (work & 0x7);
> + /* arithmetic shift */
> + work >>= 3;
> + more = !((work == 0 && (half_byte & 0x4) == 0)
> + || (work == -1 && (half_byte & 0x4) != 0));
> + if (more)
> + half_byte |= 0x8;
> +
> + bp_pack_value (bp, half_byte, 4);
> + }
> + while (more);
> + }
> +
> +
> /* Lookup NAME in ENCODER. If NAME is not found, create a new entry in
> ENCODER for NAME with the next available index of ENCODER, then
> print the index to OBS. True is returned if NAME was added to
> Index: lto-streamer.h
> ===================================================================
> *** lto-streamer.h (revision 174268)
> --- lto-streamer.h (working copy)
> *************** extern void lto_section_overrun (struct
> *** 774,779 ****
> --- 774,783 ----
> extern void lto_value_range_error (const char *,
> HOST_WIDE_INT, HOST_WIDE_INT,
> HOST_WIDE_INT) ATTRIBUTE_NORETURN;
> + extern void bp_pack_var_len_unsigned (struct bitpack_d *, unsigned
> HOST_WIDE_INT);
> + extern void bp_pack_var_len_int (struct bitpack_d *, HOST_WIDE_INT);
> + extern unsigned HOST_WIDE_INT bp_unpack_var_len_unsigned (struct bitpack_d
> *);
> + extern HOST_WIDE_INT bp_unpack_var_len_int (struct bitpack_d *);
>
> /* In lto-section-out.c */
> extern hashval_t lto_hash_decl_slot_node (const void *);
> *************** bp_pack_value (struct bitpack_d *bp, bit
> *** 1110,1115 ****
> --- 1114,1124 ----
> {
> bitpack_word_t word = bp->word;
> int pos = bp->pos;
> +
> + /* Verify that VAL fits in the NBITS. */
> + gcc_checking_assert (nbits == BITS_PER_BITPACK_WORD
> + || !(val & ~(((bitpack_word_t)1<<nbits)-1)));
> +
> /* If val does not fit into the current bitpack word switch to the
> next one. */
> if (pos + nbits > BITS_PER_BITPACK_WORD)
>
