summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Factor out the code for verifying the work of the scheduler,Dan Gohman2008-11-201-63/+2
| | | | | | | extend it a bit, and make use of it in all schedulers, to ensure consistent checking. llvm-svn: 59689
* Experimental post-pass scheduling support. Post-pass schedulingDan Gohman2008-11-191-3/+3
| | | | | | | | | | | | | | | | | is currently off by default, and can be enabled with -disable-post-RA-scheduler=false. This doesn't have a significant impact on most code yet because it doesn't yet do anything to address anti-dependencies and it doesn't attempt to disambiguate memory references. Also, several popular targets don't have pipeline descriptions yet. The majority of the changes here are splitting the SelectionDAG-specific code out of ScheduleDAG, so that ScheduleDAG can be moved to libLLVMCodeGen.a. The interface between ScheduleDAG-using code and the rest of the scheduling code is somewhat rough and will evolve. llvm-svn: 59676
* Rearrange code to reduce the nesting level. No functionality change.Dan Gohman2008-11-191-36/+36
| | | | llvm-svn: 59580
* Tidy up ScheduleNodeBottomUp methods, and make them moreDan Gohman2008-11-181-7/+5
| | | | | | consistent with ScheduleNodeTopDown methods. llvm-svn: 59550
* Change SUnit's dump method to take a ScheduleDAG* instead ofDan Gohman2008-11-181-10/+10
| | | | | | a SelectionDAG*. llvm-svn: 59488
* Avoid using a loop in ReleasePred and ReleaseSucc methods to compute theDan Gohman2008-11-181-22/+34
| | | | | | | | | | | | | new CycleBound value. Instead, just update CycleBound on each call. Also, make ReleasePred and ReleaseSucc methods more consistent accross the various schedulers. This also happens to make ScheduleDAGRRList's CycleBound computation somewhat more interesting, though it still doesn't have any noticeable effect, because no current targets that use the register-pressure reduction scheduler provide pipeline models. llvm-svn: 59475
* Eliminate some trivial differences between the ScheduleNodeTopDownDan Gohman2008-11-171-3/+4
| | | | | | functions in these two schedulers. llvm-svn: 59465
* Remove the FlaggedNodes member from SUnit. Instead of requiring each SUnitDan Gohman2008-11-131-5/+4
| | | | | | | | | | to carry a SmallVector of flagged nodes, just calculate the flagged nodes dynamically when they are needed. The local-liveness change is due to a trivial scheduling change where the scheduler arbitrary decision differently. llvm-svn: 59273
* Make the Node member of SUnit private, and add accessors.Dan Gohman2008-11-131-29/+29
| | | | llvm-svn: 59264
* Change ScheduleDAG's DAG member from a reference to a pointer, to prepareDan Gohman2008-11-131-19/+19
| | | | | | for the possibility of scheduling without a SelectionDAG being present. llvm-svn: 59263
* In ScheduleDAGRRList::CopyAndMoveSuccessors, create the SUnit for the loadDan Gohman2008-11-111-17/+17
| | | | | | | | | before creating the SUnit for the operation that it was unfolded from. This allows each SUnit to have all of its predecessor SUnits available at the time it is created. I don't know yet if this will be absolutely required, but it is a little tidier to do it this way. llvm-svn: 59083
* Change the scheduler accessor methods to accept an explicit TargetMachineDan Gohman2008-11-111-5/+7
| | | | | | | argument instead of taking the SelectionDAG's TargetMachine. This is needed for some upcoming scheduler changes. llvm-svn: 59055
* Remove some unused virtual function bodies.Dan Gohman2008-10-311-7/+5
| | | | llvm-svn: 58524
* Fix command-line option printing to print two spaces where needed,Dan Gohman2008-10-141-2/+2
| | | | | | | | | instead of requiring all "short description" strings to begin with two spaces. This makes these strings less mysterious, and it fixes some cases where short description strings mistakenly did not begin with two spaces. llvm-svn: 57521
* Replace the LiveRegs SmallSet with a simple counter that keepsDan Gohman2008-09-231-13/+16
| | | | | | | track of the number of live registers, which is all the set was being used for. llvm-svn: 56498
* Don't worry about clobbering physical register defs that aren't used.Dan Gohman2008-09-171-0/+2
| | | | llvm-svn: 56281
* erect abstraction boundaries for accessing SDValue members, rename Val -> ↵Gabor Greif2008-08-281-6/+6
| | | | | | Node to reflect semantics llvm-svn: 55504
* Optimize ScheduleDAGRRList's topological sort to use one pass insteadDan Gohman2008-08-271-19/+8
| | | | | | | | of two, and to not need a scratch std::vector. Also, compute the ordering immediately in the result array, instead of in another scratch std::vector that is copied to the result array. llvm-svn: 55421
* disallow direct access to SDValue::ResNo, provide a getter insteadGabor Greif2008-08-261-1/+1
| | | | llvm-svn: 55394
* Correct the filename in the top-of-file comment.Dan Gohman2008-08-121-1/+1
| | | | llvm-svn: 54688
* Fix several const-correctness issues, resolving some -Wcast-qual warnings.Dan Gohman2008-08-051-11/+11
| | | | llvm-svn: 54349
* Rename SDOperand to SDValue.Dan Gohman2008-07-271-4/+4
| | | | llvm-svn: 54128
* Add a new function, ReplaceAllUsesOfValuesWith, which handles bulkDan Gohman2008-07-171-15/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | replacement of multiple values. This is slightly more efficient than doing multiple ReplaceAllUsesOfValueWith calls, and theoretically could be optimized even further. However, an important property of this new function is that it handles the case where the source value set and destination value set overlap. This makes it feasible for isel to use SelectNodeTo in many very common cases, which is advantageous because SelectNodeTo avoids a temporary node and it doesn't require CSEMap updates for users of values that don't change position. Revamp MorphNodeTo, which is what does all the work of SelectNodeTo, to handle operand lists more efficiently, and to correctly handle a number of corner cases to which its new wider use exposes it. This commit also includes a change to the encoding of post-isel opcodes in SDNodes; now instead of being sandwiched between the target-independent pre-isel opcodes and the target-dependent pre-isel opcodes, post-isel opcodes are now represented as negative values. This makes it possible to test if an opcode is pre-isel or post-isel without having to know the size of the current target's post-isel instruction set. These changes speed up llc overall by 3% and reduce memory usage by 10% on the InstructionCombining.cpp testcase with -fast and -regalloc=local. llvm-svn: 53728
* Reapply 53476 and 53480, with a fix so that it properly updatesDan Gohman2008-07-141-7/+0
| | | | | | | the BB member to the current basic block after emitting instructions. llvm-svn: 53567
* Back out 53476 and 53480 for now. Somehow they cause llc to miscompile 179.art.Evan Cheng2008-07-121-0/+7
| | | | llvm-svn: 53502
* Factor out debugging code into the common base class.Dan Gohman2008-07-111-4/+0
| | | | llvm-svn: 53480
* Add support for putting NamedRegionTimers in TimerGroups, andDan Gohman2008-07-111-3/+0
| | | | | | | | use a timer group for the timers in SelectionDAGISel. Also, Split scheduling out from emitting, to give each their own timer. llvm-svn: 53476
* - Use a faster priority comparison function if -fast.Evan Cheng2008-07-021-94/+165
| | | | | | - Code clean up. llvm-svn: 53010
* Do not use computationally expensive scheduling heuristics with -fast.Evan Cheng2008-07-011-45/+53
| | | | llvm-svn: 52971
* Move a DenseMap's declaration outside of a loop, and just callDan Gohman2008-06-231-1/+2
| | | | | | | clear() on each iteration. This avoids allocating and deallocating all of DenseMap's memory on each iteration. llvm-svn: 52642
* canClobberPhysRegDefs shouldn't called without checking hasPhysRegDefs;Dan Gohman2008-06-211-3/+2
| | | | | | check this with an assert. llvm-svn: 52603
* Remove ScheduleDAG's SUnitMap altogether. Instead, use SDNode's NodeIdDan Gohman2008-06-211-33/+18
| | | | | | | field, which is otherwise unused after instruction selection, as an index into the SUnit array. llvm-svn: 52583
* Add a priority queue class, which is a wrapper around std::priority_queueDan Gohman2008-06-211-10/+8
| | | | | | | and provides fairly efficient removal of arbitrary elements. Switch ScheduleDAGRRList from std::set to this new priority queue. llvm-svn: 52582
* Change ScheduleDAG's SUnitMap from DenseMap<SDNode*, vector<SUnit*> >Dan Gohman2008-06-211-17/+23
| | | | | | | | to DenseMap<SDNode*, SUnit*>, and adjust the way cloned SUnit nodes are handled so that only the original node needs to be in the map. This speeds up llc on 447.dealII.llvm.bc by about 2%. llvm-svn: 52576
* Simplify some template parameterization.Dan Gohman2008-06-211-19/+12
| | | | llvm-svn: 52571
* Wrap MVT::ValueType in a struct to get type safetyDuncan Sands2008-06-061-6/+6
| | | | | | | | | | | | | | | | and better control the abstraction. Rename the type to MVT. To update out-of-tree patches, the main thing to do is to rename MVT::ValueType to MVT, and rewrite expressions like MVT::getSizeInBits(VT) in the form VT.getSizeInBits(). Use VT.getSimpleVT() to extract a MVT::SimpleValueType for use in switch statements (you will get an assert failure if VT is an extended value type - these shouldn't exist after type legalization). This results in a small speedup of codegen and no new testsuite failures (x86-64 linux). llvm-svn: 52044
* Silence the compiler warning differently. TheDuncan Sands2008-05-161-1/+1
| | | | | | original method caused gcc-4.2 to complain. llvm-svn: 51186
* Silence some compiler warnings.Evan Cheng2008-05-141-0/+1
| | | | llvm-svn: 51115
* 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. llvm-svn: 50412
* 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. llvm-svn: 49747
* 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. llvm-svn: 49701
* Cosmetic changes.Evan Cheng2008-03-291-24/+3
| | | | llvm-svn: 48947
* ifdef out a dead function. Should this be removed?Chris Lattner2008-03-281-0/+2
| | | | llvm-svn: 48916
* Fix spelling. Thanks, Duncan! :-)Roman Levenstein2008-03-271-1/+1
| | | | llvm-svn: 48873
* 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. llvm-svn: 48872
* Fixed some spelling errors. Thanks, Duncan!Roman Levenstein2008-03-261-52/+54
| | | | llvm-svn: 48819
* 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. llvm-svn: 48817
* Fix typos.Dan Gohman2008-03-251-3/+3
| | | | llvm-svn: 48779
* 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. llvm-svn: 48218
* Rename isOperand() to isOperandOf() (and other similar methods). It always ↵Evan Cheng2008-03-041-1/+1
| | | | | | confuses me. llvm-svn: 47872
OpenPOWER on IntegriCloud