LLVM Bugzilla is read-only and represents the historical archive of all LLVM issues filled before November 26, 2021. Use github to submit LLVM bugs

Bug 415 - [ipsccp] Sparse conditional IP constant propagation
Summary: [ipsccp] Sparse conditional IP constant propagation
Status: RESOLVED FIXED
Alias: None
Product: libraries
Classification: Unclassified
Component: Interprocedural Optimizations (show other bugs)
Version: 1.0
Hardware: All All
: P enhancement
Assignee: Chris Lattner
URL:
Keywords: new-feature
Depends on:
Blocks:
 
Reported: 2004-08-04 15:12 PDT by Chris Lattner
Modified: 2010-02-22 12:47 PST (History)
2 users (show)

See Also:
Fixed By Commit(s):


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Chris Lattner 2004-08-04 15:12:57 PDT
Brian pointed out that the Olden/mst benchmark has code that basically looks
like this:

main() {
  Do_all_BlueRule(..., 1, 0);
}

void Do_all_BlueRule(..., int nproc, int pn) {
  if (nproc > 1) {
    Do_all_BlueRule(nproc/2, nproc/2+pn);
    ... A BUNCH OF OTHER STUFF ...
  }

  bar();
}

The observation is that Do_all_BlueRule contains a bunch of code that is
dynamically dead, but it requires a smarter IPCP algorithm to notice it (the
unreachable recursive call causes us to miss this).

It seems like an aggressive IPCP coupled with SCCP'y techniques could solve this
pretty easily.

-Chris
Comment 1 Chris Lattner 2004-09-08 11:21:14 PDT
There are some notes for this bug here:
http://nondot.org/sabre/LLVMNotes/IP-SCCP.txt

-Chris
Comment 2 Chris Lattner 2004-11-10 01:10:01 PST
Here's a trivial testcase this should handle:

implementation   ; Functions:

internal int %foo(int %X) {
        %Y = call int %foo( int %X )            ; <int> [#uses=1]
        %Z = add int %Y, 1              ; <int> [#uses=1]
        ret int %Z
}

void %bar() {
        call int %foo( int 17 )         ; <int>:0 [#uses=0]
        ret void
}

IPCP should realize that %X is always '17'.  The current, simple IPCP, should
detect and handle this too.  I wish it already did, it would help pool
allocation. :(

-Chris
Comment 3 Chris Lattner 2004-11-10 13:44:24 PST
ok, another note.  Simple IPCP now handles the simple case above.
Comment 4 Chris Lattner 2004-12-10 02:04:54 PST
Initial implementation:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20041206/022044.html

There is more to come for this PR, stay tuned!

-Chris
Comment 5 Chris Lattner 2004-12-11 00:09:15 PST
This is now implemented, named -ipsccp.

-Chris