Consider backpropagating informations from uses to def

[Quuxplusone]

Bugzilla Link	PR33151
Status	NEW
Importance	P enhancement
Reported by	Davide Italiano (ditaliano@apple.com)
Reported on	2017-05-23 22:48:18 -0700
Last modified on	2020-10-08 05:11:54 -0700
Version	trunk
Hardware	PC All
CC	dberlin@dberlin.org, filcab@gmail.com, florian_hahn@apple.com, lebedev.ri@gmail.com, llvm-bugs@lists.llvm.org, llvm-dev@redking.me.uk, spatel+llvm@rotateright.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also	PR47765

Dan pointed me out to this a while ago, and given I discussed this with Simon
and Filipe recently, let me dump this somewhere :)
GCC implements some rudimental form of backpropagation from uses to defs.

This allows them to simplify this:

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define double @tinkywinky(double %x) {
  %patatino = tail call double @llvm.fabs.f64(double %x)
  %call = tail call double @llvm.cos.f64(double %patatino)
  ret double %call
}

declare double @llvm.fabs.f64(double)
declare double @llvm.cos.f64(double)

to just:

define double @tinkywinky(double %x) {
  %call = tail call double @llvm.cos.f64(double %x)
  ret double %call
}

as they can prove that the sign doesn't matter (i.e. cos(x) = cos(-x)).
Their optimistic algorithm used is just a simple series of walks (so it should
be quite fast), divided in 4 phases:

1) Walk of the function in PO, each BB backwards, collecting interesting
informations and initially ignoring PHIs.
2) Re-examine the PHIs and reprocess the uses until a maximal fixpoint is hit
3) RPO walk to propagate informations
4) PO walk to remove dead instructions

They currently just propagates sign bits, but I can see it being extended to
propagate more informations, e.g. known bits.

I'm not sure how often this triggers in practice, but in theory it should
improve the precision of constant propagation (as we would end up propagating
informations in both direction, backwards here and forward in SCCP).

[Quuxplusone]

Also, https://godbolt.org/g/3yqJkm

[Quuxplusone]

Another case mentioned by Roman on IRC:

> given  shift iN %x, %y,  %y must be [iN 0, iN N), which means all legal shift
amounts are positive, with unset sign bit
> which means, if you have  shift iN %x, (sext %y), it can be simplified to
shift iN %x, (zext %y)

Related discussion:
https://groups.google.com/d/msg/llvm-dev/rM6SZXVJ6Ls/0rfn_7ZAAwAJ