llvm / llvm/llvm-project

Missed loop simplification due to missing reasoning on (%indvars.iv & 1) != 0

Open
#188,700 10 comments 0 reactions 0 assignees View on GitHub
llvm:transforms loopoptim missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

The following reduced IR is derived from https://github.com/berkeley-abc/abc/blob/6aaf0db1e1201d72888a461463485b0b5595075a/src/sat/bmc/bmcFault.c#L225

https://godbolt.org/z/qTrac5vzz

In the reduced IR, the loop executes in a fixed pattern with only three iterations: the first iteration does nothing, the second iteration calls `@sat_solver_add_buffer(0)`, and the third iteration exits. Thus the entire loop can be simplified to a single call `@sat_solver_add_buffer(0)` followed by `ret void`.

```llvm
define void @Cnf_AddCardinConstrGeneral(ptr readonly captures(none) %0) local_unnamed_addr {
.lr.ph5.preheader:
br label %.lr.ph5

.lr.ph5:
%indvars.iv = phi i64 [ 0, %.lr.ph5.preheader ], [ %indvars.iv.next, %._crit_edge ]
%1 = trunc i64 %indvars.iv to i32
%2 = and i32 %1, 1
%.not.not = icmp eq i32 %2, 0
br i1 %.not.not, label %.lr.ph.peel.next, label %3

3:
%.not.i = icmp eq i64 %indvars.iv, 0
br i1 %.not.i, label %4, label %.lr.ph.preheader

4:
%5 = load i32, ptr %0, align 4
br label %.lr.ph.preheader

.lr.ph.preheader:
%6 = phi i32 [ %5, %4 ], [ 0, %3 ]
%7 = tail call i32 @sat_solver_add_buffer(i32 %6)
br label %._crit_edge

.lr.ph.peel.next:
%exitcond.not = icmp eq i32 %1, 0
br i1 %exitcond.not, label %._crit_edge, label %.lr.ph

.lr.ph:
ret void

._crit_edge:
%indvars.iv.next = add i64 %indvars.iv, 1
br label %.lr.ph5
}
```

Expected:
```llvm
define void @Cnf_AddCardinConstrGeneral(ptr nocapture readonly captures(none) %0) local_unnamed_addr {
.lr.ph5.preheader:
%1 = tail call i32 @sat_solver_add_buffer(i32 0)
ret void
}
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.