oota-llvm.git
15 years agoMove pattern check outside of the if-then statement. This prevents us from fiddling...
Bill Wendling [Mon, 1 Dec 2008 07:47:02 +0000 (07:47 +0000)]
Move pattern check outside of the if-then statement. This prevents us from fiddling with constants unless we have to.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60340 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoRename some variables, only increment BI once at the start of the loop instead of...
Chris Lattner [Mon, 1 Dec 2008 07:35:54 +0000 (07:35 +0000)]
Rename some variables, only increment BI once at the start of the loop instead of throughout it.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60339 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agopull the predMap densemap out of the inner loop of performPRE, so
Chris Lattner [Mon, 1 Dec 2008 07:29:03 +0000 (07:29 +0000)]
pull the predMap densemap out of the inner loop of performPRE, so
that it isn't reallocated all the time.  This is a tiny speedup for
GVN: 3.90->3.88s

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60338 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoswitch a couple more calls to use array_pod_sort.
Chris Lattner [Mon, 1 Dec 2008 06:52:57 +0000 (06:52 +0000)]
switch a couple more calls to use array_pod_sort.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60337 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agodon't assume iterators implicitly convert to pointers.
Chris Lattner [Mon, 1 Dec 2008 06:50:46 +0000 (06:50 +0000)]
don't assume iterators implicitly convert to pointers.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60336 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoIntroduce a new array_pod_sort function and switch LSR to use it
Chris Lattner [Mon, 1 Dec 2008 06:49:59 +0000 (06:49 +0000)]
Introduce a new array_pod_sort function and switch LSR to use it
instead of std::sort.  This shrinks the release-asserts LSR.o file
by 1100 bytes of code on my system.

We should start using array_pod_sort where possible.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60335 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoEliminate use of setvector for the DeadInsts set, just use a smallvector.
Chris Lattner [Mon, 1 Dec 2008 06:27:41 +0000 (06:27 +0000)]
Eliminate use of setvector for the DeadInsts set, just use a smallvector.
This is a lot cheaper and conceptually simpler.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60332 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoDeleteTriviallyDeadInstructions is always passed the
Chris Lattner [Mon, 1 Dec 2008 06:14:28 +0000 (06:14 +0000)]
DeleteTriviallyDeadInstructions is always passed the
DeadInsts ivar, just use it directly.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60330 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agosimplify DeleteTriviallyDeadInstructions again, unlike my previous
Chris Lattner [Mon, 1 Dec 2008 06:11:32 +0000 (06:11 +0000)]
simplify DeleteTriviallyDeadInstructions again, unlike my previous
buggy rewrite, this notifies ScalarEvolution of a pending instruction
about to be removed and then erases it, instead of erasing it then
notifying.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60329 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agosimplify these patterns using m_Specific. No need to grep for
Chris Lattner [Mon, 1 Dec 2008 05:16:26 +0000 (05:16 +0000)]
simplify these patterns using m_Specific.  No need to grep for
xor in testcase (or is a substring).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60328 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoTeach jump threading to clean up after itself, DCE and constfolding the
Chris Lattner [Mon, 1 Dec 2008 04:48:07 +0000 (04:48 +0000)]
Teach jump threading to clean up after itself, DCE and constfolding the
new instructions it simplifies.  Because we're threading jumps on edges
with constants coming in from PHI's, we inherently are exposing a lot more
constants to the new block.  Folding them and deleting dead conditions
allows the cost model in jump threading to be more accurate as it iterates.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60327 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoThe PreVerifier pass preserves everything. In practice, this
Chris Lattner [Mon, 1 Dec 2008 03:58:38 +0000 (03:58 +0000)]
The PreVerifier pass preserves everything.  In practice, this
prevents the passmgr from adding yet-another domtree invocation
for Verifier if there is already one live.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60326 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoChange instcombine to use FoldPHIArgGEPIntoPHI to fold two operand PHIs
Chris Lattner [Mon, 1 Dec 2008 03:42:51 +0000 (03:42 +0000)]
Change instcombine to use FoldPHIArgGEPIntoPHI to fold two operand PHIs
instead of using FoldPHIArgBinOpIntoPHI.  In addition to being more
obvious, this also fixes a problem where instcombine wouldn't merge two
phis that had different variable indices.  This prevented instcombine
from factoring big chunks of code in 403.gcc.  For example:

 insn_cuid.exit:
-       %tmp336 = load i32** @uid_cuid, align 4
-       %tmp337 = getelementptr %struct.rtx_def* %insn_addr.0.ph.i, i32 0, i32 3
-       %tmp338 = bitcast [1 x %struct.rtunion]* %tmp337 to i32*
-       %tmp339 = load i32* %tmp338, align 4
-       %tmp340 = getelementptr i32* %tmp336, i32 %tmp339
        br label %bb62

 bb61:
-       %tmp341 = load i32** @uid_cuid, align 4
-       %tmp342 = getelementptr %struct.rtx_def* %insn, i32 0, i32 3
-       %tmp343 = bitcast [1 x %struct.rtunion]* %tmp342 to i32*
-       %tmp344 = load i32* %tmp343, align 4
-       %tmp345 = getelementptr i32* %tmp341, i32 %tmp344
        br label %bb62

 bb62:
-       %iftmp.62.0.in = phi i32* [ %tmp345, %bb61 ], [ %tmp340, %insn_cuid.exit ]
+       %insn.pn2 = phi %struct.rtx_def* [ %insn, %bb61 ], [ %insn_addr.0.ph.i, %insn_cuid.exit ]
+       %tmp344.pn.in.in = getelementptr %struct.rtx_def* %insn.pn2, i32 0, i32 3
+       %tmp344.pn.in = bitcast [1 x %struct.rtunion]* %tmp344.pn.in.in to i32*
+       %tmp341.pn = load i32** @uid_cuid
+       %tmp344.pn = load i32* %tmp344.pn.in
+       %iftmp.62.0.in = getelementptr i32* %tmp341.pn, i32 %tmp344.pn
        %iftmp.62.0 = load i32* %iftmp.62.0.in

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60325 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoTeach inst combine to merge GEPs through PHIs. This is really
Chris Lattner [Mon, 1 Dec 2008 02:34:36 +0000 (02:34 +0000)]
Teach inst combine to merge GEPs through PHIs.  This is really
important because it is sinking the loads using the GEPs, but
not the GEPs themselves.  This triggers 647 times on 403.gcc
and makes the .s file much much nicer.  For example before:

        je      LBB1_87 ## bb78
LBB1_62:        ## bb77
        leal    84(%esi), %eax
LBB1_63:        ## bb79
        movl    (%eax), %eax
...
LBB1_87:        ## bb78
        movl    $0, 4(%esp)
        movl    %esi, (%esp)
        call    L_make_decl_rtl$stub
        jmp     LBB1_62 ## bb77

after:

        jne     LBB1_63 ## bb79
LBB1_62:        ## bb78
        movl    $0, 4(%esp)
        movl    %esi, (%esp)
        call    L_make_decl_rtl$stub
LBB1_63:        ## bb79
        movl    84(%esi), %eax

The input code was (and the GEPs are merged and
the PHI is now eliminated by instcombine):

        br i1 %tmp233, label %bb78, label %bb77
bb77:
        %tmp234 = getelementptr %struct.tree_node* %t_addr.3, i32 0, i32 0, i32 22
        br label %bb79
bb78:
        call void @make_decl_rtl(%struct.tree_node* %t_addr.3, i8* null) nounwind
        %tmp235 = getelementptr %struct.tree_node* %t_addr.3, i32 0, i32 0, i32 22
        br label %bb79
bb79:
        %iftmp.12.0.in = phi %struct.rtx_def** [ %tmp235, %bb78 ], [ %tmp234, %bb77 ]
        %iftmp.12.0 = load %struct.rtx_def** %iftmp.12.0.in

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60322 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agotestcase for my previous commit.
Chris Lattner [Mon, 1 Dec 2008 01:42:03 +0000 (01:42 +0000)]
testcase for my previous commit.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60315 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoMake GVN be more intelligent about redundant load
Chris Lattner [Mon, 1 Dec 2008 01:31:36 +0000 (01:31 +0000)]
Make GVN be more intelligent about redundant load
elimination: when finding dependent load/stores, realize that
they are the same if aliasing claims must alias instead of relying
on the pointers to be exactly equal.  This makes load elimination
more aggressive.  For example, on 403.gcc, we had:

<     68 gvn    - Number of instructions PRE'd
< 152718 gvn    - Number of instructions deleted
<  49699 gvn    - Number of loads deleted
<   6153 memdep - Number of dirty cached non-local responses
< 169336 memdep - Number of fully cached non-local responses
< 162428 memdep - Number of uncached non-local responses

now we have:

>     64 gvn    - Number of instructions PRE'd
> 153623 gvn    - Number of instructions deleted
>  49856 gvn    - Number of loads deleted
>   5022 memdep - Number of dirty cached non-local responses
> 159030 memdep - Number of fully cached non-local responses
> 162443 memdep - Number of uncached non-local responses

That's an extra 157 loads deleted and extra 905 other instructions nuked.

This slows down GVN very slightly, from 3.91 to 3.96s.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60314 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoReimplement the non-local dependency data structure in terms of a sorted
Chris Lattner [Mon, 1 Dec 2008 01:15:42 +0000 (01:15 +0000)]
Reimplement the non-local dependency data structure in terms of a sorted
vector instead of a densemap.  This shrinks the memory usage of this thing
substantially (the high water mark) as well as making operations like
scanning it faster.  This speeds up memdep slightly, gvn goes from
3.9376 to 3.9118s on 403.gcc

This also splits out the statistics for the cached non-local case to
differentiate between the dirty and clean cached case.  Here's the stats
for 403.gcc:

  6153 memdep - Number of dirty cached non-local responses
169336 memdep - Number of fully cached non-local responses
162428 memdep - Number of uncached non-local responses

yay for caching :)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60313 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoImplement ((A|B)&1)|(B&-2) -> (A&1) | B transformation. This also takes care of
Bill Wendling [Mon, 1 Dec 2008 01:07:11 +0000 (01:07 +0000)]
Implement ((A|B)&1)|(B&-2) -> (A&1) | B transformation. This also takes care of
permutations of this pattern.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60312 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFix bogus assertion using getSExtValue for legitimate values, like -1 in
Eli Friedman [Mon, 1 Dec 2008 00:43:48 +0000 (00:43 +0000)]
Fix bogus assertion using getSExtValue for legitimate values, like -1 in
an 128-bit-wide integer.  No testcase; the issue I ran into depends on
local changes.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60311 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoCache analyses in ivars and add some useful DEBUG output.
Chris Lattner [Mon, 1 Dec 2008 00:40:32 +0000 (00:40 +0000)]
Cache analyses in ivars and add some useful DEBUG output.
This speeds up GVN from 4.0386s to 3.9376s.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60310 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoimprove indentation, do cheap checks before expensive ones,
Chris Lattner [Sun, 30 Nov 2008 23:39:23 +0000 (23:39 +0000)]
improve indentation, do cheap checks before expensive ones,
remove some fixme's.  This speeds up GVN very slightly on 403.gcc
(4.06->4.03s)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60309 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoEliminate the DepResultTy abstraction. It is now completely
Chris Lattner [Sun, 30 Nov 2008 23:17:19 +0000 (23:17 +0000)]
Eliminate the DepResultTy abstraction.  It is now completely
redundant with MemDepResult, and MemDepResult has a nicer interface.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60308 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoMinor cleanup: use getTrue and getFalse where appropriate. No
Eli Friedman [Sun, 30 Nov 2008 22:48:49 +0000 (22:48 +0000)]
Minor cleanup: use getTrue and getFalse where appropriate.  No
functional change.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60307 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoSome minor cleanups to instcombine; no functionality change.
Eli Friedman [Sun, 30 Nov 2008 21:09:11 +0000 (21:09 +0000)]
Some minor cleanups to instcombine; no functionality change.

Note that the FoldOpIntoPhi call is dead because it's impossible for the
first operand of a subtraction to be both a ConstantInt and a PHINode.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60306 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoCache TargetData/AliasAnalysis in the pass instead of calling
Chris Lattner [Sun, 30 Nov 2008 19:24:31 +0000 (19:24 +0000)]
Cache TargetData/AliasAnalysis in the pass instead of calling
getAnalysis<>.  getAnalysis<> is apparently extremely expensive.
Doing this speeds up GVN on 403.gcc by 16%!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60304 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoadd the rest of the comparison routines.
Chris Lattner [Sun, 30 Nov 2008 19:10:41 +0000 (19:10 +0000)]
add the rest of the comparison routines.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60303 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoAdd instruction combining for ((A&~B)|(~A&B)) -> A^B and all permutations.
Bill Wendling [Sun, 30 Nov 2008 13:52:49 +0000 (13:52 +0000)]
Add instruction combining for ((A&~B)|(~A&B)) -> A^B and all permutations.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60291 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoImplement (A&((~A)|B)) -> A&B transformation in the instruction combiner. This
Bill Wendling [Sun, 30 Nov 2008 13:08:13 +0000 (13:08 +0000)]
Implement (A&((~A)|B)) -> A&B transformation in the instruction combiner. This
takes care of all permutations of this pattern.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60290 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoForgot one remaining call to getSExtValue().
Bill Wendling [Sun, 30 Nov 2008 12:41:09 +0000 (12:41 +0000)]
Forgot one remaining call to getSExtValue().

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60289 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agogetSExtValue() doesn't work for ConstantInts with bitwidth > 64 bits. Use all
Bill Wendling [Sun, 30 Nov 2008 12:38:24 +0000 (12:38 +0000)]
getSExtValue() doesn't work for ConstantInts with bitwidth > 64 bits. Use all
APInt calls instead.

This fixes PR3144.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60288 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoOptimize memmove and memset into the LLVM builtins. Note that these
Eli Friedman [Sun, 30 Nov 2008 08:32:11 +0000 (08:32 +0000)]
Optimize memmove and memset into the LLVM builtins.  Note that these
only show up in code from front-ends besides llvm-gcc, like clang.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60287 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoA couple small cleanups, plus a new potential optimization.
Eli Friedman [Sun, 30 Nov 2008 07:52:27 +0000 (07:52 +0000)]
A couple small cleanups, plus a new potential optimization.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60286 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoMoving potential optimizations out of PR2330 into lib/Target/README.txt.
Eli Friedman [Sun, 30 Nov 2008 07:36:04 +0000 (07:36 +0000)]
Moving potential optimizations out of PR2330 into lib/Target/README.txt.
Hopefully this isn't too much stuff to dump into this file.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60285 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFollowup to r60283: optimize arbitrary width signed divisions as well
Eli Friedman [Sun, 30 Nov 2008 06:35:39 +0000 (06:35 +0000)]
Followup to r60283: optimize arbitrary width signed divisions as well
as unsigned divisions.  Same caveats as before.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60284 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFix for PR2164: allow transforming arbitrary-width unsigned divides into
Eli Friedman [Sun, 30 Nov 2008 06:02:26 +0000 (06:02 +0000)]
Fix for PR2164: allow transforming arbitrary-width unsigned divides into
multiplies.

Some more cleverness would be nice, though. It would be nice if we
could do this transformation on illegal types.  Also, we would
prefer a narrower constant when possible so that we can use a narrower
multiply, which can be cheaper.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60283 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoDon't make TwoToExp signed by default.
Bill Wendling [Sun, 30 Nov 2008 05:29:33 +0000 (05:29 +0000)]
Don't make TwoToExp signed by default.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60279 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFrom Hacker's Delight:
Bill Wendling [Sun, 30 Nov 2008 05:01:05 +0000 (05:01 +0000)]
From Hacker's Delight:

"For signed integers, the determination of overflow of x*y is not so simple. If
x and y have the same sign, then overflow occurs iff xy > 2**31 - 1. If they
have opposite signs, then overflow occurs iff xy < -2**31."

In this case, x == -1.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60278 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoAPIntify a test which is potentially unsafe otherwise, and fix the
Eli Friedman [Sun, 30 Nov 2008 04:59:26 +0000 (04:59 +0000)]
APIntify a test which is potentially unsafe otherwise, and fix the
nearby FIXME.

I'm not sure what the right way to fix the Cell test was; if the
approach I used isn't okay, please let me know.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60277 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoStrengthen check for div inst-combining.
Bill Wendling [Sun, 30 Nov 2008 04:33:53 +0000 (04:33 +0000)]
Strengthen check for div inst-combining.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60276 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoInstcombine was illegally transforming -X/C into X/-C when either X or C
Bill Wendling [Sun, 30 Nov 2008 03:42:12 +0000 (03:42 +0000)]
Instcombine was illegally transforming -X/C into X/-C when either X or C
overflowed on negation. This commit checks to make sure that neithe C nor X
overflows. This requires that the RHS of X (a subtract instruction) be a
constant integer.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60275 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoTwo changes: Make getDependency remove QueryInst for a dirty record's
Chris Lattner [Sun, 30 Nov 2008 02:52:26 +0000 (02:52 +0000)]
Two changes: Make getDependency remove QueryInst for a dirty record's
ReverseLocalDeps when we update it.  This fixes a regression test
failure from my last commit.

Second, for each non-local cached information structure, keep a bit that
indicates whether it is dirty or not.  This saves us a scan over the whole
thing in the common case when it isn't dirty.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60274 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFix a link issue I ran into trying compiling LLVM on MinGW with CMake.
Eli Friedman [Sun, 30 Nov 2008 02:42:05 +0000 (02:42 +0000)]
Fix a link issue I ran into trying compiling LLVM on MinGW with CMake.
Hopefully this doesn't break anyone else's build... it shouldn't unless
the MinGW variable means something other than compiling with MinGW.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60273 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agointroduce a typedef, no functionality change.
Chris Lattner [Sun, 30 Nov 2008 02:30:50 +0000 (02:30 +0000)]
introduce a typedef, no functionality change.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60272 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoChange NonLocalDeps to be a densemap of pointers to densemap
Chris Lattner [Sun, 30 Nov 2008 02:28:25 +0000 (02:28 +0000)]
Change NonLocalDeps to be a densemap of pointers to densemap
instead of containing them by value.  This increases the density
(!) of NonLocalDeps as well as making the reallocation case
faster.  This speeds up gvn on 403.gcc by 2% and makes room for
future improvements.

I'm not super thrilled with having to explicitly manage the new/delete
of the map, but it is necesary for the next change.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60271 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agocalls never depend on allocations.
Chris Lattner [Sun, 30 Nov 2008 01:44:00 +0000 (01:44 +0000)]
calls never depend on allocations.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60268 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFix a fixme by making memdep's handling of allocations more logical.
Chris Lattner [Sun, 30 Nov 2008 01:39:32 +0000 (01:39 +0000)]
Fix a fixme by making memdep's handling of allocations more logical.
If we see that a load depends on the allocation of its memory with no
intervening stores, we now return a 'None' depedency instead of "Normal".
This tweaks GVN to do its optimization with the new result.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60267 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoimplement a fixme by introducing a new getDependencyFromInternal
Chris Lattner [Sun, 30 Nov 2008 01:26:32 +0000 (01:26 +0000)]
implement a fixme by introducing a new getDependencyFromInternal
method that returns its result as a DepResultTy instead of as a
MemDepResult.  This reduces conversion back and forth.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60266 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoMove the getNonLocalDependency method to a more logical place in
Chris Lattner [Sun, 30 Nov 2008 01:18:27 +0000 (01:18 +0000)]
Move the getNonLocalDependency method to a more logical place in
the file, no functionality change.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60265 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoREmove an old fixme, resolve another fixme by adding liberal
Chris Lattner [Sun, 30 Nov 2008 01:17:08 +0000 (01:17 +0000)]
REmove an old fixme, resolve another fixme by adding liberal
comments about what this class does.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60264 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoremove a bit of incorrect code that tried to be tricky about speeding up
Chris Lattner [Sun, 30 Nov 2008 01:09:30 +0000 (01:09 +0000)]
remove a bit of incorrect code that tried to be tricky about speeding up
dependencies.  The basic situation was this: consider if we had:

  store1
  ...
  store2
  ...
  store3

Where memdep thinks that store3 depends on store2 and store2 depends
on store1.  The problem happens when we delete store2: The code in
question was updating dep info for store3 to be store1.  This is a
spiffy optimization, but is not safe at all, because aliasing isn't
transitive.  This bug isn't exposed today with DSE because DSE will only
zap store2 if it is identifical to store 3, and in this case, it is
safe to update it to depend on store1.  However, memcpyopt is not so
fortunate, which is presumably why the "dropInstruction" code used to
exist.

Since this doesn't actually provide a speedup in practice, just rip the
code out.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60263 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agofix indentation. std::pair is "isPod" if the first/second are both isPod.
Chris Lattner [Sun, 30 Nov 2008 00:50:20 +0000 (00:50 +0000)]
fix indentation.  std::pair is "isPod" if the first/second are both isPod.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60262 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoRemove warning about declaration does not declare anything. This class was
Nick Lewycky [Sun, 30 Nov 2008 00:36:34 +0000 (00:36 +0000)]
Remove warning about declaration does not declare anything. This class was
already declared in the other headers.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60261 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoEliminate the dropInstruction method, which is not needed any more.
Chris Lattner [Sat, 29 Nov 2008 23:30:39 +0000 (23:30 +0000)]
Eliminate the dropInstruction method, which is not needed any more.
Fix a subtle iterator invalidation bug I introduced in the last commit.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60258 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoAdd protected visibility to libLTO.
Nick Lewycky [Sat, 29 Nov 2008 22:49:59 +0000 (22:49 +0000)]
Add protected visibility to libLTO.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60257 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoimplement some fixme's: when deleting an instruction with
Chris Lattner [Sat, 29 Nov 2008 22:02:15 +0000 (22:02 +0000)]
implement some fixme's: when deleting an instruction with
an entry in the nonlocal deps map, don't reset entries
referencing that instruction to [dirty, null], instead, set
them to [dirty,next] where next is the instruction after the
deleted one.  Use this information in the non-local deps
code to avoid rescanning entire blocks.

This speeds up GVN slightly by avoiding pointless work.  On
403.gcc this makes GVN 1.5% faster.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60256 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoChange MemDep::getNonLocalDependency to return its results as
Chris Lattner [Sat, 29 Nov 2008 21:33:22 +0000 (21:33 +0000)]
Change MemDep::getNonLocalDependency to return its results as
a smallvector instead of a DenseMap.  This speeds up GVN by 5%
on 403.gcc.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60255 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agomove MemoryDependenceAnalysis::verifyRemoved to the end of the file,
Chris Lattner [Sat, 29 Nov 2008 21:25:10 +0000 (21:25 +0000)]
move MemoryDependenceAnalysis::verifyRemoved to the end of the file,
no functionality/code change.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60254 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoreimplement getNonLocalDependency with a simpler worklist
Chris Lattner [Sat, 29 Nov 2008 21:22:42 +0000 (21:22 +0000)]
reimplement getNonLocalDependency with a simpler worklist
formulation that is faster and doesn't require nonLazyHelper.
Much less code.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60253 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agodon't require GVN to work on dead values, just make the
Chris Lattner [Sat, 29 Nov 2008 21:21:48 +0000 (21:21 +0000)]
don't require GVN to work on dead values, just make the
test return the loaded value.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60252 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFix a thinko that manifested as a crash on clamav last night.
Chris Lattner [Sat, 29 Nov 2008 20:29:04 +0000 (20:29 +0000)]
Fix a thinko that manifested as a crash on clamav last night.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60251 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFix spelling mistake.
Nick Lewycky [Sat, 29 Nov 2008 20:13:25 +0000 (20:13 +0000)]
Fix spelling mistake.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60250 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agotidy up some variable names.
Chris Lattner [Sat, 29 Nov 2008 09:22:14 +0000 (09:22 +0000)]
tidy up some variable names.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60243 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agorename some maps.
Chris Lattner [Sat, 29 Nov 2008 09:20:15 +0000 (09:20 +0000)]
rename some maps.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60242 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agorename some variables.
Chris Lattner [Sat, 29 Nov 2008 09:15:21 +0000 (09:15 +0000)]
rename some variables.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60241 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoeliminate a bunch of code in favor of using AliasAnalysis::getModRefInfo.
Chris Lattner [Sat, 29 Nov 2008 09:09:48 +0000 (09:09 +0000)]
eliminate a bunch of code in favor of using AliasAnalysis::getModRefInfo.
Put a some code back to handle buggy behavior that GVN expects: it wants
loads to depend on each other, and accesses to depend on their allocations.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60240 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoprotect against negative values that would exceed allowed bit width
Torok Edwin [Sat, 29 Nov 2008 08:52:45 +0000 (08:52 +0000)]
protect against negative values that would exceed allowed bit width

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60239 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agosimplify some code and rename some variables. Reduce nesting.
Chris Lattner [Sat, 29 Nov 2008 08:51:16 +0000 (08:51 +0000)]
simplify some code and rename some variables.  Reduce nesting.
Use getTypeStoreSize instead of ABITypeSize for in-memory size
in a couple places.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60238 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoapparently GCC doesn't believe that I understand C
Chris Lattner [Sat, 29 Nov 2008 08:36:39 +0000 (08:36 +0000)]
apparently GCC doesn't believe that I understand C
precedence rules.  Pacify it.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60237 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoTypo fix.
Duncan Sands [Sat, 29 Nov 2008 08:03:35 +0000 (08:03 +0000)]
Typo fix.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60236 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoSplit getDependency into getDependency and getDependencyFrom, the
Chris Lattner [Sat, 29 Nov 2008 03:47:00 +0000 (03:47 +0000)]
Split getDependency into getDependency and getDependencyFrom, the
former does caching, the later doesn't.  This dramatically simplifies
the logic in getDependency and getDependencyFrom.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60234 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoTemporarily revert r60195. It's causing an optimized bootstrap of llvm-gcc to fail.
Bill Wendling [Sat, 29 Nov 2008 03:43:04 +0000 (03:43 +0000)]
Temporarily revert r60195. It's causing an optimized bootstrap of llvm-gcc to fail.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60233 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoNow that DepType is private, we can start cleaning up some of its uses:
Chris Lattner [Sat, 29 Nov 2008 03:22:12 +0000 (03:22 +0000)]
Now that DepType is private, we can start cleaning up some of its uses:
Document the Dirty value more precisely, use it for the uninitialized
DepResultTy value.  Change reverse mappings to be from an instruction*
instead of DepResultTy, and stop tracking other forms.  This makes it more
clear that we only care about the instruction cases.

Eliminate a DepResultTy,bool pair by using Dirty in the local case as well,
shrinking the map and simplifying the code.

This speeds up GVN by ~3% on 403.gcc.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60232 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoIntroduce and use a new MemDepResult class to hold the results of a memdep
Chris Lattner [Sat, 29 Nov 2008 02:29:27 +0000 (02:29 +0000)]
Introduce and use a new MemDepResult class to hold the results of a memdep
query.  This makes it crystal clear what cases can escape from MemDep that
the clients have to handle.  This also gives the clients a nice simplified
interface to it that is easy to poke at.

This patch also makes DepResultTy and MemoryDependenceAnalysis::DepType
private, yay.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60231 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoReimplement the internal abstraction used by MemDep in terms
Chris Lattner [Sat, 29 Nov 2008 01:43:36 +0000 (01:43 +0000)]
Reimplement the internal abstraction used by MemDep in terms
of a pointer/int pair instead of a manually bitmangled pointer.
This forces clients to think a little more about checking the
appropriate pieces and will be useful for internal
implementation improvements later.

I'm not particularly happy with this.  After going through this
I don't think that the clients of memdep should be exposed to
the internal type at all.  I'll fix this in a subsequent commit.

This has no functionality change.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60230 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFix sentinels to use correctly 'aligned' pointers.
Chris Lattner [Sat, 29 Nov 2008 01:36:16 +0000 (01:36 +0000)]
Fix sentinels to use correctly 'aligned' pointers.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60229 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFix spello, add DenseMapInfo specialization for PointerIntPair.
Chris Lattner [Sat, 29 Nov 2008 01:18:05 +0000 (01:18 +0000)]
Fix spello, add DenseMapInfo specialization for PointerIntPair.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60228 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agofix comment typo
Chris Lattner [Fri, 28 Nov 2008 23:57:26 +0000 (23:57 +0000)]
fix comment typo

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60227 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agofix a bug.
Chris Lattner [Fri, 28 Nov 2008 23:36:15 +0000 (23:36 +0000)]
fix a bug.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60225 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoadd a generic "bitmangled pointer" class, which allows a parameterized
Chris Lattner [Fri, 28 Nov 2008 23:31:44 +0000 (23:31 +0000)]
add a generic "bitmangled pointer" class, which allows a parameterized
pointer and integer type to be used.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60224 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFix PR3141 by ensuring that MemoryDependenceAnalysis::removeInstruction
Chris Lattner [Fri, 28 Nov 2008 22:51:08 +0000 (22:51 +0000)]
Fix PR3141 by ensuring that MemoryDependenceAnalysis::removeInstruction
properly updates the reverse dependency map when it installs updated
dependencies for instructions that depend on the removed instruction.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60222 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agodon't revisit instructions off the beginning of the block.
Chris Lattner [Fri, 28 Nov 2008 22:50:08 +0000 (22:50 +0000)]
don't revisit instructions off the beginning of the block.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60221 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agocomment cleanups.
Chris Lattner [Fri, 28 Nov 2008 22:41:36 +0000 (22:41 +0000)]
comment cleanups.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60220 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agomore cleanups for MemoryDependenceAnalysis::removeInstruction,
Chris Lattner [Fri, 28 Nov 2008 22:28:27 +0000 (22:28 +0000)]
more cleanups for MemoryDependenceAnalysis::removeInstruction,
no functionality change.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60219 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agorandom cleanups, no functionality change.
Chris Lattner [Fri, 28 Nov 2008 22:04:47 +0000 (22:04 +0000)]
random cleanups, no functionality change.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60218 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoforward declare CallSite instead of #includ'ing it.
Chris Lattner [Fri, 28 Nov 2008 21:47:19 +0000 (21:47 +0000)]
forward declare CallSite instead of #includ'ing it.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60217 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoRun verifyRemoved from removeInstruction when -debug is specified.
Chris Lattner [Fri, 28 Nov 2008 21:45:17 +0000 (21:45 +0000)]
Run verifyRemoved from removeInstruction when -debug is specified.
This shows the root problem behind PR3141.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60216 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agorename "ping" to "verifyRemoved". I don't know why 'ping' what chosen,
Chris Lattner [Fri, 28 Nov 2008 21:42:09 +0000 (21:42 +0000)]
rename "ping" to "verifyRemoved".  I don't know why 'ping' what chosen,
but it doesn't make any sense at all.

Also make the method const, private, and fit in 80 cols while we're at it.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60215 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agocomment and indentation improvements.
Chris Lattner [Fri, 28 Nov 2008 21:36:43 +0000 (21:36 +0000)]
comment and indentation improvements.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60214 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agosimplify some code, remove escaped newline.
Chris Lattner [Fri, 28 Nov 2008 21:29:52 +0000 (21:29 +0000)]
simplify some code, remove escaped newline.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60213 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoremove mysterious escaped newlines.
Chris Lattner [Fri, 28 Nov 2008 21:16:44 +0000 (21:16 +0000)]
remove mysterious escaped newlines.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60211 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agodon't call MergeBasicBlockIntoOnlyPred on a block whose only
Chris Lattner [Fri, 28 Nov 2008 19:54:49 +0000 (19:54 +0000)]
don't call MergeBasicBlockIntoOnlyPred on a block whose only
predecessor is itself.  This doesn't make sense, and this is
a dead infinite loop anyway.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60210 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoAdd include files needed when building with
Duncan Sands [Fri, 28 Nov 2008 10:20:03 +0000 (10:20 +0000)]
Add include files needed when building with
gcc 4.4 (due to use of sprintf).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60209 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoFix build with gcc-4.4: it doesn't like PICStyle
Duncan Sands [Fri, 28 Nov 2008 09:29:37 +0000 (09:29 +0000)]
Fix build with gcc-4.4: it doesn't like PICStyle
being both a namespace and a variable name.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60208 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agorewrite RecursivelyDeleteTriviallyDeadInstructions to use a more efficient
Chris Lattner [Fri, 28 Nov 2008 01:20:46 +0000 (01:20 +0000)]
rewrite RecursivelyDeleteTriviallyDeadInstructions to use a more efficient
formulation that doesn't require set lookups or scanning a set.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60203 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoremove some weirdness that came from the LSR code that has
Chris Lattner [Fri, 28 Nov 2008 00:58:15 +0000 (00:58 +0000)]
remove some weirdness that came from the LSR code that has
nothing to do with dead instruction elimination.  No tests in
dejagnu depend on this, so I don't know what it was needed for.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60202 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agorewrite a big chunk of how DSE does recursive dead operand
Chris Lattner [Fri, 28 Nov 2008 00:27:14 +0000 (00:27 +0000)]
rewrite a big chunk of how DSE does recursive dead operand
elimination to use more modern infrastructure.  Also do a bunch
of small cleanups.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60201 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoScrap some boilerplate.
Mikhail Glushenkov [Fri, 28 Nov 2008 00:14:11 +0000 (00:14 +0000)]
Scrap some boilerplate.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60200 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoSupport multiple compilation graph definitions. Not terribly useful, but makes the...
Mikhail Glushenkov [Fri, 28 Nov 2008 00:13:47 +0000 (00:13 +0000)]
Support multiple compilation graph definitions. Not terribly useful, but makes the code more generic.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60199 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoAdd 'hidden' and 'really_hidden' option properties.
Mikhail Glushenkov [Fri, 28 Nov 2008 00:13:25 +0000 (00:13 +0000)]
Add 'hidden' and 'really_hidden' option properties.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60198 91177308-0d34-0410-b5e6-96231b3b80d8

15 years agoDocumentation: clarify what is meant by 'multiple edges'.
Mikhail Glushenkov [Fri, 28 Nov 2008 00:12:09 +0000 (00:12 +0000)]
Documentation: clarify what is meant by 'multiple edges'.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60197 91177308-0d34-0410-b5e6-96231b3b80d8