| 1 | //===- CIRBasicAliasAnalysis.cpp - Basic CIR Alias 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 "clang/CIR/Dialect/Analysis/CIRBasicAliasAnalysis.h" |
| 10 | #include "mlir/Interfaces/SideEffectInterfaces.h" |
| 11 | #include "clang/CIR/Dialect/IR/CIRAttrs.h" |
| 12 | #include "clang/CIR/Dialect/IR/CIRDialect.h" |
| 13 | #include "llvm/Support/DebugLog.h" |
| 14 | #include "llvm/Support/MathExtras.h" |
| 15 | |
| 16 | #include <limits> |
| 17 | |
| 18 | #define DEBUG_TYPE "cir-basic-alias-analysis" |
| 19 | |
| 20 | using namespace llvm; |
| 21 | using namespace cir; |
| 22 | |
| 23 | //===----------------------------------------------------------------------===// |
| 24 | // Helpers |
| 25 | //===----------------------------------------------------------------------===// |
| 26 | |
| 27 | static constexpr unsigned MaxLookupDepth = 6; |
| 28 | |
| 29 | /// Return the size in bytes of \p type, or std::nullopt when that size isn't |
| 30 | /// statically known (void, function types, incomplete records, ...). |
| 31 | static std::optional<int64_t> |
| 32 | getTypeSizeInBytes(mlir::Type type, const mlir::DataLayout &dataLayout) { |
| 33 | if (!cir::isSized(ty: type)) |
| 34 | return std::nullopt; |
| 35 | |
| 36 | llvm::TypeSize size = dataLayout.getTypeSize(t: type); |
| 37 | if (size.isScalable()) |
| 38 | return std::nullopt; |
| 39 | return size.getFixedValue(); |
| 40 | } |
| 41 | |
| 42 | /// Return the number of bytes an access through \p ptr touches, that is, the |
| 43 | /// size of its pointee type. |
| 44 | static std::optional<int64_t> |
| 45 | getAccessSize(mlir::Value ptr, const mlir::DataLayout &dataLayout) { |
| 46 | auto ptrTy = mlir::dyn_cast<cir::PointerType>(Val: ptr.getType()); |
| 47 | if (!ptrTy) |
| 48 | return std::nullopt; |
| 49 | return getTypeSizeInBytes(type: ptrTy.getPointee(), dataLayout); |
| 50 | } |
| 51 | |
| 52 | /// If \p val is a constant integer that fits in an int64_t, return its value. |
| 53 | /// The constant is interpreted according to the signedness of its type. |
| 54 | static std::optional<int64_t> getConstantIndex(mlir::Value val) { |
| 55 | auto constOp = |
| 56 | mlir::dyn_cast_if_present<cir::ConstantOp>(Val: val.getDefiningOp()); |
| 57 | if (!constOp) |
| 58 | return std::nullopt; |
| 59 | |
| 60 | auto intAttr = mlir::dyn_cast<cir::IntAttr>(Val: constOp.getValue()); |
| 61 | if (!intAttr) |
| 62 | return std::nullopt; |
| 63 | |
| 64 | const APInt &value = intAttr.getValue(); |
| 65 | if (intAttr.isSigned()) |
| 66 | return value.trySExtValue(); |
| 67 | return value.tryZExtValue(); |
| 68 | } |
| 69 | |
| 70 | /// Return `count * size`, or std::nullopt if either input is unknown or the |
| 71 | /// product overflows. |
| 72 | static std::optional<int64_t> scaleOffset(std::optional<int64_t> count, |
| 73 | std::optional<int64_t> size) { |
| 74 | if (!count || !size) |
| 75 | return std::nullopt; |
| 76 | auto [product, overflow] = MulOverflow(X: *count, Y: *size); |
| 77 | if (overflow) |
| 78 | return std::nullopt; |
| 79 | return product; |
| 80 | } |
| 81 | |
| 82 | /// Add \p delta bytes to \p offset, making the offset unknown if \p delta is |
| 83 | /// unknown or if the sum overflows. |
| 84 | static void addToOffset(std::optional<int64_t> &offset, |
| 85 | std::optional<int64_t> delta) { |
| 86 | if (!offset) |
| 87 | return; |
| 88 | if (!delta) { |
| 89 | offset.reset(); |
| 90 | return; |
| 91 | } |
| 92 | auto [sum, overflow] = AddOverflow(X: *offset, Y: *delta); |
| 93 | if (overflow) |
| 94 | offset.reset(); |
| 95 | else |
| 96 | offset = sum; |
| 97 | } |
| 98 | |
| 99 | namespace { |
| 100 | /// A pointer expressed as a byte offset into the object it points into. |
| 101 | struct PointerOffset { |
| 102 | /// The value the pointer was traced back to. This is an allocation, a block |
| 103 | /// argument, or the result of an operation this analysis cannot look through. |
| 104 | mlir::Value base; |
| 105 | |
| 106 | /// Byte offset of the pointer from the start of `base`. The offset can be |
| 107 | /// negative. If this is std::nullopt, the offset is not a compile-time |
| 108 | /// constant. |
| 109 | std::optional<int64_t> offset; |
| 110 | }; |
| 111 | } // namespace |
| 112 | |
| 113 | /// Trace \p val back to the object it points into, accumulating the byte offset |
| 114 | /// of \p val from the start of that object. |
| 115 | /// |
| 116 | /// The walk stops at a block argument, at an allocation, or at any operation |
| 117 | /// whose result cannot be described as an offset from one of its operands. The |
| 118 | /// returned base and offset always describe \p val, even when the walk stops |
| 119 | /// early because the depth limit was reached. |
| 120 | /// |
| 121 | /// Operations contributing an offset that isn't a compile-time constant (a |
| 122 | /// dynamic cir.ptr_stride index, for example) are still traced through, leaving |
| 123 | /// the offset unknown. Knowing which object a pointer points into is useful |
| 124 | /// even when the offset within that object is not known. |
| 125 | static PointerOffset decomposePointer(mlir::Value val, |
| 126 | const mlir::DataLayout &dataLayout) { |
| 127 | LDBG() << "Decomposing pointer: " << val; |
| 128 | |
| 129 | std::optional<int64_t> offset = 0; |
| 130 | |
| 131 | for (unsigned depth = 0; depth < MaxLookupDepth; ++depth) { |
| 132 | mlir::Operation *defOp = val.getDefiningOp(); |
| 133 | if (!defOp) { |
| 134 | LDBG() << "No defining operation, stopping" ; |
| 135 | break; // Block argument (e.g. function parameter) — stop here. |
| 136 | } |
| 137 | |
| 138 | // Bitcasts and address-space casts don't change the address, and |
| 139 | // array_to_ptrdecay produces a pointer to the first element of the array. |
| 140 | if (auto castOp = mlir::dyn_cast<cir::CastOp>(Val: defOp)) { |
| 141 | if (castOp.isAllocaPreservingCast() || |
| 142 | castOp.getKind() == cir::CastKind::array_to_ptrdecay) { |
| 143 | LDBG() << "Walking past cast operation" ; |
| 144 | val = castOp.getSrc(); |
| 145 | continue; |
| 146 | } |
| 147 | LDBG() << "Opaque cast operation, stopping" ; |
| 148 | break; |
| 149 | } |
| 150 | |
| 151 | // A stride moves the pointer by `stride * sizeof(pointee)` bytes. |
| 152 | if (auto strideOp = mlir::dyn_cast<cir::PtrStrideOp>(Val: defOp)) { |
| 153 | LDBG() << "Walking past PtrStrideOp" ; |
| 154 | addToOffset(offset, |
| 155 | delta: scaleOffset(count: getConstantIndex(val: strideOp.getStride()), |
| 156 | size: getTypeSizeInBytes(type: strideOp.getElementType(), |
| 157 | dataLayout))); |
| 158 | val = strideOp.getBase(); |
| 159 | continue; |
| 160 | } |
| 161 | |
| 162 | // A record member sits at a fixed offset given by the record layout. |
| 163 | if (auto memberOp = mlir::dyn_cast<cir::GetMemberOp>(Val: defOp)) { |
| 164 | LDBG() << "Walking past GetMemberOp" ; |
| 165 | auto recordTy = |
| 166 | mlir::cast<cir::RecordType>(Val: memberOp.getAddrTy().getPointee()); |
| 167 | std::optional<int64_t> memberOffset; |
| 168 | if (!recordTy.isIncomplete()) |
| 169 | memberOffset = |
| 170 | recordTy.getElementOffset(dataLayout, idx: memberOp.getIndex()); |
| 171 | addToOffset(offset, delta: memberOffset); |
| 172 | val = memberOp.getAddr(); |
| 173 | continue; |
| 174 | } |
| 175 | |
| 176 | // An array element sits at `index * sizeof(element)` bytes into the array. |
| 177 | if (auto elementOp = mlir::dyn_cast<cir::GetElementOp>(Val: defOp)) { |
| 178 | LDBG() << "Walking past GetElementOp" ; |
| 179 | addToOffset(offset, |
| 180 | delta: scaleOffset(count: getConstantIndex(val: elementOp.getIndex()), |
| 181 | size: getTypeSizeInBytes(type: elementOp.getElementType(), |
| 182 | dataLayout))); |
| 183 | val = elementOp.getBase(); |
| 184 | continue; |
| 185 | } |
| 186 | |
| 187 | // A base class subobject starts the given number of bytes into the derived |
| 188 | // object. This may return null if the input is null, but accessing memory |
| 189 | // based on that null pointer would be UB, so we always assume non-null |
| 190 | // here. |
| 191 | if (auto baseOp = mlir::dyn_cast<cir::BaseClassAddrOp>(Val: defOp)) { |
| 192 | LDBG() << "Walking past BaseClassAddrOp" ; |
| 193 | addToOffset(offset, delta: baseOp.getOffset().tryZExtValue()); |
| 194 | val = baseOp.getSrcAddr(); |
| 195 | continue; |
| 196 | } |
| 197 | |
| 198 | // Conversely, the derived object starts that many bytes before the base |
| 199 | // subobject, so the offset is applied as a negative adjustment. This may |
| 200 | // return null if the input is null, but accessing memory based on that null |
| 201 | // pointer would be UB, so we always assume non-null here. |
| 202 | if (auto derivedOp = mlir::dyn_cast<cir::DerivedClassAddrOp>(Val: defOp)) { |
| 203 | LDBG() << "Walking past DerivedClassAddrOp" ; |
| 204 | std::optional<int64_t> baseOffset = derivedOp.getOffset().tryZExtValue(); |
| 205 | if (baseOffset) |
| 206 | baseOffset = -*baseOffset; |
| 207 | addToOffset(offset, delta: baseOffset); |
| 208 | val = derivedOp.getSrcAddr(); |
| 209 | continue; |
| 210 | } |
| 211 | |
| 212 | // The real part of a complex value is at offset zero, the imaginary part |
| 213 | // right behind it. |
| 214 | if (auto realOp = mlir::dyn_cast<cir::ComplexRealPtrOp>(Val: defOp)) { |
| 215 | LDBG() << "Walking past ComplexRealPtrOp" ; |
| 216 | val = realOp.getOperand(); |
| 217 | continue; |
| 218 | } |
| 219 | if (auto imagOp = mlir::dyn_cast<cir::ComplexImagPtrOp>(Val: defOp)) { |
| 220 | LDBG() << "Walking past ComplexImagPtrOp" ; |
| 221 | auto ptrTy = mlir::cast<cir::PointerType>(Val: imagOp.getOperand().getType()); |
| 222 | auto complexTy = mlir::cast<cir::ComplexType>(Val: ptrTy.getPointee()); |
| 223 | addToOffset(offset, |
| 224 | delta: getTypeSizeInBytes(type: complexTy.getElementType(), dataLayout)); |
| 225 | val = imagOp.getOperand(); |
| 226 | continue; |
| 227 | } |
| 228 | |
| 229 | LDBG() << "Unhandled operation, stopping" ; |
| 230 | break; // Not expressible as an offset from another pointer. |
| 231 | } |
| 232 | |
| 233 | return {.base: val, .offset: offset}; |
| 234 | } |
| 235 | |
| 236 | /// Return true if \p lhs and \p rhs are provably different objects. |
| 237 | /// |
| 238 | /// TODO: Extend to cover global addresses, function arguments with noalias, and |
| 239 | /// heap allocations. |
| 240 | static bool areDistinctObjects(mlir::Value lhs, mlir::Value rhs) { |
| 241 | // Distinct cir.alloca ops allocate distinct storage. |
| 242 | return lhs != rhs && |
| 243 | mlir::isa_and_nonnull<cir::AllocaOp>(Val: lhs.getDefiningOp()) && |
| 244 | mlir::isa_and_nonnull<cir::AllocaOp>(Val: rhs.getDefiningOp()); |
| 245 | } |
| 246 | |
| 247 | //===----------------------------------------------------------------------===// |
| 248 | // CIRBasicAliasAnalysis |
| 249 | //===----------------------------------------------------------------------===// |
| 250 | |
| 251 | mlir::AliasResult CIRBasicAliasAnalysis::alias(mlir::Value lhs, |
| 252 | mlir::Value rhs) { |
| 253 | LDBG() << "Checking alias between: " << lhs << " and " << rhs; |
| 254 | |
| 255 | if (lhs == rhs) { |
| 256 | LDBG() << "Trivial alias between identical values" ; |
| 257 | return mlir::AliasResult::MustAlias; |
| 258 | } |
| 259 | |
| 260 | PointerOffset lhsPtr = decomposePointer(val: lhs, dataLayout); |
| 261 | PointerOffset rhsPtr = decomposePointer(val: rhs, dataLayout); |
| 262 | |
| 263 | if (lhsPtr.base != rhsPtr.base) { |
| 264 | if (areDistinctObjects(lhs: lhsPtr.base, rhs: rhsPtr.base)) { |
| 265 | LDBG() << "No alias between pointers into distinct objects" ; |
| 266 | return mlir::AliasResult::NoAlias; |
| 267 | } |
| 268 | LDBG() << "Unrelated base objects, may alias" ; |
| 269 | return mlir::AliasResult::MayAlias; |
| 270 | } |
| 271 | |
| 272 | // Both pointers point into the same object, so their offsets can be compared |
| 273 | // directly. |
| 274 | if (!lhsPtr.offset || !rhsPtr.offset) { |
| 275 | LDBG() << "Same object at an unknown offset, may alias" ; |
| 276 | return mlir::AliasResult::MayAlias; |
| 277 | } |
| 278 | |
| 279 | // Equal offsets means both pointers start at exactly the same address, which |
| 280 | // is all MustAlias claims. How many bytes each access touches doesn't matter. |
| 281 | if (*lhsPtr.offset == *rhsPtr.offset) { |
| 282 | LDBG() << "Must alias at the same address within the same object" ; |
| 283 | return mlir::AliasResult::MustAlias; |
| 284 | } |
| 285 | |
| 286 | // The pointers start at different addresses, so whether they overlap depends |
| 287 | // on how far each access reaches. Without the extent of both accesses there |
| 288 | // is no way to tell. |
| 289 | std::optional<int64_t> lhsSize = getAccessSize(ptr: lhs, dataLayout); |
| 290 | std::optional<int64_t> rhsSize = getAccessSize(ptr: rhs, dataLayout); |
| 291 | if (!lhsSize || !rhsSize) { |
| 292 | LDBG() << "Same object but unknown access size, may alias" ; |
| 293 | return mlir::AliasResult::MayAlias; |
| 294 | } |
| 295 | |
| 296 | auto [lhsEnd, lhsOverflow] = AddOverflow(X: *lhsPtr.offset, Y: *lhsSize); |
| 297 | auto [rhsEnd, rhsOverflow] = AddOverflow(X: *rhsPtr.offset, Y: *rhsSize); |
| 298 | if (lhsOverflow || rhsOverflow) { |
| 299 | LDBG() << "Access range overflows, may alias" ; |
| 300 | return mlir::AliasResult::MayAlias; |
| 301 | } |
| 302 | |
| 303 | if (lhsEnd <= *rhsPtr.offset || rhsEnd <= *lhsPtr.offset) { |
| 304 | LDBG() << "No alias between disjoint ranges of the same object" ; |
| 305 | return mlir::AliasResult::NoAlias; |
| 306 | } |
| 307 | |
| 308 | LDBG() << "Partial alias between overlapping ranges of the same object" ; |
| 309 | return mlir::AliasResult::PartialAlias; |
| 310 | } |
| 311 | |
| 312 | mlir::ModRefResult CIRBasicAliasAnalysis::getModRef(mlir::Operation *op, |
| 313 | mlir::Value location) { |
| 314 | LDBG() << "getModRef: " |
| 315 | << mlir::OpWithFlags(op, mlir::OpPrintingFlags().skipRegions()) |
| 316 | << " on location " << location; |
| 317 | |
| 318 | auto effects = mlir::dyn_cast<mlir::MemoryEffectOpInterface>(Val: op); |
| 319 | if (!effects) { |
| 320 | LDBG() << "No memory effect interface, returning ModAndRef" ; |
| 321 | return mlir::ModRefResult::getModAndRef(); |
| 322 | } |
| 323 | |
| 324 | SmallVector<mlir::MemoryEffects::EffectInstance> effectList; |
| 325 | effects.getEffects(effects&: effectList); |
| 326 | |
| 327 | auto classifyEffect = [location, this]( |
| 328 | const mlir::MemoryEffects::EffectInstance &effect) { |
| 329 | if (mlir::isa<mlir::MemoryEffects::Allocate>(Val: effect.getEffect())) { |
| 330 | LDBG() << "Skipping allocate effect" ; |
| 331 | return mlir::ModRefResult::getNoModRef(); |
| 332 | } |
| 333 | |
| 334 | mlir::AliasResult aliasResult = mlir::AliasResult::MayAlias; |
| 335 | if (mlir::Value affectedLocation = effect.getValue()) { |
| 336 | LDBG() << " Checking alias between affected location " |
| 337 | << affectedLocation << " and query location " << location; |
| 338 | aliasResult = alias(lhs: affectedLocation, rhs: location); |
| 339 | LDBG() << " Alias result: " << aliasResult; |
| 340 | } else { |
| 341 | // An effect on a non-addressable resource cannot affect a |
| 342 | // pointer-based location. |
| 343 | if (!effect.getResource()->isAddressable()) { |
| 344 | LDBG() << " Effect on non-addressable resource '" |
| 345 | << effect.getResource()->getName() << "', skipping (NoAlias)" ; |
| 346 | aliasResult = mlir::AliasResult::NoAlias; |
| 347 | } else { |
| 348 | LDBG() << " No effect value, assuming MayAlias" ; |
| 349 | } |
| 350 | } |
| 351 | |
| 352 | // If the affected location doesn't alias with the query location, |
| 353 | // ignore this effect. |
| 354 | if (aliasResult.isNo()) { |
| 355 | LDBG() << "No alias with affected location" ; |
| 356 | return mlir::ModRefResult::getNoModRef(); |
| 357 | } |
| 358 | |
| 359 | // TODO: Consider whether Free should be NoModRef. |
| 360 | if (mlir::isa<mlir::MemoryEffects::Free>(Val: effect.getEffect())) { |
| 361 | LDBG() << "Skipping free effect" ; |
| 362 | return mlir::ModRefResult::getModAndRef(); |
| 363 | } |
| 364 | |
| 365 | if (mlir::isa<mlir::MemoryEffects::Write>(Val: effect.getEffect())) { |
| 366 | LDBG() << "Write effect, adding Mod" ; |
| 367 | return mlir::ModRefResult::getMod(); |
| 368 | } |
| 369 | |
| 370 | if (mlir::isa<mlir::MemoryEffects::Read>(Val: effect.getEffect())) { |
| 371 | LDBG() << "Read effect, adding Ref" ; |
| 372 | return mlir::ModRefResult::getRef(); |
| 373 | } |
| 374 | |
| 375 | LDBG() << "Unexpected memory effect: " << effect.getEffect(); |
| 376 | return mlir::ModRefResult::getNoModRef(); |
| 377 | }; |
| 378 | |
| 379 | return llvm::accumulate(Range: llvm::map_range(C&: effectList, F: classifyEffect), |
| 380 | Init: mlir::ModRefResult::getNoModRef(), |
| 381 | Op: [](mlir::ModRefResult lhs, mlir::ModRefResult rhs) { |
| 382 | return lhs.merge(other: rhs); |
| 383 | }); |
| 384 | } |
| 385 | |