Dan Gohman | f90d3b0 | 2008-12-08 17:50:35 +0000 | [diff] [blame] | 1 | //===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===// |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 10 | /// \file This implements the ScheduleDAGInstrs class, which implements |
| 11 | /// re-scheduling of MachineInstrs. |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Chandler Carruth | 6bda14b | 2017-06-06 11:49:48 +0000 | [diff] [blame] | 15 | #include "llvm/CodeGen/ScheduleDAGInstrs.h" |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 16 | #include "llvm/ADT/IntEqClasses.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 17 | #include "llvm/ADT/MapVector.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 18 | #include "llvm/ADT/SmallPtrSet.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 19 | #include "llvm/ADT/SmallVector.h" |
| 20 | #include "llvm/ADT/SparseSet.h" |
Chandler Carruth | 6bda14b | 2017-06-06 11:49:48 +0000 | [diff] [blame] | 21 | #include "llvm/ADT/iterator_range.h" |
Dan Gohman | 1ee0d41 | 2009-01-30 02:49:14 +0000 | [diff] [blame] | 22 | #include "llvm/Analysis/AliasAnalysis.h" |
Dan Gohman | a4fcd24 | 2010-12-15 20:02:24 +0000 | [diff] [blame] | 23 | #include "llvm/Analysis/ValueTracking.h" |
Matthias Braun | d4f6409 | 2016-01-20 00:23:32 +0000 | [diff] [blame] | 24 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 25 | #include "llvm/CodeGen/LivePhysRegs.h" |
| 26 | #include "llvm/CodeGen/MachineBasicBlock.h" |
Arnold Schwaighofer | f54b73d | 2015-05-08 23:52:00 +0000 | [diff] [blame] | 27 | #include "llvm/CodeGen/MachineFrameInfo.h" |
Chandler Carruth | 6bda14b | 2017-06-06 11:49:48 +0000 | [diff] [blame] | 28 | #include "llvm/CodeGen/MachineFunction.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 29 | #include "llvm/CodeGen/MachineInstr.h" |
| 30 | #include "llvm/CodeGen/MachineInstrBundle.h" |
Dan Gohman | 48b185d | 2009-09-25 20:36:54 +0000 | [diff] [blame] | 31 | #include "llvm/CodeGen/MachineMemOperand.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 32 | #include "llvm/CodeGen/MachineOperand.h" |
Dan Gohman | dddc1ac | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 33 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Dan Gohman | 3aab10b | 2008-12-04 01:35:46 +0000 | [diff] [blame] | 34 | #include "llvm/CodeGen/PseudoSourceValue.h" |
Andrew Trick | 88517f6 | 2012-06-06 19:47:35 +0000 | [diff] [blame] | 35 | #include "llvm/CodeGen/RegisterPressure.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 36 | #include "llvm/CodeGen/ScheduleDAG.h" |
Andrew Trick | cd1c2f9 | 2012-11-28 05:13:24 +0000 | [diff] [blame] | 37 | #include "llvm/CodeGen/ScheduleDFS.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 38 | #include "llvm/CodeGen/SlotIndexes.h" |
| 39 | #include "llvm/IR/Constants.h" |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 40 | #include "llvm/IR/Function.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 41 | #include "llvm/IR/Instruction.h" |
| 42 | #include "llvm/IR/Instructions.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 43 | #include "llvm/IR/Operator.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 44 | #include "llvm/IR/Type.h" |
| 45 | #include "llvm/IR/Value.h" |
| 46 | #include "llvm/MC/LaneBitmask.h" |
| 47 | #include "llvm/MC/MCRegisterInfo.h" |
| 48 | #include "llvm/Support/Casting.h" |
Andrew Trick | da01ba3 | 2012-05-15 18:59:41 +0000 | [diff] [blame] | 49 | #include "llvm/Support/CommandLine.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 50 | #include "llvm/Support/Compiler.h" |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 51 | #include "llvm/Support/Debug.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 52 | #include "llvm/Support/ErrorHandling.h" |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 53 | #include "llvm/Support/Format.h" |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 54 | #include "llvm/Support/raw_ostream.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 55 | #include "llvm/Target/TargetRegisterInfo.h" |
| 56 | #include "llvm/Target/TargetSubtargetInfo.h" |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 57 | #include <algorithm> |
| 58 | #include <cassert> |
| 59 | #include <iterator> |
| 60 | #include <string> |
| 61 | #include <utility> |
| 62 | #include <vector> |
Andrew Trick | c01b004 | 2013-08-23 17:48:43 +0000 | [diff] [blame] | 63 | |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 64 | using namespace llvm; |
| 65 | |
Evandro Menezes | 0cd23f56 | 2017-07-11 22:08:28 +0000 | [diff] [blame] | 66 | #define DEBUG_TYPE "machine-scheduler" |
Chandler Carruth | 1b9dde0 | 2014-04-22 02:02:50 +0000 | [diff] [blame] | 67 | |
Andrew Trick | da01ba3 | 2012-05-15 18:59:41 +0000 | [diff] [blame] | 68 | static cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, |
| 69 | cl::ZeroOrMore, cl::init(false), |
Jonas Paulsson | bf408bb | 2015-01-07 13:20:57 +0000 | [diff] [blame] | 70 | cl::desc("Enable use of AA during MI DAG construction")); |
Andrew Trick | da01ba3 | 2012-05-15 18:59:41 +0000 | [diff] [blame] | 71 | |
Hal Finkel | dbebb52 | 2014-01-25 19:24:54 +0000 | [diff] [blame] | 72 | static cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, |
Jonas Paulsson | bf408bb | 2015-01-07 13:20:57 +0000 | [diff] [blame] | 73 | cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction")); |
Hal Finkel | dbebb52 | 2014-01-25 19:24:54 +0000 | [diff] [blame] | 74 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 75 | // Note: the two options below might be used in tuning compile time vs |
| 76 | // output quality. Setting HugeRegion so large that it will never be |
| 77 | // reached means best-effort, but may be slow. |
| 78 | |
| 79 | // When Stores and Loads maps (or NonAliasStores and NonAliasLoads) |
| 80 | // together hold this many SUs, a reduction of maps will be done. |
| 81 | static cl::opt<unsigned> HugeRegion("dag-maps-huge-region", cl::Hidden, |
| 82 | cl::init(1000), cl::desc("The limit to use while constructing the DAG " |
| 83 | "prior to scheduling, at which point a trade-off " |
| 84 | "is made to avoid excessive compile time.")); |
| 85 | |
Mehdi Amini | 59ae854 | 2016-04-16 04:58:30 +0000 | [diff] [blame] | 86 | static cl::opt<unsigned> ReductionSize( |
| 87 | "dag-maps-reduction-size", cl::Hidden, |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 88 | cl::desc("A huge scheduling region will have maps reduced by this many " |
Mehdi Amini | 59ae854 | 2016-04-16 04:58:30 +0000 | [diff] [blame] | 89 | "nodes at a time. Defaults to HugeRegion / 2.")); |
| 90 | |
| 91 | static unsigned getReductionSize() { |
| 92 | // Always reduce a huge region with half of the elements, except |
| 93 | // when user sets this number explicitly. |
| 94 | if (ReductionSize.getNumOccurrences() == 0) |
| 95 | return HugeRegion / 2; |
| 96 | return ReductionSize; |
| 97 | } |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 98 | |
| 99 | static void dumpSUList(ScheduleDAGInstrs::SUList &L) { |
| 100 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| 101 | dbgs() << "{ "; |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 102 | for (const SUnit *su : L) { |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 103 | dbgs() << "SU(" << su->NodeNum << ")"; |
| 104 | if (su != L.back()) |
| 105 | dbgs() << ", "; |
| 106 | } |
| 107 | dbgs() << "}\n"; |
| 108 | #endif |
| 109 | } |
| 110 | |
Dan Gohman | 619ef48 | 2009-01-15 19:20:50 +0000 | [diff] [blame] | 111 | ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, |
Alexey Samsonov | 8968e6d | 2014-08-20 19:36:05 +0000 | [diff] [blame] | 112 | const MachineLoopInfo *mli, |
Matthias Braun | 93563e7 | 2015-11-03 01:53:29 +0000 | [diff] [blame] | 113 | bool RemoveKillFlags) |
Matthias Braun | b17e8b1 | 2015-12-04 19:54:24 +0000 | [diff] [blame] | 114 | : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()), |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 115 | RemoveKillFlags(RemoveKillFlags), |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 116 | UnknownValue(UndefValue::get( |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 117 | Type::getVoidTy(mf.getFunction()->getContext()))) { |
Devang Patel | e5feef0 | 2011-06-02 20:07:12 +0000 | [diff] [blame] | 118 | DbgValues.clear(); |
Andrew Trick | 9b63513 | 2012-09-18 18:20:00 +0000 | [diff] [blame] | 119 | |
Eric Christopher | 2c63549 | 2015-01-27 07:54:39 +0000 | [diff] [blame] | 120 | const TargetSubtargetInfo &ST = mf.getSubtarget(); |
Pete Cooper | 1175945 | 2014-09-02 17:43:54 +0000 | [diff] [blame] | 121 | SchedModel.init(ST.getSchedModel(), &ST, TII); |
Evan Cheng | f0236e0 | 2009-10-18 19:58:47 +0000 | [diff] [blame] | 122 | } |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 123 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 124 | /// If this machine instr has memory reference information and it can be tracked |
| 125 | /// to a normal reference to a known object, return the Value for that object. |
Hal Finkel | 66859ae | 2012-12-10 18:49:16 +0000 | [diff] [blame] | 126 | static void getUnderlyingObjectsForInstr(const MachineInstr *MI, |
Matthias Braun | 941a705 | 2016-07-28 18:40:00 +0000 | [diff] [blame] | 127 | const MachineFrameInfo &MFI, |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 128 | UnderlyingObjectsVector &Objects, |
| 129 | const DataLayout &DL) { |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 130 | auto allMMOsOkay = [&]() { |
| 131 | for (const MachineMemOperand *MMO : MI->memoperands()) { |
| 132 | if (MMO->isVolatile()) |
| 133 | return false; |
Hal Finkel | 66859ae | 2012-12-10 18:49:16 +0000 | [diff] [blame] | 134 | |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 135 | if (const PseudoSourceValue *PSV = MMO->getPseudoValue()) { |
| 136 | // Function that contain tail calls don't have unique PseudoSourceValue |
| 137 | // objects. Two PseudoSourceValues might refer to the same or |
| 138 | // overlapping locations. The client code calling this function assumes |
| 139 | // this is not the case. So return a conservative answer of no known |
| 140 | // object. |
Matthias Braun | 941a705 | 2016-07-28 18:40:00 +0000 | [diff] [blame] | 141 | if (MFI.hasTailCall()) |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 142 | return false; |
Geoff Berry | c0739d8 | 2016-04-12 15:50:19 +0000 | [diff] [blame] | 143 | |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 144 | // For now, ignore PseudoSourceValues which may alias LLVM IR values |
| 145 | // because the code that uses this function has no way to cope with |
| 146 | // such aliases. |
Matthias Braun | 941a705 | 2016-07-28 18:40:00 +0000 | [diff] [blame] | 147 | if (PSV->isAliased(&MFI)) |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 148 | return false; |
Geoff Berry | c0739d8 | 2016-04-12 15:50:19 +0000 | [diff] [blame] | 149 | |
Matthias Braun | 941a705 | 2016-07-28 18:40:00 +0000 | [diff] [blame] | 150 | bool MayAlias = PSV->mayAlias(&MFI); |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 151 | Objects.push_back(UnderlyingObjectsVector::value_type(PSV, MayAlias)); |
| 152 | } else if (const Value *V = MMO->getValue()) { |
| 153 | SmallVector<Value *, 4> Objs; |
Hiroshi Inoue | b9417db | 2017-08-01 03:32:15 +0000 | [diff] [blame] | 154 | getUnderlyingObjectsForCodeGen(V, Objs, DL); |
Geoff Berry | c0739d8 | 2016-04-12 15:50:19 +0000 | [diff] [blame] | 155 | |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 156 | for (Value *V : Objs) { |
Hiroshi Inoue | b9417db | 2017-08-01 03:32:15 +0000 | [diff] [blame] | 157 | assert(isIdentifiedObject(V)); |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 158 | Objects.push_back(UnderlyingObjectsVector::value_type(V, true)); |
Geoff Berry | c0739d8 | 2016-04-12 15:50:19 +0000 | [diff] [blame] | 159 | } |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 160 | } else |
| 161 | return false; |
Geoff Berry | c0739d8 | 2016-04-12 15:50:19 +0000 | [diff] [blame] | 162 | } |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 163 | return true; |
| 164 | }; |
| 165 | |
| 166 | if (!allMMOsOkay()) |
| 167 | Objects.clear(); |
Dan Gohman | 1ee0d41 | 2009-01-30 02:49:14 +0000 | [diff] [blame] | 168 | } |
| 169 | |
Andrew Trick | 7405c6d | 2012-04-20 20:05:21 +0000 | [diff] [blame] | 170 | void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) { |
| 171 | BB = bb; |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 172 | } |
| 173 | |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 174 | void ScheduleDAGInstrs::finishBlock() { |
Andrew Trick | 51ee936 | 2012-04-20 20:24:33 +0000 | [diff] [blame] | 175 | // Subclasses should no longer refer to the old block. |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 176 | BB = nullptr; |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 177 | } |
| 178 | |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 179 | void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb, |
| 180 | MachineBasicBlock::iterator begin, |
| 181 | MachineBasicBlock::iterator end, |
Andrew Trick | a53e101 | 2013-08-23 17:48:33 +0000 | [diff] [blame] | 182 | unsigned regioninstrs) { |
Andrew Trick | 7405c6d | 2012-04-20 20:05:21 +0000 | [diff] [blame] | 183 | assert(bb == BB && "startBlock should set BB"); |
Andrew Trick | 8c207e4 | 2012-03-09 04:29:02 +0000 | [diff] [blame] | 184 | RegionBegin = begin; |
| 185 | RegionEnd = end; |
Andrew Trick | a53e101 | 2013-08-23 17:48:33 +0000 | [diff] [blame] | 186 | NumRegionInstrs = regioninstrs; |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 187 | } |
| 188 | |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 189 | void ScheduleDAGInstrs::exitRegion() { |
| 190 | // Nothing to do. |
| 191 | } |
| 192 | |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 193 | void ScheduleDAGInstrs::addSchedBarrierDeps() { |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 194 | MachineInstr *ExitMI = RegionEnd != BB->end() ? &*RegionEnd : nullptr; |
Evan Cheng | 15459b6 | 2010-10-23 02:10:46 +0000 | [diff] [blame] | 195 | ExitSU.setInstr(ExitMI); |
Matthias Braun | 325cd2c | 2016-11-11 01:34:21 +0000 | [diff] [blame] | 196 | // Add dependencies on the defs and uses of the instruction. |
| 197 | if (ExitMI) { |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 198 | for (const MachineOperand &MO : ExitMI->operands()) { |
Evan Cheng | 15459b6 | 2010-10-23 02:10:46 +0000 | [diff] [blame] | 199 | if (!MO.isReg() || MO.isDef()) continue; |
| 200 | unsigned Reg = MO.getReg(); |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 201 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) { |
Michael Ilseman | 3e3194f | 2013-01-21 18:18:53 +0000 | [diff] [blame] | 202 | Uses.insert(PhysRegSUOper(&ExitSU, -1, Reg)); |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 203 | } else if (TargetRegisterInfo::isVirtualRegister(Reg) && MO.readsReg()) { |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 204 | addVRegUseDeps(&ExitSU, ExitMI->getOperandNo(&MO)); |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 205 | } |
Evan Cheng | 15459b6 | 2010-10-23 02:10:46 +0000 | [diff] [blame] | 206 | } |
Matthias Braun | 325cd2c | 2016-11-11 01:34:21 +0000 | [diff] [blame] | 207 | } |
| 208 | if (!ExitMI || (!ExitMI->isCall() && !ExitMI->isBarrier())) { |
Evan Cheng | 15459b6 | 2010-10-23 02:10:46 +0000 | [diff] [blame] | 209 | // For others, e.g. fallthrough, conditional branch, assume the exit |
Evan Cheng | cbdf7e8 | 2010-10-27 23:17:17 +0000 | [diff] [blame] | 210 | // uses all the registers that are livein to the successor blocks. |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 211 | for (const MachineBasicBlock *Succ : BB->successors()) { |
| 212 | for (const auto &LI : Succ->liveins()) { |
Matthias Braun | d9da162 | 2015-09-09 18:08:03 +0000 | [diff] [blame] | 213 | if (!Uses.contains(LI.PhysReg)) |
| 214 | Uses.insert(PhysRegSUOper(&ExitSU, -1, LI.PhysReg)); |
Evan Cheng | cbdf7e8 | 2010-10-27 23:17:17 +0000 | [diff] [blame] | 215 | } |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 216 | } |
Evan Cheng | 15459b6 | 2010-10-23 02:10:46 +0000 | [diff] [blame] | 217 | } |
| 218 | } |
| 219 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 220 | /// MO is an operand of SU's instruction that defines a physical register. Adds |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 221 | /// data dependencies from SU to any uses of the physical register. |
Andrew Trick | ae53561 | 2012-08-23 00:39:43 +0000 | [diff] [blame] | 222 | void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { |
| 223 | const MachineOperand &MO = SU->getInstr()->getOperand(OperIdx); |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 224 | assert(MO.isDef() && "expect physreg def"); |
| 225 | |
| 226 | // Ask the target if address-backscheduling is desirable, and if so how much. |
Eric Christopher | 2c63549 | 2015-01-27 07:54:39 +0000 | [diff] [blame] | 227 | const TargetSubtargetInfo &ST = MF.getSubtarget(); |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 228 | |
Jakob Stoklund Olesen | 54038d7 | 2012-06-01 23:28:30 +0000 | [diff] [blame] | 229 | for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); |
| 230 | Alias.isValid(); ++Alias) { |
Andrew Trick | 9dbbd3e | 2012-02-24 07:04:55 +0000 | [diff] [blame] | 231 | if (!Uses.contains(*Alias)) |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 232 | continue; |
Michael Ilseman | 3e3194f | 2013-01-21 18:18:53 +0000 | [diff] [blame] | 233 | for (Reg2SUnitsMap::iterator I = Uses.find(*Alias); I != Uses.end(); ++I) { |
| 234 | SUnit *UseSU = I->SU; |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 235 | if (UseSU == SU) |
| 236 | continue; |
Andrew Trick | 07dced6 | 2012-10-08 18:54:00 +0000 | [diff] [blame] | 237 | |
Andrew Trick | 07dced6 | 2012-10-08 18:54:00 +0000 | [diff] [blame] | 238 | // Adjust the dependence latency using operand def/use information, |
| 239 | // then allow the target to perform its own adjustments. |
Michael Ilseman | 3e3194f | 2013-01-21 18:18:53 +0000 | [diff] [blame] | 240 | int UseOp = I->OpIdx; |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 241 | MachineInstr *RegUse = nullptr; |
Andrew Trick | f1ff84c | 2012-11-12 19:28:57 +0000 | [diff] [blame] | 242 | SDep Dep; |
| 243 | if (UseOp < 0) |
| 244 | Dep = SDep(SU, SDep::Artificial); |
| 245 | else { |
Andrew Trick | e833e1c | 2013-04-13 06:07:40 +0000 | [diff] [blame] | 246 | // Set the hasPhysRegDefs only for physreg defs that have a use within |
| 247 | // the scheduling region. |
| 248 | SU->hasPhysRegDefs = true; |
Andrew Trick | f1ff84c | 2012-11-12 19:28:57 +0000 | [diff] [blame] | 249 | Dep = SDep(SU, SDep::Data, *Alias); |
| 250 | RegUse = UseSU->getInstr(); |
Andrew Trick | f1ff84c | 2012-11-12 19:28:57 +0000 | [diff] [blame] | 251 | } |
| 252 | Dep.setLatency( |
Andrew Trick | de2109e | 2013-06-15 04:49:57 +0000 | [diff] [blame] | 253 | SchedModel.computeOperandLatency(SU->getInstr(), OperIdx, RegUse, |
| 254 | UseOp)); |
Andrew Trick | 4544606 | 2012-06-05 21:11:27 +0000 | [diff] [blame] | 255 | |
Andrew Trick | f1ff84c | 2012-11-12 19:28:57 +0000 | [diff] [blame] | 256 | ST.adjustSchedDependency(SU, UseSU, Dep); |
| 257 | UseSU->addPred(Dep); |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 258 | } |
| 259 | } |
| 260 | } |
| 261 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 262 | /// \brief Adds register dependencies (data, anti, and output) from this SUnit |
| 263 | /// to following instructions in the same scheduling region that depend the |
| 264 | /// physical register referenced at OperIdx. |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 265 | void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { |
Andrew Trick | 6b104f8 | 2013-12-28 21:56:55 +0000 | [diff] [blame] | 266 | MachineInstr *MI = SU->getInstr(); |
| 267 | MachineOperand &MO = MI->getOperand(OperIdx); |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 268 | unsigned Reg = MO.getReg(); |
Matthias Braun | f29b12d | 2016-11-10 23:46:44 +0000 | [diff] [blame] | 269 | // We do not need to track any dependencies for constant registers. |
| 270 | if (MRI.isConstantPhysReg(Reg)) |
| 271 | return; |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 272 | |
| 273 | // Optionally add output and anti dependencies. For anti |
| 274 | // dependencies we use a latency of 0 because for a multi-issue |
| 275 | // target we want to allow the defining instruction to issue |
| 276 | // in the same cycle as the using instruction. |
| 277 | // TODO: Using a latency of 1 here for output dependencies assumes |
| 278 | // there's no cost for reusing registers. |
| 279 | SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output; |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 280 | for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); ++Alias) { |
Andrew Trick | 9dbbd3e | 2012-02-24 07:04:55 +0000 | [diff] [blame] | 281 | if (!Defs.contains(*Alias)) |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 282 | continue; |
Michael Ilseman | 3e3194f | 2013-01-21 18:18:53 +0000 | [diff] [blame] | 283 | for (Reg2SUnitsMap::iterator I = Defs.find(*Alias); I != Defs.end(); ++I) { |
| 284 | SUnit *DefSU = I->SU; |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 285 | if (DefSU == &ExitSU) |
| 286 | continue; |
| 287 | if (DefSU != SU && |
| 288 | (Kind != SDep::Output || !MO.isDead() || |
Hal Finkel | 66d7791 | 2014-12-05 02:07:35 +0000 | [diff] [blame] | 289 | !DefSU->getInstr()->registerDefIsDead(*Alias))) { |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 290 | if (Kind == SDep::Anti) |
Andrew Trick | baeaabb | 2012-11-06 03:13:46 +0000 | [diff] [blame] | 291 | DefSU->addPred(SDep(SU, Kind, /*Reg=*/*Alias)); |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 292 | else { |
Andrew Trick | baeaabb | 2012-11-06 03:13:46 +0000 | [diff] [blame] | 293 | SDep Dep(SU, Kind, /*Reg=*/*Alias); |
Andrew Trick | de2109e | 2013-06-15 04:49:57 +0000 | [diff] [blame] | 294 | Dep.setLatency( |
| 295 | SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr())); |
Andrew Trick | baeaabb | 2012-11-06 03:13:46 +0000 | [diff] [blame] | 296 | DefSU->addPred(Dep); |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 297 | } |
| 298 | } |
| 299 | } |
| 300 | } |
| 301 | |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 302 | if (!MO.isDef()) { |
Andrew Trick | e833e1c | 2013-04-13 06:07:40 +0000 | [diff] [blame] | 303 | SU->hasPhysRegUses = true; |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 304 | // Either insert a new Reg2SUnits entry with an empty SUnits list, or |
| 305 | // retrieve the existing SUnits list for this register's uses. |
| 306 | // Push this SUnit on the use list. |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 307 | Uses.insert(PhysRegSUOper(SU, OperIdx, Reg)); |
Andrew Trick | 6b104f8 | 2013-12-28 21:56:55 +0000 | [diff] [blame] | 308 | if (RemoveKillFlags) |
| 309 | MO.setIsKill(false); |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 310 | } else { |
Andrew Trick | ae53561 | 2012-08-23 00:39:43 +0000 | [diff] [blame] | 311 | addPhysRegDataDeps(SU, OperIdx); |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 312 | |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 313 | // clear this register's use list |
Michael Ilseman | 3e3194f | 2013-01-21 18:18:53 +0000 | [diff] [blame] | 314 | if (Uses.contains(Reg)) |
| 315 | Uses.eraseAll(Reg); |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 316 | |
Michael Ilseman | 3e3194f | 2013-01-21 18:18:53 +0000 | [diff] [blame] | 317 | if (!MO.isDead()) { |
| 318 | Defs.eraseAll(Reg); |
| 319 | } else if (SU->isCall) { |
| 320 | // Calls will not be reordered because of chain dependencies (see |
| 321 | // below). Since call operands are dead, calls may continue to be added |
| 322 | // to the DefList making dependence checking quadratic in the size of |
| 323 | // the block. Instead, we leave only one call at the back of the |
| 324 | // DefList. |
| 325 | Reg2SUnitsMap::RangePair P = Defs.equal_range(Reg); |
| 326 | Reg2SUnitsMap::iterator B = P.first; |
| 327 | Reg2SUnitsMap::iterator I = P.second; |
| 328 | for (bool isBegin = I == B; !isBegin; /* empty */) { |
| 329 | isBegin = (--I) == B; |
| 330 | if (!I->SU->isCall) |
| 331 | break; |
| 332 | I = Defs.erase(I); |
| 333 | } |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 334 | } |
Michael Ilseman | 3e3194f | 2013-01-21 18:18:53 +0000 | [diff] [blame] | 335 | |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 336 | // Defs are pushed in the order they are visited and never reordered. |
Michael Ilseman | 3e3194f | 2013-01-21 18:18:53 +0000 | [diff] [blame] | 337 | Defs.insert(PhysRegSUOper(SU, OperIdx, Reg)); |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 338 | } |
| 339 | } |
| 340 | |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 341 | LaneBitmask ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const |
| 342 | { |
| 343 | unsigned Reg = MO.getReg(); |
| 344 | // No point in tracking lanemasks if we don't have interesting subregisters. |
| 345 | const TargetRegisterClass &RC = *MRI.getRegClass(Reg); |
| 346 | if (!RC.HasDisjunctSubRegs) |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 347 | return LaneBitmask::getAll(); |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 348 | |
| 349 | unsigned SubReg = MO.getSubReg(); |
| 350 | if (SubReg == 0) |
| 351 | return RC.getLaneMask(); |
| 352 | return TRI->getSubRegIndexLaneMask(SubReg); |
| 353 | } |
| 354 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 355 | /// Adds register output and data dependencies from this SUnit to instructions |
| 356 | /// that occur later in the same scheduling region if they read from or write to |
| 357 | /// the virtual register defined at OperIdx. |
Andrew Trick | 59ac4fb | 2012-01-14 02:17:18 +0000 | [diff] [blame] | 358 | /// |
| 359 | /// TODO: Hoist loop induction variable increments. This has to be |
| 360 | /// reevaluated. Generally, IV scheduling should be done before coalescing. |
| 361 | void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 362 | MachineInstr *MI = SU->getInstr(); |
| 363 | MachineOperand &MO = MI->getOperand(OperIdx); |
| 364 | unsigned Reg = MO.getReg(); |
Andrew Trick | 59ac4fb | 2012-01-14 02:17:18 +0000 | [diff] [blame] | 365 | |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 366 | LaneBitmask DefLaneMask; |
| 367 | LaneBitmask KillLaneMask; |
| 368 | if (TrackLaneMasks) { |
| 369 | bool IsKill = MO.getSubReg() == 0 || MO.isUndef(); |
| 370 | DefLaneMask = getLaneMaskForMO(MO); |
| 371 | // If we have a <read-undef> flag, none of the lane values comes from an |
| 372 | // earlier instruction. |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 373 | KillLaneMask = IsKill ? LaneBitmask::getAll() : DefLaneMask; |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 374 | |
| 375 | // Clear undef flag, we'll re-add it later once we know which subregister |
| 376 | // Def is first. |
| 377 | MO.setIsUndef(false); |
| 378 | } else { |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 379 | DefLaneMask = LaneBitmask::getAll(); |
| 380 | KillLaneMask = LaneBitmask::getAll(); |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 381 | } |
| 382 | |
| 383 | if (MO.isDead()) { |
| 384 | assert(CurrentVRegUses.find(Reg) == CurrentVRegUses.end() && |
| 385 | "Dead defs should have no uses"); |
| 386 | } else { |
| 387 | // Add data dependence to all uses we found so far. |
| 388 | const TargetSubtargetInfo &ST = MF.getSubtarget(); |
| 389 | for (VReg2SUnitOperIdxMultiMap::iterator I = CurrentVRegUses.find(Reg), |
| 390 | E = CurrentVRegUses.end(); I != E; /*empty*/) { |
| 391 | LaneBitmask LaneMask = I->LaneMask; |
| 392 | // Ignore uses of other lanes. |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 393 | if ((LaneMask & KillLaneMask).none()) { |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 394 | ++I; |
| 395 | continue; |
| 396 | } |
| 397 | |
Krzysztof Parzyszek | ea9f8ce | 2016-12-16 19:11:56 +0000 | [diff] [blame] | 398 | if ((LaneMask & DefLaneMask).any()) { |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 399 | SUnit *UseSU = I->SU; |
| 400 | MachineInstr *Use = UseSU->getInstr(); |
| 401 | SDep Dep(SU, SDep::Data, Reg); |
| 402 | Dep.setLatency(SchedModel.computeOperandLatency(MI, OperIdx, Use, |
| 403 | I->OperandIndex)); |
| 404 | ST.adjustSchedDependency(SU, UseSU, Dep); |
| 405 | UseSU->addPred(Dep); |
| 406 | } |
| 407 | |
| 408 | LaneMask &= ~KillLaneMask; |
| 409 | // If we found a Def for all lanes of this use, remove it from the list. |
Krzysztof Parzyszek | ea9f8ce | 2016-12-16 19:11:56 +0000 | [diff] [blame] | 410 | if (LaneMask.any()) { |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 411 | I->LaneMask = LaneMask; |
| 412 | ++I; |
| 413 | } else |
| 414 | I = CurrentVRegUses.erase(I); |
| 415 | } |
| 416 | } |
| 417 | |
| 418 | // Shortcut: Singly defined vregs do not have output/anti dependencies. |
Andrew Trick | 7979589 | 2012-07-30 23:48:17 +0000 | [diff] [blame] | 419 | if (MRI.hasOneDef(Reg)) |
Andrew Trick | 9405343 | 2012-07-28 01:48:15 +0000 | [diff] [blame] | 420 | return; |
Andrew Trick | db42c6f | 2012-02-22 06:08:13 +0000 | [diff] [blame] | 421 | |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 422 | // Add output dependence to the next nearest defs of this vreg. |
Andrew Trick | 59ac4fb | 2012-01-14 02:17:18 +0000 | [diff] [blame] | 423 | // |
| 424 | // Unless this definition is dead, the output dependence should be |
| 425 | // transitively redundant with antidependencies from this definition's |
| 426 | // uses. We're conservative for now until we have a way to guarantee the uses |
| 427 | // are not eliminated sometime during scheduling. The output dependence edge |
| 428 | // is also useful if output latency exceeds def-use latency. |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 429 | LaneBitmask LaneMask = DefLaneMask; |
| 430 | for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg), |
| 431 | CurrentVRegDefs.end())) { |
| 432 | // Ignore defs for other lanes. |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 433 | if ((V2SU.LaneMask & LaneMask).none()) |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 434 | continue; |
| 435 | // Add an output dependence. |
| 436 | SUnit *DefSU = V2SU.SU; |
| 437 | // Ignore additional defs of the same lanes in one instruction. This can |
| 438 | // happen because lanemasks are shared for targets with too many |
| 439 | // subregisters. We also use some representration tricks/hacks where we |
| 440 | // add super-register defs/uses, to imply that although we only access parts |
| 441 | // of the reg we care about the full one. |
| 442 | if (DefSU == SU) |
| 443 | continue; |
| 444 | SDep Dep(SU, SDep::Output, Reg); |
| 445 | Dep.setLatency( |
| 446 | SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr())); |
| 447 | DefSU->addPred(Dep); |
| 448 | |
| 449 | // Update current definition. This can get tricky if the def was about a |
| 450 | // bigger lanemask before. We then have to shrink it and create a new |
| 451 | // VReg2SUnit for the non-overlapping part. |
| 452 | LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask; |
| 453 | LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask; |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 454 | V2SU.SU = SU; |
| 455 | V2SU.LaneMask = OverlapMask; |
Krzysztof Parzyszek | ea9f8ce | 2016-12-16 19:11:56 +0000 | [diff] [blame] | 456 | if (NonOverlapMask.any()) |
Matthias Braun | 4c994ee | 2016-05-25 01:18:00 +0000 | [diff] [blame] | 457 | CurrentVRegDefs.insert(VReg2SUnit(Reg, NonOverlapMask, DefSU)); |
Andrew Trick | 59ac4fb | 2012-01-14 02:17:18 +0000 | [diff] [blame] | 458 | } |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 459 | // If there was no CurrentVRegDefs entry for some lanes yet, create one. |
Krzysztof Parzyszek | ea9f8ce | 2016-12-16 19:11:56 +0000 | [diff] [blame] | 460 | if (LaneMask.any()) |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 461 | CurrentVRegDefs.insert(VReg2SUnit(Reg, LaneMask, SU)); |
Andrew Trick | 59ac4fb | 2012-01-14 02:17:18 +0000 | [diff] [blame] | 462 | } |
| 463 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 464 | /// \brief Adds a register data dependency if the instruction that defines the |
| 465 | /// virtual register used at OperIdx is mapped to an SUnit. Add a register |
| 466 | /// antidependency from this SUnit to instructions that occur later in the same |
| 467 | /// scheduling region if they write the virtual register. |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 468 | /// |
| 469 | /// TODO: Handle ExitSU "uses" properly. |
Andrew Trick | 59ac4fb | 2012-01-14 02:17:18 +0000 | [diff] [blame] | 470 | void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 471 | const MachineInstr *MI = SU->getInstr(); |
| 472 | const MachineOperand &MO = MI->getOperand(OperIdx); |
| 473 | unsigned Reg = MO.getReg(); |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 474 | |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 475 | // Remember the use. Data dependencies will be added when we find the def. |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 476 | LaneBitmask LaneMask = TrackLaneMasks ? getLaneMaskForMO(MO) |
| 477 | : LaneBitmask::getAll(); |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 478 | CurrentVRegUses.insert(VReg2SUnitOperIdx(Reg, LaneMask, OperIdx, SU)); |
| 479 | |
| 480 | // Add antidependences to the following defs of the vreg. |
| 481 | for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg), |
| 482 | CurrentVRegDefs.end())) { |
| 483 | // Ignore defs for unrelated lanes. |
| 484 | LaneBitmask PrevDefLaneMask = V2SU.LaneMask; |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 485 | if ((PrevDefLaneMask & LaneMask).none()) |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 486 | continue; |
| 487 | if (V2SU.SU == SU) |
| 488 | continue; |
| 489 | |
| 490 | V2SU.SU->addPred(SDep(SU, SDep::Anti, Reg)); |
Andrew Trick | 2bc74c2 | 2013-08-30 04:36:57 +0000 | [diff] [blame] | 491 | } |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 492 | } |
Andrew Trick | 59ac4fb | 2012-01-14 02:17:18 +0000 | [diff] [blame] | 493 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 494 | /// Returns true if MI is an instruction we are unable to reason about |
Andrew Trick | da01ba3 | 2012-05-15 18:59:41 +0000 | [diff] [blame] | 495 | /// (like a call or something with unmodeled side effects). |
| 496 | static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) { |
Rafael Espindola | 84921b9 | 2015-10-24 23:11:13 +0000 | [diff] [blame] | 497 | return MI->isCall() || MI->hasUnmodeledSideEffects() || |
Justin Lebar | d98cf00 | 2016-09-10 01:03:20 +0000 | [diff] [blame] | 498 | (MI->hasOrderedMemoryRef() && !MI->isDereferenceableInvariantLoad(AA)); |
Andrew Trick | da01ba3 | 2012-05-15 18:59:41 +0000 | [diff] [blame] | 499 | } |
| 500 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 501 | void ScheduleDAGInstrs::addChainDependency (SUnit *SUa, SUnit *SUb, |
| 502 | unsigned Latency) { |
Eli Friedman | 93f47e5 | 2017-03-09 23:33:36 +0000 | [diff] [blame] | 503 | if (SUa->getInstr()->mayAlias(AAForDep, *SUb->getInstr(), UseTBAA)) { |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 504 | SDep Dep(SUa, SDep::MayAliasMem); |
| 505 | Dep.setLatency(Latency); |
Andrew Trick | baeaabb | 2012-11-06 03:13:46 +0000 | [diff] [blame] | 506 | SUb->addPred(Dep); |
| 507 | } |
Andrew Trick | da01ba3 | 2012-05-15 18:59:41 +0000 | [diff] [blame] | 508 | } |
| 509 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 510 | /// \brief Creates an SUnit for each real instruction, numbered in top-down |
| 511 | /// topological order. The instruction order A < B, implies that no edge exists |
| 512 | /// from B to A. |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 513 | /// |
| 514 | /// Map each real instruction to its SUnit. |
| 515 | /// |
Andrew Trick | 8823dec | 2012-03-14 04:00:41 +0000 | [diff] [blame] | 516 | /// After initSUnits, the SUnits vector cannot be resized and the scheduler may |
| 517 | /// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs |
| 518 | /// instead of pointers. |
| 519 | /// |
| 520 | /// MachineScheduler relies on initSUnits numbering the nodes by their order in |
| 521 | /// the original instruction list. |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 522 | void ScheduleDAGInstrs::initSUnits() { |
| 523 | // We'll be allocating one SUnit for each real instruction in the region, |
| 524 | // which is contained within a basic block. |
Andrew Trick | a53e101 | 2013-08-23 17:48:33 +0000 | [diff] [blame] | 525 | SUnits.reserve(NumRegionInstrs); |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 526 | |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 527 | for (MachineInstr &MI : make_range(RegionBegin, RegionEnd)) { |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 528 | if (MI.isDebugValue()) |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 529 | continue; |
| 530 | |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 531 | SUnit *SU = newSUnit(&MI); |
| 532 | MISUnitMap[&MI] = SU; |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 533 | |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 534 | SU->isCall = MI.isCall(); |
| 535 | SU->isCommutable = MI.isCommutable(); |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 536 | |
| 537 | // Assign the Latency field of SU using target-provided information. |
Andrew Trick | dd79f0f | 2012-10-10 05:43:09 +0000 | [diff] [blame] | 538 | SU->Latency = SchedModel.computeInstrLatency(SU->getInstr()); |
Andrew Trick | 880e573 | 2013-12-05 17:55:58 +0000 | [diff] [blame] | 539 | |
Andrew Trick | 1766f93 | 2014-04-18 17:35:08 +0000 | [diff] [blame] | 540 | // If this SUnit uses a reserved or unbuffered resource, mark it as such. |
| 541 | // |
Alp Toker | beaca19 | 2014-05-15 01:52:21 +0000 | [diff] [blame] | 542 | // Reserved resources block an instruction from issuing and stall the |
Andrew Trick | 1766f93 | 2014-04-18 17:35:08 +0000 | [diff] [blame] | 543 | // entire pipeline. These are identified by BufferSize=0. |
| 544 | // |
Alp Toker | beaca19 | 2014-05-15 01:52:21 +0000 | [diff] [blame] | 545 | // Unbuffered resources prevent execution of subsequent instructions that |
Andrew Trick | 1766f93 | 2014-04-18 17:35:08 +0000 | [diff] [blame] | 546 | // require the same resources. This is used for in-order execution pipelines |
| 547 | // within an out-of-order core. These are identified by BufferSize=1. |
Andrew Trick | 880e573 | 2013-12-05 17:55:58 +0000 | [diff] [blame] | 548 | if (SchedModel.hasInstrSchedModel()) { |
| 549 | const MCSchedClassDesc *SC = getSchedClass(SU); |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 550 | for (const MCWriteProcResEntry &PRE : |
| 551 | make_range(SchedModel.getWriteProcResBegin(SC), |
| 552 | SchedModel.getWriteProcResEnd(SC))) { |
| 553 | switch (SchedModel.getProcResource(PRE.ProcResourceIdx)->BufferSize) { |
Andrew Trick | 5a22df4 | 2013-12-05 17:56:02 +0000 | [diff] [blame] | 554 | case 0: |
| 555 | SU->hasReservedResource = true; |
| 556 | break; |
| 557 | case 1: |
Andrew Trick | 880e573 | 2013-12-05 17:55:58 +0000 | [diff] [blame] | 558 | SU->isUnbuffered = true; |
| 559 | break; |
Andrew Trick | 5a22df4 | 2013-12-05 17:56:02 +0000 | [diff] [blame] | 560 | default: |
| 561 | break; |
Andrew Trick | 880e573 | 2013-12-05 17:55:58 +0000 | [diff] [blame] | 562 | } |
| 563 | } |
| 564 | } |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 565 | } |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 566 | } |
| 567 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 568 | class ScheduleDAGInstrs::Value2SUsMap : public MapVector<ValueType, SUList> { |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 569 | /// Current total number of SUs in map. |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 570 | unsigned NumNodes = 0; |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 571 | |
| 572 | /// 1 for loads, 0 for stores. (see comment in SUList) |
| 573 | unsigned TrueMemOrderLatency; |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 574 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 575 | public: |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 576 | Value2SUsMap(unsigned lat = 0) : TrueMemOrderLatency(lat) {} |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 577 | |
| 578 | /// To keep NumNodes up to date, insert() is used instead of |
| 579 | /// this operator w/ push_back(). |
| 580 | ValueType &operator[](const SUList &Key) { |
| 581 | llvm_unreachable("Don't use. Use insert() instead."); }; |
| 582 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 583 | /// Adds SU to the SUList of V. If Map grows huge, reduce its size by calling |
| 584 | /// reduce(). |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 585 | void inline insert(SUnit *SU, ValueType V) { |
| 586 | MapVector::operator[](V).push_back(SU); |
| 587 | NumNodes++; |
| 588 | } |
| 589 | |
| 590 | /// Clears the list of SUs mapped to V. |
| 591 | void inline clearList(ValueType V) { |
| 592 | iterator Itr = find(V); |
| 593 | if (Itr != end()) { |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 594 | assert(NumNodes >= Itr->second.size()); |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 595 | NumNodes -= Itr->second.size(); |
| 596 | |
| 597 | Itr->second.clear(); |
| 598 | } |
| 599 | } |
| 600 | |
| 601 | /// Clears map from all contents. |
| 602 | void clear() { |
| 603 | MapVector<ValueType, SUList>::clear(); |
| 604 | NumNodes = 0; |
| 605 | } |
| 606 | |
| 607 | unsigned inline size() const { return NumNodes; } |
| 608 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 609 | /// Counts the number of SUs in this map after a reduction. |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 610 | void reComputeSize() { |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 611 | NumNodes = 0; |
| 612 | for (auto &I : *this) |
| 613 | NumNodes += I.second.size(); |
| 614 | } |
| 615 | |
| 616 | unsigned inline getTrueMemOrderLatency() const { |
| 617 | return TrueMemOrderLatency; |
| 618 | } |
| 619 | |
| 620 | void dump(); |
| 621 | }; |
| 622 | |
| 623 | void ScheduleDAGInstrs::addChainDependencies(SUnit *SU, |
| 624 | Value2SUsMap &Val2SUsMap) { |
| 625 | for (auto &I : Val2SUsMap) |
| 626 | addChainDependencies(SU, I.second, |
| 627 | Val2SUsMap.getTrueMemOrderLatency()); |
| 628 | } |
| 629 | |
| 630 | void ScheduleDAGInstrs::addChainDependencies(SUnit *SU, |
| 631 | Value2SUsMap &Val2SUsMap, |
| 632 | ValueType V) { |
| 633 | Value2SUsMap::iterator Itr = Val2SUsMap.find(V); |
| 634 | if (Itr != Val2SUsMap.end()) |
| 635 | addChainDependencies(SU, Itr->second, |
| 636 | Val2SUsMap.getTrueMemOrderLatency()); |
| 637 | } |
| 638 | |
| 639 | void ScheduleDAGInstrs::addBarrierChain(Value2SUsMap &map) { |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 640 | assert(BarrierChain != nullptr); |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 641 | |
| 642 | for (auto &I : map) { |
| 643 | SUList &sus = I.second; |
| 644 | for (auto *SU : sus) |
| 645 | SU->addPredBarrier(BarrierChain); |
| 646 | } |
| 647 | map.clear(); |
| 648 | } |
| 649 | |
| 650 | void ScheduleDAGInstrs::insertBarrierChain(Value2SUsMap &map) { |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 651 | assert(BarrierChain != nullptr); |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 652 | |
| 653 | // Go through all lists of SUs. |
| 654 | for (Value2SUsMap::iterator I = map.begin(), EE = map.end(); I != EE;) { |
| 655 | Value2SUsMap::iterator CurrItr = I++; |
| 656 | SUList &sus = CurrItr->second; |
| 657 | SUList::iterator SUItr = sus.begin(), SUEE = sus.end(); |
| 658 | for (; SUItr != SUEE; ++SUItr) { |
| 659 | // Stop on BarrierChain or any instruction above it. |
| 660 | if ((*SUItr)->NodeNum <= BarrierChain->NodeNum) |
| 661 | break; |
| 662 | |
| 663 | (*SUItr)->addPredBarrier(BarrierChain); |
| 664 | } |
| 665 | |
| 666 | // Remove also the BarrierChain from list if present. |
NAKAMURA Takumi | bc46f62 | 2016-05-02 17:29:55 +0000 | [diff] [blame] | 667 | if (SUItr != SUEE && *SUItr == BarrierChain) |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 668 | SUItr++; |
| 669 | |
| 670 | // Remove all SUs that are now successors of BarrierChain. |
| 671 | if (SUItr != sus.begin()) |
| 672 | sus.erase(sus.begin(), SUItr); |
| 673 | } |
| 674 | |
| 675 | // Remove all entries with empty su lists. |
| 676 | map.remove_if([&](std::pair<ValueType, SUList> &mapEntry) { |
| 677 | return (mapEntry.second.empty()); }); |
| 678 | |
| 679 | // Recompute the size of the map (NumNodes). |
| 680 | map.reComputeSize(); |
| 681 | } |
| 682 | |
Andrew Trick | 8863992 | 2012-04-24 17:56:43 +0000 | [diff] [blame] | 683 | void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, |
Andrew Trick | 1a83134 | 2013-08-30 03:49:48 +0000 | [diff] [blame] | 684 | RegPressureTracker *RPTracker, |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 685 | PressureDiffs *PDiffs, |
Matthias Braun | d4f6409 | 2016-01-20 00:23:32 +0000 | [diff] [blame] | 686 | LiveIntervals *LIS, |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 687 | bool TrackLaneMasks) { |
Eric Christopher | 2c63549 | 2015-01-27 07:54:39 +0000 | [diff] [blame] | 688 | const TargetSubtargetInfo &ST = MF.getSubtarget(); |
Hal Finkel | b350ffd | 2013-08-29 03:25:05 +0000 | [diff] [blame] | 689 | bool UseAA = EnableAASchedMI.getNumOccurrences() > 0 ? EnableAASchedMI |
| 690 | : ST.useAA(); |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 691 | AAForDep = UseAA ? AA : nullptr; |
| 692 | |
| 693 | BarrierChain = nullptr; |
Hal Finkel | b350ffd | 2013-08-29 03:25:05 +0000 | [diff] [blame] | 694 | |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 695 | this->TrackLaneMasks = TrackLaneMasks; |
Andrew Trick | 310190e | 2013-09-04 21:00:02 +0000 | [diff] [blame] | 696 | MISUnitMap.clear(); |
| 697 | ScheduleDAG::clearDAG(); |
| 698 | |
Andrew Trick | 46cc9a4 | 2012-02-22 06:08:11 +0000 | [diff] [blame] | 699 | // Create an SUnit for each real instruction. |
| 700 | initSUnits(); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 701 | |
Andrew Trick | 1a83134 | 2013-08-30 03:49:48 +0000 | [diff] [blame] | 702 | if (PDiffs) |
| 703 | PDiffs->init(SUnits.size()); |
| 704 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 705 | // We build scheduling units by walking a block's instruction list |
| 706 | // from bottom to top. |
Dan Gohman | 3aab10b | 2008-12-04 01:35:46 +0000 | [diff] [blame] | 707 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 708 | // Each MIs' memory operand(s) is analyzed to a list of underlying |
Jonas Paulsson | 2293685 | 2016-02-04 13:08:48 +0000 | [diff] [blame] | 709 | // objects. The SU is then inserted in the SUList(s) mapped from the |
| 710 | // Value(s). Each Value thus gets mapped to lists of SUs depending |
| 711 | // on it, stores and loads kept separately. Two SUs are trivially |
| 712 | // non-aliasing if they both depend on only identified Values and do |
| 713 | // not share any common Value. |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 714 | Value2SUsMap Stores, Loads(1 /*TrueMemOrderLatency*/); |
Dan Gohman | 3aab10b | 2008-12-04 01:35:46 +0000 | [diff] [blame] | 715 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 716 | // Certain memory accesses are known to not alias any SU in Stores |
| 717 | // or Loads, and have therefore their own 'NonAlias' |
| 718 | // domain. E.g. spill / reload instructions never alias LLVM I/R |
Jonas Paulsson | 2293685 | 2016-02-04 13:08:48 +0000 | [diff] [blame] | 719 | // Values. It would be nice to assume that this type of memory |
| 720 | // accesses always have a proper memory operand modelling, and are |
| 721 | // therefore never unanalyzable, but this is conservatively not |
| 722 | // done. |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 723 | Value2SUsMap NonAliasStores, NonAliasLoads(1 /*TrueMemOrderLatency*/); |
| 724 | |
Dale Johannesen | 49de060 | 2010-03-10 22:13:47 +0000 | [diff] [blame] | 725 | // Remove any stale debug info; sometimes BuildSchedGraph is called again |
| 726 | // without emitting the info from the previous call. |
Devang Patel | e5feef0 | 2011-06-02 20:07:12 +0000 | [diff] [blame] | 727 | DbgValues.clear(); |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 728 | FirstDbgValue = nullptr; |
Dale Johannesen | 49de060 | 2010-03-10 22:13:47 +0000 | [diff] [blame] | 729 | |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 730 | assert(Defs.empty() && Uses.empty() && |
| 731 | "Only BuildGraph should update Defs/Uses"); |
Michael Ilseman | 3e3194f | 2013-01-21 18:18:53 +0000 | [diff] [blame] | 732 | Defs.setUniverse(TRI->getNumRegs()); |
| 733 | Uses.setUniverse(TRI->getNumRegs()); |
Andrew Trick | 2e116a4 | 2011-05-06 21:52:52 +0000 | [diff] [blame] | 734 | |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 735 | assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs"); |
| 736 | assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses"); |
| 737 | unsigned NumVirtRegs = MRI.getNumVirtRegs(); |
| 738 | CurrentVRegDefs.setUniverse(NumVirtRegs); |
| 739 | CurrentVRegUses.setUniverse(NumVirtRegs); |
| 740 | |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 741 | // Model data dependencies between instructions being scheduled and the |
| 742 | // ExitSU. |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 743 | addSchedBarrierDeps(); |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 744 | |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 745 | // Walk the list of instructions, from bottom moving up. |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 746 | MachineInstr *DbgMI = nullptr; |
Andrew Trick | 8c207e4 | 2012-03-09 04:29:02 +0000 | [diff] [blame] | 747 | for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin; |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 748 | MII != MIE; --MII) { |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 749 | MachineInstr &MI = *std::prev(MII); |
| 750 | if (DbgMI) { |
| 751 | DbgValues.push_back(std::make_pair(DbgMI, &MI)); |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 752 | DbgMI = nullptr; |
Devang Patel | e5feef0 | 2011-06-02 20:07:12 +0000 | [diff] [blame] | 753 | } |
| 754 | |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 755 | if (MI.isDebugValue()) { |
| 756 | DbgMI = &MI; |
Dale Johannesen | 49de060 | 2010-03-10 22:13:47 +0000 | [diff] [blame] | 757 | continue; |
| 758 | } |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 759 | SUnit *SU = MISUnitMap[&MI]; |
Andrew Trick | 1a83134 | 2013-08-30 03:49:48 +0000 | [diff] [blame] | 760 | assert(SU && "No SUnit mapped to this MI"); |
| 761 | |
Andrew Trick | 8863992 | 2012-04-24 17:56:43 +0000 | [diff] [blame] | 762 | if (RPTracker) { |
Matthias Braun | b505c76 | 2016-01-12 22:57:35 +0000 | [diff] [blame] | 763 | RegisterOperands RegOpers; |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 764 | RegOpers.collect(MI, *TRI, MRI, TrackLaneMasks, false); |
Matthias Braun | d4f6409 | 2016-01-20 00:23:32 +0000 | [diff] [blame] | 765 | if (TrackLaneMasks) { |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 766 | SlotIndex SlotIdx = LIS->getInstructionIndex(MI); |
Matthias Braun | d4f6409 | 2016-01-20 00:23:32 +0000 | [diff] [blame] | 767 | RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx); |
| 768 | } |
Matthias Braun | b505c76 | 2016-01-12 22:57:35 +0000 | [diff] [blame] | 769 | if (PDiffs != nullptr) |
| 770 | PDiffs->addInstruction(SU->NodeNum, RegOpers, MRI); |
| 771 | |
| 772 | RPTracker->recedeSkipDebugValues(); |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 773 | assert(&*RPTracker->getPos() == &MI && "RPTracker in sync"); |
Matthias Braun | b505c76 | 2016-01-12 22:57:35 +0000 | [diff] [blame] | 774 | RPTracker->recede(RegOpers); |
Andrew Trick | 8863992 | 2012-04-24 17:56:43 +0000 | [diff] [blame] | 775 | } |
Devang Patel | e5feef0 | 2011-06-02 20:07:12 +0000 | [diff] [blame] | 776 | |
Rafael Espindola | b1f25f1 | 2014-03-07 06:08:31 +0000 | [diff] [blame] | 777 | assert( |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 778 | (CanHandleTerminators || (!MI.isTerminator() && !MI.isPosition())) && |
Rafael Espindola | b1f25f1 | 2014-03-07 06:08:31 +0000 | [diff] [blame] | 779 | "Cannot schedule terminators or labels!"); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 780 | |
Dan Gohman | 3aab10b | 2008-12-04 01:35:46 +0000 | [diff] [blame] | 781 | // Add register-based dependencies (data, anti, and output). |
Krzysztof Parzyszek | a356bb7 | 2016-05-10 16:50:30 +0000 | [diff] [blame] | 782 | // For some instructions (calls, returns, inline-asm, etc.) there can |
| 783 | // be explicit uses and implicit defs, in which case the use will appear |
| 784 | // on the operand list before the def. Do two passes over the operand |
| 785 | // list to make sure that defs are processed before any uses. |
Andrew Trick | ec25648 | 2012-12-18 20:53:01 +0000 | [diff] [blame] | 786 | bool HasVRegDef = false; |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 787 | for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) { |
| 788 | const MachineOperand &MO = MI.getOperand(j); |
Krzysztof Parzyszek | a356bb7 | 2016-05-10 16:50:30 +0000 | [diff] [blame] | 789 | if (!MO.isReg() || !MO.isDef()) |
| 790 | continue; |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 791 | unsigned Reg = MO.getReg(); |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 792 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) { |
Andrew Trick | dbee9d8 | 2012-01-14 02:17:15 +0000 | [diff] [blame] | 793 | addPhysRegDeps(SU, j); |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 794 | } else if (TargetRegisterInfo::isVirtualRegister(Reg)) { |
Krzysztof Parzyszek | a356bb7 | 2016-05-10 16:50:30 +0000 | [diff] [blame] | 795 | HasVRegDef = true; |
| 796 | addVRegDefDeps(SU, j); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 797 | } |
| 798 | } |
Krzysztof Parzyszek | a356bb7 | 2016-05-10 16:50:30 +0000 | [diff] [blame] | 799 | // Now process all uses. |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 800 | for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) { |
| 801 | const MachineOperand &MO = MI.getOperand(j); |
Matthias Braun | 8a5b467 | 2016-05-10 20:11:58 +0000 | [diff] [blame] | 802 | // Only look at use operands. |
| 803 | // We do not need to check for MO.readsReg() here because subsequent |
| 804 | // subregister defs will get output dependence edges and need no |
| 805 | // additional use dependencies. |
Krzysztof Parzyszek | a356bb7 | 2016-05-10 16:50:30 +0000 | [diff] [blame] | 806 | if (!MO.isReg() || !MO.isUse()) |
| 807 | continue; |
| 808 | unsigned Reg = MO.getReg(); |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 809 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) { |
Krzysztof Parzyszek | a356bb7 | 2016-05-10 16:50:30 +0000 | [diff] [blame] | 810 | addPhysRegDeps(SU, j); |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 811 | } else if (TargetRegisterInfo::isVirtualRegister(Reg) && MO.readsReg()) { |
Krzysztof Parzyszek | a356bb7 | 2016-05-10 16:50:30 +0000 | [diff] [blame] | 812 | addVRegUseDeps(SU, j); |
Matthias Braun | 111603f | 2016-11-10 22:11:00 +0000 | [diff] [blame] | 813 | } |
Krzysztof Parzyszek | a356bb7 | 2016-05-10 16:50:30 +0000 | [diff] [blame] | 814 | } |
| 815 | |
Andrew Trick | ec25648 | 2012-12-18 20:53:01 +0000 | [diff] [blame] | 816 | // If we haven't seen any uses in this scheduling region, create a |
| 817 | // dependence edge to ExitSU to model the live-out latency. This is required |
| 818 | // for vreg defs with no in-region use, and prefetches with no vreg def. |
| 819 | // |
| 820 | // FIXME: NumDataSuccs would be more precise than NumSuccs here. This |
| 821 | // check currently relies on being called before adding chain deps. |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 822 | if (SU->NumSuccs == 0 && SU->Latency > 1 && (HasVRegDef || MI.mayLoad())) { |
Andrew Trick | ec25648 | 2012-12-18 20:53:01 +0000 | [diff] [blame] | 823 | SDep Dep(SU, SDep::Artificial); |
| 824 | Dep.setLatency(SU->Latency - 1); |
| 825 | ExitSU.addPred(Dep); |
| 826 | } |
Dan Gohman | 3aab10b | 2008-12-04 01:35:46 +0000 | [diff] [blame] | 827 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 828 | // Add memory dependencies (Note: isStoreToStackSlot and |
| 829 | // isLoadFromStackSLot are not usable after stack slots are lowered to |
| 830 | // actual addresses). |
| 831 | |
| 832 | // This is a barrier event that acts as a pivotal node in the DAG. |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 833 | if (isGlobalMemoryObject(AA, &MI)) { |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 834 | |
| 835 | // Become the barrier chain. |
David Goodwin | d2f9c04 | 2009-11-09 19:22:17 +0000 | [diff] [blame] | 836 | if (BarrierChain) |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 837 | BarrierChain->addPredBarrier(SU); |
David Goodwin | d2f9c04 | 2009-11-09 19:22:17 +0000 | [diff] [blame] | 838 | BarrierChain = SU; |
| 839 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 840 | DEBUG(dbgs() << "Global memory object and new barrier chain: SU(" |
| 841 | << BarrierChain->NodeNum << ").\n";); |
Tom Stellard | 3e01d47 | 2014-12-08 23:36:48 +0000 | [diff] [blame] | 842 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 843 | // Add dependencies against everything below it and clear maps. |
| 844 | addBarrierChain(Stores); |
| 845 | addBarrierChain(Loads); |
| 846 | addBarrierChain(NonAliasStores); |
| 847 | addBarrierChain(NonAliasLoads); |
Hal Finkel | 66859ae | 2012-12-10 18:49:16 +0000 | [diff] [blame] | 848 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 849 | continue; |
| 850 | } |
| 851 | |
| 852 | // If it's not a store or a variant load, we're done. |
Justin Lebar | d98cf00 | 2016-09-10 01:03:20 +0000 | [diff] [blame] | 853 | if (!MI.mayStore() && |
| 854 | !(MI.mayLoad() && !MI.isDereferenceableInvariantLoad(AA))) |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 855 | continue; |
| 856 | |
| 857 | // Always add dependecy edge to BarrierChain if present. |
| 858 | if (BarrierChain) |
| 859 | BarrierChain->addPredBarrier(SU); |
| 860 | |
| 861 | // Find the underlying objects for MI. The Objs vector is either |
| 862 | // empty, or filled with the Values of memory locations which this |
| 863 | // SU depends on. An empty vector means the memory location is |
Jonas Paulsson | 98963fe | 2016-02-15 16:43:15 +0000 | [diff] [blame] | 864 | // unknown, and may alias anything. |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 865 | UnderlyingObjectsVector Objs; |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 866 | getUnderlyingObjectsForInstr(&MI, MFI, Objs, MF.getDataLayout()); |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 867 | |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 868 | if (MI.mayStore()) { |
Hal Finkel | 66859ae | 2012-12-10 18:49:16 +0000 | [diff] [blame] | 869 | if (Objs.empty()) { |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 870 | // An unknown store depends on all stores and loads. |
| 871 | addChainDependencies(SU, Stores); |
| 872 | addChainDependencies(SU, NonAliasStores); |
| 873 | addChainDependencies(SU, Loads); |
| 874 | addChainDependencies(SU, NonAliasLoads); |
| 875 | |
| 876 | // Map this store to 'UnknownValue'. |
| 877 | Stores.insert(SU, UnknownValue); |
Chandler Carruth | b472856 | 2016-03-31 21:55:58 +0000 | [diff] [blame] | 878 | } else { |
| 879 | // Add precise dependencies against all previously seen memory |
| 880 | // accesses mapped to the same Value(s). |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 881 | for (const UnderlyingObject &UnderlObj : Objs) { |
| 882 | ValueType V = UnderlObj.getValue(); |
| 883 | bool ThisMayAlias = UnderlObj.mayAlias(); |
Chandler Carruth | b472856 | 2016-03-31 21:55:58 +0000 | [diff] [blame] | 884 | |
| 885 | // Add dependencies to previous stores and loads mapped to V. |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 886 | addChainDependencies(SU, (ThisMayAlias ? Stores : NonAliasStores), V); |
Chandler Carruth | b472856 | 2016-03-31 21:55:58 +0000 | [diff] [blame] | 887 | addChainDependencies(SU, (ThisMayAlias ? Loads : NonAliasLoads), V); |
Geoff Berry | c0739d8 | 2016-04-12 15:50:19 +0000 | [diff] [blame] | 888 | } |
| 889 | // Update the store map after all chains have been added to avoid adding |
| 890 | // self-loop edge if multiple underlying objects are present. |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 891 | for (const UnderlyingObject &UnderlObj : Objs) { |
| 892 | ValueType V = UnderlObj.getValue(); |
| 893 | bool ThisMayAlias = UnderlObj.mayAlias(); |
Chandler Carruth | b472856 | 2016-03-31 21:55:58 +0000 | [diff] [blame] | 894 | |
| 895 | // Map this store to V. |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 896 | (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V); |
Chandler Carruth | b472856 | 2016-03-31 21:55:58 +0000 | [diff] [blame] | 897 | } |
| 898 | // The store may have dependencies to unanalyzable loads and |
| 899 | // stores. |
| 900 | addChainDependencies(SU, Loads, UnknownValue); |
| 901 | addChainDependencies(SU, Stores, UnknownValue); |
Hal Finkel | 66859ae | 2012-12-10 18:49:16 +0000 | [diff] [blame] | 902 | } |
Chandler Carruth | b472856 | 2016-03-31 21:55:58 +0000 | [diff] [blame] | 903 | } else { // SU is a load. |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 904 | if (Objs.empty()) { |
| 905 | // An unknown load depends on all stores. |
| 906 | addChainDependencies(SU, Stores); |
| 907 | addChainDependencies(SU, NonAliasStores); |
| 908 | |
| 909 | Loads.insert(SU, UnknownValue); |
Chandler Carruth | b472856 | 2016-03-31 21:55:58 +0000 | [diff] [blame] | 910 | } else { |
Geoff Berry | 6381713 | 2016-04-14 21:31:07 +0000 | [diff] [blame] | 911 | for (const UnderlyingObject &UnderlObj : Objs) { |
| 912 | ValueType V = UnderlObj.getValue(); |
| 913 | bool ThisMayAlias = UnderlObj.mayAlias(); |
Chandler Carruth | b472856 | 2016-03-31 21:55:58 +0000 | [diff] [blame] | 914 | |
| 915 | // Add precise dependencies against all previously seen stores |
| 916 | // mapping to the same Value(s). |
| 917 | addChainDependencies(SU, (ThisMayAlias ? Stores : NonAliasStores), V); |
| 918 | |
| 919 | // Map this load to V. |
| 920 | (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V); |
| 921 | } |
| 922 | // The load may have dependencies to unanalyzable stores. |
| 923 | addChainDependencies(SU, Stores, UnknownValue); |
Hal Finkel | 66859ae | 2012-12-10 18:49:16 +0000 | [diff] [blame] | 924 | } |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 925 | } |
| 926 | |
| 927 | // Reduce maps if they grow huge. |
| 928 | if (Stores.size() + Loads.size() >= HugeRegion) { |
| 929 | DEBUG(dbgs() << "Reducing Stores and Loads maps.\n";); |
Mehdi Amini | 59ae854 | 2016-04-16 04:58:30 +0000 | [diff] [blame] | 930 | reduceHugeMemNodeMaps(Stores, Loads, getReductionSize()); |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 931 | } |
| 932 | if (NonAliasStores.size() + NonAliasLoads.size() >= HugeRegion) { |
| 933 | DEBUG(dbgs() << "Reducing NonAliasStores and NonAliasLoads maps.\n";); |
Mehdi Amini | 59ae854 | 2016-04-16 04:58:30 +0000 | [diff] [blame] | 934 | reduceHugeMemNodeMaps(NonAliasStores, NonAliasLoads, getReductionSize()); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 935 | } |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 936 | } |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 937 | |
Andrew Trick | b767d1e | 2012-12-01 01:22:49 +0000 | [diff] [blame] | 938 | if (DbgMI) |
| 939 | FirstDbgValue = DbgMI; |
Dan Gohman | 619ef48 | 2009-01-15 19:20:50 +0000 | [diff] [blame] | 940 | |
Andrew Trick | d675a4c | 2012-02-23 01:52:38 +0000 | [diff] [blame] | 941 | Defs.clear(); |
| 942 | Uses.clear(); |
Matthias Braun | 97d0ffb | 2015-12-04 01:51:19 +0000 | [diff] [blame] | 943 | CurrentVRegDefs.clear(); |
| 944 | CurrentVRegUses.clear(); |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 945 | } |
| 946 | |
| 947 | raw_ostream &llvm::operator<<(raw_ostream &OS, const PseudoSourceValue* PSV) { |
| 948 | PSV->printCustom(OS); |
| 949 | return OS; |
| 950 | } |
| 951 | |
| 952 | void ScheduleDAGInstrs::Value2SUsMap::dump() { |
| 953 | for (auto &Itr : *this) { |
| 954 | if (Itr.first.is<const Value*>()) { |
| 955 | const Value *V = Itr.first.get<const Value*>(); |
| 956 | if (isa<UndefValue>(V)) |
| 957 | dbgs() << "Unknown"; |
| 958 | else |
| 959 | V->printAsOperand(dbgs()); |
| 960 | } |
| 961 | else if (Itr.first.is<const PseudoSourceValue*>()) |
| 962 | dbgs() << Itr.first.get<const PseudoSourceValue*>(); |
| 963 | else |
| 964 | llvm_unreachable("Unknown Value type."); |
| 965 | |
| 966 | dbgs() << " : "; |
| 967 | dumpSUList(Itr.second); |
| 968 | } |
| 969 | } |
| 970 | |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 971 | void ScheduleDAGInstrs::reduceHugeMemNodeMaps(Value2SUsMap &stores, |
| 972 | Value2SUsMap &loads, unsigned N) { |
| 973 | DEBUG(dbgs() << "Before reduction:\nStoring SUnits:\n"; |
| 974 | stores.dump(); |
| 975 | dbgs() << "Loading SUnits:\n"; |
| 976 | loads.dump()); |
| 977 | |
| 978 | // Insert all SU's NodeNums into a vector and sort it. |
| 979 | std::vector<unsigned> NodeNums; |
| 980 | NodeNums.reserve(stores.size() + loads.size()); |
| 981 | for (auto &I : stores) |
| 982 | for (auto *SU : I.second) |
| 983 | NodeNums.push_back(SU->NodeNum); |
| 984 | for (auto &I : loads) |
| 985 | for (auto *SU : I.second) |
| 986 | NodeNums.push_back(SU->NodeNum); |
| 987 | std::sort(NodeNums.begin(), NodeNums.end()); |
| 988 | |
| 989 | // The N last elements in NodeNums will be removed, and the SU with |
| 990 | // the lowest NodeNum of them will become the new BarrierChain to |
| 991 | // let the not yet seen SUs have a dependency to the removed SUs. |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 992 | assert(N <= NodeNums.size()); |
Jonas Paulsson | ac29f01 | 2016-02-03 17:52:29 +0000 | [diff] [blame] | 993 | SUnit *newBarrierChain = &SUnits[*(NodeNums.end() - N)]; |
| 994 | if (BarrierChain) { |
| 995 | // The aliasing and non-aliasing maps reduce independently of each |
| 996 | // other, but share a common BarrierChain. Check if the |
| 997 | // newBarrierChain is above the former one. If it is not, it may |
| 998 | // introduce a loop to use newBarrierChain, so keep the old one. |
| 999 | if (newBarrierChain->NodeNum < BarrierChain->NodeNum) { |
| 1000 | BarrierChain->addPredBarrier(newBarrierChain); |
| 1001 | BarrierChain = newBarrierChain; |
| 1002 | DEBUG(dbgs() << "Inserting new barrier chain: SU(" |
| 1003 | << BarrierChain->NodeNum << ").\n";); |
| 1004 | } |
| 1005 | else |
| 1006 | DEBUG(dbgs() << "Keeping old barrier chain: SU(" |
| 1007 | << BarrierChain->NodeNum << ").\n";); |
| 1008 | } |
| 1009 | else |
| 1010 | BarrierChain = newBarrierChain; |
| 1011 | |
| 1012 | insertBarrierChain(stores); |
| 1013 | insertBarrierChain(loads); |
| 1014 | |
| 1015 | DEBUG(dbgs() << "After reduction:\nStoring SUnits:\n"; |
| 1016 | stores.dump(); |
| 1017 | dbgs() << "Loading SUnits:\n"; |
| 1018 | loads.dump()); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 1019 | } |
| 1020 | |
Matthias Braun | 868bbd4 | 2017-05-27 02:50:50 +0000 | [diff] [blame] | 1021 | static void toggleKills(const MachineRegisterInfo &MRI, LivePhysRegs &LiveRegs, |
| 1022 | MachineInstr &MI, bool addToLiveRegs) { |
| 1023 | for (MachineOperand &MO : MI.operands()) { |
| 1024 | if (!MO.isReg() || !MO.readsReg()) |
| 1025 | continue; |
| 1026 | unsigned Reg = MO.getReg(); |
| 1027 | if (!Reg) |
| 1028 | continue; |
Andrew Trick | 6b104f8 | 2013-12-28 21:56:55 +0000 | [diff] [blame] | 1029 | |
Matthias Braun | 868bbd4 | 2017-05-27 02:50:50 +0000 | [diff] [blame] | 1030 | // Things that are available after the instruction are killed by it. |
| 1031 | bool IsKill = LiveRegs.available(MRI, Reg); |
| 1032 | MO.setIsKill(IsKill); |
Matthias Braun | e2ae001 | 2017-06-27 00:58:48 +0000 | [diff] [blame] | 1033 | if (addToLiveRegs) |
Matthias Braun | 868bbd4 | 2017-05-27 02:50:50 +0000 | [diff] [blame] | 1034 | LiveRegs.addReg(Reg); |
Andrew Trick | 6b104f8 | 2013-12-28 21:56:55 +0000 | [diff] [blame] | 1035 | } |
| 1036 | } |
| 1037 | |
Matthias Braun | 868bbd4 | 2017-05-27 02:50:50 +0000 | [diff] [blame] | 1038 | void ScheduleDAGInstrs::fixupKills(MachineBasicBlock &MBB) { |
| 1039 | DEBUG(dbgs() << "Fixup kills for BB#" << MBB.getNumber() << '\n'); |
Pete Cooper | 300069a | 2015-05-04 16:52:06 +0000 | [diff] [blame] | 1040 | |
Matthias Braun | 868bbd4 | 2017-05-27 02:50:50 +0000 | [diff] [blame] | 1041 | LiveRegs.init(*TRI); |
| 1042 | LiveRegs.addLiveOuts(MBB); |
Andrew Trick | 6b104f8 | 2013-12-28 21:56:55 +0000 | [diff] [blame] | 1043 | |
| 1044 | // Examine block from end to start... |
Matthias Braun | 868bbd4 | 2017-05-27 02:50:50 +0000 | [diff] [blame] | 1045 | for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) { |
Duncan P. N. Exon Smith | b77911b | 2016-07-01 16:21:48 +0000 | [diff] [blame] | 1046 | if (MI.isDebugValue()) |
Andrew Trick | 6b104f8 | 2013-12-28 21:56:55 +0000 | [diff] [blame] | 1047 | continue; |
| 1048 | |
| 1049 | // Update liveness. Registers that are defed but not used in this |
| 1050 | // instruction are now dead. Mark register and all subregs as they |
| 1051 | // are completely defined. |
Matthias Braun | 868bbd4 | 2017-05-27 02:50:50 +0000 | [diff] [blame] | 1052 | for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { |
| 1053 | const MachineOperand &MO = *O; |
| 1054 | if (MO.isReg()) { |
| 1055 | if (!MO.isDef()) |
| 1056 | continue; |
| 1057 | unsigned Reg = MO.getReg(); |
| 1058 | if (!Reg) |
| 1059 | continue; |
| 1060 | LiveRegs.removeReg(Reg); |
| 1061 | } else if (MO.isRegMask()) { |
| 1062 | LiveRegs.removeRegsInMask(MO); |
| 1063 | } |
Andrew Trick | 6b104f8 | 2013-12-28 21:56:55 +0000 | [diff] [blame] | 1064 | } |
| 1065 | |
Matthias Braun | 868bbd4 | 2017-05-27 02:50:50 +0000 | [diff] [blame] | 1066 | // If there is a bundle header fix it up first. |
| 1067 | if (!MI.isBundled()) { |
| 1068 | toggleKills(MRI, LiveRegs, MI, true); |
| 1069 | } else { |
| 1070 | MachineBasicBlock::instr_iterator First = MI.getIterator(); |
| 1071 | if (MI.isBundle()) { |
| 1072 | toggleKills(MRI, LiveRegs, MI, false); |
| 1073 | ++First; |
Andrew Trick | 6b104f8 | 2013-12-28 21:56:55 +0000 | [diff] [blame] | 1074 | } |
Matthias Braun | 868bbd4 | 2017-05-27 02:50:50 +0000 | [diff] [blame] | 1075 | // Some targets make the (questionable) assumtion that the instructions |
| 1076 | // inside the bundle are ordered and consequently only the last use of |
| 1077 | // a register inside the bundle can kill it. |
| 1078 | MachineBasicBlock::instr_iterator I = std::next(First); |
| 1079 | while (I->isBundledWithSucc()) |
| 1080 | ++I; |
| 1081 | do { |
| 1082 | if (!I->isDebugValue()) |
| 1083 | toggleKills(MRI, LiveRegs, *I, true); |
| 1084 | --I; |
| 1085 | } while(I != First); |
Andrew Trick | 6b104f8 | 2013-12-28 21:56:55 +0000 | [diff] [blame] | 1086 | } |
| 1087 | } |
| 1088 | } |
| 1089 | |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 1090 | void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { |
Matthias Braun | 8c209aa | 2017-01-28 02:02:38 +0000 | [diff] [blame] | 1091 | // Cannot completely remove virtual function even in release mode. |
Manman Ren | 19f49ac | 2012-09-11 22:23:19 +0000 | [diff] [blame] | 1092 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 1093 | SU->getInstr()->dump(); |
Manman Ren | 742534c | 2012-09-06 19:06:06 +0000 | [diff] [blame] | 1094 | #endif |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 1095 | } |
| 1096 | |
| 1097 | std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { |
Alp Toker | e69170a | 2014-06-26 22:52:05 +0000 | [diff] [blame] | 1098 | std::string s; |
| 1099 | raw_string_ostream oss(s); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 1100 | if (SU == &EntrySU) |
| 1101 | oss << "<entry>"; |
| 1102 | else if (SU == &ExitSU) |
| 1103 | oss << "<exit>"; |
| 1104 | else |
Eric Christopher | 1cdefae | 2015-02-27 00:11:34 +0000 | [diff] [blame] | 1105 | SU->getInstr()->print(oss, /*SkipOpers=*/true); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 1106 | return oss.str(); |
| 1107 | } |
| 1108 | |
Andrew Trick | 1b2324d | 2012-03-07 00:18:22 +0000 | [diff] [blame] | 1109 | /// Return the basic block label. It is not necessarilly unique because a block |
| 1110 | /// contains multiple scheduling regions. But it is fine for visualization. |
| 1111 | std::string ScheduleDAGInstrs::getDAGName() const { |
| 1112 | return "dag." + BB->getFullName(); |
| 1113 | } |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1114 | |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1115 | //===----------------------------------------------------------------------===// |
| 1116 | // SchedDFSResult Implementation |
| 1117 | //===----------------------------------------------------------------------===// |
| 1118 | |
| 1119 | namespace llvm { |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 1120 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1121 | /// Internal state used to compute SchedDFSResult. |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1122 | class SchedDFSImpl { |
| 1123 | SchedDFSResult &R; |
| 1124 | |
| 1125 | /// Join DAG nodes into equivalence classes by their subtree. |
| 1126 | IntEqClasses SubtreeClasses; |
| 1127 | /// List PredSU, SuccSU pairs that represent data edges between subtrees. |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 1128 | std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs; |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1129 | |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1130 | struct RootData { |
| 1131 | unsigned NodeID; |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1132 | unsigned ParentNodeID; ///< Parent node (member of the parent subtree). |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 1133 | unsigned SubInstrCount = 0; ///< Instr count in this tree only, not |
| 1134 | /// children. |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1135 | |
| 1136 | RootData(unsigned id): NodeID(id), |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 1137 | ParentNodeID(SchedDFSResult::InvalidSubtreeID) {} |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1138 | |
| 1139 | unsigned getSparseSetIndex() const { return NodeID; } |
| 1140 | }; |
| 1141 | |
| 1142 | SparseSet<RootData> RootSet; |
| 1143 | |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1144 | public: |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1145 | SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSNodeData.size()) { |
| 1146 | RootSet.setUniverse(R.DFSNodeData.size()); |
| 1147 | } |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1148 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1149 | /// Returns true if this node been visited by the DFS traversal. |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1150 | /// |
| 1151 | /// During visitPostorderNode the Node's SubtreeID is assigned to the Node |
| 1152 | /// ID. Later, SubtreeID is updated but remains valid. |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1153 | bool isVisited(const SUnit *SU) const { |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1154 | return R.DFSNodeData[SU->NodeNum].SubtreeID |
| 1155 | != SchedDFSResult::InvalidSubtreeID; |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1156 | } |
| 1157 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1158 | /// Initializes this node's instruction count. We don't need to flag the node |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1159 | /// visited until visitPostorder because the DAG cannot have cycles. |
| 1160 | void visitPreorder(const SUnit *SU) { |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1161 | R.DFSNodeData[SU->NodeNum].InstrCount = |
| 1162 | SU->getInstr()->isTransient() ? 0 : 1; |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1163 | } |
| 1164 | |
| 1165 | /// Called once for each node after all predecessors are visited. Revisit this |
| 1166 | /// node's predecessors and potentially join them now that we know the ILP of |
| 1167 | /// the other predecessors. |
| 1168 | void visitPostorderNode(const SUnit *SU) { |
| 1169 | // Mark this node as the root of a subtree. It may be joined with its |
| 1170 | // successors later. |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1171 | R.DFSNodeData[SU->NodeNum].SubtreeID = SU->NodeNum; |
| 1172 | RootData RData(SU->NodeNum); |
| 1173 | RData.SubInstrCount = SU->getInstr()->isTransient() ? 0 : 1; |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1174 | |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1175 | // If any predecessors are still in their own subtree, they either cannot be |
| 1176 | // joined or are large enough to remain separate. If this parent node's |
| 1177 | // total instruction count is not greater than a child subtree by at least |
| 1178 | // the subtree limit, then try to join it now since splitting subtrees is |
| 1179 | // only useful if multiple high-pressure paths are possible. |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1180 | unsigned InstrCount = R.DFSNodeData[SU->NodeNum].InstrCount; |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1181 | for (const SDep &PredDep : SU->Preds) { |
| 1182 | if (PredDep.getKind() != SDep::Data) |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1183 | continue; |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1184 | unsigned PredNum = PredDep.getSUnit()->NodeNum; |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1185 | if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit) |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1186 | joinPredSubtree(PredDep, SU, /*CheckLimit=*/false); |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1187 | |
| 1188 | // Either link or merge the TreeData entry from the child to the parent. |
Andrew Trick | 646eeb6 | 2013-01-25 06:52:30 +0000 | [diff] [blame] | 1189 | if (R.DFSNodeData[PredNum].SubtreeID == PredNum) { |
| 1190 | // If the predecessor's parent is invalid, this is a tree edge and the |
| 1191 | // current node is the parent. |
| 1192 | if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID) |
| 1193 | RootSet[PredNum].ParentNodeID = SU->NodeNum; |
| 1194 | } |
| 1195 | else if (RootSet.count(PredNum)) { |
| 1196 | // The predecessor is not a root, but is still in the root set. This |
| 1197 | // must be the new parent that it was just joined to. Note that |
| 1198 | // RootSet[PredNum].ParentNodeID may either be invalid or may still be |
| 1199 | // set to the original parent. |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1200 | RData.SubInstrCount += RootSet[PredNum].SubInstrCount; |
| 1201 | RootSet.erase(PredNum); |
| 1202 | } |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1203 | } |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1204 | RootSet[SU->NodeNum] = RData; |
| 1205 | } |
| 1206 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1207 | /// \brief Called once for each tree edge after calling visitPostOrderNode on |
| 1208 | /// the predecessor. Increment the parent node's instruction count and |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1209 | /// preemptively join this subtree to its parent's if it is small enough. |
| 1210 | void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ) { |
| 1211 | R.DFSNodeData[Succ->NodeNum].InstrCount |
| 1212 | += R.DFSNodeData[PredDep.getSUnit()->NodeNum].InstrCount; |
| 1213 | joinPredSubtree(PredDep, Succ); |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1214 | } |
| 1215 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1216 | /// Adds a connection for cross edges. |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1217 | void visitCrossEdge(const SDep &PredDep, const SUnit *Succ) { |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1218 | ConnectionPairs.push_back(std::make_pair(PredDep.getSUnit(), Succ)); |
| 1219 | } |
| 1220 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1221 | /// Sets each node's subtree ID to the representative ID and record |
| 1222 | /// connections between trees. |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1223 | void finalize() { |
| 1224 | SubtreeClasses.compress(); |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1225 | R.DFSTreeData.resize(SubtreeClasses.getNumClasses()); |
| 1226 | assert(SubtreeClasses.getNumClasses() == RootSet.size() |
| 1227 | && "number of roots should match trees"); |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1228 | for (const RootData &Root : RootSet) { |
| 1229 | unsigned TreeID = SubtreeClasses[Root.NodeID]; |
| 1230 | if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID) |
| 1231 | R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID]; |
| 1232 | R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount; |
Andrew Trick | 646eeb6 | 2013-01-25 06:52:30 +0000 | [diff] [blame] | 1233 | // Note that SubInstrCount may be greater than InstrCount if we joined |
| 1234 | // subtrees across a cross edge. InstrCount will be attributed to the |
| 1235 | // original parent, while SubInstrCount will be attributed to the joined |
| 1236 | // parent. |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1237 | } |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1238 | R.SubtreeConnections.resize(SubtreeClasses.getNumClasses()); |
| 1239 | R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses()); |
| 1240 | DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n"); |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1241 | for (unsigned Idx = 0, End = R.DFSNodeData.size(); Idx != End; ++Idx) { |
| 1242 | R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx]; |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1243 | DEBUG(dbgs() << " SU(" << Idx << ") in tree " |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1244 | << R.DFSNodeData[Idx].SubtreeID << '\n'); |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1245 | } |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1246 | for (const std::pair<const SUnit*, const SUnit*> &P : ConnectionPairs) { |
| 1247 | unsigned PredTree = SubtreeClasses[P.first->NodeNum]; |
| 1248 | unsigned SuccTree = SubtreeClasses[P.second->NodeNum]; |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1249 | if (PredTree == SuccTree) |
| 1250 | continue; |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1251 | unsigned Depth = P.first->getDepth(); |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1252 | addConnection(PredTree, SuccTree, Depth); |
| 1253 | addConnection(SuccTree, PredTree, Depth); |
| 1254 | } |
| 1255 | } |
| 1256 | |
| 1257 | protected: |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1258 | /// Joins the predecessor subtree with the successor that is its DFS parent. |
| 1259 | /// Applies some heuristics before joining. |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1260 | bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ, |
| 1261 | bool CheckLimit = true) { |
| 1262 | assert(PredDep.getKind() == SDep::Data && "Subtrees are for data edges"); |
| 1263 | |
| 1264 | // Check if the predecessor is already joined. |
| 1265 | const SUnit *PredSU = PredDep.getSUnit(); |
| 1266 | unsigned PredNum = PredSU->NodeNum; |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1267 | if (R.DFSNodeData[PredNum].SubtreeID != PredNum) |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1268 | return false; |
Andrew Trick | b52a856 | 2013-01-25 00:12:57 +0000 | [diff] [blame] | 1269 | |
| 1270 | // Four is the magic number of successors before a node is considered a |
| 1271 | // pinch point. |
| 1272 | unsigned NumDataSucs = 0; |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1273 | for (const SDep &SuccDep : PredSU->Succs) { |
| 1274 | if (SuccDep.getKind() == SDep::Data) { |
Andrew Trick | b52a856 | 2013-01-25 00:12:57 +0000 | [diff] [blame] | 1275 | if (++NumDataSucs >= 4) |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1276 | return false; |
Andrew Trick | b52a856 | 2013-01-25 00:12:57 +0000 | [diff] [blame] | 1277 | } |
| 1278 | } |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1279 | if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit) |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1280 | return false; |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1281 | R.DFSNodeData[PredNum].SubtreeID = Succ->NodeNum; |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1282 | SubtreeClasses.join(Succ->NodeNum, PredNum); |
| 1283 | return true; |
Andrew Trick | b52a856 | 2013-01-25 00:12:57 +0000 | [diff] [blame] | 1284 | } |
| 1285 | |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1286 | /// Called by finalize() to record a connection between trees. |
| 1287 | void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth) { |
| 1288 | if (!Depth) |
| 1289 | return; |
| 1290 | |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1291 | do { |
| 1292 | SmallVectorImpl<SchedDFSResult::Connection> &Connections = |
| 1293 | R.SubtreeConnections[FromTree]; |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1294 | for (SchedDFSResult::Connection &C : Connections) { |
| 1295 | if (C.TreeID == ToTree) { |
| 1296 | C.Level = std::max(C.Level, Depth); |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1297 | return; |
| 1298 | } |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1299 | } |
Andrew Trick | ffc8097 | 2013-01-25 06:52:27 +0000 | [diff] [blame] | 1300 | Connections.push_back(SchedDFSResult::Connection(ToTree, Depth)); |
| 1301 | FromTree = R.DFSTreeData[FromTree].ParentTreeID; |
| 1302 | } while (FromTree != SchedDFSResult::InvalidSubtreeID); |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1303 | } |
| 1304 | }; |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 1305 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1306 | } // end namespace llvm |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1307 | |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1308 | namespace { |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 1309 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1310 | /// Manage the stack used by a reverse depth-first search over the DAG. |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1311 | class SchedDAGReverseDFS { |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 1312 | std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack; |
| 1313 | |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1314 | public: |
| 1315 | bool isComplete() const { return DFSStack.empty(); } |
| 1316 | |
| 1317 | void follow(const SUnit *SU) { |
| 1318 | DFSStack.push_back(std::make_pair(SU, SU->Preds.begin())); |
| 1319 | } |
| 1320 | void advance() { ++DFSStack.back().second; } |
| 1321 | |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1322 | const SDep *backtrack() { |
| 1323 | DFSStack.pop_back(); |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 1324 | return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second); |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1325 | } |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1326 | |
| 1327 | const SUnit *getCurr() const { return DFSStack.back().first; } |
| 1328 | |
| 1329 | SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; } |
| 1330 | |
| 1331 | SUnit::const_pred_iterator getPredEnd() const { |
| 1332 | return getCurr()->Preds.end(); |
| 1333 | } |
| 1334 | }; |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 1335 | |
| 1336 | } // end anonymous namespace |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1337 | |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1338 | static bool hasDataSucc(const SUnit *SU) { |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1339 | for (const SDep &SuccDep : SU->Succs) { |
| 1340 | if (SuccDep.getKind() == SDep::Data && |
| 1341 | !SuccDep.getSUnit()->isBoundaryNode()) |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1342 | return true; |
| 1343 | } |
| 1344 | return false; |
| 1345 | } |
| 1346 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1347 | /// Computes an ILP metric for all nodes in the subDAG reachable via depth-first |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1348 | /// search from this root. |
Andrew Trick | e2c3f5c | 2013-01-25 06:33:57 +0000 | [diff] [blame] | 1349 | void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) { |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1350 | if (!IsBottomUp) |
Eric Christopher | 52854dc | 2017-08-03 22:41:12 +0000 | [diff] [blame] | 1351 | llvm_unreachable("Top-down ILP metric is unimplemented"); |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1352 | |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1353 | SchedDFSImpl Impl(*this); |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1354 | for (const SUnit &SU : SUnits) { |
| 1355 | if (Impl.isVisited(&SU) || hasDataSucc(&SU)) |
Andrew Trick | e2c3f5c | 2013-01-25 06:33:57 +0000 | [diff] [blame] | 1356 | continue; |
| 1357 | |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1358 | SchedDAGReverseDFS DFS; |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1359 | Impl.visitPreorder(&SU); |
| 1360 | DFS.follow(&SU); |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 1361 | while (true) { |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1362 | // Traverse the leftmost path as far as possible. |
| 1363 | while (DFS.getPred() != DFS.getPredEnd()) { |
| 1364 | const SDep &PredDep = *DFS.getPred(); |
| 1365 | DFS.advance(); |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1366 | // Ignore non-data edges. |
Andrew Trick | 646eeb6 | 2013-01-25 06:52:30 +0000 | [diff] [blame] | 1367 | if (PredDep.getKind() != SDep::Data |
| 1368 | || PredDep.getSUnit()->isBoundaryNode()) { |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1369 | continue; |
Andrew Trick | 646eeb6 | 2013-01-25 06:52:30 +0000 | [diff] [blame] | 1370 | } |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1371 | // An already visited edge is a cross edge, assuming an acyclic DAG. |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1372 | if (Impl.isVisited(PredDep.getSUnit())) { |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1373 | Impl.visitCrossEdge(PredDep, DFS.getCurr()); |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1374 | continue; |
| 1375 | } |
| 1376 | Impl.visitPreorder(PredDep.getSUnit()); |
| 1377 | DFS.follow(PredDep.getSUnit()); |
| 1378 | } |
| 1379 | // Visit the top of the stack in postorder and backtrack. |
| 1380 | const SUnit *Child = DFS.getCurr(); |
| 1381 | const SDep *PredDep = DFS.backtrack(); |
Andrew Trick | 5b07eeb | 2013-01-25 06:02:44 +0000 | [diff] [blame] | 1382 | Impl.visitPostorderNode(Child); |
| 1383 | if (PredDep) |
| 1384 | Impl.visitPostorderEdge(*PredDep, DFS.getCurr()); |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1385 | if (DFS.isComplete()) |
| 1386 | break; |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1387 | } |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1388 | } |
| 1389 | Impl.finalize(); |
| 1390 | } |
| 1391 | |
| 1392 | /// The root of the given SubtreeID was just scheduled. For all subtrees |
| 1393 | /// connected to this tree, record the depth of the connection so that the |
| 1394 | /// nearest connected subtrees can be prioritized. |
| 1395 | void SchedDFSResult::scheduleTree(unsigned SubtreeID) { |
Matthias Braun | 298e007 | 2016-09-30 23:08:07 +0000 | [diff] [blame] | 1396 | for (const Connection &C : SubtreeConnections[SubtreeID]) { |
| 1397 | SubtreeConnectLevels[C.TreeID] = |
| 1398 | std::max(SubtreeConnectLevels[C.TreeID], C.Level); |
| 1399 | DEBUG(dbgs() << " Tree: " << C.TreeID |
| 1400 | << " @" << SubtreeConnectLevels[C.TreeID] << '\n'); |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1401 | } |
| 1402 | } |
| 1403 | |
Matthias Braun | 8c209aa | 2017-01-28 02:02:38 +0000 | [diff] [blame] | 1404 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| 1405 | LLVM_DUMP_METHOD void ILPValue::print(raw_ostream &OS) const { |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1406 | OS << InstrCount << " / " << Length << " = "; |
| 1407 | if (!Length) |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1408 | OS << "BADILP"; |
Andrew Trick | 48d392e | 2012-11-28 05:13:28 +0000 | [diff] [blame] | 1409 | else |
| 1410 | OS << format("%g", ((double)InstrCount / Length)); |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1411 | } |
| 1412 | |
Matthias Braun | 8c209aa | 2017-01-28 02:02:38 +0000 | [diff] [blame] | 1413 | LLVM_DUMP_METHOD void ILPValue::dump() const { |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1414 | dbgs() << *this << '\n'; |
| 1415 | } |
| 1416 | |
| 1417 | namespace llvm { |
| 1418 | |
Alp Toker | d8d510a | 2014-07-01 21:19:13 +0000 | [diff] [blame] | 1419 | LLVM_DUMP_METHOD |
Andrew Trick | 90f711d | 2012-10-15 18:02:27 +0000 | [diff] [blame] | 1420 | raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val) { |
| 1421 | Val.print(OS); |
| 1422 | return OS; |
| 1423 | } |
| 1424 | |
Matthias Braun | bd7d918 | 2017-01-27 18:53:00 +0000 | [diff] [blame] | 1425 | } // end namespace llvm |
Eugene Zelenko | 7ea6923 | 2017-06-01 23:25:02 +0000 | [diff] [blame] | 1426 | |
Matthias Braun | 8c209aa | 2017-01-28 02:02:38 +0000 | [diff] [blame] | 1427 | #endif |