1//===- SparseVectorization.cpp - Vectorization of sparsified loops --------===//
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// A pass that converts loops generated by the sparsifier into a form that
10// can exploit SIMD instructions of the target architecture. Note that this pass
11// ensures the sparsifier can generate efficient SIMD (including ArmSVE
12// support) with proper separation of concerns as far as sparsification and
13// vectorization is concerned. However, this pass is not the final abstraction
14// level we want, and not the general vectorizer we want either. It forms a good
15// stepping stone for incremental future improvements though.
16//
17//===----------------------------------------------------------------------===//
18
19#include "Utils/CodegenUtils.h"
20#include "Utils/LoopEmitter.h"
21
22#include "mlir/Dialect/Affine/IR/AffineOps.h"
23#include "mlir/Dialect/Arith/IR/Arith.h"
24#include "mlir/Dialect/Math/IR/Math.h"
25#include "mlir/Dialect/MemRef/IR/MemRef.h"
26#include "mlir/Dialect/SCF/IR/SCF.h"
27#include "mlir/Dialect/SparseTensor/Transforms/Passes.h"
28#include "mlir/Dialect/Vector/IR/VectorOps.h"
29#include "mlir/Dialect/Vector/Transforms/LoweringPatterns.h"
30#include "mlir/IR/Matchers.h"
31
32using namespace mlir;
33using namespace mlir::sparse_tensor;
34
35namespace {
36
37/// Target SIMD properties:
38/// vectorLength: # packed data elements (viz. vector<16xf32> has length 16)
39/// enableVLAVectorization: enables scalable vectors (viz. ARMSve)
40/// enableSIMDIndex32: uses 32-bit indices in gather/scatter for efficiency
41struct VL {
42 unsigned vectorLength;
43 bool enableVLAVectorization;
44 bool enableSIMDIndex32;
45};
46
47/// Helper test for invariant value (defined outside given block).
48static bool isInvariantValue(Value val, Block *block) {
49 return val.getDefiningOp() && val.getDefiningOp()->getBlock() != block;
50}
51
52/// Helper test for invariant argument (defined outside given block).
53static bool isInvariantArg(BlockArgument arg, Block *block) {
54 return arg.getOwner() != block;
55}
56
57/// Returns true when `mem`'s most minor dimension has a statically known
58/// non-unit stride.
59///
60/// `genVectorLoad/genVectorStore` assume a contiguous
61/// `vector.maskedload/vector.maskedstore` is safe for consecutive loop
62/// indices, which breaks for a strided view extracting one component out
63/// of an interleaved (AoS) COO coordinate buffer.
64///
65/// Example:
66/// A `compressed(nonunique) + singleton` region stores coordinates as
67/// `[row0, col0, row1, col1, ...]`, so a 2-lane masked load of `col[0:2]`
68/// (offset=1) would read physical offsets {1, 2} = `[col0, row1]` instead
69/// of the intended {1, 3} = `[col0, col1]`: a silent miscompile.
70///
71/// NOTE: A stride that can't be proven non-unit by either means is assumed
72/// safe.
73static bool hasKnownNonUnitStride(Value mem) {
74 // sparse_tensor.coordinates isn't lowered to a concrete strided memref
75 // until sparse-tensor-codegen runs, so at this point its type
76 // still has a dynamic stride even when the true stride is already known
77 // from the tensor's encoding -- hence the special case below instead of
78 // trusting the memref type.
79 if (auto toCoords = mem.getDefiningOp<ToCoordinatesOp>()) {
80 SparseTensorType stt = getSparseTensorType(val: toCoords.getTensor());
81 Level cooStart = stt.getAoSCOOStart();
82 // A single trailing level (lvlRank - cooStart == 1) is not actually
83 // interleaved with anything else, so it degenerates to a contiguous
84 // buffer.
85 if (toCoords.getLevel() >= cooStart)
86 return stt.getLvlRank() - cooStart != 1;
87 return false;
88 }
89
90 auto memTp = dyn_cast<MemRefType>(Val: mem.getType());
91 if (!memTp)
92 return false;
93 SmallVector<int64_t> strides;
94 int64_t offset;
95 if (failed(Result: memTp.getStridesAndOffset(strides, offset)))
96 return false;
97 return !strides.empty() && !ShapedType::isDynamic(dValue: strides.back()) &&
98 strides.back() != 1;
99}
100
101/// Constructs vector type for element type.
102static VectorType vectorType(VL vl, Type etp) {
103 return VectorType::get(shape: vl.vectorLength, elementType: etp, scalableDims: vl.enableVLAVectorization);
104}
105
106/// Constructs vector type from a memref value.
107static VectorType vectorType(VL vl, Value mem) {
108 return vectorType(vl, etp: getMemRefType(t&: mem).getElementType());
109}
110
111/// Constructs vector iteration mask.
112static Value genVectorMask(PatternRewriter &rewriter, Location loc, VL vl,
113 Value iv, Value lo, Value hi, Value step) {
114 VectorType mtp = vectorType(vl, etp: rewriter.getI1Type());
115 // Special case if the vector length evenly divides the trip count (for
116 // example, "for i = 0, 128, 16"). A constant all-true mask is generated
117 // so that all subsequent masked memory operations are immediately folded
118 // into unconditional memory operations.
119 IntegerAttr loInt, hiInt, stepInt;
120 if (matchPattern(value: lo, pattern: m_Constant(bind_value: &loInt)) &&
121 matchPattern(value: hi, pattern: m_Constant(bind_value: &hiInt)) &&
122 matchPattern(value: step, pattern: m_Constant(bind_value: &stepInt))) {
123 if (((hiInt.getInt() - loInt.getInt()) % stepInt.getInt()) == 0) {
124 Value trueVal = constantI1(builder&: rewriter, loc, b: true);
125 return vector::BroadcastOp::create(builder&: rewriter, location: loc, result: mtp, source: trueVal);
126 }
127 }
128 // Otherwise, generate a vector mask that avoids overrunning the upperbound
129 // during vector execution. Here we rely on subsequent loop optimizations to
130 // avoid executing the mask in all iterations, for example, by splitting the
131 // loop into an unconditional vector loop and a scalar cleanup loop.
132 auto min = AffineMap::get(
133 /*dimCount=*/2, /*symbolCount=*/1,
134 results: {rewriter.getAffineSymbolExpr(position: 0),
135 rewriter.getAffineDimExpr(position: 0) - rewriter.getAffineDimExpr(position: 1)},
136 context: rewriter.getContext());
137 Value end = rewriter.createOrFold<affine::AffineMinOp>(
138 location: loc, args&: min, args: ValueRange{hi, iv, step});
139 return vector::CreateMaskOp::create(builder&: rewriter, location: loc, resultType0: mtp, mask_dim_sizes: end);
140}
141
142/// Generates a vectorized invariant. Here we rely on subsequent loop
143/// optimizations to hoist the invariant broadcast out of the vector loop.
144static Value genVectorInvariantValue(PatternRewriter &rewriter, VL vl,
145 Value val) {
146 VectorType vtp = vectorType(vl, etp: val.getType());
147 return vector::BroadcastOp::create(builder&: rewriter, location: val.getLoc(), result: vtp, source: val);
148}
149
150/// Generates a vectorized load lhs = a[ind[lo:hi]] or lhs = a[lo:hi],
151/// where 'lo' denotes the current index and 'hi = lo + vl - 1'. Note
152/// that the sparsifier can only generate indirect loads in
153/// the last index, i.e. back().
154static Value genVectorLoad(PatternRewriter &rewriter, Location loc, VL vl,
155 Value mem, ArrayRef<Value> idxs, Value vmask) {
156 VectorType vtp = vectorType(vl, mem);
157 Value pass = constantZero(builder&: rewriter, loc, tp: vtp);
158 if (llvm::isa<VectorType>(Val: idxs.back().getType())) {
159 SmallVector<Value> scalarArgs(idxs);
160 Value indexVec = idxs.back();
161 scalarArgs.back() = constantIndex(builder&: rewriter, loc, i: 0);
162 return vector::GatherOp::create(builder&: rewriter, location: loc, resultType: vtp, base: mem, indices: scalarArgs,
163 index_vec: indexVec, mask: vmask, passthrough: pass);
164 }
165 return vector::MaskedLoadOp::create(builder&: rewriter, location: loc, resultType: vtp, base: mem, indices: idxs, mask: vmask,
166 passthrough: pass);
167}
168
169/// Generates a vectorized store a[ind[lo:hi]] = rhs or a[lo:hi] = rhs
170/// where 'lo' denotes the current index and 'hi = lo + vl - 1'. Note
171/// that the sparsifier can only generate indirect stores in
172/// the last index, i.e. back().
173static void genVectorStore(PatternRewriter &rewriter, Location loc, Value mem,
174 ArrayRef<Value> idxs, Value vmask, Value rhs) {
175 if (llvm::isa<VectorType>(Val: idxs.back().getType())) {
176 SmallVector<Value> scalarArgs(idxs);
177 Value indexVec = idxs.back();
178 scalarArgs.back() = constantIndex(builder&: rewriter, loc, i: 0);
179 vector::ScatterOp::create(builder&: rewriter, location: loc, /*resultType=*/nullptr, base: mem,
180 indices: scalarArgs, index_vec: indexVec, mask: vmask, valueToStore: rhs);
181 return;
182 }
183 vector::MaskedStoreOp::create(builder&: rewriter, location: loc, base: mem, indices: idxs, mask: vmask, valueToStore: rhs);
184}
185
186/// Detects a vectorizable reduction operations and returns the
187/// combining kind of reduction on success in `kind`.
188static bool isVectorizableReduction(Value red, Value iter,
189 vector::CombiningKind &kind) {
190 if (auto addf = red.getDefiningOp<arith::AddFOp>()) {
191 kind = vector::CombiningKind::ADD;
192 return addf->getOperand(idx: 0) == iter || addf->getOperand(idx: 1) == iter;
193 }
194 if (auto addi = red.getDefiningOp<arith::AddIOp>()) {
195 kind = vector::CombiningKind::ADD;
196 return addi->getOperand(idx: 0) == iter || addi->getOperand(idx: 1) == iter;
197 }
198 if (auto subf = red.getDefiningOp<arith::SubFOp>()) {
199 kind = vector::CombiningKind::ADD;
200 return subf->getOperand(idx: 0) == iter;
201 }
202 if (auto subi = red.getDefiningOp<arith::SubIOp>()) {
203 kind = vector::CombiningKind::ADD;
204 return subi->getOperand(idx: 0) == iter;
205 }
206 if (auto mulf = red.getDefiningOp<arith::MulFOp>()) {
207 kind = vector::CombiningKind::MUL;
208 return mulf->getOperand(idx: 0) == iter || mulf->getOperand(idx: 1) == iter;
209 }
210 if (auto muli = red.getDefiningOp<arith::MulIOp>()) {
211 kind = vector::CombiningKind::MUL;
212 return muli->getOperand(idx: 0) == iter || muli->getOperand(idx: 1) == iter;
213 }
214 if (auto andi = red.getDefiningOp<arith::AndIOp>()) {
215 kind = vector::CombiningKind::AND;
216 return andi->getOperand(idx: 0) == iter || andi->getOperand(idx: 1) == iter;
217 }
218 if (auto ori = red.getDefiningOp<arith::OrIOp>()) {
219 kind = vector::CombiningKind::OR;
220 return ori->getOperand(idx: 0) == iter || ori->getOperand(idx: 1) == iter;
221 }
222 if (auto xori = red.getDefiningOp<arith::XOrIOp>()) {
223 kind = vector::CombiningKind::XOR;
224 return xori->getOperand(idx: 0) == iter || xori->getOperand(idx: 1) == iter;
225 }
226 return false;
227}
228
229/// Generates an initial value for a vector reduction, following the scheme
230/// given in Chapter 5 of "The Software Vectorization Handbook", where the
231/// initial scalar value is correctly embedded in the vector reduction value,
232/// and a straightforward horizontal reduction will complete the operation.
233/// Value 'r' denotes the initial value of the reduction outside the loop.
234static Value genVectorReducInit(PatternRewriter &rewriter, Location loc,
235 Value red, Value iter, Value r,
236 VectorType vtp) {
237 vector::CombiningKind kind;
238 if (!isVectorizableReduction(red, iter, kind))
239 llvm_unreachable("unknown reduction");
240 switch (kind) {
241 case vector::CombiningKind::ADD:
242 case vector::CombiningKind::XOR:
243 // Initialize reduction vector to: | 0 | .. | 0 | r |
244 return vector::InsertOp::create(builder&: rewriter, location: loc, valueToStore: r,
245 dest: constantZero(builder&: rewriter, loc, tp: vtp),
246 position: constantIndex(builder&: rewriter, loc, i: 0));
247 case vector::CombiningKind::MUL:
248 // Initialize reduction vector to: | 1 | .. | 1 | r |
249 return vector::InsertOp::create(builder&: rewriter, location: loc, valueToStore: r,
250 dest: constantOne(builder&: rewriter, loc, tp: vtp),
251 position: constantIndex(builder&: rewriter, loc, i: 0));
252 case vector::CombiningKind::AND:
253 case vector::CombiningKind::OR:
254 // Initialize reduction vector to: | r | .. | r | r |
255 return vector::BroadcastOp::create(builder&: rewriter, location: loc, result: vtp, source: r);
256 default:
257 break;
258 }
259 llvm_unreachable("unknown reduction kind");
260}
261
262/// This method is called twice to analyze and rewrite the given subscripts.
263/// The first call (!codegen) does the analysis. Then, on success, the second
264/// call (codegen) yields the proper vector form in the output parameter
265/// vector 'idxs'. This mechanism ensures that analysis and rewriting code
266/// stay in sync. Note that the analyis part is simple because the sparsifier
267/// only generates relatively simple subscript expressions.
268///
269/// See https://llvm.org/docs/GetElementPtr.html for some background on
270/// the complications described below.
271///
272/// We need to generate a position/coordinate load from the sparse storage
273/// scheme. Narrower data types need to be zero extended before casting
274/// the value into the `index` type used for looping and indexing.
275///
276/// For the scalar case, subscripts simply zero extend narrower indices
277/// into 64-bit values before casting to an index type without a performance
278/// penalty. Indices that already are 64-bit, in theory, cannot express the
279/// full range since the LLVM backend defines addressing in terms of an
280/// unsigned pointer/signed index pair.
281static bool vectorizeSubscripts(PatternRewriter &rewriter, scf::ForOp forOp,
282 VL vl, ValueRange subs, bool codegen,
283 Value vmask, SmallVectorImpl<Value> &idxs) {
284 unsigned d = 0;
285 unsigned dim = subs.size();
286 Block *block = &forOp.getRegion().front();
287 for (auto sub : subs) {
288 bool innermost = ++d == dim;
289 // Invariant subscripts in outer dimensions simply pass through.
290 // Note that we rely on LICM to hoist loads where all subscripts
291 // are invariant in the innermost loop.
292 // Example:
293 // a[inv][i] for inv
294 if (isInvariantValue(val: sub, block)) {
295 if (innermost)
296 return false;
297 if (codegen)
298 idxs.push_back(Elt: sub);
299 continue; // success so far
300 }
301 // Invariant block arguments (including outer loop indices) in outer
302 // dimensions simply pass through. Direct loop indices in the
303 // innermost loop simply pass through as well.
304 // Example:
305 // a[i][j] for both i and j
306 if (auto arg = llvm::dyn_cast<BlockArgument>(Val&: sub)) {
307 if (isInvariantArg(arg, block) == innermost)
308 return false;
309 if (codegen)
310 idxs.push_back(Elt: sub);
311 continue; // success so far
312 }
313 // Look under the hood of casting.
314 auto cast = sub;
315 while (true) {
316 if (auto icast = cast.getDefiningOp<arith::IndexCastOp>())
317 cast = icast->getOperand(idx: 0);
318 else if (auto ecast = cast.getDefiningOp<arith::ExtUIOp>())
319 cast = ecast->getOperand(idx: 0);
320 else
321 break;
322 }
323 // Since the index vector is used in a subsequent gather/scatter
324 // operations, which effectively defines an unsigned pointer + signed
325 // index, we must zero extend the vector to an index width. For 8-bit
326 // and 16-bit values, an 32-bit index width suffices. For 32-bit values,
327 // zero extending the elements into 64-bit loses some performance since
328 // the 32-bit indexed gather/scatter is more efficient than the 64-bit
329 // index variant (if the negative 32-bit index space is unused, the
330 // enableSIMDIndex32 flag can preserve this performance). For 64-bit
331 // values, there is no good way to state that the indices are unsigned,
332 // which creates the potential of incorrect address calculations in the
333 // unlikely case we need such extremely large offsets.
334 // Example:
335 // a[ ind[i] ]
336 if (auto load = cast.getDefiningOp<memref::LoadOp>()) {
337 if (!innermost)
338 return false;
339 if (hasKnownNonUnitStride(mem: load.getMemRef()))
340 return false;
341 if (codegen) {
342 SmallVector<Value> idxs2(load.getIndices()); // no need to analyze
343 Location loc = forOp.getLoc();
344 Value vload =
345 genVectorLoad(rewriter, loc, vl, mem: load.getMemRef(), idxs: idxs2, vmask);
346 Type etp = llvm::cast<VectorType>(Val: vload.getType()).getElementType();
347 if (!llvm::isa<IndexType>(Val: etp)) {
348 if (etp.getIntOrFloatBitWidth() < 32)
349 vload = arith::ExtUIOp::create(
350 builder&: rewriter, location: loc, out: vectorType(vl, etp: rewriter.getI32Type()), in: vload);
351 else if (etp.getIntOrFloatBitWidth() < 64 && !vl.enableSIMDIndex32)
352 vload = arith::ExtUIOp::create(
353 builder&: rewriter, location: loc, out: vectorType(vl, etp: rewriter.getI64Type()), in: vload);
354 }
355 idxs.push_back(Elt: vload);
356 }
357 continue; // success so far
358 }
359 // Address calculation 'i = add inv, idx' (after LICM).
360 // Example:
361 // a[base + i]
362 if (auto load = cast.getDefiningOp<arith::AddIOp>()) {
363 Value inv = load.getOperand(i: 0);
364 Value idx = load.getOperand(i: 1);
365 // Swap non-invariant.
366 if (!isInvariantValue(val: inv, block)) {
367 inv = idx;
368 idx = load.getOperand(i: 0);
369 }
370 // Inspect.
371 if (isInvariantValue(val: inv, block)) {
372 if (auto arg = llvm::dyn_cast<BlockArgument>(Val&: idx)) {
373 if (isInvariantArg(arg, block) || !innermost)
374 return false;
375 if (codegen)
376 idxs.push_back(
377 Elt: arith::AddIOp::create(builder&: rewriter, location: forOp.getLoc(), lhs: inv, rhs: idx));
378 continue; // success so far
379 }
380 }
381 }
382 return false;
383 }
384 return true;
385}
386
387#define UNAOP(xxx) \
388 if (auto x = dyn_cast<xxx>(def)) { \
389 if (codegen) { \
390 vexp = xxx::create(rewriter, loc, ValueRange{vx}, x.getProperties(), \
391 x->getDiscardableAttrDictionary().getValue()); \
392 } \
393 return true; \
394 }
395
396#define TYPEDUNAOP(xxx) \
397 if (auto x = dyn_cast<xxx>(def)) { \
398 if (codegen) { \
399 VectorType vtp = vectorType(vl, x.getType()); \
400 vexp = xxx::create(rewriter, loc, TypeRange{vtp}, ValueRange{vx}, \
401 x.getProperties(), \
402 x->getDiscardableAttrDictionary().getValue()); \
403 } \
404 return true; \
405 }
406
407#define BINOP(xxx) \
408 if (auto x = dyn_cast<xxx>(def)) { \
409 if (codegen) { \
410 vexp = xxx::create(rewriter, loc, ValueRange{vx, vy}, x.getProperties(), \
411 x->getDiscardableAttrDictionary().getValue()); \
412 } \
413 return true; \
414 }
415
416/// This method is called twice to analyze and rewrite the given expression.
417/// The first call (!codegen) does the analysis. Then, on success, the second
418/// call (codegen) yields the proper vector form in the output parameter 'vexp'.
419/// This mechanism ensures that analysis and rewriting code stay in sync. Note
420/// that the analyis part is simple because the sparsifier only generates
421/// relatively simple expressions inside the for-loops.
422static bool vectorizeExpr(PatternRewriter &rewriter, scf::ForOp forOp, VL vl,
423 Value exp, bool codegen, Value vmask, Value &vexp) {
424 Location loc = forOp.getLoc();
425 // Reject unsupported types.
426 if (!VectorType::isValidElementType(t: exp.getType()))
427 return false;
428 // A block argument is invariant/reduction/index.
429 if (auto arg = llvm::dyn_cast<BlockArgument>(Val&: exp)) {
430 if (arg == forOp.getInductionVar()) {
431 // We encountered a single, innermost index inside the computation,
432 // such as a[i] = i, which must convert to [i, i+1, ...].
433 if (codegen) {
434 VectorType vtp = vectorType(vl, etp: arg.getType());
435 Value veci = vector::BroadcastOp::create(builder&: rewriter, location: loc, result: vtp, source: arg);
436 Value incr = vector::StepOp::create(builder&: rewriter, location: loc, result: vtp);
437 vexp = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: veci, rhs: incr);
438 }
439 return true;
440 }
441 // An invariant or reduction. In both cases, we treat this as an
442 // invariant value, and rely on later replacing and folding to
443 // construct a proper reduction chain for the latter case.
444 if (codegen)
445 vexp = genVectorInvariantValue(rewriter, vl, val: exp);
446 return true;
447 }
448 // Something defined outside the loop-body is invariant.
449 Operation *def = exp.getDefiningOp();
450 Block *block = &forOp.getRegion().front();
451 if (def->getBlock() != block) {
452 if (codegen)
453 vexp = genVectorInvariantValue(rewriter, vl, val: exp);
454 return true;
455 }
456 // Proper load operations. These are either values involved in the
457 // actual computation, such as a[i] = b[i] becomes a[lo:hi] = b[lo:hi],
458 // or coordinate values inside the computation that are now fetched from
459 // the sparse storage coordinates arrays, such as a[i] = i becomes
460 // a[lo:hi] = ind[lo:hi], where 'lo' denotes the current index
461 // and 'hi = lo + vl - 1'.
462 if (auto load = dyn_cast<memref::LoadOp>(Val: def)) {
463 if (hasKnownNonUnitStride(mem: load.getMemRef()))
464 return false;
465 auto subs = load.getIndices();
466 SmallVector<Value> idxs;
467 if (vectorizeSubscripts(rewriter, forOp, vl, subs, codegen, vmask, idxs)) {
468 if (codegen)
469 vexp = genVectorLoad(rewriter, loc, vl, mem: load.getMemRef(), idxs, vmask);
470 return true;
471 }
472 return false;
473 }
474 // Inside loop-body unary and binary operations. Note that it would be
475 // nicer if we could somehow test and build the operations in a more
476 // concise manner than just listing them all (although this way we know
477 // for certain that they can vectorize).
478 //
479 // TODO: avoid visiting CSEs multiple times
480 //
481 if (def->getNumOperands() == 1) {
482 Value vx;
483 if (vectorizeExpr(rewriter, forOp, vl, exp: def->getOperand(idx: 0), codegen, vmask,
484 vexp&: vx)) {
485 UNAOP(math::AbsFOp)
486 UNAOP(math::AbsIOp)
487 UNAOP(math::CeilOp)
488 UNAOP(math::FloorOp)
489 UNAOP(math::SqrtOp)
490 UNAOP(math::ExpM1Op)
491 UNAOP(math::Log1pOp)
492 UNAOP(math::SinOp)
493 UNAOP(math::TanhOp)
494 UNAOP(arith::NegFOp)
495 TYPEDUNAOP(arith::TruncFOp)
496 TYPEDUNAOP(arith::ExtFOp)
497 TYPEDUNAOP(arith::FPToSIOp)
498 TYPEDUNAOP(arith::FPToUIOp)
499 TYPEDUNAOP(arith::SIToFPOp)
500 TYPEDUNAOP(arith::UIToFPOp)
501 TYPEDUNAOP(arith::ExtSIOp)
502 TYPEDUNAOP(arith::ExtUIOp)
503 TYPEDUNAOP(arith::IndexCastOp)
504 TYPEDUNAOP(arith::TruncIOp)
505 TYPEDUNAOP(arith::BitcastOp)
506 // TODO: complex?
507 }
508 } else if (def->getNumOperands() == 2) {
509 Value vx, vy;
510 if (vectorizeExpr(rewriter, forOp, vl, exp: def->getOperand(idx: 0), codegen, vmask,
511 vexp&: vx) &&
512 vectorizeExpr(rewriter, forOp, vl, exp: def->getOperand(idx: 1), codegen, vmask,
513 vexp&: vy)) {
514 // We only accept shift-by-invariant (where the same shift factor applies
515 // to all packed elements). In the vector dialect, this is still
516 // represented with an expanded vector at the right-hand-side, however,
517 // so that we do not have to special case the code generation.
518 if (isa<arith::ShLIOp>(Val: def) || isa<arith::ShRUIOp>(Val: def) ||
519 isa<arith::ShRSIOp>(Val: def)) {
520 Value shiftFactor = def->getOperand(idx: 1);
521 if (!isInvariantValue(val: shiftFactor, block))
522 return false;
523 }
524 // Generate code.
525 BINOP(arith::MulFOp)
526 BINOP(arith::MulIOp)
527 BINOP(arith::DivFOp)
528 BINOP(arith::DivSIOp)
529 BINOP(arith::DivUIOp)
530 BINOP(arith::AddFOp)
531 BINOP(arith::AddIOp)
532 BINOP(arith::SubFOp)
533 BINOP(arith::SubIOp)
534 BINOP(arith::AndIOp)
535 BINOP(arith::OrIOp)
536 BINOP(arith::XOrIOp)
537 BINOP(arith::ShLIOp)
538 BINOP(arith::ShRUIOp)
539 BINOP(arith::ShRSIOp)
540 // TODO: complex?
541 }
542 }
543 return false;
544}
545
546#undef UNAOP
547#undef TYPEDUNAOP
548#undef BINOP
549
550/// This method is called twice to analyze and rewrite the given for-loop.
551/// The first call (!codegen) does the analysis. Then, on success, the second
552/// call (codegen) rewriters the IR into vector form. This mechanism ensures
553/// that analysis and rewriting code stay in sync.
554static bool vectorizeStmt(PatternRewriter &rewriter, scf::ForOp forOp, VL vl,
555 bool codegen) {
556 Block &block = forOp.getRegion().front();
557 // For loops with single yield statement (as below) could be generated
558 // when custom reduce is used with unary operation.
559 // for (...)
560 // yield c_0
561 if (block.getOperations().size() <= 1)
562 return false;
563
564 Location loc = forOp.getLoc();
565 scf::YieldOp yield = cast<scf::YieldOp>(Val: block.getTerminator());
566 auto &last = *++block.rbegin();
567 scf::ForOp forOpNew;
568
569 // Perform initial set up during codegen (we know that the first analysis
570 // pass was successful). For reductions, we need to construct a completely
571 // new for-loop, since the incoming and outgoing reduction type
572 // changes into SIMD form. For stores, we can simply adjust the stride
573 // and insert in the existing for-loop. In both cases, we set up a vector
574 // mask for all operations which takes care of confining vectors to
575 // the original iteration space (later cleanup loops or other
576 // optimizations can take care of those).
577 Value vmask;
578 if (codegen) {
579 Value step = constantIndex(builder&: rewriter, loc, i: vl.vectorLength);
580 if (vl.enableVLAVectorization) {
581 Value vscale =
582 vector::VectorScaleOp::create(builder&: rewriter, location: loc, result: rewriter.getIndexType());
583 step = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: vscale, rhs: step);
584 }
585 if (!yield.getResults().empty()) {
586 Value init = forOp.getInitArgs()[0];
587 VectorType vtp = vectorType(vl, etp: init.getType());
588 Value vinit = genVectorReducInit(rewriter, loc, red: yield->getOperand(idx: 0),
589 iter: forOp.getRegionIterArg(index: 0), r: init, vtp);
590 forOpNew =
591 scf::ForOp::create(builder&: rewriter, location: loc, lowerBound: forOp.getLowerBound(),
592 upperBound: forOp.getUpperBound(), step, initArgs: vinit,
593 /*bodyBuilder=*/odsArg4: nullptr, unsignedCmp: forOp.getUnsignedCmp());
594 forOpNew->setDiscardableAttr(
595 name: LoopEmitter::getLoopEmitterLoopAttrName(),
596 value: forOp->getDiscardableAttr(name: LoopEmitter::getLoopEmitterLoopAttrName()));
597 rewriter.setInsertionPointToStart(forOpNew.getBody());
598 } else {
599 rewriter.modifyOpInPlace(root: forOp, callable: [&]() { forOp.setStep(step); });
600 rewriter.setInsertionPoint(yield);
601 }
602 vmask = genVectorMask(rewriter, loc, vl, iv: forOp.getInductionVar(),
603 lo: forOp.getLowerBound(), hi: forOp.getUpperBound(), step);
604 }
605
606 // Sparse for-loops either are terminated by a non-empty yield operation
607 // (reduction loop) or otherwise by a store operation (pararallel loop).
608 if (!yield.getResults().empty()) {
609 // Analyze/vectorize reduction.
610 if (yield->getNumOperands() != 1)
611 return false;
612 Value red = yield->getOperand(idx: 0);
613 Value iter = forOp.getRegionIterArg(index: 0);
614 vector::CombiningKind kind;
615 Value vrhs;
616 if (isVectorizableReduction(red, iter, kind) &&
617 vectorizeExpr(rewriter, forOp, vl, exp: red, codegen, vmask, vexp&: vrhs)) {
618 if (codegen) {
619 Value partial = forOpNew.getResult(i: 0);
620 Value vpass = genVectorInvariantValue(rewriter, vl, val: iter);
621 Value vred = arith::SelectOp::create(builder&: rewriter, location: loc, condition: vmask, true_value: vrhs, false_value: vpass);
622 scf::YieldOp::create(builder&: rewriter, location: loc, results: vred);
623 rewriter.setInsertionPointAfter(forOpNew);
624 Value vres = vector::ReductionOp::create(builder&: rewriter, location: loc, kind, vector: partial);
625 // Now do some relinking (last one is not completely type safe
626 // but all bad ones are removed right away). This also folds away
627 // nop broadcast operations.
628 rewriter.replaceAllUsesWith(from: forOp.getResult(i: 0), to: vres);
629 rewriter.replaceAllUsesWith(from: forOp.getInductionVar(),
630 to: forOpNew.getInductionVar());
631 rewriter.replaceAllUsesWith(from: forOp.getRegionIterArg(index: 0),
632 to: forOpNew.getRegionIterArg(index: 0));
633 rewriter.eraseOp(op: forOp);
634 }
635 return true;
636 }
637 } else if (auto store = dyn_cast<memref::StoreOp>(Val&: last)) {
638 // Analyze/vectorize store operation.
639 if (hasKnownNonUnitStride(mem: store.getMemRef()))
640 return false;
641 auto subs = store.getIndices();
642 SmallVector<Value> idxs;
643 Value rhs = store.getValue();
644 Value vrhs;
645 if (vectorizeSubscripts(rewriter, forOp, vl, subs, codegen, vmask, idxs) &&
646 vectorizeExpr(rewriter, forOp, vl, exp: rhs, codegen, vmask, vexp&: vrhs)) {
647 if (codegen) {
648 genVectorStore(rewriter, loc, mem: store.getMemRef(), idxs, vmask, rhs: vrhs);
649 rewriter.eraseOp(op: store);
650 }
651 return true;
652 }
653 }
654
655 assert(!codegen && "cannot call codegen when analysis failed");
656 return false;
657}
658
659/// Basic for-loop vectorizer.
660struct ForOpRewriter : public OpRewritePattern<scf::ForOp> {
661public:
662 using OpRewritePattern<scf::ForOp>::OpRewritePattern;
663
664 ForOpRewriter(MLIRContext *context, unsigned vectorLength,
665 bool enableVLAVectorization, bool enableSIMDIndex32)
666 : OpRewritePattern(context),
667 vl{.vectorLength: vectorLength, .enableVLAVectorization: enableVLAVectorization, .enableSIMDIndex32: enableSIMDIndex32} {}
668
669 LogicalResult matchAndRewrite(scf::ForOp op,
670 PatternRewriter &rewriter) const override {
671 // Check for single block, unit-stride for-loop that is generated by
672 // sparsifier, which means no data dependence analysis is required,
673 // and its loop-body is very restricted in form.
674 if (!op.getRegion().hasOneBlock() || !isOneInteger(v: op.getStep()) ||
675 !op->hasDiscardableAttr(name: LoopEmitter::getLoopEmitterLoopAttrName()))
676 return failure();
677 // Analyze (!codegen) and rewrite (codegen) loop-body.
678 if (vectorizeStmt(rewriter, forOp: op, vl, /*codegen=*/false) &&
679 vectorizeStmt(rewriter, forOp: op, vl, /*codegen=*/true))
680 return success();
681 return failure();
682 }
683
684private:
685 const VL vl;
686};
687
688static LogicalResult cleanReducChain(PatternRewriter &rewriter, Operation *op,
689 Value inp) {
690 if (auto redOp = inp.getDefiningOp<vector::ReductionOp>()) {
691 if (auto forOp = redOp.getVector().getDefiningOp<scf::ForOp>()) {
692 if (forOp->hasDiscardableAttr(
693 name: LoopEmitter::getLoopEmitterLoopAttrName())) {
694 rewriter.replaceOp(op, newValues: redOp.getVector());
695 return success();
696 }
697 }
698 }
699 return failure();
700}
701
702/// Reduction chain cleanup.
703/// v = for { }
704/// s = vsum(v) v = for { }
705/// u = broadcast(s) -> for (v) { }
706/// for (u) { }
707struct ReducChainBroadcastRewriter
708 : public OpRewritePattern<vector::BroadcastOp> {
709public:
710 using OpRewritePattern<vector::BroadcastOp>::OpRewritePattern;
711
712 LogicalResult matchAndRewrite(vector::BroadcastOp op,
713 PatternRewriter &rewriter) const override {
714 return cleanReducChain(rewriter, op, inp: op.getSource());
715 }
716};
717
718/// Reduction chain cleanup.
719/// v = for { }
720/// s = vsum(v) v = for { }
721/// u = insert(s) -> for (v) { }
722/// for (u) { }
723struct ReducChainInsertRewriter : public OpRewritePattern<vector::InsertOp> {
724public:
725 using OpRewritePattern<vector::InsertOp>::OpRewritePattern;
726
727 LogicalResult matchAndRewrite(vector::InsertOp op,
728 PatternRewriter &rewriter) const override {
729 return cleanReducChain(rewriter, op, inp: op.getValueToStore());
730 }
731};
732} // namespace
733
734//===----------------------------------------------------------------------===//
735// Public method for populating vectorization rules.
736//===----------------------------------------------------------------------===//
737
738/// Populates the given patterns list with vectorization rules.
739void mlir::populateSparseVectorizationPatterns(RewritePatternSet &patterns,
740 unsigned vectorLength,
741 bool enableVLAVectorization,
742 bool enableSIMDIndex32) {
743 assert(vectorLength > 0);
744 vector::populateVectorStepLoweringPatterns(patterns);
745 patterns.add<ForOpRewriter>(arg: patterns.getContext(), args&: vectorLength,
746 args&: enableVLAVectorization, args&: enableSIMDIndex32);
747 patterns.add<ReducChainInsertRewriter, ReducChainBroadcastRewriter>(
748 arg: patterns.getContext());
749}
750