1//===- AliasAnalysis.cpp - Alias Analysis for FIR ------------------------===//
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 "flang/Optimizer/Analysis/AliasAnalysis.h"
10#include "flang/Optimizer/Dialect/FIROps.h"
11#include "flang/Optimizer/Dialect/FIROpsSupport.h"
12#include "flang/Optimizer/Dialect/FIRType.h"
13#include "flang/Optimizer/Dialect/FortranVariableInterface.h"
14#include "flang/Optimizer/HLFIR/HLFIROps.h"
15#include "mlir/Analysis/AliasAnalysis.h"
16#include "mlir/IR/BuiltinOps.h"
17#include "mlir/IR/Value.h"
18#include "mlir/Interfaces/SideEffectInterfaces.h"
19#include "llvm/ADT/TypeSwitch.h"
20#include "llvm/Support/Casting.h"
21#include "llvm/Support/Debug.h"
22
23using namespace mlir;
24
25#define DEBUG_TYPE "fir-alias-analysis"
26
27//===----------------------------------------------------------------------===//
28// AliasAnalysis: alias
29//===----------------------------------------------------------------------===//
30
31static bool isDummyArgument(mlir::Value v) {
32 auto blockArg{mlir::dyn_cast<mlir::BlockArgument>(v)};
33 if (!blockArg)
34 return false;
35
36 return blockArg.getOwner()->isEntryBlock();
37}
38
39/// Temporary function to skip through all the no op operations
40/// TODO: Generalize support of fir.load
41static mlir::Value getOriginalDef(mlir::Value v) {
42 mlir::Operation *defOp;
43 bool breakFromLoop = false;
44 while (!breakFromLoop && (defOp = v.getDefiningOp())) {
45 llvm::TypeSwitch<Operation *>(defOp)
46 .Case<fir::ConvertOp>([&](fir::ConvertOp op) { v = op.getValue(); })
47 .Case<fir::DeclareOp, hlfir::DeclareOp>(
48 [&](auto op) { v = op.getMemref(); })
49 .Default([&](auto op) { breakFromLoop = true; });
50 }
51 return v;
52}
53
54namespace fir {
55
56void AliasAnalysis::Source::print(llvm::raw_ostream &os) const {
57 if (auto v = llvm::dyn_cast<mlir::Value>(u))
58 os << v;
59 else if (auto gbl = llvm::dyn_cast<mlir::SymbolRefAttr>(u))
60 os << gbl;
61 os << " SourceKind: " << EnumToString(kind);
62 os << " Type: " << valueType << " ";
63 attributes.Dump(os, EnumToString);
64}
65
66bool AliasAnalysis::Source::isPointerReference(mlir::Type ty) {
67 auto eleTy = fir::dyn_cast_ptrEleTy(ty);
68 if (!eleTy)
69 return false;
70
71 return fir::isPointerType(eleTy) || eleTy.isa<fir::PointerType>();
72}
73
74bool AliasAnalysis::Source::isTargetOrPointer() const {
75 return attributes.test(Attribute::Pointer) ||
76 attributes.test(Attribute::Target);
77}
78
79bool AliasAnalysis::Source::isRecordWithPointerComponent() const {
80 auto eleTy = fir::dyn_cast_ptrEleTy(valueType);
81 if (!eleTy)
82 return false;
83 // TO DO: Look for pointer components
84 return eleTy.isa<fir::RecordType>();
85}
86
87AliasResult AliasAnalysis::alias(Value lhs, Value rhs) {
88 auto lhsSrc = getSource(lhs);
89 auto rhsSrc = getSource(rhs);
90 bool approximateSource = lhsSrc.approximateSource || rhsSrc.approximateSource;
91 LLVM_DEBUG(llvm::dbgs() << "AliasAnalysis::alias\n";
92 llvm::dbgs() << " lhs: " << lhs << "\n";
93 llvm::dbgs() << " lhsSrc: " << lhsSrc << "\n";
94 llvm::dbgs() << " rhs: " << rhs << "\n";
95 llvm::dbgs() << " rhsSrc: " << rhsSrc << "\n";
96 llvm::dbgs() << "\n";);
97
98 // Indirect case currently not handled. Conservatively assume
99 // it aliases with everything
100 if (lhsSrc.kind > SourceKind::Direct || rhsSrc.kind > SourceKind::Direct) {
101 return AliasResult::MayAlias;
102 }
103
104 // SourceKind::Direct is set for the addresses wrapped in a global boxes.
105 // ie: fir.global @_QMpointersEp : !fir.box<!fir.ptr<f32>>
106 // Though nothing is known about them, they would only alias with targets or
107 // pointers
108 bool directSourceToNonTargetOrPointer = false;
109 if (lhsSrc.u != rhsSrc.u || lhsSrc.kind != rhsSrc.kind) {
110 if ((lhsSrc.kind == SourceKind::Direct && !rhsSrc.isTargetOrPointer()) ||
111 (rhsSrc.kind == SourceKind::Direct && !lhsSrc.isTargetOrPointer()))
112 directSourceToNonTargetOrPointer = true;
113 }
114
115 if (lhsSrc.kind == SourceKind::Direct ||
116 rhsSrc.kind == SourceKind::Direct) {
117 if (!directSourceToNonTargetOrPointer)
118 return AliasResult::MayAlias;
119 }
120
121 if (lhsSrc.kind == rhsSrc.kind) {
122 if (lhsSrc.u == rhsSrc.u) {
123 if (approximateSource)
124 return AliasResult::MayAlias;
125 return AliasResult::MustAlias;
126 }
127
128 // Two host associated accesses may overlap due to an equivalence.
129 if (lhsSrc.kind == SourceKind::HostAssoc)
130 return AliasResult::MayAlias;
131
132 // Allocate and global memory address cannot physically alias
133 if (lhsSrc.kind == SourceKind::Allocate ||
134 lhsSrc.kind == SourceKind::Global)
135 return AliasResult::NoAlias;
136
137 // Dummy TARGET/POINTER arguments may alias.
138 if (lhsSrc.isTargetOrPointer() && rhsSrc.isTargetOrPointer())
139 return AliasResult::MayAlias;
140
141 // Box for POINTER component inside an object of a derived type
142 // may alias box of a POINTER object, as well as boxes for POINTER
143 // components inside two objects of derived types may alias.
144 if ((lhsSrc.isRecordWithPointerComponent() && rhsSrc.isTargetOrPointer()) ||
145 (rhsSrc.isRecordWithPointerComponent() && lhsSrc.isTargetOrPointer()) ||
146 (lhsSrc.isRecordWithPointerComponent() &&
147 rhsSrc.isRecordWithPointerComponent()))
148 return AliasResult::MayAlias;
149
150 return AliasResult::NoAlias;
151 }
152
153 assert(lhsSrc.kind != rhsSrc.kind && "memory source kinds must be different");
154
155 Source *src1, *src2;
156 if (lhsSrc.kind < rhsSrc.kind) {
157 src1 = &lhsSrc;
158 src2 = &rhsSrc;
159 } else {
160 src1 = &rhsSrc;
161 src2 = &lhsSrc;
162 }
163
164 if (src1->kind == SourceKind::Argument &&
165 src2->kind == SourceKind::HostAssoc) {
166 // Treat the host entity as TARGET for the purpose of disambiguating
167 // it with a dummy access. It is required for this particular case:
168 // subroutine test
169 // integer :: x(10)
170 // call inner(x)
171 // contains
172 // subroutine inner(y)
173 // integer, target :: y(:)
174 // x(1) = y(1)
175 // end subroutine inner
176 // end subroutine test
177 //
178 // F18 15.5.2.13 (4) (b) allows 'x' and 'y' to address the same object.
179 // 'y' has an explicit TARGET attribute, but 'x' has neither TARGET
180 // nor POINTER.
181 src2->attributes.set(Attribute::Target);
182 }
183
184 // Dummy TARGET/POINTER argument may alias with a global TARGET/POINTER.
185 if (src1->isTargetOrPointer() && src2->isTargetOrPointer())
186 return AliasResult::MayAlias;
187
188 // Box for POINTER component inside an object of a derived type
189 // may alias box of a POINTER object, as well as boxes for POINTER
190 // components inside two objects of derived types may alias.
191 if ((src1->isRecordWithPointerComponent() && src2->isTargetOrPointer()) ||
192 (src2->isRecordWithPointerComponent() && src1->isTargetOrPointer()) ||
193 (src1->isRecordWithPointerComponent() &&
194 src2->isRecordWithPointerComponent()))
195 return AliasResult::MayAlias;
196
197 return AliasResult::NoAlias;
198}
199
200//===----------------------------------------------------------------------===//
201// AliasAnalysis: getModRef
202//===----------------------------------------------------------------------===//
203
204/// This is mostly inspired by MLIR::LocalAliasAnalysis with 2 notable
205/// differences 1) Regions are not handled here but will be handled by a data
206/// flow analysis to come 2) Allocate and Free effects are considered
207/// modifying
208ModRefResult AliasAnalysis::getModRef(Operation *op, Value location) {
209 MemoryEffectOpInterface interface = dyn_cast<MemoryEffectOpInterface>(op);
210 if (!interface)
211 return ModRefResult::getModAndRef();
212
213 // Build a ModRefResult by merging the behavior of the effects of this
214 // operation.
215 SmallVector<MemoryEffects::EffectInstance> effects;
216 interface.getEffects(effects);
217
218 ModRefResult result = ModRefResult::getNoModRef();
219 for (const MemoryEffects::EffectInstance &effect : effects) {
220
221 // Check for an alias between the effect and our memory location.
222 AliasResult aliasResult = AliasResult::MayAlias;
223 if (Value effectValue = effect.getValue())
224 aliasResult = alias(effectValue, location);
225
226 // If we don't alias, ignore this effect.
227 if (aliasResult.isNo())
228 continue;
229
230 // Merge in the corresponding mod or ref for this effect.
231 if (isa<MemoryEffects::Read>(effect.getEffect()))
232 result = result.merge(ModRefResult::getRef());
233 else
234 result = result.merge(ModRefResult::getMod());
235
236 if (result.isModAndRef())
237 break;
238 }
239 return result;
240}
241
242AliasAnalysis::Source::Attributes
243getAttrsFromVariable(fir::FortranVariableOpInterface var) {
244 AliasAnalysis::Source::Attributes attrs;
245 if (var.isTarget())
246 attrs.set(AliasAnalysis::Attribute::Target);
247 if (var.isPointer())
248 attrs.set(AliasAnalysis::Attribute::Pointer);
249 if (var.isIntentIn())
250 attrs.set(AliasAnalysis::Attribute::IntentIn);
251
252 return attrs;
253}
254
255AliasAnalysis::Source AliasAnalysis::getSource(mlir::Value v) {
256 auto *defOp = v.getDefiningOp();
257 SourceKind type{SourceKind::Unknown};
258 mlir::Type ty;
259 bool breakFromLoop{false};
260 bool approximateSource{false};
261 bool followBoxAddr{mlir::isa<fir::BaseBoxType>(v.getType())};
262 mlir::SymbolRefAttr global;
263 Source::Attributes attributes;
264 while (defOp && !breakFromLoop) {
265 ty = defOp->getResultTypes()[0];
266 llvm::TypeSwitch<Operation *>(defOp)
267 .Case<fir::AllocaOp, fir::AllocMemOp>([&](auto op) {
268 // Unique memory allocation.
269 type = SourceKind::Allocate;
270 breakFromLoop = true;
271 })
272 .Case<fir::ConvertOp>([&](auto op) {
273 // Skip ConvertOp's and track further through the operand.
274 v = op->getOperand(0);
275 defOp = v.getDefiningOp();
276 })
277 .Case<fir::BoxAddrOp>([&](auto op) {
278 v = op->getOperand(0);
279 defOp = v.getDefiningOp();
280 if (mlir::isa<fir::BaseBoxType>(v.getType()))
281 followBoxAddr = true;
282 })
283 .Case<fir::ArrayCoorOp, fir::CoordinateOp>([&](auto op) {
284 v = op->getOperand(0);
285 defOp = v.getDefiningOp();
286 if (mlir::isa<fir::BaseBoxType>(v.getType()))
287 followBoxAddr = true;
288 approximateSource = true;
289 })
290 .Case<fir::EmboxOp, fir::ReboxOp>([&](auto op) {
291 if (followBoxAddr) {
292 v = op->getOperand(0);
293 defOp = v.getDefiningOp();
294 } else
295 breakFromLoop = true;
296 })
297 .Case<fir::LoadOp>([&](auto op) {
298 if (followBoxAddr && mlir::isa<fir::BaseBoxType>(op.getType())) {
299 // For now, support the load of an argument or fir.address_of
300 // TODO: generalize to all operations (in particular fir.alloca and
301 // fir.allocmem)
302 auto def = getOriginalDef(op.getMemref());
303 if (isDummyArgument(def) ||
304 def.template getDefiningOp<fir::AddrOfOp>()) {
305 v = def;
306 defOp = v.getDefiningOp();
307 return;
308 }
309 }
310 // No further tracking for addresses loaded from memory for now.
311 type = SourceKind::Indirect;
312 breakFromLoop = true;
313 })
314 .Case<fir::AddrOfOp>([&](auto op) {
315 // Address of a global scope object.
316 ty = v.getType();
317
318 // When the global is a
319 // fir.global @_QMpointersEp : !fir.box<!fir.ptr<f32>>
320 // or
321 // fir.global @_QMpointersEp : !fir.box<!fir.heap<f32>>
322 //
323 // and when following through the wrapped address, capture
324 // the fact that there is nothing known about it. Therefore setting
325 // the source to Direct.
326 //
327 // When not following the wrapped address, then consider the address
328 // of the box, which has nothing to do with the wrapped address and
329 // lies in the global memory space.
330 if (followBoxAddr &&
331 mlir::isa<fir::BaseBoxType>(fir::unwrapRefType(ty)))
332 type = SourceKind::Direct;
333 else
334 type = SourceKind::Global;
335
336 auto globalOpName = mlir::OperationName(
337 fir::GlobalOp::getOperationName(), defOp->getContext());
338 if (fir::valueHasFirAttribute(
339 v, fir::GlobalOp::getTargetAttrName(globalOpName)))
340 attributes.set(Attribute::Target);
341
342 // TODO: Take followBoxAddr into account when setting the pointer
343 // attribute
344 if (Source::isPointerReference(ty))
345 attributes.set(Attribute::Pointer);
346
347 global = llvm::cast<fir::AddrOfOp>(op).getSymbol();
348 breakFromLoop = true;
349 })
350 .Case<hlfir::DeclareOp, fir::DeclareOp>([&](auto op) {
351 auto varIf = llvm::cast<fir::FortranVariableOpInterface>(defOp);
352 // While going through a declare operation collect
353 // the variable attributes from it. Right now, some
354 // of the attributes are duplicated, e.g. a TARGET dummy
355 // argument has the target attribute both on its declare
356 // operation and on the entry block argument.
357 // In case of host associated use, the declare operation
358 // is the only carrier of the variable attributes,
359 // so we have to collect them here.
360 attributes |= getAttrsFromVariable(varIf);
361 if (varIf.isHostAssoc()) {
362 // Do not track past such DeclareOp, because it does not
363 // currently provide any useful information. The host associated
364 // access will end up dereferencing the host association tuple,
365 // so we may as well stop right now.
366 v = defOp->getResult(0);
367 // TODO: if the host associated variable is a dummy argument
368 // of the host, I think, we can treat it as SourceKind::Argument
369 // for the purpose of alias analysis inside the internal procedure.
370 type = SourceKind::HostAssoc;
371 breakFromLoop = true;
372 return;
373 }
374 // TODO: Look for the fortran attributes present on the operation
375 // Track further through the operand
376 v = op.getMemref();
377 defOp = v.getDefiningOp();
378 })
379 .Case<hlfir::DesignateOp>([&](auto op) {
380 // Track further through the memory indexed into
381 // => if the source arrays/structures don't alias then nor do the
382 // results of hlfir.designate
383 v = op.getMemref();
384 defOp = v.getDefiningOp();
385 // TODO: there will be some cases which provably don't alias if one
386 // takes into account the component or indices, which are currently
387 // ignored here - leading to false positives
388 // because of this limitation, we need to make sure we never return
389 // MustAlias after going through a designate operation
390 approximateSource = true;
391 if (mlir::isa<fir::BaseBoxType>(v.getType()))
392 followBoxAddr = true;
393 })
394 .Default([&](auto op) {
395 defOp = nullptr;
396 breakFromLoop = true;
397 });
398 }
399 if (!defOp && type == SourceKind::Unknown)
400 // Check if the memory source is coming through a dummy argument.
401 if (isDummyArgument(v)) {
402 type = SourceKind::Argument;
403 ty = v.getType();
404 if (fir::valueHasFirAttribute(v, fir::getTargetAttrName()))
405 attributes.set(Attribute::Target);
406
407 if (Source::isPointerReference(ty))
408 attributes.set(Attribute::Pointer);
409 }
410
411 if (type == SourceKind::Global || type == SourceKind::Direct)
412 return {global, type, ty, attributes, approximateSource};
413
414 return {v, type, ty, attributes, approximateSource};
415}
416
417} // namespace fir
418

source code of flang/lib/Optimizer/Analysis/AliasAnalysis.cpp