summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Make debug output more informative.Dan Gohman2008-12-041-1/+1
| | | | llvm-svn: 60524
* Initial support for anti-dependence breaking. Currently this code does notDan Gohman2008-11-251-238/+26
| | | | | | | | | introduce any new spilling; it just uses unused registers. Refactor the SUnit topological sort code out of the RRList scheduler and make use of it to help with the post-pass scheduler. llvm-svn: 59999
* Check in the rest of this change. The isAntiDep flag needs to be passedDan Gohman2008-11-241-1/+1
| | | | | | | to removePred because an SUnit can both data-depend and anti-depend on the same SUnit. llvm-svn: 59969
* Add a flag to SDep for tracking which edges are anti-dependence edges.Dan Gohman2008-11-211-4/+4
| | | | llvm-svn: 59785
* Rename SDep's isSpecial to isArtificial, to make this field a littleDan Gohman2008-11-211-20/+20
| | | | | | less mysterious. llvm-svn: 59782
* Remove the CycleBound computation code from the ScheduleDAGRRListDan Gohman2008-11-211-58/+5
| | | | | | | | | | | | | schedulers. This doesn't have much immediate impact because targets that use these schedulers by default don't yet provide pipeline information. This code also didn't have the benefit of register pressure information. Also, removing it will avoid problems with list-burr suddenly starting to do latency-oriented scheduling on x86 when we start providing pipeline data, which would increase spilling. llvm-svn: 59775
* Change these schedulers to not emit no-ops. It turns out thatDan Gohman2008-11-211-6/+2
| | | | | | | | | the RR scheduler actually does look at latency values, but it doesn't use a hazard recognizer so it has no way to know when a no-op is needed, as opposed to just stalling and incrementing the cycle count. llvm-svn: 59759
* Remove a remnant of list-burr's fast mode.Dan Gohman2008-11-201-20/+0
| | | | llvm-svn: 59702
* Factor out the SethiUllman numbering logic from the list-burr andDan Gohman2008-11-201-159/+47
| | | | | | list-tdrr schedulers into a common base class. llvm-svn: 59701
* Remove the "fast" form of the list-burr scheduler, and use theDan Gohman2008-11-201-68/+9
| | | | | | | | | dedicated "fast" scheduler in -fast mode instead, which is faster. This speeds up llc -fast by a few percent on some testcases -- the speedup only happens for code not handled by fast-isel. llvm-svn: 59700
* Facter AddPseudoTwoAddrDeps and associated infrasructure out ofDan Gohman2008-11-201-43/+60
| | | | | | | the list-burr scheduler so that it can be used by the list-tdrr scheduler too. llvm-svn: 59698
* 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
OpenPOWER on IntegriCloud