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/Felt/IR/Ops.h"
#include "llzk/Dialect/Function/IR/Dialect.h"
#include "llzk/Dialect/Function/IR/Ops.h"
#include "llzk/Dialect/Global/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/Polymorphic/IR/Ops.h"
#include "llzk/Dialect/RAM/IR/Dialect.h"
#include "llzk/Dialect/String/IR/Dialect.h"
#include "llzk/Dialect/String/IR/Ops.h"
#include "llzk/Dialect/Struct/IR/Ops.h"
#include "llzk/Transforms/ConversionUtils.h"
#include "llzk/Transforms/LLZKTransformationPasses.h"
#include "llzk/Transforms/SpecializedMemoryPasses.h"
#include "llzk/Util/Compare.h"
#include "llzk/Util/Concepts.h"
#include "llzk/Util/Walk.h"
#include <mlir/Dialect/Arith/IR/Arith.h>
#include <mlir/Dialect/SCF/IR/SCF.h>
#include <mlir/Dialect/UB/IR/UBOps.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 >
class	llzk::array::impl::StraightLineStaticArrayPromotionPassBase< DerivedT >

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

Macros
#define	GEN_PASS_DEF_ARRAYTOSCALARPASS
#define	GEN_PASS_DEF_STRAIGHTLINESTATICARRAYPROMOTIONPASS
#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 ()
std::unique_ptr<::mlir::Pass >	llzk::array::impl::createStraightLineStaticArrayPromotionPass ()
std::unique_ptr<::mlir::Pass >	llzk::array::createStraightLineStaticArrayPromotionPass ()

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. Fold read-only, constant-index accesses to constant global arrays without expanding them.
6. Promote straight-line static arrays in one walk per block.
7. Run restricted "sroa" pass to split each remaining array with linear size N into N size-1 arrays (to prepare for "mem2reg" pass because its API cannot deal with splitting up memory).
8. Run restricted "mem2reg" as a fallback for allocations with control flow or unsupported uses.
9. Remove array allocations that become unread after memory promotion, then canonicalize local 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 123 of file ArrayToScalarPass.cpp.

GEN_PASS_DEF_ARRAYTOSCALARPASS

#define GEN_PASS_DEF_ARRAYTOSCALARPASS

Definition at line 111 of file ArrayToScalarPass.cpp.

GEN_PASS_DEF_STRAIGHTLINESTATICARRAYPROMOTIONPASS

#define GEN_PASS_DEF_STRAIGHTLINESTATICARRAYPROMOTIONPASS

Definition at line 112 of file ArrayToScalarPass.cpp.