1 /* 2 * Copyright (c) 2023 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 #ifndef MAPLEBE_INCLUDE_CG_SCHEDULE_HEURISTIC_H 16 #define MAPLEBE_INCLUDE_CG_SCHEDULE_HEURISTIC_H 17 18 #include "deps.h" 19 20 // Define a series of priority comparison function objects. 21 // @ReturnValue: 22 // - positive: node1 has higher priority 23 // - negative: node2 has higher priority 24 // - zero: node1 == node2 25 // And ensure the sort is stable. 26 namespace maplebe { 27 28 // Prefer max delay priority 29 class CompareDelay { 30 public: operator()31 int operator()(const DepNode &node1, const DepNode &node2) const 32 { 33 return static_cast<int>(node1.GetDelay() - node2.GetDelay()); 34 } 35 }; 36 37 // To make better use of cpu cache prefetch: 38 // (1) If both insns are memory operation and have same base address (same base register) and same access 39 // byte, prefer lowest offset. 40 // The following (2) and (3) are not implemented currently, and can be optimized in the future: 41 // (2) If one insn is store and the other is not memory operation, prefer non-memory-insn scheduled before store. 42 // (3) If one insn is load and the other is not memory operation, prefer load scheduled before non-memory-insn. 43 class CompareDataCache { 44 public: operator()45 int operator()(const DepNode &node1, const DepNode &node2) 46 { 47 Insn *insn1 = node1.GetInsn(); 48 ASSERT_NOT_NULL(insn1); 49 Insn *insn2 = node2.GetInsn(); 50 ASSERT_NOT_NULL(insn2); 51 // Exclude adrp 52 if (insn1->IsMemAccess() && insn2->IsMemAccess()) { 53 auto *memOpnd1 = static_cast<MemOperand *>(insn1->GetMemOpnd()); 54 auto *memOpnd2 = static_cast<MemOperand *>(insn2->GetMemOpnd()); 55 // Need the same access byte 56 if ((insn1->IsLoadStorePair() && !insn2->IsLoadStorePair()) || 57 (!insn1->IsLoadStorePair() && insn2->IsLoadStorePair())) { 58 return 0; 59 } 60 if (memOpnd1 != nullptr && memOpnd2 != nullptr) { // Exclude load address 61 if (memOpnd1->GetAddrMode() == MemOperand::kAddrModeBOi && 62 memOpnd2->GetAddrMode() == MemOperand::kAddrModeBOi) { 63 RegOperand *baseOpnd1 = memOpnd1->GetBaseRegister(); 64 ASSERT_NOT_NULL(baseOpnd1); 65 RegOperand *baseOpnd2 = memOpnd2->GetBaseRegister(); 66 ASSERT_NOT_NULL(baseOpnd2); 67 if (baseOpnd1->GetRegisterNumber() == baseOpnd2->GetRegisterNumber()) { 68 ImmOperand *ofstOpnd1 = memOpnd1->GetOffsetOperand(); 69 ImmOperand *ofstOpnd2 = memOpnd2->GetOffsetOperand(); 70 if (ofstOpnd1 == nullptr && ofstOpnd2 == nullptr) { 71 return 0; 72 } else if (ofstOpnd1 == nullptr) { 73 return 1; 74 } else if (ofstOpnd2 == nullptr) { 75 return -1; 76 } else { 77 return static_cast<int>(ofstOpnd2->GetValue() - ofstOpnd1->GetValue()); 78 } 79 } 80 } else { 81 // Schedule load before store 82 if ((insn1->IsLoad() || insn1->IsLoadPair()) && (insn2->IsStore() || insn2->IsStorePair())) { 83 return 1; 84 } else if ((insn2->IsLoad() || insn2->IsLoadPair()) && (insn1->IsStore() || insn1->IsStorePair())) { 85 return -1; 86 } 87 } 88 } 89 } else if (enableIrrelevant && insn1->IsMemAccess()) { 90 return (insn1->IsLoad() || insn1->IsLoadPair()) ? 1 : -1; 91 } else if (enableIrrelevant && insn2->IsMemAccess()) { 92 return (insn2->IsLoad() || insn2->IsLoadPair()) ? -1 : 1; 93 } 94 return 0; 95 } 96 97 bool enableIrrelevant = false; 98 }; 99 100 // Prefer the class of the edges of two insn and last scheduled insn with the highest class number: 101 // 1. true dependency 102 // 2. anti/output dependency 103 // 3. the rest of the dependency 104 // 4. independent of last scheduled insn 105 class CompareClassOfLastScheduledNode { 106 public: CompareClassOfLastScheduledNode(uint32 lsid)107 explicit CompareClassOfLastScheduledNode(uint32 lsid) : lastSchedInsnId(lsid) {} 108 ~CompareClassOfLastScheduledNode() = default; 109 operator()110 int operator()(const DepNode &node1, const DepNode &node2) const 111 { 112 DepType type1 = kDependenceTypeNone; 113 DepType type2 = kDependenceTypeNone; 114 for (auto *predLink : node1.GetPreds()) { 115 DepNode &predNode = predLink->GetFrom(); 116 if (lastSchedInsnId != 0 && predNode.GetInsn()->GetId() == lastSchedInsnId) { 117 type1 = predLink->GetDepType(); 118 } 119 } 120 for (auto *predLink : node2.GetPreds()) { 121 DepNode &predNode = predLink->GetFrom(); 122 if (lastSchedInsnId != 0 && predNode.GetInsn()->GetId() == lastSchedInsnId) { 123 type2 = predLink->GetDepType(); 124 } 125 } 126 CHECK_FATAL(type1 != kDependenceTypeSeparator && type2 != kDependenceTypeSeparator, "invalid dependency type"); 127 128 uint32 typeClass1 = 0; 129 switch (type1) { 130 case kDependenceTypeTrue: 131 typeClass1 = kNumOne; 132 break; 133 case kDependenceTypeAnti: 134 case kDependenceTypeOutput: 135 typeClass1 = kNumTwo; 136 break; 137 case kDependenceTypeSeparator: 138 CHECK_FATAL(false, "invalid dependency type"); 139 break; 140 case kDependenceTypeNone: 141 typeClass1 = kNumFour; 142 break; 143 default: 144 typeClass1 = kNumThree; 145 break; 146 } 147 148 uint32 typeClass2 = 0; 149 switch (type2) { 150 case kDependenceTypeTrue: 151 typeClass2 = kNumOne; 152 break; 153 case kDependenceTypeAnti: 154 case kDependenceTypeOutput: 155 typeClass2 = kNumTwo; 156 break; 157 case kDependenceTypeSeparator: 158 CHECK_FATAL(false, "invalid dependency type"); 159 case kDependenceTypeNone: 160 typeClass2 = kNumFour; 161 break; 162 default: 163 typeClass2 = kNumThree; 164 break; 165 } 166 167 return static_cast<int>(typeClass1 - typeClass2); 168 } 169 170 uint32 lastSchedInsnId = 0; 171 }; 172 173 // Prefer min eStart 174 class CompareEStart { 175 public: operator()176 int operator()(const DepNode &node1, const DepNode &node2) const 177 { 178 return static_cast<int>(node2.GetEStart() - node1.GetEStart()); 179 } 180 }; 181 182 // Prefer min lStart 183 class CompareLStart { 184 public: operator()185 int operator()(const DepNode &node1, const DepNode &node2) const 186 { 187 return static_cast<int>(node2.GetLStart() - node1.GetLStart()); 188 } 189 }; 190 191 // Prefer max cost of insn 192 class CompareCost { 193 public: operator()194 int operator()(const DepNode &node1, const DepNode &node2) 195 { 196 return (node1.GetReservation()->GetLatency() - node2.GetReservation()->GetLatency()); 197 } 198 }; 199 200 // Prefer using more unit kind 201 class CompareUnitKindNum { 202 public: CompareUnitKindNum(uint32 maxUnitIndex)203 explicit CompareUnitKindNum(uint32 maxUnitIndex) : maxUnitIdx(maxUnitIndex) {} 204 operator()205 int operator()(const DepNode &node1, const DepNode &node2) const 206 { 207 bool use1 = IsUseUnitKind(node1); 208 bool use2 = IsUseUnitKind(node2); 209 if ((use1 && use2) || (!use1 && !use2)) { 210 return 0; 211 } else if (!use2) { 212 return 1; 213 } else { 214 return -1; 215 } 216 } 217 218 private: 219 // Check if a node use a specific unit kind IsUseUnitKind(const DepNode & depNode)220 bool IsUseUnitKind(const DepNode &depNode) const 221 { 222 uint32 unitKind = depNode.GetUnitKind(); 223 auto idx = static_cast<uint32>(__builtin_ffs(static_cast<int>(unitKind))); 224 while (idx != 0) { 225 DEBUG_ASSERT(maxUnitIdx < kUnitKindLast, "invalid unit index"); 226 if (idx == maxUnitIdx) { 227 return true; 228 } 229 unitKind &= ~(1u << (idx - 1u)); 230 idx = static_cast<uint32>(__builtin_ffs(static_cast<int>(unitKind))); 231 } 232 return false; 233 } 234 235 uint32 maxUnitIdx = 0; 236 }; 237 238 // Prefer slot0 239 class CompareSlotType { 240 public: operator()241 int operator()(const DepNode &node1, const DepNode &node2) 242 { 243 SlotType slotType1 = node1.GetReservation()->GetSlot(); 244 SlotType slotType2 = node2.GetReservation()->GetSlot(); 245 if (slotType1 == kSlots) { 246 slotType1 = kSlot0; 247 } 248 if (slotType2 == kSlots) { 249 slotType2 = kSlot0; 250 } 251 return (slotType2 - slotType1); 252 } 253 }; 254 255 // Prefer more succNodes 256 class CompareSuccNodeSize { 257 public: operator()258 int operator()(const DepNode &node1, const DepNode &node2) const 259 { 260 return static_cast<int>(node1.GetSuccs().size() - node2.GetSuccs().size()); 261 } 262 }; 263 264 // Default order 265 class CompareInsnID { 266 public: operator()267 int operator()(const DepNode &node1, const DepNode &node2) 268 { 269 Insn *insn1 = node1.GetInsn(); 270 DEBUG_ASSERT(insn1 != nullptr, "get insn from depNode failed"); 271 Insn *insn2 = node2.GetInsn(); 272 DEBUG_ASSERT(insn2 != nullptr, "get insn from depNode failed"); 273 return static_cast<int>(insn2->GetId() - insn1->GetId()); 274 } 275 }; 276 } // namespace maplebe 277 #endif // MAPLEBE_INCLUDE_CG_SCHEDULE_HEURISTIC_H 278