aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/ScheduleDAGInstrs.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Add -enable-aa-sched-mi, off by default, for AliasAnalysis inside ↵Andrew Trick2012-05-151-22/+243
| | | | | | | | | | | | | | | MachineScheduler. This feature avoids creating edges in the scheduler's dependence graph for non-aliasing memory operations according to whichever alias analysis is available. It has been fully tested in Hexagon. Before making this default, it needs to be extended to handle multiple MachineMemOperands, compile time needs more evaluation, and benchmarking on X86 and ARM is needed. Patch by Sergei Larin! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156842 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: DAG builder must special case earlyclobberAndrew Trick2012-04-241-0/+9
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155459 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: DAG builder support for tracking register pressure within the ↵Andrew Trick2012-04-241-1/+10
| | | | | | | | | current scheduling region. The DAG builder is a convenient place to do it. Hopefully this is more efficient than a separate traversal over the same region. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155456 91177308-0d34-0410-b5e6-96231b3b80d8
* New and improved comment.Andrew Trick2012-04-201-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155229 91177308-0d34-0410-b5e6-96231b3b80d8
* SparseSet: Add support for key-derived indexes and arbitrary key types.Andrew Trick2012-04-201-2/+2
| | | | | | | | | | | | | | | | | | | This nicely handles the most common case of virtual register sets, but also handles anticipated cases where we will map pointers to IDs. The goal is not to develop a completely generic SparseSet template. Instead we want to handle the expected uses within llvm without any template antics in the client code. I'm adding a bit of template nastiness here, and some assumption about expected usage in order to make the client code very clean. The expected common uses cases I'm designing for: - integer keys that need to be reindexed, and may map to additional data - densely numbered objects where we want pointer keys because no number->object map exists. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155227 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: initialize BBAndrew Trick2012-04-201-2/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155226 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: Added CanHandleTerminators.Andrew Trick2012-04-131-3/+3
| | | | | | | | | This is a special flag for targets that really want their block terminators in the DAG. The default scheduler cannot handle this correctly, so it becomes the specialized scheduler's responsibility to schedule terminators. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154712 91177308-0d34-0410-b5e6-96231b3b80d8
* ScheduleDAGInstrs: When adding uses we add them into a set that's empty at ↵Benjamin Kramer2012-03-161-2/+2
| | | | | | the beginning, no need to maintain another set for the added regs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152934 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: add DAG edges from vreg defs to ExitSU.Andrew Trick2012-03-161-1/+3
| | | | | | | | | | These edges are not really necessary, but it is consistent with the way we currently create physreg edges. Scheduler heuristics that expect a DAG edge to the block terminator could benefit from this change. Although in the future I hope we have a better mechanism for modeling latency across scheduling regions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152895 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: implemented a framework for top-down or bottom-up scheduling.Andrew Trick2012-03-141-4/+7
| | | | | | | | | | | | | | | | | | | 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 interface: rename Begin/End to RegionBegin/RegionEnd since they are ↵Andrew Trick2012-03-091-5/+5
| | | | | | not private. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152382 91177308-0d34-0410-b5e6-96231b3b80d8
* misched prep: Expose the ScheduleDAGInstrs interface so targets mayAndrew Trick2012-03-071-1/+1
| | | | | | implement their own MachineScheduler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152261 91177308-0d34-0410-b5e6-96231b3b80d8
* misched prep: Comment the ScheduleDAGInstrs interface.Andrew Trick2012-03-071-2/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152259 91177308-0d34-0410-b5e6-96231b3b80d8
* misched prep: Cleanup ScheduleDAGInstrs interface.Andrew Trick2012-03-071-2/+2
| | | | | | | | ScheduleDAGInstrs will be the main interface for MI-level schedulers. Make sure it's readable: one page of protected fields, one page of public methids. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152258 91177308-0d34-0410-b5e6-96231b3b80d8
* misched prep: rename InsertPos to End.Andrew Trick2012-03-071-5/+5
| | | | | | ScheduleDAGInstrs knows nothing about how instructions will be moved or inserted. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152256 91177308-0d34-0410-b5e6-96231b3b80d8
* misched preparation: rename core scheduler methods for consistency.Andrew Trick2012-03-071-13/+13
| | | | | | | 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-071-20/+29
| | | | | | | | | | | | | | | | | | | 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-071-35/+0
| | | | | | 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
* Cleanup in preparation for misched: Move DAG visualization logic.Andrew Trick2012-03-071-0/+6
| | | | | | 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
* Use uint16_t to store register overlaps to reduce static data.Craig Topper2012-03-041-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152001 91177308-0d34-0410-b5e6-96231b3b80d8
* PostRA sched: speed up physreg tracking by not abusing SparseSet.Andrew Trick2012-02-241-15/+26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151348 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: cleanup reaching def computationAndrew Trick2012-02-231-3/+5
| | | | | | | | Ignore undef uses completely. Use a more explicit SlotIndex API. Add more explicit comments. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151233 91177308-0d34-0410-b5e6-96231b3b80d8
* PostRASched: Convert physreg def/use tracking to Jakob's SparseSet.Andrew Trick2012-02-231-78/+86
| | | | | | | Added array subscript to SparseSet for convenience. Slight reorg to make it easier to manage the def/use sets. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151228 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't compute latencies for regmask operands.Jakob Stoklund Olesen2012-02-221-1/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151211 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: Use SparseSet for VRegDegs for constant time clear().Andrew Trick2012-02-221-13/+19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151205 91177308-0d34-0410-b5e6-96231b3b80d8
* Comment from code reviewAndrew Trick2012-02-221-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151178 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: DAG builder should not track dependencies for SSA defs.Andrew Trick2012-02-221-1/+5
| | | | | | | The vast majority of virtual register definitions don't need an entry in the DAG builder's VRegDefs set. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151136 91177308-0d34-0410-b5e6-96231b3b80d8
* Initialize SUnits before DAG building.Andrew Trick2012-02-221-61/+83
| | | | | | | | | | | | 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
* Clear virtual registers after they are no longer referenced.Andrew Trick2012-02-211-0/+2
| | | | | | | | | | | | | Passes after RegAlloc should be able to rely on MRI->getNumVirtRegs() == 0. This makes sharing code for pre/postRA passes more robust. Now, to check if a pass is running before the RA pipeline begins, use MRI->isSSA(). To check if a pass is running after the RA pipeline ends, use !MRI->getNumVirtRegs(). PEI resets virtual regs when it's done scavenging. PTX will either have to provide its own PEI pass or assign physregs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151032 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: Initial code for building an MI level scheduling DAGAndrew Trick2012-01-141-8/+86
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148174 91177308-0d34-0410-b5e6-96231b3b80d8
* Move physreg dependency generation into aptly named addPhysRegDeps.Andrew Trick2012-01-141-155/+175
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148173 91177308-0d34-0410-b5e6-96231b3b80d8
* misched: Added ScheduleDAGInstrs::IsPostRAAndrew Trick2012-01-141-3/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148172 91177308-0d34-0410-b5e6-96231b3b80d8
* Added a late machine instruction copy propagation pass. This catchesEvan Cheng2012-01-071-6/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | opportunities that only present themselves after late optimizations such as tail duplication .e.g. ## BB#1: movl %eax, %ecx movl %ecx, %eax ret The register allocator also leaves some of them around (due to false dep between copies from phi-elimination, etc.) This required some changes in codegen passes. Post-ra scheduler and the pseudo-instruction expansion passes have been moved after branch folding and tail merging. They were before branch folding before because it did not always update block livein's. That's fixed now. The pass change makes independently since we want to properly schedule instructions after branch folding / tail duplication. rdar://10428165 rdar://10640363 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147716 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove an unused variable.Chandler Carruth2012-01-051-1/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147605 91177308-0d34-0410-b5e6-96231b3b80d8
* Minor postra scheduler cleanup. It could result in more precise ↵Andrew Trick2012-01-051-25/+19
| | | | | | antidependence latency on ARM in exceedingly rare cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147594 91177308-0d34-0410-b5e6-96231b3b80d8
* Model ARM predicated write as read-mod-write. e.g.Evan Cheng2011-12-141-2/+2
| | | | | | | | | | | | r0 = mov #0 r0 = moveq #1 Then the second instruction has an implicit data dependency on the first instruction. Sadly I have yet to come up with a small test case that demonstrate the post-ra scheduler taking advantage of this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146583 91177308-0d34-0410-b5e6-96231b3b80d8
* Allow target to specify register output dependency. Still default to one.Evan Cheng2011-12-141-1/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146547 91177308-0d34-0410-b5e6-96231b3b80d8
* - Add MachineInstrBundle.h and MachineInstrBundle.cpp. This includes a functionEvan Cheng2011-12-141-11/+6
| | | | | | | | | | | to finalize MI bundles (i.e. add BUNDLE instruction and computing register def and use lists of the BUNDLE instruction) and a pass to unpack bundles. - Teach more of MachineBasic and MachineInstr methods to be bundle aware. - Switch Thumb2 IT block to MI bundles and delete the hazard recognizer hack to prevent IT blocks from being broken apart. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146542 91177308-0d34-0410-b5e6-96231b3b80d8
* Add bundle aware API for querying instruction properties and switch the codeEvan Cheng2011-12-071-11/+10
| | | | | | | | | | | | | | | generator to it. For non-bundle instructions, these behave exactly the same as the MC layer API. For properties like mayLoad / mayStore, look into the bundle and if any of the bundled instructions has the property it would return true. For properties like isPredicable, only return true if *all* of the bundled instructions have the property. For properties like canFoldAsLoad, isCompare, conservatively return false for bundles. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146026 91177308-0d34-0410-b5e6-96231b3b80d8
* First chunk of MachineInstr bundle support.Evan Cheng2011-12-061-1/+1
| | | | | | | | | | 1. Added opcode BUNDLE 2. Taught MachineInstr class to deal with bundled MIs 3. Changed MachineBasicBlock iterator to skip over bundled MIs; added an iterator to walk all the MIs 4. Taught MachineBasicBlock methods about bundled MIs git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145975 91177308-0d34-0410-b5e6-96231b3b80d8
* make sure ScheduleDAGInstrs::EmitSchedule does not crash when the first ↵Hal Finkel2011-12-021-5/+5
| | | | | | instruction in Sequence is a Noop git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145677 91177308-0d34-0410-b5e6-96231b3b80d8
* PostRA scheduler fix. Clear stale loop dependencies.Andrew Trick2011-10-071-0/+1
| | | | | | | Fixes <rdar://problem/10235725> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141357 91177308-0d34-0410-b5e6-96231b3b80d8
* whitespaceAndrew Trick2011-10-071-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141356 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename TargetSubtarget to TargetSubtargetInfo for consistency.Evan Cheng2011-07-011-2/+2
| | | | 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-291-0/+1
| | | | | | 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-281-16/+16
| | | | | | | | | 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
* Remove dead code.Devang Patel2011-06-021-8/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132488 91177308-0d34-0410-b5e6-96231b3b80d8
* Update DBG_VALUEs while breaking anti dependencies.Devang Patel2011-06-021-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132487 91177308-0d34-0410-b5e6-96231b3b80d8
* During post RA scheduling, do not try to chase reg defs. to preserve ↵Devang Patel2011-06-021-36/+29
| | | | | | | | | DBG_VALUEs. This approach has several downsides, for example, it does not work when dbg value is a constant integer, it does not work if reg is defined more than once, it places end of debug value range markers in the wrong place. It even causes misleading incorrect debug info when duplicate DBG_VALUE instructions point to same reg def. Instead, use simpler approach and let DBG_VALUE follow its predecessor instruction. After live debug value analysis pass, all DBG_VALUE instruction are placed at the right place. Thanks Jakob for the hint! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132483 91177308-0d34-0410-b5e6-96231b3b80d8
* Added an assertion, and updated a comment.Andrew Trick2011-05-061-5/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131022 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-02-10 06:13:40 +0000