[Bug tree-optimization/106415] New: loop-ivopts prevents correct usage of dbra with 16-bit loop counters on m68k

[Bug tree-optimization/106415] New: loop-ivopts prevents correct usage of dbra with 16-bit loop counters on m68k

[undefinedopcode2 at gmail dot com]

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

            Bug ID: 106415
           Summary: loop-ivopts prevents correct usage of dbra with 16-bit
                    loop counters on m68k
           Product: gcc
           Version: 11.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: undefinedopcode2 at gmail dot com
  Target Milestone: ---

Created attachment 53338
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53338&action=edit
C file that reproduces the problem.

When targeting m68k and compiling certain loops with 16-bit counters that
should trivially generate a DBRA instruction, GCC's optimization passes end up
converting the IV to 32-bit, which  requires extra logic to check the upper
half. More specifically, these are loops where the number of iterations is
known at compile time.

This additional code is completely useless since we know the loop count fits in
16 bits.

I am using GCC 11.2.0 hosted on ARM64 macOS and targeting m68k. All code
snippets were compiled with `-O3 -std=c99 -march=68000 -mtune=68000`.

Consider the following function:
void dbra_test1(short i) {
    do {
        foo(i);
    } while(--i != -1);
}

As expected, the generated body is a tiny loop consisting solely of call setup,
the call itself, call cleanup, and a DBRA:
.L2:
        movew %d2,%a0
        movel %a0,%sp@-
        jsr %a2@
        addql #4,%sp
        dbra %d2,.L2

Now consider this function, where we change the initial value of the loop count
to be a constant:
void dbra_test2(void) {
    short i = 15;
    do {
        foo(i);
    } while(--i != -1);
}

GCC generates the following code for the body of the loop:
.L7:
        movel %d2,%sp@-
        jsr %a2@
        addql #4,%sp
        dbra %d2,.L7
        clrw %d2
        subql #1,%d2
        jcc .L7

Note the extraneous clr/subq/jcc.

During ivcanon, GCC transforms the second loop to run from 16 to 0 instead of
15 to -1. Later during ivopts, it transforms back into 15 to -1 form, but
promotes the variable from short to int. Future transformations are no longer
able to optimize around the short variable, and we end up with extraneous
checks inserted during codegen.

I've attached a simple file that reproduces the problem. GCC 2.95.3 performed
the operation correctly, but it's been broken since at least 4.3.2, possibly
earlier.

Thanks
--UD2

[Bug tree-optimization/106415] loop-ivopts prevents correct usage of dbra with 16-bit loop counters on m68k

[undefinedopcode2 at gmail dot com]

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

--- Comment #1 from Undefined Opcode <undefinedopcode2 at gmail dot com> ---
Adding `-fno-tree-loop-ivcanon -fno-ivopts` to the compiler flags ensures the
second example function gets a properly optimized DBRA loop.

[Bug target/106415] loop-ivopts prevents correct usage of dbra with 16-bit loop counters on m68k

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|tree-optimization           |target

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I suspect this is a target cost model issue ...

You can look at the ivopts dump to see the costs there.

[Bug target/106415] loop-ivopts prevents correct usage of dbra with 16-bit loop counters on m68k

[undefinedopcode2 at gmail dot com]

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

--- Comment #3 from Undefined Opcode <undefinedopcode2 at gmail dot com> ---
Created attachment 53348
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53348&action=edit
dump of buggy optimization pass

(In reply to Andrew Pinski from comment #2)
> I suspect this is a target cost model issue ...
> 
> You can look at the ivopts dump to see the costs there.

Funny, I was just about to reply to the thread about this. It looks like it's
choosing candidate 7. I've also included the candidate 3 info for completeness.
Candidate 3:
  Incr POS: orig biv
  IV struct:
    Type:       short int
    Base:       15
    Step:       -1
    Biv:        N
    Overflowness wrto loop niter:       No-overflow
...
<trimmed>
...
Candidate 7:
  Var befor: ivtmp.19
  Var after: ivtmp.19
  Incr POS: before exit test
  IV struct:
    Type:       unsigned int
    Base:       15
    Step:       4294967295
    Biv:        N
    Overflowness wrto loop niter:       Overflow
...
<trimmed>
...
<Candidate Costs>:
  cand  cost
  0     5
  1     5
  2     5
  3     4
  4     5
  5     5
  6     5
  7     5
  8     5

It's odd to me that it's choosing 7 over 3, since 3 is clearly lower cost. It
also spits out "group candidate costs", but I'm not sure what those actually
represent (sorry, this is my first time poking through GCC optimization
internals).

I've attached a copy of test.c.174t.ivopts if someone else can make more sense
of it.

[Bug target/106415] loop-ivopts prevents correct usage of dbra with 16-bit loop counters on m68k

[undefinedopcode2 at gmail dot com]

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

--- Comment #4 from Undefined Opcode <undefinedopcode2 at gmail dot com> ---
As an experiment, I added the following logic to m68k_rtx_costs():
      case PLUS:
      // <omitted a few lines related to LEA>
      if(TUNE_68000_10 && !(mode == QImode || mode == HImode))
        {
          *total = 400; // make non-byte/word ADD outrageously expensive
          return true;
        }

Sure enough, the costs for all non-short IV shot up. However, it's still
choosing candidate 7, same as before:
<Candidate Costs>:
  cand  cost
force_expr_to_var_cost size costs:
  integer 2
  symbol 4
  address 4
  other 16

force_expr_to_var_cost speed costs:
  integer 2
  symbol 4
  address 4
  other 16

  0     401
  1     5
  2     5
  3     4
  4     5
  5     5
  6     5
  7     401
  8     401

Later, when we get to group costs, the results aren't what I'd expect:
<Group-candidate Costs>:
Group 0:
  cand  cost    compl.  inv.expr.       inv.vars
  0     400     0       NIL;    NIL;
  7     0       0       NIL;    NIL;
  8     400     0       NIL;    NIL;

Group 1:
  cand  cost    compl.  inv.expr.       inv.vars
  0     0       0       NIL;    NIL;
  1     0       0       NIL;    NIL;
  2     0       0       NIL;    NIL;
  3     0       0       NIL;    NIL;
  4     0       0       NIL;    NIL;
  5     0       0       NIL;    NIL;
  6     -1      0       NIL;    NIL;
  7     0       0       NIL;    NIL;
  8     0       0       NIL;    NIL;

I'm not entirely sure what's going on here. Why does candidate 7 suddenly cost
0?

[Bug target/106415] loop-ivopts prevents correct usage of dbra with 16-bit loop counters on m68k

[linkw at gcc dot gnu.org]

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

Kewen Lin <linkw at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |linkw at gcc dot gnu.org

--- Comment #5 from Kewen Lin <linkw at gcc dot gnu.org> ---
At the top of tree-ssa-loop-ivopts.cc file, there are some useful comments
describing the costs for iv candidate itself and group, it may help.

<Candidate Costs>:
  cand  cost
  0     5
  1     5
  2     5
  3     4
  4     5
  5     5
  6     5
  7     5
  8     5

This part is for "variable costs".

<Group-candidate Costs>:
Group 0:
  cand  cost    compl.  inv.expr.       inv.vars
  0     400     0       NIL;    NIL;
  7     0       0       NIL;    NIL;
  8     400     0       NIL;    NIL;

This part is for "group/use costs".

There would be no dumping for a candidate when it has infinite cost for the
group, so the above means only candidate 0, 7 and 8 are valid to be used for
group 0.

Final cost looks like:

    cost: 7 (complexity 0)
    reg_cost: 2
    cand_cost: 5
    cand_group_cost: 0 (complexity 0)
    candidates: 7
     group:0 --> iv_cand:7, cost=(0,0)
     group:1 --> iv_cand:7, cost=(0,0)
    invariant variables:
    invariant expressions:

----

By quick checking, it looks the inf cost for the pair (cand 3, group 0) is due
to:

  /* Check if we have enough precision to express the values of use.  */
  if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
    return infinite_cost;

[Bug target/106415] loop-ivopts prevents correct usage of dbra with 16-bit loop counters on m68k

[undefinedopcode2 at gmail dot com]

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

--- Comment #6 from Undefined Opcode <undefinedopcode2 at gmail dot com> ---
(In reply to Kewen Lin from comment #5)
> At the top of tree-ssa-loop-ivopts.cc file, there are some useful comments
> describing the costs for iv candidate itself and group, it may help.
> 
> <Candidate Costs>:
>   cand  cost
>   0     5
>   1     5
>   2     5
>   3     4
>   4     5
>   5     5
>   6     5
>   7     5
>   8     5
> 
> This part is for "variable costs".
> 
> <Group-candidate Costs>:
> Group 0:
>   cand	cost	compl.	inv.expr.	inv.vars
>   0	400	0	NIL;	NIL;
>   7	0	0	NIL;	NIL;
>   8	400	0	NIL;	NIL;
> 
> This part is for "group/use costs".
> 
> There would be no dumping for a candidate when it has infinite cost for the
> group, so the above means only candidate 0, 7 and 8 are valid to be used for
> group 0.
> 
> Final cost looks like:
> 
>     cost: 7 (complexity 0)
>     reg_cost: 2
>     cand_cost: 5
>     cand_group_cost: 0 (complexity 0)
>     candidates: 7
>      group:0 --> iv_cand:7, cost=(0,0)
>      group:1 --> iv_cand:7, cost=(0,0)
>     invariant variables:
>     invariant expressions:
> 
> ----
> 
> By quick checking, it looks the inf cost for the pair (cand 3, group 0) is
> due to:
> 
>   /* Check if we have enough precision to express the values of use.  */
>   if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
>     return infinite_cost;

Some debug prints confirm this is indeed what's happening, the pass thinks
candidate 3 is trying to fit a 32-bit value into 16-bits and bails. What's not
clear to me is why. Does it have some notion of -1 requiring 32-bits to store
even though it'll fit just fine in 16 for our purposes?

[Bug target/106415] loop-ivopts prevents correct usage of dbra with 16-bit loop counters on m68k

[undefinedopcode2 at gmail dot com]

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

--- Comment #7 from Undefined Opcode <undefinedopcode2 at gmail dot com> ---
(In reply to Undefined Opcode from comment #6)
A little more context:
Group 1:
  cand  cost    compl.  inv.expr.       inv.vars
  0     0       0       NIL;    NIL;
  1     0       0       NIL;    NIL;
  2     0       0       NIL;    NIL;
  3     0       0       NIL;    NIL;
  4     0       0       NIL;    NIL;
  5     0       0       NIL;    NIL;
  6     -1      0       NIL;    NIL;
  7     0       0       NIL;    NIL;
  8     0       0       NIL;    NIL;

I'm not sure what a negative cost means, but it's also odd to me that the other
candidates all have the same cost. The candidates requiring 32-bit operations
should be strictly more expensive than those operating on 16-bit data, and
indeed they do during the initial candidate costs.