a03b439af3396be798d3f11d945f2d5541444a02
[lldb.git] / mlir / include / mlir / Transforms / Passes.td
1 //===-- Passes.td - Transforms pass definition file --------*- tablegen -*-===//
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 // This file contains definitions for passes within the Transforms/ directory.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #ifndef MLIR_TRANSFORMS_PASSES
14 #define MLIR_TRANSFORMS_PASSES
15
16 include "mlir/Pass/PassBase.td"
17
18 def AffineLoopFusion : FunctionPass<"affine-loop-fusion"> {
19   let summary = "Fuse affine loop nests";
20   let description = [{
21     This pass performs fusion of loop nests using a slicing-based approach. It
22     combines two fusion strategies: producer-consumer fusion and sibling fusion.
23     Producer-consumer fusion is aimed at fusing pairs of loops where the first
24     one writes to a memref that the second reads. Sibling fusion targets pairs
25     of loops that share no dependences between them but that load from the same
26     memref. The fused loop nests, when possible, are rewritten to access
27     significantly smaller local buffers instead of the original memref's, and
28     the latter are often either completely optimized away or contracted. This
29     transformation leads to enhanced locality and lower memory footprint through
30     the elimination or contraction of temporaries/intermediate memref's. These
31     benefits are sometimes achieved at the expense of redundant computation
32     through a cost model that evaluates available choices such as the depth at
33     which a source slice should be materialized in the designation slice.
34
35     Example 1: Producer-consumer fusion.
36     Input:
37     ```mlir
38     func @producer_consumer_fusion(%arg0: memref<10xf32>, %arg1: memref<10xf32>) {
39       %0 = alloc() : memref<10xf32>
40       %1 = alloc() : memref<10xf32>
41       %cst = constant 0.000000e+00 : f32
42       affine.for %arg2 = 0 to 10 {
43         affine.store %cst, %0[%arg2] : memref<10xf32>
44         affine.store %cst, %1[%arg2] : memref<10xf32>
45       }
46       affine.for %arg2 = 0 to 10 {
47         %2 = affine.load %0[%arg2] : memref<10xf32>
48         %3 = addf %2, %2 : f32
49         affine.store %3, %arg0[%arg2] : memref<10xf32>
50       }
51       affine.for %arg2 = 0 to 10 {
52         %2 = affine.load %1[%arg2] : memref<10xf32>
53         %3 = mulf %2, %2 : f32
54         affine.store %3, %arg1[%arg2] : memref<10xf32>
55       }
56       return
57     }
58     ```
59     Output:
60     ```mlir
61     func @producer_consumer_fusion(%arg0: memref<10xf32>, %arg1: memref<10xf32>) {
62       %0 = alloc() : memref<1xf32>
63       %1 = alloc() : memref<1xf32>
64       %cst = constant 0.000000e+00 : f32
65       affine.for %arg2 = 0 to 10 {
66         affine.store %cst, %0[0] : memref<1xf32>
67         affine.store %cst, %1[0] : memref<1xf32>
68         %2 = affine.load %1[0] : memref<1xf32>
69         %3 = mulf %2, %2 : f32
70         affine.store %3, %arg1[%arg2] : memref<10xf32>
71         %4 = affine.load %0[0] : memref<1xf32>
72         %5 = addf %4, %4 : f32
73         affine.store %5, %arg0[%arg2] : memref<10xf32>
74       }
75       return
76     }
77     ```
78
79     Example 2: Sibling fusion.
80     Input:
81     ```mlir
82     func @sibling_fusion(%arg0: memref<10x10xf32>, %arg1: memref<10x10xf32>,
83                          %arg2: memref<10x10xf32>, %arg3: memref<10x10xf32>,
84                          %arg4: memref<10x10xf32>) {
85       affine.for %arg5 = 0 to 3 {
86         affine.for %arg6 = 0 to 3 {
87           %0 = affine.load %arg0[%arg5, %arg6] : memref<10x10xf32>
88           %1 = affine.load %arg1[%arg5, %arg6] : memref<10x10xf32>
89           %2 = mulf %0, %1 : f32
90           affine.store %2, %arg3[%arg5, %arg6] : memref<10x10xf32>
91         }
92       }
93       affine.for %arg5 = 0 to 3 {
94         affine.for %arg6 = 0 to 3 {
95           %0 = affine.load %arg0[%arg5, %arg6] : memref<10x10xf32>
96           %1 = affine.load %arg2[%arg5, %arg6] : memref<10x10xf32>
97           %2 = addf %0, %1 : f32
98           affine.store %2, %arg4[%arg5, %arg6] : memref<10x10xf32>
99         }
100       }
101       return
102     }
103     ```
104     Output:
105     ```mlir
106     func @sibling_fusion(%arg0: memref<10x10xf32>, %arg1: memref<10x10xf32>,
107                          %arg2: memref<10x10xf32>, %arg3: memref<10x10xf32>,
108                          %arg4: memref<10x10xf32>) {
109       affine.for %arg5 = 0 to 3 {
110         affine.for %arg6 = 0 to 3 {
111           %0 = affine.load %arg0[%arg5, %arg6] : memref<10x10xf32>
112           %1 = affine.load %arg1[%arg5, %arg6] : memref<10x10xf32>
113           %2 = mulf %0, %1 : f32
114           affine.store %2, %arg3[%arg5, %arg6] : memref<10x10xf32>
115           %3 = affine.load %arg0[%arg5, %arg6] : memref<10x10xf32>
116           %4 = affine.load %arg2[%arg5, %arg6] : memref<10x10xf32>
117           %5 = addf %3, %4 : f32
118           affine.store %5, %arg4[%arg5, %arg6] : memref<10x10xf32>
119         }
120       }
121       return
122     }
123     ```
124   }];
125   let constructor = "mlir::createLoopFusionPass()";
126   let options = [
127     Option<"computeToleranceThreshold", "fusion-compute-tolerance", "double",
128            /*default=*/"0.30f", "Fractional increase in additional computation "
129                                 "tolerated while fusing">,
130     Option<"fastMemorySpace", "fusion-fast-mem-space", "unsigned",
131            /*default=*/"0",
132            "Faster memory space number to promote fusion buffers to">,
133     Option<"localBufSizeThreshold", "fusion-local-buf-threshold", "uint64_t",
134            /*default=*/"0", "Threshold size (KiB) for promoting local buffers "
135                             "to fast memory space">,
136     Option<"maximalFusion", "fusion-maximal", "bool", /*default=*/"false",
137            "Enables maximal loop fusion">,
138   ];
139 }
140
141 def AffinePipelineDataTransfer
142     : FunctionPass<"affine-pipeline-data-transfer"> {
143   let summary = "Pipeline non-blocking data transfers between explicitly "
144                 "managed levels of the memory hierarchy";
145   let description = [{
146     This pass performs a transformation to overlap non-blocking DMA operations
147     in a loop with computations through double buffering. This is achieved by
148     advancing dma_start operations with respect to other operations.
149
150     Input
151
152     ```mlir
153     func @pipelinedatatransfer() {
154       %0 = alloc() : memref<256xf32>
155       %1 = alloc() : memref<32xf32, 1>
156       %2 = alloc() : memref<1xf32>
157       %c0 = constant 0 : index
158       %c128 = constant 128 : index
159       affine.for %i0 = 0 to 8 {
160         affine.dma_start %0[%i0], %1[%i0], %2[%c0], %c128 : memref<256xf32>, memref<32xf32, 1>, memref<1xf32>
161         affine.dma_wait %2[%c0], %c128 : memref<1xf32>
162         %3 = affine.load %1[%i0] : memref<32xf32, 1>
163         %4 = "compute"(%3) : (f32) -> f32
164         affine.store %4, %1[%i0] : memref<32xf32, 1>
165       }
166       return
167     }
168     ```
169
170     Output
171
172     ```mlir
173     module {
174       func @pipelinedatatransfer() {
175         %c8 = constant 8 : index
176         %c0 = constant 0 : index
177         %0 = alloc() : memref<256xf32>
178         %c0_0 = constant 0 : index
179         %c128 = constant 128 : index
180         %1 = alloc() : memref<2x32xf32, 1>
181         %2 = alloc() : memref<2x1xf32>
182         affine.dma_start %0[%c0], %1[%c0 mod 2, %c0], %2[%c0 mod 2, symbol(%c0_0)], %c128 : memref<256xf32>, memref<2x32xf32, 1>, memref<2x1xf32>
183         affine.for %arg0 = 1 to 8 {
184           affine.dma_start %0[%arg0], %1[%arg0 mod 2, %arg0], %2[%arg0 mod 2, symbol(%c0_0)], %c128 : memref<256xf32>, memref<2x32xf32, 1>, memref<2x1xf32>
185           %8 = affine.apply #map3(%arg0)
186           %9 = affine.apply #map4(%8)
187           %10 = affine.apply #map4(%8)
188           affine.dma_wait %2[%8 mod 2, symbol(%c0_0)], %c128 : memref<2x1xf32>
189           %11 = affine.load %1[%8 mod 2, %8] : memref<2x32xf32, 1>
190           %12 = "compute"(%11) : (f32) -> f32
191           affine.store %12, %1[%8 mod 2, %8] : memref<2x32xf32, 1>
192         }
193         %3 = affine.apply #map3(%c8)
194         %4 = affine.apply #map4(%3)
195         %5 = affine.apply #map4(%3)
196         affine.dma_wait %2[%3 mod 2, symbol(%c0_0)], %c128 : memref<2x1xf32>
197         %6 = affine.load %1[%3 mod 2, %3] : memref<2x32xf32, 1>
198         %7 = "compute"(%6) : (f32) -> f32
199         affine.store %7, %1[%3 mod 2, %3] : memref<2x32xf32, 1>
200         dealloc %2 : memref<2x1xf32>
201         dealloc %1 : memref<2x32xf32, 1>
202         return
203       }
204     }
205     ```
206   }];
207   let constructor = "mlir::createPipelineDataTransferPass()";
208 }
209
210 def BufferDeallocation : FunctionPass<"buffer-deallocation"> {
211   let summary = "Adds all required dealloc operations for all allocations in the "
212                 "input program";
213   let description = [{
214     This pass implements an algorithm to automatically introduce all required
215     deallocation operations for all buffers in the input program. This ensures that
216     the resulting program does not have any memory leaks.
217
218
219     Input
220
221     ```mlir
222     #map0 = affine_map<(d0) -> (d0)>
223     module {
224       func @condBranch(%arg0: i1, %arg1: memref<2xf32>, %arg2: memref<2xf32>) {
225         cond_br %arg0, ^bb1, ^bb2
226       ^bb1:
227         br ^bb3(%arg1 : memref<2xf32>)
228       ^bb2:
229         %0 = alloc() : memref<2xf32>
230         linalg.generic {
231           args_in = 1 : i64,
232           args_out = 1 : i64,
233           indexing_maps = [#map0, #map0],
234           iterator_types = ["parallel"]} %arg1, %0 {
235         ^bb0(%gen1_arg0: f32, %gen1_arg1: f32):
236           %tmp1 = exp %gen1_arg0 : f32
237           linalg.yield %tmp1 : f32
238         }: memref<2xf32>, memref<2xf32>
239         br ^bb3(%0 : memref<2xf32>)
240       ^bb3(%1: memref<2xf32>):
241         "linalg.copy"(%1, %arg2) : (memref<2xf32>, memref<2xf32>) -> ()
242         return
243       }
244     }
245
246     ```
247
248     Output
249
250     ```mlir
251     #map0 = affine_map<(d0) -> (d0)>
252     module {
253       func @condBranch(%arg0: i1, %arg1: memref<2xf32>, %arg2: memref<2xf32>) {
254         cond_br %arg0, ^bb1, ^bb2
255       ^bb1:  // pred: ^bb0
256         %0 = alloc() : memref<2xf32>
257         linalg.copy(%arg1, %0) : memref<2xf32>, memref<2xf32>
258         br ^bb3(%0 : memref<2xf32>)
259       ^bb2:  // pred: ^bb0
260         %1 = alloc() : memref<2xf32>
261         linalg.generic {
262           args_in = 1 : i64,
263           args_out = 1 : i64,
264           indexing_maps = [#map0, #map0],
265           iterator_types = ["parallel"]} %arg1, %1 {
266         ^bb0(%arg3: f32, %arg4: f32):  // no predecessors
267           %4 = exp %arg3 : f32
268           linalg.yield %4 : f32
269         }: memref<2xf32>, memref<2xf32>
270         %2 = alloc() : memref<2xf32>
271         linalg.copy(%1, %2) : memref<2xf32>, memref<2xf32>
272         dealloc %1 : memref<2xf32>
273         br ^bb3(%2 : memref<2xf32>)
274       ^bb3(%3: memref<2xf32>):  // 2 preds: ^bb1, ^bb2
275         linalg.copy(%3, %arg2) : memref<2xf32>, memref<2xf32>
276         dealloc %3 : memref<2xf32>
277         return
278       }
279
280     }
281     ```
282
283   }];
284   let constructor = "mlir::createBufferDeallocationPass()";
285   // TODO: this pass likely shouldn't depend on Linalg?
286   let dependentDialects = ["linalg::LinalgDialect"];
287 }
288
289 def BufferHoisting : FunctionPass<"buffer-hoisting"> {
290   let summary = "Optimizes placement of allocation operations by moving them "
291                 "into common dominators and out of nested regions";
292   let description = [{
293     This pass implements an approach to aggressively move allocations upwards
294     into common dominators and out of nested regions.
295   }];
296   let constructor = "mlir::createBufferHoistingPass()";
297 }
298
299 def BufferLoopHoisting : FunctionPass<"buffer-loop-hoisting"> {
300   let summary = "Optimizes placement of allocation operations by moving them "
301                 "out of loop nests";
302   let description = [{
303     This pass implements an approach to aggressively move allocations upwards
304     out of loop nests. It does not move allocations into common dominators.
305   }];
306   let constructor = "mlir::createBufferLoopHoistingPass()";
307 }
308
309 def PromoteBuffersToStack : FunctionPass<"promote-buffers-to-stack"> {
310   let summary = "Promotes heap-based allocations to automatically managed "
311                 "stack-based allocations";
312   let description = [{
313     This pass implements a simple algorithm to convert heap-based memory
314     allocations to stack-based ones. It uses a built-in heuristic to decide
315     whether it makes sense to convert an allocation. Furthermore, dynamic
316     shaped buffers that are limited by the rank of the tensor can be
317     converted. They are only transformed if they are considered to be small.
318   }];
319   let constructor = "mlir::createPromoteBuffersToStackPass()";
320   let options = [
321     Option<"maxAllocSizeInBytes", "max-alloc-size-in-bytes", "unsigned",
322            /*default=*/"1024",
323            "Maximal size in bytes to promote allocations to stack.">,
324     Option<"bitwidthOfIndexType", "bitwidth-of-index-type", "unsigned",
325            /*default=*/"64",
326            "Bitwidth of the index type. Used for size estimation.">,
327     Option<"maxRankOfAllocatedMemRef", "max-rank-of-allocated-memref", "unsigned",
328            /*default=*/"1",
329            "Maximal memref rank to promote dynamic buffers.">,
330   ];
331 }
332
333 def BufferResultsToOutParams : Pass<"buffer-results-to-out-params", "ModuleOp">  {
334   let summary = "Converts memref-typed function results to out-params";
335   let description = [{
336     Some calling conventions prefer to pass output memrefs as "out params". The
337     conversion to this calling convention must be done as an atomic
338     transformation of the entire program (hence this is a module pass).
339
340     For example, if a call is rewritten, the callee needs to be rewritten
341     otherwise the IR will end up invalid. Thus, this transformation
342     require an atomic change to the entire program (e.g. the whole module).
343
344     This pass is expected to run immediately after bufferization is finished.
345     At that point, tensor-typed results will have been converted to memref-typed
346     results, and can be consistently converted to out params.
347
348     All memref-typed results are appended to the function argument list.
349
350     The main issue with this pass (and the out-param calling convention) is that
351     buffers for results need to be allocated in the caller. This currently only
352     works for static shaped memrefs.
353   }];
354   let constructor = "mlir::createBufferResultsToOutParamsPass()";
355   let dependentDialects = ["linalg::LinalgDialect"];
356 }
357
358 def Canonicalizer : Pass<"canonicalize"> {
359   let summary = "Canonicalize operations";
360   let description = [{
361     This pass performs various types of canonicalizations over a set of
362     operations. See [Operation Canonicalization](Canonicalization.md) for more
363     details.
364   }];
365   let constructor = "mlir::createCanonicalizerPass()";
366 }
367
368 def CopyRemoval : FunctionPass<"copy-removal"> {
369   let summary = "Remove the redundant copies from input IR";
370   let constructor = "mlir::createCopyRemovalPass()";
371 }
372
373 def CSE : Pass<"cse"> {
374   let summary = "Eliminate common sub-expressions";
375   let description = [{
376     This pass implements a generalized algorithm for common sub-expression
377     elimination. This pass relies on information provided by the
378     `Memory SideEffect` interface to identify when it is safe to eliminate
379     operations. See [Common subexpression elimination](https://en.wikipedia.org/wiki/Common_subexpression_elimination)
380     for more general details on this optimization.
381   }];
382   let constructor = "mlir::createCSEPass()";
383   let statistics = [
384     Statistic<"numCSE", "num-cse'd", "Number of operations CSE'd">,
385     Statistic<"numDCE", "num-dce'd", "Number of operations DCE'd">
386   ];
387 }
388
389 def Inliner : Pass<"inline"> {
390   let summary = "Inline function calls";
391   let constructor = "mlir::createInlinerPass()";
392   let options = [
393     Option<"defaultPipelineStr", "default-pipeline", "std::string",
394            /*default=*/"", "The default optimizer pipeline used for callables">,
395     ListOption<"opPipelineStrs", "op-pipelines", "std::string",
396                "Callable operation specific optimizer pipelines (in the form "
397                "of `dialect.op(pipeline)`)",
398                "llvm::cl::MiscFlags::CommaSeparated">,
399     Option<"maxInliningIterations", "max-iterations", "unsigned",
400            /*default=*/"4",
401            "Maximum number of iterations when inlining within an SCC">,
402   ];
403 }
404
405 def FinalizingBufferize : FunctionPass<"finalizing-bufferize"> {
406   let summary = "Finalize a partial bufferization";
407   let description = [{
408     A bufferize pass that finalizes a partial bufferization by removing
409     remaining `tensor_load` and `tensor_to_memref` operations.
410
411     The removal of those operations is only possible if the operations only
412     exist in pairs, i.e., all uses of `tensor_load` operations are
413     `tensor_to_memref` operations.
414
415     This pass will fail if not all operations can be removed or if any operation
416     with tensor typed operands remains.
417   }];
418   let constructor = "mlir::createFinalizingBufferizePass()";
419 }
420
421 def LocationSnapshot : Pass<"snapshot-op-locations"> {
422   let summary = "Generate new locations from the current IR";
423   let description = [{
424     This pass allows for generating new locations from the IR during any stage
425     of compilation, by snapshotting the IR to a file and using that file to
426     generate new locations for the operations.
427
428     Depending on the value of the `tag` option, different resulting locations
429     may be generated:
430
431     * If unset, the original location of the operation is replaced.
432
433     Example:
434
435     ```mlir
436     // old:
437     ... loc("original_source.cpp":1:1)
438
439     // new:
440     ... loc("snapshot_source.mlir":10:10)
441     ```
442
443     * If set, the new location is fused with the original location in the form
444     of a [`Name Location`](Diagnostics.md#name-location) with the specified tag.
445
446     Example:
447
448     ```mlir
449     // old:
450     ... loc("original_source.cpp":1:1)
451
452     // new:
453     ... loc(fused["original_source.cpp":1:1, "snapshot"("snapshot_source.mlir":10:10)])
454     ```
455   }];
456   let constructor = "mlir::createLocationSnapshotPass()";
457   let options = [
458     Option<"fileName", "filename", "std::string", /*default=*/"",
459            "The filename to print the generated IR">,
460     Option<"tag", "tag", "std::string", /*default=*/"",
461            "A tag to use when fusing the new locations with the "
462            "original. If unset, the locations are replaced.">,
463   ];
464 }
465
466 def LoopCoalescing : FunctionPass<"loop-coalescing"> {
467   let summary = "Coalesce nested loops with independent bounds into a single "
468                 "loop";
469   let constructor = "mlir::createLoopCoalescingPass()";
470 }
471
472 def LoopInvariantCodeMotion : Pass<"loop-invariant-code-motion"> {
473   let summary = "Hoist loop invariant instructions outside of the loop";
474   let constructor = "mlir::createLoopInvariantCodeMotionPass()";
475 }
476
477 def MemRefDataFlowOpt : FunctionPass<"memref-dataflow-opt"> {
478   let summary = "Perform store/load forwarding for memrefs";
479   let description = [{
480     This pass performs store to load forwarding for memref's to eliminate memory
481     accesses and potentially the entire memref if all its accesses are
482     forwarded.
483
484     Input
485
486     ```mlir
487     func @store_load_affine_apply() -> memref<10x10xf32> {
488       %cf7 = constant 7.0 : f32
489       %m = alloc() : memref<10x10xf32>
490       affine.for %i0 = 0 to 10 {
491         affine.for %i1 = 0 to 10 {
492           affine.store %cf7, %m[%i0, %i1] : memref<10x10xf32>
493           %v0 = affine.load %m[%i0, %i1] : memref<10x10xf32>
494           %v1 = addf %v0, %v0 : f32
495         }
496       }
497       return %m : memref<10x10xf32>
498     }
499     ```
500
501     Output
502
503     ```mlir
504     module {
505       func @store_load_affine_apply() -> memref<10x10xf32> {
506         %cst = constant 7.000000e+00 : f32
507         %0 = alloc() : memref<10x10xf32>
508         affine.for %arg0 = 0 to 10 {
509           affine.for %arg1 = 0 to 10 {
510             affine.store %cst, %0[%arg0, %arg1] : memref<10x10xf32>
511             %1 = addf %cst, %cst : f32
512           }
513         }
514         return %0 : memref<10x10xf32>
515       }
516     }
517     ```
518   }];
519   let constructor = "mlir::createMemRefDataFlowOptPass()";
520 }
521
522 def NormalizeMemRefs : Pass<"normalize-memrefs", "ModuleOp"> {
523   let summary = "Normalize memrefs";
524    let description = [{
525     This pass transforms memref types with a non-trivial
526     [layout map](https://mlir.llvm.org/docs/LangRef/#layout-map) into
527     memref types with an identity layout map, e.g. (i, j) -> (i, j). This
528     pass is inter-procedural, in the sense that it can modify function
529     interfaces and call sites that pass memref types. In order to modify
530     memref types while preserving the original behavior, users of those
531     memref types are also modified to incorporate the resulting layout map.
532     For instance, an [AffineLoadOp]
533     (https://mlir.llvm.org/docs/Dialects/Affine/#affineload-affineloadop)
534     will be updated to compose the layout map with with the affine expression
535     contained in the op. Operations marked with the [MemRefsNormalizable]
536     (https://mlir.llvm.org/docs/Traits/#memrefsnormalizable) trait are
537     expected to be normalizable. Supported operations include affine
538     operations, std.alloc, std.dealloc, and std.return.
539
540     Given an appropriate layout map specified in the code, this transformation
541     can express tiled or linearized access to multi-dimensional data
542     structures, but will not modify memref types without an explicit layout
543     map.
544
545     Currently this pass is limited to only modify
546     functions where all memref types can be normalized. If a function
547     contains any operations that are not MemRefNormalizable, then the function
548     and any functions that call or call it will not be modified.
549
550     Input
551
552     ```mlir
553     #tile = affine_map<(i) -> (i floordiv 4, i mod 4)>
554     func @matmul(%A: memref<16xf64, #tile>,
555                  %B: index, %C: memref<16xf64>) -> (memref<16xf64, #tile>) {
556       affine.for %arg3 = 0 to 16 {
557             %a = affine.load %A[%arg3] : memref<16xf64, #tile>
558             %p = mulf %a, %a : f64
559             affine.store %p, %A[%arg3] : memref<16xf64, #tile>
560       }
561       %c = alloc() : memref<16xf64, #tile>
562       %d = affine.load %c[0] : memref<16xf64, #tile>
563       return %A: memref<16xf64, #tile>
564     }
565     ```
566
567     Output
568
569     ```mlir
570     func @matmul(%arg0: memref<4x4xf64>, %arg1: index, %arg2: memref<16xf64>)
571       -> memref<4x4xf64> {
572       affine.for %arg3 = 0 to 16 {
573         %3 = affine.load %arg0[%arg3 floordiv 4, %arg3 mod 4]: memref<4x4xf64>
574         %4 = mulf %3, %3 : f64
575         affine.store %4, %arg0[%arg3 floordiv 4, %arg3 mod 4]: memref<4x4xf64>
576       }
577       %0 = alloc() : memref<4x4xf64>
578       %1 = affine.apply #map1()
579       %2 = affine.load %0[0, 0] : memref<4x4xf64>
580       return %arg0 : memref<4x4xf64>
581     }
582     ```
583
584     Input
585
586     ```
587     #linear8 = affine_map<(i, j) -> (i * 8 + j)>
588     func @linearize(%arg0: memref<8x8xi32, #linear8>,
589                     %arg1: memref<8x8xi32, #linear8>,
590                     %arg2: memref<8x8xi32, #linear8>) {
591       %c8 = constant 8 : index
592       %c0 = constant 0 : index
593       %c1 = constant 1 : index
594       affine.for %arg3 = %c0 to %c8  {
595       affine.for %arg4 = %c0 to %c8  {
596         affine.for %arg5 = %c0 to %c8 {
597           %0 = affine.load %arg0[%arg3, %arg5] : memref<8x8xi32, #linear8>
598           %1 = affine.load %arg1[%arg5, %arg4] : memref<8x8xi32, #linear8>
599           %2 = affine.load %arg2[%arg3, %arg4] : memref<8x8xi32, #linear8>
600           %3 = muli %0, %1 : i32
601           %4 = addi %2, %3 : i32
602           affine.store %4, %arg2[%arg3, %arg4] : memref<8x8xi32, #linear8>
603         }
604       }
605       }
606       return
607     }
608     ```
609
610     Output
611
612     ```mlir
613     func @linearize(%arg0: memref<64xi32>,
614                     %arg1: memref<64xi32>,
615                     %arg2: memref<64xi32>) {
616     %c8 = constant 8 : index
617     %c0 = constant 0 : index
618     affine.for %arg3 = %c0 to %c8 {
619       affine.for %arg4 = %c0 to %c8 {
620         affine.for %arg5 = %c0 to %c8 {
621           %0 = affine.load %arg0[%arg3 * 8 + %arg5] : memref<64xi32>
622           %1 = affine.load %arg1[%arg5 * 8 + %arg4] : memref<64xi32>
623           %2 = affine.load %arg2[%arg3 * 8 + %arg4] : memref<64xi32>
624           %3 = muli %0, %1 : i32
625           %4 = addi %2, %3 : i32
626           affine.store %4, %arg2[%arg3 * 8 + %arg4] : memref<64xi32>
627         }
628       }
629     }
630     return
631   }
632   ```
633   }];
634   let constructor = "mlir::createNormalizeMemRefsPass()";
635 }
636
637 def ParallelLoopCollapsing : Pass<"parallel-loop-collapsing"> {
638   let summary = "Collapse parallel loops to use less induction variables";
639   let constructor = "mlir::createParallelLoopCollapsingPass()";
640   let options = [
641     ListOption<"clCollapsedIndices0", "collapsed-indices-0", "unsigned",
642                "Which loop indices to combine 0th loop index",
643                "llvm::cl::MiscFlags::CommaSeparated">,
644     ListOption<"clCollapsedIndices1", "collapsed-indices-1", "unsigned",
645                "Which loop indices to combine into the position 1 loop index",
646                "llvm::cl::MiscFlags::CommaSeparated">,
647     ListOption<"clCollapsedIndices2", "collapsed-indices-2", "unsigned",
648                "Which loop indices to combine into the position 2 loop index",
649                "llvm::cl::MiscFlags::CommaSeparated">,
650   ];
651 }
652
653 def PrintCFG : FunctionPass<"print-cfg-graph"> {
654   let summary = "Print CFG graph per-Region";
655   let constructor = "mlir::createPrintCFGGraphPass()";
656 }
657
658 def PrintOpStats : Pass<"print-op-stats"> {
659   let summary = "Print statistics of operations";
660   let constructor = "mlir::createPrintOpStatsPass()";
661 }
662
663 def PrintOp : Pass<"print-op-graph", "ModuleOp"> {
664   let summary = "Print op graph per-Region";
665   let constructor = "mlir::createPrintOpGraphPass()";
666 }
667
668 def SCCP : Pass<"sccp"> {
669   let summary = "Sparse Conditional Constant Propagation";
670   let description = [{
671     This pass implements a general algorithm for sparse conditional constant
672     propagation. This algorithm detects values that are known to be constant and
673     optimistically propagates this throughout the IR. Any values proven to be
674     constant are replaced, and removed if possible.
675
676     This implementation is based on the algorithm described by Wegman and Zadeck
677     in [“Constant Propagation with Conditional Branches”](https://dl.acm.org/doi/10.1145/103135.103136) (1991).
678   }];
679   let constructor = "mlir::createSCCPPass()";
680 }
681
682 def StripDebugInfo : Pass<"strip-debuginfo"> {
683   let summary = "Strip debug info from all operations";
684   let description = [{
685     This pass strips the IR of any location information, by replacing all
686     operation locations with [`unknown`](Diagnostics.md#unknown-location).
687   }];
688   let constructor = "mlir::createStripDebugInfoPass()";
689 }
690
691 def SymbolDCE : Pass<"symbol-dce"> {
692   let summary = "Eliminate dead symbols";
693   let description = [{
694     This pass deletes all symbols that are found to be unreachable. This is done
695     by computing the set of operations that are known to be live, propagating
696     that liveness to other symbols, and then deleting all symbols that are not
697     within this live set. Live symbols are those that have a
698     [visibility](SymbolsAndSymbolTables.md#symbol-visibility) that extends
699     beyond the IR, e.g. `public`, or those that are referenced by live symbols
700     or other non-Symbol operations.
701
702     For example, consider the following input:
703
704     ```mlir
705     func private @dead_private_function()
706     func private @live_private_function()
707
708     // Note: The `public` isn't necessary here, as this is the default.
709     func public @public_function() {
710       "foo.return"() {uses = [@live_private_function]} : () -> ()
711     }
712     ```
713
714     A known live function, `public_function`, contains a reference to an
715     otherwise non-live function `live_private_function`. After running
716     `symbol-dce`, only these two symbols should remain, as the final symbol
717     `dead_private_function` is not visible outside of the current IR and there
718     are no links to known-live operations. After running, we get the expected:
719
720     ```mlir
721     func private @live_private_function()
722
723     func public @public_function() {
724       "foo.return"() {uses = [@live_private_function]} : () -> ()
725     }
726     ```
727
728     See [Symbols and SymbolTables](SymbolsAndSymbolTables.md) for more
729     information on `Symbols`.
730   }];
731   let constructor = "mlir::createSymbolDCEPass()";
732 }
733 #endif // MLIR_TRANSFORMS_PASSES