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 16 #ifndef MAPLEBE_INCLUDE_CG_AARCH64_AARCH64_MEM_REFERENCE_H 17 #define MAPLEBE_INCLUDE_CG_AARCH64_AARCH64_MEM_REFERENCE_H 18 19 #include "deps.h" 20 #include "aarch64_insn.h" 21 22 namespace maplebe { 23 class AArch64MemReference { 24 public: 25 // If one of the memory is volatile, we need build dependency. HasVolatile(const Insn & memInsn1,const Insn & memInsn2)26 static bool HasVolatile(const Insn &memInsn1, const Insn &memInsn2) 27 { 28 auto *memOpnd1 = static_cast<MemOperand *>(memInsn1.GetMemOpnd()); 29 auto *memOpnd2 = static_cast<MemOperand *>(memInsn2.GetMemOpnd()); 30 if (memOpnd1 != nullptr && memOpnd2 != nullptr) { 31 if (memOpnd1->IsVolatile() || memOpnd2->IsVolatile()) { 32 return true; 33 } 34 } 35 return false; 36 } 37 38 // If the two memory reference sets do not have the same element(ostIdx), 39 // there is no alias, return false. HasMemoryReferenceAlias(const MemDefUseSet & refSet1,const MemDefUseSet & refSet2)40 static bool HasMemoryReferenceAlias(const MemDefUseSet &refSet1, const MemDefUseSet &refSet2) 41 { 42 // Process conservatively when no alias info is available 43 if (refSet1.empty() || refSet2.empty()) { 44 return true; 45 } 46 for (const auto &ostIdx : refSet2) { 47 if (refSet1.find(ostIdx) != refSet1.end()) { 48 return true; 49 } 50 } 51 return false; 52 } 53 54 // Check memory overlap of same baseAddress in basic analysis and 55 // can be used for both [stack] and [heap] memory. IsMemoryOverlap(const Insn & memInsn1,const Insn & memInsn2,const Insn * baseDefInsn1,const Insn * baseDefInsn2)56 static bool IsMemoryOverlap(const Insn &memInsn1, const Insn &memInsn2, const Insn *baseDefInsn1, 57 const Insn *baseDefInsn2) 58 { 59 auto *memOpnd1 = static_cast<MemOperand *>(memInsn1.GetMemOpnd()); 60 auto *memOpnd2 = static_cast<MemOperand *>(memInsn2.GetMemOpnd()); 61 ASSERT_NOT_NULL(memOpnd1); 62 ASSERT_NOT_NULL(memOpnd2); 63 // Must be BOI-mode 64 DEBUG_ASSERT(memOpnd1->GetAddrMode() == MemOperand::kAddrModeBOi && 65 memOpnd2->GetAddrMode() == MemOperand::kAddrModeBOi, 66 "invalid addressing mode"); 67 68 RegOperand *baseOpnd1 = memOpnd1->GetBaseRegister(); 69 RegOperand *baseOpnd2 = memOpnd2->GetBaseRegister(); 70 // BaseRegister will be nullptr in BOI-mode, in what cases? 71 if (baseOpnd1 == nullptr || baseOpnd2 == nullptr) { 72 return true; 73 } 74 75 // If the two base addresses are different, we can not analyze whether they overlap here, 76 // so we process conservatively. 77 if (baseOpnd1->GetRegisterNumber() != baseOpnd2->GetRegisterNumber()) { 78 return true; 79 } 80 if (baseDefInsn1 != baseDefInsn2) { 81 return true; 82 } 83 84 OfstOperand *ofstOpnd1 = memOpnd1->GetOffsetImmediate(); 85 OfstOperand *ofstOpnd2 = memOpnd2->GetOffsetImmediate(); 86 87 int64 ofstValue1 = (ofstOpnd1 == nullptr ? 0 : ofstOpnd1->GetOffsetValue()); 88 int64 ofstValue2 = (ofstOpnd2 == nullptr ? 0 : ofstOpnd2->GetOffsetValue()); 89 90 // Compatible with the load/store pair and load/store 91 uint32 memByteSize1 = memInsn1.GetMemoryByteSize(); 92 uint32 memByteSize2 = memInsn2.GetMemoryByteSize(); 93 94 int64 memByteBoundary1 = ofstValue1 + static_cast<int64>(memByteSize1); 95 int64 memByteBoundary2 = ofstValue2 + static_cast<int64>(memByteSize2); 96 97 // no overlap 98 // baseAddr ofst2 ofst1 ofst2---> 99 // |________|___memSize2_____|_____memSize1_____|__________ 100 // | | 101 // memBoundary2 memBoundary1 102 if (ofstValue2 >= memByteBoundary1 || ofstValue1 >= memByteBoundary2) { 103 return false; 104 } 105 return true; 106 } 107 108 // Simply distinguish irrelevant stack memory. HasBasicMemoryDep(const Insn & memInsn1,const Insn & memInsn2,Insn * baseDefInsn1,Insn * baseDefInsn2)109 static bool HasBasicMemoryDep(const Insn &memInsn1, const Insn &memInsn2, Insn *baseDefInsn1, Insn *baseDefInsn2) 110 { 111 // The callee-save and callee-reload instructions do not conflict with any other memory access instructions, 112 // we use the $isIndependent field to check that. 113 const MemDefUse *memReference1 = memInsn1.GetReferenceOsts(); 114 const MemDefUse *memReference2 = memInsn2.GetReferenceOsts(); 115 if (memReference1 != nullptr && memReference1->IsIndependent()) { 116 return false; 117 } 118 if (memReference2 != nullptr && memReference2->IsIndependent()) { 119 return false; 120 } 121 122 auto *memOpnd1 = static_cast<MemOperand *>(memInsn1.GetMemOpnd()); 123 auto *memOpnd2 = static_cast<MemOperand *>(memInsn2.GetMemOpnd()); 124 // Not here to consider StImmOperand(e.g. adrp) or call(e.g. bl) 125 if (memOpnd1 == nullptr || memOpnd2 == nullptr) { 126 return true; 127 } 128 // 1. Check MIRSymbol 129 if (memOpnd1->GetSymbol() != nullptr && memOpnd2->GetSymbol() != nullptr && 130 memOpnd1->GetSymbol() != memOpnd2->GetSymbol()) { 131 return false; 132 } 133 // Only consider the BOI-mode for basic overlap analysis 134 if (memOpnd1->GetAddrMode() != MemOperand::kAddrModeBOi || 135 memOpnd2->GetAddrMode() != MemOperand::kAddrModeBOi) { 136 return true; 137 } 138 RegOperand *baseOpnd1 = memOpnd1->GetBaseRegister(); 139 RegOperand *baseOpnd2 = memOpnd2->GetBaseRegister(); 140 // BaseRegister will be nullptr in BOI-mode, in what cases? 141 if (baseOpnd1 == nullptr || baseOpnd2 == nullptr) { 142 return true; 143 } 144 // 2. Check memory overlap 145 if (!IsMemoryOverlap(memInsn1, memInsn2, baseDefInsn1, baseDefInsn2)) { 146 return false; 147 } 148 return true; 149 } 150 HasAliasMemoryDep(const Insn & fromMemInsn,const Insn & toMemInsn,DepType depType)151 static bool HasAliasMemoryDep(const Insn &fromMemInsn, const Insn &toMemInsn, DepType depType) 152 { 153 const MemDefUse *fromReferenceOsts = fromMemInsn.GetReferenceOsts(); 154 const MemDefUse *toReferenceOsts = toMemInsn.GetReferenceOsts(); 155 // Process conservatively when no alias info is available 156 if (fromReferenceOsts == nullptr || toReferenceOsts == nullptr) { 157 return true; 158 } 159 const MemDefUseSet &fromMemDefSet = fromReferenceOsts->GetDefSet(); 160 const MemDefUseSet &fromMemUseSet = fromReferenceOsts->GetUseSet(); 161 const MemDefUseSet &toMemDefSet = toReferenceOsts->GetDefSet(); 162 const MemDefUseSet &toMemUseSet = toReferenceOsts->GetUseSet(); 163 164 switch (depType) { 165 // Check write->read dependency 166 case kDependenceTypeTrue: 167 return HasMemoryReferenceAlias(fromMemDefSet, toMemUseSet); 168 // Check read->write dependency 169 case kDependenceTypeAnti: 170 return HasMemoryReferenceAlias(fromMemUseSet, toMemDefSet); 171 // Check write->write dependency 172 case kDependenceTypeOutput: 173 return HasMemoryReferenceAlias(fromMemDefSet, toMemDefSet); 174 case kDependenceTypeNone: { 175 if (HasMemoryReferenceAlias(fromMemDefSet, toMemDefSet) || 176 HasMemoryReferenceAlias(fromMemDefSet, toMemUseSet) || 177 HasMemoryReferenceAlias(fromMemUseSet, toMemDefSet)) { 178 return true; 179 } else { 180 return false; 181 } 182 } 183 default: 184 CHECK_FATAL(false, "invalid memory dependency type"); 185 } 186 } 187 188 // The entrance: if memory dependency needs to be build, return true. 189 // fromMemInsn & toMemInsn: will be [load, store, adrp, call] 190 // baseDefInsns: for basic memory dependency analysis, they define the base address and can be nullptr. 191 // depType: for memory analysis based on me-alias-info, only consider TRUE, ANTI, OUTPUT and NONE dependency type 192 // from fromMemInsn to toMemInsn, if it is NONE, we take care of both def and use sets. NeedBuildMemoryDependency(const Insn & fromMemInsn,const Insn & toMemInsn,Insn * baseDefInsn1,Insn * baseDefInsn2,DepType depType)193 static bool NeedBuildMemoryDependency(const Insn &fromMemInsn, const Insn &toMemInsn, Insn *baseDefInsn1, 194 Insn *baseDefInsn2, DepType depType) 195 { 196 // 0. Check volatile 197 if (HasVolatile(fromMemInsn, toMemInsn)) { 198 return true; 199 } 200 // 1. Do basic analysis of memory-related instructions based on cg-ir 201 if (!HasBasicMemoryDep(fromMemInsn, toMemInsn, baseDefInsn1, baseDefInsn2)) { 202 return false; 203 } 204 // 2. Do alias analysis of memory-related instructions based on me-alias-info 205 return HasAliasMemoryDep(fromMemInsn, toMemInsn, depType); 206 } 207 }; 208 } // namespace maplebe 209 210 #endif // MAPLEBE_INCLUDE_CG_AARCH64_AARCH64_MEM_REFERENCE_H 211