fhahn
commented
4 years ago 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
llvmbot
Extended Description
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).