Bug ID: 33813
           Summary: Optimization for removing same variable comparisons in
                    loop: while(it != end1 && it != end2)
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Loop Optimizer

Simple iteration by std::deque elements produces suboptimal code. For example 

#include <deque>

unsigned sum(std::deque<unsigned> cont) {
    unsigned sum = 0;
    for (unsigned v : cont)
        sum += v;

    return sum;

produces the following loop:

.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        cmp     rsi, rcx
        je      .LBB0_4
        add     eax, dword ptr [rcx]
        add     rcx, 4
        cmp     rcx, rdx
        jne     .LBB0_1
        jmp     .LBB0_3

The loop has two comparisons in it and behaves close to the following C code:

unsigned sum_like_deque_does(unsigned** chunks, unsigned* end) {
    unsigned sum = 0;

    for (unsigned* it = *chunks; it != end; it = *(++chunks)) {
        for (;it != end && it != *chunks + 128; ++it) {
            sum += *it;

    return sum;

Note the `it != end && it != *chunks + 128` condition. It could be simplified:
if `end` belongs to `[it, *chunks + 128]` change the condition to `it != end`
and use the condition `it != *chunks + 128` otherwise. Such optimization
removes the cmp from the loop and produces a much more faster loop:

.LBB2_3:                                #   Parent Loop BB2_2 Depth=1
        add     eax, dword ptr [rcx]
        add     rcx, 4
        cmp     rdx, rcx
        jne     .LBB2_3

Synthetic tests show up to 2 times better performance. Assembly outputs:

You are receiving this mail because:
You are on the CC list for the bug.
llvm-bugs mailing list

Reply via email to