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
22using namespace mlir;
23using namespace cir;
24
25namespace 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
34namespace {
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.
41class RewriteDominanceInfo final : public RewriterBase::Listener {
42public:
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
56private:
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.
66cir::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`.
105struct 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
132private:
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
157struct 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
186private:
187 bool isSimpleTernaryBranch(mlir::Region &region) 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
230struct 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/// }
294struct 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
385struct 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
418struct CIRSimplifyPass : public impl::CIRSimplifyBase<CIRSimplifyPass> {
419 using CIRSimplifyBase::CIRSimplifyBase;
420
421 void runOnOperation() override;
422};
423
424void 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
437void 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
462std::unique_ptr<Pass> mlir::createCIRSimplifyPass() {
463 return std::make_unique<CIRSimplifyPass>();
464}
465