Overhead of SSA operands

[Steven Bosscher <stevenb at suse dot de>]

Hi,

Recently I've seen into-SSA take up significant amounts of time on
a number of test cases, including gcc itself and the test case for 
PR8361.  Functions like rewrite_stmt() in tree-into-ssa() can take
as much as 2% of the entire compile time at -O2.

Much of this seems to be due to the overhead of your SSA operands
work.  Consider this little loop here, from rewrite_stmt.

        -: 1113:
        -: 1114:  /* Step 1.  Rewrite USES and VUSES in the statement.  */
 20553582: 1115:  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
  7842752: 1116:    rewrite_operand (use_p);
        -: 1117:


Here is the code we produce for this loop, including initialization:

.L1104:
        addl    $20, %eax       #  ops
        movb    $0, -28(%ebp)   #  <variable>.done
        xorl    %ecx, %ecx
        movl    %eax, -32(%ebp) #  ops,  <variable>.ops
        movl    4(%eax), %edx   #  <variable>.use_ops
        movl    $0, -84(%ebp)   #  <variable>.num_def
        testl   %edx, %edx
        je      .L1110
        movl    (%edx), %ecx    #  <variable>.num_uses
.L1110:
        movl    12(%eax), %edx  #  <variable>.vuse_ops
        movl    %ecx, (%esi)    #  <variable>.num_use
        xorl    %ecx, %ecx
        testl   %edx, %edx
        je      .L1114
        movl    (%edx), %ecx    #  <variable>.num_vuses
.L1114:
        movl    8(%eax), %edx   #  <variable>.v_may_def_ops
        movl    %ecx, 8(%esi)   #  <variable>.num_vuse
        xorl    %ecx, %ecx
        testl   %edx, %edx
        je      .L1118
        movl    (%edx), %ecx    #  <variable>.num_v_may_defs
.L1118:
        movl    16(%eax), %eax  #  <variable>.v_must_def_ops
        xorl    %edx, %edx
        movl    %ecx, 12(%esi)  #  <variable>.num_v_mayu
        movl    $0, 16(%esi)    #  <variable>.num_v_mayd
        testl   %eax, %eax
        je      .L1126
        movl    (%eax), %edx    #  <variable>.num_v_must_defs
.L1126:
        xorl    %eax, %eax
        movl    %edx, 20(%esi)  #  <variable>.num_v_mustu
        movl    $0, 24(%esi)    #  <variable>.num_v_mustd
        movl    $0, 32(%esi)    #  <variable>.def_i
        movl    $0, 28(%esi)    #  <variable>.use_i
        movl    $0, 36(%esi)    #  <variable>.vuse_i
        movl    $0, 40(%esi)    #  <variable>.v_mayu_i
        movl    $0, 44(%esi)    #  <variable>.v_mayd_i
        movl    $0, 48(%esi)    #  <variable>.v_mustu_i
        movl    $0, 52(%esi)    #  <variable>.v_mustd_i
        cmpl    (%esi), %eax    #  <variable>.num_use
        jge     .L1134
        movl    56(%esi), %eax  #  <variable>.ops
        movl    $1, 28(%esi)    #  <variable>.use_i
        movl    4(%eax), %eax   #  <variable>.use_ops,  uses
        movl    4(%eax), %eax   #  <variable>.uses,  <anonymous>
.L1136:
        movl    %eax, %ebx      #  <anonymous>,  use_p
        cmpb    $0, -28(%ebp)   #  <variable>.done
        je      .L1161
        jmp     .L1220
        .p2align 4,,7
.L1226:
        movl    -32(%ebp), %eax #  <variable>.ops
        movl    4(%eax), %edx   #  <variable>.use_ops,  uses
        leal    1(%ecx), %eax
        movl    %eax, -60(%ebp) #  <variable>.use_i
        movl    4(%edx,%ecx,4), %eax    #  <variable>.uses,  <anonymous>
.L1154:
        movl    %eax, %ebx      #  <anonymous>,  use_p
        cmpb    $0, -28(%ebp)   #  <variable>.done
        jne     .L1220
.L1161:
        movl    (%ebx), %eax    # * use_p,  <anonymous>
        cmpb    $-113, 12(%eax) #  <variable>.common.code
        je      .L1146
        subl    $12, %esp
        pushl   %eax    #  <anonymous>
        call    get_reaching_def
        addl    $16, %esp
        movl    %eax, (%ebx)    #  <anonymous>, * use_p
.L1146:
        movl    -60(%ebp), %ecx #  <variable>.use_i
        cmpl    -88(%ebp), %ecx #  <variable>.num_use
        jl      .L1226
        movl    -52(%ebp), %ecx #  <variable>.vuse_i
        cmpl    -80(%ebp), %ecx #  <variable>.num_vuse
        jge     .L1155
        movl    -32(%ebp), %eax #  <variable>.ops
        movl    12(%eax), %edx  #  <variable>.vuse_ops,  vuses
        leal    1(%ecx), %eax
        movl    %eax, -52(%ebp) #  <variable>.vuse_i
        leal    4(%edx,%ecx,4), %eax    #  <anonymous>
        movl    %eax, %ebx      #  <anonymous>,  use_p
        cmpb    $0, -28(%ebp)   #  <variable>.done
        je      .L1161
        .p2align 4,,7

        (...)

.L1155:
        movl    -48(%ebp), %ecx #  <variable>.v_mayu_i
        cmpl    -76(%ebp), %ecx #  <variable>.num_v_mayu
        jge     .L1157
        movl    -32(%ebp), %eax #  <variable>.ops
        movl    8(%eax), %edx   #  <variable>.v_may_def_ops,  v_may_defs
        leal    1(%ecx), %eax
        movl    %eax, -48(%ebp) #  <variable>.v_mayu_i
        leal    8(%edx,%ecx,8), %eax    #  <anonymous>
        jmp     .L1154
        .p2align 4,,7

        (...)

.L1157:
        movl    -40(%ebp), %ecx #  <variable>.v_mustu_i
        cmpl    -68(%ebp), %ecx #  <variable>.num_v_mustu
        jge     .L1159
        movl    -32(%ebp), %eax #  <variable>.ops
        movl    16(%eax), %edx  #  <variable>.v_must_def_ops,  v_must_defs
        leal    1(%ecx), %eax
        movl    %eax, -40(%ebp) #  <variable>.v_mustu_i
        leal    8(%edx,%ecx,8), %eax    #  <anonymous>
        jmp     .L1154

        (...)

.L1159:
        movb    $1, -28(%ebp)   #  <variable>.done
        movl    NULL_USE_OPERAND_P, %eax        #  NULL_USE_OPERAND_P,  <anonymous>
        jmp     .L1154


That is pretty bad eh?

Note how some of those conditions, say "use_i < num_use", execute many
times over even if it obviously never can be false once all USEs have
been visited.  Also note that the actual loop only starts at L1154, so
the initialization overhead for this "iterator" is also significant.
Especially for the common case in GIMPLE where a statement only has a
pair of normal USE operands.  Then, the block ordering is really bad.
Finally, the iterator itself is so big that it can't be scalarized (it
is not scalarized on PowerPC either).

This is just for this one loop.  For the next loop in rewrite_stmt we
go through the same thing again.  And this is just rewrite_stmt...

Is the benefit of abstraction really worth this?  With smaller, per
operand type iterators we would probably get much better code than
this.

Gr.
Steven