Re: [PATCH][RFC] Fix PR63155

[Richard Biener <rguenther at suse dot de>]

On March 18, 2015 4:59:30 PM GMT+01:00, Alan Lawrence <alan.lawrence@arm.com> wrote:
>Following this patch (r221318), we're seeing what appears to be a
>miscompile of 
>glibc on AArch64. This causes quite a bunch of tests to fail, segfaults
>etc., if 
>LD_LIBRARY_PATH leads to a libc.so.6 built with that patch vs without
>(same 
>glibc sources). We are still working on a reduced testcase, but this is
>proving 
>difficult...

The patch was supposed to end up in the very same code generation.  Thus it's enough to identify the problematic source file and send me preprocessed source and cc1 invocation so I can investigate with a cross.

Thanks,
Richard.

>--Alan
>
>Richard Biener wrote:
>> On Mon, 9 Mar 2015, Richard Biener wrote:
>> 
>>> On Fri, 6 Mar 2015, Jeff Law wrote:
>>>
>>>> On 03/06/15 06:16, Richard Biener wrote:
>>>>> This fixes PR63155 and reduces the memory usage at -O0 from
>reported
>>>>> 10GB (couldn't verify/update on my small box) to 350MB (still
>worse
>>>>> compared to 4.8 which needs only 50MB).
>>>>>
>>>>> It fixes this by no longer computing live info or building a
>conflict
>>>>> graph for coalescing of SSA names flowing over abnormal edges
>>>>> (which needs to succeed).
>>>>>
>>>>> Of course this also removes verification that this coalescing is
>valid
>>>>> (but computing this has quadratic cost).  With this it turns
>>>>> ICEs into miscompiles.
>>>>>
>>>>> We could restrict verifying that we can perform abnormal
>coalescing
>>>>> to ENABLE_CHECKING (and I've wanted a verifier pass that can
>verify
>>>>> this multiple times to be able to catch what breaks it and not
>having
>>>>> to work back from out-of-SSA ICEing...).
>>>>>
>>>>> So any opinion on this patch welcome.
>>>>>
>>>>> Bootstrap and regtest running on x86_64-unknown-linux-gnu.
>>>>>
>>>>> Ok for trunk? ;)
>>>>>
>>>>> Thanks,
>>>>> Richard.
>>>>>
>>>>> 2015-03-06  Richard Biener  <rguenther@suse.de>
>>>>>
>>>>>   PR middle-end/63155
>>>>>   * tree-ssa-coalesce.c (attempt_coalesce): Handle graph being
>NULL.
>>>>>   (coalesce_partitions): Split out abnormal coalescing to ...
>>>>>   (perform_abnormal_coalescing): ... this function.
>>>>>   (coalesce_ssa_name): Perform abnormal coalescing without
>computing
>>>>>   live/conflict.
>>>> I'd personally like to keep the checking when ENABLE_CHECKING.
>>>>
>>>> I haven't followed this discussion real closely, but I wonder if
>some kind of
>>>> blocking approach would work without blowing up the memory
>consumption.
>>>> There's no inherent reason why we have to coalesce everything at
>the same
>>>> time.  We can use a blocking factor and do coalescing on some N
>number of
>>>> SSA_NAMEs at a time.
>>> Yes, that's possible at (quite?) some compile-time cost.  Note that
>we
>>> can't really guarantee that the resulting live/conflict problems
>shrink
>>> significantly enough without sorting the coalesces in a different
>way
>>> (not after important coalesces but after their basevars).
>>>
>>>> I suspect we can select an N that ultimately degenerates into the
>current "do
>>>> everything together" for the common case and only has to iterate
>over blocks
>>>> of SSA_NAMEs in extreme cases.
>>> I've attached a patch to the PR that adds such a number N after
>which we
>>> simply stop coalescing.  Of course that doesn't work for abnormals
>where
>>> we _must_ coalesce.  Thus this patch ...
>>>
>>> As said, it's simple to keep the checking with ENABLE_CHECKING (I
>wonder
>>> if we should make some of the checking we do a runtime choice rather
>>> than a compile-time one...).  I'll update the patch.
>> 
>> Ok, like the following which adds a verify_ssa_coalescing () function
>> (which could in theory be called from IL verification like
>verify_ssa)
>> and calls it when ENABLE_CHECKING is defined.
>> 
>> Bootstrap & regtest running on x86_64-unknown-linux-gnu.
>> 
>> It didn't look appropriate for this stage to implement virtual
>operand
>> verification.
>> 
>> Ok this way?
>> 
>> Thanks,
>> Richard.
>> 
>> 2015-03-06  Richard Biener  <rguenther@suse.de>
>> 
>>         PR middle-end/63155
>>         * tree-ssa-coalesce.h (verify_ssa_coalescing): Declare.
>>         * tree-ssa-coalesce.c (attempt_coalesce): Handle graph being
>NULL.
>>         (coalesce_partitions): Call verify_ssa_coalescing if
>ENABLE_CHECKING.
>>         Split out abnormal coalescing to ...
>>         (perform_abnormal_coalescing): ... this function.
>>         (coalesce_ssa_name): Perform abnormal coalescing without
>computing
>>         live/conflict.
>>         (verify_ssa_coalescing_worker): New function.
>>         (verify_ssa_coalescing): Likewise.
>> 
>> Index: gcc/tree-ssa-coalesce.c
>> ===================================================================
>> *** gcc/tree-ssa-coalesce.c     (revision 221278)
>> --- gcc/tree-ssa-coalesce.c     (working copy)
>> *************** create_outofssa_var_map (coalesce_list_p
>> *** 1121,1128 ****
>> 
>> 
>>   /* Attempt to coalesce ssa versions X and Y together using the
>partition
>> !    mapping in MAP and checking conflicts in GRAPH.  Output any
>debug info to
>> !    DEBUG, if it is nun-NULL.  */
>> 
>>   static inline bool
>>   attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
>> --- 1121,1128 ----
>> 
>> 
>>   /* Attempt to coalesce ssa versions X and Y together using the
>partition
>> !    mapping in MAP and checking conflicts in GRAPH if not NULL.
>> !    Output any debug info to DEBUG, if it is nun-NULL.  */
>> 
>>   static inline bool
>>   attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
>> *************** attempt_coalesce (var_map map, ssa_confl
>> *** 1154,1160 ****
>>       fprintf (debug, " [map: %d, %d] ", p1, p2);
>> 
>> 
>> !   if (!ssa_conflicts_test_p (graph, p1, p2))
>>       {
>>         var1 = partition_to_var (map, p1);
>>         var2 = partition_to_var (map, p2);
>> --- 1154,1161 ----
>>       fprintf (debug, " [map: %d, %d] ", p1, p2);
>> 
>> 
>> !   if (!graph
>> !       || !ssa_conflicts_test_p (graph, p1, p2))
>>       {
>>         var1 = partition_to_var (map, p1);
>>         var2 = partition_to_var (map, p2);
>> *************** attempt_coalesce (var_map map, ssa_confl
>> *** 1168,1177 ****
>> 
>>         /* z is the new combined partition.  Remove the other
>partition from
>>          the list, and merge the conflicts.  */
>> !       if (z == p1)
>> !       ssa_conflicts_merge (graph, p1, p2);
>> !       else
>> !       ssa_conflicts_merge (graph, p2, p1);
>> 
>>         if (debug)
>>         fprintf (debug, ": Success -> %d\n", z);
>> --- 1169,1181 ----
>> 
>>         /* z is the new combined partition.  Remove the other
>partition from
>>          the list, and merge the conflicts.  */
>> !       if (graph)
>> !       {
>> !         if (z == p1)
>> !           ssa_conflicts_merge (graph, p1, p2);
>> !         else
>> !           ssa_conflicts_merge (graph, p2, p1);
>> !       }
>> 
>>         if (debug)
>>         fprintf (debug, ": Success -> %d\n", z);
>> *************** attempt_coalesce (var_map map, ssa_confl
>> *** 1185,1208 ****
>>   }
>> 
>> 
>> ! /* Attempt to Coalesce partitions in MAP which occur in the list CL
>using
>> !    GRAPH.  Debug output is sent to DEBUG if it is non-NULL.  */
>> 
>>   static void
>> ! coalesce_partitions (var_map map, ssa_conflicts_p graph,
>coalesce_list_p cl,
>> !                    FILE *debug)
>>   {
>> -   int x = 0, y = 0;
>> -   tree var1, var2;
>> -   int cost;
>>     basic_block bb;
>>     edge e;
>>     edge_iterator ei;
>> 
>> -   /* First, coalesce all the copies across abnormal edges.  These
>are not placed
>> -      in the coalesce list because they do not need to be sorted,
>and simply
>> -      consume extra memory/compilation time in large programs.  */
>> -
>>     FOR_EACH_BB_FN (bb, cfun)
>>       {
>>         FOR_EACH_EDGE (e, ei, bb->preds)
>> --- 1189,1204 ----
>>   }
>> 
>> 
>> ! /* Perform all abnormal coalescing on MAP.
>> !    Debug output is sent to DEBUG if it is non-NULL.  */
>> 
>>   static void
>> ! perform_abnormal_coalescing (var_map map, FILE *debug)
>>   {
>>     basic_block bb;
>>     edge e;
>>     edge_iterator ei;
>> 
>>     FOR_EACH_BB_FN (bb, cfun)
>>       {
>>         FOR_EACH_EDGE (e, ei, bb->preds)
>> *************** coalesce_partitions (var_map map, ssa_co
>> *** 1226,1236 ****
>>                 if (debug)
>>                   fprintf (debug, "Abnormal coalesce: ");
>> 
>> !               if (!attempt_coalesce (map, graph, v1, v2, debug))
>>                   fail_abnormal_edge_coalesce (v1, v2);
>>               }
>>           }
>>       }
>> 
>>     /* Now process the items in the coalesce list.  */
>> 
>> --- 1222,1244 ----
>>                 if (debug)
>>                   fprintf (debug, "Abnormal coalesce: ");
>> 
>> !               if (!attempt_coalesce (map, NULL, v1, v2, debug))
>>                   fail_abnormal_edge_coalesce (v1, v2);
>>               }
>>           }
>>       }
>> + }
>> +
>> + /* Attempt to Coalesce partitions in MAP which occur in the list CL
>using
>> +    GRAPH.  Debug output is sent to DEBUG if it is non-NULL.  */
>> +
>> + static void
>> + coalesce_partitions (var_map map, ssa_conflicts_p graph,
>coalesce_list_p cl,
>> +                    FILE *debug)
>> + {
>> +   int x = 0, y = 0;
>> +   tree var1, var2;
>> +   int cost;
>> 
>>     /* Now process the items in the coalesce list.  */
>> 
>> *************** coalesce_ssa_name (void)
>> *** 1285,1290 ****
>> --- 1293,1303 ----
>>     var_map map;
>>     unsigned int i;
>> 
>> + #ifdef ENABLE_CHECKING
>> +   /* Verify we can perform all must coalesces.  */
>> +   verify_ssa_coalescing ();
>> + #endif
>> +
>>     cl = create_coalesce_list ();
>>     map = create_outofssa_var_map (cl, used_in_copies);
>> 
>> *************** coalesce_ssa_name (void)
>> *** 1341,1346 ****
>> --- 1354,1368 ----
>>         return map;
>>       }
>> 
>> +   /* First, coalesce all the copies across abnormal edges.  These
>are not placed
>> +      in the coalesce list because they do not need to be sorted,
>and simply
>> +      consume extra memory/compilation time in large programs.
>> +      Performing abnormal coalescing also needs no live/conflict
>computation
>> +      because it must succeed (but we lose checking that it indeed
>does).
>> +      Still for PR63155 this reduces memory usage from 10GB to zero.
> */
>> +   perform_abnormal_coalescing (map,
>> +                              ((dump_flags & TDF_DETAILS) ?
>dump_file : NULL));
>> +
>>     if (dump_file && (dump_flags & TDF_DETAILS))
>>       dump_var_map (dump_file, map);
>> 
>> *************** coalesce_ssa_name (void)
>> *** 1371,1381 ****
>> 
>>     /* Now coalesce everything in the list.  */
>>     coalesce_partitions (map, graph, cl,
>> !                      ((dump_flags & TDF_DETAILS) ? dump_file
>> !                                                  : NULL));
>> 
>>     delete_coalesce_list (cl);
>>     ssa_conflicts_delete (graph);
>> 
>>     return map;
>>   }
>> --- 1393,1493 ----
>> 
>>     /* Now coalesce everything in the list.  */
>>     coalesce_partitions (map, graph, cl,
>> !                      ((dump_flags & TDF_DETAILS) ? dump_file :
>NULL));
>> 
>>     delete_coalesce_list (cl);
>>     ssa_conflicts_delete (graph);
>> 
>>     return map;
>>   }
>> +
>> +
>> + /* Helper for verify_ssa_coalescing.  Operates in two modes:
>> +    1) scan the function for coalesces we must perform and store the
>> +       SSA names participating in USED_IN_COPIES
>> +    2) scan the function for coalesces and verify they can be
>performed
>> +       under the constraints of GRAPH updating MAP in the process
>> +    FIXME:  This can be extended to verify that the virtual operands
>> +    form a factored use-def chain (coalescing the active virtual use
>> +    with the virtual def at virtual def point).  */
>> +
>> + static void
>> + verify_ssa_coalescing_worker (bitmap used_in_copies,
>> +                             var_map map, ssa_conflicts_p graph)
>> + {
>> +   basic_block bb;
>> +
>> +   FOR_EACH_BB_FN (bb, cfun)
>> +     {
>> +       edge e;
>> +       edge_iterator ei;
>> +
>> +       FOR_EACH_EDGE (e, ei, bb->preds)
>> +       if (e->flags & EDGE_ABNORMAL)
>> +         {
>> +           gphi_iterator gsi;
>> +           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
>> +                gsi_next (&gsi))
>> +             {
>> +               gphi *phi = gsi.phi ();
>> +               tree arg = PHI_ARG_DEF (phi, e->dest_idx);
>> +               if (SSA_NAME_IS_DEFAULT_DEF (arg)
>> +                   && (!SSA_NAME_VAR (arg)
>> +                       || TREE_CODE (SSA_NAME_VAR (arg)) !=
>PARM_DECL))
>> +                 continue;
>> +
>> +               tree res = PHI_RESULT (phi);
>> +
>> +               if (used_in_copies)
>> +                 {
>> +                   int v1 = SSA_NAME_VERSION (res);
>> +                   int v2 = SSA_NAME_VERSION (arg);
>> +                   bitmap_set_bit (used_in_copies, v1);
>> +                   bitmap_set_bit (used_in_copies, v2);
>> +                 }
>> +               else
>> +                 {
>> +                   int p1 = var_to_partition (map, res);
>> +                   int p2 = var_to_partition (map, arg);
>> +                   if (p1 != p2)
>> +                     {
>> +                       if (ssa_conflicts_test_p (graph, p1, p2))
>> +                         error ("Overlapping life-ranges for SSA
>names");
>> +                       int z = var_union (map,
>> +                                          partition_to_var (map,
>p1),
>> +                                          partition_to_var (map,
>p2));
>> +                       if (z == p1)
>> +                         ssa_conflicts_merge (graph, p1, p2);
>> +                       else
>> +                         ssa_conflicts_merge (graph, p2, p1);
>> +                     }
>> +                 }
>> +             }
>> +         }
>> +     }
>> + }
>> +
>> + /* Verify that we can coalesce SSA names we must coalesce.  */
>> +
>> + DEBUG_FUNCTION void
>> + verify_ssa_coalescing (void)
>> + {
>> +   timevar_push (TV_TREE_SSA_VERIFY);
>> +   bitmap used_in_copies = BITMAP_ALLOC (NULL);
>> +   verify_ssa_coalescing_worker (used_in_copies, NULL, NULL);
>> +   if (bitmap_empty_p (used_in_copies))
>> +     {
>> +       BITMAP_FREE (used_in_copies);
>> +       return;
>> +     }
>> +   var_map map = init_var_map (bitmap_last_set_bit (used_in_copies)
>+ 1);
>> +   partition_view_bitmap (map, used_in_copies, true);
>> +   BITMAP_FREE (used_in_copies);
>> +   tree_live_info_p liveinfo = calculate_live_ranges (map, false);
>> +   ssa_conflicts_p graph = build_ssa_conflict_graph (liveinfo);
>> +   delete_tree_live_info (liveinfo);
>> +   verify_ssa_coalescing_worker (NULL, map, graph);
>> +   ssa_conflicts_delete (graph);
>> +   delete_var_map (map);
>> +   timevar_pop (TV_TREE_SSA_VERIFY);
>> + }
>> Index: gcc/tree-ssa-coalesce.h
>> ===================================================================
>> *** gcc/tree-ssa-coalesce.h     (revision 221278)
>> --- gcc/tree-ssa-coalesce.h     (working copy)
>> *************** along with GCC; see the file COPYING3.
>> *** 21,25 ****
>> --- 21,26 ----
>>   #define GCC_TREE_SSA_COALESCE_H
>> 
>>   extern var_map coalesce_ssa_name (void);
>> + extern void verify_ssa_coalescing (void);
>> 
>>   #endif /* GCC_TREE_SSA_COALESCE_H */
>> 
>>