SimplifyCFG switch removal should add no-wrap flags when possible

[scottmcm]

Today, LLVM optimizes

define noundef i8 @src(i8 noundef %x) unnamed_addr {
start:
  switch i8 %x, label %bb3 [
    i8 -1, label %bb1
    i8 0, label %bb5
    i8 1, label %bb2
  ]

bb3:                                              ; preds = %start
  unreachable

bb5:                                              ; preds = %start
  br label %bb1

bb2:                                              ; preds = %start
  br label %bb1

bb1:                                              ; preds = %start, %bb5, %bb2
  %.0 = phi i8 [ -1, %bb2 ], [ 0, %bb5 ], [ 1, %start ]
  ret i8 %.0
}

down to

start:
  %switch.offset = sub i8 0, %x
  ret i8 %switch.offset

That's a huge improvement, but it could be slightly better as a sub nsw instead: https://alive2.llvm.org/ce/z/GZs_dj

If I'm understanding things right, SimplifyCFG turns the switch into

define noundef i8 @tgt(i8 noundef %x) unnamed_addr {
start:
  %switch.tableidx = sub i8 %x, -1
  %switch.idx.mult = mul i8 %switch.tableidx, -1
  %switch.offset = add i8 %switch.idx.mult, 1
  ret i8 %switch.offset
}

but in this case it could (https://alive2.llvm.org/ce/z/XzPeQv) have those be sub nsw, mul nsw, and add nsw, to better preserve the knowledge of the limited input range -- or maybe special case switches that map 0 to 0 to just emit mul nsw (or nuw) when legal without the extra sub/add complication.

Then something else (instcombine?) could take advantage of those nsw flags to optimize down to just the sub nsw i8, 0, %x: https://alive2.llvm.org/ce/z/tESh4R. But it looks like they got lost right now (https://llvm.godbolt.org/z/3dMW8j1sr), so maybe there'd be more work there too. (If SimplifyCFG left off the sub/add, though, and just had the mul nsw, then InstCombine looks like it would already preserve the nsw to the sub https://llvm.godbolt.org/z/9der4sraG.)

---

Original rust exploration that led me here: https://rust.godbolt.org/z/EW1aba8Mr

[khei4]

nit: Currently arithmetically negated branch optimization has not been implemented even on the main. But logical negation is implemented.
https://llvm.godbolt.org/z/8ozvqj1cf
But InstCombine part seems reasonable.

Edit: Sorry I misunderstand the related pass and just have seen the partial IR result(missing data layout) https://llvm.godbolt.org/z/7saozhM5K.

Original rust exploration that led me here: https://rust.godbolt.org/z/EW1aba8Mr

[khei4]

reduced case for opt -O3, (SimplifyCFG switch-to-lookup depends on native integer widths)
https://llvm.godbolt.org/z/1Ynvjqvnn
for SimplifyCFG, switch-to-lookup enabled
https://llvm.godbolt.org/z/nraenEz7j

[nikic]

Does the missing nsw flag actually matter for some following optimization?

[nikic]

The last part of this has landed in https://reviews.llvm.org/D150943, so closing this issue. We how produce sub nsw i8 0, %x for this input.

[scottmcm]

Thanks nikic!

I forget specifically what I was looking at back when I opened this, so I'm not certain what, if anything, needed it. My guess would be something like a c.reverse() < 0 after a bunch of inlining, and thus knowing that it's nsw is important to turn that into c > 0.