406 lines · cpp
1//===- SideEffectInterfaces.cpp - SideEffects in MLIR ---------------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "mlir/Interfaces/SideEffectInterfaces.h"10 11#include "mlir/IR/SymbolTable.h"12#include <utility>13 14using namespace mlir;15 16//===----------------------------------------------------------------------===//17// SideEffect Interfaces18//===----------------------------------------------------------------------===//19 20/// Include the definitions of the side effect interfaces.21#include "mlir/Interfaces/SideEffectInterfaces.cpp.inc"22 23//===----------------------------------------------------------------------===//24// MemoryEffects25//===----------------------------------------------------------------------===//26 27bool MemoryEffects::Effect::classof(const SideEffects::Effect *effect) {28 return isa<Allocate, Free, Read, Write>(effect);29}30 31//===----------------------------------------------------------------------===//32// SideEffect Utilities33//===----------------------------------------------------------------------===//34 35bool mlir::isOpTriviallyDead(Operation *op) {36 return op->use_empty() && wouldOpBeTriviallyDead(op);37}38 39/// Internal implementation of `mlir::wouldOpBeTriviallyDead` that also40/// considers terminator operations as dead if they have no side effects. This41/// allows for marking region operations as trivially dead without always being42/// conservative of terminators.43static bool wouldOpBeTriviallyDeadImpl(Operation *rootOp) {44 // The set of operation intervals (end-exclusive) to consider when checking45 // for side effects.46 SmallVector<std::pair<Block::iterator, Block::iterator>, 1> effectingOps = {47 std::make_pair(Block::iterator(rootOp), ++Block::iterator(rootOp))};48 while (!effectingOps.empty()) {49 Block::iterator &it = effectingOps.back().first;50 Block::iterator end = effectingOps.back().second;51 if (it == end) {52 effectingOps.pop_back();53 continue;54 }55 mlir::Operation *op = &*(it++);56 57 // If the operation has recursive effects, push all of the nested operations58 // on to the stack to consider.59 bool hasRecursiveEffects =60 op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();61 if (hasRecursiveEffects) {62 for (Region ®ion : op->getRegions()) {63 for (auto &block : region) {64 effectingOps.push_back(std::make_pair(block.begin(), block.end()));65 }66 }67 }68 69 // If the op has memory effects, try to characterize them to see if the op70 // is trivially dead here.71 if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(op)) {72 // Check to see if this op either has no effects, or only allocates/reads73 // memory.74 SmallVector<MemoryEffects::EffectInstance, 1> effects;75 effectInterface.getEffects(effects);76 77 // Gather all results of this op that are allocated.78 SmallPtrSet<Value, 4> allocResults;79 for (const MemoryEffects::EffectInstance &it : effects)80 if (isa<MemoryEffects::Allocate>(it.getEffect()) && it.getValue() &&81 it.getValue().getDefiningOp() == op)82 allocResults.insert(it.getValue());83 84 if (!llvm::all_of(effects, [&allocResults](85 const MemoryEffects::EffectInstance &it) {86 // We can drop effects if the value is an allocation and is a result87 // of the operation.88 if (allocResults.contains(it.getValue()))89 return true;90 // Otherwise, the effect must be a read.91 return isa<MemoryEffects::Read>(it.getEffect());92 })) {93 return false;94 }95 continue;96 }97 // Otherwise, if the op only has recursive side effects we can treat the98 // operation itself as having no effects. We will visit its children next.99 if (hasRecursiveEffects)100 continue;101 102 // If there were no effect interfaces, we treat this op as conservatively103 // having effects.104 return false;105 }106 107 // If we get here, none of the operations had effects that prevented marking108 // 'op' as dead.109 return true;110}111 112template <typename EffectTy>113bool mlir::hasSingleEffect(Operation *op) {114 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);115 if (!memOp)116 return false;117 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;118 memOp.getEffects(effects);119 bool hasSingleEffectOnVal = false;120 // Iterate through `effects` and check if an effect of type `EffectTy` and121 // only of that type is present.122 for (auto &effect : effects) {123 hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());124 if (!hasSingleEffectOnVal)125 return false;126 }127 return hasSingleEffectOnVal;128}129template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *);130template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *);131template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *);132template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *);133 134template <typename EffectTy>135bool mlir::hasSingleEffect(Operation *op, Value value) {136 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);137 if (!memOp)138 return false;139 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;140 memOp.getEffects(effects);141 bool hasSingleEffectOnVal = false;142 // Iterate through `effects` and check if an effect of type `EffectTy` and143 // only of that type is present.144 for (auto &effect : effects) {145 if (effect.getValue() != value)146 continue;147 hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());148 if (!hasSingleEffectOnVal)149 return false;150 }151 return hasSingleEffectOnVal;152}153 154template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *,155 Value value);156template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *,157 Value value);158template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *,159 Value value);160template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *,161 Value value);162 163template <typename ValueTy, typename EffectTy>164bool mlir::hasSingleEffect(Operation *op, ValueTy value) {165 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);166 if (!memOp)167 return false;168 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;169 memOp.getEffects(effects);170 bool hasSingleEffectOnVal = false;171 // Iterate through `effects` and check if an effect of type `EffectTy` and172 // only of that type is present on value.173 for (auto &effect : effects) {174 if (effect.getEffectValue<ValueTy>() != value)175 continue;176 hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());177 if (!hasSingleEffectOnVal)178 return false;179 }180 return hasSingleEffectOnVal;181}182 183template bool184mlir::hasSingleEffect<OpOperand *, MemoryEffects::Allocate>(Operation *,185 OpOperand *);186template bool187mlir::hasSingleEffect<OpOperand *, MemoryEffects::Free>(Operation *,188 OpOperand *);189template bool190mlir::hasSingleEffect<OpOperand *, MemoryEffects::Read>(Operation *,191 OpOperand *);192template bool193mlir::hasSingleEffect<OpOperand *, MemoryEffects::Write>(Operation *,194 OpOperand *);195template bool196mlir::hasSingleEffect<OpResult, MemoryEffects::Allocate>(Operation *, OpResult);197template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Free>(Operation *,198 OpResult);199template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Read>(Operation *,200 OpResult);201template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Write>(Operation *,202 OpResult);203template bool204mlir::hasSingleEffect<BlockArgument, MemoryEffects::Allocate>(Operation *,205 BlockArgument);206template bool207mlir::hasSingleEffect<BlockArgument, MemoryEffects::Free>(Operation *,208 BlockArgument);209template bool210mlir::hasSingleEffect<BlockArgument, MemoryEffects::Read>(Operation *,211 BlockArgument);212template bool213mlir::hasSingleEffect<BlockArgument, MemoryEffects::Write>(Operation *,214 BlockArgument);215 216template <typename... EffectTys>217bool mlir::hasEffect(Operation *op) {218 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);219 if (!memOp)220 return false;221 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;222 memOp.getEffects(effects);223 return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {224 return isa<EffectTys...>(effect.getEffect());225 });226}227template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *);228template bool mlir::hasEffect<MemoryEffects::Free>(Operation *);229template bool mlir::hasEffect<MemoryEffects::Read>(Operation *);230template bool mlir::hasEffect<MemoryEffects::Write>(Operation *);231template bool232mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *);233 234template <typename... EffectTys>235bool mlir::hasEffect(Operation *op, Value value) {236 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);237 if (!memOp)238 return false;239 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;240 memOp.getEffects(effects);241 return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {242 if (effect.getValue() != value)243 return false;244 return isa<EffectTys...>(effect.getEffect());245 });246}247template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *,248 Value value);249template bool mlir::hasEffect<MemoryEffects::Free>(Operation *, Value value);250template bool mlir::hasEffect<MemoryEffects::Read>(Operation *, Value value);251template bool mlir::hasEffect<MemoryEffects::Write>(Operation *, Value value);252template bool253mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *,254 Value value);255 256template <typename ValueTy, typename... EffectTys>257bool mlir::hasEffect(Operation *op, ValueTy value) {258 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);259 if (!memOp)260 return false;261 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;262 memOp.getEffects(effects);263 return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {264 if (effect.getEffectValue<ValueTy>() != value)265 return false;266 return isa<EffectTys...>(effect.getEffect());267 });268}269template bool270mlir::hasEffect<OpOperand *, MemoryEffects::Allocate>(Operation *, OpOperand *);271template bool mlir::hasEffect<OpOperand *, MemoryEffects::Free>(Operation *,272 OpOperand *);273template bool mlir::hasEffect<OpOperand *, MemoryEffects::Read>(Operation *,274 OpOperand *);275template bool mlir::hasEffect<OpOperand *, MemoryEffects::Write>(Operation *,276 OpOperand *);277template bool278mlir::hasEffect<OpOperand *, MemoryEffects::Write, MemoryEffects::Free>(279 Operation *, OpOperand *);280 281template bool mlir::hasEffect<OpResult, MemoryEffects::Allocate>(Operation *,282 OpResult);283template bool mlir::hasEffect<OpResult, MemoryEffects::Free>(Operation *,284 OpResult);285template bool mlir::hasEffect<OpResult, MemoryEffects::Read>(Operation *,286 OpResult);287template bool mlir::hasEffect<OpResult, MemoryEffects::Write>(Operation *,288 OpResult);289template bool290mlir::hasEffect<OpResult, MemoryEffects::Write, MemoryEffects::Free>(291 Operation *, OpResult);292 293template bool294mlir::hasEffect<BlockArgument, MemoryEffects::Allocate>(Operation *,295 BlockArgument);296template bool297mlir::hasEffect<BlockArgument, MemoryEffects::Free>(Operation *, BlockArgument);298template bool299mlir::hasEffect<BlockArgument, MemoryEffects::Read>(Operation *, BlockArgument);300template bool301mlir::hasEffect<BlockArgument, MemoryEffects::Write>(Operation *,302 BlockArgument);303template bool304mlir::hasEffect<BlockArgument, MemoryEffects::Write, MemoryEffects::Free>(305 Operation *, BlockArgument);306 307bool mlir::hasUnknownEffects(Operation *op) {308 return !isa<MemoryEffectOpInterface>(op) &&309 !op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();310}311 312bool mlir::wouldOpBeTriviallyDead(Operation *op) {313 if (op->mightHaveTrait<OpTrait::IsTerminator>())314 return false;315 if (isa<SymbolOpInterface>(op))316 return false;317 return wouldOpBeTriviallyDeadImpl(op);318}319 320bool mlir::isMemoryEffectFree(Operation *op) {321 if (auto memInterface = dyn_cast<MemoryEffectOpInterface>(op)) {322 if (!memInterface.hasNoEffect())323 return false;324 // If the op does not have recursive side effects, then it is memory effect325 // free.326 if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>())327 return true;328 } else if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>()) {329 // Otherwise, if the op does not implement the memory effect interface and330 // it does not have recursive side effects, then it cannot be known that the331 // op is moveable.332 return false;333 }334 335 // Recurse into the regions and ensure that all nested ops are memory effect336 // free.337 for (Region ®ion : op->getRegions())338 for (Operation &op : region.getOps())339 if (!isMemoryEffectFree(&op))340 return false;341 return true;342}343 344// the returned vector may contain duplicate effects345std::optional<llvm::SmallVector<MemoryEffects::EffectInstance>>346mlir::getEffectsRecursively(Operation *rootOp) {347 SmallVector<MemoryEffects::EffectInstance> effects;348 SmallVector<Operation *> effectingOps(1, rootOp);349 while (!effectingOps.empty()) {350 Operation *op = effectingOps.pop_back_val();351 352 // If the operation has recursive effects, push all of the nested353 // operations on to the stack to consider.354 bool hasRecursiveEffects =355 op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();356 if (hasRecursiveEffects) {357 for (Region ®ion : op->getRegions()) {358 for (Block &block : region) {359 for (Operation &nestedOp : block) {360 effectingOps.push_back(&nestedOp);361 }362 }363 }364 }365 366 if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(op)) {367 effectInterface.getEffects(effects);368 } else if (!hasRecursiveEffects) {369 // the operation does not have recursive memory effects or implement370 // the memory effect op interface. Its effects are unknown.371 return std::nullopt;372 }373 }374 return effects;375}376 377bool mlir::isSpeculatable(Operation *op) {378 auto conditionallySpeculatable = dyn_cast<ConditionallySpeculatable>(op);379 if (!conditionallySpeculatable)380 return false;381 382 switch (conditionallySpeculatable.getSpeculatability()) {383 case Speculation::RecursivelySpeculatable:384 for (Region ®ion : op->getRegions()) {385 for (Operation &op : region.getOps())386 if (!isSpeculatable(&op))387 return false;388 }389 return true;390 391 case Speculation::Speculatable:392 return true;393 394 case Speculation::NotSpeculatable:395 return false;396 }397 398 llvm_unreachable("Unhandled enum in mlir::isSpeculatable!");399}400 401/// The implementation of this function replicates the `def Pure : TraitList`402/// in `SideEffectInterfaces.td` and has to be kept in sync manually.403bool mlir::isPure(Operation *op) {404 return isSpeculatable(op) && isMemoryEffectFree(op);405}406