[llvm-bugs] [Bug 33151] New: Consider backpropagating informations from uses to def

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=33151

            Bug ID: 33151
           Summary: Consider backpropagating informations from uses to def
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: davide at freebsd.org
                CC: dberlin at dberlin.org, filcab at gmail.com,
                    llvm-bugs at lists.llvm.org, llvm-dev at redking.me.uk

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).

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20170524/e906a117/attachment.html>