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