[PATCH] Redesign jump threading profile updates

[PATCH] Redesign jump threading profile updates

[Teresa Johnson]

[-- Attachment #1: Type: text/plain, Size: 33319 bytes --]

Recently I discovered that the profile updates being performed by jump
threading were incorrect in many cases, particularly in the case where
the threading path contains a joiner. Some of the duplicated
blocks/edges were not getting any counts, leading to incorrect
function splitting and other downstream optimizations, and there were
other insanities as well. After making a few attempts to fix the
handling I ended up completely redesigning the profile update code,
removing a few places throughout the code where it was attempting to
do some updates.

The biggest complication (see the large comment and example above the
new routine compute_path_counts) is that we duplicate a conditional
jump in the joiner case, possibly multiple times for multiple jump
thread paths through that joiner, and it isn't trivial to figure out
what probability to assign each of the duplicated successor edges (and
the original after threading). Each jump thread path may need to have
a different probability of staying on path through the joiner in order
to keep the counts going out of the threading path sane.

The patch below was bootstrapped and tested on
x86_64-unknown-linux-gnu, and also tested with a profiledbootstrap. I
additionally tested with cpu2006, confirming that the amount of
resulting cycle samples in the split cold sections reduced, and
through manual inspection that many different cases were now correct.
I also measured performance with cpu2006, running each benchmark
multiple times on a Westmere and see some speedups (453.povray 1-2%,
403.gcc 1-1.5%, and noisy but positive speedups in 471.omnetpp and
483.xalancbmk).

Looks like my mailer is corrupting the spacing, which makes it harder
to look at the CFG examples in the big header comment block I added.
So I have also included the patch as an attachment.

Ok for stage 1?

Thanks,
Teresa

 2014-03-26  Teresa Johnson  <tejohnson@google.com>

        * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
        duplicate_blocks bitmap.
        (remove_ctrl_stmt_and_useless_edges): Ditto.
        (create_block_for_threading): Ditto.
        (compute_path_counts): New function.
        (update_profile): Ditto.
        (deduce_freq): Ditto.
        (recompute_probabilities): Ditto.
        (update_joiner_offpath_counts): Ditto.
        (ssa_fix_duplicate_block_edges): Update profile info.
        (ssa_create_duplicates): Pass new parameter.
        (ssa_redirect_edges): Remove old profile update.
        (thread_block_1): New duplicate_blocks bitmap,
        remove old profile update.
        (thread_single_edge): Pass new parameter.

Index: tree-ssa-threadupdate.c
===================================================================
--- tree-ssa-threadupdate.c     (revision 208491)
+++ tree-ssa-threadupdate.c     (working copy)
@@ -229,6 +229,9 @@ struct ssa_local_info_t

   /* TRUE if we thread one or more jumps, FALSE otherwise.  */
   bool jumps_threaded;
+
+  /* Blocks duplicated for the thread.  */
+  bitmap duplicate_blocks;
 };

 /* Passes which use the jump threading code register jump threading
@@ -292,7 +295,8 @@ remove_ctrl_stmt_and_useless_edges (basic_block bb
 static void
 create_block_for_threading (basic_block bb,
                            struct redirection_data *rd,
-                           unsigned int count)
+                           unsigned int count,
+                           bitmap *duplicate_blocks)
 {
   edge_iterator ei;
   edge e;
@@ -307,6 +311,8 @@ create_block_for_threading (basic_block bb,
   /* Zero out the profile, since the block is unreachable for now.  */
   rd->dup_blocks[count]->frequency = 0;
   rd->dup_blocks[count]->count = 0;
+  if (duplicate_blocks)
+    bitmap_set_bit (*duplicate_blocks, rd->dup_blocks[count]->index);
 }

 /* Main data structure to hold information for duplicates of BB.  */
@@ -495,17 +501,457 @@ any_remaining_duplicated_blocks (vec<jump_thread_e
   return false;
 }

+
+/* Compute the amount of profile count/frequency coming into the jump threading
+   path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
+   PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
+   duplicated path, returned in PATH_OUT_COUNT_PTR.  LOCAL_INFO is used to
+   identify blocks duplicated for jump threading, which have duplicated
+   edges that need to be ignored in the analysis.  Return true if path contains
+   a joiner, false otherwise.
+
+   In the non-joiner case, this is straightforward - all the counts/frequency
+   flowing into the jump threading path should flow through the duplicated
+   block and out of the duplicated path.
+
+   In the joiner case, it is very tricky.  Some of the counts flowing into
+   the original path go offpath at the joiner.  The problem is that while
+   we know how much total count goes off-path in the original control flow,
+   we don't know how many of the counts corresponding to just the jump
+   threading path go offpath at the joiner.
+
+   For example, assume we have the following control flow and identified
+   jump threading paths:
+
+                A     B     C
+                 \    |    /
+               Ea \   |Eb / Ec
+                   \  |  /
+                    v v v
+                      J       <-- Joiner
+                     / \
+                Eoff/   \Eon
+                   /     \
+                  v       v
+                Soff     Son  <--- Normal
+                         /\
+                      Ed/  \ Ee
+                       /    \
+                      v     v
+                      D      E
+
+            Jump threading paths: A -> J -> Son -> D (path 1)
+                                  C -> J -> Son -> E (path 2)
+
+   Note that the control flow could be more complicated:
+   - Each jump threading path may have more than one incoming edge.  I.e. A and
+   Ea could represent multiple incoming blocks/edges that are included in
+   path 1.
+   - There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
+   before or after the "normal" copy block).  These are not duplicated onto
+   the jump threading path, as they are single-successor.
+   - Any of the blocks along the path may have other incoming edges that
+   are not part of any jump threading path, but add profile counts along
+   the path.
+
+   In the aboe example, after all jump threading is complete, we will
+   end up with the following control flow:
+
+                A          B            C
+                |          |            |
+              Ea|          |Eb          |Ec
+                |          |            |
+                v          v            v
+               Ja          J           Jc
+               / \        / \Eon'     / \
+          Eona/   \   ---/---\--------   \Eonc
+             /     \ /  /     \           \
+            v       v  v       v          v
+           Sona     Soff      Son        Sonc
+             \                 /\         /
+              \___________    /  \  _____/
+                          \  /    \/
+                           vv      v
+                            D      E
+
+   The main issue to notice here is that when we are processing path 1
+   (A->J->Son->D) we need to figure out the outgoing edge weights to
+   the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
+   sum of the incoming weights to D remain Ed.  The problem with simply
+   assuming that Ja (and Jc when processing path 2) has the same outgoing
+   probabilities to its successors as the original block J, is that after
+   all paths are processed and other edges/counts removed (e.g. none
+   of Ec will reach D after processing path 2), we may end up with not
+   enough count flowing along duplicated edge Sona->D.
+
+   Therefore, in the case of a joiner, we keep track of all counts
+   coming in along the current path, as well as from predecessors not
+   on any jump threading path (Eb in the above example).  While we
+   first assume that the duplicated Eona for Ja->Sona has the same
+   probability as the original, we later compensate for other jump
+   threading paths that may eliminate edges.  We do that by keep track
+   of all counts coming into the original path that are not in a jump
+   thread (Eb in the above example, but as noted earlier, there could
+   be other predecessors incoming to the path at various points, such
+   as at Son).  Call this cumulative non-path count coming into the path
+   before D as Enonpath.  We then ensure that the count from Sona->D is as at
+   least as big as (Ed - Enonpath), but no bigger than the minimum
+   weight along the jump threading path.  The probabilities of both the
+   original and duplicated joiner block J and Ja will be adjusted
+   accordingly after the updates.  */
+
+static bool
+compute_path_counts (struct redirection_data *rd,
+                     ssa_local_info_t *local_info,
+                     gcov_type *path_in_count_ptr,
+                     gcov_type *path_out_count_ptr,
+                     int *path_in_freq_ptr)
+{
+  edge e = rd->incoming_edges->e;
+  vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge elast = path->last ()->e;
+  gcov_type nonpath_count = 0;
+  bool has_joiner = false;
+  gcov_type path_in_count = 0;
+  int path_in_freq = 0;
+
+  /* Start by accumulating incoming edge counts to the path's first bb
+     into a couple buckets:
+        path_in_count: total count of incoming edges that flow into the
+                  current path.
+        nonpath_count: total count of incoming edges that are not
+                  flowing along *any* path.  These are the counts
+                  that will still flow along the original path after
+                  all path duplication is done by potentially multiple
+                  calls to this routine.
+     (any other incoming edge counts are for a different jump threading
+     path that will be handled by a later call to this routine.)
+     To make this easier, start by recording all incoming edges that flow into
+     the current path in a bitmap.  We could add up the path's incoming edge
+     counts here, but we still need to walk all the first bb's incoming edges
+     below to add up the counts of the other edges not included in this jump
+     threading path.  */
+  struct el *next, *el;
+  bitmap in_edge_srcs = BITMAP_ALLOC (NULL);
+  for (el = rd->incoming_edges; el; el = next)
+    {
+      next = el->next;
+      bitmap_set_bit (in_edge_srcs, el->e->src->index);
+    }
+  edge ein;
+  edge_iterator ei;
+  FOR_EACH_EDGE (ein, ei, e->dest->preds)
+    {
+      vec<jump_thread_edge *> *ein_path = THREAD_PATH (ein);
+      /* Simply check the incoming edge src against the set captured above.  */
+      if (ein_path
+          && bitmap_bit_p (in_edge_srcs, (*ein_path)[0]->e->src->index))
+        {
+          /* It is necessary but not sufficient that the last path edges
+             are identical.  There may be different paths that share the
+             same last path edge in the case where the last edge has a nocopy
+             source block.  */
+          gcc_assert (ein_path->last ()->e == elast);
+          path_in_count += ein->count;
+          path_in_freq += EDGE_FREQUENCY (ein);
+        }
+      else if (!ein_path)
+        {
+          /* Keep track of the incoming edges that are not on any
jump-threading
+             path.  These counts will still flow out of original path after all
+             jump threading is complete.  */
+            nonpath_count += ein->count;
+        }
+    }
+  BITMAP_FREE (in_edge_srcs);
+
+  /* Now compute the fraction of the total count coming into the first
+     path bb that is from the current threading path.  */
+  gcov_type total_count = e->dest->count;
+  /* Handle incoming profile insanities.  */
+  if (total_count < path_in_count)
+    path_in_count = total_count;
+  int onpath_scale = GCOV_COMPUTE_SCALE (path_in_count, total_count);
+
+  /* Walk the entire path to do some more computation in order to estimate
+     how much of the path_in_count will flow out of the duplicated threading
+     path.  In the non-joiner case this is straightforward (it should be
+     the same as path_in_count, although we will handle incoming profile
+     insanities by setting it equal to the minimum count along the path).
+
+     In the joiner case, we need to estimate how much of the path_in_count
+     will stay on the threading path after the joiner's conditional branch.
+     We don't really know for sure how much of the counts
+     associated with this path go to each successor of the joiner, but we'll
+     estimate based on the fraction of the total count coming into the path
+     bb was from the threading paths (computed above in onpath_scale).
+     Afterwards, we will need to do some fixup to account for other threading
+     paths and possible profile insanities.
+
+     In order to estimate the joiner case's counts we also need to update
+     nonpath_count with any additional counts coming into the path.  Other
+     blocks along the path may have additional predecessors from outside
+     the path.  */
+  gcov_type path_out_count = path_in_count;
+  gcov_type min_path_count = path_in_count;
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      gcov_type cur_count = epath->count;
+      if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+        {
+          has_joiner = true;
+          cur_count = apply_probability (cur_count, onpath_scale);
+        }
+      /* In the joiner case we need to update nonpath_count for any edges
+         coming into the path that will contribute to the count flowing
+         into the path successor.  */
+      if (has_joiner && epath != elast)
+      {
+        /* Look for other incoming edges after joiner.  */
+        FOR_EACH_EDGE (ein, ei, epath->dest->preds)
+          {
+            if (ein != epath
+                /* Ignore in edges from blocks we have duplicated for a
+                   threading path, which have duplicated edge counts until
+                   they are redirected by an invocation of this routine.  */
+                && !bitmap_bit_p (local_info->duplicate_blocks,
+                                  ein->src->index))
+              nonpath_count += ein->count;
+          }
+      }
+      if (cur_count < path_out_count)
+        path_out_count = cur_count;
+      if (epath->count < min_path_count)
+        min_path_count = epath->count;
+    }
+
+  /* We computed path_out_count above assuming that this path targeted
+     the joiner's on-path successor with the same likelihood as it
+     reached the joiner.  However, other thread paths through the joiner
+     may take a different path through the normal copy source block
+     (i.e. they have a different elast), meaning that they do not
+     contribute any counts to this path's elast.  As a result, it may
+     turn out that this path must have more count flowing to the on-path
+     successor of the joiner.  Essentially, all of this path's elast
+     count must be contributed by this path and any nonpath counts
+     (since any path through the joiner with a different elast will not
+     include a copy of this elast in its duplicated path).
+     So ensure that this path's path_out_count is at least the
+     difference between elast->count and nonpath_count.  Otherwise the edge
+     counts after threading will not be sane.  */
+  if (has_joiner && path_out_count < elast->count - nonpath_count)
+  {
+    path_out_count = elast->count - nonpath_count;
+    /* But neither can we go above the minimum count along the path
+       we are duplicating.  This can be an issue due to profile
+       insanities coming in to this pass.  */
+    if (path_out_count > min_path_count)
+      path_out_count = min_path_count;
+  }
+
+  *path_in_count_ptr = path_in_count;
+  *path_out_count_ptr = path_out_count;
+  *path_in_freq_ptr = path_in_freq;
+  return has_joiner;
+}
+
+
+/* Update the counts and frequencies for both an original path
+   edge EPATH and its duplicate EDUP.  The duplicate source block
+   will get a count/frequency of PATH_IN_COUNT and PATH_IN_FREQ,
+   and the duplicate edge EDUP will have a count of PATH_OUT_COUNT.  */
+static void
+update_profile (edge epath, edge edup, gcov_type path_in_count,
+                gcov_type path_out_count, int path_in_freq)
+{
+
+  /* First update the duplicated block's count / frequency.  */
+  if (edup)
+    {
+      basic_block dup_block = edup->src;
+      gcc_assert (dup_block->count == 0);
+      gcc_assert (dup_block->frequency == 0);
+      dup_block->count = path_in_count;
+      dup_block->frequency = path_in_freq;
+    }
+
+  /* Now update the original block's count and frequency in the
+     opposite manner - remove the counts/freq that will flow
+     into the duplicated block.  Handle underflow due to precision/
+     rounding issues.  */
+  epath->src->count -= path_in_count;
+  if (epath->src->count < 0)
+    epath->src->count = 0;
+  epath->src->frequency -= path_in_freq;
+  if (epath->src->frequency < 0)
+    epath->src->frequency = 0;
+
+  /* Next update this path edge's original and duplicated counts.  We know
+     that the duplicated path will have path_out_count flowing
+     out of it (in the joiner case this is the count along the duplicated path
+     out of the duplicated joiner).  This count can then be removed from the
+     original path edge.  */
+  if (edup)
+    edup->count = path_out_count;
+  epath->count -= path_out_count;
+  gcc_assert (epath->count >= 0);
+}
+
+
+/* This routine will determine what frequency is needed by an edge E
+   to ensure that its destination block meets its current block frequency.
+   This is used when we don't know E's probability.  */
+
+static int
+deduce_freq (edge e)
+{
+  edge_iterator ei;
+  edge epred;
+  int freq = e->dest->frequency;
+  FOR_EACH_EDGE (epred, ei, e->dest->preds)
+    {
+      if (epred == e)
+        continue;
+      freq -= EDGE_FREQUENCY (epred);
+    }
+  if (freq < 0)
+    freq = 0;
+  return freq;
+}
+
+
+/* The duplicate and original joiner blocks may end up with different
+   probabilities (different from both the original and from each other).
+   Recompute the probabilities here once we have updated the edge
+   counts and frequencies.  */
+
+static void
+recompute_probabilities (basic_block bb)
+{
+  edge esucc;
+  edge_iterator ei;
+  FOR_EACH_EDGE (esucc, ei, bb->succs)
+    {
+      if (bb->count)
+        esucc->probability = GCOV_COMPUTE_SCALE (esucc->count,
+                                                 bb->count);
+      else if (bb->frequency)
+        esucc->probability = GCOV_COMPUTE_SCALE (deduce_freq (esucc),
+                                                 bb->frequency);
+      if (esucc->probability > REG_BR_PROB_BASE)
+        {
+         /* Can happen with missing/guessed probabilities, since we
+            may determine that more is flowing along duplicated
+            path than joiner succ probabilities allowed.
+            Counts and freqs will be insane after jump threading,
+            at least make sure probability is sane or we will
+            get a flow verification error.
+            Not much we can do to make counts/freqs sane without
+            redoing the profile estimation.  */
+         esucc->probability = REG_BR_PROB_BASE;
+       }
+    }
+}
+
+
+/* Update the counts of the original and duplicated edges from a joiner
+   that go off path, given that we have already determined that the
+   duplicate joiner DUP_BB has incoming count PATH_IN_COUNT and
+   outgoing count along the path PATH_OUT_COUNT.  The original (on-)path
+   edge from joiner is EPATH.  */
+
+static void
+update_joiner_offpath_counts (edge epath, basic_block dup_bb,
+                              gcov_type path_in_count,
+                              gcov_type path_out_count)
+{
+  /* Compute the count that currently flows off path from the joiner.
+     In other words, the total count of joiner's out edges other than
+     epath.  Compute this by walking the successors instead of
+     subtracting epath's count from the joiner bb count, since there
+     are sometimes slight insanities where the total out edge count is
+     larger than the bb count (possibly due to rounding/truncation
+     errors).  */
+  gcov_type total_orig_off_path_count = 0;
+  edge enonpath;
+  edge_iterator ei;
+  FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
+    {
+      if (enonpath == epath)
+        continue;
+      total_orig_off_path_count += enonpath->count;
+    }
+
+  /* For the path that we are duplicating, the amount that will flow
+     off path from the duplicated joiner is the delta between the
+     path's cumulative in count and the portion of that count we
+     estimated above as flowing from the joiner along the duplicated
+     path.  */
+  gcov_type total_dup_off_path_count = path_in_count - path_out_count;
+
+  /* Now do the actual updates of the off-path edges.  */
+  FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
+    {
+      /* Look for edges going off of the threading path.  */
+      if (enonpath == epath)
+        continue;
+
+      /* Find the corresponding edge out of the duplicated joiner.  */
+      edge enonpathdup = find_edge (dup_bb, enonpath->dest);
+      gcc_assert (enonpathdup);
+
+      /* We can't use the original probability of the joiner's out
+         edges, since the probabilities of the original branch
+         and the duplicated branches may vary after all threading is
+         complete.  But apportion the duplicated joiner's off-path
+         total edge count computed earlier (total_dup_off_path_count)
+         among the duplicated off-path edges based on their original
+         ratio to the full off-path count (total_orig_off_path_count).
+         */
+      int scale = GCOV_COMPUTE_SCALE (enonpath->count,
+                                      total_orig_off_path_count);
+      /* Give the duplicated offpath edge a portion of the duplicated
+         total.  */
+      enonpathdup->count = apply_scale (scale,
+                                        total_dup_off_path_count);
+      /* Now update the original offpath edge count, handling underflow
+         due to rounding errors.  */
+      enonpath->count -= enonpathdup->count;
+      if (enonpath->count < 0)
+        enonpath->count = 0;
+    }
+}
+
 /* Wire up the outgoing edges from the duplicate blocks and
-   update any PHIs as needed.  */
+   update any PHIs as needed.  Also update the profile counts
+   on the original and duplicate blocks and edges.  */
 void
 ssa_fix_duplicate_block_edges (struct redirection_data *rd,
                               ssa_local_info_t *local_info)
 {
   edge e = rd->incoming_edges->e;
   vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge elast = path->last ()->e;
+  gcov_type path_in_count = 0;
+  gcov_type path_out_count = 0;
+  int path_in_freq = 0;

+  /* First determine how much profile count to move from original
+     path to the duplicate path.  This is tricky in the presence of
+     a joiner (see comments for compute_path_counts), where some portion
+     of the path's counts will flow off-path from the joiner.  In the
+     non-joiner case the path_in_count and path_out_count should be the
+     same.  */
+  bool has_joiner = compute_path_counts (rd, local_info,
+                                         &path_in_count, &path_out_count,
+                                         &path_in_freq);
+
+  int cur_path_freq = path_in_freq;
   for (unsigned int count = 0, i = 1; i < path->length (); i++)
     {
+      edge epath = (*path)[i]->e;
+
       /* If we were threading through an joiner block, then we want
         to keep its control statement and redirect an outgoing edge.
         Else we want to remove the control statement & edges, then create
@@ -515,6 +961,8 @@ ssa_fix_duplicate_block_edges (struct redirection_
          edge victim;
          edge e2;

+          gcc_assert (has_joiner);
+
          /* This updates the PHIs at the destination of the duplicate
             block.  */
          update_destination_phis (local_info->bb, rd->dup_blocks[count]);
@@ -528,14 +976,13 @@ ssa_fix_duplicate_block_edges (struct redirection_
             threading path.  */
          if (!any_remaining_duplicated_blocks (path, i))
            {
-             e2 = redirect_edge_and_branch (victim, path->last ()->e->dest);
-             e2->count = path->last ()->e->count;
+             e2 = redirect_edge_and_branch (victim, elast->dest);
              /* If we redirected the edge, then we need to copy PHI arguments
                 at the target.  If the edge already existed (e2 != victim
                 case), then the PHIs in the target already have the correct
                 arguments.  */
              if (e2 == victim)
-               copy_phi_args (e2->dest, path->last ()->e, e2);
+               copy_phi_args (e2->dest, elast, e2);
            }
          else
            {
@@ -562,7 +1009,31 @@ ssa_fix_duplicate_block_edges (struct redirection_
                    }
                }
            }
-         count++;
+
+         /* Update the counts and frequency of both the original block
+            and path edge, and the duplicates.  The path duplicate's
+            incoming count and frequency are the totals for all edges
+            incoming to this jump threading path computed earlier.
+            And we know that the duplicated path will have path_out_count
+            flowing out of it (i.e. along the duplicated path out of the
+            duplicated joiner).  */
+         update_profile (epath, e2, path_in_count, path_out_count,
+                         path_in_freq);
+
+         /* Next we need to update the counts of the original and duplicated
+            edges from the joiner that go off path.  */
+         update_joiner_offpath_counts (epath, e2->src, path_in_count,
+                                        path_out_count);
+
+         /* Finally, we need to set the probabilities on the duplicated
+            edges out of the duplicated joiner (e2->src).  The probabilities
+            along the original path will all be updated below after we finish
+            processing the whole path.  */
+         recompute_probabilities (e2->src);
+
+         /* Record the frequency flowing to the downstream duplicated
+            path blocks.  */
+         cur_path_freq = EDGE_FREQUENCY (e2);
        }
       else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK)
        {
@@ -570,9 +1041,55 @@ ssa_fix_duplicate_block_edges (struct redirection_
          create_edge_and_update_destination_phis (rd, rd->dup_blocks[count]);
          if (count == 1)
            single_succ_edge (rd->dup_blocks[1])->aux = NULL;
+
+         /* Update the counts and frequency of both the original block
+            and path edge, and the duplicates.  Since we are now after
+            any joiner that may have existed on the path, the count
+            flowing along the duplicated threaded path is path_out_count.
+            If we didn't have a joiner, then cur_path_freq was the sum
+            of the total frequencies along all incoming edges to the
+            thread path (path_in_freq).  If we had a joiner, it would have
+            been updated at the end of that handling to the edge frequency
+            along the duplicated joiner path edge.  */
+         update_profile (epath, EDGE_SUCC (rd->dup_blocks[count], 0),
+                         path_out_count, path_out_count,
+                         cur_path_freq);
+       }
+      else
+        {
+         /* No copy case.  In this case we don't have an equivalent block
+            on the duplicated thread path to update, but we do need
+            to remove the portion of the counts/freqs that were moved
+            to the duplicated path from the counts/freqs flowing through
+            this block on the original path.  Since all the no-copy edges
+            are after any joiner, the removed count is the same as
+            path_out_count.
+
+            If we didn't have a joiner, then cur_path_freq was the sum
+            of the total frequencies along all incoming edges to the
+            thread path (path_in_freq).  If we had a joiner, it would have
+            been updated at the end of that handling to the edge frequency
+            along the duplicated joiner path edge.  */
+            update_profile (epath, NULL, path_out_count, path_out_count,
+                            cur_path_freq);
+       }
+
+      /* Increment the index into the duplicated path when we processed
+         a duplicated block.  */
+      if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
+          || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
+      {
          count++;
-       }
+      }
     }
+
+  /* Now walk orig blocks and update their probabilities, since the
+     counts and freqs should be updated properly by above loop.  */
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      recompute_probabilities (epath->src);
+    }
 }

 /* Hash table traversal callback routine to create duplicate blocks.  */
@@ -598,7 +1115,8 @@ ssa_create_duplicates (struct redirection_data **s
       if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
          || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
        {
-         create_block_for_threading ((*path)[i]->e->src, rd, 1);
+         create_block_for_threading ((*path)[i]->e->src, rd, 1,
+                                      &local_info->duplicate_blocks);
          break;
        }
     }
@@ -607,7 +1125,8 @@ ssa_create_duplicates (struct redirection_data **s
      use the template to create a new block.  */
   if (local_info->template_block == NULL)
     {
-      create_block_for_threading ((*path)[1]->e->src, rd, 0);
+      create_block_for_threading ((*path)[1]->e->src, rd, 0,
+                                  &local_info->duplicate_blocks);
       local_info->template_block = rd->dup_blocks[0];

       /* We do not create any outgoing edges for the template.  We will
@@ -616,7 +1135,8 @@ ssa_create_duplicates (struct redirection_data **s
     }
   else
     {
-      create_block_for_threading (local_info->template_block, rd, 0);
+      create_block_for_threading (local_info->template_block, rd, 0,
+                                  &local_info->duplicate_blocks);

       /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
         block.   */
@@ -686,19 +1206,6 @@ ssa_redirect_edges (struct redirection_data **slot
            fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
                     e->src->index, e->dest->index, rd->dup_blocks[0]->index);

-         rd->dup_blocks[0]->count += e->count;
-
-         /* Excessive jump threading may make frequencies large enough so
-            the computation overflows.  */
-         if (rd->dup_blocks[0]->frequency < BB_FREQ_MAX * 2)
-           rd->dup_blocks[0]->frequency += EDGE_FREQUENCY (e);
-
-         /* In the case of threading through a joiner block, the outgoing
-            edges from the duplicate block were updated when they were
-            redirected during ssa_fix_duplicate_block_edges.  */
-         if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
-           EDGE_SUCC (rd->dup_blocks[0], 0)->count += e->count;
-
          /* Redirect the incoming edge (possibly to the joiner block) to the
             appropriate duplicate block.  */
          e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
@@ -781,6 +1288,8 @@ thread_block_1 (basic_block bb, bool noloop_only,
   ssa_local_info_t local_info;
   struct loop *loop = bb->loop_father;

+  local_info.duplicate_blocks = BITMAP_ALLOC (NULL);
+
   /* To avoid scanning a linear array for the element we need we instead
      use a hash table.  For normal code there should be no noticeable
      difference.  However, if we have a block with a large number of
@@ -865,10 +1374,6 @@ thread_block_1 (basic_block bb, bool noloop_only,
            continue;
        }

-      if (e->dest == e2->src)
-       update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
-                                        e->count, (*THREAD_PATH (e))[1]->e);
-
       /* Insert the outgoing edge into the hash table if it is not
         already in the hash table.  */
       lookup_redirection_data (e, INSERT);
@@ -921,6 +1426,9 @@ thread_block_1 (basic_block bb, bool noloop_only,
       && bb == bb->loop_father->header)
     set_loop_copy (bb->loop_father, NULL);

+  BITMAP_FREE (local_info.duplicate_blocks);
+  local_info.duplicate_blocks = NULL;
+
   /* Indicate to our caller whether or not any jumps were threaded.  */
   return local_info.jumps_threaded;
 }
@@ -987,7 +1495,7 @@ thread_single_edge (edge e)
   npath->safe_push (x);
   rd.path = npath;

-  create_block_for_threading (bb, &rd, 0);
+  create_block_for_threading (bb, &rd, 0, NULL);
   remove_ctrl_stmt_and_useless_edges (rd.dup_blocks[0], NULL);
   create_edge_and_update_destination_phis (&rd, rd.dup_blocks[0]);

-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

[-- Attachment #2: patch.diff --]
[-- Type: text/plain, Size: 30331 bytes --]

2014-03-26  Teresa Johnson  <tejohnson@google.com>

	* tree-ssa-threadupdate.c (struct ssa_local_info_t): New
	duplicate_blocks bitmap.
	(remove_ctrl_stmt_and_useless_edges): Ditto.
	(create_block_for_threading): Ditto.
	(compute_path_counts): New function.
	(update_profile): Ditto.
	(deduce_freq): Ditto.
	(recompute_probabilities): Ditto.
	(update_joiner_offpath_counts): Ditto.
	(ssa_fix_duplicate_block_edges): Update profile info.
	(ssa_create_duplicates): Pass new parameter.
	(ssa_redirect_edges): Remove old profile update.
	(thread_block_1): New duplicate_blocks bitmap,
	remove old profile update.
	(thread_single_edge): Pass new parameter.

Index: tree-ssa-threadupdate.c
===================================================================
--- tree-ssa-threadupdate.c	(revision 208491)
+++ tree-ssa-threadupdate.c	(working copy)
@@ -229,6 +229,9 @@ struct ssa_local_info_t
 
   /* TRUE if we thread one or more jumps, FALSE otherwise.  */
   bool jumps_threaded;
+
+  /* Blocks duplicated for the thread.  */
+  bitmap duplicate_blocks;
 };
 
 /* Passes which use the jump threading code register jump threading
@@ -292,7 +295,8 @@ remove_ctrl_stmt_and_useless_edges (basic_block bb
 static void
 create_block_for_threading (basic_block bb,
 			    struct redirection_data *rd,
-			    unsigned int count)
+			    unsigned int count,
+			    bitmap *duplicate_blocks)
 {
   edge_iterator ei;
   edge e;
@@ -307,6 +311,8 @@ create_block_for_threading (basic_block bb,
   /* Zero out the profile, since the block is unreachable for now.  */
   rd->dup_blocks[count]->frequency = 0;
   rd->dup_blocks[count]->count = 0;
+  if (duplicate_blocks)
+    bitmap_set_bit (*duplicate_blocks, rd->dup_blocks[count]->index);
 }
 
 /* Main data structure to hold information for duplicates of BB.  */
@@ -495,17 +501,457 @@ any_remaining_duplicated_blocks (vec<jump_thread_e
   return false;
 }
 
+
+/* Compute the amount of profile count/frequency coming into the jump threading
+   path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
+   PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
+   duplicated path, returned in PATH_OUT_COUNT_PTR.  LOCAL_INFO is used to
+   identify blocks duplicated for jump threading, which have duplicated
+   edges that need to be ignored in the analysis.  Return true if path contains
+   a joiner, false otherwise.
+
+   In the non-joiner case, this is straightforward - all the counts/frequency
+   flowing into the jump threading path should flow through the duplicated
+   block and out of the duplicated path.
+
+   In the joiner case, it is very tricky.  Some of the counts flowing into
+   the original path go offpath at the joiner.  The problem is that while
+   we know how much total count goes off-path in the original control flow,
+   we don't know how many of the counts corresponding to just the jump
+   threading path go offpath at the joiner.
+
+   For example, assume we have the following control flow and identified
+   jump threading paths:
+
+                A     B     C
+                 \    |    /
+               Ea \   |Eb / Ec
+                   \  |  /
+                    v v v
+                      J       <-- Joiner
+                     / \
+                Eoff/   \Eon
+                   /     \
+                  v       v
+                Soff     Son  <--- Normal
+                         /\
+                      Ed/  \ Ee
+                       /    \
+                      v     v
+                      D      E
+
+            Jump threading paths: A -> J -> Son -> D (path 1)
+                                  C -> J -> Son -> E (path 2)
+
+   Note that the control flow could be more complicated:
+   - Each jump threading path may have more than one incoming edge.  I.e. A and
+   Ea could represent multiple incoming blocks/edges that are included in
+   path 1.
+   - There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
+   before or after the "normal" copy block).  These are not duplicated onto
+   the jump threading path, as they are single-successor.
+   - Any of the blocks along the path may have other incoming edges that
+   are not part of any jump threading path, but add profile counts along
+   the path.
+
+   In the aboe example, after all jump threading is complete, we will
+   end up with the following control flow:
+
+                A          B            C
+                |          |            |
+              Ea|          |Eb          |Ec
+                |          |            |
+                v          v            v
+               Ja          J           Jc
+               / \        / \Eon'     / \
+          Eona/   \   ---/---\--------   \Eonc
+             /     \ /  /     \           \
+            v       v  v       v          v
+           Sona     Soff      Son        Sonc
+             \                 /\         /
+              \___________    /  \  _____/
+                          \  /    \/
+                           vv      v
+                            D      E
+
+   The main issue to notice here is that when we are processing path 1
+   (A->J->Son->D) we need to figure out the outgoing edge weights to
+   the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
+   sum of the incoming weights to D remain Ed.  The problem with simply
+   assuming that Ja (and Jc when processing path 2) has the same outgoing
+   probabilities to its successors as the original block J, is that after
+   all paths are processed and other edges/counts removed (e.g. none
+   of Ec will reach D after processing path 2), we may end up with not
+   enough count flowing along duplicated edge Sona->D.
+
+   Therefore, in the case of a joiner, we keep track of all counts
+   coming in along the current path, as well as from predecessors not
+   on any jump threading path (Eb in the above example).  While we
+   first assume that the duplicated Eona for Ja->Sona has the same
+   probability as the original, we later compensate for other jump
+   threading paths that may eliminate edges.  We do that by keep track
+   of all counts coming into the original path that are not in a jump
+   thread (Eb in the above example, but as noted earlier, there could
+   be other predecessors incoming to the path at various points, such
+   as at Son).  Call this cumulative non-path count coming into the path
+   before D as Enonpath.  We then ensure that the count from Sona->D is as at
+   least as big as (Ed - Enonpath), but no bigger than the minimum
+   weight along the jump threading path.  The probabilities of both the
+   original and duplicated joiner block J and Ja will be adjusted
+   accordingly after the updates.  */
+
+static bool
+compute_path_counts (struct redirection_data *rd,
+                     ssa_local_info_t *local_info,
+                     gcov_type *path_in_count_ptr,
+                     gcov_type *path_out_count_ptr,
+                     int *path_in_freq_ptr)
+{
+  edge e = rd->incoming_edges->e;
+  vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge elast = path->last ()->e;
+  gcov_type nonpath_count = 0;
+  bool has_joiner = false;
+  gcov_type path_in_count = 0;
+  int path_in_freq = 0;
+
+  /* Start by accumulating incoming edge counts to the path's first bb
+     into a couple buckets:
+        path_in_count: total count of incoming edges that flow into the
+                  current path.
+        nonpath_count: total count of incoming edges that are not
+                  flowing along *any* path.  These are the counts
+                  that will still flow along the original path after
+                  all path duplication is done by potentially multiple
+                  calls to this routine.
+     (any other incoming edge counts are for a different jump threading
+     path that will be handled by a later call to this routine.)
+     To make this easier, start by recording all incoming edges that flow into
+     the current path in a bitmap.  We could add up the path's incoming edge
+     counts here, but we still need to walk all the first bb's incoming edges
+     below to add up the counts of the other edges not included in this jump
+     threading path.  */
+  struct el *next, *el;
+  bitmap in_edge_srcs = BITMAP_ALLOC (NULL);
+  for (el = rd->incoming_edges; el; el = next)
+    {
+      next = el->next;
+      bitmap_set_bit (in_edge_srcs, el->e->src->index);
+    }
+  edge ein;
+  edge_iterator ei;
+  FOR_EACH_EDGE (ein, ei, e->dest->preds)
+    {
+      vec<jump_thread_edge *> *ein_path = THREAD_PATH (ein);
+      /* Simply check the incoming edge src against the set captured above.  */
+      if (ein_path
+          && bitmap_bit_p (in_edge_srcs, (*ein_path)[0]->e->src->index))
+        {
+          /* It is necessary but not sufficient that the last path edges
+             are identical.  There may be different paths that share the
+             same last path edge in the case where the last edge has a nocopy
+             source block.  */
+          gcc_assert (ein_path->last ()->e == elast);
+          path_in_count += ein->count;
+          path_in_freq += EDGE_FREQUENCY (ein);
+        }
+      else if (!ein_path)
+        {
+          /* Keep track of the incoming edges that are not on any jump-threading
+             path.  These counts will still flow out of original path after all
+             jump threading is complete.  */
+            nonpath_count += ein->count;
+        }
+    }
+  BITMAP_FREE (in_edge_srcs);
+
+  /* Now compute the fraction of the total count coming into the first
+     path bb that is from the current threading path.  */
+  gcov_type total_count = e->dest->count;
+  /* Handle incoming profile insanities.  */
+  if (total_count < path_in_count)
+    path_in_count = total_count;
+  int onpath_scale = GCOV_COMPUTE_SCALE (path_in_count, total_count);
+
+  /* Walk the entire path to do some more computation in order to estimate
+     how much of the path_in_count will flow out of the duplicated threading
+     path.  In the non-joiner case this is straightforward (it should be
+     the same as path_in_count, although we will handle incoming profile
+     insanities by setting it equal to the minimum count along the path).
+
+     In the joiner case, we need to estimate how much of the path_in_count
+     will stay on the threading path after the joiner's conditional branch.
+     We don't really know for sure how much of the counts
+     associated with this path go to each successor of the joiner, but we'll
+     estimate based on the fraction of the total count coming into the path
+     bb was from the threading paths (computed above in onpath_scale).
+     Afterwards, we will need to do some fixup to account for other threading
+     paths and possible profile insanities.
+
+     In order to estimate the joiner case's counts we also need to update
+     nonpath_count with any additional counts coming into the path.  Other
+     blocks along the path may have additional predecessors from outside
+     the path.  */
+  gcov_type path_out_count = path_in_count;
+  gcov_type min_path_count = path_in_count;
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      gcov_type cur_count = epath->count;
+      if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+        {
+          has_joiner = true;
+          cur_count = apply_probability (cur_count, onpath_scale);
+        }
+      /* In the joiner case we need to update nonpath_count for any edges
+         coming into the path that will contribute to the count flowing
+         into the path successor.  */
+      if (has_joiner && epath != elast)
+      {
+        /* Look for other incoming edges after joiner.  */
+        FOR_EACH_EDGE (ein, ei, epath->dest->preds)
+          {
+            if (ein != epath
+                /* Ignore in edges from blocks we have duplicated for a
+                   threading path, which have duplicated edge counts until
+                   they are redirected by an invocation of this routine.  */
+                && !bitmap_bit_p (local_info->duplicate_blocks,
+                                  ein->src->index))
+              nonpath_count += ein->count;
+          }
+      }
+      if (cur_count < path_out_count)
+        path_out_count = cur_count;
+      if (epath->count < min_path_count)
+        min_path_count = epath->count;
+    }
+
+  /* We computed path_out_count above assuming that this path targeted
+     the joiner's on-path successor with the same likelihood as it
+     reached the joiner.  However, other thread paths through the joiner
+     may take a different path through the normal copy source block
+     (i.e. they have a different elast), meaning that they do not
+     contribute any counts to this path's elast.  As a result, it may
+     turn out that this path must have more count flowing to the on-path
+     successor of the joiner.  Essentially, all of this path's elast
+     count must be contributed by this path and any nonpath counts
+     (since any path through the joiner with a different elast will not
+     include a copy of this elast in its duplicated path).
+     So ensure that this path's path_out_count is at least the
+     difference between elast->count and nonpath_count.  Otherwise the edge
+     counts after threading will not be sane.  */
+  if (has_joiner && path_out_count < elast->count - nonpath_count)
+  {
+    path_out_count = elast->count - nonpath_count;
+    /* But neither can we go above the minimum count along the path
+       we are duplicating.  This can be an issue due to profile
+       insanities coming in to this pass.  */
+    if (path_out_count > min_path_count)
+      path_out_count = min_path_count;
+  }
+
+  *path_in_count_ptr = path_in_count;
+  *path_out_count_ptr = path_out_count;
+  *path_in_freq_ptr = path_in_freq;
+  return has_joiner;
+}
+
+
+/* Update the counts and frequencies for both an original path
+   edge EPATH and its duplicate EDUP.  The duplicate source block
+   will get a count/frequency of PATH_IN_COUNT and PATH_IN_FREQ,
+   and the duplicate edge EDUP will have a count of PATH_OUT_COUNT.  */
+static void
+update_profile (edge epath, edge edup, gcov_type path_in_count,
+                gcov_type path_out_count, int path_in_freq)
+{
+
+  /* First update the duplicated block's count / frequency.  */
+  if (edup)
+    {
+      basic_block dup_block = edup->src;
+      gcc_assert (dup_block->count == 0);
+      gcc_assert (dup_block->frequency == 0);
+      dup_block->count = path_in_count;
+      dup_block->frequency = path_in_freq;
+    }
+
+  /* Now update the original block's count and frequency in the
+     opposite manner - remove the counts/freq that will flow
+     into the duplicated block.  Handle underflow due to precision/
+     rounding issues.  */
+  epath->src->count -= path_in_count;
+  if (epath->src->count < 0)
+    epath->src->count = 0;
+  epath->src->frequency -= path_in_freq;
+  if (epath->src->frequency < 0)
+    epath->src->frequency = 0;
+
+  /* Next update this path edge's original and duplicated counts.  We know
+     that the duplicated path will have path_out_count flowing
+     out of it (in the joiner case this is the count along the duplicated path
+     out of the duplicated joiner).  This count can then be removed from the
+     original path edge.  */
+  if (edup)
+    edup->count = path_out_count;
+  epath->count -= path_out_count;
+  gcc_assert (epath->count >= 0);
+}
+
+
+/* This routine will determine what frequency is needed by an edge E
+   to ensure that its destination block meets its current block frequency.
+   This is used when we don't know E's probability.  */
+
+static int
+deduce_freq (edge e)
+{
+  edge_iterator ei;
+  edge epred;
+  int freq = e->dest->frequency;
+  FOR_EACH_EDGE (epred, ei, e->dest->preds)
+    {
+      if (epred == e)
+        continue;
+      freq -= EDGE_FREQUENCY (epred);
+    }
+  if (freq < 0)
+    freq = 0;
+  return freq;
+}
+
+
+/* The duplicate and original joiner blocks may end up with different
+   probabilities (different from both the original and from each other).
+   Recompute the probabilities here once we have updated the edge
+   counts and frequencies.  */
+
+static void
+recompute_probabilities (basic_block bb)
+{
+  edge esucc;
+  edge_iterator ei;
+  FOR_EACH_EDGE (esucc, ei, bb->succs)
+    {
+      if (bb->count)
+        esucc->probability = GCOV_COMPUTE_SCALE (esucc->count,
+                                                 bb->count);
+      else if (bb->frequency)
+        esucc->probability = GCOV_COMPUTE_SCALE (deduce_freq (esucc),
+                                                 bb->frequency);
+      if (esucc->probability > REG_BR_PROB_BASE)
+        {
+	  /* Can happen with missing/guessed probabilities, since we
+	     may determine that more is flowing along duplicated
+	     path than joiner succ probabilities allowed.
+	     Counts and freqs will be insane after jump threading,
+	     at least make sure probability is sane or we will
+	     get a flow verification error.
+	     Not much we can do to make counts/freqs sane without
+	     redoing the profile estimation.  */
+	  esucc->probability = REG_BR_PROB_BASE;
+	}
+    }
+}
+
+
+/* Update the counts of the original and duplicated edges from a joiner
+   that go off path, given that we have already determined that the
+   duplicate joiner DUP_BB has incoming count PATH_IN_COUNT and
+   outgoing count along the path PATH_OUT_COUNT.  The original (on-)path
+   edge from joiner is EPATH.  */
+
+static void
+update_joiner_offpath_counts (edge epath, basic_block dup_bb,
+                              gcov_type path_in_count,
+                              gcov_type path_out_count)
+{
+  /* Compute the count that currently flows off path from the joiner.
+     In other words, the total count of joiner's out edges other than
+     epath.  Compute this by walking the successors instead of
+     subtracting epath's count from the joiner bb count, since there
+     are sometimes slight insanities where the total out edge count is
+     larger than the bb count (possibly due to rounding/truncation
+     errors).  */
+  gcov_type total_orig_off_path_count = 0;
+  edge enonpath;
+  edge_iterator ei;
+  FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
+    {
+      if (enonpath == epath)
+        continue;
+      total_orig_off_path_count += enonpath->count;
+    }
+
+  /* For the path that we are duplicating, the amount that will flow
+     off path from the duplicated joiner is the delta between the
+     path's cumulative in count and the portion of that count we
+     estimated above as flowing from the joiner along the duplicated
+     path.  */
+  gcov_type total_dup_off_path_count = path_in_count - path_out_count;
+
+  /* Now do the actual updates of the off-path edges.  */
+  FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
+    {
+      /* Look for edges going off of the threading path.  */
+      if (enonpath == epath)
+        continue;
+
+      /* Find the corresponding edge out of the duplicated joiner.  */
+      edge enonpathdup = find_edge (dup_bb, enonpath->dest);
+      gcc_assert (enonpathdup);
+
+      /* We can't use the original probability of the joiner's out
+         edges, since the probabilities of the original branch
+         and the duplicated branches may vary after all threading is
+         complete.  But apportion the duplicated joiner's off-path
+         total edge count computed earlier (total_dup_off_path_count)
+         among the duplicated off-path edges based on their original
+         ratio to the full off-path count (total_orig_off_path_count).
+         */
+      int scale = GCOV_COMPUTE_SCALE (enonpath->count,
+                                      total_orig_off_path_count);
+      /* Give the duplicated offpath edge a portion of the duplicated
+         total.  */
+      enonpathdup->count = apply_scale (scale,
+                                        total_dup_off_path_count);
+      /* Now update the original offpath edge count, handling underflow
+         due to rounding errors.  */
+      enonpath->count -= enonpathdup->count;
+      if (enonpath->count < 0)
+        enonpath->count = 0;
+    }
+}
+
 /* Wire up the outgoing edges from the duplicate blocks and
-   update any PHIs as needed.  */
+   update any PHIs as needed.  Also update the profile counts
+   on the original and duplicate blocks and edges.  */
 void
 ssa_fix_duplicate_block_edges (struct redirection_data *rd,
 			       ssa_local_info_t *local_info)
 {
   edge e = rd->incoming_edges->e;
   vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge elast = path->last ()->e;
+  gcov_type path_in_count = 0;
+  gcov_type path_out_count = 0;
+  int path_in_freq = 0;
 
+  /* First determine how much profile count to move from original
+     path to the duplicate path.  This is tricky in the presence of
+     a joiner (see comments for compute_path_counts), where some portion
+     of the path's counts will flow off-path from the joiner.  In the
+     non-joiner case the path_in_count and path_out_count should be the
+     same.  */
+  bool has_joiner = compute_path_counts (rd, local_info,
+                                         &path_in_count, &path_out_count,
+                                         &path_in_freq);
+
+  int cur_path_freq = path_in_freq;
   for (unsigned int count = 0, i = 1; i < path->length (); i++)
     {
+      edge epath = (*path)[i]->e;
+
       /* If we were threading through an joiner block, then we want
 	 to keep its control statement and redirect an outgoing edge.
 	 Else we want to remove the control statement & edges, then create
@@ -515,6 +961,8 @@ ssa_fix_duplicate_block_edges (struct redirection_
 	  edge victim;
 	  edge e2;
 
+          gcc_assert (has_joiner);
+
 	  /* This updates the PHIs at the destination of the duplicate
 	     block.  */
 	  update_destination_phis (local_info->bb, rd->dup_blocks[count]);
@@ -528,14 +976,13 @@ ssa_fix_duplicate_block_edges (struct redirection_
 	     threading path.  */
 	  if (!any_remaining_duplicated_blocks (path, i))
 	    {
-	      e2 = redirect_edge_and_branch (victim, path->last ()->e->dest);
-	      e2->count = path->last ()->e->count;
+	      e2 = redirect_edge_and_branch (victim, elast->dest);
 	      /* If we redirected the edge, then we need to copy PHI arguments
 		 at the target.  If the edge already existed (e2 != victim
 		 case), then the PHIs in the target already have the correct
 		 arguments.  */
 	      if (e2 == victim)
-		copy_phi_args (e2->dest, path->last ()->e, e2);
+		copy_phi_args (e2->dest, elast, e2);
 	    }
 	  else
 	    {
@@ -562,7 +1009,31 @@ ssa_fix_duplicate_block_edges (struct redirection_
 		    }
 		}
 	    }
-	  count++;
+
+	  /* Update the counts and frequency of both the original block
+	     and path edge, and the duplicates.  The path duplicate's
+	     incoming count and frequency are the totals for all edges
+	     incoming to this jump threading path computed earlier.
+	     And we know that the duplicated path will have path_out_count
+	     flowing out of it (i.e. along the duplicated path out of the
+	     duplicated joiner).  */
+	  update_profile (epath, e2, path_in_count, path_out_count,
+			  path_in_freq);
+
+	  /* Next we need to update the counts of the original and duplicated
+	     edges from the joiner that go off path.  */
+	  update_joiner_offpath_counts (epath, e2->src, path_in_count,
+                                        path_out_count);
+
+	  /* Finally, we need to set the probabilities on the duplicated
+	     edges out of the duplicated joiner (e2->src).  The probabilities
+	     along the original path will all be updated below after we finish
+	     processing the whole path.  */
+	  recompute_probabilities (e2->src);
+
+	  /* Record the frequency flowing to the downstream duplicated
+	     path blocks.  */
+	  cur_path_freq = EDGE_FREQUENCY (e2);
 	}
       else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK)
 	{
@@ -570,9 +1041,55 @@ ssa_fix_duplicate_block_edges (struct redirection_
 	  create_edge_and_update_destination_phis (rd, rd->dup_blocks[count]);
 	  if (count == 1)
 	    single_succ_edge (rd->dup_blocks[1])->aux = NULL;
+
+	  /* Update the counts and frequency of both the original block
+	     and path edge, and the duplicates.  Since we are now after
+	     any joiner that may have existed on the path, the count
+	     flowing along the duplicated threaded path is path_out_count.
+	     If we didn't have a joiner, then cur_path_freq was the sum
+	     of the total frequencies along all incoming edges to the
+	     thread path (path_in_freq).  If we had a joiner, it would have
+	     been updated at the end of that handling to the edge frequency
+	     along the duplicated joiner path edge.  */
+	  update_profile (epath, EDGE_SUCC (rd->dup_blocks[count], 0),
+			  path_out_count, path_out_count,
+			  cur_path_freq);
+	}
+      else
+        {
+	  /* No copy case.  In this case we don't have an equivalent block
+	     on the duplicated thread path to update, but we do need
+	     to remove the portion of the counts/freqs that were moved
+	     to the duplicated path from the counts/freqs flowing through
+	     this block on the original path.  Since all the no-copy edges
+	     are after any joiner, the removed count is the same as
+	     path_out_count.
+
+	     If we didn't have a joiner, then cur_path_freq was the sum
+	     of the total frequencies along all incoming edges to the
+	     thread path (path_in_freq).  If we had a joiner, it would have
+	     been updated at the end of that handling to the edge frequency
+	     along the duplicated joiner path edge.  */
+	     update_profile (epath, NULL, path_out_count, path_out_count,
+			     cur_path_freq);
+	}
+
+      /* Increment the index into the duplicated path when we processed
+         a duplicated block.  */
+      if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
+          || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
+      {
 	  count++;
-	}
+      }
     }
+
+  /* Now walk orig blocks and update their probabilities, since the
+     counts and freqs should be updated properly by above loop.  */
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      recompute_probabilities (epath->src);
+    }
 }
 
 /* Hash table traversal callback routine to create duplicate blocks.  */
@@ -598,7 +1115,8 @@ ssa_create_duplicates (struct redirection_data **s
       if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
 	  || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
 	{
-	  create_block_for_threading ((*path)[i]->e->src, rd, 1);
+	  create_block_for_threading ((*path)[i]->e->src, rd, 1,
+                                      &local_info->duplicate_blocks);
 	  break;
 	}
     }
@@ -607,7 +1125,8 @@ ssa_create_duplicates (struct redirection_data **s
      use the template to create a new block.  */
   if (local_info->template_block == NULL)
     {
-      create_block_for_threading ((*path)[1]->e->src, rd, 0);
+      create_block_for_threading ((*path)[1]->e->src, rd, 0,
+                                  &local_info->duplicate_blocks);
       local_info->template_block = rd->dup_blocks[0];
 
       /* We do not create any outgoing edges for the template.  We will
@@ -616,7 +1135,8 @@ ssa_create_duplicates (struct redirection_data **s
     }
   else
     {
-      create_block_for_threading (local_info->template_block, rd, 0);
+      create_block_for_threading (local_info->template_block, rd, 0,
+                                  &local_info->duplicate_blocks);
 
       /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
 	 block.   */
@@ -686,19 +1206,6 @@ ssa_redirect_edges (struct redirection_data **slot
 	    fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
 		     e->src->index, e->dest->index, rd->dup_blocks[0]->index);
 
-	  rd->dup_blocks[0]->count += e->count;
-
-	  /* Excessive jump threading may make frequencies large enough so
-	     the computation overflows.  */
-	  if (rd->dup_blocks[0]->frequency < BB_FREQ_MAX * 2)
-	    rd->dup_blocks[0]->frequency += EDGE_FREQUENCY (e);
-
-	  /* In the case of threading through a joiner block, the outgoing
-	     edges from the duplicate block were updated when they were
-	     redirected during ssa_fix_duplicate_block_edges.  */
-	  if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
-	    EDGE_SUCC (rd->dup_blocks[0], 0)->count += e->count;
-
 	  /* Redirect the incoming edge (possibly to the joiner block) to the
 	     appropriate duplicate block.  */
 	  e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
@@ -781,6 +1288,8 @@ thread_block_1 (basic_block bb, bool noloop_only,
   ssa_local_info_t local_info;
   struct loop *loop = bb->loop_father;
 
+  local_info.duplicate_blocks = BITMAP_ALLOC (NULL);
+
   /* To avoid scanning a linear array for the element we need we instead
      use a hash table.  For normal code there should be no noticeable
      difference.  However, if we have a block with a large number of
@@ -865,10 +1374,6 @@ thread_block_1 (basic_block bb, bool noloop_only,
 	    continue;
 	}
 
-      if (e->dest == e2->src)
-	update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
-					 e->count, (*THREAD_PATH (e))[1]->e);
-
       /* Insert the outgoing edge into the hash table if it is not
 	 already in the hash table.  */
       lookup_redirection_data (e, INSERT);
@@ -921,6 +1426,9 @@ thread_block_1 (basic_block bb, bool noloop_only,
       && bb == bb->loop_father->header)
     set_loop_copy (bb->loop_father, NULL);
 
+  BITMAP_FREE (local_info.duplicate_blocks);
+  local_info.duplicate_blocks = NULL;
+
   /* Indicate to our caller whether or not any jumps were threaded.  */
   return local_info.jumps_threaded;
 }
@@ -987,7 +1495,7 @@ thread_single_edge (edge e)
   npath->safe_push (x);
   rd.path = npath;
 
-  create_block_for_threading (bb, &rd, 0);
+  create_block_for_threading (bb, &rd, 0, NULL);
   remove_ctrl_stmt_and_useless_edges (rd.dup_blocks[0], NULL);
   create_edge_and_update_destination_phis (&rd, rd.dup_blocks[0]);
 

Re: [PATCH] Redesign jump threading profile updates

[Jeff Law]

On 03/26/14 17:44, Teresa Johnson wrote:
> Recently I discovered that the profile updates being performed by jump
> threading were incorrect in many cases, particularly in the case where
> the threading path contains a joiner. Some of the duplicated
> blocks/edges were not getting any counts, leading to incorrect
> function splitting and other downstream optimizations, and there were
> other insanities as well. After making a few attempts to fix the
> handling I ended up completely redesigning the profile update code,
> removing a few places throughout the code where it was attempting to
> do some updates.
The profile updates in that code is a mess.  It's never really been 
looked at in any systematic way, what's there is ad-hoc and usually in 
response to someone mentioning the profile data was incorrectly updated. 
   As we rely more and more on that data the ad-hoc updating is going to 
cause us more and more pain.

So any work in this space is going to be greatly appreciated.

I'll have to look at this in some detail.  But I wanted you to know I 
was aware of the work and it's in my queue.

Thanks!

jeff

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Wed, Apr 16, 2014 at 10:39 PM, Jeff Law <law@redhat.com> wrote:
> On 03/26/14 17:44, Teresa Johnson wrote:
>>
>> Recently I discovered that the profile updates being performed by jump
>> threading were incorrect in many cases, particularly in the case where
>> the threading path contains a joiner. Some of the duplicated
>> blocks/edges were not getting any counts, leading to incorrect
>> function splitting and other downstream optimizations, and there were
>> other insanities as well. After making a few attempts to fix the
>> handling I ended up completely redesigning the profile update code,
>> removing a few places throughout the code where it was attempting to
>> do some updates.
>
> The profile updates in that code is a mess.  It's never really been looked
> at in any systematic way, what's there is ad-hoc and usually in response to
> someone mentioning the profile data was incorrectly updated.   As we rely
> more and more on that data the ad-hoc updating is going to cause us more and
> more pain.
>
> So any work in this space is going to be greatly appreciated.
>
> I'll have to look at this in some detail.  But I wanted you to know I was
> aware of the work and it's in my queue.

Great, thanks for the update! I realize that it is not a trivial
change so it would take some time to get through. Hopefully it should
address the ongoing profile fixup issues.
Teresa

>
> Thanks!
>
> jeff



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Thu, Apr 17, 2014 at 6:23 AM, Teresa Johnson <tejohnson@google.com> wrote:
> On Wed, Apr 16, 2014 at 10:39 PM, Jeff Law <law@redhat.com> wrote:
>> On 03/26/14 17:44, Teresa Johnson wrote:
>>>
>>> Recently I discovered that the profile updates being performed by jump
>>> threading were incorrect in many cases, particularly in the case where
>>> the threading path contains a joiner. Some of the duplicated
>>> blocks/edges were not getting any counts, leading to incorrect
>>> function splitting and other downstream optimizations, and there were
>>> other insanities as well. After making a few attempts to fix the
>>> handling I ended up completely redesigning the profile update code,
>>> removing a few places throughout the code where it was attempting to
>>> do some updates.
>>
>> The profile updates in that code is a mess.  It's never really been looked
>> at in any systematic way, what's there is ad-hoc and usually in response to
>> someone mentioning the profile data was incorrectly updated.   As we rely
>> more and more on that data the ad-hoc updating is going to cause us more and
>> more pain.
>>
>> So any work in this space is going to be greatly appreciated.
>>
>> I'll have to look at this in some detail.  But I wanted you to know I was
>> aware of the work and it's in my queue.
>
> Great, thanks for the update! I realize that it is not a trivial
> change so it would take some time to get through. Hopefully it should
> address the ongoing profile fixup issues.
> Teresa

Ping.
Thanks,
Teresa

>
>>
>> Thanks!
>>
>> jeff
>
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

Ping. Jeff, any update on when you can look at this?
Thanks,
Teresa

On Tue, May 27, 2014 at 7:10 AM, Teresa Johnson <tejohnson@google.com> wrote:
> On Thu, Apr 17, 2014 at 6:23 AM, Teresa Johnson <tejohnson@google.com> wrote:
>> On Wed, Apr 16, 2014 at 10:39 PM, Jeff Law <law@redhat.com> wrote:
>>> On 03/26/14 17:44, Teresa Johnson wrote:
>>>>
>>>> Recently I discovered that the profile updates being performed by jump
>>>> threading were incorrect in many cases, particularly in the case where
>>>> the threading path contains a joiner. Some of the duplicated
>>>> blocks/edges were not getting any counts, leading to incorrect
>>>> function splitting and other downstream optimizations, and there were
>>>> other insanities as well. After making a few attempts to fix the
>>>> handling I ended up completely redesigning the profile update code,
>>>> removing a few places throughout the code where it was attempting to
>>>> do some updates.
>>>
>>> The profile updates in that code is a mess.  It's never really been looked
>>> at in any systematic way, what's there is ad-hoc and usually in response to
>>> someone mentioning the profile data was incorrectly updated.   As we rely
>>> more and more on that data the ad-hoc updating is going to cause us more and
>>> more pain.
>>>
>>> So any work in this space is going to be greatly appreciated.
>>>
>>> I'll have to look at this in some detail.  But I wanted you to know I was
>>> aware of the work and it's in my queue.
>>
>> Great, thanks for the update! I realize that it is not a trivial
>> change so it would take some time to get through. Hopefully it should
>> address the ongoing profile fixup issues.
>> Teresa
>
> Ping.
> Thanks,
> Teresa
>
>>
>>>
>>> Thanks!
>>>
>>> jeff
>>
>>
>>
>> --
>> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413
>
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Jeff Law]

On 07/07/14 15:22, Teresa Johnson wrote:
> Ping. Jeff, any update on when you can look at this?
Hoping to do so on that long plane ride to the UK for Cauldron :-)

SLC->LAX->Heathrow  Lots of uninterrupted time to look at those changes.


Jeff

Re: [PATCH] Redesign jump threading profile updates

[Jeff Law]

On 03/26/14 17:44, Teresa Johnson wrote:
> Recently I discovered that the profile updates being performed by jump
> threading were incorrect in many cases, particularly in the case where
> the threading path contains a joiner. Some of the duplicated
> blocks/edges were not getting any counts, leading to incorrect
> function splitting and other downstream optimizations, and there were
> other insanities as well. After making a few attempts to fix the
> handling I ended up completely redesigning the profile update code,
> removing a few places throughout the code where it was attempting to
> do some updates.
>
> The biggest complication (see the large comment and example above the
> new routine compute_path_counts) is that we duplicate a conditional
> jump in the joiner case, possibly multiple times for multiple jump
> thread paths through that joiner, and it isn't trivial to figure out
> what probability to assign each of the duplicated successor edges (and
> the original after threading). Each jump thread path may need to have
> a different probability of staying on path through the joiner in order
> to keep the counts going out of the threading path sane.
>
> The patch below was bootstrapped and tested on
> x86_64-unknown-linux-gnu, and also tested with a profiledbootstrap. I
> additionally tested with cpu2006, confirming that the amount of
> resulting cycle samples in the split cold sections reduced, and
> through manual inspection that many different cases were now correct.
> I also measured performance with cpu2006, running each benchmark
> multiple times on a Westmere and see some speedups (453.povray 1-2%,
> 403.gcc 1-1.5%, and noisy but positive speedups in 471.omnetpp and
> 483.xalancbmk).
>
> Looks like my mailer is corrupting the spacing, which makes it harder
> to look at the CFG examples in the big header comment block I added.
> So I have also included the patch as an attachment.
>
> Ok for stage 1?
>
> Thanks,
> Teresa
>
>   2014-03-26  Teresa Johnson  <tejohnson@google.com>
>
>          * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
>          duplicate_blocks bitmap.
>          (remove_ctrl_stmt_and_useless_edges): Ditto.
>          (create_block_for_threading): Ditto.
>          (compute_path_counts): New function.
>          (update_profile): Ditto.
>          (deduce_freq): Ditto.
>          (recompute_probabilities): Ditto.
>          (update_joiner_offpath_counts): Ditto.
>          (ssa_fix_duplicate_block_edges): Update profile info.
>          (ssa_create_duplicates): Pass new parameter.
>          (ssa_redirect_edges): Remove old profile update.
>          (thread_block_1): New duplicate_blocks bitmap,
>          remove old profile update.
>          (thread_single_edge): Pass new parameter.
First off, sorry this took so long to get reviewed.

Most of what's going on in here is similar to something I sketched out, 
but never coded up a while back -- with the significant difference that 
you're handling joiner blocks as well.

Everything looks to be well thought through and documented in the code 
at a level I wish existed throughout GCC.

The only thing I see missing is regression tests.  I don't think you 
need to do anything huge here, but it ought to be possible to set up 
relatively simple cases which show the probabilities/counts being 
updated properly.

Otherwise it looks excellent.  It's pre-approved once you've added some 
kind of testing and fixed the nits noted below.


> +   In the aboe example, after all jump threading is complete, we will
s/aboe/above/


> +  struct el *next, *el;
> +  bitmap in_edge_srcs = BITMAP_ALLOC (NULL);
> +  for (el = rd->incoming_edges; el; el = next)
> +    {
> +      next = el->next;
> +      bitmap_set_bit (in_edge_srcs, el->e->src->index);
> +    }
Please add vertical whitespace after this loop, but before declaring 
variables for the next loop.

Jeff

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Tue, Jul 22, 2014 at 7:29 PM, Jeff Law <law@redhat.com> wrote:
> On 03/26/14 17:44, Teresa Johnson wrote:
>>
>> Recently I discovered that the profile updates being performed by jump
>> threading were incorrect in many cases, particularly in the case where
>> the threading path contains a joiner. Some of the duplicated
>> blocks/edges were not getting any counts, leading to incorrect
>> function splitting and other downstream optimizations, and there were
>> other insanities as well. After making a few attempts to fix the
>> handling I ended up completely redesigning the profile update code,
>> removing a few places throughout the code where it was attempting to
>> do some updates.
>>
>> The biggest complication (see the large comment and example above the
>> new routine compute_path_counts) is that we duplicate a conditional
>> jump in the joiner case, possibly multiple times for multiple jump
>> thread paths through that joiner, and it isn't trivial to figure out
>> what probability to assign each of the duplicated successor edges (and
>> the original after threading). Each jump thread path may need to have
>> a different probability of staying on path through the joiner in order
>> to keep the counts going out of the threading path sane.
>>
>> The patch below was bootstrapped and tested on
>> x86_64-unknown-linux-gnu, and also tested with a profiledbootstrap. I
>> additionally tested with cpu2006, confirming that the amount of
>> resulting cycle samples in the split cold sections reduced, and
>> through manual inspection that many different cases were now correct.
>> I also measured performance with cpu2006, running each benchmark
>> multiple times on a Westmere and see some speedups (453.povray 1-2%,
>> 403.gcc 1-1.5%, and noisy but positive speedups in 471.omnetpp and
>> 483.xalancbmk).
>>
>> Looks like my mailer is corrupting the spacing, which makes it harder
>> to look at the CFG examples in the big header comment block I added.
>> So I have also included the patch as an attachment.
>>
>> Ok for stage 1?
>>
>> Thanks,
>> Teresa
>>
>>   2014-03-26  Teresa Johnson  <tejohnson@google.com>
>>
>>          * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
>>          duplicate_blocks bitmap.
>>          (remove_ctrl_stmt_and_useless_edges): Ditto.
>>          (create_block_for_threading): Ditto.
>>          (compute_path_counts): New function.
>>          (update_profile): Ditto.
>>          (deduce_freq): Ditto.
>>          (recompute_probabilities): Ditto.
>>          (update_joiner_offpath_counts): Ditto.
>>          (ssa_fix_duplicate_block_edges): Update profile info.
>>          (ssa_create_duplicates): Pass new parameter.
>>          (ssa_redirect_edges): Remove old profile update.
>>          (thread_block_1): New duplicate_blocks bitmap,
>>          remove old profile update.
>>          (thread_single_edge): Pass new parameter.
>
> First off, sorry this took so long to get reviewed.
>
> Most of what's going on in here is similar to something I sketched out, but
> never coded up a while back -- with the significant difference that you're
> handling joiner blocks as well.
>
> Everything looks to be well thought through and documented in the code at a
> level I wish existed throughout GCC.
>
> The only thing I see missing is regression tests.  I don't think you need to
> do anything huge here, but it ought to be possible to set up relatively
> simple cases which show the probabilities/counts being updated properly.
>
> Otherwise it looks excellent.  It's pre-approved once you've added some kind
> of testing and fixed the nits noted below.

Thanks! I will fix the issues you note below and create some test
cases before I commit.
Teresa

>
>
>
>> +   In the aboe example, after all jump threading is complete, we will
>
> s/aboe/above/
>
>
>
>> +  struct el *next, *el;
>> +  bitmap in_edge_srcs = BITMAP_ALLOC (NULL);
>> +  for (el = rd->incoming_edges; el; el = next)
>> +    {
>> +      next = el->next;
>> +      bitmap_set_bit (in_edge_srcs, el->e->src->index);
>> +    }
>
> Please add vertical whitespace after this loop, but before declaring
> variables for the next loop.
>
> Jeff
>



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Wed, Jul 23, 2014 at 2:08 PM, Teresa Johnson <tejohnson@google.com> wrote:
> On Tue, Jul 22, 2014 at 7:29 PM, Jeff Law <law@redhat.com> wrote:
>> On 03/26/14 17:44, Teresa Johnson wrote:
>>>
>>> Recently I discovered that the profile updates being performed by jump
>>> threading were incorrect in many cases, particularly in the case where
>>> the threading path contains a joiner. Some of the duplicated
>>> blocks/edges were not getting any counts, leading to incorrect
>>> function splitting and other downstream optimizations, and there were
>>> other insanities as well. After making a few attempts to fix the
>>> handling I ended up completely redesigning the profile update code,
>>> removing a few places throughout the code where it was attempting to
>>> do some updates.
>>>
>>> The biggest complication (see the large comment and example above the
>>> new routine compute_path_counts) is that we duplicate a conditional
>>> jump in the joiner case, possibly multiple times for multiple jump
>>> thread paths through that joiner, and it isn't trivial to figure out
>>> what probability to assign each of the duplicated successor edges (and
>>> the original after threading). Each jump thread path may need to have
>>> a different probability of staying on path through the joiner in order
>>> to keep the counts going out of the threading path sane.
>>>
>>> The patch below was bootstrapped and tested on
>>> x86_64-unknown-linux-gnu, and also tested with a profiledbootstrap. I
>>> additionally tested with cpu2006, confirming that the amount of
>>> resulting cycle samples in the split cold sections reduced, and
>>> through manual inspection that many different cases were now correct.
>>> I also measured performance with cpu2006, running each benchmark
>>> multiple times on a Westmere and see some speedups (453.povray 1-2%,
>>> 403.gcc 1-1.5%, and noisy but positive speedups in 471.omnetpp and
>>> 483.xalancbmk).
>>>
>>> Looks like my mailer is corrupting the spacing, which makes it harder
>>> to look at the CFG examples in the big header comment block I added.
>>> So I have also included the patch as an attachment.
>>>
>>> Ok for stage 1?
>>>
>>> Thanks,
>>> Teresa
>>>
>>>   2014-03-26  Teresa Johnson  <tejohnson@google.com>
>>>
>>>          * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
>>>          duplicate_blocks bitmap.
>>>          (remove_ctrl_stmt_and_useless_edges): Ditto.
>>>          (create_block_for_threading): Ditto.
>>>          (compute_path_counts): New function.
>>>          (update_profile): Ditto.
>>>          (deduce_freq): Ditto.
>>>          (recompute_probabilities): Ditto.
>>>          (update_joiner_offpath_counts): Ditto.
>>>          (ssa_fix_duplicate_block_edges): Update profile info.
>>>          (ssa_create_duplicates): Pass new parameter.
>>>          (ssa_redirect_edges): Remove old profile update.
>>>          (thread_block_1): New duplicate_blocks bitmap,
>>>          remove old profile update.
>>>          (thread_single_edge): Pass new parameter.
>>
>> First off, sorry this took so long to get reviewed.
>>
>> Most of what's going on in here is similar to something I sketched out, but
>> never coded up a while back -- with the significant difference that you're
>> handling joiner blocks as well.
>>
>> Everything looks to be well thought through and documented in the code at a
>> level I wish existed throughout GCC.
>>
>> The only thing I see missing is regression tests.  I don't think you need to
>> do anything huge here, but it ought to be possible to set up relatively
>> simple cases which show the probabilities/counts being updated properly.
>>
>> Otherwise it looks excellent.  It's pre-approved once you've added some kind
>> of testing and fixed the nits noted below.
>
> Thanks! I will fix the issues you note below and create some test
> cases before I commit.

Just an update - I found some good test cases by compiling the
c-torture tests with profile feedback with and without my patch. But
in the cases I pulled out I saw that there were still a couple profile
or probability insanities introduced by jump threading (albeit far
less than before), so I wanted to investigate before I commit. I ran
out of time this week and will not get to this until I get back from
vacation the week after next.

Teresa

> Teresa
>
>>
>>
>>
>>> +   In the aboe example, after all jump threading is complete, we will
>>
>> s/aboe/above/
>>
>>
>>
>>> +  struct el *next, *el;
>>> +  bitmap in_edge_srcs = BITMAP_ALLOC (NULL);
>>> +  for (el = rd->incoming_edges; el; el = next)
>>> +    {
>>> +      next = el->next;
>>> +      bitmap_set_bit (in_edge_srcs, el->e->src->index);
>>> +    }
>>
>> Please add vertical whitespace after this loop, but before declaring
>> variables for the next loop.
>>
>> Jeff
>>
>
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Andrew Pinski]

On Fri, Aug 1, 2014 at 10:10 PM, Teresa Johnson <tejohnson@google.com> wrote:
> On Wed, Jul 23, 2014 at 2:08 PM, Teresa Johnson <tejohnson@google.com> wrote:
>> On Tue, Jul 22, 2014 at 7:29 PM, Jeff Law <law@redhat.com> wrote:
>>> On 03/26/14 17:44, Teresa Johnson wrote:
>>>>
>>>> Recently I discovered that the profile updates being performed by jump
>>>> threading were incorrect in many cases, particularly in the case where
>>>> the threading path contains a joiner. Some of the duplicated
>>>> blocks/edges were not getting any counts, leading to incorrect
>>>> function splitting and other downstream optimizations, and there were
>>>> other insanities as well. After making a few attempts to fix the
>>>> handling I ended up completely redesigning the profile update code,
>>>> removing a few places throughout the code where it was attempting to
>>>> do some updates.
>>>>
>>>> The biggest complication (see the large comment and example above the
>>>> new routine compute_path_counts) is that we duplicate a conditional
>>>> jump in the joiner case, possibly multiple times for multiple jump
>>>> thread paths through that joiner, and it isn't trivial to figure out
>>>> what probability to assign each of the duplicated successor edges (and
>>>> the original after threading). Each jump thread path may need to have
>>>> a different probability of staying on path through the joiner in order
>>>> to keep the counts going out of the threading path sane.
>>>>
>>>> The patch below was bootstrapped and tested on
>>>> x86_64-unknown-linux-gnu, and also tested with a profiledbootstrap. I
>>>> additionally tested with cpu2006, confirming that the amount of
>>>> resulting cycle samples in the split cold sections reduced, and
>>>> through manual inspection that many different cases were now correct.
>>>> I also measured performance with cpu2006, running each benchmark
>>>> multiple times on a Westmere and see some speedups (453.povray 1-2%,
>>>> 403.gcc 1-1.5%, and noisy but positive speedups in 471.omnetpp and
>>>> 483.xalancbmk).
>>>>
>>>> Looks like my mailer is corrupting the spacing, which makes it harder
>>>> to look at the CFG examples in the big header comment block I added.
>>>> So I have also included the patch as an attachment.
>>>>
>>>> Ok for stage 1?
>>>>
>>>> Thanks,
>>>> Teresa
>>>>
>>>>   2014-03-26  Teresa Johnson  <tejohnson@google.com>
>>>>
>>>>          * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
>>>>          duplicate_blocks bitmap.
>>>>          (remove_ctrl_stmt_and_useless_edges): Ditto.
>>>>          (create_block_for_threading): Ditto.
>>>>          (compute_path_counts): New function.
>>>>          (update_profile): Ditto.
>>>>          (deduce_freq): Ditto.
>>>>          (recompute_probabilities): Ditto.
>>>>          (update_joiner_offpath_counts): Ditto.
>>>>          (ssa_fix_duplicate_block_edges): Update profile info.
>>>>          (ssa_create_duplicates): Pass new parameter.
>>>>          (ssa_redirect_edges): Remove old profile update.
>>>>          (thread_block_1): New duplicate_blocks bitmap,
>>>>          remove old profile update.
>>>>          (thread_single_edge): Pass new parameter.
>>>
>>> First off, sorry this took so long to get reviewed.
>>>
>>> Most of what's going on in here is similar to something I sketched out, but
>>> never coded up a while back -- with the significant difference that you're
>>> handling joiner blocks as well.
>>>
>>> Everything looks to be well thought through and documented in the code at a
>>> level I wish existed throughout GCC.
>>>
>>> The only thing I see missing is regression tests.  I don't think you need to
>>> do anything huge here, but it ought to be possible to set up relatively
>>> simple cases which show the probabilities/counts being updated properly.
>>>
>>> Otherwise it looks excellent.  It's pre-approved once you've added some kind
>>> of testing and fixed the nits noted below.
>>
>> Thanks! I will fix the issues you note below and create some test
>> cases before I commit.
>
> Just an update - I found some good test cases by compiling the
> c-torture tests with profile feedback with and without my patch. But
> in the cases I pulled out I saw that there were still a couple profile
> or probability insanities introduced by jump threading (albeit far
> less than before), so I wanted to investigate before I commit. I ran
> out of time this week and will not get to this until I get back from
> vacation the week after next.

Another one to try is
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=22401 .  Jeff and I are
hoping your changes fix this one too.

Thanks,
Andrew Pinski

>
> Teresa
>
>> Teresa
>>
>>>
>>>
>>>
>>>> +   In the aboe example, after all jump threading is complete, we will
>>>
>>> s/aboe/above/
>>>
>>>
>>>
>>>> +  struct el *next, *el;
>>>> +  bitmap in_edge_srcs = BITMAP_ALLOC (NULL);
>>>> +  for (el = rd->incoming_edges; el; el = next)
>>>> +    {
>>>> +      next = el->next;
>>>> +      bitmap_set_bit (in_edge_srcs, el->e->src->index);
>>>> +    }
>>>
>>> Please add vertical whitespace after this loop, but before declaring
>>> variables for the next loop.
>>>
>>> Jeff
>>>
>>
>>
>>
>> --
>> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413
>
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

[-- Attachment #1: Type: text/plain, Size: 45969 bytes --]

On Fri, Aug 1, 2014 at 10:10 PM, Teresa Johnson <tejohnson@google.com> wrote:
> On Wed, Jul 23, 2014 at 2:08 PM, Teresa Johnson <tejohnson@google.com> wrote:
>> On Tue, Jul 22, 2014 at 7:29 PM, Jeff Law <law@redhat.com> wrote:
>>> On 03/26/14 17:44, Teresa Johnson wrote:
>>>>
>>>> Recently I discovered that the profile updates being performed by jump
>>>> threading were incorrect in many cases, particularly in the case where
>>>> the threading path contains a joiner. Some of the duplicated
>>>> blocks/edges were not getting any counts, leading to incorrect
>>>> function splitting and other downstream optimizations, and there were
>>>> other insanities as well. After making a few attempts to fix the
>>>> handling I ended up completely redesigning the profile update code,
>>>> removing a few places throughout the code where it was attempting to
>>>> do some updates.
>>>>
>>>> The biggest complication (see the large comment and example above the
>>>> new routine compute_path_counts) is that we duplicate a conditional
>>>> jump in the joiner case, possibly multiple times for multiple jump
>>>> thread paths through that joiner, and it isn't trivial to figure out
>>>> what probability to assign each of the duplicated successor edges (and
>>>> the original after threading). Each jump thread path may need to have
>>>> a different probability of staying on path through the joiner in order
>>>> to keep the counts going out of the threading path sane.
>>>>
>>>> The patch below was bootstrapped and tested on
>>>> x86_64-unknown-linux-gnu, and also tested with a profiledbootstrap. I
>>>> additionally tested with cpu2006, confirming that the amount of
>>>> resulting cycle samples in the split cold sections reduced, and
>>>> through manual inspection that many different cases were now correct.
>>>> I also measured performance with cpu2006, running each benchmark
>>>> multiple times on a Westmere and see some speedups (453.povray 1-2%,
>>>> 403.gcc 1-1.5%, and noisy but positive speedups in 471.omnetpp and
>>>> 483.xalancbmk).
>>>>
>>>> Looks like my mailer is corrupting the spacing, which makes it harder
>>>> to look at the CFG examples in the big header comment block I added.
>>>> So I have also included the patch as an attachment.
>>>>
>>>> Ok for stage 1?
>>>>
>>>> Thanks,
>>>> Teresa
>>>>
>>>>   2014-03-26  Teresa Johnson  <tejohnson@google.com>
>>>>
>>>>          * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
>>>>          duplicate_blocks bitmap.
>>>>          (remove_ctrl_stmt_and_useless_edges): Ditto.
>>>>          (create_block_for_threading): Ditto.
>>>>          (compute_path_counts): New function.
>>>>          (update_profile): Ditto.
>>>>          (deduce_freq): Ditto.
>>>>          (recompute_probabilities): Ditto.
>>>>          (update_joiner_offpath_counts): Ditto.
>>>>          (ssa_fix_duplicate_block_edges): Update profile info.
>>>>          (ssa_create_duplicates): Pass new parameter.
>>>>          (ssa_redirect_edges): Remove old profile update.
>>>>          (thread_block_1): New duplicate_blocks bitmap,
>>>>          remove old profile update.
>>>>          (thread_single_edge): Pass new parameter.
>>>
>>> First off, sorry this took so long to get reviewed.
>>>
>>> Most of what's going on in here is similar to something I sketched out, but
>>> never coded up a while back -- with the significant difference that you're
>>> handling joiner blocks as well.
>>>
>>> Everything looks to be well thought through and documented in the code at a
>>> level I wish existed throughout GCC.
>>>
>>> The only thing I see missing is regression tests.  I don't think you need to
>>> do anything huge here, but it ought to be possible to set up relatively
>>> simple cases which show the probabilities/counts being updated properly.
>>>
>>> Otherwise it looks excellent.  It's pre-approved once you've added some kind
>>> of testing and fixed the nits noted below.
>>
>> Thanks! I will fix the issues you note below and create some test
>> cases before I commit.
>
> Just an update - I found some good test cases by compiling the
> c-torture tests with profile feedback with and without my patch. But
> in the cases I pulled out I saw that there were still a couple profile
> or probability insanities introduced by jump threading (albeit far
> less than before), so I wanted to investigate before I commit. I ran
> out of time this week and will not get to this until I get back from
> vacation the week after next.

Hi Jeff,

I finally had a chance to get back to this and look at the remaining
insanities in the new test cases I created. It turns out that there
were still a few issues in the case where there were guessed
frequencies and no profile counts. The two test cases I created do use
FDO, and the insanities in the routines with profile counts went away
with my patch. But the outlined copies of routines that were also
inlined into the main routine still had estimated frequencies, and
these still had a few issues.

The problem is that the profile updates are done incrementally as we
walk and update the paths in ssa_fix_duplicate_block_edges, including
the block and edge counts, the block frequencies and the
probabilities. This is very difficult to do when only operating on
frequencies since the edge frequencies are derived from the source
block frequency and the probability. Therefore, once the source block
frequency is updated, the edge frequency is also affected, and it is
really difficult to figure out what the update to the edge frequency
(essentially the probability) is using the same incremental update
approach. I was attempting to handle this with the routine
deduce_freq, for example, but this turned out to have issues for
certain types of paths. I tried a few other approaches, but they start
looking really ugly and I didn't want to add a parallel but different
algorithm in the case of no profile counts.

So by far the simplest approach was simply to take a snapshot of the
existing block and edge frequencies along the path before we start the
updates in ssa_fix_duplicate_block_edges, by copying them into the
profile count fields of those blocks and edges. Then the existing
algorithm operates the same as when we do have counts, and can
essentially operate incrementally on the edge frequencies since they
live in the count field of the edge and are no longer affected anytime
the source block is updated. Since the algorithm does update block
frequencies and probabilities as well (based on the count updates
performed), we can simply clear out these fake count fields at the end
of ssa_fix_duplicate_block_edges. This takes care of the remaining
insanities introduced by jump threading from these test cases. During
testing I also added in some checking to ensure that the count fields
for the whole routine were cleared properly to make sure the new
clear_counts_path was not missing anything (checking is a little too
heavyweight to add in normally).

New patch below (also attached since my mailer sometimes eats spaces).
The differences between the old patch and the new one:
- removed deduce_freq (which was my least favorite part of the patch
anyway!), and its call from recompute_probabilities, since it is no
longer necessary.
- two new routines freqs_to_counts_path and clear_counts_path, invoked
from ssa_fix_duplicate_block_edges.
- two new tests

Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk?

Thanks,
Teresa

gcc:

2014-09-29  Teresa Johnson  <tejohnson@google.com>

        * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
        duplicate_blocks bitmap.
        (remove_ctrl_stmt_and_useless_edges): Ditto.
        (create_block_for_threading): Ditto.
        (compute_path_counts): New function.
        (update_profile): Ditto.
        (recompute_probabilities): Ditto.
        (update_joiner_offpath_counts): Ditto.
        (freqs_to_counts_path): Ditto.
        (clear_counts_path): Ditto.
        (ssa_fix_duplicate_block_edges): Update profile info.
        (ssa_create_duplicates): Pass new parameter.
        (ssa_redirect_edges): Remove old profile update.
        (thread_block_1): New duplicate_blocks bitmap,
        remove old profile update.
        (thread_single_edge): Pass new parameter.

gcc/testsuite:

2014-09-29  Teresa Johnson  <tejohnson@google.com>

        * testsuite/gcc.dg/tree-prof/20050826-2.c: New test.
        * testsuite/gcc.dg/tree-prof/cmpsf-1.c: Ditto.

Index: tree-ssa-threadupdate.c
===================================================================
--- tree-ssa-threadupdate.c     (revision 215645)
+++ tree-ssa-threadupdate.c     (working copy)
@@ -229,6 +229,9 @@ struct ssa_local_info_t

   /* TRUE if we thread one or more jumps, FALSE otherwise.  */
   bool jumps_threaded;
+
+  /* Blocks duplicated for the thread.  */
+  bitmap duplicate_blocks;
 };

 /* Passes which use the jump threading code register jump threading
@@ -292,7 +295,8 @@ remove_ctrl_stmt_and_useless_edges (basic_block bb
 static void
 create_block_for_threading (basic_block bb,
                            struct redirection_data *rd,
-                           unsigned int count)
+                           unsigned int count,
+                           bitmap *duplicate_blocks)
 {
   edge_iterator ei;
   edge e;
@@ -307,6 +311,8 @@ create_block_for_threading (basic_block bb,
   /* Zero out the profile, since the block is unreachable for now.  */
   rd->dup_blocks[count]->frequency = 0;
   rd->dup_blocks[count]->count = 0;
+  if (duplicate_blocks)
+    bitmap_set_bit (*duplicate_blocks, rd->dup_blocks[count]->index);
 }

 /* Main data structure to hold information for duplicates of BB.  */
@@ -555,8 +561,475 @@ any_remaining_duplicated_blocks (vec<jump_thread_e
   return false;
 }

+
+/* Compute the amount of profile count/frequency coming into the jump threading
+   path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
+   PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
+   duplicated path, returned in PATH_OUT_COUNT_PTR.  LOCAL_INFO is used to
+   identify blocks duplicated for jump threading, which have duplicated
+   edges that need to be ignored in the analysis.  Return true if path contains
+   a joiner, false otherwise.
+
+   In the non-joiner case, this is straightforward - all the counts/frequency
+   flowing into the jump threading path should flow through the duplicated
+   block and out of the duplicated path.
+
+   In the joiner case, it is very tricky.  Some of the counts flowing into
+   the original path go offpath at the joiner.  The problem is that while
+   we know how much total count goes off-path in the original control flow,
+   we don't know how many of the counts corresponding to just the jump
+   threading path go offpath at the joiner.
+
+   For example, assume we have the following control flow and identified
+   jump threading paths:
+
+                A     B     C
+                 \    |    /
+               Ea \   |Eb / Ec
+                   \  |  /
+                    v v v
+                      J       <-- Joiner
+                     / \
+                Eoff/   \Eon
+                   /     \
+                  v       v
+                Soff     Son  <--- Normal
+                         /\
+                      Ed/  \ Ee
+                       /    \
+                      v     v
+                      D      E
+
+            Jump threading paths: A -> J -> Son -> D (path 1)
+                                  C -> J -> Son -> E (path 2)
+
+   Note that the control flow could be more complicated:
+   - Each jump threading path may have more than one incoming edge.  I.e. A and
+   Ea could represent multiple incoming blocks/edges that are included in
+   path 1.
+   - There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
+   before or after the "normal" copy block).  These are not duplicated onto
+   the jump threading path, as they are single-successor.
+   - Any of the blocks along the path may have other incoming edges that
+   are not part of any jump threading path, but add profile counts along
+   the path.
+
+   In the aboe example, after all jump threading is complete, we will
+   end up with the following control flow:
+
+                A          B            C
+                |          |            |
+              Ea|          |Eb          |Ec
+                |          |            |
+                v          v            v
+               Ja          J           Jc
+               / \        / \Eon'     / \
+          Eona/   \   ---/---\--------   \Eonc
+             /     \ /  /     \           \
+            v       v  v       v          v
+           Sona     Soff      Son        Sonc
+             \                 /\         /
+              \___________    /  \  _____/
+                          \  /    \/
+                           vv      v
+                            D      E
+
+   The main issue to notice here is that when we are processing path 1
+   (A->J->Son->D) we need to figure out the outgoing edge weights to
+   the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
+   sum of the incoming weights to D remain Ed.  The problem with simply
+   assuming that Ja (and Jc when processing path 2) has the same outgoing
+   probabilities to its successors as the original block J, is that after
+   all paths are processed and other edges/counts removed (e.g. none
+   of Ec will reach D after processing path 2), we may end up with not
+   enough count flowing along duplicated edge Sona->D.
+
+   Therefore, in the case of a joiner, we keep track of all counts
+   coming in along the current path, as well as from predecessors not
+   on any jump threading path (Eb in the above example).  While we
+   first assume that the duplicated Eona for Ja->Sona has the same
+   probability as the original, we later compensate for other jump
+   threading paths that may eliminate edges.  We do that by keep track
+   of all counts coming into the original path that are not in a jump
+   thread (Eb in the above example, but as noted earlier, there could
+   be other predecessors incoming to the path at various points, such
+   as at Son).  Call this cumulative non-path count coming into the path
+   before D as Enonpath.  We then ensure that the count from Sona->D is as at
+   least as big as (Ed - Enonpath), but no bigger than the minimum
+   weight along the jump threading path.  The probabilities of both the
+   original and duplicated joiner block J and Ja will be adjusted
+   accordingly after the updates.  */
+
+static bool
+compute_path_counts (struct redirection_data *rd,
+                     ssa_local_info_t *local_info,
+                     gcov_type *path_in_count_ptr,
+                     gcov_type *path_out_count_ptr,
+                     int *path_in_freq_ptr)
+{
+  edge e = rd->incoming_edges->e;
+  vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge elast = path->last ()->e;
+  gcov_type nonpath_count = 0;
+  bool has_joiner = false;
+  gcov_type path_in_count = 0;
+  int path_in_freq = 0;
+
+  /* Start by accumulating incoming edge counts to the path's first bb
+     into a couple buckets:
+        path_in_count: total count of incoming edges that flow into the
+                  current path.
+        nonpath_count: total count of incoming edges that are not
+                  flowing along *any* path.  These are the counts
+                  that will still flow along the original path after
+                  all path duplication is done by potentially multiple
+                  calls to this routine.
+     (any other incoming edge counts are for a different jump threading
+     path that will be handled by a later call to this routine.)
+     To make this easier, start by recording all incoming edges that flow into
+     the current path in a bitmap.  We could add up the path's incoming edge
+     counts here, but we still need to walk all the first bb's incoming edges
+     below to add up the counts of the other edges not included in this jump
+     threading path.  */
+  struct el *next, *el;
+  bitmap in_edge_srcs = BITMAP_ALLOC (NULL);
+  for (el = rd->incoming_edges; el; el = next)
+    {
+      next = el->next;
+      bitmap_set_bit (in_edge_srcs, el->e->src->index);
+    }
+  edge ein;
+  edge_iterator ei;
+  FOR_EACH_EDGE (ein, ei, e->dest->preds)
+    {
+      vec<jump_thread_edge *> *ein_path = THREAD_PATH (ein);
+      /* Simply check the incoming edge src against the set captured above.  */
+      if (ein_path
+          && bitmap_bit_p (in_edge_srcs, (*ein_path)[0]->e->src->index))
+        {
+          /* It is necessary but not sufficient that the last path edges
+             are identical.  There may be different paths that share the
+             same last path edge in the case where the last edge has a nocopy
+             source block.  */
+          gcc_assert (ein_path->last ()->e == elast);
+          path_in_count += ein->count;
+          path_in_freq += EDGE_FREQUENCY (ein);
+        }
+      else if (!ein_path)
+        {
+          /* Keep track of the incoming edges that are not on any
jump-threading
+             path.  These counts will still flow out of original path after all
+             jump threading is complete.  */
+            nonpath_count += ein->count;
+        }
+    }
+  BITMAP_FREE (in_edge_srcs);
+
+  /* Now compute the fraction of the total count coming into the first
+     path bb that is from the current threading path.  */
+  gcov_type total_count = e->dest->count;
+  /* Handle incoming profile insanities.  */
+  if (total_count < path_in_count)
+    path_in_count = total_count;
+  int onpath_scale = GCOV_COMPUTE_SCALE (path_in_count, total_count);
+
+  /* Walk the entire path to do some more computation in order to estimate
+     how much of the path_in_count will flow out of the duplicated threading
+     path.  In the non-joiner case this is straightforward (it should be
+     the same as path_in_count, although we will handle incoming profile
+     insanities by setting it equal to the minimum count along the path).
+
+     In the joiner case, we need to estimate how much of the path_in_count
+     will stay on the threading path after the joiner's conditional branch.
+     We don't really know for sure how much of the counts
+     associated with this path go to each successor of the joiner, but we'll
+     estimate based on the fraction of the total count coming into the path
+     bb was from the threading paths (computed above in onpath_scale).
+     Afterwards, we will need to do some fixup to account for other threading
+     paths and possible profile insanities.
+
+     In order to estimate the joiner case's counts we also need to update
+     nonpath_count with any additional counts coming into the path.  Other
+     blocks along the path may have additional predecessors from outside
+     the path.  */
+  gcov_type path_out_count = path_in_count;
+  gcov_type min_path_count = path_in_count;
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      gcov_type cur_count = epath->count;
+      if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+        {
+          has_joiner = true;
+          cur_count = apply_probability (cur_count, onpath_scale);
+        }
+      /* In the joiner case we need to update nonpath_count for any edges
+         coming into the path that will contribute to the count flowing
+         into the path successor.  */
+      if (has_joiner && epath != elast)
+      {
+        /* Look for other incoming edges after joiner.  */
+        FOR_EACH_EDGE (ein, ei, epath->dest->preds)
+          {
+            if (ein != epath
+                /* Ignore in edges from blocks we have duplicated for a
+                   threading path, which have duplicated edge counts until
+                   they are redirected by an invocation of this routine.  */
+                && !bitmap_bit_p (local_info->duplicate_blocks,
+                                  ein->src->index))
+              nonpath_count += ein->count;
+          }
+      }
+      if (cur_count < path_out_count)
+        path_out_count = cur_count;
+      if (epath->count < min_path_count)
+        min_path_count = epath->count;
+    }
+
+  /* We computed path_out_count above assuming that this path targeted
+     the joiner's on-path successor with the same likelihood as it
+     reached the joiner.  However, other thread paths through the joiner
+     may take a different path through the normal copy source block
+     (i.e. they have a different elast), meaning that they do not
+     contribute any counts to this path's elast.  As a result, it may
+     turn out that this path must have more count flowing to the on-path
+     successor of the joiner.  Essentially, all of this path's elast
+     count must be contributed by this path and any nonpath counts
+     (since any path through the joiner with a different elast will not
+     include a copy of this elast in its duplicated path).
+     So ensure that this path's path_out_count is at least the
+     difference between elast->count and nonpath_count.  Otherwise the edge
+     counts after threading will not be sane.  */
+  if (has_joiner && path_out_count < elast->count - nonpath_count)
+  {
+    path_out_count = elast->count - nonpath_count;
+    /* But neither can we go above the minimum count along the path
+       we are duplicating.  This can be an issue due to profile
+       insanities coming in to this pass.  */
+    if (path_out_count > min_path_count)
+      path_out_count = min_path_count;
+  }
+
+  *path_in_count_ptr = path_in_count;
+  *path_out_count_ptr = path_out_count;
+  *path_in_freq_ptr = path_in_freq;
+  return has_joiner;
+}
+
+
+/* Update the counts and frequencies for both an original path
+   edge EPATH and its duplicate EDUP.  The duplicate source block
+   will get a count/frequency of PATH_IN_COUNT and PATH_IN_FREQ,
+   and the duplicate edge EDUP will have a count of PATH_OUT_COUNT.  */
+static void
+update_profile (edge epath, edge edup, gcov_type path_in_count,
+                gcov_type path_out_count, int path_in_freq)
+{
+
+  /* First update the duplicated block's count / frequency.  */
+  if (edup)
+    {
+      basic_block dup_block = edup->src;
+      gcc_assert (dup_block->count == 0);
+      gcc_assert (dup_block->frequency == 0);
+      dup_block->count = path_in_count;
+      dup_block->frequency = path_in_freq;
+    }
+
+  /* Now update the original block's count and frequency in the
+     opposite manner - remove the counts/freq that will flow
+     into the duplicated block.  Handle underflow due to precision/
+     rounding issues.  */
+  epath->src->count -= path_in_count;
+  if (epath->src->count < 0)
+    epath->src->count = 0;
+  epath->src->frequency -= path_in_freq;
+  if (epath->src->frequency < 0)
+    epath->src->frequency = 0;
+
+  /* Next update this path edge's original and duplicated counts.  We know
+     that the duplicated path will have path_out_count flowing
+     out of it (in the joiner case this is the count along the duplicated path
+     out of the duplicated joiner).  This count can then be removed from the
+     original path edge.  */
+  if (edup)
+    edup->count = path_out_count;
+  epath->count -= path_out_count;
+  gcc_assert (epath->count >= 0);
+}
+
+
+/* The duplicate and original joiner blocks may end up with different
+   probabilities (different from both the original and from each other).
+   Recompute the probabilities here once we have updated the edge
+   counts and frequencies.  */
+
+static void
+recompute_probabilities (basic_block bb)
+{
+  edge esucc;
+  edge_iterator ei;
+  FOR_EACH_EDGE (esucc, ei, bb->succs)
+    {
+      if (bb->count)
+        esucc->probability = GCOV_COMPUTE_SCALE (esucc->count,
+                                                 bb->count);
+      if (esucc->probability > REG_BR_PROB_BASE)
+        {
+         /* Can happen with missing/guessed probabilities, since we
+            may determine that more is flowing along duplicated
+            path than joiner succ probabilities allowed.
+            Counts and freqs will be insane after jump threading,
+            at least make sure probability is sane or we will
+            get a flow verification error.
+            Not much we can do to make counts/freqs sane without
+            redoing the profile estimation.  */
+         esucc->probability = REG_BR_PROB_BASE;
+       }
+    }
+}
+
+
+/* Update the counts of the original and duplicated edges from a joiner
+   that go off path, given that we have already determined that the
+   duplicate joiner DUP_BB has incoming count PATH_IN_COUNT and
+   outgoing count along the path PATH_OUT_COUNT.  The original (on-)path
+   edge from joiner is EPATH.  */
+
+static void
+update_joiner_offpath_counts (edge epath, basic_block dup_bb,
+                              gcov_type path_in_count,
+                              gcov_type path_out_count)
+{
+  /* Compute the count that currently flows off path from the joiner.
+     In other words, the total count of joiner's out edges other than
+     epath.  Compute this by walking the successors instead of
+     subtracting epath's count from the joiner bb count, since there
+     are sometimes slight insanities where the total out edge count is
+     larger than the bb count (possibly due to rounding/truncation
+     errors).  */
+  gcov_type total_orig_off_path_count = 0;
+  edge enonpath;
+  edge_iterator ei;
+  FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
+    {
+      if (enonpath == epath)
+        continue;
+      total_orig_off_path_count += enonpath->count;
+    }
+
+  /* For the path that we are duplicating, the amount that will flow
+     off path from the duplicated joiner is the delta between the
+     path's cumulative in count and the portion of that count we
+     estimated above as flowing from the joiner along the duplicated
+     path.  */
+  gcov_type total_dup_off_path_count = path_in_count - path_out_count;
+
+  /* Now do the actual updates of the off-path edges.  */
+  FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
+    {
+      /* Look for edges going off of the threading path.  */
+      if (enonpath == epath)
+        continue;
+
+      /* Find the corresponding edge out of the duplicated joiner.  */
+      edge enonpathdup = find_edge (dup_bb, enonpath->dest);
+      gcc_assert (enonpathdup);
+
+      /* We can't use the original probability of the joiner's out
+         edges, since the probabilities of the original branch
+         and the duplicated branches may vary after all threading is
+         complete.  But apportion the duplicated joiner's off-path
+         total edge count computed earlier (total_dup_off_path_count)
+         among the duplicated off-path edges based on their original
+         ratio to the full off-path count (total_orig_off_path_count).
+         */
+      int scale = GCOV_COMPUTE_SCALE (enonpath->count,
+                                      total_orig_off_path_count);
+      /* Give the duplicated offpath edge a portion of the duplicated
+         total.  */
+      enonpathdup->count = apply_scale (scale,
+                                        total_dup_off_path_count);
+      /* Now update the original offpath edge count, handling underflow
+         due to rounding errors.  */
+      enonpath->count -= enonpathdup->count;
+      if (enonpath->count < 0)
+        enonpath->count = 0;
+    }
+}
+
+
+/* Invoked for routines that have guessed frequencies and no profile
+   counts to record the block and edge frequencies for paths through RD
+   in the profile count fields of those blocks and edges.  This is because
+   ssa_fix_duplicate_block_edges incrementally updates the block and
+   edge counts as edges are redirected, and it is difficult to do that
+   for edge frequencies which are computed on the fly from the source
+   block frequency and probability.  When a block frequency is updated
+   its outgoing edge frequencies are affected and become difficult to
+   adjust.  */
+
+static void
+freqs_to_counts_path (struct redirection_data *rd)
+{
+  edge e = rd->incoming_edges->e;
+  vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge ein;
+  edge_iterator ei;
+  FOR_EACH_EDGE (ein, ei, e->dest->preds)
+    {
+      gcc_assert (!ein->count);
+      ein->count = EDGE_FREQUENCY (ein);
+    }
+
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      gcc_assert (!epath->count);
+      edge esucc;
+      FOR_EACH_EDGE (esucc, ei, epath->src->succs)
+        {
+          esucc->count = EDGE_FREQUENCY (esucc);
+        }
+      epath->src->count = epath->src->frequency;
+    }
+}
+
+static void
+clear_counts_path (struct redirection_data *rd)
+{
+  edge e = rd->incoming_edges->e;
+  vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge ein, esucc;
+  edge_iterator ei;
+  FOR_EACH_EDGE (ein, ei, e->dest->preds)
+    ein->count = 0;
+
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      FOR_EACH_EDGE (esucc, ei, epath->src->succs)
+      {
+        esucc->count = 0;
+      }
+      epath->src->count = 0;
+    }
+  for (unsigned int i = 0; i < 2; i++)
+    {
+      basic_block dup = rd->dup_blocks[i];
+      if (!dup)
+        continue;
+      FOR_EACH_EDGE (esucc, ei, dup->succs)
+      {
+        esucc->count = 0;
+      }
+      dup->count = 0;
+    }
+}
+
 /* Wire up the outgoing edges from the duplicate blocks and
-   update any PHIs as needed.  */
+   update any PHIs as needed.  Also update the profile counts
+   on the original and duplicate blocks and edges.  */
 void
 ssa_fix_duplicate_block_edges (struct redirection_data *rd,
                               ssa_local_info_t *local_info)
@@ -564,9 +1037,31 @@ ssa_fix_duplicate_block_edges (struct redirection_
   bool multi_incomings = (rd->incoming_edges->next != NULL);
   edge e = rd->incoming_edges->e;
   vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge elast = path->last ()->e;
+  gcov_type path_in_count = 0;
+  gcov_type path_out_count = 0;
+  int path_in_freq = 0;

+  bool do_freqs_to_counts = (profile_status_for_fn (cfun) != PROFILE_READ
+                             || !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count);
+  if (do_freqs_to_counts)
+    freqs_to_counts_path (rd);
+
+  /* First determine how much profile count to move from original
+     path to the duplicate path.  This is tricky in the presence of
+     a joiner (see comments for compute_path_counts), where some portion
+     of the path's counts will flow off-path from the joiner.  In the
+     non-joiner case the path_in_count and path_out_count should be the
+     same.  */
+  bool has_joiner = compute_path_counts (rd, local_info,
+                                         &path_in_count, &path_out_count,
+                                         &path_in_freq);
+
+  int cur_path_freq = path_in_freq;
   for (unsigned int count = 0, i = 1; i < path->length (); i++)
     {
+      edge epath = (*path)[i]->e;
+
       /* If we were threading through an joiner block, then we want
         to keep its control statement and redirect an outgoing edge.
         Else we want to remove the control statement & edges, then create
@@ -576,6 +1071,8 @@ ssa_fix_duplicate_block_edges (struct redirection_
          edge victim;
          edge e2;

+          gcc_assert (has_joiner);
+
          /* This updates the PHIs at the destination of the duplicate
             block.  Pass 0 instead of i if we are threading a path which
             has multiple incoming edges.  */
@@ -591,14 +1088,13 @@ ssa_fix_duplicate_block_edges (struct redirection_
             threading path.  */
          if (!any_remaining_duplicated_blocks (path, i))
            {
-             e2 = redirect_edge_and_branch (victim, path->last ()->e->dest);
-             e2->count = path->last ()->e->count;
+             e2 = redirect_edge_and_branch (victim, elast->dest);
              /* If we redirected the edge, then we need to copy PHI arguments
                 at the target.  If the edge already existed (e2 != victim
                 case), then the PHIs in the target already have the correct
                 arguments.  */
              if (e2 == victim)
-               copy_phi_args (e2->dest, path->last ()->e, e2,
+               copy_phi_args (e2->dest, elast, e2,
                               path, multi_incomings ? 0 : i);
            }
          else
@@ -626,7 +1122,31 @@ ssa_fix_duplicate_block_edges (struct redirection_
                    }
                }
            }
-         count++;
+
+         /* Update the counts and frequency of both the original block
+            and path edge, and the duplicates.  The path duplicate's
+            incoming count and frequency are the totals for all edges
+            incoming to this jump threading path computed earlier.
+            And we know that the duplicated path will have path_out_count
+            flowing out of it (i.e. along the duplicated path out of the
+            duplicated joiner).  */
+         update_profile (epath, e2, path_in_count, path_out_count,
+                         path_in_freq);
+
+         /* Next we need to update the counts of the original and duplicated
+            edges from the joiner that go off path.  */
+         update_joiner_offpath_counts (epath, e2->src, path_in_count,
+                                        path_out_count);
+
+         /* Finally, we need to set the probabilities on the duplicated
+            edges out of the duplicated joiner (e2->src).  The probabilities
+            along the original path will all be updated below after we finish
+            processing the whole path.  */
+         recompute_probabilities (e2->src);
+
+         /* Record the frequency flowing to the downstream duplicated
+            path blocks.  */
+         cur_path_freq = EDGE_FREQUENCY (e2);
        }
       else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK)
        {
@@ -635,9 +1155,58 @@ ssa_fix_duplicate_block_edges (struct redirection_
                                                   multi_incomings ? 0 : i);
          if (count == 1)
            single_succ_edge (rd->dup_blocks[1])->aux = NULL;
+
+         /* Update the counts and frequency of both the original block
+            and path edge, and the duplicates.  Since we are now after
+            any joiner that may have existed on the path, the count
+            flowing along the duplicated threaded path is path_out_count.
+            If we didn't have a joiner, then cur_path_freq was the sum
+            of the total frequencies along all incoming edges to the
+            thread path (path_in_freq).  If we had a joiner, it would have
+            been updated at the end of that handling to the edge frequency
+            along the duplicated joiner path edge.  */
+         update_profile (epath, EDGE_SUCC (rd->dup_blocks[count], 0),
+                         path_out_count, path_out_count,
+                         cur_path_freq);
+       }
+      else
+        {
+         /* No copy case.  In this case we don't have an equivalent block
+            on the duplicated thread path to update, but we do need
+            to remove the portion of the counts/freqs that were moved
+            to the duplicated path from the counts/freqs flowing through
+            this block on the original path.  Since all the no-copy edges
+            are after any joiner, the removed count is the same as
+            path_out_count.
+
+            If we didn't have a joiner, then cur_path_freq was the sum
+            of the total frequencies along all incoming edges to the
+            thread path (path_in_freq).  If we had a joiner, it would have
+            been updated at the end of that handling to the edge frequency
+            along the duplicated joiner path edge.  */
+            update_profile (epath, NULL, path_out_count, path_out_count,
+                            cur_path_freq);
+       }
+
+      /* Increment the index into the duplicated path when we processed
+         a duplicated block.  */
+      if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
+          || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
+      {
          count++;
-       }
+      }
     }
+
+  /* Now walk orig blocks and update their probabilities, since the
+     counts and freqs should be updated properly by above loop.  */
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      recompute_probabilities (epath->src);
+    }
+
+  if (do_freqs_to_counts)
+    clear_counts_path (rd);
 }

 /* Hash table traversal callback routine to create duplicate blocks.  */
@@ -663,7 +1232,8 @@ ssa_create_duplicates (struct redirection_data **s
       if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
          || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
        {
-         create_block_for_threading ((*path)[i]->e->src, rd, 1);
+         create_block_for_threading ((*path)[i]->e->src, rd, 1,
+                                      &local_info->duplicate_blocks);
          break;
        }
     }
@@ -672,7 +1242,8 @@ ssa_create_duplicates (struct redirection_data **s
      use the template to create a new block.  */
   if (local_info->template_block == NULL)
     {
-      create_block_for_threading ((*path)[1]->e->src, rd, 0);
+      create_block_for_threading ((*path)[1]->e->src, rd, 0,
+                                  &local_info->duplicate_blocks);
       local_info->template_block = rd->dup_blocks[0];

       /* We do not create any outgoing edges for the template.  We will
@@ -681,7 +1252,8 @@ ssa_create_duplicates (struct redirection_data **s
     }
   else
     {
-      create_block_for_threading (local_info->template_block, rd, 0);
+      create_block_for_threading (local_info->template_block, rd, 0,
+                                  &local_info->duplicate_blocks);

       /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
         block.   */
@@ -751,19 +1323,6 @@ ssa_redirect_edges (struct redirection_data **slot
            fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
                     e->src->index, e->dest->index, rd->dup_blocks[0]->index);

-         rd->dup_blocks[0]->count += e->count;
-
-         /* Excessive jump threading may make frequencies large enough so
-            the computation overflows.  */
-         if (rd->dup_blocks[0]->frequency < BB_FREQ_MAX * 2)
-           rd->dup_blocks[0]->frequency += EDGE_FREQUENCY (e);
-
-         /* In the case of threading through a joiner block, the outgoing
-            edges from the duplicate block were updated when they were
-            redirected during ssa_fix_duplicate_block_edges.  */
-         if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
-           EDGE_SUCC (rd->dup_blocks[0], 0)->count += e->count;
-
          /* If we redirect a loop latch edge cancel its loop.  */
          if (e->src == e->src->loop_father->latch)
            mark_loop_for_removal (e->src->loop_father);
@@ -849,6 +1408,8 @@ thread_block_1 (basic_block bb, bool noloop_only,
   edge_iterator ei;
   ssa_local_info_t local_info;

+  local_info.duplicate_blocks = BITMAP_ALLOC (NULL);
+
   /* To avoid scanning a linear array for the element we need we instead
      use a hash table.  For normal code there should be no noticeable
      difference.  However, if we have a block with a large number of
@@ -908,10 +1469,6 @@ thread_block_1 (basic_block bb, bool noloop_only,
            continue;
        }

-      if (e->dest == e2->src)
-       update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
-                                        e->count, (*THREAD_PATH (e))[1]->e);
-
       /* Insert the outgoing edge into the hash table if it is not
         already in the hash table.  */
       lookup_redirection_data (e, INSERT);
@@ -965,6 +1522,9 @@ thread_block_1 (basic_block bb, bool noloop_only,
       && bb == bb->loop_father->header)
     set_loop_copy (bb->loop_father, NULL);

+  BITMAP_FREE (local_info.duplicate_blocks);
+  local_info.duplicate_blocks = NULL;
+
   /* Indicate to our caller whether or not any jumps were threaded.  */
   return local_info.jumps_threaded;
 }
@@ -1031,7 +1591,7 @@ thread_single_edge (edge e)
   npath->safe_push (x);
   rd.path = npath;

-  create_block_for_threading (bb, &rd, 0);
+  create_block_for_threading (bb, &rd, 0, NULL);
   remove_ctrl_stmt_and_useless_edges (rd.dup_blocks[0], NULL);
   create_edge_and_update_destination_phis (&rd, rd.dup_blocks[0], 0);

Index: testsuite/gcc.dg/tree-prof/20050826-2.c
===================================================================
--- testsuite/gcc.dg/tree-prof/20050826-2.c     (revision 0)
+++ testsuite/gcc.dg/tree-prof/20050826-2.c     (revision 0)
@@ -0,0 +1,75 @@
+/* Testcase derived from gcc.c-torture/execute 20050826-2.c
+   which showed jump threading profile insanities.  */
+/* { dg-options "-Ofast -fdump-tree-dom1-all" } */
+
+struct rtattr
+{
+  unsigned short rta_len;
+  unsigned short rta_type;
+};
+
+__attribute__ ((noinline))
+int inet_check_attr (void *r, struct rtattr **rta)
+{
+  int i;
+
+  for (i = 1; i <= 14; i++)
+    {
+      struct rtattr *attr = rta[i - 1];
+      if (attr)
+       {
+         if (attr->rta_len - sizeof (struct rtattr) < 4)
+           return -22;
+         if (i != 9 && i != 8)
+           rta[i - 1] = attr + 1;
+       }
+    }
+  return 0;
+}
+
+extern void abort (void);
+
+int
+test (void)
+{
+  struct rtattr rt[2];
+  struct rtattr *rta[14];
+  int i;
+
+  rt[0].rta_len = sizeof (struct rtattr) + 8;
+  rt[0].rta_type = 0;
+  rt[1] = rt[0];
+  for (i = 0; i < 14; i++)
+    rta[i] = &rt[0];
+  if (inet_check_attr (0, rta) != 0)
+    abort ();
+  for (i = 0; i < 14; i++)
+    if (rta[i] != &rt[i != 7 && i != 8])
+      abort ();
+  for (i = 0; i < 14; i++)
+    rta[i] = &rt[0];
+  rta[1] = 0;
+  rt[1].rta_len -= 8;
+  rta[5] = &rt[1];
+  if (inet_check_attr (0, rta) != -22)
+    abort ();
+  for (i = 0; i < 14; i++)
+    if (i == 1 && rta[i] != 0)
+      abort ();
+    else if (i != 1 && i <= 5 && rta[i] != &rt[1])
+      abort ();
+    else if (i > 5 && rta[i] != &rt[0])
+      abort ();
+  return 0;
+}
+
+int
+main (void)
+{
+  int i;
+  for (i=0; i<100; i++)
+    test ();
+  return 0;
+}
+
+/* { dg-final-use { scan-tree-dump-not "Invalid sum" "dom1"} } */
Index: testsuite/gcc.dg/tree-prof/cmpsf-1.c
===================================================================
--- testsuite/gcc.dg/tree-prof/cmpsf-1.c        (revision 0)
+++ testsuite/gcc.dg/tree-prof/cmpsf-1.c        (revision 0)
@@ -0,0 +1,178 @@
+/* Testcase derived from gcc.c-torture/execute cmpsf-1.c
+   which showed jump threading profile insanities.  */
+/* { dg-options "-Ofast -fdump-tree-dom1-all" } */
+
+#include <limits.h>
+
+void abort();
+extern void exit (int);
+
+#define F 140
+#define T 13
+
+feq (float x, float y)
+{
+  if (x == y)
+    return T;
+  else
+    return F;
+}
+
+fne (float x, float y)
+{
+  if (x != y)
+    return T;
+  else
+    return F;
+}
+
+flt (float x, float y)
+{
+  if (x < y)
+    return T;
+  else
+    return F;
+}
+
+fge (float x, float y)
+{
+  if (x >= y)
+    return T;
+  else
+    return F;
+}
+
+fgt (float x, float y)
+{
+  if (x > y)
+    return T;
+  else
+    return F;
+}
+
+fle (float x, float y)
+{
+  if (x <= y)
+    return T;
+  else
+    return F;
+}
+
+float args[] =
+{
+  0.0F,
+  1.0F,
+  -1.0F,
+  __FLT_MAX__,
+  __FLT_MIN__,
+  0.0000000000001F,
+  123456789.0F,
+  -987654321.0F
+};
+
+int correct_results[] =
+{
+ T, F, F, T, F, T,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ T, F, F, T, F, T,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ T, F, F, T, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ T, F, F, T, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ T, F, F, T, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ T, F, F, T, F, T,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ T, F, F, T, F, T,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ T, F, F, T, F, T,
+};
+
+void
+test (void)
+{
+  int i, j, *res = correct_results;
+
+  for (i = 0; i < 8; i++)
+    {
+      float arg0 = args[i];
+      for (j = 0; j < 8; j++)
+       {
+         float arg1 = args[j];
+
+         if (feq (arg0, arg1) != *res++)
+           abort ();
+         if (fne (arg0, arg1) != *res++)
+           abort ();
+         if (flt (arg0, arg1) != *res++)
+           abort ();
+         if (fge (arg0, arg1) != *res++)
+           abort ();
+         if (fgt (arg0, arg1) != *res++)
+           abort ();
+         if (fle (arg0, arg1) != *res++)
+           abort ();
+       }
+    }
+}
+
+int
+main (void)
+{
+  int i;
+  for (i=0; i<100; i++)
+    test ();
+  exit (0);
+}
+
+/* { dg-final-use { scan-tree-dump-not "Invalid sum" "dom1"} } */


-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

[-- Attachment #2: patch.diff --]
[-- Type: text/plain, Size: 38290 bytes --]

gcc:

2014-09-29  Teresa Johnson  <tejohnson@google.com>

	* tree-ssa-threadupdate.c (struct ssa_local_info_t): New
	duplicate_blocks bitmap.
	(remove_ctrl_stmt_and_useless_edges): Ditto.
	(create_block_for_threading): Ditto.
	(compute_path_counts): New function.
	(update_profile): Ditto.
	(recompute_probabilities): Ditto.
	(update_joiner_offpath_counts): Ditto.
	(freqs_to_counts_path): Ditto.
	(clear_counts_path): Ditto.
	(ssa_fix_duplicate_block_edges): Update profile info.
	(ssa_create_duplicates): Pass new parameter.
	(ssa_redirect_edges): Remove old profile update.
	(thread_block_1): New duplicate_blocks bitmap,
	remove old profile update.
	(thread_single_edge): Pass new parameter.

gcc/testsuite:

2014-09-29  Teresa Johnson  <tejohnson@google.com>

	* testsuite/gcc.dg/tree-prof/20050826-2.c: New test.
	* testsuite/gcc.dg/tree-prof/cmpsf-1.c: Ditto.

Index: tree-ssa-threadupdate.c
===================================================================
--- tree-ssa-threadupdate.c	(revision 215645)
+++ tree-ssa-threadupdate.c	(working copy)
@@ -229,6 +229,9 @@ struct ssa_local_info_t
 
   /* TRUE if we thread one or more jumps, FALSE otherwise.  */
   bool jumps_threaded;
+
+  /* Blocks duplicated for the thread.  */
+  bitmap duplicate_blocks;
 };
 
 /* Passes which use the jump threading code register jump threading
@@ -292,7 +295,8 @@ remove_ctrl_stmt_and_useless_edges (basic_block bb
 static void
 create_block_for_threading (basic_block bb,
 			    struct redirection_data *rd,
-			    unsigned int count)
+			    unsigned int count,
+			    bitmap *duplicate_blocks)
 {
   edge_iterator ei;
   edge e;
@@ -307,6 +311,8 @@ create_block_for_threading (basic_block bb,
   /* Zero out the profile, since the block is unreachable for now.  */
   rd->dup_blocks[count]->frequency = 0;
   rd->dup_blocks[count]->count = 0;
+  if (duplicate_blocks)
+    bitmap_set_bit (*duplicate_blocks, rd->dup_blocks[count]->index);
 }
 
 /* Main data structure to hold information for duplicates of BB.  */
@@ -555,8 +561,475 @@ any_remaining_duplicated_blocks (vec<jump_thread_e
   return false;
 }
 
+
+/* Compute the amount of profile count/frequency coming into the jump threading
+   path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
+   PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
+   duplicated path, returned in PATH_OUT_COUNT_PTR.  LOCAL_INFO is used to
+   identify blocks duplicated for jump threading, which have duplicated
+   edges that need to be ignored in the analysis.  Return true if path contains
+   a joiner, false otherwise.
+
+   In the non-joiner case, this is straightforward - all the counts/frequency
+   flowing into the jump threading path should flow through the duplicated
+   block and out of the duplicated path.
+
+   In the joiner case, it is very tricky.  Some of the counts flowing into
+   the original path go offpath at the joiner.  The problem is that while
+   we know how much total count goes off-path in the original control flow,
+   we don't know how many of the counts corresponding to just the jump
+   threading path go offpath at the joiner.
+
+   For example, assume we have the following control flow and identified
+   jump threading paths:
+
+                A     B     C
+                 \    |    /
+               Ea \   |Eb / Ec
+                   \  |  /
+                    v v v
+                      J       <-- Joiner
+                     / \
+                Eoff/   \Eon
+                   /     \
+                  v       v
+                Soff     Son  <--- Normal
+                         /\
+                      Ed/  \ Ee
+                       /    \
+                      v     v
+                      D      E
+
+            Jump threading paths: A -> J -> Son -> D (path 1)
+                                  C -> J -> Son -> E (path 2)
+
+   Note that the control flow could be more complicated:
+   - Each jump threading path may have more than one incoming edge.  I.e. A and
+   Ea could represent multiple incoming blocks/edges that are included in
+   path 1.
+   - There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
+   before or after the "normal" copy block).  These are not duplicated onto
+   the jump threading path, as they are single-successor.
+   - Any of the blocks along the path may have other incoming edges that
+   are not part of any jump threading path, but add profile counts along
+   the path.
+
+   In the aboe example, after all jump threading is complete, we will
+   end up with the following control flow:
+
+                A          B            C
+                |          |            |
+              Ea|          |Eb          |Ec
+                |          |            |
+                v          v            v
+               Ja          J           Jc
+               / \        / \Eon'     / \
+          Eona/   \   ---/---\--------   \Eonc
+             /     \ /  /     \           \
+            v       v  v       v          v
+           Sona     Soff      Son        Sonc
+             \                 /\         /
+              \___________    /  \  _____/
+                          \  /    \/
+                           vv      v
+                            D      E
+
+   The main issue to notice here is that when we are processing path 1
+   (A->J->Son->D) we need to figure out the outgoing edge weights to
+   the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
+   sum of the incoming weights to D remain Ed.  The problem with simply
+   assuming that Ja (and Jc when processing path 2) has the same outgoing
+   probabilities to its successors as the original block J, is that after
+   all paths are processed and other edges/counts removed (e.g. none
+   of Ec will reach D after processing path 2), we may end up with not
+   enough count flowing along duplicated edge Sona->D.
+
+   Therefore, in the case of a joiner, we keep track of all counts
+   coming in along the current path, as well as from predecessors not
+   on any jump threading path (Eb in the above example).  While we
+   first assume that the duplicated Eona for Ja->Sona has the same
+   probability as the original, we later compensate for other jump
+   threading paths that may eliminate edges.  We do that by keep track
+   of all counts coming into the original path that are not in a jump
+   thread (Eb in the above example, but as noted earlier, there could
+   be other predecessors incoming to the path at various points, such
+   as at Son).  Call this cumulative non-path count coming into the path
+   before D as Enonpath.  We then ensure that the count from Sona->D is as at
+   least as big as (Ed - Enonpath), but no bigger than the minimum
+   weight along the jump threading path.  The probabilities of both the
+   original and duplicated joiner block J and Ja will be adjusted
+   accordingly after the updates.  */
+
+static bool
+compute_path_counts (struct redirection_data *rd,
+                     ssa_local_info_t *local_info,
+                     gcov_type *path_in_count_ptr,
+                     gcov_type *path_out_count_ptr,
+                     int *path_in_freq_ptr)
+{
+  edge e = rd->incoming_edges->e;
+  vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge elast = path->last ()->e;
+  gcov_type nonpath_count = 0;
+  bool has_joiner = false;
+  gcov_type path_in_count = 0;
+  int path_in_freq = 0;
+
+  /* Start by accumulating incoming edge counts to the path's first bb
+     into a couple buckets:
+        path_in_count: total count of incoming edges that flow into the
+                  current path.
+        nonpath_count: total count of incoming edges that are not
+                  flowing along *any* path.  These are the counts
+                  that will still flow along the original path after
+                  all path duplication is done by potentially multiple
+                  calls to this routine.
+     (any other incoming edge counts are for a different jump threading
+     path that will be handled by a later call to this routine.)
+     To make this easier, start by recording all incoming edges that flow into
+     the current path in a bitmap.  We could add up the path's incoming edge
+     counts here, but we still need to walk all the first bb's incoming edges
+     below to add up the counts of the other edges not included in this jump
+     threading path.  */
+  struct el *next, *el;
+  bitmap in_edge_srcs = BITMAP_ALLOC (NULL);
+  for (el = rd->incoming_edges; el; el = next)
+    {
+      next = el->next;
+      bitmap_set_bit (in_edge_srcs, el->e->src->index);
+    }
+  edge ein;
+  edge_iterator ei;
+  FOR_EACH_EDGE (ein, ei, e->dest->preds)
+    {
+      vec<jump_thread_edge *> *ein_path = THREAD_PATH (ein);
+      /* Simply check the incoming edge src against the set captured above.  */
+      if (ein_path
+          && bitmap_bit_p (in_edge_srcs, (*ein_path)[0]->e->src->index))
+        {
+          /* It is necessary but not sufficient that the last path edges
+             are identical.  There may be different paths that share the
+             same last path edge in the case where the last edge has a nocopy
+             source block.  */
+          gcc_assert (ein_path->last ()->e == elast);
+          path_in_count += ein->count;
+          path_in_freq += EDGE_FREQUENCY (ein);
+        }
+      else if (!ein_path)
+        {
+          /* Keep track of the incoming edges that are not on any jump-threading
+             path.  These counts will still flow out of original path after all
+             jump threading is complete.  */
+            nonpath_count += ein->count;
+        }
+    }
+  BITMAP_FREE (in_edge_srcs);
+
+  /* Now compute the fraction of the total count coming into the first
+     path bb that is from the current threading path.  */
+  gcov_type total_count = e->dest->count;
+  /* Handle incoming profile insanities.  */
+  if (total_count < path_in_count)
+    path_in_count = total_count;
+  int onpath_scale = GCOV_COMPUTE_SCALE (path_in_count, total_count);
+
+  /* Walk the entire path to do some more computation in order to estimate
+     how much of the path_in_count will flow out of the duplicated threading
+     path.  In the non-joiner case this is straightforward (it should be
+     the same as path_in_count, although we will handle incoming profile
+     insanities by setting it equal to the minimum count along the path).
+
+     In the joiner case, we need to estimate how much of the path_in_count
+     will stay on the threading path after the joiner's conditional branch.
+     We don't really know for sure how much of the counts
+     associated with this path go to each successor of the joiner, but we'll
+     estimate based on the fraction of the total count coming into the path
+     bb was from the threading paths (computed above in onpath_scale).
+     Afterwards, we will need to do some fixup to account for other threading
+     paths and possible profile insanities.
+
+     In order to estimate the joiner case's counts we also need to update
+     nonpath_count with any additional counts coming into the path.  Other
+     blocks along the path may have additional predecessors from outside
+     the path.  */
+  gcov_type path_out_count = path_in_count;
+  gcov_type min_path_count = path_in_count;
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      gcov_type cur_count = epath->count;
+      if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+        {
+          has_joiner = true;
+          cur_count = apply_probability (cur_count, onpath_scale);
+        }
+      /* In the joiner case we need to update nonpath_count for any edges
+         coming into the path that will contribute to the count flowing
+         into the path successor.  */
+      if (has_joiner && epath != elast)
+      {
+        /* Look for other incoming edges after joiner.  */
+        FOR_EACH_EDGE (ein, ei, epath->dest->preds)
+          {
+            if (ein != epath
+                /* Ignore in edges from blocks we have duplicated for a
+                   threading path, which have duplicated edge counts until
+                   they are redirected by an invocation of this routine.  */
+                && !bitmap_bit_p (local_info->duplicate_blocks,
+                                  ein->src->index))
+              nonpath_count += ein->count;
+          }
+      }
+      if (cur_count < path_out_count)
+        path_out_count = cur_count;
+      if (epath->count < min_path_count)
+        min_path_count = epath->count;
+    }
+
+  /* We computed path_out_count above assuming that this path targeted
+     the joiner's on-path successor with the same likelihood as it
+     reached the joiner.  However, other thread paths through the joiner
+     may take a different path through the normal copy source block
+     (i.e. they have a different elast), meaning that they do not
+     contribute any counts to this path's elast.  As a result, it may
+     turn out that this path must have more count flowing to the on-path
+     successor of the joiner.  Essentially, all of this path's elast
+     count must be contributed by this path and any nonpath counts
+     (since any path through the joiner with a different elast will not
+     include a copy of this elast in its duplicated path).
+     So ensure that this path's path_out_count is at least the
+     difference between elast->count and nonpath_count.  Otherwise the edge
+     counts after threading will not be sane.  */
+  if (has_joiner && path_out_count < elast->count - nonpath_count)
+  {
+    path_out_count = elast->count - nonpath_count;
+    /* But neither can we go above the minimum count along the path
+       we are duplicating.  This can be an issue due to profile
+       insanities coming in to this pass.  */
+    if (path_out_count > min_path_count)
+      path_out_count = min_path_count;
+  }
+
+  *path_in_count_ptr = path_in_count;
+  *path_out_count_ptr = path_out_count;
+  *path_in_freq_ptr = path_in_freq;
+  return has_joiner;
+}
+
+
+/* Update the counts and frequencies for both an original path
+   edge EPATH and its duplicate EDUP.  The duplicate source block
+   will get a count/frequency of PATH_IN_COUNT and PATH_IN_FREQ,
+   and the duplicate edge EDUP will have a count of PATH_OUT_COUNT.  */
+static void
+update_profile (edge epath, edge edup, gcov_type path_in_count,
+                gcov_type path_out_count, int path_in_freq)
+{
+
+  /* First update the duplicated block's count / frequency.  */
+  if (edup)
+    {
+      basic_block dup_block = edup->src;
+      gcc_assert (dup_block->count == 0);
+      gcc_assert (dup_block->frequency == 0);
+      dup_block->count = path_in_count;
+      dup_block->frequency = path_in_freq;
+    }
+
+  /* Now update the original block's count and frequency in the
+     opposite manner - remove the counts/freq that will flow
+     into the duplicated block.  Handle underflow due to precision/
+     rounding issues.  */
+  epath->src->count -= path_in_count;
+  if (epath->src->count < 0)
+    epath->src->count = 0;
+  epath->src->frequency -= path_in_freq;
+  if (epath->src->frequency < 0)
+    epath->src->frequency = 0;
+
+  /* Next update this path edge's original and duplicated counts.  We know
+     that the duplicated path will have path_out_count flowing
+     out of it (in the joiner case this is the count along the duplicated path
+     out of the duplicated joiner).  This count can then be removed from the
+     original path edge.  */
+  if (edup)
+    edup->count = path_out_count;
+  epath->count -= path_out_count;
+  gcc_assert (epath->count >= 0);
+}
+
+
+/* The duplicate and original joiner blocks may end up with different
+   probabilities (different from both the original and from each other).
+   Recompute the probabilities here once we have updated the edge
+   counts and frequencies.  */
+
+static void
+recompute_probabilities (basic_block bb)
+{
+  edge esucc;
+  edge_iterator ei;
+  FOR_EACH_EDGE (esucc, ei, bb->succs)
+    {
+      if (bb->count)
+        esucc->probability = GCOV_COMPUTE_SCALE (esucc->count,
+                                                 bb->count);
+      if (esucc->probability > REG_BR_PROB_BASE)
+        {
+	  /* Can happen with missing/guessed probabilities, since we
+	     may determine that more is flowing along duplicated
+	     path than joiner succ probabilities allowed.
+	     Counts and freqs will be insane after jump threading,
+	     at least make sure probability is sane or we will
+	     get a flow verification error.
+	     Not much we can do to make counts/freqs sane without
+	     redoing the profile estimation.  */
+	  esucc->probability = REG_BR_PROB_BASE;
+	}
+    }
+}
+
+
+/* Update the counts of the original and duplicated edges from a joiner
+   that go off path, given that we have already determined that the
+   duplicate joiner DUP_BB has incoming count PATH_IN_COUNT and
+   outgoing count along the path PATH_OUT_COUNT.  The original (on-)path
+   edge from joiner is EPATH.  */
+
+static void
+update_joiner_offpath_counts (edge epath, basic_block dup_bb,
+                              gcov_type path_in_count,
+                              gcov_type path_out_count)
+{
+  /* Compute the count that currently flows off path from the joiner.
+     In other words, the total count of joiner's out edges other than
+     epath.  Compute this by walking the successors instead of
+     subtracting epath's count from the joiner bb count, since there
+     are sometimes slight insanities where the total out edge count is
+     larger than the bb count (possibly due to rounding/truncation
+     errors).  */
+  gcov_type total_orig_off_path_count = 0;
+  edge enonpath;
+  edge_iterator ei;
+  FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
+    {
+      if (enonpath == epath)
+        continue;
+      total_orig_off_path_count += enonpath->count;
+    }
+
+  /* For the path that we are duplicating, the amount that will flow
+     off path from the duplicated joiner is the delta between the
+     path's cumulative in count and the portion of that count we
+     estimated above as flowing from the joiner along the duplicated
+     path.  */
+  gcov_type total_dup_off_path_count = path_in_count - path_out_count;
+
+  /* Now do the actual updates of the off-path edges.  */
+  FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
+    {
+      /* Look for edges going off of the threading path.  */
+      if (enonpath == epath)
+        continue;
+
+      /* Find the corresponding edge out of the duplicated joiner.  */
+      edge enonpathdup = find_edge (dup_bb, enonpath->dest);
+      gcc_assert (enonpathdup);
+
+      /* We can't use the original probability of the joiner's out
+         edges, since the probabilities of the original branch
+         and the duplicated branches may vary after all threading is
+         complete.  But apportion the duplicated joiner's off-path
+         total edge count computed earlier (total_dup_off_path_count)
+         among the duplicated off-path edges based on their original
+         ratio to the full off-path count (total_orig_off_path_count).
+         */
+      int scale = GCOV_COMPUTE_SCALE (enonpath->count,
+                                      total_orig_off_path_count);
+      /* Give the duplicated offpath edge a portion of the duplicated
+         total.  */
+      enonpathdup->count = apply_scale (scale,
+                                        total_dup_off_path_count);
+      /* Now update the original offpath edge count, handling underflow
+         due to rounding errors.  */
+      enonpath->count -= enonpathdup->count;
+      if (enonpath->count < 0)
+        enonpath->count = 0;
+    }
+}
+
+
+/* Invoked for routines that have guessed frequencies and no profile
+   counts to record the block and edge frequencies for paths through RD
+   in the profile count fields of those blocks and edges.  This is because
+   ssa_fix_duplicate_block_edges incrementally updates the block and
+   edge counts as edges are redirected, and it is difficult to do that
+   for edge frequencies which are computed on the fly from the source
+   block frequency and probability.  When a block frequency is updated
+   its outgoing edge frequencies are affected and become difficult to
+   adjust.  */
+
+static void
+freqs_to_counts_path (struct redirection_data *rd)
+{
+  edge e = rd->incoming_edges->e;
+  vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge ein;
+  edge_iterator ei;
+  FOR_EACH_EDGE (ein, ei, e->dest->preds)
+    {
+      gcc_assert (!ein->count);
+      ein->count = EDGE_FREQUENCY (ein);
+    }
+
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      gcc_assert (!epath->count);
+      edge esucc;
+      FOR_EACH_EDGE (esucc, ei, epath->src->succs)
+        {
+          esucc->count = EDGE_FREQUENCY (esucc);
+        }
+      epath->src->count = epath->src->frequency;
+    }
+}
+
+static void
+clear_counts_path (struct redirection_data *rd)
+{
+  edge e = rd->incoming_edges->e;
+  vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge ein, esucc;
+  edge_iterator ei;
+  FOR_EACH_EDGE (ein, ei, e->dest->preds)
+    ein->count = 0;
+
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      FOR_EACH_EDGE (esucc, ei, epath->src->succs)
+      {
+        esucc->count = 0;
+      }
+      epath->src->count = 0;
+    }
+  for (unsigned int i = 0; i < 2; i++)
+    {
+      basic_block dup = rd->dup_blocks[i];
+      if (!dup)
+        continue;
+      FOR_EACH_EDGE (esucc, ei, dup->succs)
+      {
+        esucc->count = 0;
+      }
+      dup->count = 0;
+    }
+}
+
 /* Wire up the outgoing edges from the duplicate blocks and
-   update any PHIs as needed.  */
+   update any PHIs as needed.  Also update the profile counts
+   on the original and duplicate blocks and edges.  */
 void
 ssa_fix_duplicate_block_edges (struct redirection_data *rd,
 			       ssa_local_info_t *local_info)
@@ -564,9 +1037,31 @@ ssa_fix_duplicate_block_edges (struct redirection_
   bool multi_incomings = (rd->incoming_edges->next != NULL);
   edge e = rd->incoming_edges->e;
   vec<jump_thread_edge *> *path = THREAD_PATH (e);
+  edge elast = path->last ()->e;
+  gcov_type path_in_count = 0;
+  gcov_type path_out_count = 0;
+  int path_in_freq = 0;
 
+  bool do_freqs_to_counts = (profile_status_for_fn (cfun) != PROFILE_READ
+                             || !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count);
+  if (do_freqs_to_counts)
+    freqs_to_counts_path (rd);
+
+  /* First determine how much profile count to move from original
+     path to the duplicate path.  This is tricky in the presence of
+     a joiner (see comments for compute_path_counts), where some portion
+     of the path's counts will flow off-path from the joiner.  In the
+     non-joiner case the path_in_count and path_out_count should be the
+     same.  */
+  bool has_joiner = compute_path_counts (rd, local_info,
+                                         &path_in_count, &path_out_count,
+                                         &path_in_freq);
+
+  int cur_path_freq = path_in_freq;
   for (unsigned int count = 0, i = 1; i < path->length (); i++)
     {
+      edge epath = (*path)[i]->e;
+
       /* If we were threading through an joiner block, then we want
 	 to keep its control statement and redirect an outgoing edge.
 	 Else we want to remove the control statement & edges, then create
@@ -576,6 +1071,8 @@ ssa_fix_duplicate_block_edges (struct redirection_
 	  edge victim;
 	  edge e2;
 
+          gcc_assert (has_joiner);
+
 	  /* This updates the PHIs at the destination of the duplicate
 	     block.  Pass 0 instead of i if we are threading a path which
 	     has multiple incoming edges.  */
@@ -591,14 +1088,13 @@ ssa_fix_duplicate_block_edges (struct redirection_
 	     threading path.  */
 	  if (!any_remaining_duplicated_blocks (path, i))
 	    {
-	      e2 = redirect_edge_and_branch (victim, path->last ()->e->dest);
-	      e2->count = path->last ()->e->count;
+	      e2 = redirect_edge_and_branch (victim, elast->dest);
 	      /* If we redirected the edge, then we need to copy PHI arguments
 		 at the target.  If the edge already existed (e2 != victim
 		 case), then the PHIs in the target already have the correct
 		 arguments.  */
 	      if (e2 == victim)
-		copy_phi_args (e2->dest, path->last ()->e, e2,
+		copy_phi_args (e2->dest, elast, e2,
 			       path, multi_incomings ? 0 : i);
 	    }
 	  else
@@ -626,7 +1122,31 @@ ssa_fix_duplicate_block_edges (struct redirection_
 		    }
 		}
 	    }
-	  count++;
+
+	  /* Update the counts and frequency of both the original block
+	     and path edge, and the duplicates.  The path duplicate's
+	     incoming count and frequency are the totals for all edges
+	     incoming to this jump threading path computed earlier.
+	     And we know that the duplicated path will have path_out_count
+	     flowing out of it (i.e. along the duplicated path out of the
+	     duplicated joiner).  */
+	  update_profile (epath, e2, path_in_count, path_out_count,
+			  path_in_freq);
+
+	  /* Next we need to update the counts of the original and duplicated
+	     edges from the joiner that go off path.  */
+	  update_joiner_offpath_counts (epath, e2->src, path_in_count,
+                                        path_out_count);
+
+	  /* Finally, we need to set the probabilities on the duplicated
+	     edges out of the duplicated joiner (e2->src).  The probabilities
+	     along the original path will all be updated below after we finish
+	     processing the whole path.  */
+	  recompute_probabilities (e2->src);
+
+	  /* Record the frequency flowing to the downstream duplicated
+	     path blocks.  */
+	  cur_path_freq = EDGE_FREQUENCY (e2);
 	}
       else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK)
 	{
@@ -635,9 +1155,58 @@ ssa_fix_duplicate_block_edges (struct redirection_
 						   multi_incomings ? 0 : i);
 	  if (count == 1)
 	    single_succ_edge (rd->dup_blocks[1])->aux = NULL;
+
+	  /* Update the counts and frequency of both the original block
+	     and path edge, and the duplicates.  Since we are now after
+	     any joiner that may have existed on the path, the count
+	     flowing along the duplicated threaded path is path_out_count.
+	     If we didn't have a joiner, then cur_path_freq was the sum
+	     of the total frequencies along all incoming edges to the
+	     thread path (path_in_freq).  If we had a joiner, it would have
+	     been updated at the end of that handling to the edge frequency
+	     along the duplicated joiner path edge.  */
+	  update_profile (epath, EDGE_SUCC (rd->dup_blocks[count], 0),
+			  path_out_count, path_out_count,
+			  cur_path_freq);
+	}
+      else
+        {
+	  /* No copy case.  In this case we don't have an equivalent block
+	     on the duplicated thread path to update, but we do need
+	     to remove the portion of the counts/freqs that were moved
+	     to the duplicated path from the counts/freqs flowing through
+	     this block on the original path.  Since all the no-copy edges
+	     are after any joiner, the removed count is the same as
+	     path_out_count.
+
+	     If we didn't have a joiner, then cur_path_freq was the sum
+	     of the total frequencies along all incoming edges to the
+	     thread path (path_in_freq).  If we had a joiner, it would have
+	     been updated at the end of that handling to the edge frequency
+	     along the duplicated joiner path edge.  */
+	     update_profile (epath, NULL, path_out_count, path_out_count,
+			     cur_path_freq);
+	}
+
+      /* Increment the index into the duplicated path when we processed
+         a duplicated block.  */
+      if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
+          || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
+      {
 	  count++;
-	}
+      }
     }
+
+  /* Now walk orig blocks and update their probabilities, since the
+     counts and freqs should be updated properly by above loop.  */
+  for (unsigned int i = 1; i < path->length (); i++)
+    {
+      edge epath = (*path)[i]->e;
+      recompute_probabilities (epath->src);
+    }
+
+  if (do_freqs_to_counts)
+    clear_counts_path (rd);
 }
 
 /* Hash table traversal callback routine to create duplicate blocks.  */
@@ -663,7 +1232,8 @@ ssa_create_duplicates (struct redirection_data **s
       if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
 	  || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
 	{
-	  create_block_for_threading ((*path)[i]->e->src, rd, 1);
+	  create_block_for_threading ((*path)[i]->e->src, rd, 1,
+                                      &local_info->duplicate_blocks);
 	  break;
 	}
     }
@@ -672,7 +1242,8 @@ ssa_create_duplicates (struct redirection_data **s
      use the template to create a new block.  */
   if (local_info->template_block == NULL)
     {
-      create_block_for_threading ((*path)[1]->e->src, rd, 0);
+      create_block_for_threading ((*path)[1]->e->src, rd, 0,
+                                  &local_info->duplicate_blocks);
       local_info->template_block = rd->dup_blocks[0];
 
       /* We do not create any outgoing edges for the template.  We will
@@ -681,7 +1252,8 @@ ssa_create_duplicates (struct redirection_data **s
     }
   else
     {
-      create_block_for_threading (local_info->template_block, rd, 0);
+      create_block_for_threading (local_info->template_block, rd, 0,
+                                  &local_info->duplicate_blocks);
 
       /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
 	 block.   */
@@ -751,19 +1323,6 @@ ssa_redirect_edges (struct redirection_data **slot
 	    fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
 		     e->src->index, e->dest->index, rd->dup_blocks[0]->index);
 
-	  rd->dup_blocks[0]->count += e->count;
-
-	  /* Excessive jump threading may make frequencies large enough so
-	     the computation overflows.  */
-	  if (rd->dup_blocks[0]->frequency < BB_FREQ_MAX * 2)
-	    rd->dup_blocks[0]->frequency += EDGE_FREQUENCY (e);
-
-	  /* In the case of threading through a joiner block, the outgoing
-	     edges from the duplicate block were updated when they were
-	     redirected during ssa_fix_duplicate_block_edges.  */
-	  if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
-	    EDGE_SUCC (rd->dup_blocks[0], 0)->count += e->count;
-
 	  /* If we redirect a loop latch edge cancel its loop.  */
 	  if (e->src == e->src->loop_father->latch)
 	    mark_loop_for_removal (e->src->loop_father);
@@ -849,6 +1408,8 @@ thread_block_1 (basic_block bb, bool noloop_only,
   edge_iterator ei;
   ssa_local_info_t local_info;
 
+  local_info.duplicate_blocks = BITMAP_ALLOC (NULL);
+
   /* To avoid scanning a linear array for the element we need we instead
      use a hash table.  For normal code there should be no noticeable
      difference.  However, if we have a block with a large number of
@@ -908,10 +1469,6 @@ thread_block_1 (basic_block bb, bool noloop_only,
 	    continue;
 	}
 
-      if (e->dest == e2->src)
-	update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
-					 e->count, (*THREAD_PATH (e))[1]->e);
-
       /* Insert the outgoing edge into the hash table if it is not
 	 already in the hash table.  */
       lookup_redirection_data (e, INSERT);
@@ -965,6 +1522,9 @@ thread_block_1 (basic_block bb, bool noloop_only,
       && bb == bb->loop_father->header)
     set_loop_copy (bb->loop_father, NULL);
 
+  BITMAP_FREE (local_info.duplicate_blocks);
+  local_info.duplicate_blocks = NULL;
+
   /* Indicate to our caller whether or not any jumps were threaded.  */
   return local_info.jumps_threaded;
 }
@@ -1031,7 +1591,7 @@ thread_single_edge (edge e)
   npath->safe_push (x);
   rd.path = npath;
 
-  create_block_for_threading (bb, &rd, 0);
+  create_block_for_threading (bb, &rd, 0, NULL);
   remove_ctrl_stmt_and_useless_edges (rd.dup_blocks[0], NULL);
   create_edge_and_update_destination_phis (&rd, rd.dup_blocks[0], 0);
 
Index: testsuite/gcc.dg/tree-prof/20050826-2.c
===================================================================
--- testsuite/gcc.dg/tree-prof/20050826-2.c	(revision 0)
+++ testsuite/gcc.dg/tree-prof/20050826-2.c	(revision 0)
@@ -0,0 +1,75 @@
+/* Testcase derived from gcc.c-torture/execute 20050826-2.c
+   which showed jump threading profile insanities.  */
+/* { dg-options "-Ofast -fdump-tree-dom1-all" } */
+
+struct rtattr
+{
+  unsigned short rta_len;
+  unsigned short rta_type;
+};
+
+__attribute__ ((noinline))
+int inet_check_attr (void *r, struct rtattr **rta)
+{
+  int i;
+
+  for (i = 1; i <= 14; i++)
+    {
+      struct rtattr *attr = rta[i - 1];
+      if (attr)
+	{
+	  if (attr->rta_len - sizeof (struct rtattr) < 4)
+	    return -22;
+	  if (i != 9 && i != 8)
+	    rta[i - 1] = attr + 1;
+	}
+    }
+  return 0;
+}
+
+extern void abort (void);
+
+int
+test (void)
+{
+  struct rtattr rt[2];
+  struct rtattr *rta[14];
+  int i;
+
+  rt[0].rta_len = sizeof (struct rtattr) + 8;
+  rt[0].rta_type = 0;
+  rt[1] = rt[0];
+  for (i = 0; i < 14; i++)
+    rta[i] = &rt[0];
+  if (inet_check_attr (0, rta) != 0)
+    abort ();
+  for (i = 0; i < 14; i++)
+    if (rta[i] != &rt[i != 7 && i != 8])
+      abort ();
+  for (i = 0; i < 14; i++)
+    rta[i] = &rt[0];
+  rta[1] = 0;
+  rt[1].rta_len -= 8;
+  rta[5] = &rt[1];
+  if (inet_check_attr (0, rta) != -22)
+    abort ();
+  for (i = 0; i < 14; i++)
+    if (i == 1 && rta[i] != 0)
+      abort ();
+    else if (i != 1 && i <= 5 && rta[i] != &rt[1])
+      abort ();
+    else if (i > 5 && rta[i] != &rt[0])
+      abort ();
+  return 0;
+}
+
+int
+main (void)
+{
+  int i;
+  for (i=0; i<100; i++)
+    test ();
+  return 0;
+}
+
+/* { dg-final-use { scan-tree-dump-not "Invalid sum" "dom1"} } */
Index: testsuite/gcc.dg/tree-prof/cmpsf-1.c
===================================================================
--- testsuite/gcc.dg/tree-prof/cmpsf-1.c	(revision 0)
+++ testsuite/gcc.dg/tree-prof/cmpsf-1.c	(revision 0)
@@ -0,0 +1,178 @@
+/* Testcase derived from gcc.c-torture/execute cmpsf-1.c
+   which showed jump threading profile insanities.  */
+/* { dg-options "-Ofast -fdump-tree-dom1-all" } */
+
+#include <limits.h>
+
+void abort();
+extern void exit (int);
+
+#define F 140
+#define T 13
+
+feq (float x, float y)
+{
+  if (x == y)
+    return T;
+  else
+    return F;
+}
+
+fne (float x, float y)
+{
+  if (x != y)
+    return T;
+  else
+    return F;
+}
+
+flt (float x, float y)
+{
+  if (x < y)
+    return T;
+  else
+    return F;
+}
+
+fge (float x, float y)
+{
+  if (x >= y)
+    return T;
+  else
+    return F;
+}
+
+fgt (float x, float y)
+{
+  if (x > y)
+    return T;
+  else
+    return F;
+}
+
+fle (float x, float y)
+{
+  if (x <= y)
+    return T;
+  else
+    return F;
+}
+
+float args[] =
+{
+  0.0F,
+  1.0F,
+  -1.0F, 
+  __FLT_MAX__,
+  __FLT_MIN__,
+  0.0000000000001F,
+  123456789.0F,
+  -987654321.0F
+};
+
+int correct_results[] =
+{
+ T, F, F, T, F, T,                                             
+ F, T, T, F, F, T,                                             
+ F, T, F, T, T, F,                                             
+ F, T, T, F, F, T,                                             
+ F, T, T, F, F, T,                                             
+ F, T, T, F, F, T,                                             
+ F, T, T, F, F, T,                                             
+ F, T, F, T, T, F,                                             
+ F, T, F, T, T, F,                                             
+ T, F, F, T, F, T,                                             
+ F, T, F, T, T, F,                                             
+ F, T, T, F, F, T,                                             
+ F, T, F, T, T, F,                                             
+ F, T, F, T, T, F,                                             
+ F, T, T, F, F, T,                                             
+ F, T, F, T, T, F,                                             
+ F, T, T, F, F, T,                                             
+ F, T, T, F, F, T,                                             
+ T, F, F, T, F, T,                                             
+ F, T, T, F, F, T,                                             
+ F, T, T, F, F, T,                                             
+ F, T, T, F, F, T,                                             
+ F, T, T, F, F, T,                                             
+ F, T, F, T, T, F,                                             
+ F, T, F, T, T, F,                                             
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ T, F, F, T, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ T, F, F, T, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ T, F, F, T, F, T,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, F, T, T, F,
+ F, T, F, T, T, F,
+ T, F, F, T, F, T,
+ F, T, F, T, T, F,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ F, T, T, F, F, T,
+ T, F, F, T, F, T,
+};
+
+void
+test (void)
+{
+  int i, j, *res = correct_results;
+
+  for (i = 0; i < 8; i++)
+    {
+      float arg0 = args[i];
+      for (j = 0; j < 8; j++)
+	{
+	  float arg1 = args[j];
+
+	  if (feq (arg0, arg1) != *res++)
+	    abort ();
+	  if (fne (arg0, arg1) != *res++)
+	    abort ();
+	  if (flt (arg0, arg1) != *res++)
+	    abort ();
+	  if (fge (arg0, arg1) != *res++)
+	    abort ();
+	  if (fgt (arg0, arg1) != *res++)
+	    abort ();
+	  if (fle (arg0, arg1) != *res++)
+	    abort ();
+	}
+    }
+}
+
+int
+main (void)
+{
+  int i;
+  for (i=0; i<100; i++)
+    test ();
+  exit (0);
+}
+
+/* { dg-final-use { scan-tree-dump-not "Invalid sum" "dom1"} } */

Re: [PATCH] Redesign jump threading profile updates

[Jeff Law]

On 09/29/14 08:19, Teresa Johnson wrote:
>>
>> Just an update - I found some good test cases by compiling the
>> c-torture tests with profile feedback with and without my patch. But
>> in the cases I pulled out I saw that there were still a couple profile
>> or probability insanities introduced by jump threading (albeit far
>> less than before), so I wanted to investigate before I commit. I ran
>> out of time this week and will not get to this until I get back from
>> vacation the week after next.
>
> Hi Jeff,
>
> I finally had a chance to get back to this and look at the remaining
> insanities in the new test cases I created. It turns out that there
> were still a few issues in the case where there were guessed
> frequencies and no profile counts. The two test cases I created do use
> FDO, and the insanities in the routines with profile counts went away
> with my patch. But the outlined copies of routines that were also
> inlined into the main routine still had estimated frequencies, and
> these still had a few issues.
>
> The problem is that the profile updates are done incrementally as we
> walk and update the paths in ssa_fix_duplicate_block_edges, including
> the block and edge counts, the block frequencies and the
> probabilities. This is very difficult to do when only operating on
> frequencies since the edge frequencies are derived from the source
> block frequency and the probability. Therefore, once the source block
> frequency is updated, the edge frequency is also affected, and it is
> really difficult to figure out what the update to the edge frequency
> (essentially the probability) is using the same incremental update
> approach. I was attempting to handle this with the routine
> deduce_freq, for example, but this turned out to have issues for
> certain types of paths. I tried a few other approaches, but they start
> looking really ugly and I didn't want to add a parallel but different
> algorithm in the case of no profile counts.
>
> So by far the simplest approach was simply to take a snapshot of the
> existing block and edge frequencies along the path before we start the
> updates in ssa_fix_duplicate_block_edges, by copying them into the
> profile count fields of those blocks and edges. Then the existing
> algorithm operates the same as when we do have counts, and can
> essentially operate incrementally on the edge frequencies since they
> live in the count field of the edge and are no longer affected anytime
> the source block is updated. Since the algorithm does update block
> frequencies and probabilities as well (based on the count updates
> performed), we can simply clear out these fake count fields at the end
> of ssa_fix_duplicate_block_edges. This takes care of the remaining
> insanities introduced by jump threading from these test cases. During
> testing I also added in some checking to ensure that the count fields
> for the whole routine were cleared properly to make sure the new
> clear_counts_path was not missing anything (checking is a little too
> heavyweight to add in normally).
>
> New patch below (also attached since my mailer sometimes eats spaces).
> The differences between the old patch and the new one:
> - removed deduce_freq (which was my least favorite part of the patch
> anyway!), and its call from recompute_probabilities, since it is no
> longer necessary.
> - two new routines freqs_to_counts_path and clear_counts_path, invoked
> from ssa_fix_duplicate_block_edges.
> - two new tests
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk?
>
> Thanks,
> Teresa
>
> gcc:
>
> 2014-09-29  Teresa Johnson  <tejohnson@google.com>
>
>          * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
>          duplicate_blocks bitmap.
>          (remove_ctrl_stmt_and_useless_edges): Ditto.
>          (create_block_for_threading): Ditto.
>          (compute_path_counts): New function.
>          (update_profile): Ditto.
>          (recompute_probabilities): Ditto.
>          (update_joiner_offpath_counts): Ditto.
>          (freqs_to_counts_path): Ditto.
>          (clear_counts_path): Ditto.
>          (ssa_fix_duplicate_block_edges): Update profile info.
>          (ssa_create_duplicates): Pass new parameter.
>          (ssa_redirect_edges): Remove old profile update.
>          (thread_block_1): New duplicate_blocks bitmap,
>          remove old profile update.
>          (thread_single_edge): Pass new parameter.
>
> gcc/testsuite:
>
> 2014-09-29  Teresa Johnson  <tejohnson@google.com>
>
>          * testsuite/gcc.dg/tree-prof/20050826-2.c: New test.
>          * testsuite/gcc.dg/tree-prof/cmpsf-1.c: Ditto.
Given I'd already been through this pretty thoroughly, I just gave this 
a cursory review.

clear_counts_path needs a function comment.  It's pretty obvious what 
it's doing, but for completeness let's go ahead and get the obvious 
comment in there.

With that fix, approved for the trunk.  Thanks for taking the time to 
sort out all these issues.

jeff

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Mon, Sep 29, 2014 at 9:33 PM, Jeff Law <law@redhat.com> wrote:
> On 09/29/14 08:19, Teresa Johnson wrote:
>>>
>>>
>>> Just an update - I found some good test cases by compiling the
>>> c-torture tests with profile feedback with and without my patch. But
>>> in the cases I pulled out I saw that there were still a couple profile
>>> or probability insanities introduced by jump threading (albeit far
>>> less than before), so I wanted to investigate before I commit. I ran
>>> out of time this week and will not get to this until I get back from
>>> vacation the week after next.
>>
>>
>> Hi Jeff,
>>
>> I finally had a chance to get back to this and look at the remaining
>> insanities in the new test cases I created. It turns out that there
>> were still a few issues in the case where there were guessed
>> frequencies and no profile counts. The two test cases I created do use
>> FDO, and the insanities in the routines with profile counts went away
>> with my patch. But the outlined copies of routines that were also
>> inlined into the main routine still had estimated frequencies, and
>> these still had a few issues.
>>
>> The problem is that the profile updates are done incrementally as we
>> walk and update the paths in ssa_fix_duplicate_block_edges, including
>> the block and edge counts, the block frequencies and the
>> probabilities. This is very difficult to do when only operating on
>> frequencies since the edge frequencies are derived from the source
>> block frequency and the probability. Therefore, once the source block
>> frequency is updated, the edge frequency is also affected, and it is
>> really difficult to figure out what the update to the edge frequency
>> (essentially the probability) is using the same incremental update
>> approach. I was attempting to handle this with the routine
>> deduce_freq, for example, but this turned out to have issues for
>> certain types of paths. I tried a few other approaches, but they start
>> looking really ugly and I didn't want to add a parallel but different
>> algorithm in the case of no profile counts.
>>
>> So by far the simplest approach was simply to take a snapshot of the
>> existing block and edge frequencies along the path before we start the
>> updates in ssa_fix_duplicate_block_edges, by copying them into the
>> profile count fields of those blocks and edges. Then the existing
>> algorithm operates the same as when we do have counts, and can
>> essentially operate incrementally on the edge frequencies since they
>> live in the count field of the edge and are no longer affected anytime
>> the source block is updated. Since the algorithm does update block
>> frequencies and probabilities as well (based on the count updates
>> performed), we can simply clear out these fake count fields at the end
>> of ssa_fix_duplicate_block_edges. This takes care of the remaining
>> insanities introduced by jump threading from these test cases. During
>> testing I also added in some checking to ensure that the count fields
>> for the whole routine were cleared properly to make sure the new
>> clear_counts_path was not missing anything (checking is a little too
>> heavyweight to add in normally).
>>
>> New patch below (also attached since my mailer sometimes eats spaces).
>> The differences between the old patch and the new one:
>> - removed deduce_freq (which was my least favorite part of the patch
>> anyway!), and its call from recompute_probabilities, since it is no
>> longer necessary.
>> - two new routines freqs_to_counts_path and clear_counts_path, invoked
>> from ssa_fix_duplicate_block_edges.
>> - two new tests
>>
>> Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk?
>>
>> Thanks,
>> Teresa
>>
>> gcc:
>>
>> 2014-09-29  Teresa Johnson  <tejohnson@google.com>
>>
>>          * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
>>          duplicate_blocks bitmap.
>>          (remove_ctrl_stmt_and_useless_edges): Ditto.
>>          (create_block_for_threading): Ditto.
>>          (compute_path_counts): New function.
>>          (update_profile): Ditto.
>>          (recompute_probabilities): Ditto.
>>          (update_joiner_offpath_counts): Ditto.
>>          (freqs_to_counts_path): Ditto.
>>          (clear_counts_path): Ditto.
>>          (ssa_fix_duplicate_block_edges): Update profile info.
>>          (ssa_create_duplicates): Pass new parameter.
>>          (ssa_redirect_edges): Remove old profile update.
>>          (thread_block_1): New duplicate_blocks bitmap,
>>          remove old profile update.
>>          (thread_single_edge): Pass new parameter.
>>
>> gcc/testsuite:
>>
>> 2014-09-29  Teresa Johnson  <tejohnson@google.com>
>>
>>          * testsuite/gcc.dg/tree-prof/20050826-2.c: New test.
>>          * testsuite/gcc.dg/tree-prof/cmpsf-1.c: Ditto.
>
> Given I'd already been through this pretty thoroughly, I just gave this a
> cursory review.
>
> clear_counts_path needs a function comment.  It's pretty obvious what it's
> doing, but for completeness let's go ahead and get the obvious comment in
> there.

Done and committed as r215739.

Thanks,
Teresa

>
> With that fix, approved for the trunk.  Thanks for taking the time to sort
> out all these issues.
>
> jeff
>
>



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Christophe Lyon]

On 30 September 2014 20:20, Teresa Johnson <tejohnson@google.com> wrote:
> On Mon, Sep 29, 2014 at 9:33 PM, Jeff Law <law@redhat.com> wrote:
>> On 09/29/14 08:19, Teresa Johnson wrote:
>>>>
>>>>
>>>> Just an update - I found some good test cases by compiling the
>>>> c-torture tests with profile feedback with and without my patch. But
>>>> in the cases I pulled out I saw that there were still a couple profile
>>>> or probability insanities introduced by jump threading (albeit far
>>>> less than before), so I wanted to investigate before I commit. I ran
>>>> out of time this week and will not get to this until I get back from
>>>> vacation the week after next.
>>>
>>>
>>> Hi Jeff,
>>>
>>> I finally had a chance to get back to this and look at the remaining
>>> insanities in the new test cases I created. It turns out that there
>>> were still a few issues in the case where there were guessed
>>> frequencies and no profile counts. The two test cases I created do use
>>> FDO, and the insanities in the routines with profile counts went away
>>> with my patch. But the outlined copies of routines that were also
>>> inlined into the main routine still had estimated frequencies, and
>>> these still had a few issues.
>>>
>>> The problem is that the profile updates are done incrementally as we
>>> walk and update the paths in ssa_fix_duplicate_block_edges, including
>>> the block and edge counts, the block frequencies and the
>>> probabilities. This is very difficult to do when only operating on
>>> frequencies since the edge frequencies are derived from the source
>>> block frequency and the probability. Therefore, once the source block
>>> frequency is updated, the edge frequency is also affected, and it is
>>> really difficult to figure out what the update to the edge frequency
>>> (essentially the probability) is using the same incremental update
>>> approach. I was attempting to handle this with the routine
>>> deduce_freq, for example, but this turned out to have issues for
>>> certain types of paths. I tried a few other approaches, but they start
>>> looking really ugly and I didn't want to add a parallel but different
>>> algorithm in the case of no profile counts.
>>>
>>> So by far the simplest approach was simply to take a snapshot of the
>>> existing block and edge frequencies along the path before we start the
>>> updates in ssa_fix_duplicate_block_edges, by copying them into the
>>> profile count fields of those blocks and edges. Then the existing
>>> algorithm operates the same as when we do have counts, and can
>>> essentially operate incrementally on the edge frequencies since they
>>> live in the count field of the edge and are no longer affected anytime
>>> the source block is updated. Since the algorithm does update block
>>> frequencies and probabilities as well (based on the count updates
>>> performed), we can simply clear out these fake count fields at the end
>>> of ssa_fix_duplicate_block_edges. This takes care of the remaining
>>> insanities introduced by jump threading from these test cases. During
>>> testing I also added in some checking to ensure that the count fields
>>> for the whole routine were cleared properly to make sure the new
>>> clear_counts_path was not missing anything (checking is a little too
>>> heavyweight to add in normally).
>>>
>>> New patch below (also attached since my mailer sometimes eats spaces).
>>> The differences between the old patch and the new one:
>>> - removed deduce_freq (which was my least favorite part of the patch
>>> anyway!), and its call from recompute_probabilities, since it is no
>>> longer necessary.
>>> - two new routines freqs_to_counts_path and clear_counts_path, invoked
>>> from ssa_fix_duplicate_block_edges.
>>> - two new tests
>>>
>>> Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk?
>>>
>>> Thanks,
>>> Teresa
>>>
>>> gcc:
>>>
>>> 2014-09-29  Teresa Johnson  <tejohnson@google.com>
>>>
>>>          * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
>>>          duplicate_blocks bitmap.
>>>          (remove_ctrl_stmt_and_useless_edges): Ditto.
>>>          (create_block_for_threading): Ditto.
>>>          (compute_path_counts): New function.
>>>          (update_profile): Ditto.
>>>          (recompute_probabilities): Ditto.
>>>          (update_joiner_offpath_counts): Ditto.
>>>          (freqs_to_counts_path): Ditto.
>>>          (clear_counts_path): Ditto.
>>>          (ssa_fix_duplicate_block_edges): Update profile info.
>>>          (ssa_create_duplicates): Pass new parameter.
>>>          (ssa_redirect_edges): Remove old profile update.
>>>          (thread_block_1): New duplicate_blocks bitmap,
>>>          remove old profile update.
>>>          (thread_single_edge): Pass new parameter.
>>>
>>> gcc/testsuite:
>>>
>>> 2014-09-29  Teresa Johnson  <tejohnson@google.com>
>>>
>>>          * testsuite/gcc.dg/tree-prof/20050826-2.c: New test.
>>>          * testsuite/gcc.dg/tree-prof/cmpsf-1.c: Ditto.
>>
>> Given I'd already been through this pretty thoroughly, I just gave this a
>> cursory review.
>>
>> clear_counts_path needs a function comment.  It's pretty obvious what it's
>> doing, but for completeness let's go ahead and get the obvious comment in
>> there.
>
> Done and committed as r215739.
>

Since this commit, I can see all my builds for arm*linux* and
aarch64*linux* fail while building glibc:

/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/aarch64-none-linux-gnu-gcc
iso-2022-cn.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Win
line -Wundef -Wwrite-strings -fmerge-all-constants -frounding-math -g
-Wstrict-prototypes   -fPIC        -I../include
-I/tmp/3496222_18.tmpdir/aci-gcc-f
sf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata
-I/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux
-gnu/glibc-1  -I../sysdeps/unix/sysv/linux/aarch64/nptl
-I../sysdeps/unix/sysv/linux/aarch64
-I../sysdeps/unix/sysv/linux/generic  -I../sysdeps/unix/s
ysv/linux/wordsize-64  -I../nptl/sysdeps/unix/sysv/linux
-I../nptl/sysdeps/pthread  -I../sysdeps/pthread
-I../sysdeps/unix/sysv/linux  -I../sysdeps/gn
u  -I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv
-I../sysdeps/unix/sysv  -I../nptl/sysdeps/unix  -I../sysdeps/unix
-I../sysdeps/posix  -I../sysd
eps/aarch64/fpu  -I../sysdeps/aarch64/nptl  -I../sysdeps/aarch64
-I../sysdeps/wordsize-64  -I../sysdeps/ieee754/ldbl-128
-I../sysdeps/ieee754/dbl-64/w
ordsize-64  -I../sysdeps/ieee754/dbl-64  -I../sysdeps/ieee754/flt-32
-I../sysdeps/aarch64/soft-fp  -I../sysdeps/ieee754
-I../sysdeps/generic  -I../npt
l  -I.. -I../libio -I. -nostdinc -isystem
/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include
-i
system /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include-fixed
-isystem /tmp/3496222_18.tmpdir
/aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-aarch64-none-linux-gnu/usr/include
 -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
-DNOT_IN_libc -o
/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
-MD -MP -MF /tmp/3
496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os.dt
-MT /tmp/3496222_18.tmpdir/aci-gcc-fsf
/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os

In file included from iso-2022-cn.c:407:0:
../iconv/skeleton.c: In function 'gconv':
../iconv/skeleton.c:800:1: internal compiler error: in
check_probability, at basic-block.h:959
0xe4e2fb find_many_sub_basic_blocks(simple_bitmap_def*)
        /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/basic-block.h:959
0x6623f0 execute
        /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/cfgexpand.c:5916
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

Can you have a look?

Thanks,

Christophe.

> Thanks,
> Teresa
>
>>
>> With that fix, approved for the trunk.  Thanks for taking the time to sort
>> out all these issues.
>>
>> jeff
>>
>>
>
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

Sorry, yes, will try to reproduce.
Teresa

On Wed, Oct 1, 2014 at 12:03 AM, Christophe Lyon
<christophe.lyon@linaro.org> wrote:
> On 30 September 2014 20:20, Teresa Johnson <tejohnson@google.com> wrote:
>> On Mon, Sep 29, 2014 at 9:33 PM, Jeff Law <law@redhat.com> wrote:
>>> On 09/29/14 08:19, Teresa Johnson wrote:
>>>>>
>>>>>
>>>>> Just an update - I found some good test cases by compiling the
>>>>> c-torture tests with profile feedback with and without my patch. But
>>>>> in the cases I pulled out I saw that there were still a couple profile
>>>>> or probability insanities introduced by jump threading (albeit far
>>>>> less than before), so I wanted to investigate before I commit. I ran
>>>>> out of time this week and will not get to this until I get back from
>>>>> vacation the week after next.
>>>>
>>>>
>>>> Hi Jeff,
>>>>
>>>> I finally had a chance to get back to this and look at the remaining
>>>> insanities in the new test cases I created. It turns out that there
>>>> were still a few issues in the case where there were guessed
>>>> frequencies and no profile counts. The two test cases I created do use
>>>> FDO, and the insanities in the routines with profile counts went away
>>>> with my patch. But the outlined copies of routines that were also
>>>> inlined into the main routine still had estimated frequencies, and
>>>> these still had a few issues.
>>>>
>>>> The problem is that the profile updates are done incrementally as we
>>>> walk and update the paths in ssa_fix_duplicate_block_edges, including
>>>> the block and edge counts, the block frequencies and the
>>>> probabilities. This is very difficult to do when only operating on
>>>> frequencies since the edge frequencies are derived from the source
>>>> block frequency and the probability. Therefore, once the source block
>>>> frequency is updated, the edge frequency is also affected, and it is
>>>> really difficult to figure out what the update to the edge frequency
>>>> (essentially the probability) is using the same incremental update
>>>> approach. I was attempting to handle this with the routine
>>>> deduce_freq, for example, but this turned out to have issues for
>>>> certain types of paths. I tried a few other approaches, but they start
>>>> looking really ugly and I didn't want to add a parallel but different
>>>> algorithm in the case of no profile counts.
>>>>
>>>> So by far the simplest approach was simply to take a snapshot of the
>>>> existing block and edge frequencies along the path before we start the
>>>> updates in ssa_fix_duplicate_block_edges, by copying them into the
>>>> profile count fields of those blocks and edges. Then the existing
>>>> algorithm operates the same as when we do have counts, and can
>>>> essentially operate incrementally on the edge frequencies since they
>>>> live in the count field of the edge and are no longer affected anytime
>>>> the source block is updated. Since the algorithm does update block
>>>> frequencies and probabilities as well (based on the count updates
>>>> performed), we can simply clear out these fake count fields at the end
>>>> of ssa_fix_duplicate_block_edges. This takes care of the remaining
>>>> insanities introduced by jump threading from these test cases. During
>>>> testing I also added in some checking to ensure that the count fields
>>>> for the whole routine were cleared properly to make sure the new
>>>> clear_counts_path was not missing anything (checking is a little too
>>>> heavyweight to add in normally).
>>>>
>>>> New patch below (also attached since my mailer sometimes eats spaces).
>>>> The differences between the old patch and the new one:
>>>> - removed deduce_freq (which was my least favorite part of the patch
>>>> anyway!), and its call from recompute_probabilities, since it is no
>>>> longer necessary.
>>>> - two new routines freqs_to_counts_path and clear_counts_path, invoked
>>>> from ssa_fix_duplicate_block_edges.
>>>> - two new tests
>>>>
>>>> Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk?
>>>>
>>>> Thanks,
>>>> Teresa
>>>>
>>>> gcc:
>>>>
>>>> 2014-09-29  Teresa Johnson  <tejohnson@google.com>
>>>>
>>>>          * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
>>>>          duplicate_blocks bitmap.
>>>>          (remove_ctrl_stmt_and_useless_edges): Ditto.
>>>>          (create_block_for_threading): Ditto.
>>>>          (compute_path_counts): New function.
>>>>          (update_profile): Ditto.
>>>>          (recompute_probabilities): Ditto.
>>>>          (update_joiner_offpath_counts): Ditto.
>>>>          (freqs_to_counts_path): Ditto.
>>>>          (clear_counts_path): Ditto.
>>>>          (ssa_fix_duplicate_block_edges): Update profile info.
>>>>          (ssa_create_duplicates): Pass new parameter.
>>>>          (ssa_redirect_edges): Remove old profile update.
>>>>          (thread_block_1): New duplicate_blocks bitmap,
>>>>          remove old profile update.
>>>>          (thread_single_edge): Pass new parameter.
>>>>
>>>> gcc/testsuite:
>>>>
>>>> 2014-09-29  Teresa Johnson  <tejohnson@google.com>
>>>>
>>>>          * testsuite/gcc.dg/tree-prof/20050826-2.c: New test.
>>>>          * testsuite/gcc.dg/tree-prof/cmpsf-1.c: Ditto.
>>>
>>> Given I'd already been through this pretty thoroughly, I just gave this a
>>> cursory review.
>>>
>>> clear_counts_path needs a function comment.  It's pretty obvious what it's
>>> doing, but for completeness let's go ahead and get the obvious comment in
>>> there.
>>
>> Done and committed as r215739.
>>
>
> Since this commit, I can see all my builds for arm*linux* and
> aarch64*linux* fail while building glibc:
>
> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/aarch64-none-linux-gnu-gcc
> iso-2022-cn.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Win
> line -Wundef -Wwrite-strings -fmerge-all-constants -frounding-math -g
> -Wstrict-prototypes   -fPIC        -I../include
> -I/tmp/3496222_18.tmpdir/aci-gcc-f
> sf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata
> -I/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux
> -gnu/glibc-1  -I../sysdeps/unix/sysv/linux/aarch64/nptl
> -I../sysdeps/unix/sysv/linux/aarch64
> -I../sysdeps/unix/sysv/linux/generic  -I../sysdeps/unix/s
> ysv/linux/wordsize-64  -I../nptl/sysdeps/unix/sysv/linux
> -I../nptl/sysdeps/pthread  -I../sysdeps/pthread
> -I../sysdeps/unix/sysv/linux  -I../sysdeps/gn
> u  -I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv
> -I../sysdeps/unix/sysv  -I../nptl/sysdeps/unix  -I../sysdeps/unix
> -I../sysdeps/posix  -I../sysd
> eps/aarch64/fpu  -I../sysdeps/aarch64/nptl  -I../sysdeps/aarch64
> -I../sysdeps/wordsize-64  -I../sysdeps/ieee754/ldbl-128
> -I../sysdeps/ieee754/dbl-64/w
> ordsize-64  -I../sysdeps/ieee754/dbl-64  -I../sysdeps/ieee754/flt-32
> -I../sysdeps/aarch64/soft-fp  -I../sysdeps/ieee754
> -I../sysdeps/generic  -I../npt
> l  -I.. -I../libio -I. -nostdinc -isystem
> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include
> -i
> system /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include-fixed
> -isystem /tmp/3496222_18.tmpdir
> /aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-aarch64-none-linux-gnu/usr/include
>  -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
> -DNOT_IN_libc -o
> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
> -MD -MP -MF /tmp/3
> 496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os.dt
> -MT /tmp/3496222_18.tmpdir/aci-gcc-fsf
> /builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>
> In file included from iso-2022-cn.c:407:0:
> ../iconv/skeleton.c: In function 'gconv':
> ../iconv/skeleton.c:800:1: internal compiler error: in
> check_probability, at basic-block.h:959
> 0xe4e2fb find_many_sub_basic_blocks(simple_bitmap_def*)
>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/basic-block.h:959
> 0x6623f0 execute
>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/cfgexpand.c:5916
> Please submit a full bug report,
> with preprocessed source if appropriate.
> Please include the complete backtrace with any bug report.
> See <http://gcc.gnu.org/bugs.html> for instructions.
>
> Can you have a look?
>
> Thanks,
>
> Christophe.
>
>> Thanks,
>> Teresa
>>
>>>
>>> With that fix, approved for the trunk.  Thanks for taking the time to sort
>>> out all these issues.
>>>
>>> jeff
>>>
>>>
>>
>>
>>
>> --
>> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Wed, Oct 1, 2014 at 6:20 AM, Teresa Johnson <tejohnson@google.com> wrote:
> Sorry, yes, will try to reproduce.
> Teresa
>
> On Wed, Oct 1, 2014 at 12:03 AM, Christophe Lyon
> <christophe.lyon@linaro.org> wrote:
>> On 30 September 2014 20:20, Teresa Johnson <tejohnson@google.com> wrote:
>>> On Mon, Sep 29, 2014 at 9:33 PM, Jeff Law <law@redhat.com> wrote:
>>>> On 09/29/14 08:19, Teresa Johnson wrote:
>>>>>>
>>>>>>
>>>>>> Just an update - I found some good test cases by compiling the
>>>>>> c-torture tests with profile feedback with and without my patch. But
>>>>>> in the cases I pulled out I saw that there were still a couple profile
>>>>>> or probability insanities introduced by jump threading (albeit far
>>>>>> less than before), so I wanted to investigate before I commit. I ran
>>>>>> out of time this week and will not get to this until I get back from
>>>>>> vacation the week after next.
>>>>>
>>>>>
>>>>> Hi Jeff,
>>>>>
>>>>> I finally had a chance to get back to this and look at the remaining
>>>>> insanities in the new test cases I created. It turns out that there
>>>>> were still a few issues in the case where there were guessed
>>>>> frequencies and no profile counts. The two test cases I created do use
>>>>> FDO, and the insanities in the routines with profile counts went away
>>>>> with my patch. But the outlined copies of routines that were also
>>>>> inlined into the main routine still had estimated frequencies, and
>>>>> these still had a few issues.
>>>>>
>>>>> The problem is that the profile updates are done incrementally as we
>>>>> walk and update the paths in ssa_fix_duplicate_block_edges, including
>>>>> the block and edge counts, the block frequencies and the
>>>>> probabilities. This is very difficult to do when only operating on
>>>>> frequencies since the edge frequencies are derived from the source
>>>>> block frequency and the probability. Therefore, once the source block
>>>>> frequency is updated, the edge frequency is also affected, and it is
>>>>> really difficult to figure out what the update to the edge frequency
>>>>> (essentially the probability) is using the same incremental update
>>>>> approach. I was attempting to handle this with the routine
>>>>> deduce_freq, for example, but this turned out to have issues for
>>>>> certain types of paths. I tried a few other approaches, but they start
>>>>> looking really ugly and I didn't want to add a parallel but different
>>>>> algorithm in the case of no profile counts.
>>>>>
>>>>> So by far the simplest approach was simply to take a snapshot of the
>>>>> existing block and edge frequencies along the path before we start the
>>>>> updates in ssa_fix_duplicate_block_edges, by copying them into the
>>>>> profile count fields of those blocks and edges. Then the existing
>>>>> algorithm operates the same as when we do have counts, and can
>>>>> essentially operate incrementally on the edge frequencies since they
>>>>> live in the count field of the edge and are no longer affected anytime
>>>>> the source block is updated. Since the algorithm does update block
>>>>> frequencies and probabilities as well (based on the count updates
>>>>> performed), we can simply clear out these fake count fields at the end
>>>>> of ssa_fix_duplicate_block_edges. This takes care of the remaining
>>>>> insanities introduced by jump threading from these test cases. During
>>>>> testing I also added in some checking to ensure that the count fields
>>>>> for the whole routine were cleared properly to make sure the new
>>>>> clear_counts_path was not missing anything (checking is a little too
>>>>> heavyweight to add in normally).
>>>>>
>>>>> New patch below (also attached since my mailer sometimes eats spaces).
>>>>> The differences between the old patch and the new one:
>>>>> - removed deduce_freq (which was my least favorite part of the patch
>>>>> anyway!), and its call from recompute_probabilities, since it is no
>>>>> longer necessary.
>>>>> - two new routines freqs_to_counts_path and clear_counts_path, invoked
>>>>> from ssa_fix_duplicate_block_edges.
>>>>> - two new tests
>>>>>
>>>>> Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk?
>>>>>
>>>>> Thanks,
>>>>> Teresa
>>>>>
>>>>> gcc:
>>>>>
>>>>> 2014-09-29  Teresa Johnson  <tejohnson@google.com>
>>>>>
>>>>>          * tree-ssa-threadupdate.c (struct ssa_local_info_t): New
>>>>>          duplicate_blocks bitmap.
>>>>>          (remove_ctrl_stmt_and_useless_edges): Ditto.
>>>>>          (create_block_for_threading): Ditto.
>>>>>          (compute_path_counts): New function.
>>>>>          (update_profile): Ditto.
>>>>>          (recompute_probabilities): Ditto.
>>>>>          (update_joiner_offpath_counts): Ditto.
>>>>>          (freqs_to_counts_path): Ditto.
>>>>>          (clear_counts_path): Ditto.
>>>>>          (ssa_fix_duplicate_block_edges): Update profile info.
>>>>>          (ssa_create_duplicates): Pass new parameter.
>>>>>          (ssa_redirect_edges): Remove old profile update.
>>>>>          (thread_block_1): New duplicate_blocks bitmap,
>>>>>          remove old profile update.
>>>>>          (thread_single_edge): Pass new parameter.
>>>>>
>>>>> gcc/testsuite:
>>>>>
>>>>> 2014-09-29  Teresa Johnson  <tejohnson@google.com>
>>>>>
>>>>>          * testsuite/gcc.dg/tree-prof/20050826-2.c: New test.
>>>>>          * testsuite/gcc.dg/tree-prof/cmpsf-1.c: Ditto.
>>>>
>>>> Given I'd already been through this pretty thoroughly, I just gave this a
>>>> cursory review.
>>>>
>>>> clear_counts_path needs a function comment.  It's pretty obvious what it's
>>>> doing, but for completeness let's go ahead and get the obvious comment in
>>>> there.
>>>
>>> Done and committed as r215739.
>>>
>>
>> Since this commit, I can see all my builds for arm*linux* and
>> aarch64*linux* fail while building glibc:
>>
>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/aarch64-none-linux-gnu-gcc
>> iso-2022-cn.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Win
>> line -Wundef -Wwrite-strings -fmerge-all-constants -frounding-math -g
>> -Wstrict-prototypes   -fPIC        -I../include
>> -I/tmp/3496222_18.tmpdir/aci-gcc-f
>> sf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata
>> -I/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux
>> -gnu/glibc-1  -I../sysdeps/unix/sysv/linux/aarch64/nptl
>> -I../sysdeps/unix/sysv/linux/aarch64
>> -I../sysdeps/unix/sysv/linux/generic  -I../sysdeps/unix/s
>> ysv/linux/wordsize-64  -I../nptl/sysdeps/unix/sysv/linux
>> -I../nptl/sysdeps/pthread  -I../sysdeps/pthread
>> -I../sysdeps/unix/sysv/linux  -I../sysdeps/gn
>> u  -I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv
>> -I../sysdeps/unix/sysv  -I../nptl/sysdeps/unix  -I../sysdeps/unix
>> -I../sysdeps/posix  -I../sysd
>> eps/aarch64/fpu  -I../sysdeps/aarch64/nptl  -I../sysdeps/aarch64
>> -I../sysdeps/wordsize-64  -I../sysdeps/ieee754/ldbl-128
>> -I../sysdeps/ieee754/dbl-64/w
>> ordsize-64  -I../sysdeps/ieee754/dbl-64  -I../sysdeps/ieee754/flt-32
>> -I../sysdeps/aarch64/soft-fp  -I../sysdeps/ieee754
>> -I../sysdeps/generic  -I../npt
>> l  -I.. -I../libio -I. -nostdinc -isystem
>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include
>> -i
>> system /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include-fixed
>> -isystem /tmp/3496222_18.tmpdir
>> /aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-aarch64-none-linux-gnu/usr/include
>>  -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
>> -DNOT_IN_libc -o
>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>> -MD -MP -MF /tmp/3
>> 496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os.dt
>> -MT /tmp/3496222_18.tmpdir/aci-gcc-fsf
>> /builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>>
>> In file included from iso-2022-cn.c:407:0:
>> ../iconv/skeleton.c: In function 'gconv':
>> ../iconv/skeleton.c:800:1: internal compiler error: in
>> check_probability, at basic-block.h:959
>> 0xe4e2fb find_many_sub_basic_blocks(simple_bitmap_def*)
>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/basic-block.h:959
>> 0x6623f0 execute
>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/cfgexpand.c:5916
>> Please submit a full bug report,
>> with preprocessed source if appropriate.
>> Please include the complete backtrace with any bug report.
>> See <http://gcc.gnu.org/bugs.html> for instructions.
>>
>> Can you have a look?

Unfortunately doesn't reproduce with x86_64, so I will build an
aarch64 cross-compiler next and give that a try. This was with the
latest glibc sources I git cloned from sourceware.org. Let me know if
I need something else.

Also, the instructions I found for configuring an aarch64 cross-compiler are:

./configure --prefix=$prefix \
    --target=aarch64-none-linux --enable-languages=c \
    --disable-threads --disable-shared --disable-libmudflap \
    --disable-libssp --disable-libgomp --disable-libquadmath

Let me know if I need to configure it differently.

Thanks,
Teresa

>>
>> Thanks,
>>
>> Christophe.
>>
>>> Thanks,
>>> Teresa
>>>
>>>>
>>>> With that fix, approved for the trunk.  Thanks for taking the time to sort
>>>> out all these issues.
>>>>
>>>> jeff
>>>>
>>>>
>>>
>>>
>>>
>>> --
>>> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413
>
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Sebastian Pop]

Christophe Lyon wrote:
> Since this commit, I can see all my builds for arm*linux* and
> aarch64*linux* fail while building glibc:
> 
> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/aarch64-none-linux-gnu-gcc
> iso-2022-cn.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Win
> line -Wundef -Wwrite-strings -fmerge-all-constants -frounding-math -g
> -Wstrict-prototypes   -fPIC        -I../include
> -I/tmp/3496222_18.tmpdir/aci-gcc-f
> sf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata
> -I/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux
> -gnu/glibc-1  -I../sysdeps/unix/sysv/linux/aarch64/nptl
> -I../sysdeps/unix/sysv/linux/aarch64
> -I../sysdeps/unix/sysv/linux/generic  -I../sysdeps/unix/s
> ysv/linux/wordsize-64  -I../nptl/sysdeps/unix/sysv/linux
> -I../nptl/sysdeps/pthread  -I../sysdeps/pthread
> -I../sysdeps/unix/sysv/linux  -I../sysdeps/gn
> u  -I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv
> -I../sysdeps/unix/sysv  -I../nptl/sysdeps/unix  -I../sysdeps/unix
> -I../sysdeps/posix  -I../sysd
> eps/aarch64/fpu  -I../sysdeps/aarch64/nptl  -I../sysdeps/aarch64
> -I../sysdeps/wordsize-64  -I../sysdeps/ieee754/ldbl-128
> -I../sysdeps/ieee754/dbl-64/w
> ordsize-64  -I../sysdeps/ieee754/dbl-64  -I../sysdeps/ieee754/flt-32
> -I../sysdeps/aarch64/soft-fp  -I../sysdeps/ieee754
> -I../sysdeps/generic  -I../npt
> l  -I.. -I../libio -I. -nostdinc -isystem
> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include
> -i
> system /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include-fixed
> -isystem /tmp/3496222_18.tmpdir
> /aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-aarch64-none-linux-gnu/usr/include
>  -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
> -DNOT_IN_libc -o
> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
> -MD -MP -MF /tmp/3
> 496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os.dt
> -MT /tmp/3496222_18.tmpdir/aci-gcc-fsf
> /builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
> 
> In file included from iso-2022-cn.c:407:0:
> ../iconv/skeleton.c: In function 'gconv':
> ../iconv/skeleton.c:800:1: internal compiler error: in
> check_probability, at basic-block.h:959
> 0xe4e2fb find_many_sub_basic_blocks(simple_bitmap_def*)
>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/basic-block.h:959
> 0x6623f0 execute
>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/cfgexpand.c:5916
> Please submit a full bug report,
> with preprocessed source if appropriate.
> Please include the complete backtrace with any bug report.
> See <http://gcc.gnu.org/bugs.html> for instructions.
> 
> Can you have a look?

It would help if you could attach a preprocessed file.

Thanks,
Sebastian

Re: [PATCH] Redesign jump threading profile updates

[Christophe Lyon]

On 1 October 2014 17:22, Sebastian Pop <sebpop@gmail.com> wrote:
> Christophe Lyon wrote:
>> Since this commit, I can see all my builds for arm*linux* and
>> aarch64*linux* fail while building glibc:
>>
>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/aarch64-none-linux-gnu-gcc
>> iso-2022-cn.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Win
>> line -Wundef -Wwrite-strings -fmerge-all-constants -frounding-math -g
>> -Wstrict-prototypes   -fPIC        -I../include
>> -I/tmp/3496222_18.tmpdir/aci-gcc-f
>> sf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata
>> -I/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux
>> -gnu/glibc-1  -I../sysdeps/unix/sysv/linux/aarch64/nptl
>> -I../sysdeps/unix/sysv/linux/aarch64
>> -I../sysdeps/unix/sysv/linux/generic  -I../sysdeps/unix/s
>> ysv/linux/wordsize-64  -I../nptl/sysdeps/unix/sysv/linux
>> -I../nptl/sysdeps/pthread  -I../sysdeps/pthread
>> -I../sysdeps/unix/sysv/linux  -I../sysdeps/gn
>> u  -I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv
>> -I../sysdeps/unix/sysv  -I../nptl/sysdeps/unix  -I../sysdeps/unix
>> -I../sysdeps/posix  -I../sysd
>> eps/aarch64/fpu  -I../sysdeps/aarch64/nptl  -I../sysdeps/aarch64
>> -I../sysdeps/wordsize-64  -I../sysdeps/ieee754/ldbl-128
>> -I../sysdeps/ieee754/dbl-64/w
>> ordsize-64  -I../sysdeps/ieee754/dbl-64  -I../sysdeps/ieee754/flt-32
>> -I../sysdeps/aarch64/soft-fp  -I../sysdeps/ieee754
>> -I../sysdeps/generic  -I../npt
>> l  -I.. -I../libio -I. -nostdinc -isystem
>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include
>> -i
>> system /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include-fixed
>> -isystem /tmp/3496222_18.tmpdir
>> /aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-aarch64-none-linux-gnu/usr/include
>>  -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
>> -DNOT_IN_libc -o
>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>> -MD -MP -MF /tmp/3
>> 496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os.dt
>> -MT /tmp/3496222_18.tmpdir/aci-gcc-fsf
>> /builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>>
>> In file included from iso-2022-cn.c:407:0:
>> ../iconv/skeleton.c: In function 'gconv':
>> ../iconv/skeleton.c:800:1: internal compiler error: in
>> check_probability, at basic-block.h:959
>> 0xe4e2fb find_many_sub_basic_blocks(simple_bitmap_def*)
>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/basic-block.h:959
>> 0x6623f0 execute
>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/cfgexpand.c:5916
>> Please submit a full bug report,
>> with preprocessed source if appropriate.
>> Please include the complete backtrace with any bug report.
>> See <http://gcc.gnu.org/bugs.html> for instructions.
>>
>> Can you have a look?
>
> It would help if you could attach a preprocessed file.
>
I did it in a followup mail, but the list server rejected it because
it was too large.
I suppose Teresa did receive it though.

Not sure whether I can attach it in .xz format? Is this allowed?

Thanks
Christophe.

> Thanks,
> Sebastian

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

I got the preprocessed source. With the aarch64 cross-compiler I built
I am able to reproduce the ICE. Looking at it now.

Thanks,
Teresa

On Wed, Oct 1, 2014 at 8:25 AM, Christophe Lyon
<christophe.lyon@linaro.org> wrote:
> On 1 October 2014 17:22, Sebastian Pop <sebpop@gmail.com> wrote:
>> Christophe Lyon wrote:
>>> Since this commit, I can see all my builds for arm*linux* and
>>> aarch64*linux* fail while building glibc:
>>>
>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/aarch64-none-linux-gnu-gcc
>>> iso-2022-cn.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Win
>>> line -Wundef -Wwrite-strings -fmerge-all-constants -frounding-math -g
>>> -Wstrict-prototypes   -fPIC        -I../include
>>> -I/tmp/3496222_18.tmpdir/aci-gcc-f
>>> sf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata
>>> -I/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux
>>> -gnu/glibc-1  -I../sysdeps/unix/sysv/linux/aarch64/nptl
>>> -I../sysdeps/unix/sysv/linux/aarch64
>>> -I../sysdeps/unix/sysv/linux/generic  -I../sysdeps/unix/s
>>> ysv/linux/wordsize-64  -I../nptl/sysdeps/unix/sysv/linux
>>> -I../nptl/sysdeps/pthread  -I../sysdeps/pthread
>>> -I../sysdeps/unix/sysv/linux  -I../sysdeps/gn
>>> u  -I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv
>>> -I../sysdeps/unix/sysv  -I../nptl/sysdeps/unix  -I../sysdeps/unix
>>> -I../sysdeps/posix  -I../sysd
>>> eps/aarch64/fpu  -I../sysdeps/aarch64/nptl  -I../sysdeps/aarch64
>>> -I../sysdeps/wordsize-64  -I../sysdeps/ieee754/ldbl-128
>>> -I../sysdeps/ieee754/dbl-64/w
>>> ordsize-64  -I../sysdeps/ieee754/dbl-64  -I../sysdeps/ieee754/flt-32
>>> -I../sysdeps/aarch64/soft-fp  -I../sysdeps/ieee754
>>> -I../sysdeps/generic  -I../npt
>>> l  -I.. -I../libio -I. -nostdinc -isystem
>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include
>>> -i
>>> system /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include-fixed
>>> -isystem /tmp/3496222_18.tmpdir
>>> /aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-aarch64-none-linux-gnu/usr/include
>>>  -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
>>> -DNOT_IN_libc -o
>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>>> -MD -MP -MF /tmp/3
>>> 496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os.dt
>>> -MT /tmp/3496222_18.tmpdir/aci-gcc-fsf
>>> /builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>>>
>>> In file included from iso-2022-cn.c:407:0:
>>> ../iconv/skeleton.c: In function 'gconv':
>>> ../iconv/skeleton.c:800:1: internal compiler error: in
>>> check_probability, at basic-block.h:959
>>> 0xe4e2fb find_many_sub_basic_blocks(simple_bitmap_def*)
>>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/basic-block.h:959
>>> 0x6623f0 execute
>>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/cfgexpand.c:5916
>>> Please submit a full bug report,
>>> with preprocessed source if appropriate.
>>> Please include the complete backtrace with any bug report.
>>> See <http://gcc.gnu.org/bugs.html> for instructions.
>>>
>>> Can you have a look?
>>
>> It would help if you could attach a preprocessed file.
>>
> I did it in a followup mail, but the list server rejected it because
> it was too large.
> I suppose Teresa did receive it though.
>
> Not sure whether I can attach it in .xz format? Is this allowed?
>
> Thanks
> Christophe.
>
>> Thanks,
>> Sebastian



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Sebastian Pop]

Christophe Lyon wrote:
> I did it in a followup mail, but the list server rejected it because
> it was too large.
> I suppose Teresa did receive it though.
> 
> Not sure whether I can attach it in .xz format? Is this allowed?

You can open a bug report and attach the preprocessed file there.

Thanks,
Sebastian

Re: [PATCH] Redesign jump threading profile updates

[H.J. Lu]

On Wed, Oct 1, 2014 at 8:29 AM, Teresa Johnson <tejohnson@google.com> wrote:
> I got the preprocessed source. With the aarch64 cross-compiler I built
> I am able to reproduce the ICE. Looking at it now.

It may also cause:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63432


-- 
H.J.

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Wed, Oct 1, 2014 at 9:20 AM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Wed, Oct 1, 2014 at 8:29 AM, Teresa Johnson <tejohnson@google.com> wrote:
>> I got the preprocessed source. With the aarch64 cross-compiler I built
>> I am able to reproduce the ICE. Looking at it now.
>
> It may also cause:
>
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63432

That looks like a dup of
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63422, which I just
diagnosed to be due to incoming profile insanities. I will loosen up
my new assert to deal with that one.

Teresa

>
>
> --
> H.J.



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

The block frequencies are very small in this case leading to rounding
errors when computing the edge frequency. The rounding error was then
propagated into the recomputed probabilities, leading to insanities in
the outgoing edge probabilities on the jump threading path. Eventually
during rtl expansion these insanities somehow caused an ICE.

(Before this patch the probabilities weren't even being updated,
leading to insanities in other cases where they needed to be updated.)

Specifically, in this case we had a block with frequency = 1. It had
two outgoing edges each with probability 50%. Because the
EDGE_FREQUENCY computation uses a rounding divide, the outgoing edge
frequencies were both computed as 1. Later use of these block and edge
frequencies to recompute the probability lead to both outgoing edges
getting 100%.

To address this, in the routine freqs_to_counts_path can simply scale
up the frequencies when recording them in the count field. I added a
scale by REG_BR_PROB_BASE. The largest count possible would therefore
be REG_BR_PROB_BASE * BB_FREQ_MAX which is 10000 * 10000 = 100mil
which safely fits in gcov_type.

Here is the patch I am testing. Confirmed it fixes the reported issue.
Currently bootstrapping and testing on x86_64-unknown-linux-gnu. Ok
for trunk if it passes?

(The whitespace is getting messed up when I copy the patch in here -
the indentations do line up in the patch.)

Thanks,
Teresa

2014-10-01  Teresa Johnson  <tejohnson@google.com>

        * tree-ssa-threadupdate.c (freqs_to_counts_path): Scale frequencies
        up when synthesizing counts to avoid rounding errors.

Index: tree-ssa-threadupdate.c
===================================================================
--- tree-ssa-threadupdate.c     (revision 215739)
+++ tree-ssa-threadupdate.c     (working copy)
@@ -979,7 +979,11 @@ freqs_to_counts_path (struct redirection_data *rd)
   FOR_EACH_EDGE (ein, ei, e->dest->preds)
     {
       gcc_assert (!ein->count);
-      ein->count = EDGE_FREQUENCY (ein);
+      /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
+         errors applying the probability when the frequencies are very
+         small.  */
+      ein->count = apply_probability (ein->src->frequency * REG_BR_PROB_BASE,
+                                      ein->probability);
     }

   for (unsigned int i = 1; i < path->length (); i++)
@@ -987,11 +991,13 @@ freqs_to_counts_path (struct redirection_data *rd)
       edge epath = (*path)[i]->e;
       gcc_assert (!epath->count);
       edge esucc;
+      /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
+         errors applying the edge probability when the frequencies are very
+         small.  */
+      epath->src->count = epath->src->frequency * REG_BR_PROB_BASE;
       FOR_EACH_EDGE (esucc, ei, epath->src->succs)
-        {
-          esucc->count = EDGE_FREQUENCY (esucc);
-        }
-      epath->src->count = epath->src->frequency;
+        esucc->count = apply_probability (esucc->src->count,
+                                          esucc->probability);
     }
 }


On Wed, Oct 1, 2014 at 8:29 AM, Teresa Johnson <tejohnson@google.com> wrote:
> I got the preprocessed source. With the aarch64 cross-compiler I built
> I am able to reproduce the ICE. Looking at it now.
>
> Thanks,
> Teresa
>
> On Wed, Oct 1, 2014 at 8:25 AM, Christophe Lyon
> <christophe.lyon@linaro.org> wrote:
>> On 1 October 2014 17:22, Sebastian Pop <sebpop@gmail.com> wrote:
>>> Christophe Lyon wrote:
>>>> Since this commit, I can see all my builds for arm*linux* and
>>>> aarch64*linux* fail while building glibc:
>>>>
>>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/aarch64-none-linux-gnu-gcc
>>>> iso-2022-cn.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Win
>>>> line -Wundef -Wwrite-strings -fmerge-all-constants -frounding-math -g
>>>> -Wstrict-prototypes   -fPIC        -I../include
>>>> -I/tmp/3496222_18.tmpdir/aci-gcc-f
>>>> sf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata
>>>> -I/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux
>>>> -gnu/glibc-1  -I../sysdeps/unix/sysv/linux/aarch64/nptl
>>>> -I../sysdeps/unix/sysv/linux/aarch64
>>>> -I../sysdeps/unix/sysv/linux/generic  -I../sysdeps/unix/s
>>>> ysv/linux/wordsize-64  -I../nptl/sysdeps/unix/sysv/linux
>>>> -I../nptl/sysdeps/pthread  -I../sysdeps/pthread
>>>> -I../sysdeps/unix/sysv/linux  -I../sysdeps/gn
>>>> u  -I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv
>>>> -I../sysdeps/unix/sysv  -I../nptl/sysdeps/unix  -I../sysdeps/unix
>>>> -I../sysdeps/posix  -I../sysd
>>>> eps/aarch64/fpu  -I../sysdeps/aarch64/nptl  -I../sysdeps/aarch64
>>>> -I../sysdeps/wordsize-64  -I../sysdeps/ieee754/ldbl-128
>>>> -I../sysdeps/ieee754/dbl-64/w
>>>> ordsize-64  -I../sysdeps/ieee754/dbl-64  -I../sysdeps/ieee754/flt-32
>>>> -I../sysdeps/aarch64/soft-fp  -I../sysdeps/ieee754
>>>> -I../sysdeps/generic  -I../npt
>>>> l  -I.. -I../libio -I. -nostdinc -isystem
>>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include
>>>> -i
>>>> system /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include-fixed
>>>> -isystem /tmp/3496222_18.tmpdir
>>>> /aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-aarch64-none-linux-gnu/usr/include
>>>>  -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
>>>> -DNOT_IN_libc -o
>>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>>>> -MD -MP -MF /tmp/3
>>>> 496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os.dt
>>>> -MT /tmp/3496222_18.tmpdir/aci-gcc-fsf
>>>> /builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>>>>
>>>> In file included from iso-2022-cn.c:407:0:
>>>> ../iconv/skeleton.c: In function 'gconv':
>>>> ../iconv/skeleton.c:800:1: internal compiler error: in
>>>> check_probability, at basic-block.h:959
>>>> 0xe4e2fb find_many_sub_basic_blocks(simple_bitmap_def*)
>>>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/basic-block.h:959
>>>> 0x6623f0 execute
>>>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/cfgexpand.c:5916
>>>> Please submit a full bug report,
>>>> with preprocessed source if appropriate.
>>>> Please include the complete backtrace with any bug report.
>>>> See <http://gcc.gnu.org/bugs.html> for instructions.
>>>>
>>>> Can you have a look?
>>>
>>> It would help if you could attach a preprocessed file.
>>>
>> I did it in a followup mail, but the list server rejected it because
>> it was too large.
>> I suppose Teresa did receive it though.
>>
>> Not sure whether I can attach it in .xz format? Is this allowed?
>>
>> Thanks
>> Christophe.
>>
>>> Thanks,
>>> Sebastian
>
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Steve Ellcey]

On Wed, 2014-10-01 at 13:04 -0700, Teresa Johnson wrote:

> 2014-10-01  Teresa Johnson  <tejohnson@google.com>
> 
>         * tree-ssa-threadupdate.c (freqs_to_counts_path): Scale frequencies
>         up when synthesizing counts to avoid rounding errors.

I tried this patch on my MIPS toolchain build but GCC is still failing
while building glibc.

iconv_open.c: In function 'iconv_open':
iconv_open.c:32:1: error: verify_flow_info: Wrong probability of edge
14->18 -920374544
 iconv_open (const char *tocode, const char *fromcode)
 ^
iconv_open.c:32:1: error: verify_flow_info: Wrong probability of edge
14->19 -903724544
iconv_open.c:32:1: internal compiler error: verify_flow_info failed
0x626a70 verify_flow_info()
        /scratch/sellcey/repos/nightly/src/gcc/gcc/cfghooks.c:260
0x9f36e4 cleanup_tree_cfg_noloop
        /scratch/sellcey/repos/nightly/src/gcc/gcc/tree-cfgcleanup.c:765
0x9f36e4 cleanup_tree_cfg()
        /scratch/sellcey/repos/nightly/src/gcc/gcc/tree-cfgcleanup.c:814
0x8eeff4 execute_function_todo
        /scratch/sellcey/repos/nightly/src/gcc/gcc/passes.c:1704
0x8efb23 execute_todo
        /scratch/sellcey/repos/nightly/src/gcc/gcc/passes.c:1808
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

Re: [PATCH] Redesign jump threading profile updates

[Jan Hubicka]

> The block frequencies are very small in this case leading to rounding
> errors when computing the edge frequency. The rounding error was then
> propagated into the recomputed probabilities, leading to insanities in
> the outgoing edge probabilities on the jump threading path. Eventually
> during rtl expansion these insanities somehow caused an ICE.

Concerning the never ending rounoff issues, I thing we ought to progress
on turning counts, freqs and probabilities into a type that eliminates
most of this fun.

I see basically two options - first would be to take wide_int and build
a fixed point type template around it (so one can chose precisions),
other would be to have software emulated floating point type.

Actually I think the second will be less troublesome - FP seems to fit
the bill very well.  We already have sreal.h that does the job for
propagation of frequencies.  What about turning it ito C++ type with
operations on it and reroganizing code to use it?
(we may consider making the base 64bit, as opposed to HOST_WIDE_INT
right now)

Or are there other options I missed? It would be very cool if someone
could volunteer and implement the basic datatype and possibly start with
convertion.

I think we could do type by type, first redefining counts from gcov_t
and relying on conversion to gcov_t to work to not having to update all
uses at once.  THen we can just update the code pass by pass.

One nice thing we could add into the type is to make difference in betwen
known zeros (i.e. read from profile) and zeros that were results of updates
that may or may not be precise.  THis should hopefully solve the bad
iteraction of Martin's code ordering and Theresa's BB-reorder work.

Honza
> 
> (Before this patch the probabilities weren't even being updated,
> leading to insanities in other cases where they needed to be updated.)
> 
> Specifically, in this case we had a block with frequency = 1. It had
> two outgoing edges each with probability 50%. Because the
> EDGE_FREQUENCY computation uses a rounding divide, the outgoing edge
> frequencies were both computed as 1. Later use of these block and edge
> frequencies to recompute the probability lead to both outgoing edges
> getting 100%.
> 
> To address this, in the routine freqs_to_counts_path can simply scale
> up the frequencies when recording them in the count field. I added a
> scale by REG_BR_PROB_BASE. The largest count possible would therefore
> be REG_BR_PROB_BASE * BB_FREQ_MAX which is 10000 * 10000 = 100mil
> which safely fits in gcov_type.
> 
> Here is the patch I am testing. Confirmed it fixes the reported issue.
> Currently bootstrapping and testing on x86_64-unknown-linux-gnu. Ok
> for trunk if it passes?
> 
> (The whitespace is getting messed up when I copy the patch in here -
> the indentations do line up in the patch.)
> 
> Thanks,
> Teresa
> 
> 2014-10-01  Teresa Johnson  <tejohnson@google.com>
> 
>         * tree-ssa-threadupdate.c (freqs_to_counts_path): Scale frequencies
>         up when synthesizing counts to avoid rounding errors.
> 
> Index: tree-ssa-threadupdate.c
> ===================================================================
> --- tree-ssa-threadupdate.c     (revision 215739)
> +++ tree-ssa-threadupdate.c     (working copy)
> @@ -979,7 +979,11 @@ freqs_to_counts_path (struct redirection_data *rd)
>    FOR_EACH_EDGE (ein, ei, e->dest->preds)
>      {
>        gcc_assert (!ein->count);
> -      ein->count = EDGE_FREQUENCY (ein);
> +      /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
> +         errors applying the probability when the frequencies are very
> +         small.  */
> +      ein->count = apply_probability (ein->src->frequency * REG_BR_PROB_BASE,
> +                                      ein->probability);
>      }
> 
>    for (unsigned int i = 1; i < path->length (); i++)
> @@ -987,11 +991,13 @@ freqs_to_counts_path (struct redirection_data *rd)
>        edge epath = (*path)[i]->e;
>        gcc_assert (!epath->count);
>        edge esucc;
> +      /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
> +         errors applying the edge probability when the frequencies are very
> +         small.  */
> +      epath->src->count = epath->src->frequency * REG_BR_PROB_BASE;
>        FOR_EACH_EDGE (esucc, ei, epath->src->succs)
> -        {
> -          esucc->count = EDGE_FREQUENCY (esucc);
> -        }
> -      epath->src->count = epath->src->frequency;
> +        esucc->count = apply_probability (esucc->src->count,
> +                                          esucc->probability);
>      }
>  }
> 
> 
> On Wed, Oct 1, 2014 at 8:29 AM, Teresa Johnson <tejohnson@google.com> wrote:
> > I got the preprocessed source. With the aarch64 cross-compiler I built
> > I am able to reproduce the ICE. Looking at it now.
> >
> > Thanks,
> > Teresa
> >
> > On Wed, Oct 1, 2014 at 8:25 AM, Christophe Lyon
> > <christophe.lyon@linaro.org> wrote:
> >> On 1 October 2014 17:22, Sebastian Pop <sebpop@gmail.com> wrote:
> >>> Christophe Lyon wrote:
> >>>> Since this commit, I can see all my builds for arm*linux* and
> >>>> aarch64*linux* fail while building glibc:
> >>>>
> >>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/aarch64-none-linux-gnu-gcc
> >>>> iso-2022-cn.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Win
> >>>> line -Wundef -Wwrite-strings -fmerge-all-constants -frounding-math -g
> >>>> -Wstrict-prototypes   -fPIC        -I../include
> >>>> -I/tmp/3496222_18.tmpdir/aci-gcc-f
> >>>> sf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata
> >>>> -I/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux
> >>>> -gnu/glibc-1  -I../sysdeps/unix/sysv/linux/aarch64/nptl
> >>>> -I../sysdeps/unix/sysv/linux/aarch64
> >>>> -I../sysdeps/unix/sysv/linux/generic  -I../sysdeps/unix/s
> >>>> ysv/linux/wordsize-64  -I../nptl/sysdeps/unix/sysv/linux
> >>>> -I../nptl/sysdeps/pthread  -I../sysdeps/pthread
> >>>> -I../sysdeps/unix/sysv/linux  -I../sysdeps/gn
> >>>> u  -I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv
> >>>> -I../sysdeps/unix/sysv  -I../nptl/sysdeps/unix  -I../sysdeps/unix
> >>>> -I../sysdeps/posix  -I../sysd
> >>>> eps/aarch64/fpu  -I../sysdeps/aarch64/nptl  -I../sysdeps/aarch64
> >>>> -I../sysdeps/wordsize-64  -I../sysdeps/ieee754/ldbl-128
> >>>> -I../sysdeps/ieee754/dbl-64/w
> >>>> ordsize-64  -I../sysdeps/ieee754/dbl-64  -I../sysdeps/ieee754/flt-32
> >>>> -I../sysdeps/aarch64/soft-fp  -I../sysdeps/ieee754
> >>>> -I../sysdeps/generic  -I../npt
> >>>> l  -I.. -I../libio -I. -nostdinc -isystem
> >>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include
> >>>> -i
> >>>> system /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include-fixed
> >>>> -isystem /tmp/3496222_18.tmpdir
> >>>> /aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-aarch64-none-linux-gnu/usr/include
> >>>>  -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
> >>>> -DNOT_IN_libc -o
> >>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
> >>>> -MD -MP -MF /tmp/3
> >>>> 496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os.dt
> >>>> -MT /tmp/3496222_18.tmpdir/aci-gcc-fsf
> >>>> /builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
> >>>>
> >>>> In file included from iso-2022-cn.c:407:0:
> >>>> ../iconv/skeleton.c: In function 'gconv':
> >>>> ../iconv/skeleton.c:800:1: internal compiler error: in
> >>>> check_probability, at basic-block.h:959
> >>>> 0xe4e2fb find_many_sub_basic_blocks(simple_bitmap_def*)
> >>>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/basic-block.h:959
> >>>> 0x6623f0 execute
> >>>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/cfgexpand.c:5916
> >>>> Please submit a full bug report,
> >>>> with preprocessed source if appropriate.
> >>>> Please include the complete backtrace with any bug report.
> >>>> See <http://gcc.gnu.org/bugs.html> for instructions.
> >>>>
> >>>> Can you have a look?
> >>>
> >>> It would help if you could attach a preprocessed file.
> >>>
> >> I did it in a followup mail, but the list server rejected it because
> >> it was too large.
> >> I suppose Teresa did receive it though.
> >>
> >> Not sure whether I can attach it in .xz format? Is this allowed?
> >>
> >> Thanks
> >> Christophe.
> >>
> >>> Thanks,
> >>> Sebastian
> >
> >
> >
> > --
> > Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413
> 
> 
> 
> -- 
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Wed, Oct 1, 2014 at 3:46 PM, Steve Ellcey <sellcey@mips.com> wrote:
> On Wed, 2014-10-01 at 13:04 -0700, Teresa Johnson wrote:
>
>> 2014-10-01  Teresa Johnson  <tejohnson@google.com>
>>
>>         * tree-ssa-threadupdate.c (freqs_to_counts_path): Scale frequencies
>>         up when synthesizing counts to avoid rounding errors.
>
> I tried this patch on my MIPS toolchain build but GCC is still failing
> while building glibc.
>
> iconv_open.c: In function 'iconv_open':
> iconv_open.c:32:1: error: verify_flow_info: Wrong probability of edge
> 14->18 -920374544
>  iconv_open (const char *tocode, const char *fromcode)
>  ^
> iconv_open.c:32:1: error: verify_flow_info: Wrong probability of edge
> 14->19 -903724544
> iconv_open.c:32:1: internal compiler error: verify_flow_info failed
> 0x626a70 verify_flow_info()
>         /scratch/sellcey/repos/nightly/src/gcc/gcc/cfghooks.c:260
> 0x9f36e4 cleanup_tree_cfg_noloop
>         /scratch/sellcey/repos/nightly/src/gcc/gcc/tree-cfgcleanup.c:765
> 0x9f36e4 cleanup_tree_cfg()
>         /scratch/sellcey/repos/nightly/src/gcc/gcc/tree-cfgcleanup.c:814
> 0x8eeff4 execute_function_todo
>         /scratch/sellcey/repos/nightly/src/gcc/gcc/passes.c:1704
> 0x8efb23 execute_todo
>         /scratch/sellcey/repos/nightly/src/gcc/gcc/passes.c:1808
> Please submit a full bug report,
> with preprocessed source if appropriate.
> Please include the complete backtrace with any bug report.
> See <http://gcc.gnu.org/bugs.html> for instructions.
>

Will take a look. In case I can't reproduce it with the aarch64
cross-compiler or x86_64, can you give me the preprocessed source? And
also the instructions for how to configure for MIPS.

Teresa

-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Wed, Oct 1, 2014 at 4:09 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> The block frequencies are very small in this case leading to rounding
>> errors when computing the edge frequency. The rounding error was then
>> propagated into the recomputed probabilities, leading to insanities in
>> the outgoing edge probabilities on the jump threading path. Eventually
>> during rtl expansion these insanities somehow caused an ICE.
>
> Concerning the never ending rounoff issues, I thing we ought to progress
> on turning counts, freqs and probabilities into a type that eliminates
> most of this fun.
>
> I see basically two options - first would be to take wide_int and build
> a fixed point type template around it (so one can chose precisions),
> other would be to have software emulated floating point type.
>
> Actually I think the second will be less troublesome - FP seems to fit
> the bill very well.  We already have sreal.h that does the job for
> propagation of frequencies.  What about turning it ito C++ type with
> operations on it and reroganizing code to use it?
> (we may consider making the base 64bit, as opposed to HOST_WIDE_INT
> right now)
>
> Or are there other options I missed? It would be very cool if someone
> could volunteer and implement the basic datatype and possibly start with
> convertion.
>
> I think we could do type by type, first redefining counts from gcov_t
> and relying on conversion to gcov_t to work to not having to update all
> uses at once.  THen we can just update the code pass by pass.
>
> One nice thing we could add into the type is to make difference in betwen
> known zeros (i.e. read from profile) and zeros that were results of updates
> that may or may not be precise.  THis should hopefully solve the bad
> iteraction of Martin's code ordering and Theresa's BB-reorder work.

Yes, this would avoid a number of headaches with roundoff errors I've
seen and worked around in various contexts. Using C++ to implement the
sreal type and provide the operators seems like a good option. I had
hoped to work on this after we talked about it in the past but haven't
had the bandwidth unfortunately.

Teresa

>
> Honza
>>
>> (Before this patch the probabilities weren't even being updated,
>> leading to insanities in other cases where they needed to be updated.)
>>
>> Specifically, in this case we had a block with frequency = 1. It had
>> two outgoing edges each with probability 50%. Because the
>> EDGE_FREQUENCY computation uses a rounding divide, the outgoing edge
>> frequencies were both computed as 1. Later use of these block and edge
>> frequencies to recompute the probability lead to both outgoing edges
>> getting 100%.
>>
>> To address this, in the routine freqs_to_counts_path can simply scale
>> up the frequencies when recording them in the count field. I added a
>> scale by REG_BR_PROB_BASE. The largest count possible would therefore
>> be REG_BR_PROB_BASE * BB_FREQ_MAX which is 10000 * 10000 = 100mil
>> which safely fits in gcov_type.
>>
>> Here is the patch I am testing. Confirmed it fixes the reported issue.
>> Currently bootstrapping and testing on x86_64-unknown-linux-gnu. Ok
>> for trunk if it passes?
>>
>> (The whitespace is getting messed up when I copy the patch in here -
>> the indentations do line up in the patch.)
>>
>> Thanks,
>> Teresa
>>
>> 2014-10-01  Teresa Johnson  <tejohnson@google.com>
>>
>>         * tree-ssa-threadupdate.c (freqs_to_counts_path): Scale frequencies
>>         up when synthesizing counts to avoid rounding errors.
>>
>> Index: tree-ssa-threadupdate.c
>> ===================================================================
>> --- tree-ssa-threadupdate.c     (revision 215739)
>> +++ tree-ssa-threadupdate.c     (working copy)
>> @@ -979,7 +979,11 @@ freqs_to_counts_path (struct redirection_data *rd)
>>    FOR_EACH_EDGE (ein, ei, e->dest->preds)
>>      {
>>        gcc_assert (!ein->count);
>> -      ein->count = EDGE_FREQUENCY (ein);
>> +      /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
>> +         errors applying the probability when the frequencies are very
>> +         small.  */
>> +      ein->count = apply_probability (ein->src->frequency * REG_BR_PROB_BASE,
>> +                                      ein->probability);
>>      }
>>
>>    for (unsigned int i = 1; i < path->length (); i++)
>> @@ -987,11 +991,13 @@ freqs_to_counts_path (struct redirection_data *rd)
>>        edge epath = (*path)[i]->e;
>>        gcc_assert (!epath->count);
>>        edge esucc;
>> +      /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
>> +         errors applying the edge probability when the frequencies are very
>> +         small.  */
>> +      epath->src->count = epath->src->frequency * REG_BR_PROB_BASE;
>>        FOR_EACH_EDGE (esucc, ei, epath->src->succs)
>> -        {
>> -          esucc->count = EDGE_FREQUENCY (esucc);
>> -        }
>> -      epath->src->count = epath->src->frequency;
>> +        esucc->count = apply_probability (esucc->src->count,
>> +                                          esucc->probability);
>>      }
>>  }
>>
>>
>> On Wed, Oct 1, 2014 at 8:29 AM, Teresa Johnson <tejohnson@google.com> wrote:
>> > I got the preprocessed source. With the aarch64 cross-compiler I built
>> > I am able to reproduce the ICE. Looking at it now.
>> >
>> > Thanks,
>> > Teresa
>> >
>> > On Wed, Oct 1, 2014 at 8:25 AM, Christophe Lyon
>> > <christophe.lyon@linaro.org> wrote:
>> >> On 1 October 2014 17:22, Sebastian Pop <sebpop@gmail.com> wrote:
>> >>> Christophe Lyon wrote:
>> >>>> Since this commit, I can see all my builds for arm*linux* and
>> >>>> aarch64*linux* fail while building glibc:
>> >>>>
>> >>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/aarch64-none-linux-gnu-gcc
>> >>>> iso-2022-cn.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Win
>> >>>> line -Wundef -Wwrite-strings -fmerge-all-constants -frounding-math -g
>> >>>> -Wstrict-prototypes   -fPIC        -I../include
>> >>>> -I/tmp/3496222_18.tmpdir/aci-gcc-f
>> >>>> sf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata
>> >>>> -I/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux
>> >>>> -gnu/glibc-1  -I../sysdeps/unix/sysv/linux/aarch64/nptl
>> >>>> -I../sysdeps/unix/sysv/linux/aarch64
>> >>>> -I../sysdeps/unix/sysv/linux/generic  -I../sysdeps/unix/s
>> >>>> ysv/linux/wordsize-64  -I../nptl/sysdeps/unix/sysv/linux
>> >>>> -I../nptl/sysdeps/pthread  -I../sysdeps/pthread
>> >>>> -I../sysdeps/unix/sysv/linux  -I../sysdeps/gn
>> >>>> u  -I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv
>> >>>> -I../sysdeps/unix/sysv  -I../nptl/sysdeps/unix  -I../sysdeps/unix
>> >>>> -I../sysdeps/posix  -I../sysd
>> >>>> eps/aarch64/fpu  -I../sysdeps/aarch64/nptl  -I../sysdeps/aarch64
>> >>>> -I../sysdeps/wordsize-64  -I../sysdeps/ieee754/ldbl-128
>> >>>> -I../sysdeps/ieee754/dbl-64/w
>> >>>> ordsize-64  -I../sysdeps/ieee754/dbl-64  -I../sysdeps/ieee754/flt-32
>> >>>> -I../sysdeps/aarch64/soft-fp  -I../sysdeps/ieee754
>> >>>> -I../sysdeps/generic  -I../npt
>> >>>> l  -I.. -I../libio -I. -nostdinc -isystem
>> >>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include
>> >>>> -i
>> >>>> system /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include-fixed
>> >>>> -isystem /tmp/3496222_18.tmpdir
>> >>>> /aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-aarch64-none-linux-gnu/usr/include
>> >>>>  -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
>> >>>> -DNOT_IN_libc -o
>> >>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>> >>>> -MD -MP -MF /tmp/3
>> >>>> 496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os.dt
>> >>>> -MT /tmp/3496222_18.tmpdir/aci-gcc-fsf
>> >>>> /builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>> >>>>
>> >>>> In file included from iso-2022-cn.c:407:0:
>> >>>> ../iconv/skeleton.c: In function 'gconv':
>> >>>> ../iconv/skeleton.c:800:1: internal compiler error: in
>> >>>> check_probability, at basic-block.h:959
>> >>>> 0xe4e2fb find_many_sub_basic_blocks(simple_bitmap_def*)
>> >>>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/basic-block.h:959
>> >>>> 0x6623f0 execute
>> >>>>         /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/cfgexpand.c:5916
>> >>>> Please submit a full bug report,
>> >>>> with preprocessed source if appropriate.
>> >>>> Please include the complete backtrace with any bug report.
>> >>>> See <http://gcc.gnu.org/bugs.html> for instructions.
>> >>>>
>> >>>> Can you have a look?
>> >>>
>> >>> It would help if you could attach a preprocessed file.
>> >>>
>> >> I did it in a followup mail, but the list server rejected it because
>> >> it was too large.
>> >> I suppose Teresa did receive it though.
>> >>
>> >> Not sure whether I can attach it in .xz format? Is this allowed?
>> >>
>> >> Thanks
>> >> Christophe.
>> >>
>> >>> Thanks,
>> >>> Sebastian
>> >
>> >
>> >
>> > --
>> > Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413
>>
>>
>>
>> --
>> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Wed, Oct 1, 2014 at 10:02 PM, Teresa Johnson <tejohnson@google.com> wrote:
> On Wed, Oct 1, 2014 at 3:46 PM, Steve Ellcey <sellcey@mips.com> wrote:
>> On Wed, 2014-10-01 at 13:04 -0700, Teresa Johnson wrote:
>>
>>> 2014-10-01  Teresa Johnson  <tejohnson@google.com>
>>>
>>>         * tree-ssa-threadupdate.c (freqs_to_counts_path): Scale frequencies
>>>         up when synthesizing counts to avoid rounding errors.
>>
>> I tried this patch on my MIPS toolchain build but GCC is still failing
>> while building glibc.
>>
>> iconv_open.c: In function 'iconv_open':
>> iconv_open.c:32:1: error: verify_flow_info: Wrong probability of edge
>> 14->18 -920374544
>>  iconv_open (const char *tocode, const char *fromcode)
>>  ^
>> iconv_open.c:32:1: error: verify_flow_info: Wrong probability of edge
>> 14->19 -903724544
>> iconv_open.c:32:1: internal compiler error: verify_flow_info failed
>> 0x626a70 verify_flow_info()
>>         /scratch/sellcey/repos/nightly/src/gcc/gcc/cfghooks.c:260
>> 0x9f36e4 cleanup_tree_cfg_noloop
>>         /scratch/sellcey/repos/nightly/src/gcc/gcc/tree-cfgcleanup.c:765
>> 0x9f36e4 cleanup_tree_cfg()
>>         /scratch/sellcey/repos/nightly/src/gcc/gcc/tree-cfgcleanup.c:814
>> 0x8eeff4 execute_function_todo
>>         /scratch/sellcey/repos/nightly/src/gcc/gcc/passes.c:1704
>> 0x8efb23 execute_todo
>>         /scratch/sellcey/repos/nightly/src/gcc/gcc/passes.c:1808
>> Please submit a full bug report,
>> with preprocessed source if appropriate.
>> Please include the complete backtrace with any bug report.
>> See <http://gcc.gnu.org/bugs.html> for instructions.
>>
>
> Will take a look. In case I can't reproduce it with the aarch64
> cross-compiler or x86_64, can you give me the preprocessed source? And
> also the instructions for how to configure for MIPS.

Hi Steve,

Please do send me the preprocessed source and if possible also
instructions for configuring a MIPS cross-compiler. I haven't been
able to reproduce this with either x86_64 or the aarch64
cross-compiler I built yesterday. But I can't reproduce Christophe's
failure either with my aarch64-configured glibc, so my version or
headers must be different.

Thanks!
Teresa

>
> Teresa
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Steve Ellcey]

On Wed, 2014-10-01 at 22:02 -0700, Teresa Johnson wrote:

> Will take a look. In case I can't reproduce it with the aarch64
> cross-compiler or x86_64, can you give me the preprocessed source? And
> also the instructions for how to configure for MIPS.
> 
> Teresa

Never mind, I messed up the patch when applying it.  It looks good on
MIPS now.  I haven't done a complete build and test but the ICE went
away when I re-applied the patch.

Steve Ellcey
sellcey@mips.com

Re: [PATCH] Redesign jump threading profile updates

[Teresa Johnson]

On Thu, Oct 2, 2014 at 8:45 AM, Steve Ellcey <sellcey@mips.com> wrote:
> On Wed, 2014-10-01 at 22:02 -0700, Teresa Johnson wrote:
>
>> Will take a look. In case I can't reproduce it with the aarch64
>> cross-compiler or x86_64, can you give me the preprocessed source? And
>> also the instructions for how to configure for MIPS.
>>
>> Teresa
>
> Never mind, I messed up the patch when applying it.  It looks good on
> MIPS now.  I haven't done a complete build and test but the ICE went
> away when I re-applied the patch.

Ok, phew. =) Thanks for the update.

Jeff or Honza, did the patch look ok for trunk? Regression tests pass.

Thanks,
Teresa

>
> Steve Ellcey
> sellcey@mips.com
>



-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Re: [PATCH] Redesign jump threading profile updates

[Jeff Law]

On 10/01/14 14:04, Teresa Johnson wrote:
> The block frequencies are very small in this case leading to rounding
> errors when computing the edge frequency. The rounding error was then
> propagated into the recomputed probabilities, leading to insanities in
> the outgoing edge probabilities on the jump threading path. Eventually
> during rtl expansion these insanities somehow caused an ICE.
>
> (Before this patch the probabilities weren't even being updated,
> leading to insanities in other cases where they needed to be updated.)
>
> Specifically, in this case we had a block with frequency = 1. It had
> two outgoing edges each with probability 50%. Because the
> EDGE_FREQUENCY computation uses a rounding divide, the outgoing edge
> frequencies were both computed as 1. Later use of these block and edge
> frequencies to recompute the probability lead to both outgoing edges
> getting 100%.
>
> To address this, in the routine freqs_to_counts_path can simply scale
> up the frequencies when recording them in the count field. I added a
> scale by REG_BR_PROB_BASE. The largest count possible would therefore
> be REG_BR_PROB_BASE * BB_FREQ_MAX which is 10000 * 10000 = 100mil
> which safely fits in gcov_type.
>
> Here is the patch I am testing. Confirmed it fixes the reported issue.
> Currently bootstrapping and testing on x86_64-unknown-linux-gnu. Ok
> for trunk if it passes?
>
> (The whitespace is getting messed up when I copy the patch in here -
> the indentations do line up in the patch.)
>
> Thanks,
> Teresa
>
> 2014-10-01  Teresa Johnson  <tejohnson@google.com>
>
>          * tree-ssa-threadupdate.c (freqs_to_counts_path): Scale frequencies
>          up when synthesizing counts to avoid rounding errors.
OK.
jeff

Re: [PATCH] Redesign jump threading profile updates

[Renlin Li]

On 01/10/14 21:04, Teresa Johnson wrote:
> The block frequencies are very small in this case leading to rounding
> errors when computing the edge frequency. The rounding error was then
> propagated into the recomputed probabilities, leading to insanities in
> the outgoing edge probabilities on the jump threading path. Eventually
> during rtl expansion these insanities somehow caused an ICE.
That's exactly what I have observed while investigation this bug: 
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61529

In this ICE while building glibc, we have frequency = 16, but we have 
even probabilities for 45 successors.
The count for each outgoing edge is rounding to 0. Later in the 
update_joiner_offpath_counts() function, the count for each edge is 
re-calculated to  be equal to e->src->count, thus the probability for 
each outgoing edge is 100% when probability is recomputed.

This patch fixed the bug. Thank you!

>
> (Before this patch the probabilities weren't even being updated,
> leading to insanities in other cases where they needed to be updated.)
>
> Specifically, in this case we had a block with frequency = 1. It had
> two outgoing edges each with probability 50%. Because the
> EDGE_FREQUENCY computation uses a rounding divide, the outgoing edge
> frequencies were both computed as 1. Later use of these block and edge
> frequencies to recompute the probability lead to both outgoing edges
> getting 100%.
>
> To address this, in the routine freqs_to_counts_path can simply scale
> up the frequencies when recording them in the count field. I added a
> scale by REG_BR_PROB_BASE. The largest count possible would therefore
> be REG_BR_PROB_BASE * BB_FREQ_MAX which is 10000 * 10000 = 100mil
> which safely fits in gcov_type.
>
> Here is the patch I am testing. Confirmed it fixes the reported issue.
> Currently bootstrapping and testing on x86_64-unknown-linux-gnu. Ok
> for trunk if it passes?
>
> (The whitespace is getting messed up when I copy the patch in here -
> the indentations do line up in the patch.)
>
> Thanks,
> Teresa
>
> 2014-10-01  Teresa Johnson  <tejohnson@google.com>
>
>          * tree-ssa-threadupdate.c (freqs_to_counts_path): Scale frequencies
>          up when synthesizing counts to avoid rounding errors.
>
> Index: tree-ssa-threadupdate.c
> ===================================================================
> --- tree-ssa-threadupdate.c     (revision 215739)
> +++ tree-ssa-threadupdate.c     (working copy)
> @@ -979,7 +979,11 @@ freqs_to_counts_path (struct redirection_data *rd)
>     FOR_EACH_EDGE (ein, ei, e->dest->preds)
>       {
>         gcc_assert (!ein->count);
> -      ein->count = EDGE_FREQUENCY (ein);
> +      /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
> +         errors applying the probability when the frequencies are very
> +         small.  */
> +      ein->count = apply_probability (ein->src->frequency * REG_BR_PROB_BASE,
> +                                      ein->probability);
>       }
>
>     for (unsigned int i = 1; i < path->length (); i++)
> @@ -987,11 +991,13 @@ freqs_to_counts_path (struct redirection_data *rd)
>         edge epath = (*path)[i]->e;
>         gcc_assert (!epath->count);
>         edge esucc;
> +      /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
> +         errors applying the edge probability when the frequencies are very
> +         small.  */
> +      epath->src->count = epath->src->frequency * REG_BR_PROB_BASE;
>         FOR_EACH_EDGE (esucc, ei, epath->src->succs)
> -        {
> -          esucc->count = EDGE_FREQUENCY (esucc);
> -        }
> -      epath->src->count = epath->src->frequency;
> +        esucc->count = apply_probability (esucc->src->count,
> +                                          esucc->probability);
>       }
>   }
>
>
> On Wed, Oct 1, 2014 at 8:29 AM, Teresa Johnson <tejohnson@google.com> wrote:
>> I got the preprocessed source. With the aarch64 cross-compiler I built
>> I am able to reproduce the ICE. Looking at it now.
>>
>> Thanks,
>> Teresa
>>
>> On Wed, Oct 1, 2014 at 8:25 AM, Christophe Lyon
>> <christophe.lyon@linaro.org> wrote:
>>> On 1 October 2014 17:22, Sebastian Pop <sebpop@gmail.com> wrote:
>>>> Christophe Lyon wrote:
>>>>> Since this commit, I can see all my builds for arm*linux* and
>>>>> aarch64*linux* fail while building glibc:
>>>>>
>>>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/aarch64-none-linux-gnu-gcc
>>>>> iso-2022-cn.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Win
>>>>> line -Wundef -Wwrite-strings -fmerge-all-constants -frounding-math -g
>>>>> -Wstrict-prototypes   -fPIC        -I../include
>>>>> -I/tmp/3496222_18.tmpdir/aci-gcc-f
>>>>> sf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata
>>>>> -I/tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux
>>>>> -gnu/glibc-1  -I../sysdeps/unix/sysv/linux/aarch64/nptl
>>>>> -I../sysdeps/unix/sysv/linux/aarch64
>>>>> -I../sysdeps/unix/sysv/linux/generic  -I../sysdeps/unix/s
>>>>> ysv/linux/wordsize-64  -I../nptl/sysdeps/unix/sysv/linux
>>>>> -I../nptl/sysdeps/pthread  -I../sysdeps/pthread
>>>>> -I../sysdeps/unix/sysv/linux  -I../sysdeps/gn
>>>>> u  -I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv
>>>>> -I../sysdeps/unix/sysv  -I../nptl/sysdeps/unix  -I../sysdeps/unix
>>>>> -I../sysdeps/posix  -I../sysd
>>>>> eps/aarch64/fpu  -I../sysdeps/aarch64/nptl  -I../sysdeps/aarch64
>>>>> -I../sysdeps/wordsize-64  -I../sysdeps/ieee754/ldbl-128
>>>>> -I../sysdeps/ieee754/dbl-64/w
>>>>> ordsize-64  -I../sysdeps/ieee754/dbl-64  -I../sysdeps/ieee754/flt-32
>>>>> -I../sysdeps/aarch64/soft-fp  -I../sysdeps/ieee754
>>>>> -I../sysdeps/generic  -I../npt
>>>>> l  -I.. -I../libio -I. -nostdinc -isystem
>>>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include
>>>>> -i
>>>>> system /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/aarch64-none-linux-gnu/5.0.0/include-fixed
>>>>> -isystem /tmp/3496222_18.tmpdir
>>>>> /aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-aarch64-none-linux-gnu/usr/include
>>>>>   -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
>>>>> -DNOT_IN_libc -o
>>>>> /tmp/3496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>>>>> -MD -MP -MF /tmp/3
>>>>> 496222_18.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os.dt
>>>>> -MT /tmp/3496222_18.tmpdir/aci-gcc-fsf
>>>>> /builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/glibc-1/iconvdata/iso-2022-cn.os
>>>>>
>>>>> In file included from iso-2022-cn.c:407:0:
>>>>> ../iconv/skeleton.c: In function 'gconv':
>>>>> ../iconv/skeleton.c:800:1: internal compiler error: in
>>>>> check_probability, at basic-block.h:959
>>>>> 0xe4e2fb find_many_sub_basic_blocks(simple_bitmap_def*)
>>>>>          /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/basic-block.h:959
>>>>> 0x6623f0 execute
>>>>>          /tmp/3496222_18.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/cfgexpand.c:5916
>>>>> Please submit a full bug report,
>>>>> with preprocessed source if appropriate.
>>>>> Please include the complete backtrace with any bug report.
>>>>> See <http://gcc.gnu.org/bugs.html> for instructions.
>>>>>
>>>>> Can you have a look?
>>>> It would help if you could attach a preprocessed file.
>>>>
>>> I did it in a followup mail, but the list server rejected it because
>>> it was too large.
>>> I suppose Teresa did receive it though.
>>>
>>> Not sure whether I can attach it in .xz format? Is this allowed?
>>>
>>> Thanks
>>> Christophe.
>>>
>>>> Thanks,
>>>> Sebastian
>>
>>
>> --
>> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413
>