| 1 | //===----------------------------------------------------------------------===// |
| 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 "PassDetail.h" |
| 10 | #include "mlir/Dialect/Func/IR/FuncOps.h" |
| 11 | #include "mlir/IR/Block.h" |
| 12 | #include "mlir/IR/Dominance.h" |
| 13 | #include "mlir/IR/Operation.h" |
| 14 | #include "mlir/IR/PatternMatch.h" |
| 15 | #include "mlir/IR/Region.h" |
| 16 | #include "mlir/Support/LogicalResult.h" |
| 17 | #include "mlir/Transforms/GreedyPatternRewriteDriver.h" |
| 18 | #include "clang/CIR/Dialect/IR/CIRDialect.h" |
| 19 | #include "clang/CIR/Dialect/Passes.h" |
| 20 | #include "llvm/ADT/SmallVector.h" |
| 21 | |
| 22 | using namespace mlir; |
| 23 | using namespace cir; |
| 24 | |
| 25 | namespace mlir { |
| 26 | #define GEN_PASS_DEF_CIRSIMPLIFY |
| 27 | #include "clang/CIR/Dialect/Passes.h.inc" |
| 28 | } // namespace mlir |
| 29 | |
| 30 | //===----------------------------------------------------------------------===// |
| 31 | // Rewrite patterns |
| 32 | //===----------------------------------------------------------------------===// |
| 33 | |
| 34 | namespace { |
| 35 | |
| 36 | /// Dominance information that stays coherent while patterns rewrite the IR. |
| 37 | /// DominanceInfo caches per region and never notices IR edits, so this doubles |
| 38 | /// as the rewrite listener and drops a region's cached tree whenever its block |
| 39 | /// list changes. Successor edits would need notifyOperationModified as well; no |
| 40 | /// pattern here makes any. |
| 41 | class RewriteDominanceInfo final : public RewriterBase::Listener { |
| 42 | public: |
| 43 | DominanceInfo &getDominanceInfo() { return domInfo; } |
| 44 | |
| 45 | void notifyBlockInserted(Block *block, Region *previous, |
| 46 | Region::iterator previousIt) override { |
| 47 | domInfo.invalidate(region: block->getParent(), /*recursive=*/false); |
| 48 | if (previous) |
| 49 | domInfo.invalidate(region: previous, /*recursive=*/false); |
| 50 | } |
| 51 | |
| 52 | void notifyBlockErased(Block *block) override { |
| 53 | domInfo.invalidate(region: block->getParent(), /*recursive=*/false); |
| 54 | } |
| 55 | |
| 56 | private: |
| 57 | DominanceInfo domInfo; |
| 58 | }; |
| 59 | |
| 60 | /// Find the `cir.store` operation that stores to the given alloca and dominates |
| 61 | /// the given load operation. Dominance calculation is done through the given |
| 62 | /// DominanceInfo object. |
| 63 | /// |
| 64 | /// Return nullptr if no such store operation exists or if multiple store |
| 65 | /// operations satisfy the criteria. |
| 66 | cir::StoreOp findDominatingInitOp(cir::AllocaOp alloca, cir::LoadOp load, |
| 67 | const DominanceInfo &domInfo) { |
| 68 | cir::StoreOp result; |
| 69 | |
| 70 | // Walk through all uses of the alloca and visit the store operations that |
| 71 | // store to the alloca |
| 72 | for (const mlir::OpOperand &use : alloca->getUses()) { |
| 73 | auto store = mlir::dyn_cast<cir::StoreOp>(Val: use.getOwner()); |
| 74 | if (!store) |
| 75 | continue; |
| 76 | |
| 77 | // `cir.store` has two operands, we're only interested if the store is |
| 78 | // storing into the alloca, not if the store is storing the address of the |
| 79 | // alloca slot into somewhere else |
| 80 | if (use.getOperandNumber() != cir::StoreOp::odsIndex_addr) |
| 81 | continue; |
| 82 | |
| 83 | if (domInfo.dominates(a: store, b: load)) { |
| 84 | if (result) { |
| 85 | // If we have already found a dominating store, then there are multiple |
| 86 | // dominating stores, we intentionally don't simplify the load. |
| 87 | return nullptr; |
| 88 | } |
| 89 | result = store; |
| 90 | } |
| 91 | } |
| 92 | |
| 93 | return result; |
| 94 | } |
| 95 | |
| 96 | /// Simplify `cir.load` that loads from an alloca marked as "constant". |
| 97 | /// |
| 98 | /// For example: |
| 99 | /// |
| 100 | /// %0 = cir.alloca "x" align(4) const : !cir.ptr<!s32i> |
| 101 | /// cir.store %init, %0 : !s32i, !cir.ptr<!s32i> |
| 102 | /// %1 = cir.load %0 : !cir.ptr<!s32i> |
| 103 | /// |
| 104 | /// All uses of the load above could be replaced with the SSA value `%init`. |
| 105 | struct SimplifyConstantLoad final : public OpRewritePattern<LoadOp> { |
| 106 | SimplifyConstantLoad(MLIRContext *context, RewriteDominanceInfo &domInfo) |
| 107 | : OpRewritePattern(context), domInfo(domInfo) {} |
| 108 | |
| 109 | LogicalResult matchAndRewrite(LoadOp op, |
| 110 | PatternRewriter &rewriter) const override { |
| 111 | if (op.isVolatileOrAtomic()) |
| 112 | return mlir::failure(); |
| 113 | |
| 114 | auto allocaOp = op.getAddr().getDefiningOp<cir::AllocaOp>(); |
| 115 | if (!allocaOp || !allocaOp.getConstant()) |
| 116 | return mlir::failure(); |
| 117 | |
| 118 | cir::StoreOp initStoreOp = |
| 119 | findDominatingInitOp(alloca: allocaOp, load: op, domInfo: domInfo.getDominanceInfo()); |
| 120 | if (!initStoreOp) |
| 121 | return mlir::failure(); |
| 122 | if (initStoreOp.isVolatileOrAtomic()) { |
| 123 | // We intentionally act conservatively here and we don't want to simplify |
| 124 | // the load if the corresponding store is either volatile or atomic. |
| 125 | return mlir::failure(); |
| 126 | } |
| 127 | |
| 128 | rewriter.replaceOp(op, newValues: initStoreOp.getValue()); |
| 129 | return mlir::success(); |
| 130 | } |
| 131 | |
| 132 | private: |
| 133 | RewriteDominanceInfo &domInfo; |
| 134 | }; |
| 135 | |
| 136 | /// Simplify suitable ternary operations into select operations. |
| 137 | /// |
| 138 | /// For now we only simplify those ternary operations whose true and false |
| 139 | /// branches directly yield a value or a constant. That is, both of the true and |
| 140 | /// the false branch must either contain a cir.yield operation as the only |
| 141 | /// operation in the branch, or contain a cir.const operation followed by a |
| 142 | /// cir.yield operation that yields the constant value. |
| 143 | /// |
| 144 | /// For example, we will simplify the following ternary operation: |
| 145 | /// |
| 146 | /// %0 = ... |
| 147 | /// %1 = cir.ternary (%condition, true { |
| 148 | /// %2 = cir.const ... |
| 149 | /// cir.yield %2 |
| 150 | /// } false { |
| 151 | /// cir.yield %0 |
| 152 | /// |
| 153 | /// into the following sequence of operations: |
| 154 | /// |
| 155 | /// %1 = cir.const ... |
| 156 | /// %0 = cir.select if %condition then %1 else %2 |
| 157 | struct SimplifyTernary final : public OpRewritePattern<TernaryOp> { |
| 158 | using OpRewritePattern<TernaryOp>::OpRewritePattern; |
| 159 | |
| 160 | LogicalResult matchAndRewrite(TernaryOp op, |
| 161 | PatternRewriter &rewriter) const override { |
| 162 | if (op->getNumResults() != 1) |
| 163 | return mlir::failure(); |
| 164 | |
| 165 | if (!isSimpleTernaryBranch(region&: op.getTrueRegion()) || |
| 166 | !isSimpleTernaryBranch(region&: op.getFalseRegion())) |
| 167 | return mlir::failure(); |
| 168 | |
| 169 | cir::YieldOp trueBranchYieldOp = |
| 170 | mlir::cast<cir::YieldOp>(Val: op.getTrueRegion().front().getTerminator()); |
| 171 | cir::YieldOp falseBranchYieldOp = |
| 172 | mlir::cast<cir::YieldOp>(Val: op.getFalseRegion().front().getTerminator()); |
| 173 | mlir::Value trueValue = trueBranchYieldOp.getArgs()[0]; |
| 174 | mlir::Value falseValue = falseBranchYieldOp.getArgs()[0]; |
| 175 | |
| 176 | rewriter.inlineBlockBefore(source: &op.getTrueRegion().front(), op); |
| 177 | rewriter.inlineBlockBefore(source: &op.getFalseRegion().front(), op); |
| 178 | rewriter.eraseOp(op: trueBranchYieldOp); |
| 179 | rewriter.eraseOp(op: falseBranchYieldOp); |
| 180 | rewriter.replaceOpWithNewOp<cir::SelectOp>(op, args: op.getCond(), args&: trueValue, |
| 181 | args&: falseValue); |
| 182 | |
| 183 | return mlir::success(); |
| 184 | } |
| 185 | |
| 186 | private: |
| 187 | bool isSimpleTernaryBranch(mlir::Region ®ion) const { |
| 188 | if (!region.hasOneBlock()) |
| 189 | return false; |
| 190 | |
| 191 | mlir::Block &onlyBlock = region.front(); |
| 192 | mlir::Block::OpListType &ops = onlyBlock.getOperations(); |
| 193 | |
| 194 | // The region/block could only contain at most 2 operations. |
| 195 | if (ops.size() > 2) |
| 196 | return false; |
| 197 | |
| 198 | if (ops.size() == 1) { |
| 199 | // The region/block only contain a cir.yield operation. |
| 200 | return true; |
| 201 | } |
| 202 | |
| 203 | // Check whether the region/block contains a cir.const followed by a |
| 204 | // cir.yield that yields the value. |
| 205 | auto yieldOp = mlir::cast<cir::YieldOp>(Val: onlyBlock.getTerminator()); |
| 206 | auto yieldValueDefOp = |
| 207 | yieldOp.getArgs()[0].getDefiningOp<cir::ConstantOp>(); |
| 208 | return yieldValueDefOp && yieldValueDefOp->getBlock() == &onlyBlock; |
| 209 | } |
| 210 | }; |
| 211 | |
| 212 | /// Simplify select operations with boolean constants into simpler forms. |
| 213 | /// |
| 214 | /// This pattern simplifies select operations where both true and false values |
| 215 | /// are boolean constants. Two specific cases are handled: |
| 216 | /// |
| 217 | /// 1. When selecting between true and false based on a condition, |
| 218 | /// the operation simplifies to just the condition itself: |
| 219 | /// |
| 220 | /// %0 = cir.select if %condition then true else false |
| 221 | /// -> |
| 222 | /// (replaced with %condition directly) |
| 223 | /// |
| 224 | /// 2. When selecting between false and true based on a condition, |
| 225 | /// the operation simplifies to the logical negation of the condition: |
| 226 | /// |
| 227 | /// %0 = cir.select if %condition then false else true |
| 228 | /// -> |
| 229 | /// %0 = cir.not %condition |
| 230 | struct SimplifySelect : public OpRewritePattern<SelectOp> { |
| 231 | using OpRewritePattern<SelectOp>::OpRewritePattern; |
| 232 | |
| 233 | LogicalResult matchAndRewrite(SelectOp op, |
| 234 | PatternRewriter &rewriter) const final { |
| 235 | auto trueValueOp = op.getTrueValue().getDefiningOp<cir::ConstantOp>(); |
| 236 | auto falseValueOp = op.getFalseValue().getDefiningOp<cir::ConstantOp>(); |
| 237 | if (!trueValueOp || !falseValueOp) |
| 238 | return mlir::failure(); |
| 239 | |
| 240 | auto trueValue = trueValueOp.getValueAttr<cir::BoolAttr>(); |
| 241 | auto falseValue = falseValueOp.getValueAttr<cir::BoolAttr>(); |
| 242 | if (!trueValue || !falseValue) |
| 243 | return mlir::failure(); |
| 244 | |
| 245 | // cir.select if %0 then #true else #false -> %0 |
| 246 | if (trueValue.getValue() && !falseValue.getValue()) { |
| 247 | rewriter.replaceAllUsesWith(from: op, to: op.getCondition()); |
| 248 | rewriter.eraseOp(op); |
| 249 | return mlir::success(); |
| 250 | } |
| 251 | |
| 252 | // cir.select if %0 then #false else #true -> cir.not %0 |
| 253 | if (!trueValue.getValue() && falseValue.getValue()) { |
| 254 | rewriter.replaceOpWithNewOp<cir::NotOp>(op, args: op.getCondition()); |
| 255 | return mlir::success(); |
| 256 | } |
| 257 | |
| 258 | return mlir::failure(); |
| 259 | } |
| 260 | }; |
| 261 | |
| 262 | /// Simplify `cir.switch` operations by folding cascading cases |
| 263 | /// into a single `cir.case` with the `anyof` kind. |
| 264 | /// |
| 265 | /// This pattern identifies cascading cases within a `cir.switch` operation. |
| 266 | /// Cascading cases are defined as consecutive `cir.case` operations of kind |
| 267 | /// `equal`, each containing a single `cir.yield` operation in their body. |
| 268 | /// |
| 269 | /// The pattern merges these cascading cases into a single `cir.case` operation |
| 270 | /// with kind `anyof`, aggregating all the case values. |
| 271 | /// |
| 272 | /// The merging process continues until a `cir.case` with a different body |
| 273 | /// (e.g., containing `cir.break` or compound stmt) is encountered, which |
| 274 | /// breaks the chain. |
| 275 | /// |
| 276 | /// Example: |
| 277 | /// |
| 278 | /// Before: |
| 279 | /// cir.case equal, [#cir.int<0> : !s32i] { |
| 280 | /// cir.yield |
| 281 | /// } |
| 282 | /// cir.case equal, [#cir.int<1> : !s32i] { |
| 283 | /// cir.yield |
| 284 | /// } |
| 285 | /// cir.case equal, [#cir.int<2> : !s32i] { |
| 286 | /// cir.break |
| 287 | /// } |
| 288 | /// |
| 289 | /// After applying SimplifySwitch: |
| 290 | /// cir.case anyof, [#cir.int<0> : !s32i, #cir.int<1> : !s32i, #cir.int<2> : |
| 291 | /// !s32i] { |
| 292 | /// cir.break |
| 293 | /// } |
| 294 | struct SimplifySwitch : public OpRewritePattern<SwitchOp> { |
| 295 | using OpRewritePattern<SwitchOp>::OpRewritePattern; |
| 296 | LogicalResult matchAndRewrite(SwitchOp op, |
| 297 | PatternRewriter &rewriter) const override { |
| 298 | |
| 299 | LogicalResult changed = mlir::failure(); |
| 300 | SmallVector<CaseOp, 8> cases; |
| 301 | SmallVector<CaseOp, 4> cascadingCases; |
| 302 | SmallVector<mlir::Attribute, 4> cascadingCaseValues; |
| 303 | |
| 304 | op.collectCases(cases); |
| 305 | if (cases.empty()) |
| 306 | return mlir::failure(); |
| 307 | |
| 308 | auto resetMergeState = [&]() { |
| 309 | cascadingCases.clear(); |
| 310 | cascadingCaseValues.clear(); |
| 311 | }; |
| 312 | |
| 313 | auto flushMergedOps = [&]() { |
| 314 | for (CaseOp &c : cascadingCases) |
| 315 | rewriter.eraseOp(op: c); |
| 316 | resetMergeState(); |
| 317 | }; |
| 318 | |
| 319 | auto mergeCascadingInto = [&](CaseOp &target) { |
| 320 | rewriter.modifyOpInPlace(root: target, callable: [&]() { |
| 321 | target.setValueAttr(rewriter.getArrayAttr(value: cascadingCaseValues)); |
| 322 | target.setKind(CaseOpKind::Anyof); |
| 323 | }); |
| 324 | changed = mlir::success(); |
| 325 | }; |
| 326 | |
| 327 | // Merge all pending cascading cases into the last one collected, which |
| 328 | // survives as a distinct `cir.case`; the rest are erased since their |
| 329 | // values have been folded into it. |
| 330 | auto mergeLastCascadingAndFlush = [&]() { |
| 331 | assert(!cir::MissingFeatures::foldRangeCase()); |
| 332 | CaseOp lastCascadingCase = cascadingCases.back(); |
| 333 | mergeCascadingInto(lastCascadingCase); |
| 334 | cascadingCases.pop_back(); |
| 335 | flushMergedOps(); |
| 336 | }; |
| 337 | |
| 338 | for (CaseOp c : cases) { |
| 339 | // Cascading cases must be textually adjacent to the previously |
| 340 | // collected cascading case. This is false when something is in the |
| 341 | // way (e.g. a goto) or when the previous cascading case was found |
| 342 | // nested inside a sibling case's body (e.g. a case label that falls |
| 343 | // through into a compound statement) rather than next to `c`. |
| 344 | bool isAdjacentToLastCascadingCase = |
| 345 | !cascadingCases.empty() && |
| 346 | c->getPrevNode() == cascadingCases.back().getOperation(); |
| 347 | |
| 348 | if (!cascadingCases.empty() && !isAdjacentToLastCascadingCase) { |
| 349 | if (cascadingCases.size() > 1) |
| 350 | mergeLastCascadingAndFlush(); |
| 351 | else |
| 352 | resetMergeState(); |
| 353 | } |
| 354 | |
| 355 | cir::CaseOpKind kind = c.getKind(); |
| 356 | if (kind == cir::CaseOpKind::Equal && |
| 357 | isa<YieldOp>(Val: c.getCaseRegion().front().front())) { |
| 358 | // If the case contains only a YieldOp, collect it for cascading merge |
| 359 | cascadingCases.push_back(Elt: c); |
| 360 | cascadingCaseValues.push_back(Elt: c.getValue()[0]); |
| 361 | } else if (kind == cir::CaseOpKind::Equal && !cascadingCases.empty()) { |
| 362 | // merge previously collected cascading cases |
| 363 | cascadingCaseValues.push_back(Elt: c.getValue()[0]); |
| 364 | mergeCascadingInto(c); |
| 365 | flushMergedOps(); |
| 366 | } else if (kind != cir::CaseOpKind::Equal && cascadingCases.size() > 1) { |
| 367 | // If a Default, Anyof or Range case is found and there are previous |
| 368 | // cascading cases, merge all of them into the last cascading case. |
| 369 | // We don't currently fold case range statements with other case |
| 370 | // statements. |
| 371 | mergeLastCascadingAndFlush(); |
| 372 | } else { |
| 373 | resetMergeState(); |
| 374 | } |
| 375 | } |
| 376 | |
| 377 | // Edge case: all cases are simple cascading cases |
| 378 | if (cascadingCases.size() == cases.size()) |
| 379 | mergeLastCascadingAndFlush(); |
| 380 | |
| 381 | return changed; |
| 382 | } |
| 383 | }; |
| 384 | |
| 385 | struct SimplifyVecSplat : public OpRewritePattern<VecSplatOp> { |
| 386 | using OpRewritePattern<VecSplatOp>::OpRewritePattern; |
| 387 | LogicalResult matchAndRewrite(VecSplatOp op, |
| 388 | PatternRewriter &rewriter) const override { |
| 389 | mlir::Value splatValue = op.getValue(); |
| 390 | auto constant = splatValue.getDefiningOp<cir::ConstantOp>(); |
| 391 | if (!constant) |
| 392 | return mlir::failure(); |
| 393 | |
| 394 | auto value = constant.getValue(); |
| 395 | if (!mlir::isa_and_nonnull<cir::IntAttr>(Val: value) && |
| 396 | !mlir::isa_and_nonnull<cir::FPAttr>(Val: value)) |
| 397 | return mlir::failure(); |
| 398 | |
| 399 | // FIXME(CIR): We should consider making a matrix constant attribute so that |
| 400 | // we can simplify it here too. |
| 401 | assert(!MissingFeatures::matrixType()); |
| 402 | auto resultType = mlir::dyn_cast<cir::VectorType>(Val: op.getResult().getType()); |
| 403 | if (!resultType || resultType.isScalable()) |
| 404 | return mlir::failure(); |
| 405 | SmallVector<mlir::Attribute, 16> elements(resultType.getFixedSize(), value); |
| 406 | auto constVecAttr = cir::ConstVectorAttr::get( |
| 407 | type: resultType, elts: mlir::ArrayAttr::get(context: getContext(), value: elements)); |
| 408 | |
| 409 | rewriter.replaceOpWithNewOp<cir::ConstantOp>(op, args&: constVecAttr); |
| 410 | return mlir::success(); |
| 411 | } |
| 412 | }; |
| 413 | |
| 414 | //===----------------------------------------------------------------------===// |
| 415 | // CIRSimplifyPass |
| 416 | //===----------------------------------------------------------------------===// |
| 417 | |
| 418 | struct CIRSimplifyPass : public impl::CIRSimplifyBase<CIRSimplifyPass> { |
| 419 | using CIRSimplifyBase::CIRSimplifyBase; |
| 420 | |
| 421 | void runOnOperation() override; |
| 422 | }; |
| 423 | |
| 424 | void populateMergeCleanupPatterns(RewritePatternSet &patterns, |
| 425 | RewriteDominanceInfo &domInfo) { |
| 426 | // clang-format off |
| 427 | patterns.add< |
| 428 | SimplifyTernary, |
| 429 | SimplifySelect, |
| 430 | SimplifySwitch, |
| 431 | SimplifyVecSplat |
| 432 | >(arg: patterns.getContext()); |
| 433 | // clang-format on |
| 434 | patterns.add<SimplifyConstantLoad>(arg: patterns.getContext(), args&: domInfo); |
| 435 | } |
| 436 | |
| 437 | void CIRSimplifyPass::runOnOperation() { |
| 438 | // Collect rewrite patterns. SimplifyConstantLoad queries dominance, so the |
| 439 | // dominance info doubles as the driver's listener to stay coherent. |
| 440 | RewriteDominanceInfo domInfo; |
| 441 | RewritePatternSet patterns(&getContext()); |
| 442 | populateMergeCleanupPatterns(patterns, domInfo); |
| 443 | |
| 444 | // Collect operations to apply patterns. |
| 445 | llvm::SmallVector<Operation *, 16> ops; |
| 446 | getOperation()->walk(callback: [&](Operation *op) { |
| 447 | if (isa<TernaryOp, SelectOp, SwitchOp, VecSplatOp, LoadOp>(Val: op)) |
| 448 | ops.push_back(Elt: op); |
| 449 | }); |
| 450 | |
| 451 | // Apply patterns. Scope the rewrite to the body region, which encloses |
| 452 | // the common ancestor the driver would otherwise search for. |
| 453 | GreedyRewriteConfig config; |
| 454 | config.setScope(&getOperation()->getRegion(index: 0)); |
| 455 | config.setListener(&domInfo); |
| 456 | if (applyOpPatternsGreedily(ops, patterns: std::move(patterns), config).failed()) |
| 457 | signalPassFailure(); |
| 458 | } |
| 459 | |
| 460 | } // namespace |
| 461 | |
| 462 | std::unique_ptr<Pass> mlir::createCIRSimplifyPass() { |
| 463 | return std::make_unique<CIRSimplifyPass>(); |
| 464 | } |
| 465 | |