Get Gentoo!
gentoo.org sites
gentoo.org Wiki Bugs Forums Packages
Planet Archives Sources
Infra Status
aboutsummaryrefslogtreecommitdiff
path: root/cse.c
Commit message (Collapse)AuthorAgeFilesLines
* cse: Size insn_hash_table more realistically, speeding up CSE significantlyJosh Triplett2007-07-291-1/+1
| | | | | | | | | Profiling showed that Sparse spent much of its time doing CSE, which involved traversing every bucket of insn_hash_table repeatedly. insn_hash_table had 64K buckets, but never more than a few dozen entries. Shrink insn_hash_table to 256 entries. This makes Sparse 2-4 times faster for me. Signed-off-by: Josh Triplett <josh@freedesktop.org>
* Fix typos in commentsJosh Triplett2007-03-091-4/+4
| | | | Signed-off-by: Josh Triplett <josh@freedesktop.org>
* Do stupid and crappy CSE on casts.Linus Torvalds2005-09-241-0/+25
| | | | | | | | | | | | It's better than nothing, but I need to re-do cast linearization some day. Right now we squirrell away the whole original type, but the fact is, we only need to save away a few bits of "type of cast". We need to know if it's sign-extending, and whether the source or destination are floating point values. And the source size, of course. But we don't really need to know the detailed original type. Oh, well. This makes at least trivial things look much better.
* [PATCH] using 0 as NULL in sparseChristopher Li2005-04-071-3/+3
| | | | | | | | | | This trivial patch remove the warning when I try to compile sparse in with sparse. Another warning I did not fix is: ../pre-process.c:554:18: warning: bad constant expression The offending line is: struct arg args[nargs];
* Use the new per-instruction position information for betterLinus Torvalds2005-04-071-1/+1
| | | | error reporting.
* Split the binops where signedness matters into unsigned and signed.Linus Torvalds2005-04-071-6/+10
| | | | | | | This is OP_MUL/OP_DIV/OP_MOD/OP_SHR. We actually do the constant simplifications still wrong, but now the information is all there.
* Split OP_SETVAL into OP_SETVAL (fp expressions and labels) and OP_SYMADDRLinus Torvalds2005-04-071-2/+8
| | | | | | | (symbol addresses). They are pretty different. Symbol addresses have special meaning during various phases, from symbol simplification to CSE.
* Remove phi source merging.Linus Torvalds2005-04-071-17/+1
| | | | | It looked good on paper. Not so good when actually trying to generate code.
* Expose "show_instruction()" for debugging.Linus Torvalds2005-04-071-2/+0
| | | | We already did this, we just didn't have a visible prototype.
* Be more aggressive on PHI-node CSE.Linus Torvalds2005-04-071-3/+10
| | | | | | | | | | | | We don't care _where_ a PHI-node is, since the real location is at the phi sources. So unlike other instructions, we do not bother with any dominance analysis - we can just combine them blindly across basic block borders. It might make sense to totally disconnect the PHI nodes from the flow graph to make this lack of positional information even more explicit. That might also allow us to combine more basic blocks.
* Make OP_PHISOURCE track the OP_PHI instructions that it defines.Linus Torvalds2005-04-071-4/+2
| | | | | | | | This allows us to always see which pseudos are nonlocally affected by the phi source. We can only do this after the instruction flow is fixed, together with the OP_DEATHNOTE phase.
* Yet another missed "entry" change point.Linus Torvalds2005-04-071-1/+1
| | | | | Umm. The compiler even warned about it, I don't see how I could miss it. I'm a maroon.
* Remove OP_SETCC, make OP_SEL bigger instead.Linus Torvalds2005-04-071-6/+10
| | | | | | | This was originally done so that "struct instruction" would be smaller, but it has since grown anyway (for the memops), so splitting OP_SEL into two instructions no longer makes sense, and makes it harder on CSE.
* Don't try to share parenthood fn between phi node removal and Linus Torvalds2005-04-071-1/+15
| | | | | | | | regular CSE. The CSE case is totally different: since both children use the same pseudos, there can be no question that a common parent wouldn't have that pseudo live.
* Start using instruction sizes properly.Linus Torvalds2005-04-071-1/+3
| | | | | | | | | | We should drop symbol types by now, and base things on just raw sizes. Anything else just doesn't work from a CSE standpoint. Some things may care about actual types later, notably the type- based alias analysis. Those types still exist in the cast nodes. Also, make the printout be more readable.
* Oops. Don't try to CSE OP_SEL, at least not until we learn toLinus Torvalds2005-04-071-2/+2
| | | | CSE it together with the OP_SETCC that goes with it ;)
* Do CSE over children with trivially common parents.Linus Torvalds2005-04-071-1/+21
| | | | Hey, it's simple, and it happens.
* Allow CSE to run after bb packing. Linus Torvalds2005-04-071-1/+5
| | | | | | ...but we can't merge phi-sources after packing. Or rather, we could, but we'll have to be more careful about not re-ordering them, which we aren't. Sort it out later.
* Add "memop" simplification phase.Linus Torvalds2005-04-071-1/+2
| | | | | | | | | | | It's a bit more simple-minded than the symbol simplification, and it can be more costly. So we start off with the (cheap) symbol simplification algorithm, and then use this new more generic phase later. This allows us to remove extra loads (and, in theory, stores, but the dead store elimination is so simple-minded right now that it's effectively useless).
* Be more careful about insn->bb pointers.Linus Torvalds2005-04-071-0/+1
| | | | | | | Make sure to clear them when turning operations into NOP's. And when doing OP_LOAD->OP_PHI conversion, just re-use the target pseudo, which means that we don't need to unnecessarily move all the uses over.
* Make the CSE "repeat" logic be more fine-grained than justLinus Torvalds2005-04-071-6/+8
| | | | | | | | repeating CSE itself. In particular, some symbol address simplifications imply that we should repeat symbol simplification, since things may have improved.
* Move instruction simplification to new file "simplify.c".Linus Torvalds2005-04-071-193/+18
| | | | | | | | | | Also, allow marking a pseudo unused by setting it to VOID, which just disables further renaming of that use. This is needed to make phi-source instructions (that can be shared among multiple phi-nodes thanks to CSE) be collectable. We used to just mark the phi source dead, but that was wrong, since _another_ phi node might be using it.
* Another assert - verify bb validity.Linus Torvalds2005-04-071-2/+2
|
* Don't change instruction pseudo's when nopping them out.Linus Torvalds2005-04-071-1/+0
| | | | | It may be a nice readability thing, but with the usage lists we really mustn't change a location that may be on a list.
* Damn. We can't actually sort the phi-node list of phi's nowLinus Torvalds2005-04-071-21/+4
| | | | | | | | | | that we keep track of usage notes. The usage trackign tracks the address of the phi pseudo, so sorting the list would need to update that too. This sucks, because it means we can't turn the phi-nodes into canonical format, and thus not CSE phi-nodes as effectively.
* Now that phi sources are just instructions, we can CSE them.Linus Torvalds2005-04-071-0/+12
| | | | | | | They's _slightly_ special in that they depend on their bb, so we can only combine them within one basic block, but that's easily handled by making the bb be part of the hashing and comparison.
* Clear phi list when killing a phi-node instructionLinus Torvalds2005-04-071-1/+3
|
* Oops. Clean up some left-overs from phi removal.Linus Torvalds2005-04-071-8/+10
| | | | | The "half-way" point was making the phi be an instruction, and some of that half-way stuff remained.
* Remove "struct phi", replace with instruction that generates a pseudo.Linus Torvalds2005-04-071-24/+27
| | | | | | | | | | | The instruction contains everything "struct phi" had, namely source bb and pseudo. And generating a new pseudo means that we not only have the pointer to the instruction that defines the phi-node (in pseudo->def), we also end up with automatic phi-node usage tracking (pseudo->users). The changes may look large, but almost all of this is just direct search-and-replace of the old phi-node usage.
* Do if-conversion.Linus Torvalds2005-04-071-0/+101
| | | | | | | | | We can turn trivial phi-nodes into OP_SEL instructions instead, and generally improve code flow. This doesn't remove the empty blocks this results in yet, so it's not quite as dramatic as it could be, but it does the hard work. Empty block removal is trivial.
* Re-do CSE if we did a phi-node simplification.Linus Torvalds2005-04-071-12/+11
|
* We need to pack the phi-list even if we simplify the phiLinus Torvalds2005-04-071-2/+3
| | | | instruction.
* Make phi-node normalization (part of CSE) do trivial simplification.Linus Torvalds2005-04-071-2/+17
|
* Oops. Don't try to CSE the dead instructions.Linus Torvalds2005-04-071-0/+2
|
* Kill trivially dead instructionsLinus Torvalds2005-04-071-0/+55
| | | | That is - simple instructions with no users.
* Make the "cse nop" a bit more informativeLinus Torvalds2005-04-071-0/+1
| | | | Show the source that the thing was replaced with.
* Make CSE convert instructions to OP_NOPLinus Torvalds2005-04-071-2/+2
| | | | | Instead of using the "convert_load_insn()" that converts them to OP_LNOP's, which ends up confusing instruction printout horribly.
* Add simple-stupid dominance testing for CSE.Linus Torvalds2005-04-071-2/+32
| | | | | | | | This makes us able to CSE stuff where one subexpression directly dominates another. But we still don't do any fancy code motion in the non- dominance case.
* Pack the phi-list after removing duplicates.Linus Torvalds2005-04-071-0/+3
|
* Add initial CSE passLinus Torvalds2005-04-071-0/+291
It ain't very smart yet, but give it time. In particular, right now it gathers information for the whole function, but it only does the actual replacement if the instructions are in the same basic block.