[Bug rtl-optimization/33828] Issues with the implementation of code hoisting in gcse.c

[steven at gcc dot gnu dot org]

------- Comment #9 from steven at gcc dot gnu dot org  2007-10-28 21:30 -------
The computation of VBEIN and VBEOUT in gcse.c's code hoisting implementation
appears to be performed in the wrong order, if you ask me.

The code in gcse.c is a copy-and-paste of Muchnick, which presents the dataflow
problem as:

VBEIN(i) = EVAL(i) | (VBEOUT(i) - KILL(i))
VBEOUT(i) = intersection of VBEIN(j) for each j in SUCC(i)

In gcse.c, EVAL is called ANTLOC and KILL is ~ANTLOC. This results in the
following code in compute_code_hoist_vbeinout():

      FOR_EACH_BB_REVERSE (bb)
        {
          changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index],
                                              antloc[bb->index],
                                              hoist_vbeout[bb->index],
                                              transp[bb->index]);
          if (bb->next_bb != EXIT_BLOCK_PTR)
            sbitmap_intersection_of_succs (hoist_vbeout[bb->index],
                                           hoist_vbein, bb->index);
        }

The code hoisting data flow problem is a backward data flow problem, i.e.
information is propagated upwards through the control flow graph. It is
therefore desirable for quick convergence to compute VBEOUT before VBEIN.

Consider the following test case:

---------------------------
void bar (void);

int p, q;

void
foo (int a, int b, int c)
{
  int x;

  if (a > 0)
    bar ();

  if (c > 0)
    {
      x = a + b;
      p = x + c;
    }
  x = a + b;
  q = x + c;
}
---------------------------

There are no back edges in the control flow graph for this function, so the
dataflow problem should converge in just 2 iterations (1 to propagate the
information across the CFG and 1 to notice convergence).

compute_code_hoist_vbeinout() currently needs 6 (!) iterations to converge for
this function. That is one iteration for each basic block, plus 1 to notice
convergence.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33828