summaryrefslogtreecommitdiff
path: root/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
Commit message (Collapse)AuthorAge
* Merging r205738:Tom Stellard2014-04-08
| | | | | | | | | | | | | | | | | | | | | | | | | ------------------------------------------------------------------------ r205738 | atrick | 2014-04-07 17:29:22 -0400 (Mon, 07 Apr 2014) | 16 lines Put a limit on ScheduleDAGSDNodes::ClusterNeighboringLoads to avoid blowing up compile time. Fixes PR16365 - Extremely slow compilation in -O1 and -O2. The SD scheduler has a quadratic implementation of load clustering which absolutely blows up compile time for large blocks with constant pool loads. The MI scheduler has a better implementation of load clustering. However, we have not done the work yet to completely eliminate the SD scheduler. Some benchmarks still seem to benefit from early load clustering, although maybe by chance. As an intermediate term fix, I just put a nice limit on the number of DAG users to search before finding a match. With this limit there are no binary differences in the LLVM test suite, and the PR16365 test case does not suffer any compile time impact from this routine. ------------------------------------------------------------------------ git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_34@205808 91177308-0d34-0410-b5e6-96231b3b80d8
* [PATCH] Fix PR17168 (DAG scheduler inserts DBG_VALUE before PHI with fast-isel)Bill Schmidt2013-10-18
| | | | | | | | | | | | | | | | | | | | | | | | | PR17168 describes a test case that fails when compiling for debug with fast-isel. Investigation showed that the test was failing because a DBG_VALUE machine instruction was placed prior to a PHI. For this problem to occur requires the following: * Compile for debug * Compile with fast-isel * In a block B, fast-isel must partially succeed before punting to DAG-isel * B must start with a PHI * The first unhandled node in the DAG must not generate a machine instruction * A debug value with an order less than that of that first node exists When all of these circumstances apply, the existing test that an instruction was not inserted won't fire. Currently it tests whether the block is empty, or whether the last instruction generated is a phi. When fast-isel has partially succeeded, the last instruction generated will not be a phi. Instead, we need to check whether the current insert position is immediately following a phi. This patch adds that check, and adds the test case from the PR as a regression test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192976 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a function object to compare the first or second component of a std::pair.Benjamin Kramer2013-08-24
| | | | | | Replace instances of this scattered around the code base. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@189169 91177308-0d34-0410-b5e6-96231b3b80d8
* Use SmallVectorImpl& instead of SmallVector to avoid repeating small vector ↵Craig Topper2013-07-14
| | | | | | size. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186274 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix PR16143: Insert DEBUG_VALUE before terminator.Andrew Trick2013-05-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182717 91177308-0d34-0410-b5e6-96231b3b80d8
* Track IR ordering of SelectionDAG nodes 3/4.Andrew Trick2013-05-25
| | | | | | | Remove the old IR ordering mechanism and switch to new one. Fix unit test failures. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182704 91177308-0d34-0410-b5e6-96231b3b80d8
* Change TargetLowering::getRepRegClassFor to take an MVT, instead ofPatrik Hagglund2012-12-13
| | | | | | | | | EVT. Accordingly, change RegDefIter to contain MVTs instead of EVTs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@170140 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert EVT->MVT changes, r169836-169851, due to buildbot failures.Patrik Hagglund2012-12-11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169854 91177308-0d34-0410-b5e6-96231b3b80d8
* Change TargetLowering::getRepRegClassFor to take an MVT, instead ofPatrik Hagglund2012-12-11
| | | | | | | | | EVT. Accordingly, change RegDefIter to contain MVTs instead of EVTs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169838 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-03
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
* ScheduleDAG interface. Added OrderKind to distinguish nonregister dependencies.Andrew Trick2012-11-06
| | | | | | | This is in preparation for adding "weak" DAG edges, but generally simplifies the design. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167435 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a really faster pre-RA scheduler (-pre-RA-sched=linearize). It doesn't useEvan Cheng2012-10-17
| | | | | | | | | | | | | | | any scheduling heuristics nor does it build up any scheduling data structure that other heuristics use. It essentially linearize by doing a DFA walk but it does handle glues correctly. IMPORTANT: it probably can't handle all the physical register dependencies so it's not suitable for x86. It also doesn't deal with dbg_value nodes right now so it's definitely is still WIP. rdar://12474515 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166122 91177308-0d34-0410-b5e6-96231b3b80d8
* Release build: guard dump functions withManman Ren2012-09-11
| | | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163339. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163653 91177308-0d34-0410-b5e6-96231b3b80d8
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-06
| | | | | | | No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163339 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply 155668: Fix the SD scheduler to avoid gluing the same node twice.Andrew Trick2012-04-28
| | | | | | | | | | This time, also fix the caller of AddGlue to properly handle incomplete chains. AddGlue had failure modes, but shamefully hid them from its caller. It's luck ran out. Fixes rdar://11314175: BuildSchedUnits assert. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155749 91177308-0d34-0410-b5e6-96231b3b80d8
* Temporarily revert r155668: Fix the SD scheduler to avoid gluing.Andrew Trick2012-04-27
| | | | | | This definitely caused regression with ARM -mno-thumb. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155743 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix the SD scheduler to avoid gluing the same node twice.Andrew Trick2012-04-26
| | | | | | | | | | | DAGCombine strangeness may result in multiple loads from the same offset. They both may try to glue themselves to another load. We could insist that the redundant loads glue themselves to each other, but the beter fix is to bail out from bad gluing at the time we detect it. Fixes rdar://11314175: BuildSchedUnits assert. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155668 91177308-0d34-0410-b5e6-96231b3b80d8
* Insert the debugging instructions in one fell-swoop so that it doesn't call theBill Wendling2012-03-14
| | | | | | | | expensive "getFirstTerminator" call. This reduces the time of compilation in PR12258 from >10 minutes to < 10 seconds. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152704 91177308-0d34-0410-b5e6-96231b3b80d8
* misched preparation: rename core scheduler methods for consistency.Andrew Trick2012-03-07
| | | | | | | We had half the API with one convention, half with another. Now was a good time to clean it up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152255 91177308-0d34-0410-b5e6-96231b3b80d8
* misched preparation: clarify ScheduleDAG and ScheduleDAGInstrs roles.Andrew Trick2012-03-07
| | | | | | | | | | | | | | | | | | | ScheduleDAG is responsible for the DAG: SUnits and SDeps. It provides target hooks for latency computation. ScheduleDAGInstrs extends ScheduleDAG and defines the current scheduling region in terms of MachineInstr iterators. It has access to the target's scheduling itinerary data. ScheduleDAGInstrs provides the logic for building the ScheduleDAG for the sequence of MachineInstrs in the current region. Target's can implement highly custom schedulers by extending this class. ScheduleDAGPostRATDList provides the driver and diagnostics for current postRA scheduling. It maintains a current Sequence of scheduled machine instructions and logic for splicing them into the block. During scheduling, it uses the ScheduleHazardRecognizer provided by the target. Specific changes: - Removed driver code from ScheduleDAG. clearDAG is the only interface needed. - Added enterRegion/exitRegion hooks to ScheduleDAGInstrs to delimit the scope of each scheduling region and associated DAG. They should be used to setup and cleanup any region-specific state in addition to the DAG itself. This is necessary because we reuse the same ScheduleDAG object for the entire function. The target may extend these hooks to do things at regions boundaries, like bundle terminators. The hooks are called even if we decide not to schedule the region. So all instructions in a block are "covered" by these calls. - Added ScheduleDAGInstrs::begin()/end() public API. - Moved Sequence into the driver layer, which is specific to the scheduling algorithm. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152208 91177308-0d34-0410-b5e6-96231b3b80d8
* misched preparation: modularize schedule emission.Andrew Trick2012-03-07
| | | | | | ScheduleDAG has nothing to do with how the instructions are scheduled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152206 91177308-0d34-0410-b5e6-96231b3b80d8
* misched preparation: modularize schedule printing.Andrew Trick2012-03-07
| | | | | | ScheduleDAG will not refer to the scheduled instruction sequence. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152205 91177308-0d34-0410-b5e6-96231b3b80d8
* misched preparation: modularize schedule verification.Andrew Trick2012-03-07
| | | | | | ScheduleDAG will not refer to the scheduled instruction sequence. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152204 91177308-0d34-0410-b5e6-96231b3b80d8
* Cleanup in preparation for misched: Move DAG visualization logic.Andrew Trick2012-03-07
| | | | | | Soon, ScheduleDAG will not refer to the BB. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152177 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename TargetSubtarget to TargetSubtargetInfo for consistency.Evan Cheng2011-07-01
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134259 91177308-0d34-0410-b5e6-96231b3b80d8
* Sink SubtargetFeature and TargetInstrItineraries (renamed ↵Evan Cheng2011-06-29
| | | | | | MCInstrItineraries) into MC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134049 91177308-0d34-0410-b5e6-96231b3b80d8
* - Rename TargetInstrDesc, TargetOperandInfo to MCInstrDesc and MCOperandInfo andEvan Cheng2011-06-28
| | | | | | | | | sink them into MC layer. - Added MCInstrInfo, which captures the tablegen generated static data. Chang TargetInstrInfo so it's based off MCInstrInfo. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134021 91177308-0d34-0410-b5e6-96231b3b80d8
* pre-RA-sched: Cleanup register pressure tracking.Andrew Trick2011-06-27
| | | | | | | | | Removed the check that peeks past EXTRA_SUBREG, which I don't think makes sense any more. Intead treat it as a normal register def. No significant affect on x86 or ARM benchmarks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133917 91177308-0d34-0410-b5e6-96231b3b80d8
* The scheduler needs to be aware on the existence of untyped nodes when it ↵Owen Anderson2011-06-24
| | | | | | performs type propagation for EXTRACT_SUBREG. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133838 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't allocate empty read-only SmallVectors during SelectionDAG deallocation.Benjamin Kramer2011-06-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133348 91177308-0d34-0410-b5e6-96231b3b80d8
* Added -stress-sched flag in the Asserts build.Andrew Trick2011-06-15
| | | | | | | Added a test case for handling physreg aliases during pre-RA-sched. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133063 91177308-0d34-0410-b5e6-96231b3b80d8
* Be careful about scheduling nodes above previous calls. It increase usages ofEvan Cheng2011-04-26
| | | | | | | | | | | | | more callee-saved registers and introduce copies. Only allows it if scheduling a node above calls would end up lessen register pressure. Call operands also has added ABI restrictions for register allocation, so be extra careful with hoisting them above calls. rdar://9329627 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130245 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a ton of comment typos found by codespell. Patch byChris Lattner2011-04-15
| | | | | | | | Luis Felipe Strano Moraes! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129558 91177308-0d34-0410-b5e6-96231b3b80d8
* In the pre-RA scheduler, maintain cmp+br proximity.Andrew Trick2011-04-14
| | | | | | | | | | | | | | | | | | | | | | | | | This is done by pushing physical register definitions close to their use, which happens to handle flag definitions if they're not glued to the branch. This seems to be generally a good thing though, so I didn't need to add a target hook yet. The primary motivation is to generate code closer to what people expect and rule out missed opportunity from enabling macro-op fusion. As a side benefit, we get several 2-5% gains on x86 benchmarks. There is one regression: SingleSource/Benchmarks/Shootout/lists slows down be -10%. But this is an independent scheduler bug that will be tracked separately. See rdar://problem/9283108. Incidentally, pre-RA scheduling is only half the solution. Fixing the later passes is tracked by: <rdar://problem/8932804> [pre-RA-sched] on x86, attempt to schedule CMP/TEST adjacent with condition jump Fixes: <rdar://problem/9262453> Scheduler unnecessary break of cmp/jump fusion git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129508 91177308-0d34-0410-b5e6-96231b3b80d8
* Recommit r129383. PreRA scheduler heuristic fixes: VRegCycle, TokenFactor ↵Andrew Trick2011-04-13
| | | | | | | | | | | | | | | | | | | | | | latency. Additional fixes: Do something reasonable for subtargets with generic itineraries by handle node latency the same as for an empty itinerary. Now nodes default to unit latency unless an itinerary explicitly specifies a zero cycle stage or it is a TokenFactor chain. Original fixes: UnitsSharePred was a source of randomness in the scheduler: node priority depended on the queue data structure. I rewrote the recent VRegCycle heuristics to completely replace the old heuristic without any randomness. To make the ndoe latency adjustments work, I also needed to do something a little more reasonable with TokenFactor. I gave it zero latency to its consumers and always schedule it as low as possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129421 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert 129383. It causes some targets to hit a scheduler assert.Andrew Trick2011-04-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129385 91177308-0d34-0410-b5e6-96231b3b80d8
* PreRA scheduler heuristic fixes: VRegCycle, TokenFactor latency.Andrew Trick2011-04-12
| | | | | | | | | | | | | UnitsSharePred was a source of randomness in the scheduler: node priority depended on the queue data structure. I rewrote the recent VRegCycle heuristics to completely replace the old heuristic without any randomness. To make these heuristic adjustments to node latency work, I also needed to do something a little more reasonable with TokenFactor. I gave it zero latency to its consumers and always schedule it as low as possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129383 91177308-0d34-0410-b5e6-96231b3b80d8
* Added a check in the preRA scheduler for potential interference on aAndrew Trick2011-04-07
| | | | | | | | | | induction variable. The preRA scheduler is unaware of induction vars, so we look for potential "virtual register cycles" instead. Fixes <rdar://problem/8946719> Bad scheduling prevents coalescing git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129100 91177308-0d34-0410-b5e6-96231b3b80d8
* Improve pre-RA-sched register pressure tracking for duplicate operands.Andrew Trick2011-03-09
| | | | | | | This helps cases like 2008-07-19-movups-spills.ll, but doesn't have an obvious impact on benchmarks git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127347 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix some latent bugs if the nodes are unschedulable. We'd gotten awayEric Christopher2011-03-08
| | | | | | | | | | | | | with this before since none of the register tracking or nightly tests had unschedulable nodes. This should probably be refixed with a special default Node that just returns some "don't touch me" values. Fixes PR9427 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127263 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix for -sched-high-latency-cycles in sched=list-ilp mode.Andrew Trick2011-03-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127071 91177308-0d34-0410-b5e6-96231b3b80d8
* Increased the register pressure limit on x86_64 from 8 to 12Andrew Trick2011-03-05
| | | | | | | | | | | | | | | | | | | | | | | | regs. This is the only change in this checkin that may affects the default scheduler. With better register tracking and heuristics, it doesn't make sense to artificially lower the register limit so much. Added -sched-high-latency-cycles and X86InstrInfo::isHighLatencyDef to give the scheduler a way to account for div and sqrt on targets that don't have an itinerary. It is currently defaults to 10 (the actual number doesn't matter much), but only takes effect on non-default schedulers: list-hybrid and list-ilp. Added several heuristics that can be individually disabled for the non-default sched=list-ilp mode. This helps us determine how much better we can do on a given benchmark than the default scheduler. Certain compute intensive loops run much faster in this mode with the right set of heuristics, and it doesn't seem to have much negative impact elsewhere. Not all of the heuristics are needed, but we still need to experiment to decide which should be disabled by default for sched=list-ilp. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127067 91177308-0d34-0410-b5e6-96231b3b80d8
* Introducing a new method of tracking register pressure. We can'tAndrew Trick2011-02-04
| | | | | | | | | | | | | | | | precisely track pressure on a selection DAG, but we can at least keep it balanced. This design accounts for various interesting aspects of selection DAGS: register and subregister copies, glued nodes, dead nodes, unused registers, etc. Added SUnit::NumRegDefsLeft and ScheduleDAGSDNodes::RegDefIter. Note: I disabled PrescheduleNodesWithMultipleUses when register pressure is enabled, based on no evidence other than I don't think it makes sense to have both enabled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124853 91177308-0d34-0410-b5e6-96231b3b80d8
* whitespaceAndrew Trick2011-02-03
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124827 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply 124301Devang Patel2011-01-27
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124339 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert 124301.Devang Patel2011-01-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124327 91177308-0d34-0410-b5e6-96231b3b80d8
* Process valid SDDbgValues even if the node does not have any order assigned.Devang Patel2011-01-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124301 91177308-0d34-0410-b5e6-96231b3b80d8
* Refactor.Devang Patel2011-01-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124300 91177308-0d34-0410-b5e6-96231b3b80d8
* This assertion is too restrictive, it does not apply for dangling dbg value ↵Devang Patel2011-01-25
| | | | | | nodes (nodes where dbg.value intrinsic preceds use of the value). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124202 91177308-0d34-0410-b5e6-96231b3b80d8
* flags -> glue for selectiondagChris Lattner2010-12-23
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122509 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-29 13:43:04 +0000