ArrayToScalarPass.cpp File Reference

This file implements the -llzk-array-to-scalar pass. More...

#include "llzk/Dialect/Array/IR/Dialect.h"
#include "llzk/Dialect/Array/IR/Ops.h"
#include "llzk/Dialect/Array/IR/Types.h"
#include "llzk/Dialect/Array/Transforms/TransformationPasses.h"
#include "llzk/Dialect/Array/Util/ArrayTypeHelper.h"
#include "llzk/Dialect/Bool/IR/Dialect.h"
#include "llzk/Dialect/Cast/IR/Dialect.h"
#include "llzk/Dialect/Constrain/IR/Dialect.h"
#include "llzk/Dialect/Felt/IR/Dialect.h"
#include "llzk/Dialect/Function/IR/Dialect.h"
#include "llzk/Dialect/Function/IR/Ops.h"
#include "llzk/Dialect/Include/IR/Dialect.h"
#include "llzk/Dialect/LLZK/IR/Dialect.h"
#include "llzk/Dialect/LLZK/IR/Ops.h"
#include "llzk/Dialect/POD/IR/Dialect.h"
#include "llzk/Dialect/Polymorphic/IR/Dialect.h"
#include "llzk/Dialect/RAM/IR/Dialect.h"
#include "llzk/Dialect/String/IR/Dialect.h"
#include "llzk/Dialect/Struct/IR/Ops.h"
#include "llzk/Transforms/LLZKConversionUtils.h"
#include "llzk/Transforms/LLZKTransformationPasses.h"
#include "llzk/Transforms/SpecializedMemoryPasses.h"
#include "llzk/Util/Compare.h"
#include "llzk/Util/Concepts.h"
#include <mlir/Dialect/SCF/IR/SCF.h>
#include <mlir/IR/BuiltinOps.h>
#include <mlir/Pass/PassManager.h>
#include <mlir/Transforms/DialectConversion.h>
#include <mlir/Transforms/Passes.h>
#include <llvm/Support/Debug.h>
#include <optional>
#include "llzk/Dialect/Array/Transforms/TransformationPasses.h.inc"

Include dependency graph for ArrayToScalarPass.cpp:

Go to the source code of this file.

Classes
class	llzk::array::impl::ArrayToScalarPassBase< DerivedT >

Namespaces
namespace	llzk
namespace	llzk::array
namespace	llzk::array::impl

Macros
#define	GEN_PASS_DEF_ARRAYTOSCALARPASS
#define	DEBUG_TYPE   "llzk-array-to-scalar"

Functions
std::unique_ptr<::mlir::Pass >	llzk::array::impl::createArrayToScalarPass ()
std::unique_ptr<::mlir::Pass >	llzk::array::createArrayToScalarPass ()

Detailed Description

This file implements the -llzk-array-to-scalar pass.

The steps of this transformation are as follows:

1. Scan to find llzk.nondet ops that allocate uninitialized arrays and replace them with an equivalent array.new
2. Run a dialect conversion that replaces ArrayType struct members with N scalar members.
3. Run a dialect conversion that does the following:
   • Replace MemberReadOp and MemberWriteOp targeting the members that were split in step 1 so they instead perform scalar reads and writes from the new members. The transformation is local to the current op. Therefore, when replacing the MemberReadOp a new array is created locally and all uses of the MemberReadOp are replaced with the new array Value, then each scalar member read is followed by scalar write into the new array. Similarly, when replacing a MemberWriteOp, each element in the array operand needs a scalar read from the array followed by a scalar write to the new member. Making only local changes keeps this step simple and later steps will optimize.
   • Replace ArrayLengthOp with the constant size of the selected dimension.
   • Remove element initialization from CreateArrayOp and instead insert a list of WriteArrayOp immediately following.
   • Desugar InsertArrayOp and ExtractArrayOp into their element-wise scalar reads/writes.
   • Split arrays to scalars in FuncDefOp, CallOp, and ReturnOp and insert the necessary create/read/write ops so the changes are as local as possible (just as described for MemberReadOp and MemberWriteOp)
4. Replace branch-local reads (in scf.if) with the value written by a same-index write op that dominates the parent scf.if (because the passes below cannot handle that case).
5. Run MLIR "sroa" pass to split each array with linear size N into N arrays of size 1 (to prepare for "mem2reg" pass because its API cannot deal with splitting up memory).
6. Run MLIR "mem2reg" pass to convert all of the size 1 array allocation and access into SSA values. This pass also runs several standard optimizations so the final result is condensed.
7. Remove array allocations that become unread after memory promotion, then remove SSA values made dead by that cleanup.

Note: This transformation imposes a "last write wins" semantics on array elements. If different/configurable semantics are added in the future, some additional transformation would be necessary before/during this pass so that multiple writes to the same index can be handled properly while they still exist.

Note: This transformation will introduce a nondet op when there exists a read from an array index that was not earlier written to.

Definition in file ArrayToScalarPass.cpp.

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "llzk-array-to-scalar"

Definition at line 111 of file ArrayToScalarPass.cpp.

GEN_PASS_DEF_ARRAYTOSCALARPASS

#define GEN_PASS_DEF_ARRAYTOSCALARPASS

Definition at line 101 of file ArrayToScalarPass.cpp.