1 //==- llvm/CodeGen/SelectionDAGAddressAnalysis.cpp - DAG Address Analysis --==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/CodeGen/SelectionDAGAddressAnalysis.h" 10 #include "llvm/CodeGen/ISDOpcodes.h" 11 #include "llvm/CodeGen/MachineFrameInfo.h" 12 #include "llvm/CodeGen/MachineFunction.h" 13 #include "llvm/CodeGen/SelectionDAG.h" 14 #include "llvm/CodeGen/SelectionDAGNodes.h" 15 #include "llvm/CodeGen/TargetLowering.h" 16 #include "llvm/Support/Casting.h" 17 #include "llvm/Support/Debug.h" 18 #include <cstdint> 19 20 using namespace llvm; 21 22 bool BaseIndexOffset::equalBaseIndex(const BaseIndexOffset &Other, 23 const SelectionDAG &DAG, 24 int64_t &Off) const { 25 // Conservatively fail if we a match failed.. 26 if (!Base.getNode() || !Other.Base.getNode()) 27 return false; 28 if (!hasValidOffset() || !Other.hasValidOffset()) 29 return false; 30 // Initial Offset difference. 31 Off = *Other.Offset - *Offset; 32 33 if ((Other.Index == Index) && (Other.IsIndexSignExt == IsIndexSignExt)) { 34 // Trivial match. 35 if (Other.Base == Base) 36 return true; 37 38 // Match GlobalAddresses 39 if (auto *A = dyn_cast<GlobalAddressSDNode>(Base)) 40 if (auto *B = dyn_cast<GlobalAddressSDNode>(Other.Base)) 41 if (A->getGlobal() == B->getGlobal()) { 42 Off += B->getOffset() - A->getOffset(); 43 return true; 44 } 45 46 // Match Constants 47 if (auto *A = dyn_cast<ConstantPoolSDNode>(Base)) 48 if (auto *B = dyn_cast<ConstantPoolSDNode>(Other.Base)) { 49 bool IsMatch = 50 A->isMachineConstantPoolEntry() == B->isMachineConstantPoolEntry(); 51 if (IsMatch) { 52 if (A->isMachineConstantPoolEntry()) 53 IsMatch = A->getMachineCPVal() == B->getMachineCPVal(); 54 else 55 IsMatch = A->getConstVal() == B->getConstVal(); 56 } 57 if (IsMatch) { 58 Off += B->getOffset() - A->getOffset(); 59 return true; 60 } 61 } 62 63 const MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo(); 64 65 // Match FrameIndexes. 66 if (auto *A = dyn_cast<FrameIndexSDNode>(Base)) 67 if (auto *B = dyn_cast<FrameIndexSDNode>(Other.Base)) { 68 // Equal FrameIndexes - offsets are directly comparable. 69 if (A->getIndex() == B->getIndex()) 70 return true; 71 // Non-equal FrameIndexes - If both frame indices are fixed 72 // we know their relative offsets and can compare them. Otherwise 73 // we must be conservative. 74 if (MFI.isFixedObjectIndex(A->getIndex()) && 75 MFI.isFixedObjectIndex(B->getIndex())) { 76 Off += MFI.getObjectOffset(B->getIndex()) - 77 MFI.getObjectOffset(A->getIndex()); 78 return true; 79 } 80 } 81 } 82 return false; 83 } 84 85 bool BaseIndexOffset::computeAliasing(const SDNode *Op0, 86 const Optional<int64_t> NumBytes0, 87 const SDNode *Op1, 88 const Optional<int64_t> NumBytes1, 89 const SelectionDAG &DAG, bool &IsAlias) { 90 91 BaseIndexOffset BasePtr0 = match(Op0, DAG); 92 BaseIndexOffset BasePtr1 = match(Op1, DAG); 93 94 if (!(BasePtr0.getBase().getNode() && BasePtr1.getBase().getNode())) 95 return false; 96 int64_t PtrDiff; 97 if (NumBytes0.hasValue() && NumBytes1.hasValue() && 98 BasePtr0.equalBaseIndex(BasePtr1, DAG, PtrDiff)) { 99 // BasePtr1 is PtrDiff away from BasePtr0. They alias if none of the 100 // following situations arise: 101 IsAlias = !( 102 // [----BasePtr0----] 103 // [---BasePtr1--] 104 // ========PtrDiff========> 105 (*NumBytes0 <= PtrDiff) || 106 // [----BasePtr0----] 107 // [---BasePtr1--] 108 // =====(-PtrDiff)====> 109 (PtrDiff + *NumBytes1 <= 0)); // i.e. *NumBytes1 < -PtrDiff. 110 return true; 111 } 112 // If both BasePtr0 and BasePtr1 are FrameIndexes, we will not be 113 // able to calculate their relative offset if at least one arises 114 // from an alloca. However, these allocas cannot overlap and we 115 // can infer there is no alias. 116 if (auto *A = dyn_cast<FrameIndexSDNode>(BasePtr0.getBase())) 117 if (auto *B = dyn_cast<FrameIndexSDNode>(BasePtr1.getBase())) { 118 MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo(); 119 // If the base are the same frame index but the we couldn't find a 120 // constant offset, (indices are different) be conservative. 121 if (A != B && (!MFI.isFixedObjectIndex(A->getIndex()) || 122 !MFI.isFixedObjectIndex(B->getIndex()))) { 123 IsAlias = false; 124 return true; 125 } 126 } 127 128 bool IsFI0 = isa<FrameIndexSDNode>(BasePtr0.getBase()); 129 bool IsFI1 = isa<FrameIndexSDNode>(BasePtr1.getBase()); 130 bool IsGV0 = isa<GlobalAddressSDNode>(BasePtr0.getBase()); 131 bool IsGV1 = isa<GlobalAddressSDNode>(BasePtr1.getBase()); 132 bool IsCV0 = isa<ConstantPoolSDNode>(BasePtr0.getBase()); 133 bool IsCV1 = isa<ConstantPoolSDNode>(BasePtr1.getBase()); 134 135 // If of mismatched base types or checkable indices we can check 136 // they do not alias. 137 if ((BasePtr0.getIndex() == BasePtr1.getIndex() || (IsFI0 != IsFI1) || 138 (IsGV0 != IsGV1) || (IsCV0 != IsCV1)) && 139 (IsFI0 || IsGV0 || IsCV0) && (IsFI1 || IsGV1 || IsCV1)) { 140 IsAlias = false; 141 return true; 142 } 143 return false; // Cannot determine whether the pointers alias. 144 } 145 146 bool BaseIndexOffset::contains(const SelectionDAG &DAG, int64_t BitSize, 147 const BaseIndexOffset &Other, 148 int64_t OtherBitSize, int64_t &BitOffset) const { 149 int64_t Offset; 150 if (!equalBaseIndex(Other, DAG, Offset)) 151 return false; 152 if (Offset >= 0) { 153 // Other is after *this: 154 // [-------*this---------] 155 // [---Other--] 156 // ==Offset==> 157 BitOffset = 8 * Offset; 158 return BitOffset + OtherBitSize <= BitSize; 159 } 160 // Other starts strictly before *this, it cannot be fully contained. 161 // [-------*this---------] 162 // [--Other--] 163 return false; 164 } 165 166 /// Parses tree in Ptr for base, index, offset addresses. 167 static BaseIndexOffset matchLSNode(const LSBaseSDNode *N, 168 const SelectionDAG &DAG) { 169 SDValue Ptr = N->getBasePtr(); 170 171 // (((B + I*M) + c)) + c ... 172 SDValue Base = DAG.getTargetLoweringInfo().unwrapAddress(Ptr); 173 SDValue Index = SDValue(); 174 int64_t Offset = 0; 175 bool IsIndexSignExt = false; 176 177 // pre-inc/pre-dec ops are components of EA. 178 if (N->getAddressingMode() == ISD::PRE_INC) { 179 if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset())) 180 Offset += C->getSExtValue(); 181 else // If unknown, give up now. 182 return BaseIndexOffset(SDValue(), SDValue(), 0, false); 183 } else if (N->getAddressingMode() == ISD::PRE_DEC) { 184 if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset())) 185 Offset -= C->getSExtValue(); 186 else // If unknown, give up now. 187 return BaseIndexOffset(SDValue(), SDValue(), 0, false); 188 } 189 190 // Consume constant adds & ors with appropriate masking. 191 while (true) { 192 switch (Base->getOpcode()) { 193 case ISD::OR: 194 // Only consider ORs which act as adds. 195 if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) 196 if (DAG.MaskedValueIsZero(Base->getOperand(0), C->getAPIntValue())) { 197 Offset += C->getSExtValue(); 198 Base = DAG.getTargetLoweringInfo().unwrapAddress(Base->getOperand(0)); 199 continue; 200 } 201 break; 202 case ISD::ADD: 203 if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) { 204 Offset += C->getSExtValue(); 205 Base = DAG.getTargetLoweringInfo().unwrapAddress(Base->getOperand(0)); 206 continue; 207 } 208 break; 209 case ISD::LOAD: 210 case ISD::STORE: { 211 auto *LSBase = cast<LSBaseSDNode>(Base.getNode()); 212 unsigned int IndexResNo = (Base->getOpcode() == ISD::LOAD) ? 1 : 0; 213 if (LSBase->isIndexed() && Base.getResNo() == IndexResNo) 214 if (auto *C = dyn_cast<ConstantSDNode>(LSBase->getOffset())) { 215 auto Off = C->getSExtValue(); 216 if (LSBase->getAddressingMode() == ISD::PRE_DEC || 217 LSBase->getAddressingMode() == ISD::POST_DEC) 218 Offset -= Off; 219 else 220 Offset += Off; 221 Base = DAG.getTargetLoweringInfo().unwrapAddress(LSBase->getBasePtr()); 222 continue; 223 } 224 break; 225 } 226 } 227 // If we get here break out of the loop. 228 break; 229 } 230 231 if (Base->getOpcode() == ISD::ADD) { 232 // TODO: The following code appears to be needless as it just 233 // bails on some Ptrs early, reducing the cases where we 234 // find equivalence. We should be able to remove this. 235 // Inside a loop the current BASE pointer is calculated using an ADD and a 236 // MUL instruction. In this case Base is the actual BASE pointer. 237 // (i64 add (i64 %array_ptr) 238 // (i64 mul (i64 %induction_var) 239 // (i64 %element_size))) 240 if (Base->getOperand(1)->getOpcode() == ISD::MUL) 241 return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt); 242 243 // Look at Base + Index + Offset cases. 244 Index = Base->getOperand(1); 245 SDValue PotentialBase = Base->getOperand(0); 246 247 // Skip signextends. 248 if (Index->getOpcode() == ISD::SIGN_EXTEND) { 249 Index = Index->getOperand(0); 250 IsIndexSignExt = true; 251 } 252 253 // Check if Index Offset pattern 254 if (Index->getOpcode() != ISD::ADD || 255 !isa<ConstantSDNode>(Index->getOperand(1))) 256 return BaseIndexOffset(PotentialBase, Index, Offset, IsIndexSignExt); 257 258 Offset += cast<ConstantSDNode>(Index->getOperand(1))->getSExtValue(); 259 Index = Index->getOperand(0); 260 if (Index->getOpcode() == ISD::SIGN_EXTEND) { 261 Index = Index->getOperand(0); 262 IsIndexSignExt = true; 263 } else 264 IsIndexSignExt = false; 265 Base = PotentialBase; 266 } 267 return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt); 268 } 269 270 BaseIndexOffset BaseIndexOffset::match(const SDNode *N, 271 const SelectionDAG &DAG) { 272 if (const auto *LS0 = dyn_cast<LSBaseSDNode>(N)) 273 return matchLSNode(LS0, DAG); 274 if (const auto *LN = dyn_cast<LifetimeSDNode>(N)) { 275 if (LN->hasOffset()) 276 return BaseIndexOffset(LN->getOperand(1), SDValue(), LN->getOffset(), 277 false); 278 return BaseIndexOffset(LN->getOperand(1), SDValue(), false); 279 } 280 return BaseIndexOffset(); 281 } 282 283 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 284 285 LLVM_DUMP_METHOD void BaseIndexOffset::dump() const { 286 print(dbgs()); 287 } 288 289 void BaseIndexOffset::print(raw_ostream& OS) const { 290 OS << "BaseIndexOffset base=["; 291 Base->print(OS); 292 OS << "] index=["; 293 if (Index) 294 Index->print(OS); 295 OS << "] offset=" << Offset; 296 } 297 298 #endif 299