[llvm-bugs] [Bug 43836] New: Making memmove unconditional and reducing bb count

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=43836

            Bug ID: 43836
           Summary: Making memmove unconditional and reducing bb count
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: lebedev.ri at gmail.com
                CC: llvm-bugs at lists.llvm.org

I'm not fully sure these samples fully reproduce the issue, but that is not
intentional.

It is not unheard of to apply a running summation (predictor) to each line
of image. I have seen it widely in image decoding.
But it's a bit ugly - for the first row some default value needs to be used,
and for each next row we could need to copy said initial value
from the beginning of the previous row.
Naively this results in pretty ugly branching.
But it can also be written with no extra branching:

#include <algorithm>

static constexpr int pred_size = 4;

void sink(int* data, int* pred);

void bad(int* data, int* pred, int len, int width) {
    for(int i = 0; i < len; i++) {
        int *row = data + width*i;
        if(i != 0) {
            std::copy_n(data + width*(i-1),
                        pred_size,
                        pred);
        }
        sink(row, pred);
    }
}
void subpar(int* data, int* pred, int len, int width) {
    for(int i = 0; i < len; i++) {
        int *row = data + width*i;
        std::copy_n(i == 0 ? pred : (data + width*(i-1)),
                    pred_size,
                    pred);
        sink(row, pred);
    }
}
void good(int* data, int* pred, int len, int width) {
    int* predNext = pred;
    for(int i = 0; i < len; i++) {
        int *row = data + width*i;
        // If i=0, this is a NOP copy, we memmove [pred, pred+pred_size) over
itself
        // Else, we copy [data + width*(i-1), data + width*(i-1) + pred_size)
        // from previous row into [pred, pred+pred_size).
        std::copy_n(predNext,
                    pred_size,
                    pred);
        predNext = row;
        sink(row, pred);
    }
}

https://godbolt.org/z/julQt_ 


I'm wondering how this optimization could be approached.
I guess there are several steps here:
1. Turn `bad()` into `subpar()`, by making mem copy unconditional (selecting
between the sources)
2. Replace select with phi
3. #43835 ?

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20191029/661b1f44/attachment.html>