summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Make a few things const, fix some comments, and simplifyDan Gohman2009-01-291-16/+8
| | | | | | some assertions. llvm-svn: 63328
* Move a few containers out of ScheduleDAGInstrs::BuildSchedGraphDan Gohman2009-01-151-15/+13
| | | | | | | | | | | and into the ScheduleDAGInstrs class, so that they don't get destructed and re-constructed for each block. This fixes a compile-time hot spot in the post-pass scheduler. To help facilitate this, tidy and do some minor reorganization in the scheduler constructor functions. llvm-svn: 62275
* The list-td and list-tdrr schedulers don't yet support physregDan Gohman2009-01-131-1/+5
| | | | | | | | | | | scheduling dependencies. Add assertion checks to help catch this. It appears the Mips target defaults to list-td, and it has a regression test that uses a physreg dependence. Such code was liable to be miscompiled, and now evokes an assertion failure. llvm-svn: 62177
* Fix PR3241: Currently EmitCopyFromReg emits a copy from the physical ↵Evan Cheng2009-01-121-27/+31
| | | | | | | | register to a virtual register unless it requires an expensive cross class copy. That means we are only treating "expensive to copy" register dependency as physical register dependency. Also future proof the scheduler to handle "normal" physical register dependencies. The code is not exercised yet. llvm-svn: 62074
* Minor debug output tweak.Evan Cheng2009-01-091-2/+2
| | | | llvm-svn: 62005
* Remove redundant 'else's. No functionality change.Dan Gohman2009-01-071-7/+6
| | | | llvm-svn: 61891
* Update these argument lists for the isNormalMemoryDan Gohman2009-01-061-3/+6
| | | | | | argument. This doesn't affect current functionality. llvm-svn: 61779
* Use a latency value of 0 for the artificial edges inserted byDan Gohman2009-01-061-1/+1
| | | | | | | | | | | | AddPseudoTwoAddrDeps. This lets the scheduling infrastructure avoid recalculating node heights. In very large testcases this was a major bottleneck. Thanks to Roman Levenstein for finding this! As a side effect, fold-pcmpeqd-0.ll is now scheduled better and it no longer requires spilling on x86-32. llvm-svn: 61778
* Tidy up #includes, deleting a bunch of unnecessary #includes.Dan Gohman2009-01-051-2/+0
| | | | llvm-svn: 61715
* CommuteNodesToReducePressure() is now removed.Dan Gohman2009-01-031-1/+0
| | | | llvm-svn: 61612
* Remove the code from the scheduler that commuted two-addressDan Gohman2009-01-031-54/+0
| | | | | | | | | | | | | | instructions to avoid copies, because TwoAddressInstructionPass also does this optimization. The scheduler's version didn't account for live-out values, which resulted in spurious commutes and missed opportunities. Now, TwoAddressInstructionPass handles all the opportunities, instead of just those that the scheduler missed. The result is usually the same, though there are occasional trivial differences resulting from the avoidance of spurious commutes. llvm-svn: 61611
* Rename BuildSchedUnits to BuildSchedGraph, and refactor theDan Gohman2008-12-231-2/+2
| | | | | | code in ScheduleDAGSDNodes' BuildSchedGraph into separate functions. llvm-svn: 61376
* Fix some register-alias-related bugs in the post-RA scheduler livenessDan Gohman2008-12-161-37/+30
| | | | | | | | | | | | | | computation code. Also, avoid adding output-depenency edges when both defs are dead, which frequently happens with EFLAGS defs. Compute Depth and Height lazily, and always in terms of edge latency values. For the schedulers that don't care about latency, edge latencies are set to 1. Eliminate Cycle and CycleBound, and LatencyPriorityQueue's Latencies array. These are all subsumed by the Depth and Height fields. llvm-svn: 61073
* Make addPred and removePred return void, since the return value is notDan Gohman2008-12-161-4/+4
| | | | | | currently used by anything. llvm-svn: 61066
* Rewrite the SDep class, and simplify some of the related code.Dan Gohman2008-12-091-118/+134
| | | | | | | | | | | | | | | | | The Cost field is removed. It was only being used in a very limited way, to indicate when the scheduler should attempt to protect a live register, and it isn't really needed to do that. If we ever want the scheduler to start inserting copies in non-prohibitive situations, we'll have to rethink some things anyway. A Latency field is added. Instead of giving each node a single fixed latency, each edge can have its own latency. This will eventually be used to model various micro-architecture properties more accurately. The PointerIntPair class and an internal union are now used, which reduce the overall size. llvm-svn: 60806
* 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
OpenPOWER on IntegriCloud