summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
Commit message (Collapse)AuthorAgeFilesLines
* MISched: add dependence to ExitSU to model live-out latency.Andrew Trick2012-12-181-1/+16
| | | | llvm-svn: 170454
* Use GetUnderlyingObjects in mischedHal Finkel2012-12-101-92/+143
| | | | | | | | | | | | | | | | misched used GetUnderlyingObject in order to break false load/store dependencies, and the -enable-aa-sched-mi feature similarly relied on GetUnderlyingObject in order to ensure it is safe to use the aliasing analysis. Unfortunately, GetUnderlyingObject does not recurse through phi nodes, and so (especially due to LSR) all of these mechanisms failed for induction-variable-dependent loads and stores inside loops. This change replaces uses of GetUnderlyingObject with GetUnderlyingObjects (which will recurse through phi and select instructions) in misched. Andy reviewed, tested and simplified this patch; Thanks! llvm-svn: 169744
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-9/+9
| | | | | | | | | | | | | | | | | 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. =] llvm-svn: 169131
* misched: Fix RegisterPressureTracker handling of DebugVals.Andrew Trick2012-12-011-7/+7
| | | | | | | Assertion failed: (TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker"). rdar://12790302. llvm-svn: 169072
* misched: Fix the DAG builder to handle an undef operand at ExitSU.Andrew Trick2012-12-011-1/+2
| | | | | | | Assertion failed: (VNI && "No value to read by operand") rdar://12790267. llvm-svn: 169071
* misched: Analysis that partitions the DAG into subtrees.Andrew Trick2012-11-281-41/+166
| | | | | | | | | | | This is a simple, cheap infrastructure for analyzing the shape of a DAG. It recognizes uniform DAGs that take the shape of bottom-up subtrees, such as the included matrix multiplication example. This is useful for heuristics that balance register pressure with ILP. Two canonical expressions of the heuristic are implemented in scheduling modes: -misched-ilpmin and -misched-ilpmax. llvm-svn: 168773
* misched: rename ScheduleDAGILP to ScheduleDFS to prepare for other heuristics.Andrew Trick2012-11-281-1/+1
| | | | llvm-svn: 168772
* misched: better alias analysis.Andrew Trick2012-11-281-2/+3
| | | | | | | | | | | | | This fixes a hole in the "cheap" alias analysis logic implemented within the DAG builder itself, regardless of whether proper alias analysis is enabled. It now handles this pattern produced by LSR+CodeGenPrepare. %sunkaddr1 = ptrtoint * %obj to i64 %sunkaddr2 = add i64 %sunkaddr1, %lsr.iv %sunkaddr3 = inttoptr i64 %sunkaddr2 to i32* store i32 %v, i32* %sunkaddr3 llvm-svn: 168768
* Fix indeterminism in MI scheduler DAG construction.Sergei Larin2012-11-151-15/+15
| | | | | | | Similarly to several recent fixes throughout the code replace std::map use with the MapVector. Add find() method to the MapVector. llvm-svn: 168051
* misched: Infrastructure for weak DAG edges.Andrew Trick2012-11-121-9/+14
| | | | | | | | This adds support for weak DAG edges to the general scheduling infrastructure in preparation for MachineScheduler support for heuristics based on weak edges. llvm-svn: 167738
* ScheduleDAG interface. Added OrderKind to distinguish nonregister dependencies.Andrew Trick2012-11-061-25/+32
| | | | | | | This is in preparation for adding "weak" DAG edges, but generally simplifies the design. llvm-svn: 167435
* [inline asm] Implement mayLoad and mayStore for inline assembly. In general,Chad Rosier2012-10-301-5/+0
| | | | | | | | | | the MachineInstr MayLoad/MayLoad flags are based on the tablegen implementation. For inline assembly, however, we need to compute these based on the constraints. Revert r166929 as this is no longer needed, but leave the test case in place. rdar://12033048 and PR13504 llvm-svn: 167040
* This patch addresses a problem with the Post RA scheduler generating anPreston Gurd2012-10-291-0/+5
| | | | | | | | | | | | | | incorrect instruction sequence due to it not being aware that an inline assembly instruction may reference memory. This patch fixes the problem by causing the scheduler to always assume that any inline assembly code instruction could access memory. This is necessary because the internal representation of the inline instruction does not include any information about memory accesses. This should fix PR13504. llvm-svn: 166929
* Fix typo in comment.Nick Lewycky2012-10-261-1/+1
| | | | llvm-svn: 166750
* misched: ILP scheduler for experimental heuristics.Andrew Trick2012-10-151-0/+93
| | | | llvm-svn: 165950
* misched: Use the TargetSchedModel interface wherever possible.Andrew Trick2012-10-101-22/+6
| | | | | | | | Allows the new machine model to be used for NumMicroOps and OutputLatency. Allows the HazardRecognizer to be disabled along with itineraries. llvm-svn: 165603
* misched: Remove LoopDependencies heuristic.Andrew Trick2012-10-091-40/+1
| | | | | | This wasn't contributing anything significant to postRA heuristics except compile time (by my measurements) and will be replaced by a more general heuristic for cross-region dependencies within the scheduler itself. llvm-svn: 165563
* misched: remove the unused getSpecialAddressLatency hook.Andrew Trick2012-10-081-40/+7
| | | | llvm-svn: 165418
* misched: remove forceUnitLatencies. Defaults are handled by the default ↵Andrew Trick2012-10-081-35/+24
| | | | | | SchedModel llvm-svn: 165417
* misched: Make ScheduleDAGInstrs use the TargetSchedule interface.Andrew Trick2012-09-181-16/+14
| | | | llvm-svn: 164153
* Release build: guard dump functions withManman Ren2012-09-111-1/+1
| | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163339. llvm-svn: 163653
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-061-0/+2
| | | | | | No functional change. llvm-svn: 163339
* Rename hasVolatileMemoryRef() to hasOrderedMemoryRef().Jakob Stoklund Olesen2012-08-291-1/+1
| | | | | | | | Ordered memory operations are more constrained than volatile loads and stores because they must be ordered with respect to all other memory operations. llvm-svn: 162861
* Simplify the computeOperandLatency API.Andrew Trick2012-08-231-27/+30
| | | | | | | | | 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. llvm-svn: 162420
* Use the latest MachineRegisterInfo APIs. No functionality.Andrew Trick2012-07-301-1/+1
| | | | llvm-svn: 161010
* Reenable a basic SSA DAG builder optimization.Andrew Trick2012-07-281-5/+4
| | | | | | Jakob fixed ProcessImplicifDefs in r159149. llvm-svn: 160910
* misched: disable SSA check pending PR13112.Andrew Trick2012-06-141-2/+4
| | | | llvm-svn: 158461
* sched: fix latency of memory dependence chain edges for consistency.Andrew Trick2012-06-131-13/+21
| | | | | | | | | | | For store->load dependencies that may alias, we should always use TrueMemOrderLatency, which may eventually become a subtarget hook. In effect, we should guarantee at least TrueMemOrderLatency on at least one DAG path from a store to a may-alias load. This should fix the standard mode as well as -enable-aa-sched-mi". llvm-svn: 158380
* Move RegisterPressure.h.Andrew Trick2012-06-061-1/+1
| | | | | | Make it a general utility for use by Targets. llvm-svn: 158097
* Remove unused private fields found by clang's new -Wunused-private-field.Benjamin Kramer2012-06-061-1/+1
| | | | | | | | There are some that I didn't remove this round because they looked like obvious stubs. There are dead variables in gtest too, they should be fixed upstream. llvm-svn: 158090
* misched: API for minimum vs. expected latency.Andrew Trick2012-06-051-61/+18
| | | | | | | Minimum latency determines per-cycle scheduling groups. Expected latency determines critical path and cost. llvm-svn: 158021
* Switch all register list clients to the new MC*Iterator interface.Jakob Stoklund Olesen2012-06-011-2/+4
| | | | | | | | | | | | | No functional change intended. Sorry for the churn. The iterator classes are supposed to help avoid giant commits like this one in the future. The TableGen-produced register lists are getting quite large, and it may be necessary to change the table representation. This makes it possible to do so without changing all clients (again). llvm-svn: 157854
* Use LiveRangeQuery in ScheduleDAGInstrs.Jakob Stoklund Olesen2012-05-201-11/+3
| | | | llvm-svn: 157144
* 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! llvm-svn: 156842
* misched: DAG builder must special case earlyclobberAndrew Trick2012-04-241-0/+9
| | | | llvm-svn: 155459
* 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. llvm-svn: 155456
* New and improved comment.Andrew Trick2012-04-201-1/+1
| | | | llvm-svn: 155229
* 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. llvm-svn: 155227
* misched: initialize BBAndrew Trick2012-04-201-2/+4
| | | | llvm-svn: 155226
* 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. llvm-svn: 154712
* 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. llvm-svn: 152934
* 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. llvm-svn: 152895
* 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. llvm-svn: 152700
* misched interface: rename Begin/End to RegionBegin/RegionEnd since they are ↵Andrew Trick2012-03-091-5/+5
| | | | | | not private. llvm-svn: 152382
* misched prep: Expose the ScheduleDAGInstrs interface so targets mayAndrew Trick2012-03-071-1/+1
| | | | | | implement their own MachineScheduler. llvm-svn: 152261
* misched prep: Comment the ScheduleDAGInstrs interface.Andrew Trick2012-03-071-2/+3
| | | | llvm-svn: 152259
* 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. llvm-svn: 152258
* misched prep: rename InsertPos to End.Andrew Trick2012-03-071-5/+5
| | | | | | ScheduleDAGInstrs knows nothing about how instructions will be moved or inserted. llvm-svn: 152256
* 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. llvm-svn: 152255
* 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. llvm-svn: 152208
OpenPOWER on IntegriCloud