aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
AgeCommit message (Collapse)Author
2008-11-19Experimental post-pass scheduling support. Post-pass schedulingDan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59676 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-19Move the code for printing a graph node label for an SUnit intoDan Gohman
a virtual method of SelectionDAG. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59667 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-19Convert SUnit's dump method into a print method and implementDan Gohman
dump in terms of it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59665 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-19Fix debug printing of flagged SDNodes in SUnits so that theyDan Gohman
print in the correct order. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59567 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-18Change SUnit's dump method to take a ScheduleDAG* instead ofDan Gohman
a SelectionDAG*. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59488 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-14Add support for building a ScheduleDAG from MachineInstrs. This is currentlyDan Gohman
fairly conservative; it doesn't do alias-analysis queries and it doesn't attempt to break anti-dependencies. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59324 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-13Remove the FlaggedNodes member from SUnit. Instead of requiring each SUnitDan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59273 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-13Make the Node member of SUnit private, and add accessors.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59264 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-13Change ScheduleDAG's DAG member from a reference to a pointer, to prepareDan Gohman
for the possibility of scheduling without a SelectionDAG being present. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59263 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-11Avoid relying on the SelectionDAG for initializing the MachineFunction andDan Gohman
TargetLoweringInfo variables for the scheduler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59082 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-25SDNodes may have at most one Flag result. Update this commentDan Gohman
to reflect that. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@58145 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-03Separate MachineInstr-emitting routines from actual schedulingDan Gohman
routines and move them into a separate file, ScheduleDAGEmit.cpp. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55699 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-28erect abstraction boundaries for accessing SDValue members, rename Val -> ↵Gabor Greif
Node to reflect semantics git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55504 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-27Optimize ScheduleDAG's ComputeDepths and ComputeHeights to not needDan Gohman
a scratch std::vector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55420 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-26disallow direct access to SDValue::ResNo, provide a getter insteadGabor Greif
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55394 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-27Rename SDOperand to SDValue.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54128 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-27Tidy SDNode::use_iterator, and complete the transition to have itDan Gohman
parallel its analogue, Value::value_use_iterator. The operator* method now returns the user, rather than the use. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54127 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-17Add a new function, ReplaceAllUsesOfValuesWith, which handles bulkDan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53728 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-14Reapply 53476 and 53480, with a fix so that it properly updatesDan Gohman
the BB member to the current basic block after emitting instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53567 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-12Back out 53476 and 53480 for now. Somehow they cause llc to miscompile 179.art.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53502 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-11Fix an obsolete top-level comment.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53481 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-11Factor out debugging code into the common base class.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53480 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-07Pool-allocation for MachineInstrs, MachineBasicBlocks, andDan Gohman
MachineMemOperands. The pools are owned by MachineFunctions. This drastically reduces the number of calls to malloc/free made during the "Emit" phase of scheduling, as well as later phases in CodeGen. Combined with other changes, this speeds up the "instruction selection" phase of CodeGen by 10% in some cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53212 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-07Make DenseMap's insert return a pair, to more closely resemble std::map.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53177 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-02Replace a few uses of SelectionDAG::getTargetNode withDan Gohman
SelectionDAG::SelectNodeTo in the instruction selector. This updates existing nodes in place instead of creating new ones. Go back to selecting ISD::DBG_LABEL nodes into TargetInstrInfo::DBG_LABEL nodes instead of leaving them unselected, now that SelectNodeTo allows us to update them in place. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53057 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-02- Use a faster priority comparison function if -fast.Evan Cheng
- Code clean up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53010 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-01Split ISD::LABEL into ISD::DBG_LABEL and ISD::EH_LABEL, eliminatingDan Gohman
the need for a flavor operand, and add a new SDNode subclass, LabelSDNode, for use with them to eliminate the need for a label id operand. Change instruction selection to let these label nodes through unmodified instead of creating copies of them. Teach the MachineInstr emitter how to emit a MachineInstr directly from an ISD label node. This avoids the need for allocating SDNodes for the label id and flavor value, as well as SDNodes for each of the post-isel label, label id, and label flavor. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52943 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-21Remove a redundant return.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52585 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-21Remove ScheduleDAG's SUnitMap altogether. Instead, use SDNode's NodeIdDan Gohman
field, which is otherwise unused after instruction selection, as an index into the SUnit array. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52583 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-21Add a priority queue class, which is a wrapper around std::priority_queueDan Gohman
and provides fairly efficient removal of arbitrary elements. Switch ScheduleDAGRRList from std::set to this new priority queue. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52582 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-21Change ScheduleDAG's SUnitMap from DenseMap<SDNode*, vector<SUnit*> >Dan Gohman
to DenseMap<SDNode*, SUnit*>, and adjust the way cloned SUnit nodes are handled so that only the original node needs to be in the map. This speeds up llc on 447.dealII.llvm.bc by about 2%. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52576 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-20Clean up some uses of std::distance, now that we have allnodes_size.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52545 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-06Wrap MVT::ValueType in a struct to get type safetyDuncan Sands
and better control the abstraction. Rename the type to MVT. To update out-of-tree patches, the main thing to do is to rename MVT::ValueType to MVT, and rewrite expressions like MVT::getSizeInBits(VT) in the form VT.getSizeInBits(). Use VT.getSimpleVT() to extract a MVT::SimpleValueType for use in switch statements (you will get an assert failure if VT is an extended value type - these shouldn't exist after type legalization). This results in a small speedup of codegen and no new testsuite failures (x86-64 linux). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52044 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-14Use a better idiom to silence compiler warnings.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51131 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-14Really silence compiler warnings.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51123 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-14Silence some compiler warnings.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51115 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-20Switch to using Simplified ConstantFP::get API.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49977 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-16Ongoing work on improving the instruction selection infrastructure:Roman Levenstein
Rename SDOperandImpl back to SDOperand. Introduce the SDUse class that represents a use of the SDNode referred by an SDOperand. Now it is more similar to Use/Value classes. Patch is approved by Dan Gohman. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49795 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-15Treat EntryToken nodes as "passive" so that they aren't added to theDan Gohman
ScheduleDAG; they don't correspond to any actual instructions so they don't need to be scheduled. This fixes a bug where the EntryToken was being scheduled multiple times in some cases, though it ended up not causing any trouble because EntryToken doesn't expand into anything. With this fixed the schedulers reliably schedule the expected number of units, so we can check this with an assertion. This requires a tweak to test/CodeGen/X86/loop-hoist.ll because it ends up getting scheduled differently in a trivial way, though it was enough to fool the prcontext+grep that the test does. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49701 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-07Rename MemOperand to MachineMemOperand. This was suggested byDan Gohman
review feedback from Chris quite a while ago. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49348 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-07Re-commit of the r48822, where the infinite looping problem discoveredRoman Levenstein
by Dan Gohman is fixed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49330 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-03Start of a series of patches related to implicit_def.Evan Cheng
There is no point in creating a long live range defined by an implicit_def. Scheduler now duplicates implicit_def instruction for each of its uses. Therefore, if an implicit_def node has multiple uses, it will become a number of very short live ranges, rather than a long one. This will make coalescer's job easier. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49164 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-03Backing out 48222 temporarily.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49124 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-26Use a linked data structure for the uses lists of an SDNode, just like Roman Levenstein
LLVM Value/Use does and MachineRegisterInfo/MachineOperand does. This allows constant time for all uses list maintenance operations. The idea was suggested by Chris. Reviewed by Evan and Dan. Patch is tested and approved by Dan. On normal use-cases compilation speed is not affected. On very big basic blocks there are compilation speedups in the range of 15-20% or even better. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48822 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-25A quick nm audit turned up several fixed tables and objects that wereDan Gohman
marked read-write. Use const so that they can be allocated in a read-only segment. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48800 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-16Make insert_subreg a two-address instruction, vastly simplifying ↵Christopher Lamb
LowerSubregs pass. Add a new TII, subreg_to_reg, which is like insert_subreg except that it takes an immediate implicit value to insert into rather than a register. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48412 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-15Replace all target specific implicit def instructions with a target ↵Evan Cheng
independent one: TargetInstrInfo::IMPLICIT_DEF. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48380 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-14Livein copy scheduling fixes: do not coalesce physical register copies, ↵Evan Cheng
correctly determine the safe location to insert the copies. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48348 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-12Experimental scheduler change to schedule / coalesce the copies added for ↵Evan Cheng
function livein's. Take 2008-03-10-RegAllocInfLoop.ll, the schedule looks like this after these copies are inserted: entry: 0x12049d0, LLVM BB @0x1201fd0, ID#0: Live Ins: %EAX %EDX %ECX %reg1031<def> = MOVPC32r 0 %reg1032<def> = ADD32ri %reg1031, <es:_GLOBAL_OFFSET_TABLE_>, %EFLAGS<imp-def> %reg1028<def> = MOV32rr %EAX %reg1029<def> = MOV32rr %EDX %reg1030<def> = MOV32rr %ECX %reg1027<def> = MOV8rm %reg0, 1, %reg0, 0, Mem:LD(1,1) [0x1201910 + 0] %reg1025<def> = MOV32rr %reg1029 %reg1026<def> = MOV32rr %reg1030 %reg1024<def> = MOV32rr %reg1028 The copies unnecessarily increase register pressure and it will end up requiring a physical register to be spilled. With -schedule-livein-copies: entry: 0x12049d0, LLVM BB @0x1201fa0, ID#0: Live Ins: %EAX %EDX %ECX %reg1031<def> = MOVPC32r 0 %reg1032<def> = ADD32ri %reg1031, <es:_GLOBAL_OFFSET_TABLE_>, %EFLAGS<imp-def> %reg1024<def> = MOV32rr %EAX %reg1025<def> = MOV32rr %EDX %reg1026<def> = MOV32rr %ECX %reg1027<def> = MOV8rm %reg0, 1, %reg0, 0, Mem:LD(1,1) [0x12018e0 + 0] Much better! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48307 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-11Recommitting parts of r48130. These do not appear to cause the observed ↵Christopher Lamb
failures. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48223 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-29 08:47:13 +0000