Missed optimization: constant range analysis

[alinas]

In the following testcase, ideally, the jump to the trap can de elided, but the current optimization pipeline misses this.

Running CorrelatedValuePropagation (-passes=correlated-propagation) misses this due to merging the ranges for the incoming predecessors into a block. Currently LVI does "union(predecessors)", followed by "computation based on instruction opcode". If the ranges were stored per block predecessor (another cache...so added cost...), LVI could theoretically do first "computation based on instruction opcode for each predecessor", followed by "union(predecessors)").

For the example below, the range for%lshr is currently the result of lshr [7, 277632] [3, 8], which is [0, 34704]. The intervals used for the lshr are the results of previous union operations from the phi nodes.
But if the intervals for the operands were computed per predecessor (for the add and phis, store the result of getEdgeValue before doing the union in mergeIn), then the range for%lshr could become the union of ((lshr [7, 1032] , 3), (lshr [15487, 262145], 7))=union of ([0, 129], [129, 2169])=[0, 2169]. With this, %icmp6 could be replaced with true in the br.

Is it worth extending LVI to support this for constant ranges only, when all predecessor values are known (i.e. clear the predecessor cache on early exit for overdefined), with compile times evaluated and the extended cache populated/used under a flag?

Are there other passes or ways this range analysis is done and could currently catch this?

@global = external local_unnamed_addr global [4338 x i32], align 16

define dso_local noundef zeroext i1 @foo(i64 noundef %arg, ptr noundef writeonly captures(none) %arg1) local_unnamed_addr {
bb:
  %icmp = icmp ult i64 %arg, 1025
  br i1 %icmp, label %bb4, label %bb2

bb2:                                              ; preds = %bb
  %icmp3 = icmp ult i64 %arg, 262145
  br i1 %icmp3, label %bb4, label %bb9

bb4:                                              ; preds = %bb2, %bb
  %phi = phi i64 [ 7, %bb ], [ 15487, %bb2 ]
  %phi5 = phi i64 [ 3, %bb ], [ 7, %bb2 ]
  %add = add nuw nsw i64 %phi, %arg
  %lshr = lshr i64 %add, %phi5
  %icmp6 = icmp samesign ult i64 %lshr, 4338
  br i1 %icmp6, label %bb8, label %bb7

bb7:                                              ; preds = %bb4
  tail call void @llvm.ubsantrap(i8 18)
  unreachable

bb8:                                              ; preds = %bb4
  %getelementptr = getelementptr inbounds nuw [4338 x i32], ptr @global, i64 0, i64 %lshr
  %load = load i32, ptr %getelementptr, align 4
  %sext = sext i32 %load to i64
  store i64 %sext, ptr %arg1, align 8
  br label %bb9

bb9:                                              ; preds = %bb8, %bb2
  %phi10 = phi i1 [ true, %bb8 ], [ false, %bb2 ]
  ret i1 %phi10
}

; Function Attrs: cold noreturn nounwind
declare void @llvm.ubsantrap(i8 immarg) #0

attributes #0 = { cold noreturn nounwind }

[VedantParanjape]

For the example below, the range for%lshr is currently the result of lshr [7, 277632] [3, 8], which is [0, 34704].

I am trying to understand the problem. So, LVI computed range of add using incoming value from bb2 and range of arg from bb2, but not from bb?

opt log

LVI Getting block end value i64 %arg at 'bb'
PUSH: i64 %arg in bb
POP i64 %arg in bb = overdefined
  Result = overdefined
LVI Getting block end value i64 %arg at 'bb'
  Result = overdefined
LVI Getting block end value i64 1025 at 'bb'
  Result = constantrange<1025, 1026>
LVI Getting block end value   %lshr = lshr i64 %add, %phi5 at 'bb4'
PUSH:   %lshr = lshr i64 %add, %phi5 in bb4
PUSH:   %add = add nuw nsw i64 %phi, %arg in bb4
PUSH:   %phi = phi i64 [ 7, %bb ], [ 15487, %bb2 ] in bb4
POP   %phi = phi i64 [ 7, %bb ], [ 15487, %bb2 ] in bb4 = constantrange<7, 15488>
PUSH: i64 %arg in bb4
PUSH: i64 %arg in bb2
POP i64 %arg in bb2 = constantrange<1025, 0>
POP i64 %arg in bb4 = constantrange<0, 262145>
POP   %add = add nuw nsw i64 %phi, %arg in bb4 = constantrange<7, 277632>
PUSH:   %phi5 = phi i64 [ 3, %bb ], [ 7, %bb2 ] in bb4
POP   %phi5 = phi i64 [ 3, %bb ], [ 7, %bb2 ] in bb4 = constantrange<3, 8>
POP   %lshr = lshr i64 %add, %phi5 in bb4 = constantrange<0, 34704>
  Result = constantrange<0, 34704>
LVI Getting block end value   %load = load i32, ptr %getelementptr, align 4 at 'bb8'
PUSH:   %load = load i32, ptr %getelementptr, align 4 in bb8
 compute BB 'bb8' - unknown inst def found.
POP   %load = load i32, ptr %getelementptr, align 4 in bb8 = overdefined
  Result = overdefined
LVI Getting block end value   %phi10 = phi i1 [ true, %bb8 ], [ false, %bb2 ] at 'bb9'
PUSH:   %phi10 = phi i1 [ true, %bb8 ], [ false, %bb2 ] in bb9
 compute BB 'bb9' - overdefined because of pred (local).
POP   %phi10 = phi i1 [ true, %bb8 ], [ false, %bb2 ] in bb9 = overdefined
  Result = overdefined
LVI Getting block end value   %phi10 = phi i1 [ true, %bb8 ], [ false, %bb2 ] at 'bb9'
  Result = overdefined
LVI Getting block end value i64 %arg at 'bb2'
  Result = constantrange<1025, 0>
LVI Getting edge value i64 %arg from 'bb' to 'bb2'
  Result = constantrange<1025, 0>
LVI Getting block end value i64 %arg at 'bb2'
  Result = constantrange<1025, 0>
LVI Getting block end value i64 262145 at 'bb2'
  Result = constantrange<262145, 262146>

[alinas]

Currently:
%arg: [0, 262145]
%phi : [ 7, 15487]
so %add is computed as: [7, 277632]
Then:
%phi5: [ 3, 7]
%lshr = lshr i64 %add, %phi5 is going to be [0, 34704]

What I'm looking for:
%arg: bb: [0, 1025] bb2: [0, 262145] (also store the intervals per predecessor)
%phi: bb: 7, bb2: 15487 (again, per predecessor)
so %add can be computed per predecessor: bb: [7, 2032] bb2: [15487, 262145] .
The union of intervals for the add gives the same result as before.
But then:
%phi5: bb: 3, bb2: 7
%lshr = lshr i64 %add, %phi5 becomes: bb: [0, 129] bb2: [129, 2169]
The union of intervals for the lshr is more restricted: [0, 2169], and the branch condition can now be evaluated to true.

Does this make sense?

[alinas]

Here's a draft version: main...alinas:llvm-project:perf/lvi-ranges

[VedantParanjape]

Yeah now it makes sense, I walked through call graph with GDB and it seems that LVI tries to reach arg in bb through bb2 and does not explore the bb4 -> bb path hence it gets the wrong ranges.

[alinas]

Compile-time increase is significant: https://llvm-compile-time-tracker.com/compare.php?from=1756b6e59cb1bbf78a9122c008ab0c6d413e1497&to=cc70d6d59bd1137b15e43a2022c0e6c14e9f2b39&stat=instructions:u

This could only be considered to be added under a flag at the moment. Note, the scenario above occurs for ubsan, and likely for other code patterns that add bounds checks. It is possible the compile-time cost is worth it for the added binary performance but I don't have data to share atm.

[alinas]

@nikic for visibility.