[llvm-bugs] [Bug 39702] New: Missed opportunity to reduce number of loop iterations?

[via llvm-bugs]

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

            Bug ID: 39702
           Summary: Missed opportunity to reduce number of loop
                    iterations?
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: vsk at apple.com
                CC: llvm-bugs at lists.llvm.org

In llvm, there's plenty of hot code that looks like this:

```
  if (pred_size(BB) != 2)
    return false; // From InstCombiner::mergeStoreIntoSuccessor.
```

Here, pred_size takes linear time, but there's never a need to visit more than
two predecessors. In a stage2 Release build of llc, we do *45 million*
unnecessary linked list iterations just at this one call site [1].

Is there a way for the optimizer to recognize that no more than two iterations
are needed?

Reduced example (https://godbolt.org/z/TOtQD6):

```
struct linked_list {
    int x = 0;
    linked_list *next = nullptr;
};

int size(linked_list *ll) {
    int s = 0;
    while (ll) {
        ++s;
        ll = ll->next;
    }
    return s;
}

int no_more_than_two_iterations(linked_list *ll) {
    int s = size(ll);
    if (s != 2)
        return 0;
    return 1;
}
```

Currently we produce:

```
define dso_local i32
@_Z27no_more_than_two_iterationsP11linked_list(%struct.linked_list* readonly)
local_unnamed_addr #0 {
  %2 = icmp eq %struct.linked_list* %0, null
  br i1 %2, label %13, label %3

; <label>:3: ; preds = %1, %3
  %4 = phi i32 [ %6, %3 ], [ 0, %1 ]
  %5 = phi %struct.linked_list* [ %8, %3 ], [ %0, %1 ]
  %6 = add nuw nsw i32 %4, 1
  %7 = getelementptr inbounds %struct.linked_list, %struct.linked_list* %5, i64
0, i32 1
  %8 = load %struct.linked_list*, %struct.linked_list** %7, align 8, !tbaa !2
  %9 = icmp eq %struct.linked_list* %8, null
  br i1 %9, label %10, label %3

; <label>:10: ; preds = %3
  %11 = icmp eq i32 %6, 2
  %12 = zext i1 %11 to i32
  ret i32 %12

; <label>:13: ; preds = %1
  ret i32 0
}
```

Could we somehow make the loop exit early if the sum ever exceeds 2? Like:

```
  %9 = icmp eq %struct.linked_list* %8, null
  %enough-seen = icmp ugt i32 %6, 2
  %early-exit = or i1 %9, %enough-seen
  br i1 %early-exit, label %10, label %3
```

[1] I defined 'wasted iterations' as `pred_size(BB) - 2`, whenever that
difference would be positive. I did the stage2 build with r347179.

-- 
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/20181119/4f5ad20c/attachment.html>