[RFC] Isolate & simplify paths with undefined behaviour

[Richard Biener]

On Mon, Oct 21, 2013 at 7:27 PM, Jeff Law <law@redhat.com> wrote:
> On 10/21/13 06:19, Richard Biener wrote:
>
>>
>> I wonder why this isn't part of the regular jump-threading code - after
>> all the opportunity is to thead to __builtin_unreachable () ;)  Otherwise
>> the question is always where you'd place this pass and whether it
>> enables jump threading or CSE opportunities (that at least it does).
>
> In theory one could do this as part of jump threading.  Doing it in jump
> threading would have the advantage that we could use a NULL generated in a
> different block than the dereference.  Of course, we'd have a full path to
> duplicate at that point.
>
> The downside is complexity.  This pass is amazingly simple and effective.
> The jump threading code is considerably more complex and bolting this on the
> side would just make it worse.
>
> From a pipeline location, if kept as a separate pass, it probably needs to
> be between DOM1 & phi-only cprop.  DOM1 does a reasonable job at propagating
> the NULL values into the PHI nodes to expose the optimization.  And the pass
> tends to expose precisely the kinds of PHI nodes that phi-only cprop can
> optimize.  VRP2/PRE/DOM2 do a good job at finding the newly exposed CSEs and
> jump threading opportunities.
>
> I haven't looked to see if there's anything left to optimize after DOM2, but
> I can certainly speculate that there would be cases exposed by the various
> passes that currently exist between DOM1 & DOM2.  That's certainly worth
> exploring.
>
> As you know, phase ordering will always be a concern.  We already have
> acknowledged that we're punting some of those issues once we stopped
> iterating DOM.

True ...

Btw, -ftree-isolate-paths sounds a bit generic for isolating paths leading
to undefined behavior, maybe -fisolate-errorneous-paths?  (please drop
'tree-' from new options, 'tree' isn't meaningful to GCC users)

The file should be named gimple-ssa-isolate-paths.c, too.

+   for (si = gsi_start_nondebug_bb (bb), si2 = gsi_start_nondebug_bb
(duplicate);
+        !gsi_end_p (si) && !gsi_end_p (si2);
+        gsi_next_nondebug (&si), gsi_next_nondebug (&si2))
+     {
+       while (gimple_code (gsi_stmt (si)) == GIMPLE_LABEL)
+       gsi_next_nondebug (&si);

gsi_after_labels (bb);
if (is_gimple_debug (gsi_stmt (gsi)))
  gsi_next_nondebug (&gsi);

warrants a new gsi_nondebug_after_labels ()

+       /* SI2 is the iterator in the duplicate block and it now points
+        to our victim statement.  */
+       gimple_seq seq = NULL;
+       tree t = build_call_expr_loc (0,
+                                   builtin_decl_explicit (BUILT_IN_TRAP), 0);
+       gimplify_and_add (t, &seq);
+       gsi_insert_before (&si2, seq, GSI_SAME_STMT);

please build a gimple call stmt directly instead of going through the
gimplifier.

+             if (operand_equal_p (op, integer_zero_node, 0))

integer_zerop ()

+                 /* We've got a NULL PHI argument.  Now see if the
+                    PHI's result is dereferenced within BB.  */
+                 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
+                   {
+                     unsigned int j;
+                     bool removed_edge = false;
+
+                     /* We only care about uses in BB which are assignements
+                        with memory operands.
+
+                        We could see if any uses are as function arguments
+                        when the callee has marked the argument as being
+                        non-null.  */
+                     if (gimple_bb (use_stmt) != bb
+                         || !gimple_has_mem_ops (use_stmt)
+                         || gimple_code (use_stmt) != GIMPLE_ASSIGN)

!is_gimple_assign (), you can drop the has_mem_ops check, but ...

+                       continue;
+
+                     /* Look at each operand for a memory reference using
+                        LHS.  */

... you want to use walk_stmt_load_store_ops () which handles all kinds
of stmts fine.

+                     for (j = 0; j < gimple_num_ops (use_stmt); j++)
+                       {
+                         tree op = gimple_op (use_stmt, j);
+
+                         if (op == NULL)
+                           continue;
+
+                         while (handled_component_p (op))
+                           op = TREE_OPERAND (op, 0);
+
+                         if ((TREE_CODE (op) == MEM_REF
+                              || TREE_CODE (op) == INDIRECT_REF)

no more INDIRECT_REFs are in the IL.

Richard.

+                             && TREE_OPERAND (op, 0) == lhs)
+                           {
+                             edge e = gimple_phi_arg_edge (phi, i);
+                             duplicate = isolate_path (bb, duplicate,
+                                                       e, use_stmt);
+
+                             /* When we remove an incoming edge, we need to
+                                reprocess the Ith element.  */
+                             next_i = i;
+
+                             removed_edge = true;
+                             cfg_altered = true;
+                             break;
+                           }
+                       }

> Jeff