summaryrefslogtreecommitdiff
path: root/include/llvm/CodeGen/ScheduleDAG.h
Commit message (Collapse)AuthorAge
* Sort the #include lines for the include/... tree with the script.Chandler Carruth2012-12-03
| | | | | | | | | | AKA: Recompile *ALL* the source code! This one went much better. No manual edits here. I spot-checked for silliness and grep-checked for really broken edits and everything seemed good. It all still compiles. Yell if you see something that looks goofy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169133 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: Don't consider artificial edges weak edges.Andrew Trick2012-11-13
| | | | | | | For now be more conservative in case other out-of-tree schedulers rely on the old behavior of artificial edges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167808 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: Infrastructure for weak DAG edges.Andrew Trick2012-11-12
| | | | | | | | This adds support for weak DAG edges to the general scheduling infrastructure in preparation for MachineScheduler support for heuristics based on weak edges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167738 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: TargetSchedule interface for machine resources.Andrew Trick2012-11-06
| | | | | | | | | | | Expose the processor resources defined by the machine model to the scheduler and other clients through the TargetSchedule interface. Normalize each resource count with respect to other kinds of resources. This allows scheduling heuristics to balance resources against other kinds of resources and latency. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167444 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
* misched: Use the TargetSchedModel interface wherever possible.Andrew Trick2012-10-10
| | | | | | | | Allows the new machine model to be used for NumMicroOps and OutputLatency. Allows the HazardRecognizer to be disabled along with itineraries. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165603 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: remove forceUnitLatencies. Defaults are handled by the default ↵Andrew Trick2012-10-08
| | | | | | SchedModel git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165417 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify the computeOperandLatency API.Andrew Trick2012-08-23
| | | | | | | | | The logic for recomputing latency based on a ScheduleDAG edge was shady. This bypasses the problem by requiring the client to provide operand indices. This ensures consistent use of the machine model's API. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162420 91177308-0d34-0410-b5e6-96231b3b80d8
* sched: Avoid trivially redundant DAG edges. Take the one with higher latency.Andrew Trick2012-06-13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158379 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: API for minimum vs. expected latency.Andrew Trick2012-06-05
| | | | | | | Minimum latency determines per-cycle scheduling groups. Expected latency determines critical path and cost. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158021 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: implemented a framework for top-down or bottom-up scheduling.Andrew Trick2012-03-14
| | | | | | | | | | | | | | | | | | | New flags: -misched-topdown, -misched-bottomup. They can be used with the default scheduler or with -misched=shuffle. Without either topdown/bottomup flag -misched=shuffle now alternates scheduling direction. LiveIntervals update is unimplemented with bottom-up scheduling, so only -misched-topdown currently works. Capped the ScheduleDAG hierarchy with a concrete ScheduleDAGMI class. ScheduleDAGMI is aware of the top and bottom of the unscheduled zone within the current region. Scheduling policy can be plugged into the ScheduleDAGMI driver by implementing MachineSchedStrategy. ConvergingScheduler is now the default scheduling algorithm. It exercises the new driver but still does no reordering. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152700 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
* Cleanup: DAG building is specific to either SD or MI scheduling. Not part of ↵Andrew Trick2012-03-07
| | | | | | the target interface. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152174 91177308-0d34-0410-b5e6-96231b3b80d8
* misched commentsAndrew Trick2012-03-07
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152173 91177308-0d34-0410-b5e6-96231b3b80d8
* Initialize SUnits before DAG building.Andrew Trick2012-02-22
| | | | | | | | | | | | Affect on SD scheduling and postRA scheduling: Printing the DAG will display the nodes in top-down topological order. This matches the order within the MBB and makes my life much easier in general. Affect on misched: We don't need to track virtual register uses at all. This is awesome. I also intend to rely on the SUnit ID as a topo-sort index. So if A < B then we cannot have an edge B -> A. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151135 91177308-0d34-0410-b5e6-96231b3b80d8
* Move some llvm_unreachable's from r149849 out of switch statements to ↵Craig Topper2012-02-06
| | | | | | satisfy -Wcovered-switch-default git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149860 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert assert(0) to llvm_unreachableCraig Topper2012-02-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149849 91177308-0d34-0410-b5e6-96231b3b80d8
* Move Sched::Preference out of TargetMachine.h where it is not referenced.Evan Cheng2012-01-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148014 91177308-0d34-0410-b5e6-96231b3b80d8
* Unweaken vtables as per ↵David Blaikie2011-12-20
| | | | | | http://llvm.org/docs/CodingStandards.html#ll_virtual_anch git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146960 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
* 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
* Remove dead code.Devang Patel2011-06-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132488 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
* 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
* Typos.Eric Christopher2011-03-07
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127186 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
* Header warning patrol.Eric Christopher2010-12-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122551 91177308-0d34-0410-b5e6-96231b3b80d8
* Minor cleanup related to my latest scheduler changes.Andrew Trick2010-12-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122545 91177308-0d34-0410-b5e6-96231b3b80d8
* Various bits of framework needed for precise machine-level selectionAndrew Trick2010-12-24
| | | | | | | | | | | | | | | | | | | | | | | | | | | DAG scheduling during isel. Most new functionality is currently guarded by -enable-sched-cycles and -enable-sched-hazard. Added InstrItineraryData::IssueWidth field, currently derived from ARM itineraries, but could be initialized differently on other targets. Added ScheduleHazardRecognizer::MaxLookAhead to indicate whether it is active, and if so how many cycles of state it holds. Added SchedulingPriorityQueue::HasReadyFilter to allowing gating entry into the scheduler's available queue. ScoreboardHazardRecognizer now accesses the ScheduleDAG in order to get information about it's SUnits, provides RecedeCycle for bottom-up scheduling, correctly computes scoreboard depth, tracks IssueCount, and considers potential stall cycles when checking for hazards. ScheduleDAGRRList now models machine cycles and hazards (under flags). It tracks MinAvailableCycle, drives the hazard recognizer and priority queue's ready filter, manages a new PendingQueue, properly accounts for stall cycles, etc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122541 91177308-0d34-0410-b5e6-96231b3b80d8
* whitespaceAndrew Trick2010-12-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122539 91177308-0d34-0410-b5e6-96231b3b80d8
* update comment.Chris Lattner2010-12-20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122212 91177308-0d34-0410-b5e6-96231b3b80d8
* SDep is POD-like. Shave off a few bytes from SUnit by moving a member around.Benjamin Kramer2010-11-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120150 91177308-0d34-0410-b5e6-96231b3b80d8
* Two sets of changes. Sorry they are intermingled.Evan Cheng2010-11-03
| | | | | | | | | | | | | | 1. Fix pre-ra scheduler so it doesn't try to push instructions above calls to "optimize for latency". Call instructions don't have the right latency and this is more likely to use introduce spills. 2. Fix if-converter cost function. For ARM, it should use instruction latencies, not # of micro-ops since multi-latency instructions is completely executed even when the predicate is false. Also, some instruction will be "slower" when they are predicated due to the register def becoming implicit input. rdar://8598427 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118135 91177308-0d34-0410-b5e6-96231b3b80d8
* Change push_all to a non-virtual function and implement it in theDan Gohman2010-05-26
| | | | | | | base class, since all the implementations are the same. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@104659 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete an unused function.Dan Gohman2010-05-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@104658 91177308-0d34-0410-b5e6-96231b3b80d8
* Allow targets more controls on what nodes are scheduled by reg pressure, ↵Evan Cheng2010-05-20
| | | | | | what for latency in hybrid mode. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@104293 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a hybrid bottom up scheduler that reduce register usage while avoidingEvan Cheng2010-05-20
| | | | | | | | | | pipeline stall. It's useful for targets like ARM cortex-a8. NEON has a lot of long latency instructions so a strict register pressure reduction scheduler does not work well. Early experiments show this speeds up some NEON loops by over 30%. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@104216 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix the post-RA instruction scheduler to handle instructions referenced byJim Grosbach2010-05-19
| | | | | | | more than one dbg_value instruction. rdar://7759363 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@104174 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unused member variable.Zhongxing Xu2010-05-17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103936 91177308-0d34-0410-b5e6-96231b3b80d8
* Get rid of the EdgeMapping map. Instead, just check for BasicBlockDan Gohman2010-05-01
| | | | | | | changes before doing phi lowering for switches. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@102809 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete an unused member variable.Dan Gohman2010-04-13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@101143 91177308-0d34-0410-b5e6-96231b3b80d8
* trim some prototypes.Chris Lattner2010-04-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@100420 91177308-0d34-0410-b5e6-96231b3b80d8
* Progress towards shepherding debug info through SelectionDAG.Dale Johannesen2010-03-10
| | | | | | | | | No functional effect yet. This is still evolving and should not be viewed as final. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@98195 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-25 14:41:51 +0000