1//===- EliminateBarriers.cpp - Eliminate extra barriers --===//
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// Barrier elimination pattern and pass. If a barrier does not enforce any
10// conflicting pair of memory effects, including a pair that is enforced by
11// another barrier, it is unnecessary and can be removed. Adapted from
12// "High-Performance GPU-to-CPU Transpilation and Optimization via High-Level
13// Parallel Constructs" by Moses, Ivanov, Domke, Endo, Doerfert, and Zinenko in
14// PPoPP 2023 and implementation in Polygeist.
15//
16//===----------------------------------------------------------------------===//
17
18#include "mlir/Dialect/Func/IR/FuncOps.h"
19#include "mlir/Dialect/GPU/IR/GPUDialect.h"
20#include "mlir/Dialect/GPU/Transforms/Passes.h"
21#include "mlir/Dialect/MemRef/IR/MemRef.h"
22#include "mlir/Dialect/SCF/IR/SCF.h"
23#include "mlir/Dialect/Vector/IR/VectorOps.h"
24#include "mlir/IR/Operation.h"
25#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
26#include "llvm/ADT/SetOperations.h"
27#include "llvm/ADT/TypeSwitch.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/DebugLog.h"
30
31namespace mlir {
32#define GEN_PASS_DEF_GPUELIMINATEBARRIERS
33#include "mlir/Dialect/GPU/Transforms/Passes.h.inc"
34} // namespace mlir
35
36using namespace mlir;
37using namespace mlir::gpu;
38
39#define DEBUG_TYPE "gpu-erase-barriers"
40#define DEBUG_TYPE_ALIAS "gpu-erase-barries-alias"
41
42// The functions below provide interface-like verification, but are too specific
43// to barrier elimination to become interfaces.
44
45/// Returns `true` if the op is defines the parallel region that is subject to
46/// barrier synchronization.
47static bool isParallelRegionBoundary(Operation *op) {
48 if (op->hasDiscardableAttr(name: "__parallel_region_boundary_for_test"))
49 return true;
50
51 return isa<GPUFuncOp, LaunchOp>(Val: op);
52}
53
54/// Returns `true` if the op behaves like a sequential loop, e.g., the control
55/// flow "wraps around" from the end of the body region back to its start.
56static bool isSequentialLoopLike(Operation *op) { return isa<scf::ForOp>(Val: op); }
57
58/// Returns `true` if the regions of the op are guaranteed to be executed at
59/// most once. Thus, if an operation in one of the nested regions of `op` is
60/// executed than so are all the other operations in this region.
61static bool hasSingleExecutionBody(Operation *op) {
62 return isa<FunctionOpInterface, scf::IfOp, memref::AllocaScopeOp>(Val: op);
63}
64
65/// Returns `true` if the operation is known to produce a pointer-like object
66/// distinct from any other object produced by a similar operation. For example,
67/// an allocation produces such an object.
68static bool producesDistinctBase(Operation *op) {
69 return isa_and_nonnull<memref::AllocOp, memref::AllocaOp>(Val: op);
70}
71
72/// Populates `effects` with all memory effects without associating them to a
73/// specific value.
74static void addAllValuelessEffects(
75 SmallVectorImpl<MemoryEffects::EffectInstance> &effects) {
76 effects.emplace_back(Args: MemoryEffects::Effect::get<MemoryEffects::Read>());
77 effects.emplace_back(Args: MemoryEffects::Effect::get<MemoryEffects::Write>());
78 effects.emplace_back(Args: MemoryEffects::Effect::get<MemoryEffects::Allocate>());
79 effects.emplace_back(Args: MemoryEffects::Effect::get<MemoryEffects::Free>());
80}
81
82/// Looks through known "view-like" ops to find the base memref.
83static Value getBase(Value v) {
84 while (Operation *definingOp = v.getDefiningOp()) {
85 if (auto viewLike = dyn_cast<ViewLikeOpInterface>(Val: definingOp)) {
86 v = viewLike.getViewSource();
87 continue;
88 }
89 if (auto transposeOp = dyn_cast<memref::TransposeOp>(Val: definingOp)) {
90 v = transposeOp.getIn();
91 continue;
92 }
93 break;
94 }
95 return v;
96}
97
98/// Returns `true` if accesses to the given memory space could potentially be
99/// fenced by a barrier synchronizing on the given `fencedAddressSpaces`. If
100/// the set of address spaces is not given, it is equal to all possible address
101/// spaces. Memory spaces that are not `#gpu.address_space` are deemed to
102/// overlap with all GPU address spaces.
103static bool isAddressSpacePotentiallyFenced(
104 Attribute memorySpace,
105 std::optional<ArrayRef<gpu::AddressSpaceAttr>> fencedAddressSpaces) {
106 if (!fencedAddressSpaces)
107 return true;
108
109 auto gpuMemSpace = dyn_cast_if_present<gpu::AddressSpaceAttr>(Val&: memorySpace);
110 if (!gpuMemSpace)
111 return true;
112
113 // Check if this GPU address space is in the fenced set.
114 return llvm::is_contained(Range&: *fencedAddressSpaces, Element: gpuMemSpace);
115}
116
117/// Succeeds if the effect operates on a memref whose memory space
118/// could be one of the given fenced address spaces. This will both look at the
119/// address space of the effect's operand and of the view-like operations that
120/// define that memref, so as to inspect any memory-space casts or similar
121/// operations (like amdgpu buffer casts) that may provide more information.
122/// This assumes that directly-conflicting casts (that is, for example, casting
123/// a memref in global memory to make it one in workspace memory) can't happen.
124static LogicalResult effectMightAffectAddressSpaces(
125 const MemoryEffects::EffectInstance &effect,
126 std::optional<ArrayRef<gpu::AddressSpaceAttr>> fencedAddressSpaces) {
127 if (!fencedAddressSpaces)
128 return success();
129
130 Value value = effect.getValue();
131 if (!value)
132 return success();
133
134 auto mightMatch = [&](Value v) {
135 auto memrefType = dyn_cast<BaseMemRefType>(Val: v.getType());
136 if (!memrefType)
137 return true;
138 return isAddressSpacePotentiallyFenced(memorySpace: memrefType.getMemorySpace(),
139 fencedAddressSpaces);
140 };
141
142 if (!mightMatch(value))
143 return failure();
144
145 Value base = value;
146 while (auto viewLike = base.getDefiningOp<ViewLikeOpInterface>()) {
147 base = viewLike.getViewSource();
148 // We assume that we won't see directly incompatible casts, like global =>
149 // flat/null => workspace.
150 if (!mightMatch(base))
151 return failure();
152 }
153
154 return success();
155}
156
157/// Returns `true` if `op` is a `BarrierOp` that fences any address spaces that
158/// could overlap with the given fenced address spaces.
159static bool isBarrierWithCommonFencedMemory(
160 Operation *op,
161 std::optional<ArrayRef<gpu::AddressSpaceAttr>> fencedAddressSpaces) {
162 auto barrier = dyn_cast<BarrierOp>(Val: op);
163 if (!barrier)
164 return false;
165
166 std::optional<ArrayAttr> otherFencedSpaces = barrier.getAddressSpaces();
167 // Barriers with unspecified fencing fence everything.
168 if (!otherFencedSpaces)
169 return true;
170 // While barriers that fence nothing can't close off our search.
171 if (otherFencedSpaces->empty())
172 return false;
173
174 // If we fence all memory, we've got fencing in common with anything but the
175 // non-merory barrier.
176 if (!fencedAddressSpaces)
177 return true;
178
179 return llvm::any_of(
180 Range: otherFencedSpaces->getAsRange<gpu::AddressSpaceAttr>(),
181 P: [&](auto a) { return llvm::is_contained(*fencedAddressSpaces, a); });
182}
183
184/// Collect the memory effects of the given op in 'effects'. Returns 'true' if
185/// it could extract the effect information from the op, otherwise returns
186/// 'false' and conservatively populates the list with all possible effects
187/// associated with no particular value or symbol. `fencedAddressSpaces` is,
188/// if given, the set of GPU memory spaces that are being synchronized by the
189/// barrier being syrchronized - memory operations where the value being
190/// impacted is known and either it or its base value have an address space that
191/// is known to be distinct from the ones being synchronized on will not be
192/// included in the effect set.
193static bool collectEffects(
194 Operation *op, SmallVectorImpl<MemoryEffects::EffectInstance> &effects,
195 std::optional<ArrayRef<gpu::AddressSpaceAttr>> fencedAddressSpaces,
196 bool ignoreBarriers = true) {
197 // Skip over barriers to avoid infinite recursion (those barriers would ask
198 // this barrier again).
199 if (ignoreBarriers && isa<BarrierOp>(Val: op))
200 return true;
201
202 // Collect effect instances the operation. Note that the implementation of
203 // getEffects erases all effect instances that have the type other than the
204 // template parameter so we collect them first in a local buffer and then
205 // copy.
206 if (auto iface = dyn_cast<MemoryEffectOpInterface>(Val: op)) {
207 SmallVector<MemoryEffects::EffectInstance> localEffects;
208 iface.getEffects(effects&: localEffects);
209 // Filter out effects that cannot affect the fenced address spaces.
210 for (const MemoryEffects::EffectInstance &effect : localEffects) {
211 if (succeeded(
212 Result: effectMightAffectAddressSpaces(effect, fencedAddressSpaces)))
213 effects.push_back(Elt: effect);
214 }
215 return true;
216 }
217 if (op->hasTrait<OpTrait::HasRecursiveMemoryEffects>()) {
218 for (auto &region : op->getRegions()) {
219 for (auto &block : region) {
220 for (auto &innerOp : block)
221 if (!collectEffects(op: &innerOp, effects, fencedAddressSpaces,
222 ignoreBarriers))
223 return false;
224 }
225 }
226 return true;
227 }
228
229 // We need to be conservative here in case the op doesn't have the interface
230 // and assume it can have any possible effect.
231 addAllValuelessEffects(effects);
232 return false;
233}
234
235/// Get all effects before the given operation caused by other operations in the
236/// same block. That is, this will not consider operations beyond the block.
237static bool getEffectsBeforeInBlock(
238 Operation *op, SmallVectorImpl<MemoryEffects::EffectInstance> &effects,
239 std::optional<ArrayRef<gpu::AddressSpaceAttr>> fencedAddressSpaces,
240 bool stopAtBarrier) {
241 if (op == &op->getBlock()->front())
242 return true;
243
244 for (Operation *it = op->getPrevNode(); it != nullptr;
245 it = it->getPrevNode()) {
246 if (isBarrierWithCommonFencedMemory(op: it, fencedAddressSpaces)) {
247 if (stopAtBarrier)
248 return true;
249 continue;
250 }
251
252 if (!collectEffects(op: it, effects, fencedAddressSpaces))
253 return false;
254 }
255 return true;
256}
257
258/// Collects memory effects from operations that may be executed before `op` in
259/// a trivial structured control flow, e.g., without branches. Stops at the
260/// parallel region boundary or at the barrier operation if `stopAtBarrier` is
261/// set. Returns `true` if the memory effects added to `effects` are exact,
262/// `false` if they are a conservative over-approximation. The latter means that
263/// `effects` contain instances not associated with a specific value.
264static bool getEffectsBefore(
265 Operation *op, SmallVectorImpl<MemoryEffects::EffectInstance> &effects,
266 std::optional<ArrayRef<gpu::AddressSpaceAttr>> fencedAddressSpaces,
267 bool stopAtBarrier) {
268 if (!op->getBlock())
269 return true;
270
271 // If there is a non-structured control flow, bail.
272 Region *region = op->getBlock()->getParent();
273 if (region && !region->hasOneBlock()) {
274 addAllValuelessEffects(effects);
275 return false;
276 }
277
278 // Collect all effects before the op.
279 getEffectsBeforeInBlock(op, effects, fencedAddressSpaces, stopAtBarrier);
280
281 // Stop if reached the parallel region boundary.
282 if (isParallelRegionBoundary(op: op->getParentOp()))
283 return true;
284
285 Operation *parent = op->getParentOp();
286 // Otherwise, keep collecting above the parent operation.
287 if (!parent->hasTrait<OpTrait::IsIsolatedFromAbove>() &&
288 !getEffectsBefore(op: parent, effects, fencedAddressSpaces, stopAtBarrier))
289 return false;
290
291 // If the op is loop-like, collect effects from the trailing operations until
292 // we hit a barrier because they can executed before the current operation by
293 // the previous iteration of this loop. For example, in the following loop
294 //
295 // for i = ... {
296 // op1
297 // ...
298 // barrier
299 // op2
300 // }
301 //
302 // the operation `op2` at iteration `i` is known to be executed before the
303 // operation `op1` at iteration `i+1` and the side effects must be ordered
304 // appropriately.
305 if (isSequentialLoopLike(op: parent)) {
306 // Assuming loop terminators have no side effects.
307 return getEffectsBeforeInBlock(op: op->getBlock()->getTerminator(), effects,
308 fencedAddressSpaces, /*stopAtBarrier=*/true);
309 }
310
311 // If the parent operation is not guaranteed to execute its (single-block)
312 // region once, walk the block.
313 bool conservative = false;
314 if (!hasSingleExecutionBody(op: op->getParentOp()))
315 op->getParentOp()->walk(callback: [&](Operation *in) {
316 if (conservative)
317 return WalkResult::interrupt();
318 if (!collectEffects(op: in, effects, fencedAddressSpaces)) {
319 conservative = true;
320 return WalkResult::interrupt();
321 }
322 return WalkResult::advance();
323 });
324
325 return !conservative;
326}
327
328/// Get all effects after the given operation caused by other operations in the
329/// same block. That is, this will not consider operations beyond the block.
330static bool getEffectsAfterInBlock(
331 Operation *op, SmallVectorImpl<MemoryEffects::EffectInstance> &effects,
332 std::optional<ArrayRef<gpu::AddressSpaceAttr>> fencedAddressSpaces,
333 bool stopAtBarrier) {
334 if (op == &op->getBlock()->back())
335 return true;
336
337 for (Operation *it = op->getNextNode(); it != nullptr;
338 it = it->getNextNode()) {
339 if (isBarrierWithCommonFencedMemory(op: it, fencedAddressSpaces)) {
340 if (stopAtBarrier)
341 return true;
342 continue;
343 }
344 if (!collectEffects(op: it, effects, fencedAddressSpaces))
345 return false;
346 }
347 return true;
348}
349
350/// Collects memory effects from operations that may be executed after `op` in
351/// a trivial structured control flow, e.g., without branches. Stops at the
352/// parallel region boundary or at the barrier operation if `stopAtBarrier` is
353/// set. Returns `true` if the memory effects added to `effects` are exact,
354/// `false` if they are a conservative over-approximation. The latter means that
355/// `effects` contain instances not associated with a specific value.
356static bool getEffectsAfter(
357 Operation *op, SmallVectorImpl<MemoryEffects::EffectInstance> &effects,
358 std::optional<ArrayRef<gpu::AddressSpaceAttr>> fencedAddressSpaces,
359 bool stopAtBarrier) {
360 if (!op->getBlock())
361 return true;
362
363 // If there is a non-structured control flow, bail.
364 Region *region = op->getBlock()->getParent();
365 if (region && !region->hasOneBlock()) {
366 addAllValuelessEffects(effects);
367 return false;
368 }
369
370 // Collect all effects after the op.
371 getEffectsAfterInBlock(op, effects, fencedAddressSpaces, stopAtBarrier);
372
373 Operation *parent = op->getParentOp();
374 // Stop if reached the parallel region boundary.
375 if (isParallelRegionBoundary(op: parent))
376 return true;
377
378 // Otherwise, keep collecting below the parent operation.
379 // Don't look into, for example, neighboring functions
380 if (!parent->hasTrait<OpTrait::IsIsolatedFromAbove>() &&
381 !getEffectsAfter(op: parent, effects, fencedAddressSpaces, stopAtBarrier))
382 return false;
383
384 // If the op is loop-like, collect effects from the leading operations until
385 // we hit a barrier because they can executed after the current operation by
386 // the next iteration of this loop. For example, in the following loop
387 //
388 // for i = ... {
389 // op1
390 // ...
391 // barrier
392 // op2
393 // }
394 //
395 // the operation `op1` at iteration `i` is known to be executed after the
396 // operation `op2` at iteration `i-1` and the side effects must be ordered
397 // appropriately.
398 if (isSequentialLoopLike(op: parent)) {
399 if (isBarrierWithCommonFencedMemory(op: &op->getBlock()->front(),
400 fencedAddressSpaces))
401 return true;
402
403 bool exact =
404 collectEffects(op: &op->getBlock()->front(), effects, fencedAddressSpaces);
405 return getEffectsAfterInBlock(op: &op->getBlock()->front(), effects,
406 fencedAddressSpaces,
407 /*stopAtBarrier=*/true) &&
408 exact;
409 }
410
411 // If the parent operation is not guaranteed to execute its (single-block)
412 // region once, walk the block.
413 bool conservative = false;
414 if (!hasSingleExecutionBody(op: op->getParentOp()))
415 op->getParentOp()->walk(callback: [&](Operation *in) {
416 if (conservative)
417 return WalkResult::interrupt();
418 if (!collectEffects(op: in, effects, fencedAddressSpaces)) {
419 conservative = true;
420 return WalkResult::interrupt();
421 }
422 return WalkResult::advance();
423 });
424
425 return !conservative;
426}
427
428/// Returns `true` if the value is defined as a function argument.
429static bool isFunctionArgument(Value v) {
430 auto arg = dyn_cast<BlockArgument>(Val&: v);
431 return arg && isa<FunctionOpInterface>(Val: arg.getOwner()->getParentOp());
432}
433
434/// Returns the operand that the operation "propagates" through it for capture
435/// purposes. That is, if the value produced by this operation is captured, then
436/// so is the returned value.
437static Value propagatesCapture(Operation *op) {
438 return llvm::TypeSwitch<Operation *, Value>(op)
439 .Case(
440 caseFn: [](ViewLikeOpInterface viewLike) { return viewLike.getViewSource(); })
441 .Case(caseFn: [](CastOpInterface castLike) { return castLike->getOperand(idx: 0); })
442 .Case(caseFn: [](memref::TransposeOp transpose) { return transpose.getIn(); })
443 .Default(nullptr);
444}
445
446/// Returns `true` if the given operation is known to capture the given value,
447/// `false` if it is known not to capture the given value, `nullopt` if neither
448/// is known.
449static std::optional<bool> getKnownCapturingStatus(Operation *op, Value v) {
450 return llvm::TypeSwitch<Operation *, std::optional<bool>>(op)
451 // Store-like operations don't capture the destination, but do capture
452 // the value.
453 .Case<memref::StoreOp, vector::TransferWriteOp>(
454 caseFn: [&](auto op) { return op.getValue() == v; })
455 .Case<vector::StoreOp, vector::MaskedStoreOp>(
456 caseFn: [&](auto op) { return op.getValueToStore() == v; })
457 // These operations are known not to capture.
458 .Case(caseFn: [](memref::DeallocOp) { return false; })
459 // By default, we don't know anything.
460 .Default(std::nullopt);
461}
462
463/// Returns `true` if the value may be captured by any of its users, i.e., if
464/// the user may be storing this value into memory. This makes aliasing analysis
465/// more conservative as it cannot assume the pointer-like value is only passed
466/// around through SSA use-def.
467static bool maybeCaptured(Value v) {
468 SmallVector<Value> todo = {v};
469 while (!todo.empty()) {
470 Value v = todo.pop_back_val();
471 for (Operation *user : v.getUsers()) {
472 // A user that is known to only read cannot capture.
473 auto iface = dyn_cast<MemoryEffectOpInterface>(Val: user);
474 if (iface) {
475 SmallVector<MemoryEffects::EffectInstance> effects;
476 iface.getEffects(effects);
477 if (llvm::all_of(Range&: effects,
478 P: [](const MemoryEffects::EffectInstance &effect) {
479 return isa<MemoryEffects::Read>(Val: effect.getEffect());
480 })) {
481 continue;
482 }
483 }
484
485 // When an operation is known to create an alias, consider if the
486 // source is captured as well.
487 if (Value v = propagatesCapture(op: user)) {
488 todo.push_back(Elt: v);
489 continue;
490 }
491
492 std::optional<bool> knownCaptureStatus = getKnownCapturingStatus(op: user, v);
493 if (!knownCaptureStatus || *knownCaptureStatus)
494 return true;
495 }
496 }
497
498 return false;
499}
500
501/// Returns true if two values may be referencing aliasing memory. This is a
502/// rather naive and conservative analysis. Values defined by different
503/// allocation-like operations as well as values derived from those by casts and
504/// views cannot alias each other. Similarly, values defined by allocations
505/// inside a function cannot alias function arguments. Global values cannot
506/// alias each other or local allocations. Values that are captured, i.e.
507/// themselves potentially stored in memory, are considered as aliasing with
508/// everything. This seems sufficient to achieve barrier removal in structured
509/// control flow, more complex cases would require a proper dataflow analysis.
510static bool mayAlias(Value first, Value second) {
511 LDBG(DEBUG_TYPE_ALIAS, 1)
512 << "checking aliasing between " << first << " and " << second;
513
514 first = getBase(v: first);
515 second = getBase(v: second);
516
517 LDBG(DEBUG_TYPE_ALIAS, 1) << "base " << first << " and " << second;
518
519 // Values derived from the same base memref do alias (unless we do a more
520 // advanced analysis to prove non-overlapping accesses).
521 if (first == second) {
522 LDBG(DEBUG_TYPE_ALIAS, 1) << "-> do alias!";
523 return true;
524 }
525
526 // Different globals cannot alias.
527 if (auto globFirst = first.getDefiningOp<memref::GetGlobalOp>()) {
528 if (auto globSecond = second.getDefiningOp<memref::GetGlobalOp>()) {
529 return globFirst.getNameAttr() == globSecond.getNameAttr();
530 }
531 }
532
533 // Two function arguments marked as noalias do not alias.
534 auto isNoaliasFuncArgument = [](Value value) {
535 auto bbArg = dyn_cast<BlockArgument>(Val&: value);
536 if (!bbArg)
537 return false;
538 auto iface = dyn_cast<FunctionOpInterface>(Val: bbArg.getOwner()->getParentOp());
539 if (!iface)
540 return false;
541 // TODO: we need a way to not depend on the LLVM dialect here.
542 return iface.getArgAttr(index: bbArg.getArgNumber(), name: "llvm.noalias") != nullptr;
543 };
544 if (isNoaliasFuncArgument(first) && isNoaliasFuncArgument(second))
545 return false;
546
547 bool isDistinct[] = {producesDistinctBase(op: first.getDefiningOp()),
548 producesDistinctBase(op: second.getDefiningOp())};
549 bool isGlobal[] = {first.getDefiningOp<memref::GetGlobalOp>() != nullptr,
550 second.getDefiningOp<memref::GetGlobalOp>() != nullptr};
551
552 // Non-equivalent distinct bases and globals cannot alias. At this point, we
553 // have already filtered out based on values being equal and global name being
554 // equal.
555 if ((isDistinct[0] || isGlobal[0]) && (isDistinct[1] || isGlobal[1]))
556 return false;
557
558 bool isArg[] = {isFunctionArgument(v: first), isFunctionArgument(v: second)};
559
560 // Distinct bases (allocations) cannot have been passed as an argument.
561 if ((isDistinct[0] && isArg[1]) || (isDistinct[1] && isArg[0]))
562 return false;
563
564 // Non-captured base distinct values cannot conflict with another base value.
565 if (isDistinct[0] && !maybeCaptured(v: first))
566 return false;
567 if (isDistinct[1] && !maybeCaptured(v: second))
568 return false;
569
570 // Otherwise, conservatively assume aliasing.
571 LDBG(DEBUG_TYPE_ALIAS, 1) << "-> may alias!";
572 return true;
573}
574
575/// Returns `true` if the effect may be affecting memory aliasing the value. If
576/// the effect is not associated with any value, it is assumed to affect all
577/// memory and therefore aliases with everything.
578static bool mayAlias(MemoryEffects::EffectInstance a, Value v2) {
579 if (Value v = a.getValue()) {
580 return mayAlias(first: v, second: v2);
581 }
582 return true;
583}
584
585/// Returns `true` if the two effects may be affecting aliasing memory. If
586/// an effect is not associated with any value, it is assumed to affect all
587/// memory and therefore aliases with everything. Effects on different resources
588/// cannot alias.
589static bool mayAlias(MemoryEffects::EffectInstance a,
590 MemoryEffects::EffectInstance b) {
591 if (a.getResource()->getResourceID() != b.getResource()->getResourceID())
592 return false;
593 if (Value v2 = b.getValue()) {
594 return mayAlias(a, v2);
595 }
596 if (Value v = a.getValue()) {
597 return mayAlias(a: b, v2: v);
598 }
599 return true;
600}
601
602/// Returns `true` if any of the "before" effect instances has a conflict with
603/// any "after" instance for the purpose of barrier elimination. The effects are
604/// supposed to be limited to a barrier synchronization scope. A conflict exists
605/// if effects instances affect aliasing memory locations and at least on of
606/// then as a write. As an exception, if the non-write effect is an allocation
607/// effect, there is no conflict since we are only expected to see the
608/// allocation happening in the same thread and it cannot be accessed from
609/// another thread without capture (which we do handle in alias analysis).
610static bool
611haveConflictingEffects(ArrayRef<MemoryEffects::EffectInstance> beforeEffects,
612 ArrayRef<MemoryEffects::EffectInstance> afterEffects) {
613 for (const MemoryEffects::EffectInstance &before : beforeEffects) {
614 for (const MemoryEffects::EffectInstance &after : afterEffects) {
615 // If cannot alias, definitely no conflict.
616 if (!mayAlias(a: before, b: after))
617 continue;
618
619 // Read/read is not a conflict.
620 if (isa<MemoryEffects::Read>(Val: before.getEffect()) &&
621 isa<MemoryEffects::Read>(Val: after.getEffect())) {
622 continue;
623 }
624
625 // Allocate/* is not a conflict since the allocation happens within the
626 // thread context.
627 // TODO: This is not the case for */Free unless the allocation happened in
628 // the thread context, which we could also check for.
629 if (isa<MemoryEffects::Allocate>(Val: before.getEffect()) ||
630 isa<MemoryEffects::Allocate>(Val: after.getEffect())) {
631 continue;
632 }
633
634 // In the particular case that the before effect is a free, we only have 2
635 // possibilities:
636 // 1. either the program is well-formed and there must be an interleaved
637 // alloc that must limit the scope of effect lookback and we can
638 // safely ignore the free -> read / free -> write and free -> free
639 // conflicts.
640 // 2. either the program is ill-formed and we are in undefined behavior
641 // territory.
642 if (isa<MemoryEffects::Free>(Val: before.getEffect()))
643 continue;
644
645 // Other kinds of effects create a conflict, e.g. read-after-write.
646 LDBG() << "found a conflict between (before): " << before.getValue()
647 << " read:" << isa<MemoryEffects::Read>(Val: before.getEffect())
648 << " write:" << isa<MemoryEffects::Write>(Val: before.getEffect())
649 << " alloc:" << isa<MemoryEffects::Allocate>(Val: before.getEffect())
650 << " free:" << isa<MemoryEffects::Free>(Val: before.getEffect());
651 LDBG() << "and (after): " << after.getValue()
652 << " read:" << isa<MemoryEffects::Read>(Val: after.getEffect())
653 << " write:" << isa<MemoryEffects::Write>(Val: after.getEffect())
654 << " alloc:" << isa<MemoryEffects::Allocate>(Val: after.getEffect())
655 << " free:" << isa<MemoryEffects::Free>(Val: after.getEffect());
656 return true;
657 }
658 }
659
660 return false;
661}
662
663namespace {
664class BarrierElimination final : public OpRewritePattern<BarrierOp> {
665public:
666 using OpRewritePattern<BarrierOp>::OpRewritePattern;
667
668 LogicalResult matchAndRewrite(BarrierOp barrier,
669 PatternRewriter &rewriter) const override {
670 LDBG() << "checking the necessity of: " << barrier << " "
671 << barrier.getLoc();
672
673 // Named barriers have precise arrival-count semantics; never eliminate.
674 if (barrier.getNamedBarrier()) {
675 LDBG() << "barrier is a named barrier, retain it";
676 return failure();
677 }
678
679 if (barrier.getScope() != gpu::BarrierScope::Workgroup) {
680 LDBG() << "barrier has non-workgroup scope, retain it";
681 return failure();
682 }
683
684 std::optional<ArrayAttr> fencedMemSpaces = barrier.getAddressSpaces();
685 if (fencedMemSpaces && fencedMemSpaces->empty()) {
686 LDBG()
687 << "barrier is not used to synchronize memory accesses, retain it\n";
688 return failure();
689 }
690
691 // Convert the fenced address spaces to the proper type for passing through.
692 SmallVector<gpu::AddressSpaceAttr> fencedSpacesStorage;
693 std::optional<ArrayRef<gpu::AddressSpaceAttr>> fencedSpaces;
694 if (fencedMemSpaces) {
695 fencedSpacesStorage = llvm::map_to_vector(
696 C&: *fencedMemSpaces, F: llvm::CastTo<gpu::AddressSpaceAttr>);
697 fencedSpaces = fencedSpacesStorage;
698 }
699
700 SmallVector<MemoryEffects::EffectInstance> beforeEffects;
701 getEffectsBefore(op: barrier, effects&: beforeEffects, fencedAddressSpaces: fencedSpaces,
702 /*stopAtBarrier=*/true);
703
704 SmallVector<MemoryEffects::EffectInstance> afterEffects;
705 getEffectsAfter(op: barrier, effects&: afterEffects, fencedAddressSpaces: fencedSpaces,
706 /*stopAtBarrier=*/true);
707
708 if (!haveConflictingEffects(beforeEffects, afterEffects)) {
709 LDBG() << "the surrounding barriers are sufficient, removing " << barrier;
710 rewriter.eraseOp(op: barrier);
711 return success();
712 }
713
714 LDBG() << "barrier is necessary: " << barrier << " " << barrier.getLoc();
715 return failure();
716 }
717};
718
719class GpuEliminateBarriersPass
720 : public impl::GpuEliminateBarriersBase<GpuEliminateBarriersPass> {
721 void runOnOperation() override {
722 auto funcOp = getOperation();
723 RewritePatternSet patterns(&getContext());
724 mlir::populateGpuEliminateBarriersPatterns(patterns);
725 if (failed(Result: applyPatternsGreedily(op: funcOp, patterns: std::move(patterns)))) {
726 return signalPassFailure();
727 }
728 }
729};
730
731} // namespace
732
733void mlir::populateGpuEliminateBarriersPatterns(RewritePatternSet &patterns) {
734 patterns.insert<BarrierElimination>(arg: patterns.getContext());
735}
736