aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Use std::set instead of std::priority_queue for the RegReductionPriorityQueue. Roman Levenstein2008-04-291-44/+29
| | | | | | | | | | | | | | | | This removes the existing bottleneck related to the removal of elements from the middle of the queue. Also fixes a subtle bug in ScheduleDAGRRList::CapturePred: It was updating the state of the SUnit before removing it. As a result, the comparison operators were working incorrectly and this SUnit could not be removed from the queue properly. Reviewed by Evan and Dan. Approved by Dan. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50412 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix the new scheduler assertion checks to work whenDan Gohman2008-04-151-2/+10
| | | | | | | | the scheduler has inserted no-ops. This fixes the 2006-07-03-schedulers.ll regression on ppc32. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49747 91177308-0d34-0410-b5e6-96231b3b80d8
* Treat EntryToken nodes as "passive" so that they aren't added to theDan Gohman2008-04-151-27/+45
| | | | | | | | | | | | | | | | | | ScheduleDAG; they don't correspond to any actual instructions so they don't need to be scheduled. This fixes a bug where the EntryToken was being scheduled multiple times in some cases, though it ended up not causing any trouble because EntryToken doesn't expand into anything. With this fixed the schedulers reliably schedule the expected number of units, so we can check this with an assertion. This requires a tweak to test/CodeGen/X86/loop-hoist.ll because it ends up getting scheduled differently in a trivial way, though it was enough to fool the prcontext+grep that the test does. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49701 91177308-0d34-0410-b5e6-96231b3b80d8
* Cosmetic changes.Evan Cheng2008-03-291-24/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48947 91177308-0d34-0410-b5e6-96231b3b80d8
* ifdef out a dead function. Should this be removed?Chris Lattner2008-03-281-0/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48916 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix spelling. Thanks, Duncan! :-)Roman Levenstein2008-03-271-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48873 91177308-0d34-0410-b5e6-96231b3b80d8
* Speed-up the SumOfUnscheduledPredsOfSuccs by introducing a new functionRoman Levenstein2008-03-271-2/+25
| | | | | | | | | | | | called LimitedSumOfUnscheduledPredsOfSuccs. It terminates the computation after a given treshold is reached. This new function is always faster, but brings real wins only on bigger test-cases. The old function SumOfUnscheduledPredsOfSuccs is left in-place for now and therefore a warning about an unused static function is produced. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48872 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixed some spelling errors. Thanks, Duncan!Roman Levenstein2008-03-261-52/+54
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48819 91177308-0d34-0410-b5e6-96231b3b80d8
* Some improvements related to the computation of isReachable.Roman Levenstein2008-03-261-54/+315
| | | | | | | | | | | | | | | | | | | | | | | | | This fixes Bugzilla #1835 (http://llvm.org/bugs/show_bug.cgi?id=1835). This patched is reviewed by Tanya and Dan. Dan tested and approved it. The reason for the bad performance of the old algorithm is that it is very naive and scans every time all nodes of the DAG in the worst case. This patch introduces a new algorithm based on the paper "Online algorithms for maintaining the topological order of a directed acyclic graph" by David J.Pearce and Paul H.J.Kelly. This is the MNR algorithm. It has a linear time worst-case and performs much better in most situations. The paper can be found here: http://fano.ics.uci.edu/cites/Document/Online-algorithms-for-maintaining-the-topological-order-of-a-directed-acyclic-graph.html The main idea of the new algorithm is to compute the topological ordering of the SNodes in the DAG and to maintain it even after DAG modifications. The topological ordering allows for very fast node reachability checks. Tests on very big input files with tens of thousands of instructions in a BB indicate huge speed-ups (up to 10x compilation time improvement) compared to the old version. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48817 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix typos.Dan Gohman2008-03-251-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48779 91177308-0d34-0410-b5e6-96231b3b80d8
* When the register allocator runs out of registers, spill a physical register ↵Evan Cheng2008-03-111-1/+1
| | | | | | around the def's and use's of the interval being allocated to make it possible for the interval to target a register and spill it right away and restore a register for uses. This likely generates terrible code but is before than aborting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48218 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename isOperand() to isOperandOf() (and other similar methods). It always ↵Evan Cheng2008-03-041-1/+1
| | | | | | confuses me. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47872 91177308-0d34-0410-b5e6-96231b3b80d8
* Refactor / clean up code; remove td list scheduler special tie breaker (no ↵Evan Cheng2008-03-011-78/+59
| | | | | | real benefit). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47779 91177308-0d34-0410-b5e6-96231b3b80d8
* Update gcc 4.3 warnings fix patch with recent head changesAnton Korobeynikov2008-02-201-6/+13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47368 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert 47177, which was incorrect.Dan Gohman2008-02-161-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47196 91177308-0d34-0410-b5e6-96231b3b80d8
* Skip over the defs and start at the uses when looking for operandsDan Gohman2008-02-151-1/+1
| | | | | | | with the TIED_TO attribute. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47177 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the TargetInstrDescr to determine the number of operandsDan Gohman2008-02-151-3/+3
| | | | | | | | that should be checked for the TIED_TO attribute instead of using CountOperands. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47176 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename MRegisterInfo to TargetRegisterInfo.Dan Gohman2008-02-101-15/+15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46930 91177308-0d34-0410-b5e6-96231b3b80d8
* Use empty() instead of comparing size() with zero.Dan Gohman2008-01-291-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46514 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a typo in a comment.Dan Gohman2008-01-291-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46513 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a typo in a comment.Dan Gohman2008-01-291-1/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46508 91177308-0d34-0410-b5e6-96231b3b80d8
* Special copy SUnit's do not have SDNode's.Evan Cheng2008-01-091-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45787 91177308-0d34-0410-b5e6-96231b3b80d8
* rename TargetInstrDescriptor -> TargetInstrDesc.Chris Lattner2008-01-071-6/+6
| | | | | | | | Make MachineInstr::getDesc return a reference instead of a pointer, since it can never be null. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45695 91177308-0d34-0410-b5e6-96231b3b80d8
* simplify some code.Chris Lattner2008-01-071-10/+13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45693 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename all the M_* flags to be namespace qualified enums, and switch Chris Lattner2008-01-071-1/+1
| | | | | | | | | all clients over to using predicates instead of these flags directly. These are now private values which are only to be used to statically initialize the tables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45692 91177308-0d34-0410-b5e6-96231b3b80d8
* Move a bunch more accessors from TargetInstrInfo to TargetInstrDescriptorChris Lattner2008-01-071-9/+10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45680 91177308-0d34-0410-b5e6-96231b3b80d8
* Update CodeGen for MRegisterInfo --> TargetInstrInfo changes.Owen Anderson2008-01-071-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45673 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename SSARegMap -> MachineRegisterInfo in keeping with the idea Chris Lattner2007-12-311-1/+0
| | | | | | | | | | | | | | | | that "machine" classes are used to represent the current state of the code being compiled. Given this expanded name, we can start moving other stuff into it. For now, move the UsedPhysRegs and LiveIn/LoveOuts vectors from MachineFunction into it. Update all the clients to match. This also reduces some needless #includes, such as MachineModuleInfo from MachineFunction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45467 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove attribution from file headers, per discussion on llvmdev.Chris Lattner2007-12-291-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45418 91177308-0d34-0410-b5e6-96231b3b80d8
* More accurate checks for two-address constraints.Evan Cheng2007-12-201-8/+40
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45259 91177308-0d34-0410-b5e6-96231b3b80d8
* Bring back a burr scheduling heuristic that's still needed.Evan Cheng2007-12-201-5/+34
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45252 91177308-0d34-0410-b5e6-96231b3b80d8
* FIX for PR1799: When a load is unfolded from an instruction, check if it is ↵Evan Cheng2007-12-181-26/+36
| | | | | | a new node. If not, do not create a new SUnit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45157 91177308-0d34-0410-b5e6-96231b3b80d8
* Bug fix. Passive nodes are not in SUnitMap.Evan Cheng2007-11-091-3/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43922 91177308-0d34-0410-b5e6-96231b3b80d8
* Add pseudo dependency to force two-address instruction to be scheduled afterEvan Cheng2007-11-061-2/+5
| | | | | | | | other uses. There was a overly restricted check that prevented some obvious cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43762 91177308-0d34-0410-b5e6-96231b3b80d8
* One mundane change: Change ReplaceAllUsesOfValueWith to *optionally* Chris Lattner2007-10-151-4/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | take a deleted nodes vector, instead of requiring it. One more significant change: Implement the start of a legalizer that just works on types. This legalizer is designed to run before the operation legalizer and ensure just that the input dag is transformed into an output dag whose operand and result types are all legal, even if the operations on those types are not. This design/impl has the following advantages: 1. When finished, this will *significantly* reduce the amount of code in LegalizeDAG.cpp. It will remove all the code related to promotion and expansion as well as splitting and scalarizing vectors. 2. The new code is very simple, idiomatic, and modular: unlike LegalizeDAG.cpp, it has no 3000 line long functions. :) 3. The implementation is completely iterative instead of recursive, good for hacking on large dags without blowing out your stack. 4. The implementation updates nodes in place when possible instead of deallocating and reallocating the entire graph that points to some mutated node. 5. The code nicely separates out handling of operations with invalid results from operations with invalid operands, making some cases simpler and easier to understand. 6. The new -debug-only=legalize-types option is very very handy :), allowing you to easily understand what legalize types is doing. This is not yet done. Until the ifdef added to SelectionDAGISel.cpp is enabled, this does nothing. However, this code is sufficient to legalize all of the code in 186.crafty, olden and freebench on an x86 machine. The biggest issues are: 1. Vectors aren't implemented at all yet 2. SoftFP is a mess, I need to talk to Evan about it. 3. No lowering to libcalls is implemented yet. 4. Various operations are missing etc. 5. There are FIXME's for stuff I hax0r'd out, like softfp. Hey, at least it is a step in the right direction :). If you'd like to help, just enable the #ifdef in SelectionDAGISel.cpp and compile code with it. If this explodes it will tell you what needs to be implemented. Help is certainly appreciated. Once this goes in, we can do three things: 1. Add a new pass of dag combine between the "type legalizer" and "operation legalizer" passes. This will let us catch some long-standing isel issues that we miss because operation legalization often obfuscates the dag with target-specific nodes. 2. We can rip out all of the type legalization code from LegalizeDAG.cpp, making it much smaller and simpler. When that happens we can then reimplement the core functionality left in it in a much more efficient and non-recursive way. 3. Once the whole legalizer is non-recursive, we can implement whole-function selectiondags maybe... git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42981 91177308-0d34-0410-b5e6-96231b3b80d8
* EXTRACT_SUBREG coalescing support. The coalescer now treats EXTRACT_SUBREG likeEvan Cheng2007-10-121-0/+13
| | | | | | | | | | (almost) a register copy. However, it always coalesced to the register of the RHS (the super-register). All uses of the result of a EXTRACT_SUBREG are sub- register uses which adds subtle complications to load folding, spiller rewrite, etc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42899 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a typo in a comment.Dan Gohman2007-10-051-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42635 91177308-0d34-0410-b5e6-96231b3b80d8
* Chain producing nodes cannot be moved, not chain reading nodes.Evan Cheng2007-10-051-5/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42627 91177308-0d34-0410-b5e6-96231b3b80d8
* Oops. Didn't mean to leave this in.Evan Cheng2007-10-051-1/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42626 91177308-0d34-0410-b5e6-96231b3b80d8
* If a node that defines a physical register that is expensive to copy. TheEvan Cheng2007-10-051-19/+132
| | | | | | | | | | scheduler will try a number of tricks in order to avoid generating the copies. This may not be possible in case the node produces a chain value that prevent movement. Try unfolding the load from the node before to allow it to be moved / cloned. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42625 91177308-0d34-0410-b5e6-96231b3b80d8
* If two instructions are both two-address code, favors (schedule closer toEvan Cheng2007-09-281-3/+20
| | | | | | | | terminator) the one that has a CopyToReg use. This fixes 2006-05-11-InstrSched.ll with -new-cc-modeling-scheme. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42453 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove a poor scheduling heuristic.Evan Cheng2007-09-281-34/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42443 91177308-0d34-0410-b5e6-96231b3b80d8
* Trim some unneeded fields.Evan Cheng2007-09-281-17/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42442 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid inserting a live register more than once.Evan Cheng2007-09-271-8/+18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42410 91177308-0d34-0410-b5e6-96231b3b80d8
* Boogs.Evan Cheng2007-09-271-10/+10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42388 91177308-0d34-0410-b5e6-96231b3b80d8
* Be smarter about which node to force schedule. Reduce # of duplications + ↵Evan Cheng2007-09-271-84/+120
| | | | | | copies; Added statistics. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42387 91177308-0d34-0410-b5e6-96231b3b80d8
* Backtracking only when it won't create a cycle.Evan Cheng2007-09-271-23/+35
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42384 91177308-0d34-0410-b5e6-96231b3b80d8
* - Move getPhysicalRegisterRegClass() from ScheduleDAG to MRegisterInfo.Evan Cheng2007-09-261-65/+145
| | | | | | | | - Added ability to emit cross class register copies to the BBRU scheduler. - More aggressive backtracking. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42375 91177308-0d34-0410-b5e6-96231b3b80d8
* Added major new capabilities to scheduler (only BURR for now) to support ↵Evan Cheng2007-09-251-71/+398
| | | | | | physical register dependency. The BURR scheduler can now backtrace and duplicate instructions in order to avoid "expensive / impossible to copy" values (e.g. status flag EFLAGS for x86) from being clobbered. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42284 91177308-0d34-0410-b5e6-96231b3b80d8
* Use struct SDep instead of std::pair for SUnit pred and succ lists. First stepEvan Cheng2007-09-191-22/+22
| | | | | | | in tracking physical register output dependencies. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42125 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-06-03 02:12:13 +0000