Better location streaming

Better location streaming

[Jan Hubicka]

Hi,
we spend a lot of effort (and disk space) into streaming file/line/column and
sys_p fields of locations. Since often the trees come from same statement, it
is common for those to not change.  We even already have current location info
in output_block and data_in, but don't use it.

This patch update streaming to stream first bitpack of what changed and then
streaming only the changed locations.  Because I did not find any use of
insys_p field in the backend, I removed streaming it (though it would be easy
doable to stream it along the file info).

Because we need only 4 bits, it would make a lot of sense to merge location
bitpack with the other bitpack and for this reason I split the i/o intput part
doing bitpack and part streaming the actual data.  At the moment we always do
that at once, since doing anything saner needs a bit of reorganization of how
we stream trees.

Regtested x86_64-linux, full bootstrap&regtest running, OK?

Honza

	* lto-streamer-out.c (clear_line_info): Set location_output_done.
	(lto_output_location_bitpack): New function.
	(lto_output_location_data): New function.
	(lto_output_location): Reorg.
	* lto-streamer-in.c (clear_line_info): Set location_input_done.
	(lto_input_location_bitpack): New function.
	(lto_input_location_data): New function.
	(lto_input_location): Reorg.
	* lto-streamer.h (struct output_block): Add output_file, output_line,
	output_col and location_output_done flags.
	(struct data_in): Add input_file, input_line, input_col and
	location_input_done flags.
Index: lto-streamer-out.c
===================================================================
--- lto-streamer-out.c	(revision 174264)
+++ lto-streamer-out.c	(working copy)
@@ -95,6 +95,7 @@ clear_line_info (struct output_block *ob
   ob->current_file = NULL;
   ob->current_line = 0;
   ob->current_col = 0;
+  ob->location_output_done = 1;
 }
 
 
@@ -587,29 +588,72 @@ pack_value_fields (struct bitpack_d *bp,
 }
 
 
-/* Emit location LOC to output block OB.  */
+/* 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)
+{
+  gcc_checking_assert (ob->location_output_done);
+  bp_pack_value (bp, loc == UNKNOWN_LOCATION, 1);
+  if (loc == UNKNOWN_LOCATION)
+    ob->output_file = ob->output_line = ob->output_col = 0;
+  else
+    {
+      expanded_location xloc;
+
+      xloc = expand_location (loc);
+
+      ob->output_file = xloc.file != ob->current_file;
+      ob->output_line = xloc.line != ob->current_line;
+      ob->output_col = xloc.column != ob->current_col;
+    }
+  bp_pack_value (bp, ob->output_file, 1);
+  bp_pack_value (bp, ob->output_line, 1);
+  bp_pack_value (bp, ob->output_col, 1);
+  ob->location_output_done = false;
+}
+
+
+/* Output location info we prepared to output in
+   lto_output_location_bitpack  */
 
 static void
-lto_output_location (struct output_block *ob, location_t loc)
+lto_output_location_data (struct output_block *ob)
 {
-  expanded_location xloc;
+  gcc_checking_assert (!ob->location_output_done);
 
-  if (loc == UNKNOWN_LOCATION)
+  if (ob->output_file)
+    lto_output_string (ob, ob->main_stream, ob->current_file);
+  if (ob->output_line)
     {
-      lto_output_string (ob, ob->main_stream, NULL);
-      return;
+      gcc_checking_assert (ob->current_line >= 0);
+      output_uleb128 (ob, ob->current_line);
     }
+  if (ob->output_col)
+    {
+      gcc_checking_assert (ob->current_col >= 0);
+      output_uleb128 (ob, ob->current_col);
+    }
+  ob->location_output_done = true;
+}
 
-  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;
+/* Emit location LOC to output block OB.
+   When bitpack is handy, it is more space effecient to call
+   lto_output_location_bitpack and lto_output_location_data directly
+   adding info into the 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);
+  lto_output_location_data (ob);
 }
 
 
@@ -642,7 +686,7 @@ lto_output_tree_ref (struct output_block
 
   if (expr == NULL_TREE)
     {
-      output_zero (ob);
+      output_record_start (ob, LTO_null);
       return;
     }
 
Index: lto-streamer-in.c
===================================================================
--- lto-streamer-in.c	(revision 174264)
+++ lto-streamer-in.c	(working copy)
@@ -281,40 +281,69 @@ clear_line_info (struct data_in *data_in
   data_in->current_file = NULL;
   data_in->current_line = 0;
   data_in->current_col = 0;
+  data_in->location_input_done = true;
 }
 
 
-/* Read a location from input block IB.  */
+/* Read a location bitpack from input block IB.  */
+
+static inline void
+lto_input_location_bitpack (struct data_in *data_in, struct bitpack_d *bp)
+{
+  gcc_checking_assert (data_in->location_input_done);
+  data_in->location_input_done = false;
+  data_in->input_unknown_location = bp_unpack_value (bp, 1);
+  data_in->input_file_p = bp_unpack_value (bp, 1);
+  data_in->input_line_p = bp_unpack_value (bp, 1);
+  data_in->input_col_p = bp_unpack_value (bp, 1);
+}
+
+
+/* Read locaiton data we determined to change and update info.  */
 
 static location_t
-lto_input_location (struct lto_input_block *ib, struct data_in *data_in)
+lto_input_location_data (struct lto_input_block *ib, struct data_in *data_in)
 {
-  expanded_location xloc;
+  bool prev_file = data_in->current_file != NULL;
 
-  xloc.file = lto_input_string (data_in, ib);
-  if (xloc.file == NULL)
+  gcc_checking_assert (!data_in->location_input_done);
+  data_in->location_input_done = true;
+  if (data_in->input_unknown_location)
     return UNKNOWN_LOCATION;
+  if (data_in->input_file_p)
+    {
+      data_in->current_file = lto_input_string (data_in, ib);
+      data_in->current_file = canon_file_name (data_in->current_file);
+    }
+  if (data_in->input_line_p)
+    data_in->current_line = lto_input_uleb128 (ib);
+  if (data_in->input_col_p)
+    data_in->current_col = lto_input_uleb128 (ib);
 
-  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->input_file_p)
     {
-      if (data_in->current_file)
+      if (prev_file)
 	linemap_add (line_table, LC_LEAVE, false, NULL, 0);
 
-      linemap_add (line_table, LC_ENTER, xloc.sysp, xloc.file, xloc.line);
+      linemap_add (line_table, LC_ENTER, false, data_in->current_file, data_in->current_line);
     }
-  else if (data_in->current_line != xloc.line)
-    linemap_line_start (line_table, xloc.line, xloc.column);
+  else if (data_in->input_line_p)
+    linemap_line_start (line_table, data_in->current_line, data_in->current_col);
 
-  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, 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;
 
-  return linemap_position_for_column (line_table, xloc.column);
+  bp = lto_input_bitpack (ib);
+  lto_input_location_bitpack (data_in, &bp);
+  return lto_input_location_data (ib, data_in);
 }
 
 
Index: lto-streamer.h
===================================================================
--- lto-streamer.h	(revision 174264)
+++ lto-streamer.h	(working copy)
@@ -694,6 +694,10 @@ struct output_block
   const char *current_file;
   int current_line;
   int current_col;
+  unsigned output_file : 1;
+  unsigned output_line : 1;
+  unsigned output_col : 1;
+  unsigned location_output_done : 1;
 
   /* True if writing globals and types.  */
   bool global;
@@ -728,6 +732,11 @@ struct data_in
   const char *current_file;
   int current_line;
   int current_col;
+  unsigned input_unknown_location : 1;
+  unsigned input_file_p : 1;
+  unsigned input_line_p : 1;
+  unsigned input_col_p : 1;
+  unsigned location_input_done : 1;
 
   /* Maps each reference number to the resolution done by the linker. */
   VEC(ld_plugin_symbol_resolution_t,heap) *globals_resolution;

Re: Better location streaming

[Richard Guenther]

On Thu, May 26, 2011 at 11:34 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> we spend a lot of effort (and disk space) into streaming file/line/column and
> sys_p fields of locations. Since often the trees come from same statement, it
> is common for those to not change.  We even already have current location info
> in output_block and data_in, but don't use it.
>
> This patch update streaming to stream first bitpack of what changed and then
> streaming only the changed locations.  Because I did not find any use of
> insys_p field in the backend, I removed streaming it (though it would be easy
> doable to stream it along the file info).
>
> Because we need only 4 bits, it would make a lot of sense to merge location
> bitpack with the other bitpack and for this reason I split the i/o intput part
> doing bitpack and part streaming the actual data.  At the moment we always do
> that at once, since doing anything saner needs a bit of reorganization of how
> we stream trees.
>
> Regtested x86_64-linux, full bootstrap&regtest running, OK?

This looks all very hackish with no immediate benefit mostly because
of the use of lto_output_string.  I think what you should do instead
is split up lto_output_string_with_length into the piece that streams
the string itself to the string-stream and returns an index into it
and the piece streaming the index to the specified stream.  Then you
can simply bitpack that index and the two int line / column fields.

Richard.

> Honza
>
>        * lto-streamer-out.c (clear_line_info): Set location_output_done.
>        (lto_output_location_bitpack): New function.
>        (lto_output_location_data): New function.
>        (lto_output_location): Reorg.
>        * lto-streamer-in.c (clear_line_info): Set location_input_done.
>        (lto_input_location_bitpack): New function.
>        (lto_input_location_data): New function.
>        (lto_input_location): Reorg.
>        * lto-streamer.h (struct output_block): Add output_file, output_line,
>        output_col and location_output_done flags.
>        (struct data_in): Add input_file, input_line, input_col and
>        location_input_done flags.
> Index: lto-streamer-out.c
> ===================================================================
> --- lto-streamer-out.c  (revision 174264)
> +++ lto-streamer-out.c  (working copy)
> @@ -95,6 +95,7 @@ clear_line_info (struct output_block *ob
>   ob->current_file = NULL;
>   ob->current_line = 0;
>   ob->current_col = 0;
> +  ob->location_output_done = 1;
>  }
>
>
> @@ -587,29 +588,72 @@ pack_value_fields (struct bitpack_d *bp,
>  }
>
>
> -/* Emit location LOC to output block OB.  */
> +/* 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)
> +{
> +  gcc_checking_assert (ob->location_output_done);
> +  bp_pack_value (bp, loc == UNKNOWN_LOCATION, 1);
> +  if (loc == UNKNOWN_LOCATION)
> +    ob->output_file = ob->output_line = ob->output_col = 0;
> +  else
> +    {
> +      expanded_location xloc;
> +
> +      xloc = expand_location (loc);
> +
> +      ob->output_file = xloc.file != ob->current_file;
> +      ob->output_line = xloc.line != ob->current_line;
> +      ob->output_col = xloc.column != ob->current_col;
> +    }
> +  bp_pack_value (bp, ob->output_file, 1);
> +  bp_pack_value (bp, ob->output_line, 1);
> +  bp_pack_value (bp, ob->output_col, 1);
> +  ob->location_output_done = false;
> +}
> +
> +
> +/* Output location info we prepared to output in
> +   lto_output_location_bitpack  */
>
>  static void
> -lto_output_location (struct output_block *ob, location_t loc)
> +lto_output_location_data (struct output_block *ob)
>  {
> -  expanded_location xloc;
> +  gcc_checking_assert (!ob->location_output_done);
>
> -  if (loc == UNKNOWN_LOCATION)
> +  if (ob->output_file)
> +    lto_output_string (ob, ob->main_stream, ob->current_file);
> +  if (ob->output_line)
>     {
> -      lto_output_string (ob, ob->main_stream, NULL);
> -      return;
> +      gcc_checking_assert (ob->current_line >= 0);
> +      output_uleb128 (ob, ob->current_line);
>     }
> +  if (ob->output_col)
> +    {
> +      gcc_checking_assert (ob->current_col >= 0);
> +      output_uleb128 (ob, ob->current_col);
> +    }
> +  ob->location_output_done = true;
> +}
>
> -  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;
> +/* Emit location LOC to output block OB.
> +   When bitpack is handy, it is more space effecient to call
> +   lto_output_location_bitpack and lto_output_location_data directly
> +   adding info into the 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);
> +  lto_output_location_data (ob);
>  }
>
>
> @@ -642,7 +686,7 @@ lto_output_tree_ref (struct output_block
>
>   if (expr == NULL_TREE)
>     {
> -      output_zero (ob);
> +      output_record_start (ob, LTO_null);

?

>       return;
>     }
>
> Index: lto-streamer-in.c
> ===================================================================
> --- lto-streamer-in.c   (revision 174264)
> +++ lto-streamer-in.c   (working copy)
> @@ -281,40 +281,69 @@ clear_line_info (struct data_in *data_in
>   data_in->current_file = NULL;
>   data_in->current_line = 0;
>   data_in->current_col = 0;
> +  data_in->location_input_done = true;
>  }
>
>
> -/* Read a location from input block IB.  */
> +/* Read a location bitpack from input block IB.  */
> +
> +static inline void
> +lto_input_location_bitpack (struct data_in *data_in, struct bitpack_d *bp)
> +{
> +  gcc_checking_assert (data_in->location_input_done);
> +  data_in->location_input_done = false;
> +  data_in->input_unknown_location = bp_unpack_value (bp, 1);
> +  data_in->input_file_p = bp_unpack_value (bp, 1);
> +  data_in->input_line_p = bp_unpack_value (bp, 1);
> +  data_in->input_col_p = bp_unpack_value (bp, 1);
> +}
> +
> +
> +/* Read locaiton data we determined to change and update info.  */
>
>  static location_t
> -lto_input_location (struct lto_input_block *ib, struct data_in *data_in)
> +lto_input_location_data (struct lto_input_block *ib, struct data_in *data_in)
>  {
> -  expanded_location xloc;
> +  bool prev_file = data_in->current_file != NULL;
>
> -  xloc.file = lto_input_string (data_in, ib);
> -  if (xloc.file == NULL)
> +  gcc_checking_assert (!data_in->location_input_done);
> +  data_in->location_input_done = true;
> +  if (data_in->input_unknown_location)
>     return UNKNOWN_LOCATION;
> +  if (data_in->input_file_p)
> +    {
> +      data_in->current_file = lto_input_string (data_in, ib);
> +      data_in->current_file = canon_file_name (data_in->current_file);
> +    }
> +  if (data_in->input_line_p)
> +    data_in->current_line = lto_input_uleb128 (ib);
> +  if (data_in->input_col_p)
> +    data_in->current_col = lto_input_uleb128 (ib);
>
> -  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->input_file_p)
>     {
> -      if (data_in->current_file)
> +      if (prev_file)
>        linemap_add (line_table, LC_LEAVE, false, NULL, 0);
>
> -      linemap_add (line_table, LC_ENTER, xloc.sysp, xloc.file, xloc.line);
> +      linemap_add (line_table, LC_ENTER, false, data_in->current_file, data_in->current_line);
>     }
> -  else if (data_in->current_line != xloc.line)
> -    linemap_line_start (line_table, xloc.line, xloc.column);
> +  else if (data_in->input_line_p)
> +    linemap_line_start (line_table, data_in->current_line, data_in->current_col);
>
> -  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, 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;
>
> -  return linemap_position_for_column (line_table, xloc.column);
> +  bp = lto_input_bitpack (ib);
> +  lto_input_location_bitpack (data_in, &bp);
> +  return lto_input_location_data (ib, data_in);
>  }
>
>
> Index: lto-streamer.h
> ===================================================================
> --- lto-streamer.h      (revision 174264)
> +++ lto-streamer.h      (working copy)
> @@ -694,6 +694,10 @@ struct output_block
>   const char *current_file;
>   int current_line;
>   int current_col;
> +  unsigned output_file : 1;
> +  unsigned output_line : 1;
> +  unsigned output_col : 1;
> +  unsigned location_output_done : 1;
>
>   /* True if writing globals and types.  */
>   bool global;
> @@ -728,6 +732,11 @@ struct data_in
>   const char *current_file;
>   int current_line;
>   int current_col;
> +  unsigned input_unknown_location : 1;
> +  unsigned input_file_p : 1;
> +  unsigned input_line_p : 1;
> +  unsigned input_col_p : 1;
> +  unsigned location_input_done : 1;
>
>   /* Maps each reference number to the resolution done by the linker. */
>   VEC(ld_plugin_symbol_resolution_t,heap) *globals_resolution;
>

Re: Better location streaming

[Jan Hubicka]

> 
> This looks all very hackish with no immediate benefit mostly because
> of the use of lto_output_string.  I think what you should do instead
> is split up lto_output_string_with_length into the piece that streams
> the string itself to the string-stream and returns an index into it
> and the piece streaming the index to the specified stream.  Then you
> can simply bitpack that index and the two int line / column fields.

Hmm, I plan to optimize string streaming (since we always stream one uleb to
set it is non-NULL that can be easilly handled by assigining NULL string index
0).  How precisely you however suggest to bitpack line/column and string offset
together?

The point is to make location info occupy not even whole byte most of time.
Adding a simple stats claims that for tramp3d 30% of time location is
undefined, 15% of time file changes, 39% of time line changes and 44% of time
column changes (on tramp3d).  So assuming one byte for each uleb (that is
optimistic, of course) one need 4 bits for the changed flags + less than a byte
for the data.  Situation is similar for combine.c where unknown id 10%, file
change is 0.5% and line change is 30%.

If we want to get fancy, we could probably mix index/line/column as you suggest
(so we will have only undefined bit and location change bit) and record only
changes to reduce uleb's range.

All location streaming I know of somehow takes advantage of fact that location
do not change completely all the time from one place to another.

Honza

Re: Better location streaming

[Jan Hubicka]

> > 
> > This looks all very hackish with no immediate benefit mostly because
> > of the use of lto_output_string.  I think what you should do instead
> > is split up lto_output_string_with_length into the piece that streams
> > the string itself to the string-stream and returns an index into it
> > and the piece streaming the index to the specified stream.  Then you
> > can simply bitpack that index and the two int line / column fields.
> 
> Hmm, I plan to optimize string streaming (since we always stream one uleb to
> set it is non-NULL that can be easilly handled by assigining NULL string index
> 0).  How precisely you however suggest to bitpack line/column and string offset
> together?
> 
> The point is to make location info occupy not even whole byte most of time.
> Adding a simple stats claims that for tramp3d 30% of time location is
> undefined, 15% of time file changes, 39% of time line changes and 44% of time
> column changes (on tramp3d).  So assuming one byte for each uleb (that is
> optimistic, of course) one need 4 bits for the changed flags + less than a byte
> for the data.  Situation is similar for combine.c where unknown id 10%, file
> change is 0.5% and line change is 30%.

Note that for tramp3d the function sections reduce in size by about 16%, decl
section by about 10%. So there is some immediate benefit.

Honza

Re: Better location streaming

[Richard Guenther]

On Thu, May 26, 2011 at 12:45 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>
>> This looks all very hackish with no immediate benefit mostly because
>> of the use of lto_output_string.  I think what you should do instead
>> is split up lto_output_string_with_length into the piece that streams
>> the string itself to the string-stream and returns an index into it
>> and the piece streaming the index to the specified stream.  Then you
>> can simply bitpack that index and the two int line / column fields.
>
> Hmm, I plan to optimize string streaming (since we always stream one uleb to
> set it is non-NULL that can be easilly handled by assigining NULL string index
> 0).  How precisely you however suggest to bitpack line/column and string offset
> together?

Similar to how you suggested, stream bits for a changed flag but
instead of finishing the bitpack simply stream HOST_BITS_PER_INT
bits for line (if changed), colunn (if changed) and file string index (if
changed and the index is 'int').

I mostly want to avoid the split between the changed bits and the
data output, esp. breaking the bitpack.

> The point is to make location info occupy not even whole byte most of time.
> Adding a simple stats claims that for tramp3d 30% of time location is
> undefined, 15% of time file changes, 39% of time line changes and 44% of time
> column changes (on tramp3d).  So assuming one byte for each uleb (that is
> optimistic, of course) one need 4 bits for the changed flags + less than a byte
> for the data.  Situation is similar for combine.c where unknown id 10%, file
> change is 0.5% and line change is 30%.
>
> If we want to get fancy, we could probably mix index/line/column as you suggest
> (so we will have only undefined bit and location change bit) and record only
> changes to reduce uleb's range.
>
> All location streaming I know of somehow takes advantage of fact that location
> do not change completely all the time from one place to another.
>
> Honza
>

Re: Better location streaming

[Jan Hubicka]

> On Thu, May 26, 2011 at 12:45 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >>
> >> This looks all very hackish with no immediate benefit mostly because
> >> of the use of lto_output_string.  I think what you should do instead
> >> is split up lto_output_string_with_length into the piece that streams
> >> the string itself to the string-stream and returns an index into it
> >> and the piece streaming the index to the specified stream.  Then you
> >> can simply bitpack that index and the two int line / column fields.
> >
> > Hmm, I plan to optimize string streaming (since we always stream one uleb to
> > set it is non-NULL that can be easilly handled by assigining NULL string index
> > 0).  How precisely you however suggest to bitpack line/column and string offset
> > together?
> 
> Similar to how you suggested, stream bits for a changed flag but
> instead of finishing the bitpack simply stream HOST_BITS_PER_INT
> bits for line (if changed), colunn (if changed) and file string index (if
> changed and the index is 'int').
> 
> I mostly want to avoid the split between the changed bits and the
> data output, esp. breaking the bitpack.

Well, that won't get me for < 1 byte overhead when location is unchanged or
unknown (that is true for about half of cases in my stats).  Additionally
HOST_BITS_PER_INT is host sensitive and wasteful compared to ulebs here as the
line numbers, file indexes and columns are all usually small numbers, so they
ought to fit in 16, 8 and 8 bits most of time.  So we would end up in need of
inventing something like uleb in bitpack?

Honza

Re: Better location streaming

[Richard Guenther]

2011/5/26 Jan Hubicka <hubicka@ucw.cz>:
>> On Thu, May 26, 2011 at 12:45 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >>
>> >> This looks all very hackish with no immediate benefit mostly because
>> >> of the use of lto_output_string.  I think what you should do instead
>> >> is split up lto_output_string_with_length into the piece that streams
>> >> the string itself to the string-stream and returns an index into it
>> >> and the piece streaming the index to the specified stream.  Then you
>> >> can simply bitpack that index and the two int line / column fields.
>> >
>> > Hmm, I plan to optimize string streaming (since we always stream one uleb to
>> > set it is non-NULL that can be easilly handled by assigining NULL string index
>> > 0).  How precisely you however suggest to bitpack line/column and string offset
>> > together?
>>
>> Similar to how you suggested, stream bits for a changed flag but
>> instead of finishing the bitpack simply stream HOST_BITS_PER_INT
>> bits for line (if changed), colunn (if changed) and file string index (if
>> changed and the index is 'int').
>>
>> I mostly want to avoid the split between the changed bits and the
>> data output, esp. breaking the bitpack.
>
> Well, that won't get me for < 1 byte overhead when location is unchanged or
> unknown (that is true for about half of cases in my stats).

Why not?  it would be 3 bits.

> Additionally
> HOST_BITS_PER_INT is host sensitive and wasteful compared to ulebs here as the
> line numbers, file indexes and columns are all usually small numbers, so they
> ought to fit in 16, 8 and 8 bits most of time.  So we would end up in need of
> inventing something like uleb in bitpack?

Well, we could do that by default for > 8 bit values we pack.  I think
the location CSE using only 3 bits for unchanged locations should
save the most, not so much the use of ulebs for line/column.
(you could also encode the number of  needed bytes for a changed
line/column and then only that many number of bytes).

Richard.

> Honza
>

Re: Better location streaming

[Jan Hubicka]

> 2011/5/26 Jan Hubicka <hubicka@ucw.cz>:
> >> On Thu, May 26, 2011 at 12:45 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> >>
> >> >> This looks all very hackish with no immediate benefit mostly because
> >> >> of the use of lto_output_string.  I think what you should do instead
> >> >> is split up lto_output_string_with_length into the piece that streams
> >> >> the string itself to the string-stream and returns an index into it
> >> >> and the piece streaming the index to the specified stream.  Then you
> >> >> can simply bitpack that index and the two int line / column fields.
> >> >
> >> > Hmm, I plan to optimize string streaming (since we always stream one uleb to
> >> > set it is non-NULL that can be easilly handled by assigining NULL string index
> >> > 0).  How precisely you however suggest to bitpack line/column and string offset
> >> > together?
> >>
> >> Similar to how you suggested, stream bits for a changed flag but
> >> instead of finishing the bitpack simply stream HOST_BITS_PER_INT
> >> bits for line (if changed), colunn (if changed) and file string index (if
> >> changed and the index is 'int').
> >>
> >> I mostly want to avoid the split between the changed bits and the
> >> data output, esp. breaking the bitpack.
> >
> > Well, that won't get me for < 1 byte overhead when location is unchanged or
> > unknown (that is true for about half of cases in my stats).
> 
> Why not?  it would be 3 bits.

Hmm, I see, so you suggest to move all the data into bitpack in order to couple
it with the bitpack in tree streaming w/o need to have two functions.  (i
originally understood the message as you are objecting to the idea of storing
only the changes).

I see one can save it into bitpack, though i was under impression that we want
to avoid variably sized bitpacks as then the accessors no longer expands to
simple arithmetics.
> 
> > Additionally
> > HOST_BITS_PER_INT is host sensitive and wasteful compared to ulebs here as the
> > line numbers, file indexes and columns are all usually small numbers, so they
> > ought to fit in 16, 8 and 8 bits most of time.  So we would end up in need of
> > inventing something like uleb in bitpack?
> 
> Well, we could do that by default for > 8 bit values we pack.  I think
> the location CSE using only 3 bits for unchanged locations should
> save the most, not so much the use of ulebs for line/column.
> (you could also encode the number of  needed bytes for a changed
> line/column and then only that many number of bytes).

Well, since almost half of time we save at least one of the 3 indices, I think the stupid
implementation would burn 3 bytes at average at least.  This would be sort of comparable
with the existing uleb path that is 5 bytes.

OK, if we want to go for variably sized bitpacks, I guess I can simply store number of bits
needed to represent the number followed by the number itself for all three indices.
It will need massaging string i/o together with the patch as currently string indexes
go into the ulebs.  Can do that if you think it is better option.

Do we have some limits on maximal bitpack size?

Honza

Re: Better location streaming

[Richard Guenther]

2011/5/26 Jan Hubicka <hubicka@ucw.cz>:
>> 2011/5/26 Jan Hubicka <hubicka@ucw.cz>:
>> >> On Thu, May 26, 2011 at 12:45 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >> >>
>> >> >> This looks all very hackish with no immediate benefit mostly because
>> >> >> of the use of lto_output_string.  I think what you should do instead
>> >> >> is split up lto_output_string_with_length into the piece that streams
>> >> >> the string itself to the string-stream and returns an index into it
>> >> >> and the piece streaming the index to the specified stream.  Then you
>> >> >> can simply bitpack that index and the two int line / column fields.
>> >> >
>> >> > Hmm, I plan to optimize string streaming (since we always stream one uleb to
>> >> > set it is non-NULL that can be easilly handled by assigining NULL string index
>> >> > 0).  How precisely you however suggest to bitpack line/column and string offset
>> >> > together?
>> >>
>> >> Similar to how you suggested, stream bits for a changed flag but
>> >> instead of finishing the bitpack simply stream HOST_BITS_PER_INT
>> >> bits for line (if changed), colunn (if changed) and file string index (if
>> >> changed and the index is 'int').
>> >>
>> >> I mostly want to avoid the split between the changed bits and the
>> >> data output, esp. breaking the bitpack.
>> >
>> > Well, that won't get me for < 1 byte overhead when location is unchanged or
>> > unknown (that is true for about half of cases in my stats).
>>
>> Why not?  it would be 3 bits.
>
> Hmm, I see, so you suggest to move all the data into bitpack in order to couple
> it with the bitpack in tree streaming w/o need to have two functions.  (i
> originally understood the message as you are objecting to the idea of storing
> only the changes).
>
> I see one can save it into bitpack, though i was under impression that we want
> to avoid variably sized bitpacks as then the accessors no longer expands to
> simple arithmetics.

Yeah, but we have this issue everywhere when conditionally saving bits,
so I wouldn't care that much - the code still is quite nice.

>>
>> > Additionally
>> > HOST_BITS_PER_INT is host sensitive and wasteful compared to ulebs here as the
>> > line numbers, file indexes and columns are all usually small numbers, so they
>> > ought to fit in 16, 8 and 8 bits most of time.  So we would end up in need of
>> > inventing something like uleb in bitpack?
>>
>> Well, we could do that by default for > 8 bit values we pack.  I think
>> the location CSE using only 3 bits for unchanged locations should
>> save the most, not so much the use of ulebs for line/column.
>> (you could also encode the number of  needed bytes for a changed
>> line/column and then only that many number of bytes).
>
> Well, since almost half of time we save at least one of the 3 indices, I think the stupid
> implementation would burn 3 bytes at average at least.  This would be sort of comparable
> with the existing uleb path that is 5 bytes.
>
> OK, if we want to go for variably sized bitpacks, I guess I can simply store number of bits
> needed to represent the number followed by the number itself for all three indices.
> It will need massaging string i/o together with the patch as currently string indexes
> go into the ulebs.  Can do that if you think it is better option.

Yes, I think so.

> Do we have some limits on maximal bitpack size?

No.

Richard.

> Honza
>

Re: Better location streaming

[Michael Matz]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 665 bytes --]

Hi,

On Thu, 26 May 2011, Richard Guenther wrote:

> > Hmm, I plan to optimize string streaming (since we always stream one 
> > uleb to set it is non-NULL that can be easilly handled by assigining 
> > NULL string index 0).  How precisely you however suggest to bitpack 
> > line/column and string offset together?
> 
> Similar to how you suggested, stream bits for a changed flag but instead 
> of finishing the bitpack simply stream HOST_BITS_PER_INT bits for line 

OMG, no.  Just write uleb outputters for bitpacks and use those.  In fact 
all outputs should just go through through bitpacks and properly align to 
byte border if necessary.


Ciao,
Michael.

Re: Better location streaming

[Jan Hubicka]

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.

Bootstrapped/regtested x86_64-linux, OK?

	* 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)

Re: Better location streaming

[Richard Guenther]

On Fri, May 27, 2011 at 10:54 AM, Jan Hubicka <hubicka@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)
>

Re: Better location streaming

[Jan Hubicka]

> On Fri, May 27, 2011 at 10:54 AM, Jan Hubicka <hubicka@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.

Yep, I tought of this a bit.  It will be fun to implement it in a way that resulting code
will be good (i.e. optimize well across the byte alignment points with word sized bitpack output
buffer)

Honza