Predicate Aware Tracing #1670

Currently, our tracer indiscriminately traces through all gamma subregions even though these gamma subregions might not affect the result of tracing due to predication.

The problem was discovered from this program:

int
recog (rtx x0 ATTRIBUTE_UNUSED,
        rtx insn ATTRIBUTE_UNUSED,
        int *pnum_clobbers ATTRIBUTE_UNUSED)
{
  rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];
  rtx x1 ATTRIBUTE_UNUSED;
  rtx x2 ATTRIBUTE_UNUSED;
  rtx x3 ATTRIBUTE_UNUSED;
  rtx x4 ATTRIBUTE_UNUSED;
  rtx x5 ATTRIBUTE_UNUSED;
  rtx x6 ATTRIBUTE_UNUSED;
  rtx x7 ATTRIBUTE_UNUSED;
  rtx x8 ATTRIBUTE_UNUSED;
  int tem ATTRIBUTE_UNUSED;
  recog_data.insn = NULL_RTX;

  switch (XVECLEN (x0, 0))
    {
    case 2:
      goto L126;
    default:
      break;
    }
 L21778: ATTRIBUTE_UNUSED_LABEL
  if (XVECLEN (x0, 0) >= 1
      && vzeroupper_operation (x0, VOIDmode))
    {
      operands[0] = x0;
      goto ret0;
    }
  goto ret0;
 L126: ATTRIBUTE_UNUSED_LABEL
  x1 = XVECEXP (x0, 0, 0);
  switch (GET_CODE (x1))
    {
    case SET:
      goto L127;
    default:
     break;
   }
  goto L21778;

 L127: ATTRIBUTE_UNUSED_LABEL
  if (constant_call_address_operand (x3, SImode))
    {
      operands[0] = x3;
      goto ret0;
    }

 ret0:
  return -1;
}

The corresponding CFG looks like this:

Note, that the basic block with the CALL constant_call_address_operand is not dominated by basic block 0x5555560293f0, and therefore all its containing getelementptr operations do not dominate the call.

After restructuring, the CFG looks like this:

Note, that the same basic block with the getelementptr is now "below" the CALL constant_call_address_operand basic block (still not dominated though).

The corresponding RVSDG looks like this:

Note that it should be possible to load-load forward the load nodes in Region 8 with the ones in Region 1, removing the load nodes from Region 8 completely, but that is currently not happening due to two facts:

1. The tracer indiscriminately traces through all gamma subregions
2. The CALL is now "above" the load nodes from Region 8

This means that the tracer starts from the memory states of the load nodes in Region 8, goes into the gamma with Region 2 and Region 3, continues in Region 2 with the gamma that has Region 4 and Region 5, and meets eventually in Region 4 the call node, where it simply has to give up as this is an external call.

However, it should actually not meet the CALL constant_call_address_operand node, as this node is not in its path in the original CFG to the other loads. Thus, the restructuring in combination with indiscriminately tracing through all subregions, even though we could statically determine that certain subregions are not relevant prohibit us from performing optimizations.

A simpler and more reduced example is shown here:

We should be able to constant fold the negate operation, but cannot do so as we indiscriminately trace through both subregions of the upper gamma, even though we statically see that only subregion 0 of the upper gamma ever causes execution to go into subregion 0 of the lower gamma.