LLVM 24.0.0git
LowerMatrixIntrinsics.cpp
Go to the documentation of this file.
1//===- LowerMatrixIntrinsics.cpp - Lower matrix intrinsics -----*- C++ -*-===//
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// Lower matrix intrinsics to vector operations.
10//
11// TODO:
12// * Improve fusion:
13// * Support more cases, e.g. multiply-add, multiply-sub, operands/results
14// transposed.
15// * Improve cost-modeling, e.g. choose different number of rows/columns
16// columns for tiles, consider cost of copies on alias.
17//
18//===----------------------------------------------------------------------===//
19
21#include "ScalarOptions.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/ScopeExit.h"
26#include "llvm/ADT/Statistic.h"
34#include "llvm/IR/CFG.h"
35#include "llvm/IR/DataLayout.h"
38#include "llvm/IR/Function.h"
39#include "llvm/IR/IRBuilder.h"
40#include "llvm/IR/InstrTypes.h"
49#include "llvm/Support/Debug.h"
53
54#include <cmath>
55
56using namespace llvm;
57using namespace PatternMatch;
58
59#define DEBUG_TYPE "lower-matrix-intrinsics"
60
61STATISTIC(FlattenedMatrices, "Number of matrix flattenings");
62STATISTIC(ReshapedMatrices, "Number of matrix reshapes");
63STATISTIC(SplitMatrices, "Number of matrix splits");
64
65/// Helper function to either return Scope, if it is a subprogram or the
66/// attached subprogram for a local scope.
68 if (auto *Subprogram = dyn_cast<DISubprogram>(Scope))
69 return Subprogram;
70 return cast<DILocalScope>(Scope)->getSubprogram();
71}
72
73/// Return true if V is a splat of a value (which is used when multiplying a
74/// matrix with a scalar).
75static bool isSplat(Value *V) {
76 if (auto *SV = dyn_cast<ShuffleVectorInst>(V))
77 return SV->isZeroEltSplat();
78 return false;
79}
80
81/// Match any mul operation (fp or integer).
82template <typename LTy, typename RTy>
83static auto m_AnyMul(const LTy &L, const RTy &R) {
84 return m_CombineOr(m_Mul(L, R), m_FMul(L, R));
85}
86
87/// Match any add operation (fp or integer).
88template <typename LTy, typename RTy>
89static auto m_AnyAdd(const LTy &L, const RTy &R) {
90 return m_CombineOr(m_Add(L, R), m_FAdd(L, R));
91}
92
93// Given an element pointer \p BasePtr to the start of a (sub) matrix, compute
94// the start address of vector \p VecIdx with type (\p EltType x \p NumElements)
95// assuming \p Stride elements between start two consecutive vectors.
96// \p Stride must be >= \p NumElements.
97// For column-major matrixes, the function computes the address of a column
98// vectors and \p NumElements must be set to the number of elements in a column
99// (= number of rows of the matrix). For row-major matrixes, the function
100// computes the address of a row vector and \p NumElements must be set to the
101// number of elements in a column (= number of columns of the matrix).
102//
103// Consider a 4x4 matrix in column-mjaor layout like below
104//
105// 0 1 2 3
106// 0 v_0_0 v_0_1 v_0_2 v_0_3
107// 1 v_1_0 v_1_1 v_1_2 v_1_3
108// 2 v_2_0 v_2_1 v_2_2 v_2_3
109// 3 v_3_0 v_3_1 v_3_2 v_3_3
110
111// To compute the column addresses for a 2x3 sub-matrix at row 1 and column 1,
112// we need a pointer to the first element of the submatrix as base pointer.
113// Then we can use computeVectorAddr to compute the addresses for the columns
114// of the sub-matrix.
115//
116// Column 0: computeVectorAddr(Base, 0 (column), 4 (stride), 2 (num rows), ..)
117// -> just returns Base
118// Column 1: computeVectorAddr(Base, 1 (column), 4 (stride), 2 (num rows), ..)
119// -> returns Base + (1 * 4)
120// Column 2: computeVectorAddr(Base, 2 (column), 4 (stride), 2 (num rows), ..)
121// -> returns Base + (2 * 4)
122//
123// The graphic below illustrates the number of elements in a column (marked
124// with |) and the number of skipped elements (marked with }).
125//
126// v_0_0 v_0_1 {v_0_2 {v_0_3
127// Base Col 1 Col 2
128// | | |
129// v_1_0 |v_1_1 |v_1_2 |v_1_3
130// v_2_0 |v_2_1 |v_2_2 |v_2_3
131// v_3_0 {v_3_1 {v_3_2 v_3_3
132//
133static Value *computeVectorAddr(Value *BasePtr, Value *VecIdx, Value *Stride,
134 unsigned NumElements, Type *EltType,
135 IRBuilder<> &Builder) {
136
137 assert((!isa<ConstantInt>(Stride) ||
138 cast<ConstantInt>(Stride)->getZExtValue() >= NumElements) &&
139 "Stride must be >= the number of elements in the result vector.");
140
141 // Compute the start of the vector with index VecIdx as VecIdx * Stride.
142 Value *VecStart = Builder.CreateMul(VecIdx, Stride, "vec.start");
143
144 // Get pointer to the start of the selected vector. Skip GEP creation,
145 // if we select vector 0.
146 if (isa<ConstantInt>(VecStart) && cast<ConstantInt>(VecStart)->isZero())
147 VecStart = BasePtr;
148 else
149 VecStart = Builder.CreateInBoundsGEP(EltType, BasePtr, VecStart, "vec.gep");
150
151 return VecStart;
152}
153
154namespace {
155struct ShapeInfo {
156 unsigned NumRows;
157 unsigned NumColumns;
158
159 ShapeInfo(unsigned NumRows = 0, unsigned NumColumns = 0)
160 : NumRows(NumRows), NumColumns(NumColumns) {}
161
162 ShapeInfo(Value *NumRows, Value *NumColumns)
163 : ShapeInfo(cast<ConstantInt>(NumRows)->getZExtValue(),
164 cast<ConstantInt>(NumColumns)->getZExtValue()) {}
165
166 bool operator==(const ShapeInfo &other) {
167 return NumRows == other.NumRows && NumColumns == other.NumColumns;
168 }
169 bool operator!=(const ShapeInfo &other) { return !(*this == other); }
170
171 /// Returns true if shape-information is defined, meaning both dimensions
172 /// are != 0.
173 operator bool() const {
174 assert(NumRows == 0 || NumColumns != 0);
175 return NumRows != 0;
176 }
177
178 /// Returns the transposed shape.
179 ShapeInfo t() const { return ShapeInfo(NumColumns, NumRows); }
180
181 friend raw_ostream &operator<<(raw_ostream &OS, ShapeInfo SI);
182
183 LLVM_DUMP_METHOD void dump() const { dbgs() << *this << '\n'; }
184};
185
186raw_ostream &operator<<(raw_ostream &OS, ShapeInfo SI) {
187 return OS << SI.NumRows << 'x' << SI.NumColumns;
188}
189
190} // namespace
191
192static bool isShapePreserving(Value *V) {
194 if (!I)
195 return true;
196
197 if (isa<SelectInst>(I))
198 return true;
199
200 if (I->isBinaryOp())
201 return true;
202
203 if (auto *Cast = dyn_cast<CastInst>(V)) {
204 switch (Cast->getOpcode()) {
205 case llvm::Instruction::Trunc:
206 case llvm::Instruction::ZExt:
207 case llvm::Instruction::SExt:
208 case llvm::Instruction::FPToUI:
209 case llvm::Instruction::FPToSI:
210 case llvm::Instruction::UIToFP:
211 case llvm::Instruction::SIToFP:
212 case llvm::Instruction::FPTrunc:
213 case llvm::Instruction::FPExt:
214 return true;
215 case llvm::Instruction::AddrSpaceCast:
216 case CastInst::PtrToAddr:
217 case CastInst::PtrToInt:
218 case CastInst::IntToPtr:
219 return false;
220 case CastInst::BitCast: {
221 if (auto *SrcVTy = dyn_cast<FixedVectorType>(Cast->getSrcTy()))
222 if (auto *DestVTy = dyn_cast<FixedVectorType>(Cast->getDestTy()))
223 return SrcVTy->getNumElements() == DestVTy->getNumElements();
224 return false;
225 }
226 case llvm::Instruction::CastOpsEnd:
227 llvm_unreachable("not an actual cast op");
228 }
229 llvm_unreachable("unhandled cast opcode");
230 }
231
232 if (auto *II = dyn_cast<IntrinsicInst>(V))
233 switch (II->getIntrinsicID()) {
234 case Intrinsic::abs:
235 case Intrinsic::fabs:
236 return true;
237 default:
238 return false;
239 }
240
241 switch (I->getOpcode()) {
242 case Instruction::PHI:
243 case Instruction::FNeg:
244 return true;
245 default:
246 return false;
247 }
248}
249
250/// Return an iterator over the operands of \p I that should share shape
251/// information with \p I.
254 "Can't retrieve shaped operands for an instruction that does not "
255 "preserve shape information");
256 auto Ops = I->operands();
257 return isa<SelectInst>(I) ? drop_begin(Ops) : Ops;
258}
259
260/// Return the ShapeInfo for the result of \p I, it it can be determined.
261static std::optional<ShapeInfo>
263 const DenseMap<Value *, ShapeInfo> &ShapeMap) {
264 Value *M;
265 Value *N;
266 Value *K;
268 m_Value(), m_Value(), m_Value(M), m_Value(N), m_Value(K))))
269 return ShapeInfo(M, K);
271 m_Value(N)))) {
272 // Flip dimensions.
273 return ShapeInfo(N, M);
274 }
276 m_Value(), m_Value(), m_Value(), m_Value(), m_Value(M),
277 m_Value(N))))
278 return ShapeInfo(N, M);
280 m_Value(), m_Value(), m_Value(), m_Value(M), m_Value(N))))
281 return ShapeInfo(M, N);
282 Value *MatrixA;
283 if (match(I, m_Store(m_Value(MatrixA), m_Value()))) {
284 auto OpShape = ShapeMap.find(MatrixA);
285 if (OpShape != ShapeMap.end())
286 return OpShape->second;
287 }
288
289 if (isShapePreserving(I)) {
290 auto ShapedOps = getShapedOperandsForInst(I);
291 // Find the first operand that has a known shape and use that.
292 for (auto &Op : ShapedOps) {
293 auto OpShape = ShapeMap.find(Op.get());
294 if (OpShape != ShapeMap.end())
295 return OpShape->second;
296 }
297 }
298 return std::nullopt;
299}
300
301namespace {
302
303/// LowerMatrixIntrinsics contains the methods used to lower matrix intrinsics.
304///
305/// Currently, the lowering for each matrix intrinsic is done as follows:
306/// 1. Propagate the shape information from intrinsics to connected
307/// instructions.
308/// 2. Lower instructions with shape information (assuming column-major layout).
309/// The lowering works similarly using row-major layout.
310/// 2.1. Get column vectors for each argument. If we already lowered the
311/// definition of an argument, use the produced column vectors directly.
312/// If not, split the operand vector containing an embedded matrix into
313/// a set of column vectors,
314/// 2.2. Lower the instruction in terms of column major operations, which
315/// yields a set of column vectors containing result matrix. Note that we
316/// lower all instructions that have shape information. Besides the
317/// intrinsics, this includes stores for example.
318/// 2.3. Update uses of the lowered instruction. If we have shape information
319/// for a user, there is nothing to do, as we will look up the result
320/// column matrix when lowering the user. For other uses, we embed the
321/// result matrix in a flat vector and update the use.
322/// 2.4. Cache the result column matrix for the instruction we lowered
323/// 3. After we lowered all instructions in a function, remove the now
324/// obsolete instructions.
325///
326class LowerMatrixIntrinsics {
327 const ScalarOptions &Opts;
328 Function &Func;
329 const DataLayout &DL;
330 const TargetTransformInfo &TTI;
332 AliasAnalysis *AA = nullptr;
333 DominatorTree *DT = nullptr;
334 LoopInfo *LI = nullptr;
335 OptimizationRemarkEmitter *ORE = nullptr;
336
337 /// Contains estimates of the number of operations (loads, stores, compute)
338 /// required to lower a matrix operation.
339 struct OpInfoTy {
340 /// Number of stores emitted to generate this matrix.
341 unsigned NumStores = 0;
342 /// Number of loads emitted to generate this matrix.
343 unsigned NumLoads = 0;
344 /// Number of compute operations emitted to generate this matrix.
345 unsigned NumComputeOps = 0;
346 /// Most of the time transposes can be fused with matrix multiplies or can
347 /// be folded away via algebraic simplifications. This is the number of
348 /// transposes that we failed to make "free" via such optimizations.
349 unsigned NumExposedTransposes = 0;
350
351 OpInfoTy &operator+=(const OpInfoTy &RHS) {
352 NumStores += RHS.NumStores;
353 NumLoads += RHS.NumLoads;
354 NumComputeOps += RHS.NumComputeOps;
355 NumExposedTransposes += RHS.NumExposedTransposes;
356 return *this;
357 }
358 };
359
360 /// Wrapper class representing a matrix as a set of vectors, either in row or
361 /// column major layout. All vectors must have the same vector type.
362 class MatrixTy {
363 SmallVector<Value *, 16> Vectors;
364
365 OpInfoTy OpInfo;
366
367 bool IsColumnMajor = true;
368
369 public:
370 MatrixTy() = default;
371 explicit MatrixTy(bool IsColumnMajor) : IsColumnMajor(IsColumnMajor) {}
372 MatrixTy(bool IsColumnMajor, ArrayRef<Value *> Vectors)
373 : Vectors(Vectors), IsColumnMajor(IsColumnMajor) {}
374 MatrixTy(bool IsColumnMajor, unsigned NumRows, unsigned NumColumns,
375 Type *EltTy)
376 : IsColumnMajor(IsColumnMajor) {
377
378 unsigned D = isColumnMajor() ? NumColumns : NumRows;
379 for (unsigned J = 0; J < D; ++J)
381 EltTy, isColumnMajor() ? NumRows : NumColumns)));
382 }
383
384 Value *getVector(unsigned i) const { return Vectors[i]; }
385 Value *getColumn(unsigned i) const {
386 assert(isColumnMajor() && "only supported for column-major matrixes");
387 return Vectors[i];
388 }
389 Value *getRow(unsigned i) const {
390 assert(!isColumnMajor() && "only supported for row-major matrixes");
391 return Vectors[i];
392 }
393
394 void setVector(unsigned i, Value *V) { Vectors[i] = V; }
395
396 Type *getElementType() const { return getVectorTy()->getElementType(); }
397
398 unsigned getNumVectors() const {
399 if (isColumnMajor())
400 return getNumColumns();
401 return getNumRows();
402 }
403
404 unsigned getNumColumns() const {
405 if (isColumnMajor())
406 return Vectors.size();
407 else {
408 assert(Vectors.size() > 0 && "Cannot call getNumRows without columns");
409 return getVectorTy()->getNumElements();
410 }
411 }
412 unsigned getNumRows() const {
413 if (isColumnMajor()) {
414 assert(Vectors.size() > 0 && "Cannot call getNumRows without columns");
415 return getVectorTy()->getNumElements();
416 } else
417 return Vectors.size();
418 }
419
420 void addVector(Value *V) { Vectors.push_back(V); }
421 FixedVectorType *getColumnTy() {
422 assert(isColumnMajor() && "only supported for column-major matrixes");
423 return getVectorTy();
424 }
425
426 FixedVectorType *getVectorTy() const {
427 return cast<FixedVectorType>(Vectors[0]->getType());
428 }
429
430 iterator_range<SmallVector<Value *, 8>::iterator> columns() {
431 assert(isColumnMajor() &&
432 "columns() only supported for column-major matrixes");
433 return make_range(Vectors.begin(), Vectors.end());
434 }
435
436 iterator_range<SmallVector<Value *, 8>::iterator> vectors() {
437 return make_range(Vectors.begin(), Vectors.end());
438 }
439
440 /// Embed the vectors of the matrix into a flat vector by concatenating
441 /// them.
442 Value *embedInVector(IRBuilder<> &Builder) const {
443 return Vectors.size() == 1 ? Vectors[0]
444 : concatenateVectors(Builder, Vectors);
445 }
446
447 MatrixTy &addNumLoads(unsigned N) {
448 OpInfo.NumLoads += N;
449 return *this;
450 }
451
452 void setNumLoads(unsigned N) { OpInfo.NumLoads = N; }
453
454 MatrixTy &addNumStores(unsigned N) {
455 OpInfo.NumStores += N;
456 return *this;
457 }
458
459 MatrixTy &addNumExposedTransposes(unsigned N) {
460 OpInfo.NumExposedTransposes += N;
461 return *this;
462 }
463
464 MatrixTy &addNumComputeOps(unsigned N) {
465 OpInfo.NumComputeOps += N;
466 return *this;
467 }
468
469 unsigned getNumStores() const { return OpInfo.NumStores; }
470 unsigned getNumLoads() const { return OpInfo.NumLoads; }
471 unsigned getNumComputeOps() const { return OpInfo.NumComputeOps; }
472
473 const OpInfoTy &getOpInfo() const { return OpInfo; }
474
475 bool isColumnMajor() const { return IsColumnMajor; }
476
477 unsigned getStride() const {
478 if (isColumnMajor())
479 return getNumRows();
480 return getNumColumns();
481 }
482
483 ShapeInfo shape() const { return {getNumRows(), getNumColumns()}; }
484
485 /// Extract a vector of \p NumElts starting at index (\p I, \p J). If the
486 /// matrix is column-major, the result vector is extracted from a column
487 /// vector, otherwise from a row vector.
488 Value *extractVector(unsigned I, unsigned J, unsigned NumElts,
489 IRBuilder<> &Builder) const {
490 Value *Vec = isColumnMajor() ? getColumn(J) : getRow(I);
491 assert(cast<FixedVectorType>(Vec->getType())->getNumElements() >=
492 NumElts &&
493 "Extracted vector will contain poison values");
494 return Builder.CreateShuffleVector(
495 Vec, createSequentialMask(isColumnMajor() ? I : J, NumElts, 0),
496 "block");
497 }
498 };
499
500 /// Maps instructions to their shape information. The shape information
501 /// describes the shape to be used while lowering. This matches the shape of
502 /// the result value of the instruction, with the only exceptions being store
503 /// instructions and the matrix_column_major_store intrinsics. For those, the
504 /// shape information indicates that those instructions should be lowered
505 /// using shape information as well. Note that extra care is needed when
506 /// erasing or RAUW'ing a value that is present in ShapeMap. If the
507 /// replacement is also a matrix operation, use
508 /// updateShapeAndReplaceAllUsesWith to make sure the replacement is added to
509 /// ShapeMap. We don't use ValueMap, as there are also cases where we do not
510 /// want to add shape information for a replacement instruction. When directly
511 /// erasing a value with an entry in ShapeMap, use
512 /// eraseFromParentAndRemoveFromShapeMap to make sure ShapeMap is also updated
513 /// accordingly.
514 DenseMap<Value *, ShapeInfo> ShapeMap;
515
516 /// List of instructions to remove. While lowering, we are not replacing all
517 /// users of a lowered instruction, if shape information is available and
518 /// those need to be removed after we finished lowering.
519 SmallVector<Instruction *, 16> ToRemove;
520
521 /// Map from instructions to their produced column matrix.
522 MapVector<Value *, MatrixTy> Inst2ColumnMatrix;
523
524private:
525 FastMathFlags getFastMathFlags(Instruction *Inst) const {
526 FastMathFlags FMF;
527
528 if (isa<FPMathOperator>(*Inst))
529 FMF = Inst->getFastMathFlags();
530
531 FMF.setAllowContract(Opts.matrix_allow_contract || FMF.allowContract());
532
533 return FMF;
534 }
535
536 bool isColumnMajor() const {
537 return Opts.matrix_default_layout == MatrixLayoutTy::ColumnMajor;
538 }
539
540 unsigned getStride(const ShapeInfo &SI) const {
541 return isColumnMajor() ? SI.NumRows : SI.NumColumns;
542 }
543
544 unsigned getNumVectors(const ShapeInfo &SI) const {
545 return isColumnMajor() ? SI.NumColumns : SI.NumRows;
546 }
547
548public:
549 LowerMatrixIntrinsics(const ScalarOptions &Opts, Function &F,
550 TargetTransformInfo &TTI, FunctionAnalysisManager *AM)
551 : Opts(Opts), Func(F), DL(F.getDataLayout()), TTI(TTI), AM(AM) {}
552
553 unsigned getNumOps(Type *VT) {
554 assert(isa<FixedVectorType>(VT) && "Expected vector type");
555 return getNumOps(VT->getScalarType(),
556 cast<FixedVectorType>(VT)->getNumElements());
557 }
558
559 /// Is this the minimal version executed in the backend pipelines.
560 bool isMinimal() const {
561 return !DT;
562 }
563
564 /// Return the estimated number of vector ops required for an operation on
565 /// \p VT * N.
566 unsigned getNumOps(Type *ST, unsigned N) {
567 return std::ceil((ST->getPrimitiveSizeInBits() * N).getFixedValue() /
568 double(TTI.getRegisterBitWidth(
570 .getFixedValue()));
571 }
572
573 /// Estimate the number of native vector operations for a multiply of matrices
574 /// with dimensions \p R x \p M and \p M x \p C. Native ops are computed as
575 /// ceil(ElementCount * ElementBits / RegisterBits).
576 ///
577 /// Native vector ops per operation type (VF = native vector elements):
578 /// FMAs: C * ceil(R/VF) * M (one FMA per VF output elements)
579 /// A loads: ceil(R/VF) * M (A has M columns, ceil(R/VF) native loads each)
580 /// B loads: ceil(M/VF) * C (B has C columns, ceil(M/VF) native loads each)
581 /// Stores: C * ceil(R/VF) (one store per VF output elements)
582 unsigned getNumNativeVectorOps(Type *EltType, unsigned R, unsigned M,
583 unsigned C) {
584 unsigned NumFMAs = C * getNumOps(EltType, R) * M;
585 unsigned NumALoads = getNumOps(EltType, R) * M;
586 unsigned NumBLoads = getNumOps(EltType, M) * C;
587 unsigned NumStores = getNumOps(EltType, R) * C;
588 return NumFMAs + NumALoads + NumBLoads + NumStores;
589 }
590
591 /// Return the set of vectors that a matrix value is lowered to.
592 ///
593 /// If we lowered \p MatrixVal, just return the cache result matrix. Otherwise
594 /// split the flat vector \p MatrixVal containing a matrix with shape \p SI
595 /// into vectors.
596 MatrixTy getMatrix(Value *MatrixVal, const ShapeInfo &SI,
597 IRBuilder<> &Builder) {
598 FixedVectorType *VType = cast<FixedVectorType>(MatrixVal->getType());
599 assert(VType->getNumElements() == SI.NumRows * SI.NumColumns &&
600 "The vector size must match the number of matrix elements");
601
602 // Check if we lowered MatrixVal using shape information. In that case,
603 // return the existing matrix, if it matches the requested shape
604 // information. If there is a mis-match, embed the result in a flat
605 // vector and split it later.
606 auto Found = Inst2ColumnMatrix.find(MatrixVal);
607 if (Found != Inst2ColumnMatrix.end()) {
608 MatrixTy &M = Found->second;
609 // Return the found matrix, if its shape matches the requested shape
610 // information
611 if (SI.NumRows == M.getNumRows() && SI.NumColumns == M.getNumColumns())
612 return M;
613
614 MatrixVal = M.embedInVector(Builder);
615 }
616
617 // Otherwise split MatrixVal.
618 SmallVector<Value *, 16> SplitVecs;
619 for (unsigned MaskStart = 0; MaskStart < VType->getNumElements();
620 MaskStart += getStride(SI)) {
621 Value *V = Builder.CreateShuffleVector(
622 MatrixVal, createSequentialMask(MaskStart, getStride(SI), 0),
623 "split");
624 SplitVecs.push_back(V);
625 }
626
627 if (Instruction *Inst = dyn_cast<Instruction>(MatrixVal)) {
628 if (Found != Inst2ColumnMatrix.end()) {
629 // FIXME: re: "at least": SplitVecs.size() doesn't count the shuffles
630 // that embedInVector created.
631 LLVM_DEBUG(dbgs() << "matrix reshape from " << Found->second.shape()
632 << " to " << SI << " using at least "
633 << SplitVecs.size() << " shuffles on behalf of:\n"
634 << *Inst << '\n');
635 ReshapedMatrices++;
636 } else if (!ShapeMap.contains(MatrixVal)) {
638 dbgs()
639 << "splitting a " << SI << " matrix with " << SplitVecs.size()
640 << " shuffles beacuse we do not have a shape-aware lowering for "
641 "its def:\n"
642 << *Inst << '\n');
643 (void)Inst;
644 SplitMatrices++;
645 } else {
646 // The ShapeMap has it, so it's a case where we're being lowered
647 // before the def, and we expect that InstCombine will clean things up
648 // afterward.
649 }
650 }
651
652 return {isColumnMajor(), SplitVecs};
653 }
654
655 /// If \p V already has a known shape return false. Otherwise set the shape
656 /// for instructions that support it.
657 bool setShapeInfo(Value *V, ShapeInfo Shape) {
658 assert(Shape && "Shape not set");
659 if (isa<UndefValue>(V) || !supportsShapeInfo(V))
660 return false;
661
662 auto SIter = ShapeMap.find(V);
663 if (SIter != ShapeMap.end()) {
664 if (Opts.verify_matrix_shapes &&
665 (SIter->second.NumRows != Shape.NumRows ||
666 SIter->second.NumColumns != Shape.NumColumns)) {
667 errs() << "Conflicting shapes (" << SIter->second.NumRows << "x"
668 << SIter->second.NumColumns << " vs " << Shape.NumRows << "x"
669 << Shape.NumColumns << ") for " << *V << "\n";
671 "Matrix shape verification failed, compilation aborted!");
672 }
673
674 LLVM_DEBUG(dbgs() << " not overriding existing shape: "
675 << SIter->second.NumRows << " "
676 << SIter->second.NumColumns << " for " << *V << "\n");
677 return false;
678 }
679
680 ShapeMap.insert({V, Shape});
681 LLVM_DEBUG(dbgs() << " " << Shape.NumRows << " x " << Shape.NumColumns
682 << " for " << *V << "\n");
683 return true;
684 }
685
686 /// Returns true if shape information can be used for \p V. The supported
687 /// instructions must match the instructions that can be lowered by this pass.
688 bool supportsShapeInfo(Value *V) {
690 if (!Inst)
691 return false;
692
693 IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst);
694 if (II)
695 switch (II->getIntrinsicID()) {
696 case Intrinsic::matrix_multiply:
697 case Intrinsic::matrix_transpose:
698 case Intrinsic::matrix_column_major_load:
699 case Intrinsic::matrix_column_major_store:
700 return true;
701 default:
702 break;
703 }
705 }
706
707 /// Propagate the shape information of instructions to their users.
708 /// The work list contains instructions for which we can compute the shape,
709 /// either based on the information provided by matrix intrinsics or known
710 /// shapes of operands.
712 propagateShapeForward(SmallVectorImpl<Instruction *> &WorkList) {
714 // Pop an element for which we guaranteed to have at least one of the
715 // operand shapes. Add the shape for this and then add users to the work
716 // list.
717 LLVM_DEBUG(dbgs() << "Forward-propagate shapes:\n");
718 while (!WorkList.empty()) {
719 Instruction *Inst = WorkList.pop_back_val();
720
721 // New entry, set the value and insert operands
722 bool Propagate = false;
723 if (auto SI = computeShapeInfoForInst(Inst, ShapeMap))
724 Propagate = setShapeInfo(Inst, *SI);
725
726 if (Propagate) {
727 NewWorkList.push_back(Inst);
728 for (auto *User : Inst->users())
729 if (ShapeMap.count(User) == 0)
730 WorkList.push_back(cast<Instruction>(User));
731 }
732 }
733
734 return NewWorkList;
735 }
736
737 /// Propagate the shape to operands of instructions with shape information.
738 /// \p Worklist contains the instruction for which we already know the shape.
740 propagateShapeBackward(SmallVectorImpl<Instruction *> &WorkList) {
742
743 auto pushInstruction = [](Value *V,
744 SmallVectorImpl<Instruction *> &WorkList) {
746 if (I)
747 WorkList.push_back(I);
748 };
749 // Pop an element with known shape. Traverse the operands, if their shape
750 // derives from the result shape and is unknown, add it and add them to the
751 // worklist.
752 LLVM_DEBUG(dbgs() << "Backward-propagate shapes:\n");
753 while (!WorkList.empty()) {
754 Value *V = WorkList.pop_back_val();
755
756 size_t BeforeProcessingV = WorkList.size();
757 if (!isa<Instruction>(V))
758 continue;
759
760 Value *MatrixA;
761 Value *MatrixB;
762 Value *M;
763 Value *N;
764 Value *K;
766 m_Value(MatrixA), m_Value(MatrixB), m_Value(M),
767 m_Value(N), m_Value(K)))) {
768 if (setShapeInfo(MatrixA, {M, N}))
769 pushInstruction(MatrixA, WorkList);
770
771 if (setShapeInfo(MatrixB, {N, K}))
772 pushInstruction(MatrixB, WorkList);
773
775 m_Value(MatrixA), m_Value(M), m_Value(N)))) {
776 // Flip dimensions.
777 if (setShapeInfo(MatrixA, {M, N}))
778 pushInstruction(MatrixA, WorkList);
780 m_Value(MatrixA), m_Value(), m_Value(), m_Value(),
781 m_Value(M), m_Value(N)))) {
782 if (setShapeInfo(MatrixA, {M, N})) {
783 pushInstruction(MatrixA, WorkList);
784 }
785 } else if (isa<LoadInst>(V) ||
787 // Nothing to do, no matrix input.
788 } else if (isa<StoreInst>(V)) {
789 // Nothing to do. We forward-propagated to this so we would just
790 // backward propagate to an instruction with an already known shape.
791 } else if (isShapePreserving(V)) {
793 // Propagate to all operands.
794 ShapeInfo Shape = ShapeMap[V];
795 for (Use &U : ShapedOps) {
796 if (setShapeInfo(U.get(), Shape))
797 pushInstruction(U.get(), WorkList);
798 }
799 }
800 // After we discovered new shape info for new instructions in the
801 // worklist, we use their users as seeds for the next round of forward
802 // propagation.
803 for (size_t I = BeforeProcessingV; I != WorkList.size(); I++)
804 for (User *U : WorkList[I]->users())
805 if (isa<Instruction>(U) && V != U)
806 NewWorkList.push_back(cast<Instruction>(U));
807 }
808 return NewWorkList;
809 }
810
811 /// (Op0 op Op1)^T -> Op0^T op Op1^T
812 /// Transpose \p Op0 and \p Op1 of shape \p Shape0 and \p Shape1, then use
813 /// them on both sides of \p Operation.
814 Instruction *distributeTransposes(
815 Value *Op0, ShapeInfo Shape0, Value *Op1, ShapeInfo Shape1,
816 MatrixBuilder &Builder,
817 function_ref<Instruction *(Value *, ShapeInfo, Value *, ShapeInfo)>
818 Operation) {
819 Value *T0 = Builder.CreateMatrixTranspose(
820 Op0, Shape0.NumRows, Shape0.NumColumns, Op0->getName() + "_t");
821 // We are being run after shape prop, add shape for newly created
822 // instructions so that we lower them later.
823 setShapeInfo(T0, Shape0.t());
824 Value *T1 = Builder.CreateMatrixTranspose(
825 Op1, Shape1.NumRows, Shape1.NumColumns, Op1->getName() + "_t");
826 setShapeInfo(T1, Shape1.t());
827 return Operation(T0, Shape0.t(), T1, Shape1.t());
828 }
829
830 /// Erase \p Inst from both ShapeMap (if an entry exists) and erase \p Inst
831 /// itself.
832 void eraseFromParentAndRemoveFromShapeMap(Instruction *Inst) {
833 ShapeMap.erase(Inst);
834 Inst->eraseFromParent();
835 }
836
837 /// Erase \p V from \p BB and move \II forward to avoid invalidating
838 /// iterators.
839 void eraseFromParentAndMove(Value *V, BasicBlock::reverse_iterator &II,
840 BasicBlock &BB) {
841 auto *Inst = cast<Instruction>(V);
842 // Still used, don't erase.
843 if (!Inst->use_empty())
844 return;
845 if (II != BB.rend() && Inst == &*II)
846 ++II;
847 eraseFromParentAndRemoveFromShapeMap(Inst);
848 }
849
850 /// Add a new entry to ShapeMap for \p New with \p Old's shape info, erase the
851 /// entry for \p Old and replace all uses of \p Old with \p New.
852 void updateShapeAndReplaceAllUsesWith(Instruction &Old, Value *New) {
853 // We need to remove Old from the ShapeMap otherwise RAUW will replace it
854 // with New. We should only add New it it supportsShapeInfo so we insert
855 // it conditionally instead.
856 auto S = ShapeMap.find(&Old);
857 if (S != ShapeMap.end()) {
858 ShapeInfo Shape = S->second;
859 ShapeMap.erase(S);
860 if (supportsShapeInfo(New))
861 ShapeMap.insert({New, Shape});
862 }
863 Old.replaceAllUsesWith(New);
864 }
865
866 /// Sink a top-level transpose inside matmuls and adds.
867 /// This creates and erases instructions as needed, and returns the newly
868 /// created instruction while updating the iterator to avoid invalidation. If
869 /// this returns nullptr, no new instruction was created.
870 Instruction *sinkTranspose(Instruction &I, BasicBlock::reverse_iterator &II,
871 bool &Changed) {
872 BasicBlock &BB = *I.getParent();
873 IRBuilder<> IB(&I);
874 MatrixBuilder Builder(IB);
875
876 Value *TA, *TAMA, *TAMB;
877 ConstantInt *R, *K, *C;
880 return nullptr;
881
882 // Transpose of a transpose is a nop when the shapes match.
883 Value *TATA;
885 m_Value(TATA), m_Specific(C), m_Specific(R)))) {
886 updateShapeAndReplaceAllUsesWith(I, TATA);
887 eraseFromParentAndMove(&I, II, BB);
888 eraseFromParentAndMove(TA, II, BB);
889 Changed = true;
890 return nullptr;
891 }
892
893 // k^T -> k
894 if (isSplat(TA)) {
895 updateShapeAndReplaceAllUsesWith(I, TA);
896 eraseFromParentAndMove(&I, II, BB);
897 Changed = true;
898 return nullptr;
899 }
900
901 // (A * B)^t -> B^t * A^t
902 // RxK KxC CxK KxR
904 m_Value(TAMA), m_Value(TAMB), m_ConstantInt(R),
906 auto NewInst = distributeTransposes(
907 TAMB, {K, C}, TAMA, {R, K}, Builder,
908 [&](Value *T0, ShapeInfo Shape0, Value *T1, ShapeInfo Shape1) {
909 return Builder.CreateMatrixMultiply(T0, T1, Shape0.NumRows,
910 Shape0.NumColumns,
911 Shape1.NumColumns, "mmul");
912 });
913 updateShapeAndReplaceAllUsesWith(I, NewInst);
914 eraseFromParentAndMove(&I, II, BB);
915 eraseFromParentAndMove(TA, II, BB);
916 Changed = true;
917 return NewInst;
918 }
919
920 // Same as above, but with a mul, which occurs when multiplied
921 // with a scalar.
922 // (A * k)^t -> A^t * k
923 // R x C RxC
924 if (match(TA, m_AnyMul(m_Value(TAMA), m_Value(TAMB))) &&
925 (isSplat(TAMA) || isSplat(TAMB))) {
926 IRBuilder<> LocalBuilder(&I);
927 // We know that the transposed operand is of shape RxC.
928 // An when multiplied with a scalar, the shape is preserved.
929 auto NewInst = distributeTransposes(
930 TAMA, {R, C}, TAMB, {R, C}, Builder,
931 [&](Value *T0, ShapeInfo Shape0, Value *T1, ShapeInfo Shape1) {
932 bool IsFP = I.getType()->isFPOrFPVectorTy();
933 auto *Mul = IsFP ? LocalBuilder.CreateFMul(T0, T1, "mmul")
934 : LocalBuilder.CreateMul(T0, T1, "mmul");
936 setShapeInfo(Result, Shape0);
937 return Result;
938 });
939 updateShapeAndReplaceAllUsesWith(I, NewInst);
940 eraseFromParentAndMove(&I, II, BB);
941 eraseFromParentAndMove(TA, II, BB);
942 Changed = true;
943 return NewInst;
944 }
945
946 // (A + B)^t -> A^t + B^t
947 // RxC RxC CxR CxR
948 if (match(TA, m_AnyAdd(m_Value(TAMA), m_Value(TAMB)))) {
949 IRBuilder<> LocalBuilder(&I);
950 auto NewInst = distributeTransposes(
951 TAMA, {R, C}, TAMB, {R, C}, Builder,
952 [&](Value *T0, ShapeInfo Shape0, Value *T1, ShapeInfo Shape1) {
953 bool IsFP = I.getType()->isFPOrFPVectorTy();
954 auto *Add = IsFP ? LocalBuilder.CreateFAdd(T0, T1, "madd")
955 : LocalBuilder.CreateAdd(T0, T1, "madd");
956
958 setShapeInfo(Result, Shape0);
959 return Result;
960 });
961 updateShapeAndReplaceAllUsesWith(I, NewInst);
962 eraseFromParentAndMove(&I, II, BB);
963 eraseFromParentAndMove(TA, II, BB);
964 Changed = true;
965 return NewInst;
966 }
967
968 return nullptr;
969 }
970
971 bool liftTranspose(Instruction &I) {
972 // Erase dead Instructions after lifting transposes from binops.
973 auto CleanupBinOp = [this](Instruction &T, Value *A, Value *B) {
974 if (T.use_empty())
975 eraseFromParentAndRemoveFromShapeMap(&T);
976 if (A->use_empty())
977 eraseFromParentAndRemoveFromShapeMap(cast<Instruction>(A));
978 if (A != B && B->use_empty())
979 eraseFromParentAndRemoveFromShapeMap(cast<Instruction>(B));
980 };
981
982 Value *A, *B, *AT, *BT;
983 ConstantInt *R, *K, *C;
984 // A^t * B ^t -> (B * A)^t
990 IRBuilder<> IB(&I);
991 MatrixBuilder Builder(IB);
992 Value *M = Builder.CreateMatrixMultiply(
993 BT, AT, C->getZExtValue(), K->getZExtValue(), R->getZExtValue());
994 setShapeInfo(M, {C, R});
995 Instruction *NewInst = Builder.CreateMatrixTranspose(M, C->getZExtValue(),
996 R->getZExtValue());
997 updateShapeAndReplaceAllUsesWith(I, NewInst);
998 CleanupBinOp(I, A, B);
999 return true;
1000 }
1001 // A^t + B ^t -> (A + B)^t. Pick rows and columns from first transpose. If
1002 // the shape of the second transpose is different, there's a shape conflict
1003 // which gets resolved by picking the shape of the first operand.
1004 else if (match(&I, m_FAdd(m_Value(A), m_Value(B))) &&
1006 m_Value(AT), m_ConstantInt(R), m_ConstantInt(C))) &&
1009 IRBuilder<> Builder(&I);
1010 auto *Add = Builder.CreateFAdd(AT, BT, "mfadd");
1011 MatrixBuilder MBuilder(Builder);
1012 Instruction *NewInst = MBuilder.CreateMatrixTranspose(
1013 Add, R->getZExtValue(), C->getZExtValue(), "mfadd_t");
1014 updateShapeAndReplaceAllUsesWith(I, NewInst);
1015 assert(computeShapeInfoForInst(NewInst, ShapeMap) ==
1016 computeShapeInfoForInst(&I, ShapeMap) &&
1017 "Shape of new instruction doesn't match original shape.");
1018 CleanupBinOp(I, A, B);
1019 if (auto *AddI = dyn_cast<Instruction>(Add)) {
1020 setShapeInfo(AddI, {R, C});
1021 assert(
1022 computeShapeInfoForInst(AddI, ShapeMap).value_or(ShapeMap[AddI]) ==
1023 ShapeMap[AddI] &&
1024 "Shape of updated addition doesn't match cached shape.");
1025 }
1026 return true;
1027 }
1028 return false;
1029 }
1030
1031 /// Try moving transposes in order to fold them away or into multiplies.
1032 bool optimizeTransposes() {
1033 bool Changed = false;
1034 // First sink all transposes inside matmuls and adds, hoping that we end up
1035 // with NN, NT or TN variants.
1036 for (BasicBlock &BB : reverse(Func)) {
1037 for (auto II = BB.rbegin(); II != BB.rend();) {
1038 Instruction &I = *II;
1039 // We may remove II. By default continue on the next/prev instruction.
1040 ++II;
1041 if (Instruction *NewInst = sinkTranspose(I, II, Changed))
1042 II = std::next(BasicBlock::reverse_iterator(NewInst));
1043 }
1044 }
1045
1046 // If we have a TT matmul or a TT add, lift the transpose. We may be able
1047 // to fold into consuming multiply or add.
1048 for (BasicBlock &BB : Func) {
1049 for (Instruction &I : llvm::make_early_inc_range(BB)) {
1050 Changed |= liftTranspose(I);
1051 }
1052 }
1053 return Changed;
1054 }
1055
1056 bool Visit() {
1058
1059 // Initially only the shape of matrix intrinsics is known.
1060 // Initialize the work list with ops carrying shape information.
1061 for (BasicBlock &BB : Func)
1062 for (Instruction &Inst : BB) {
1063 IntrinsicInst *II = dyn_cast<IntrinsicInst>(&Inst);
1064 if (!II)
1065 continue;
1066
1067 switch (II->getIntrinsicID()) {
1068 case Intrinsic::matrix_multiply:
1069 case Intrinsic::matrix_transpose:
1070 case Intrinsic::matrix_column_major_load:
1071 case Intrinsic::matrix_column_major_store:
1072 WorkList.push_back(&Inst);
1073 break;
1074 default:
1075 break;
1076 }
1077 }
1078
1079 // Avoid unnecessary work if there are no matrix intrinsics in the function.
1080 if (WorkList.empty())
1081 return false;
1082
1083 if (AM) {
1084 ORE = &AM->getResult<OptimizationRemarkEmitterAnalysis>(Func);
1085 AA = &AM->getResult<AAManager>(Func);
1086 DT = &AM->getResult<DominatorTreeAnalysis>(Func);
1087 LI = &AM->getResult<LoopAnalysis>(Func);
1088 }
1089
1090 // Propagate shapes until nothing changes any longer.
1091 while (!WorkList.empty()) {
1092 WorkList = propagateShapeForward(WorkList);
1093 WorkList = propagateShapeBackward(WorkList);
1094 }
1095
1096 bool Changed = false;
1097 if (!isMinimal()) {
1098 Changed |= optimizeTransposes();
1099 if (Opts.matrix_print_after_transpose_opt) {
1100 dbgs() << "Dump after matrix transpose optimization:\n";
1101 Func.print(dbgs());
1102 }
1103 }
1104
1105 SmallVector<CallInst *, 16> MaybeFusableInsts;
1106 SmallVector<Instruction *, 16> MatrixInsts;
1108
1109 // First, collect all instructions with shape information and candidates for
1110 // fusion (currently only matrix multiplies).
1111 ReversePostOrderTraversal<Function *> RPOT(&Func);
1112 for (auto *BB : RPOT)
1113 for (Instruction &I : *BB) {
1115 LifetimeEnds.push_back(cast<IntrinsicInst>(&I));
1116 if (!ShapeMap.contains(&I))
1117 continue;
1119 MaybeFusableInsts.push_back(cast<CallInst>(&I));
1120 MatrixInsts.push_back(&I);
1121 }
1122
1123 // Second, try to lower any dot products
1124 SmallPtrSet<Instruction *, 16> FusedInsts;
1125 for (CallInst *CI : MaybeFusableInsts)
1126 lowerDotProduct(CI, FusedInsts, getFastMathFlags(CI));
1127
1128 // Third, try to fuse candidates.
1129 for (CallInst *CI : MaybeFusableInsts)
1130 if (!FusedInsts.contains(CI))
1131 LowerMatrixMultiplyFused(CI, FusedInsts, LifetimeEnds);
1132
1133 Changed |= !FusedInsts.empty();
1134
1135 // Fourth, pre-process all the PHINode's. The incoming values will be
1136 // assigned later in VisitPHI.
1137 for (Instruction *Inst : MatrixInsts) {
1138 if (FusedInsts.count(Inst))
1139 continue;
1140
1141 auto *PHI = dyn_cast<PHINode>(Inst);
1142 if (!PHI)
1143 continue;
1144
1145 const ShapeInfo &SI = ShapeMap.at(Inst);
1146 auto *EltTy = cast<FixedVectorType>(PHI->getType())->getElementType();
1147 MatrixTy PhiM(isColumnMajor(), SI.NumRows, SI.NumColumns, EltTy);
1148
1149 IRBuilder<> Builder(Inst);
1150 for (unsigned VI = 0, VE = PhiM.getNumVectors(); VI != VE; ++VI)
1151 PhiM.setVector(VI, Builder.CreatePHI(PhiM.getVectorTy(),
1152 PHI->getNumIncomingValues(),
1153 PHI->getName()));
1154 assert(!Inst2ColumnMatrix.contains(PHI) && "map already contains phi?");
1155 Inst2ColumnMatrix[PHI] = PhiM;
1156 }
1157
1158 // Fifth, lower remaining instructions with shape information.
1159 for (Instruction *Inst : MatrixInsts) {
1160 if (FusedInsts.count(Inst))
1161 continue;
1162
1163 const ShapeInfo &SI = ShapeMap.at(Inst);
1164
1165 Value *Op1;
1166 Value *Op2;
1167 MatrixTy Result;
1168 IRBuilder<> Builder(Inst);
1169 Builder.disableGEPCanonicalization();
1170 if (auto *BinOp = dyn_cast<BinaryOperator>(Inst))
1171 Result = VisitBinaryOperator(BinOp, SI, Builder);
1172 else if (auto *Cast = dyn_cast<CastInst>(Inst))
1173 Result = VisitCastInstruction(Cast, SI, Builder);
1174 else if (auto *UnOp = dyn_cast<UnaryOperator>(Inst))
1175 Result = VisitUnaryOperator(UnOp, SI, Builder);
1176 else if (auto *Intr = dyn_cast<IntrinsicInst>(Inst))
1177 Result = VisitIntrinsicInst(Intr, SI, Builder);
1178 else if (auto *Select = dyn_cast<SelectInst>(Inst))
1179 Result = VisitSelectInst(Select, SI, Builder);
1180 else if (match(Inst, m_Load(m_Value(Op1))))
1181 Result = VisitLoad(cast<LoadInst>(Inst), SI, Op1, Builder);
1182 else if (match(Inst, m_Store(m_Value(Op1), m_Value(Op2))))
1183 Result = VisitStore(cast<StoreInst>(Inst), SI, Op1, Op2, Builder);
1184 else if (auto *PHI = dyn_cast<PHINode>(Inst))
1185 Result = VisitPHI(PHI, SI, Builder);
1186 else
1187 continue;
1188
1189 finalizeLowering(Inst, Result, Builder);
1190 Changed = true;
1191 }
1192
1193 if (ORE) {
1194 RemarkGenerator RemarkGen(Inst2ColumnMatrix, *ORE, Func);
1195 RemarkGen.emitRemarks();
1196 }
1197
1198 // Delete the instructions backwards, as it has a reduced likelihood of
1199 // having to update as many def-use and use-def chains.
1200 //
1201 // Because we add to ToRemove during fusion we can't guarantee that defs
1202 // are before uses. Change uses to poison temporarily as these should get
1203 // removed as well.
1204 //
1205 // For verification, we keep track of where we changed uses to poison in
1206 // PoisonedInsts and then check that we in fact remove them.
1207 SmallPtrSet<Instruction *, 16> PoisonedInsts;
1208 for (auto *Inst : reverse(ToRemove)) {
1209 for (Use &U : llvm::make_early_inc_range(Inst->uses())) {
1210 if (auto *Poisoned = dyn_cast<Instruction>(U.getUser()))
1211 PoisonedInsts.insert(Poisoned);
1212 U.set(PoisonValue::get(Inst->getType()));
1213 }
1214 Inst->eraseFromParent();
1215 PoisonedInsts.erase(Inst);
1216 }
1217 if (!PoisonedInsts.empty()) {
1218 // If we didn't remove all poisoned instructions, it's a hard error.
1219 dbgs() << "Poisoned but present instructions:\n";
1220 for (auto *I : PoisonedInsts)
1221 dbgs() << *I << "\n";
1222 llvm_unreachable("Poisoned but instruction not removed");
1223 }
1224
1225 return Changed;
1226 }
1227
1228 /// Replace intrinsic calls.
1229 MatrixTy VisitIntrinsicInst(IntrinsicInst *Inst, const ShapeInfo &SI,
1230 IRBuilder<> &Builder) {
1231 assert(Inst->getCalledFunction() &&
1232 Inst->getCalledFunction()->isIntrinsic());
1233
1234 switch (Inst->getCalledFunction()->getIntrinsicID()) {
1235 case Intrinsic::matrix_multiply:
1236 return LowerMultiply(Inst, Builder);
1237 case Intrinsic::matrix_transpose:
1238 return LowerTranspose(Inst, Builder);
1239 case Intrinsic::matrix_column_major_load:
1240 return LowerColumnMajorLoad(Inst, Builder);
1241 case Intrinsic::matrix_column_major_store:
1242 return LowerColumnMajorStore(Inst, Builder);
1243 case Intrinsic::abs:
1244 case Intrinsic::fabs: {
1245 MatrixTy Result(isColumnMajor());
1246 MatrixTy M = getMatrix(Inst->getOperand(0), SI, Builder);
1247 Builder.setFastMathFlags(getFastMathFlags(Inst));
1248
1249 for (auto *Vector : M.vectors()) {
1250 switch (Inst->getIntrinsicID()) {
1251 case Intrinsic::abs:
1252 Result.addVector(Builder.CreateBinaryIntrinsic(Intrinsic::abs, Vector,
1253 Inst->getOperand(1)));
1254 continue;
1255 case Intrinsic::fabs:
1256 Result.addVector(
1257 Builder.CreateUnaryIntrinsic(Inst->getIntrinsicID(), Vector));
1258 continue;
1259 default:
1260 llvm_unreachable("unexpected intrinsic");
1261 }
1262 }
1263
1264 return Result.addNumComputeOps(getNumOps(Result.getVectorTy()) *
1265 Result.getNumVectors());
1266 }
1267 default:
1268 break;
1269 }
1271 "only intrinsics supporting shape info should be seen here");
1272 }
1273
1274 /// Compute the alignment for a column/row \p Idx with \p Stride between them.
1275 /// The address at \p Idx == 0 has alignment \p A. If \p Stride is a
1276 /// ConstantInt, reduce the initial alignment based on the byte offset. For
1277 /// non-ConstantInt strides, return the common alignment of the initial
1278 /// alignment and the element size in bytes.
1279 Align getAlignForIndex(unsigned Idx, Value *Stride, Type *ElementTy,
1280 MaybeAlign A) const {
1281 Align InitialAlign = DL.getValueOrABITypeAlignment(A, ElementTy);
1282 if (Idx == 0)
1283 return InitialAlign;
1284
1285 TypeSize ElementSizeInBits = DL.getTypeSizeInBits(ElementTy);
1286 if (auto *ConstStride = dyn_cast<ConstantInt>(Stride)) {
1287 uint64_t StrideInBytes =
1288 ConstStride->getZExtValue() * ElementSizeInBits / 8;
1289 return commonAlignment(InitialAlign, Idx * StrideInBytes);
1290 }
1291 return commonAlignment(InitialAlign, ElementSizeInBits / 8);
1292 }
1293
1294 IntegerType *getIndexType(Value *Ptr) const {
1295 return cast<IntegerType>(DL.getIndexType(Ptr->getType()));
1296 }
1297
1298 Value *getIndex(Value *Ptr, uint64_t V) const {
1299 return ConstantInt::get(getIndexType(Ptr), V);
1300 }
1301
1302 Value *castToIndexType(Value *Ptr, Value *V, IRBuilder<> &Builder) const {
1303 assert(isa<IntegerType>(V->getType()) &&
1304 "Attempted to cast non-integral type to integer index");
1305 // In case the data layout's index type differs in width from the type of
1306 // the value we're given, truncate or zero extend to the appropriate width.
1307 // We zero extend here as indices are unsigned.
1308 return Builder.CreateZExtOrTrunc(V, getIndexType(Ptr),
1309 V->getName() + ".cast");
1310 }
1311
1312 /// Load a matrix with \p Shape starting at \p Ptr and using \p Stride between
1313 /// vectors.
1314 MatrixTy loadMatrix(Type *Ty, Value *Ptr, MaybeAlign MAlign, Value *Stride,
1315 bool IsVolatile, ShapeInfo Shape, IRBuilder<> &Builder) {
1316 auto *VType = cast<FixedVectorType>(Ty);
1317 Type *EltTy = VType->getElementType();
1318 Type *VecTy = FixedVectorType::get(EltTy, getStride(Shape));
1319 Value *EltPtr = Ptr;
1320 MatrixTy Result(isColumnMajor());
1321 Stride = castToIndexType(Ptr, Stride, Builder);
1322 for (unsigned I = 0, E = getNumVectors(Shape); I < E; ++I) {
1324 EltPtr, Builder.getIntN(Stride->getType()->getScalarSizeInBits(), I),
1325 Stride, getStride(Shape), EltTy, Builder);
1326 Value *Vector = Builder.CreateAlignedLoad(
1327 VecTy, GEP, getAlignForIndex(I, Stride, EltTy, MAlign),
1328 IsVolatile, "col.load");
1329
1330 Result.addVector(Vector);
1331 }
1332 return Result.addNumLoads(getNumOps(Result.getVectorTy()) *
1333 Result.getNumVectors());
1334 }
1335
1336 /// Loads a sub-matrix with shape \p ResultShape from a \p R x \p C matrix,
1337 /// starting at \p MatrixPtr[I][J].
1338 MatrixTy loadMatrix(Value *MatrixPtr, MaybeAlign Align, bool IsVolatile,
1339 ShapeInfo MatrixShape, Value *I, Value *J,
1340 ShapeInfo ResultShape, Type *EltTy,
1341 IRBuilder<> &Builder) {
1342 Value *Offset = Builder.CreateAdd(
1343 Builder.CreateMul(J, getIndex(MatrixPtr, getStride(MatrixShape))), I);
1344
1345 Value *TileStart = Builder.CreateInBoundsGEP(EltTy, MatrixPtr, Offset);
1346 auto *TileTy = FixedVectorType::get(EltTy, ResultShape.NumRows *
1347 ResultShape.NumColumns);
1348
1349 return loadMatrix(TileTy, TileStart, Align,
1350 getIndex(MatrixPtr, getStride(MatrixShape)), IsVolatile,
1351 ResultShape, Builder);
1352 }
1353
1354 /// Lower a load instruction with shape information.
1355 MatrixTy LowerLoad(Instruction *Inst, Value *Ptr, MaybeAlign Align,
1356 Value *Stride, bool IsVolatile, ShapeInfo Shape,
1357 IRBuilder<> &Builder) {
1358 return loadMatrix(Inst->getType(), Ptr, Align, Stride, IsVolatile, Shape,
1359 Builder);
1360 }
1361
1362 /// Lowers llvm.matrix.column.major.load.
1363 ///
1364 /// The intrinsic loads a matrix from memory using a stride between columns.
1365 MatrixTy LowerColumnMajorLoad(CallInst *Inst, IRBuilder<> &Builder) {
1366 assert(Opts.matrix_default_layout == MatrixLayoutTy::ColumnMajor &&
1367 "Intrinsic only supports column-major layout!");
1368 Value *Ptr = Inst->getArgOperand(0);
1369 Value *Stride = Inst->getArgOperand(1);
1370 return LowerLoad(Inst, Ptr, Inst->getParamAlign(0), Stride,
1371 cast<ConstantInt>(Inst->getArgOperand(2))->isOne(),
1372 {Inst->getArgOperand(3), Inst->getArgOperand(4)}, Builder);
1373 }
1374
1375 /// Stores a sub-matrix \p StoreVal into the \p R x \p C matrix starting at \p
1376 /// MatrixPtr[I][J].
1377 void storeMatrix(const MatrixTy &StoreVal, Value *MatrixPtr,
1378 MaybeAlign MAlign, bool IsVolatile, ShapeInfo MatrixShape,
1379 Value *I, Value *J, Type *EltTy, IRBuilder<> &Builder) {
1380 Value *Offset = Builder.CreateAdd(
1381 Builder.CreateMul(J, getIndex(MatrixPtr, getStride(MatrixShape))), I);
1382
1383 Value *TileStart = Builder.CreateInBoundsGEP(EltTy, MatrixPtr, Offset);
1384 auto *TileTy = FixedVectorType::get(EltTy, StoreVal.getNumRows() *
1385 StoreVal.getNumColumns());
1386
1387 storeMatrix(TileTy, StoreVal, TileStart, MAlign,
1388 getIndex(MatrixPtr, getStride(MatrixShape)), IsVolatile,
1389 Builder);
1390 }
1391
1392 /// Store matrix \p StoreVal starting at \p Ptr and using \p Stride between
1393 /// vectors.
1394 MatrixTy storeMatrix(Type *Ty, MatrixTy StoreVal, Value *Ptr,
1395 MaybeAlign MAlign, Value *Stride, bool IsVolatile,
1396 IRBuilder<> &Builder) {
1397 auto *VType = cast<FixedVectorType>(Ty);
1398 Value *EltPtr = Ptr;
1399 Stride = castToIndexType(Ptr, Stride, Builder);
1400 for (auto Vec : enumerate(StoreVal.vectors())) {
1402 EltPtr,
1403 Builder.getIntN(Stride->getType()->getScalarSizeInBits(),
1404 Vec.index()),
1405 Stride, StoreVal.getStride(), VType->getElementType(), Builder);
1406 Builder.CreateAlignedStore(Vec.value(), GEP,
1407 getAlignForIndex(Vec.index(), Stride,
1408 VType->getElementType(),
1409 MAlign),
1410 IsVolatile);
1411 }
1412 return MatrixTy(isColumnMajor())
1413 .addNumStores(getNumOps(StoreVal.getVectorTy()) *
1414 StoreVal.getNumVectors());
1415 }
1416
1417 /// Lower a store instruction with shape information.
1418 MatrixTy LowerStore(Instruction *Inst, Value *Matrix, Value *Ptr,
1419 MaybeAlign A, Value *Stride, bool IsVolatile,
1420 ShapeInfo Shape, IRBuilder<> &Builder) {
1421 auto StoreVal = getMatrix(Matrix, Shape, Builder);
1422 return storeMatrix(Matrix->getType(), StoreVal, Ptr, A, Stride, IsVolatile,
1423 Builder);
1424 }
1425
1426 /// Lowers llvm.matrix.column.major.store.
1427 ///
1428 /// The intrinsic store a matrix back memory using a stride between columns.
1429 MatrixTy LowerColumnMajorStore(CallInst *Inst, IRBuilder<> &Builder) {
1430 assert(Opts.matrix_default_layout == MatrixLayoutTy::ColumnMajor &&
1431 "Intrinsic only supports column-major layout!");
1432 Value *Matrix = Inst->getArgOperand(0);
1433 Value *Ptr = Inst->getArgOperand(1);
1434 Value *Stride = Inst->getArgOperand(2);
1435 return LowerStore(Inst, Matrix, Ptr, Inst->getParamAlign(1), Stride,
1436 cast<ConstantInt>(Inst->getArgOperand(3))->isOne(),
1437 {Inst->getArgOperand(4), Inst->getArgOperand(5)},
1438 Builder);
1439 }
1440
1441 // Set elements I..I+NumElts-1 to Block
1442 Value *insertVector(Value *Col, unsigned I, Value *Block,
1443 IRBuilder<> &Builder) {
1444
1445 // First, bring Block to the same size as Col
1446 unsigned BlockNumElts =
1447 cast<FixedVectorType>(Block->getType())->getNumElements();
1448 unsigned NumElts = cast<FixedVectorType>(Col->getType())->getNumElements();
1449 assert(NumElts >= BlockNumElts && "Too few elements for current block");
1450
1451 Block = Builder.CreateShuffleVector(
1452 Block, createSequentialMask(0, BlockNumElts, NumElts - BlockNumElts));
1453
1454 // If Col is 7 long and I is 2 and BlockNumElts is 2 the mask is: 0, 1, 7,
1455 // 8, 4, 5, 6
1456 SmallVector<int, 16> Mask;
1457 unsigned i;
1458 for (i = 0; i < I; i++)
1459 Mask.push_back(i);
1460
1461 unsigned VecNumElts =
1462 cast<FixedVectorType>(Col->getType())->getNumElements();
1463 for (; i < I + BlockNumElts; i++)
1464 Mask.push_back(i - I + VecNumElts);
1465
1466 for (; i < VecNumElts; i++)
1467 Mask.push_back(i);
1468
1469 return Builder.CreateShuffleVector(Col, Block, Mask);
1470 }
1471
1472 Value *createMulAdd(Value *Sum, Value *A, Value *B, bool UseFPOp,
1473 IRBuilder<> &Builder, bool AllowContraction,
1474 unsigned &NumComputeOps) {
1475 NumComputeOps += getNumOps(A->getType());
1476 if (!Sum)
1477 return UseFPOp ? Builder.CreateFMul(A, B) : Builder.CreateMul(A, B);
1478
1479 if (UseFPOp) {
1480 if (AllowContraction) {
1481 // Use fmuladd for floating point operations and let the backend decide
1482 // if that's profitable.
1483 return Builder.CreateIntrinsic(Intrinsic::fmuladd, A->getType(),
1484 {A, B, Sum});
1485 }
1486 NumComputeOps += getNumOps(A->getType());
1487 Value *Mul = Builder.CreateFMul(A, B);
1488 return Builder.CreateFAdd(Sum, Mul);
1489 }
1490
1491 NumComputeOps += getNumOps(A->getType());
1492 Value *Mul = Builder.CreateMul(A, B);
1493 return Builder.CreateAdd(Sum, Mul);
1494 }
1495
1496 /// Cache \p Matrix as result of \p Inst and update the uses of \p Inst. For
1497 /// users with shape information, there's nothing to do: they will use the
1498 /// cached value when they are lowered. For other users, \p Matrix is
1499 /// flattened and the uses are updated to use it. Also marks \p Inst for
1500 /// deletion.
1501 void finalizeLowering(Instruction *Inst, MatrixTy Matrix,
1502 IRBuilder<> &Builder) {
1503 auto inserted = Inst2ColumnMatrix.insert(std::make_pair(Inst, Matrix));
1504 (void)inserted;
1505 assert((inserted.second || isa<PHINode>(Inst)) &&
1506 "multiple matrix lowering mapping");
1507
1508 ToRemove.push_back(Inst);
1509 Value *Flattened = nullptr;
1510 for (Use &U : llvm::make_early_inc_range(Inst->uses())) {
1511 if (ShapeMap.contains(U.getUser()))
1512 continue;
1513
1514 if (!Flattened) {
1515 Flattened = Matrix.embedInVector(Builder);
1516 LLVM_DEBUG(
1517 if (Instruction *User = dyn_cast<Instruction>(U.getUser())) dbgs()
1518 << "flattening a " << Matrix.shape() << " matrix:\n"
1519 << *Inst
1520 << "\nbecause we do not have a shape-aware lowering for its "
1521 "user:\n"
1522 << *User << '\n';);
1523 FlattenedMatrices++;
1524 }
1525 U.set(Flattened);
1526 }
1527 }
1528
1529 /// Special case for MatMul lowering. Prevents scalar loads of row-major
1530 /// vectors Lowers to vector reduction add instead of sequential add if
1531 /// reassocation is enabled.
1532 void lowerDotProduct(CallInst *MatMul,
1533 SmallPtrSet<Instruction *, 16> &FusedInsts,
1534 FastMathFlags FMF) {
1535 if (FusedInsts.contains(MatMul) ||
1536 Opts.matrix_default_layout != MatrixLayoutTy::ColumnMajor)
1537 return;
1538 ShapeInfo LShape(MatMul->getArgOperand(2), MatMul->getArgOperand(3));
1539 ShapeInfo RShape(MatMul->getArgOperand(3), MatMul->getArgOperand(4));
1540
1541 if (LShape.NumRows != 1 || RShape.NumColumns != 1) // not a dot product
1542 return;
1543
1544 Value *LHS = MatMul->getArgOperand(0);
1545 Value *RHS = MatMul->getArgOperand(1);
1546
1547 Type *ElementType = cast<FixedVectorType>(LHS->getType())->getElementType();
1548 bool IsIntVec = ElementType->isIntegerTy();
1549
1551
1552 // Floating point reductions require reassocation.
1553 if (!IsIntVec && !FMF.allowReassoc())
1554 return;
1555
1556 auto CanBeFlattened = [](Value *Op) {
1557 if (match(Op, m_BinOp()))
1558 return true;
1559 return match(
1561 m_Load(m_Value()),
1564 m_Value(), m_One())))));
1565 };
1566 // Returns the cost benefit of using \p Op with the dot product lowering. If
1567 // the returned cost is < 0, the argument is cheaper to use in the
1568 // dot-product lowering.
1569 auto GetCostForArg = [this, &CanBeFlattened, CostKind](Value *Op,
1570 unsigned N) {
1571 if (!ShapeMap.contains(Op))
1573
1574 if (!isa<Instruction>(Op))
1575 return InstructionCost(0);
1576
1577 FixedVectorType *VecTy = cast<FixedVectorType>(Op->getType());
1578 Type *EltTy = VecTy->getElementType();
1579
1580 if (!CanBeFlattened(Op)) {
1581 InstructionCost EmbedCost(0);
1582 // Roughly estimate the cost for embedding the columns into a vector.
1583 for (unsigned I = 1; I < N; ++I)
1584 EmbedCost +=
1585 TTI.getShuffleCost(TTI::SK_Splice, FixedVectorType::get(EltTy, 1),
1586 FixedVectorType::get(EltTy, 1), CostKind);
1587 return EmbedCost;
1588 }
1589
1590 if (match(Op, m_BinOp()) && ShapeMap.contains(Op)) {
1591 InstructionCost OriginalCost =
1592 TTI.getArithmeticInstrCost(cast<Instruction>(Op)->getOpcode(),
1593 EltTy, CostKind) *
1594 N;
1595 InstructionCost NewCost = TTI.getArithmeticInstrCost(
1596 cast<Instruction>(Op)->getOpcode(), VecTy, CostKind);
1597 return NewCost - OriginalCost;
1598 }
1599
1601 // The transpose can be skipped for the dot product lowering, roughly
1602 // estimate the savings as the cost of embedding the columns in a
1603 // vector.
1604 InstructionCost EmbedCost(0);
1605 for (unsigned I = 1; I < N; ++I)
1606 EmbedCost -=
1607 TTI.getShuffleCost(TTI::SK_Splice, FixedVectorType::get(EltTy, 1),
1608 FixedVectorType::get(EltTy, 1), CostKind);
1609 return EmbedCost;
1610 }
1611
1612 // Costs for loads.
1613 if (N == 1)
1614 return InstructionCost(0);
1615
1616 return TTI.getMemoryOpCost(Instruction::Load, VecTy, Align(1), 0,
1617 CostKind) -
1618 N * TTI.getMemoryOpCost(Instruction::Load, EltTy, Align(1), 0,
1619 CostKind);
1620 };
1621
1622 // Iterate over LHS and operations feeding LHS and check if it is profitable
1623 // to flatten the visited ops. For each op, we compute the difference
1624 // between the flattened and matrix versions.
1625 SmallPtrSet<Value *, 4> Seen;
1626 SmallVector<Value *> WorkList;
1627 SmallVector<Value *> ToFlatten;
1628 WorkList.push_back(LHS);
1629 InstructionCost LHSCost(0);
1630 while (!WorkList.empty()) {
1631 Value *Op = WorkList.pop_back_val();
1632 if (!Seen.insert(Op).second)
1633 continue;
1634
1635 InstructionCost OpCost = GetCostForArg(Op, LShape.NumColumns);
1636 if (OpCost + LHSCost >= LHSCost)
1637 continue;
1638
1639 LHSCost += OpCost;
1640 ToFlatten.push_back(Op);
1641 if (auto *I = dyn_cast<Instruction>(Op))
1642 WorkList.append(I->op_begin(), I->op_end());
1643 }
1644
1645 // We compare the costs of a vector.reduce.add to sequential add.
1646 int AddOpCode = IsIntVec ? Instruction::Add : Instruction::FAdd;
1647 int MulOpCode = IsIntVec ? Instruction::Mul : Instruction::FMul;
1648 InstructionCost ReductionCost =
1649 TTI.getArithmeticReductionCost(
1650 AddOpCode, cast<FixedVectorType>(LHS->getType()),
1651 IsIntVec ? std::nullopt : std::optional(FMF), CostKind) +
1652 TTI.getArithmeticInstrCost(MulOpCode, LHS->getType(), CostKind);
1653 InstructionCost SequentialAddCost =
1654 TTI.getArithmeticInstrCost(AddOpCode, ElementType, CostKind) *
1655 (LShape.NumColumns - 1) +
1656 TTI.getArithmeticInstrCost(MulOpCode, ElementType, CostKind) *
1657 (LShape.NumColumns);
1658 if ((LHSCost + ReductionCost - SequentialAddCost) > InstructionCost(0))
1659 return;
1660
1661 FusedInsts.insert(MatMul);
1662 IRBuilder<> Builder(MatMul);
1663 auto FlattenArg = [&Builder, &FusedInsts, &CanBeFlattened,
1664 this](Value *Op) {
1665 // Matmul must be the only user of loads because we don't use LowerLoad
1666 // for row vectors (LowerLoad results in scalar loads and shufflevectors
1667 // instead of single vector load).
1668 if (!CanBeFlattened(Op))
1669 return;
1670
1671 if (match(Op, m_BinOp())) {
1672 auto It = ShapeMap.find(Op);
1673 if (It != ShapeMap.end()) {
1674 It->second = It->second.t();
1675 return;
1676 }
1677 }
1678
1679 FusedInsts.insert(cast<Instruction>(Op));
1680 // If vector uses the builtin load, lower to a LoadInst
1681 Value *Arg;
1683 m_Value(Arg)))) {
1684 auto *MatLoad = cast<IntrinsicInst>(Op);
1685 bool IsVolatile = cast<ConstantInt>(MatLoad->getArgOperand(2))->isOne();
1686 // Preserve the volatile flag and alignment of the original load.
1687 Align Alignment = getAlignForIndex(
1688 0, MatLoad->getArgOperand(1),
1689 cast<FixedVectorType>(Op->getType())->getElementType(),
1690 MatLoad->getParamAlign(0));
1691 auto *NewLoad = Builder.CreateAlignedLoad(Op->getType(), Arg, Alignment,
1692 IsVolatile);
1693 Op->replaceAllUsesWith(NewLoad);
1694 eraseFromParentAndRemoveFromShapeMap(cast<Instruction>(Op));
1695 return;
1697 m_Value(Arg)))) {
1698 ToRemove.push_back(cast<Instruction>(Op));
1699 Op->replaceAllUsesWith(Arg);
1700 return;
1701 }
1702 };
1703
1704 for (auto *V : ToFlatten)
1705 FlattenArg(V);
1706
1707 LHS = MatMul->getArgOperand(0);
1708
1709 // Insert mul/fmul and llvm.vector.reduce.fadd
1710 Value *Mul =
1711 IsIntVec ? Builder.CreateMul(LHS, RHS) : Builder.CreateFMul(LHS, RHS);
1712
1713 Value *Result;
1714 if (IsIntVec)
1715 Result = Builder.CreateAddReduce(Mul);
1716 else {
1717 Result = Builder.CreateFAddReduce(
1718 ConstantFP::getNegativeZero(ElementType), Mul);
1719 cast<Instruction>(Result)->setFastMathFlags(FMF);
1720 }
1721
1722 // pack scalar back into a matrix and then replace matmul inst
1724 Result, uint64_t(0));
1725 MatMul->replaceAllUsesWith(Result);
1726 FusedInsts.insert(MatMul);
1727 ToRemove.push_back(MatMul);
1728 }
1729
1730 /// Given \p Remainder iterations of the the matmul inner loop,
1731 /// potentially lower \p Blocksize that is used for the underlying
1732 /// vector.
1733 unsigned capBlockSize(unsigned BlockSize, unsigned Remainder, Type *EltType) {
1734 if (BlockSize <= Remainder)
1735 return BlockSize;
1736
1737 // If the remainder is also a legal type just use it.
1738 auto *VecTy = FixedVectorType::get(EltType, Remainder);
1739 if (TTI.isTypeLegal(VecTy))
1740 return Remainder;
1741
1742 // Similarly, if the vector is small enough that we don't want
1743 // to split further.
1744 if (VecTy->getPrimitiveSizeInBits() <=
1745 Opts.matrix_split_matmul_remainder_over_threshold)
1746 return Remainder;
1747
1748 // Gradually lower the vectorization factor to cover the
1749 // remainder.
1750 do {
1751 BlockSize /= 2;
1752 } while (BlockSize > Remainder);
1753 return BlockSize;
1754 }
1755
1756 /// Compute \p Result += \p A * \p B for input matrices with left-associating
1757 /// addition.
1758 ///
1759 /// We can fold a transpose into the operand that is used to extract scalars.
1760 /// This is the first operands with row-major and the second with
1761 /// column-major. If \p IsScalarMatrixTransposed we assume the appropriate
1762 /// operand is transposed.
1763 void emitMatrixMultiply(MatrixTy &Result, const MatrixTy &A,
1764 const MatrixTy &B, IRBuilder<> &Builder, bool IsTiled,
1765 bool IsScalarMatrixTransposed, FastMathFlags FMF) {
1766 const unsigned VF = std::max<unsigned>(
1767 TTI.getRegisterBitWidth(TargetTransformInfo::RGK_FixedWidthVector)
1768 .getFixedValue() /
1769 Result.getElementType()->getPrimitiveSizeInBits().getFixedValue(),
1770 1U);
1771 unsigned R = Result.getNumRows();
1772 unsigned C = Result.getNumColumns();
1773 unsigned M = A.getNumColumns();
1774
1775 bool IsFP = Result.getElementType()->isFloatingPointTy();
1776 assert(A.isColumnMajor() == B.isColumnMajor() &&
1777 Result.isColumnMajor() == A.isColumnMajor() &&
1778 "operands must agree on matrix layout");
1779 unsigned NumComputeOps = 0;
1780
1781 Builder.setFastMathFlags(FMF);
1782
1783 if (A.isColumnMajor()) {
1784 // Multiply columns from the first operand with scalars from the second
1785 // operand. Then move along the K axes and accumulate the columns. With
1786 // this the adds can be vectorized without reassociation.
1787 for (unsigned J = 0; J < C; ++J) {
1788 unsigned BlockSize = VF;
1789 // If Result is zero, we don't need to accumulate in the K==0 iteration.
1790 bool isSumZero = isa<ConstantAggregateZero>(Result.getColumn(J));
1791
1792 for (unsigned I = 0; I < R; I += BlockSize) {
1793 // Lower block size to make sure we stay within bounds.
1794 BlockSize = capBlockSize(BlockSize, R - I, Result.getElementType());
1795 Value *Sum = IsTiled ? Result.extractVector(I, J, BlockSize, Builder)
1796 : nullptr;
1797 for (unsigned K = 0; K < M; ++K) {
1798 Value *L = A.extractVector(I, K, BlockSize, Builder);
1799 Value *RH = Builder.CreateExtractElement(
1800 B.getColumn(IsScalarMatrixTransposed ? K : J),
1801 IsScalarMatrixTransposed ? J : K);
1802 Value *Splat = Builder.CreateVectorSplat(BlockSize, RH, "splat");
1803 Sum =
1804 createMulAdd(isSumZero && K == 0 ? nullptr : Sum, L, Splat,
1805 IsFP, Builder, FMF.allowContract(), NumComputeOps);
1806 }
1807 Result.setVector(J,
1808 insertVector(Result.getVector(J), I, Sum, Builder));
1809 }
1810 }
1811 } else {
1812 // Multiply rows from the second operand with scalars from the first
1813 // operand. Then move along the K axes and accumulate the rows. With this
1814 // the adds can be vectorized without reassociation.
1815 for (unsigned I = 0; I < R; ++I) {
1816 unsigned BlockSize = VF;
1817 bool isSumZero = isa<ConstantAggregateZero>(Result.getRow(I));
1818 for (unsigned J = 0; J < C; J += BlockSize) {
1819 // Lower the vectorization factor to cover the remainder.
1820 BlockSize = capBlockSize(BlockSize, C - J, Result.getElementType());
1821
1822 Value *Sum = nullptr;
1823 for (unsigned K = 0; K < M; ++K) {
1824 Value *R = B.extractVector(K, J, BlockSize, Builder);
1825 Value *LH = Builder.CreateExtractElement(
1826 A.getVector(IsScalarMatrixTransposed ? K : I),
1827 IsScalarMatrixTransposed ? I : K);
1828 Value *Splat = Builder.CreateVectorSplat(BlockSize, LH, "splat");
1829 Sum =
1830 createMulAdd(isSumZero && K == 0 ? nullptr : Sum, Splat, R,
1831 IsFP, Builder, FMF.allowContract(), NumComputeOps);
1832 }
1833 Result.setVector(I,
1834 insertVector(Result.getVector(I), J, Sum, Builder));
1835 }
1836 }
1837 }
1838 Result.addNumComputeOps(NumComputeOps);
1839 }
1840
1841 /// Ensure that the memory in \p Load does not alias \p Store by potentially
1842 /// copying it to a new location. This new or otherwise the original location
1843 /// is returned.
1844 std::pair<Value *, AllocaInst *>
1845 getNonAliasingPointer(LoadInst *Load, StoreInst *Store, CallInst *MatMul) {
1846 MemoryLocation StoreLoc = MemoryLocation::get(Store);
1847 MemoryLocation LoadLoc = MemoryLocation::get(Load);
1848
1849 // If we can statically determine noalias we're good.
1850 if (AA->isNoAlias(LoadLoc, StoreLoc))
1851 return {Load->getPointerOperand(), nullptr};
1852
1853 // Use an array type for the alloca, to avoid potentially huge alignment
1854 // requirements for large vector types.
1855 auto *VT = cast<FixedVectorType>(Load->getType());
1856 auto *ArrayTy = ArrayType::get(VT->getElementType(), VT->getNumElements());
1857 IRBuilder<> AllocaBuilder(&Func.getEntryBlock().front());
1858 AllocaInst *Alloca =
1859 AllocaBuilder.CreateAlloca(ArrayTy, Load->getPointerAddressSpace());
1860 // The fused loads use the original load's alignment.
1861 Alloca->setAlignment(std::max(Alloca->getAlign(), Load->getAlign()));
1862
1863 // If the pointers are in different address spaces, we cannot compare them
1864 // at runtime. Conservatively copy the load operand to a new buffer.
1865 if (Load->getPointerAddressSpace() != Store->getPointerAddressSpace()) {
1866 IRBuilder<> Builder(MatMul);
1867 Builder.CreateLifetimeStart(Alloca);
1868 Builder.CreateMemCpy(Alloca, Alloca->getAlign(),
1869 Load->getPointerOperand(), Load->getAlign(),
1870 LoadLoc.Size.getValue());
1871 return {Alloca, Alloca};
1872 }
1873
1874 // Create code to check if the memory locations of the Load and Store
1875 // overlap and if they do, copy Load's operand to a new buffer.
1876
1877 // First, create new blocks for 2n part of the check and the copy.
1878 BasicBlock *Check0 = MatMul->getParent();
1879 // FIXME: Use lazy DTU and update SplitBlock to accept a DTU instead of a
1880 // DT. Manually collect dominator tree updates, to avoid unnecessary work,
1881 // as we adjust Check0 and Check1's branches.
1883 for (BasicBlock *Succ : successors(Check0))
1884 DTUpdates.push_back({DT->Delete, Check0, Succ});
1885
1886 BasicBlock *Check1 =
1887 SplitBlock(MatMul->getParent(), MatMul, (DomTreeUpdater *)nullptr, LI,
1888 nullptr, "alias_cont");
1889 BasicBlock *Copy =
1890 SplitBlock(MatMul->getParent(), MatMul, (DomTreeUpdater *)nullptr, LI,
1891 nullptr, "copy");
1892 BasicBlock *Fusion =
1893 SplitBlock(MatMul->getParent(), MatMul, (DomTreeUpdater *)nullptr, LI,
1894 nullptr, "no_alias");
1895
1896 // Check if the loaded memory location begins before the end of the store
1897 // location. If the condition holds, they might overlap, otherwise they are
1898 // guaranteed to not overlap.
1899 IRBuilder<> Builder(MatMul);
1900 Check0->getTerminator()->eraseFromParent();
1901 Builder.SetInsertPoint(Check0);
1902 Value *StoreBegin = Store->getPointerOperand();
1903 Value *StoreEnd = Builder.CreatePtrAddWithUnsignedOffset(
1904 StoreBegin, StoreLoc.Size.getValue(), "store.end",
1906 Value *LoadBegin = Load->getPointerOperand();
1907 CondBrInst *BR1 = Builder.CreateCondBr(
1908 Builder.CreateICmpULT(LoadBegin, StoreEnd), Check1, Fusion);
1910
1911 // Check if the store begins before the end of the load location. If the
1912 // condition holds, they alias, otherwise they are guaranteed to not
1913 // overlap.
1914 Check1->getTerminator()->eraseFromParent();
1915 Builder.SetInsertPoint(Check1->begin());
1916 Builder.CreateLifetimeStart(Alloca);
1917
1918 Value *LoadEnd = Builder.CreatePtrAddWithUnsignedOffset(
1919 LoadBegin, LoadLoc.Size.getValue(), "load.end",
1921 CondBrInst *BR2 = Builder.CreateCondBr(
1922 Builder.CreateICmpULT(StoreBegin, LoadEnd), Copy, Fusion);
1924
1925 // Copy load operand to new alloca.
1926 Builder.SetInsertPoint(Copy->begin());
1927 Builder.CreateMemCpy(Alloca, Alloca->getAlign(), Load->getPointerOperand(),
1928 Load->getAlign(), LoadLoc.Size.getValue());
1929 Builder.SetInsertPoint(Fusion->begin());
1930 PHINode *PHI = Builder.CreatePHI(Load->getPointerOperandType(), 3);
1931 PHI->addIncoming(Load->getPointerOperand(), Check0);
1932 PHI->addIncoming(Load->getPointerOperand(), Check1);
1933 PHI->addIncoming(Alloca, Copy);
1934
1935 // Adjust DT.
1936 DTUpdates.push_back({DT->Insert, Check0, Check1});
1937 DTUpdates.push_back({DT->Insert, Check0, Fusion});
1938 DTUpdates.push_back({DT->Insert, Check1, Copy});
1939 DTUpdates.push_back({DT->Insert, Check1, Fusion});
1940 DT->applyUpdates(DTUpdates);
1941 return {PHI, Alloca};
1942 }
1943
1944 bool isFusionProfitable(CallInst *MatMul) {
1945 if (Opts.force_fuse_matrix)
1946 return true;
1947
1948 ShapeInfo LShape(MatMul->getArgOperand(2), MatMul->getArgOperand(3));
1949 ShapeInfo RShape(MatMul->getArgOperand(3), MatMul->getArgOperand(4));
1950
1951 const unsigned R = LShape.NumRows;
1952 const unsigned C = RShape.NumColumns;
1953 const unsigned M = LShape.NumColumns;
1954 auto *EltType = cast<FixedVectorType>(MatMul->getType())->getElementType();
1955
1956 const unsigned VF = std::max<unsigned>(
1957 TTI.getRegisterBitWidth(TargetTransformInfo::RGK_FixedWidthVector)
1958 .getFixedValue() /
1960 1U);
1961
1962 // Cost model for tiling
1963 //
1964 // For tiling to be beneficial, we need reuse either along the R or
1965 // the C axis. We vectorize along the R axis so that means at least
1966 // 3 elements.
1967 // TODO: Also consider cost of copying if operands alias.
1968 if (R <= VF && C == 1)
1969 return false;
1970 // Then we need enough elements to exceed the number of vector
1971 // registers we have. Note that this is an oversimplification since
1972 // fusing also takes some extra loads which may exceed the number of
1973 // reloads necessary.
1974 unsigned Op0Regs = (R + VF - 1) / VF * M;
1975 unsigned Op1Regs = (M + VF - 1) / VF * C;
1976 return Op0Regs + Op1Regs >
1977 TTI.getNumberOfRegisters(TTI.getRegisterClassForType(true));
1978 }
1979
1980 MatrixTy getZeroMatrix(Type *EltType, unsigned R, unsigned C) {
1981 MatrixTy Res(isColumnMajor());
1982 auto *ColumType = FixedVectorType::get(EltType, R);
1983 for (unsigned I = 0; I < C; ++I)
1984 Res.addVector(ConstantAggregateZero::get(ColumType));
1985 return Res;
1986 }
1987
1988 void createTiledLoops(CallInst *MatMul, Value *LPtr, ShapeInfo LShape,
1989 Value *RPtr, ShapeInfo RShape, StoreInst *Store) {
1990 auto *EltType = cast<FixedVectorType>(MatMul->getType())->getElementType();
1991
1992 // Create the main tiling loop nest.
1993 TileInfo TI(LShape.NumRows, RShape.NumColumns, LShape.NumColumns,
1994 Opts.fuse_matrix_tile_size);
1995 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1996 Instruction *InsertI = cast<Instruction>(MatMul);
1997 BasicBlock *Start = InsertI->getParent();
1998 BasicBlock *End =
1999 SplitBlock(InsertI->getParent(), InsertI, DT, LI, nullptr, "continue");
2000 IRBuilder<> Builder(MatMul);
2002 BasicBlock *InnerBody = TI.CreateTiledLoops(Start, End, Builder, DTU, *LI);
2003
2004 Type *TileVecTy = FixedVectorType::get(MatMul->getType()->getScalarType(),
2005 Opts.fuse_matrix_tile_size);
2006 MatrixTy TileResult(isColumnMajor());
2007 // Insert in the inner loop header.
2008 Builder.SetInsertPoint(TI.KLoop.Header->getTerminator());
2009 Constant *Init = EltType->isFloatingPointTy()
2010 ? ConstantFP::getNegativeZero(TileVecTy)
2011 : Constant::getNullValue(TileVecTy);
2012 // Create PHI nodes for the result columns to accumulate across iterations.
2013 SmallVector<PHINode *, 4> ColumnPhis;
2014 for (unsigned I = 0; I < Opts.fuse_matrix_tile_size; I++) {
2015 auto *Phi = Builder.CreatePHI(TileVecTy, 2, "result.vec." + Twine(I));
2016 Phi->addIncoming(Init, TI.RowLoop.Header->getSingleSuccessor());
2017 TileResult.addVector(Phi);
2018 ColumnPhis.push_back(Phi);
2019 }
2020
2021 // Insert in the inner loop body, which computes
2022 // Res += Load(CurrentRow, K) * Load(K, CurrentColumn)
2023 Builder.SetInsertPoint(InnerBody->getTerminator());
2024 // Load tiles of the operands.
2025 MatrixTy A =
2026 loadMatrix(LPtr, {}, false, LShape, TI.RowLoop.Index, TI.KLoop.Index,
2027 {Opts.fuse_matrix_tile_size, Opts.fuse_matrix_tile_size},
2028 EltType, Builder);
2029 MatrixTy B =
2030 loadMatrix(RPtr, {}, false, RShape, TI.KLoop.Index, TI.ColumnLoop.Index,
2031 {Opts.fuse_matrix_tile_size, Opts.fuse_matrix_tile_size},
2032 EltType, Builder);
2033 emitMatrixMultiply(TileResult, A, B, Builder, true, false,
2034 getFastMathFlags(MatMul));
2035 // Store result after the inner loop is done.
2036 Builder.SetInsertPoint(TI.RowLoop.Latch->getTerminator());
2037 storeMatrix(TileResult, Store->getPointerOperand(), Store->getAlign(),
2038 Store->isVolatile(), {LShape.NumRows, RShape.NumColumns},
2039 TI.RowLoop.Index, TI.ColumnLoop.Index, EltType, Builder);
2040
2041 for (unsigned I = 0; I < TileResult.getNumVectors(); I++)
2042 ColumnPhis[I]->addIncoming(TileResult.getVector(I), TI.KLoop.Latch);
2043
2044 // Force unrolling of a few iterations of the inner loop, to make sure there
2045 // is enough work per iteration.
2046 // FIXME: The unroller should make this decision directly instead, but
2047 // currently the cost-model is not up to the task.
2048 unsigned InnerLoopUnrollCount =
2049 std::min(10u, LShape.NumColumns / Opts.fuse_matrix_tile_size);
2050 addStringMetadataToLoop(LI->getLoopFor(TI.KLoop.Header),
2051 "llvm.loop.unroll.count", InnerLoopUnrollCount);
2052 }
2053
2054 void emitSIMDTiling(CallInst *MatMul, LoadInst *LoadOp0, LoadInst *LoadOp1,
2055 StoreInst *Store,
2056 SmallPtrSetImpl<Instruction *> &FusedInsts) {
2057 assert(Opts.matrix_default_layout == MatrixLayoutTy::ColumnMajor &&
2058 "Tiling only supported for column-major matrixes at the moment!");
2059 if (!isFusionProfitable(MatMul))
2060 return;
2061
2062 ShapeInfo LShape(MatMul->getArgOperand(2), MatMul->getArgOperand(3));
2063 ShapeInfo RShape(MatMul->getArgOperand(3), MatMul->getArgOperand(4));
2064
2065 const unsigned R = LShape.NumRows;
2066 const unsigned C = RShape.NumColumns;
2067 const unsigned M = LShape.NumColumns;
2068 auto *EltType = cast<FixedVectorType>(MatMul->getType())->getElementType();
2069
2070 auto [APtr, AAlloca] = getNonAliasingPointer(LoadOp0, Store, MatMul);
2071 auto [BPtr, BAlloca] = getNonAliasingPointer(LoadOp1, Store, MatMul);
2072 Value *CPtr = Store->getPointerOperand();
2073
2074 // Use loop-based tiling when the number of expected operations exceeds
2075 // threshold.
2076 unsigned NumOps = getNumNativeVectorOps(EltType, R, M, C);
2077 bool UseLoops = (NumOps > Opts.fuse_matrix_loops_threshold) &&
2078 R % Opts.fuse_matrix_tile_size == 0 &&
2079 C % Opts.fuse_matrix_tile_size == 0;
2080 if (UseLoops)
2081 createTiledLoops(MatMul, APtr, LShape, BPtr, RShape, Store);
2082 else {
2083 IRBuilder<> Builder(Store);
2085 for (unsigned J = 0; J < C; J += Opts.fuse_matrix_tile_size)
2086 for (unsigned I = 0; I < R; I += Opts.fuse_matrix_tile_size) {
2087 const unsigned TileR = std::min(R - I, Opts.fuse_matrix_tile_size);
2088 const unsigned TileC = std::min(C - J, Opts.fuse_matrix_tile_size);
2089 MatrixTy Res = getZeroMatrix(EltType, TileR, TileC);
2090
2091 for (unsigned K = 0; K < M; K += Opts.fuse_matrix_tile_size) {
2092 const unsigned TileM = std::min(M - K, Opts.fuse_matrix_tile_size);
2093 MatrixTy A =
2094 loadMatrix(APtr, LoadOp0->getAlign(), LoadOp0->isVolatile(),
2095 LShape, getIndex(APtr, I), getIndex(APtr, K),
2096 {TileR, TileM}, EltType, Builder);
2097 MatrixTy B =
2098 loadMatrix(BPtr, LoadOp1->getAlign(), LoadOp1->isVolatile(),
2099 RShape, getIndex(BPtr, K), getIndex(BPtr, J),
2100 {TileM, TileC}, EltType, Builder);
2101 emitMatrixMultiply(Res, A, B, Builder, true, false,
2102 getFastMathFlags(MatMul));
2103 }
2104 storeMatrix(Res, CPtr, Store->getAlign(), Store->isVolatile(), {R, M},
2105 getIndex(CPtr, I), getIndex(CPtr, J), EltType, Builder);
2106 }
2107 }
2108
2109 // End the lifetime of the allocas used for alias-safe copies.
2110 {
2111 IRBuilder<> Builder(Store);
2112 if (AAlloca)
2113 Builder.CreateLifetimeEnd(AAlloca);
2114 if (BAlloca)
2115 Builder.CreateLifetimeEnd(BAlloca);
2116 }
2117
2118 // Mark eliminated instructions as fused and remove them.
2119 FusedInsts.insert(Store);
2120 FusedInsts.insert(MatMul);
2121 eraseFromParentAndRemoveFromShapeMap(Store);
2122 eraseFromParentAndRemoveFromShapeMap(MatMul);
2123 if (LoadOp0->use_empty()) {
2124 FusedInsts.insert(LoadOp0);
2125 eraseFromParentAndRemoveFromShapeMap(LoadOp0);
2126 }
2127 if (LoadOp1 != LoadOp0 && LoadOp1->use_empty()) {
2128 FusedInsts.insert(LoadOp1);
2129 eraseFromParentAndRemoveFromShapeMap(LoadOp1);
2130 }
2131 }
2132
2133 /// Try to lower matrix multiply chains by fusing operations.
2134 ///
2135 /// Call finalizeLowering on lowered instructions. Instructions that are
2136 /// completely eliminated by fusion are added to \p FusedInsts.
2137 void
2138 LowerMatrixMultiplyFused(CallInst *MatMul,
2139 SmallPtrSetImpl<Instruction *> &FusedInsts,
2140 SmallVector<IntrinsicInst *, 16> &LifetimeEnds) {
2141 if (!Opts.fuse_matrix || !DT || Opts.fuse_matrix_tile_size == 0)
2142 return;
2143
2144 assert(AA && LI && "Analyses should be available");
2145
2146 Value *A = MatMul->getArgOperand(0);
2147 Value *B = MatMul->getArgOperand(1);
2148
2149 // We can fold the transpose into the operand that is used to fetch scalars.
2150 Value *T;
2151 if (Opts.matrix_default_layout == MatrixLayoutTy::ColumnMajor
2154 IRBuilder<> Builder(MatMul);
2155 auto *EltType =
2156 cast<FixedVectorType>(MatMul->getType())->getElementType();
2157 ShapeInfo LShape(MatMul->getArgOperand(2), MatMul->getArgOperand(3));
2158 ShapeInfo RShape(MatMul->getArgOperand(3), MatMul->getArgOperand(4));
2159 const unsigned R = LShape.NumRows;
2160 const unsigned M = LShape.NumColumns;
2161 const unsigned C = RShape.NumColumns;
2162
2163 MatrixTy MA;
2164 MatrixTy MB;
2165
2166 Value *Transpose;
2167 if (Opts.matrix_default_layout == MatrixLayoutTy::ColumnMajor) {
2168 MA = getMatrix(A, ShapeInfo(R, M), Builder);
2169 MB = getMatrix(T, ShapeInfo(C, M), Builder);
2170 Transpose = B;
2171 } else {
2172 MA = getMatrix(T, ShapeInfo(R, M), Builder);
2173 MB = getMatrix(B, ShapeInfo(C, M), Builder);
2174 Transpose = A;
2175 }
2176
2177 // Initialize the output
2178 MatrixTy Result(isColumnMajor(), R, C, EltType);
2179
2180 emitMatrixMultiply(Result, MA, MB, Builder, false, true,
2181 getFastMathFlags(MatMul));
2182
2183 FusedInsts.insert(MatMul);
2184 if (Transpose->hasOneUse()) {
2185 FusedInsts.insert(cast<Instruction>(Transpose));
2186 ToRemove.push_back(cast<Instruction>(Transpose));
2187 // TODO: add a fake entry for the folded instruction so that this is
2188 // included in the expression in the remark.
2189 Inst2ColumnMatrix[Transpose] = MatrixTy(isColumnMajor(), M, C, EltType);
2190 }
2191 finalizeLowering(MatMul, Result, Builder);
2192 return;
2193 }
2194
2195 if (!MatMul->hasOneUse() ||
2196 Opts.matrix_default_layout != MatrixLayoutTy::ColumnMajor)
2197 return;
2198
2199 // Lower {ld, ld} -> matmul -> st chains. No need to call finalizeLowering
2200 // since the single store user will be lowered as part of this.
2201 auto *LoadOp0 = dyn_cast<LoadInst>(A);
2202 auto *LoadOp1 = dyn_cast<LoadInst>(B);
2203 auto *Store = dyn_cast<StoreInst>(*MatMul->user_begin());
2204 if (LoadOp0 && LoadOp1 && Store) {
2205 // The store address must dominate the MatMul instruction, otherwise
2206 // we create invalid IR.
2207 SetVector<Value *> WorkList;
2208 WorkList.insert(Store->getOperand(1));
2209 SmallVector<Instruction *> ToHoist;
2210 for (unsigned I = 0; I != WorkList.size(); ++I) {
2211 Value *Current = WorkList[I];
2212 auto *CurrI = dyn_cast<Instruction>(Current);
2213 if (!CurrI)
2214 continue;
2215 if (isa<PHINode>(CurrI))
2216 return;
2217 if (DT->dominates(CurrI, MatMul))
2218 continue;
2219 if (CurrI->mayHaveSideEffects() || CurrI->mayReadFromMemory())
2220 return;
2221 ToHoist.push_back(CurrI);
2222 WorkList.insert_range(CurrI->operands());
2223 }
2224
2225 sort(ToHoist, [this](Instruction *A, Instruction *B) {
2226 return DT->dominates(A, B);
2227 });
2228 for (Instruction *I : ToHoist)
2229 I->moveBefore(MatMul->getIterator());
2230
2231 // Deal with lifetime.end calls that might be between Load0/Load1 and the
2232 // store. To avoid introducing loads to dead objects (i.e. after the
2233 // lifetime has been termined by @llvm.lifetime.end), either sink them
2234 // after the store if in the same block, or remove the lifetime.end marker
2235 // otherwise. This might pessimize further optimizations, by extending the
2236 // lifetime of the object until the function returns, but should be
2237 // conservatively correct.
2238 MemoryLocation Load0Loc = MemoryLocation::get(LoadOp0);
2239 MemoryLocation Load1Loc = MemoryLocation::get(LoadOp1);
2240 BasicBlock *StoreParent = Store->getParent();
2241 bool FusableOpsInSameBlock = LoadOp0->getParent() == StoreParent &&
2242 LoadOp1->getParent() == StoreParent;
2243 for (unsigned Idx = 0; Idx != LifetimeEnds.size();) {
2244 IntrinsicInst *End = LifetimeEnds[Idx];
2245 llvm::scope_exit Inc([&Idx]() { Idx++; });
2246 // If the lifetime.end is guaranteed to be before the loads or after the
2247 // store, it won't interfere with fusion.
2248 if (DT->dominates(End, LoadOp0) && DT->dominates(End, LoadOp1))
2249 continue;
2250 if (DT->dominates(Store, End))
2251 continue;
2252 // If all fusable ops are in the same block and the lifetime.end is in a
2253 // different block, it won't interfere with fusion.
2254 if (FusableOpsInSameBlock && End->getParent() != StoreParent)
2255 continue;
2256
2257 // If the loads don't alias the lifetime.end, it won't interfere with
2258 // fusion.
2259 MemoryLocation EndLoc = MemoryLocation::getForArgument(End, 0, nullptr);
2260 if (!EndLoc.Ptr)
2261 continue;
2262 if (AA->isNoAlias(Load0Loc, EndLoc) && AA->isNoAlias(Load1Loc, EndLoc))
2263 continue;
2264
2265 // If both lifetime.end and the store are in the same block, extend the
2266 // lifetime until after the store, so the new lifetime covers the loads
2267 // we introduce later.
2268 if (End->getParent() == StoreParent) {
2269 End->moveAfter(Store);
2270 continue;
2271 }
2272
2273 // Otherwise remove the conflicting lifetime.end marker.
2274 ToRemove.push_back(End);
2275 std::swap(LifetimeEnds[Idx], LifetimeEnds.back());
2276 LifetimeEnds.pop_back();
2277 Inc.release();
2278 }
2279
2280 emitSIMDTiling(MatMul, LoadOp0, LoadOp1, Store, FusedInsts);
2281 return;
2282 }
2283 }
2284
2285 /// Lowers llvm.matrix.multiply.
2286 MatrixTy LowerMultiply(CallInst *MatMul, IRBuilder<> &Builder) {
2287 auto *EltType = cast<FixedVectorType>(MatMul->getType())->getElementType();
2288 ShapeInfo LShape(MatMul->getArgOperand(2), MatMul->getArgOperand(3));
2289 ShapeInfo RShape(MatMul->getArgOperand(3), MatMul->getArgOperand(4));
2290
2291 const MatrixTy &Lhs = getMatrix(MatMul->getArgOperand(0), LShape, Builder);
2292 const MatrixTy &Rhs = getMatrix(MatMul->getArgOperand(1), RShape, Builder);
2293 assert(Lhs.getElementType() == Rhs.getElementType() &&
2294 "Matrix multiply argument element types do not match.");
2295
2296 const unsigned R = LShape.NumRows;
2297 const unsigned C = RShape.NumColumns;
2298 assert(LShape.NumColumns == RShape.NumRows);
2299
2300 // Initialize the output
2301 MatrixTy Result(isColumnMajor(), R, C, EltType);
2302 assert(Lhs.getElementType() == Result.getElementType() &&
2303 "Matrix multiply result element type does not match arguments.");
2304
2305 emitMatrixMultiply(Result, Lhs, Rhs, Builder, false, false,
2306 getFastMathFlags(MatMul));
2307 return Result;
2308 }
2309
2310 /// Lowers llvm.matrix.transpose.
2311 MatrixTy LowerTranspose(CallInst *Inst, IRBuilder<> &Builder) {
2312 MatrixTy Result(isColumnMajor());
2313 Value *InputVal = Inst->getArgOperand(0);
2314 FixedVectorType *VectorTy = cast<FixedVectorType>(InputVal->getType());
2315 ShapeInfo ArgShape(Inst->getArgOperand(1), Inst->getArgOperand(2));
2316 MatrixTy InputMatrix = getMatrix(InputVal, ArgShape, Builder);
2317
2318 const unsigned NewNumVecs =
2319 InputMatrix.isColumnMajor() ? ArgShape.NumRows : ArgShape.NumColumns;
2320 const unsigned NewNumElts =
2321 InputMatrix.isColumnMajor() ? ArgShape.NumColumns : ArgShape.NumRows;
2322
2323 for (unsigned I = 0; I < NewNumVecs; ++I) {
2324 // Build a single result vector. First initialize it.
2325 Value *ResultVector = PoisonValue::get(
2326 FixedVectorType::get(VectorTy->getElementType(), NewNumElts));
2327 // Go through the old elements and insert it into the resulting vector.
2328 for (auto J : enumerate(InputMatrix.vectors())) {
2329 Value *Elt = Builder.CreateExtractElement(J.value(), I);
2330 // Row and column indices are transposed.
2331 ResultVector =
2332 Builder.CreateInsertElement(ResultVector, Elt, J.index());
2333 }
2334 Result.addVector(ResultVector);
2335 }
2336
2337 // TODO: Improve estimate of operations needed for transposes. Currently we
2338 // just count the insertelement/extractelement instructions, but do not
2339 // account for later simplifications/combines.
2340 return Result.addNumComputeOps(2 * ArgShape.NumRows * ArgShape.NumColumns)
2341 .addNumExposedTransposes(1);
2342 }
2343
2344 /// Lower load instructions.
2345 MatrixTy VisitLoad(LoadInst *Inst, const ShapeInfo &SI, Value *Ptr,
2346 IRBuilder<> &Builder) {
2347 return LowerLoad(Inst, Ptr, Inst->getAlign(), getIndex(Ptr, getStride(SI)),
2348 Inst->isVolatile(), SI, Builder);
2349 }
2350
2351 MatrixTy VisitStore(StoreInst *Inst, const ShapeInfo &SI, Value *StoredVal,
2352 Value *Ptr, IRBuilder<> &Builder) {
2353 return LowerStore(Inst, StoredVal, Ptr, Inst->getAlign(),
2354 getIndex(Ptr, getStride(SI)), Inst->isVolatile(), SI,
2355 Builder);
2356 }
2357
2358 MatrixTy VisitPHI(PHINode *Inst, const ShapeInfo &SI, IRBuilder<> &Builder) {
2359 auto BlockIP = Inst->getParent()->getFirstInsertionPt();
2360 Builder.SetInsertPoint(BlockIP);
2361 MatrixTy PhiM = getMatrix(Inst, SI, Builder);
2362
2363 // Cache the reshaped columns per incoming block, so that a block listed
2364 // more than once contributes identical incoming values to the new PHIs.
2365 SmallDenseMap<BasicBlock *, MatrixTy> ReshapedIncoming;
2366 for (auto [IncomingV, IncomingB] :
2367 llvm::zip_equal(Inst->incoming_values(), Inst->blocks())) {
2368 // getMatrix() may insert some instructions to help with reshaping. The
2369 // safest place for those is just before the terminator of the incoming
2370 // block. If there's a valid insert point before the def, even better.
2371 Builder.SetInsertPoint(IncomingB->getTerminator());
2372 if (auto *IncomingInst = dyn_cast<Instruction>(IncomingV))
2373 if (auto MaybeIP = IncomingInst->getInsertionPointAfterDef())
2374 Builder.SetInsertPoint(*MaybeIP);
2375
2376 auto [It, Inserted] = ReshapedIncoming.try_emplace(IncomingB);
2377 if (Inserted)
2378 It->second = getMatrix(IncomingV, SI, Builder);
2379 const MatrixTy &OpM = It->second;
2380
2381 for (unsigned VI = 0, VE = PhiM.getNumVectors(); VI != VE; ++VI) {
2382 PHINode *NewPHI = cast<PHINode>(PhiM.getVector(VI));
2383 NewPHI->addIncoming(OpM.getVector(VI), IncomingB);
2384 }
2385 }
2386
2387 // finalizeLowering() may also insert instructions in some cases. The safe
2388 // place for those is at the end of the initial block of PHIs.
2389 Builder.SetInsertPoint(BlockIP);
2390 return PhiM;
2391 }
2392
2393 /// Lower binary operators.
2394 MatrixTy VisitBinaryOperator(BinaryOperator *Inst, const ShapeInfo &SI,
2395 IRBuilder<> &Builder) {
2396 Value *Lhs = Inst->getOperand(0);
2397 Value *Rhs = Inst->getOperand(1);
2398
2399 MatrixTy Result(isColumnMajor());
2400 MatrixTy A = getMatrix(Lhs, SI, Builder);
2401 MatrixTy B = getMatrix(Rhs, SI, Builder);
2402 assert(A.isColumnMajor() == B.isColumnMajor() &&
2403 Result.isColumnMajor() == A.isColumnMajor() &&
2404 "operands must agree on matrix layout");
2405
2406 Builder.setFastMathFlags(getFastMathFlags(Inst));
2407
2408 for (auto [AV, BV] : llvm::zip_equal(A.vectors(), B.vectors()))
2409 Result.addVector(Builder.CreateBinOp(Inst->getOpcode(), AV, BV));
2410
2411 return Result.addNumComputeOps(getNumOps(Result.getVectorTy()) *
2412 Result.getNumVectors());
2413 }
2414
2415 /// Lower unary operators.
2416 MatrixTy VisitUnaryOperator(UnaryOperator *Inst, const ShapeInfo &SI,
2417 IRBuilder<> &Builder) {
2418 Value *Op = Inst->getOperand(0);
2419
2420 MatrixTy Result(isColumnMajor());
2421 MatrixTy M = getMatrix(Op, SI, Builder);
2422
2423 Builder.setFastMathFlags(getFastMathFlags(Inst));
2424
2425 // Helper to perform unary op on vectors.
2426 auto BuildVectorOp = [&Builder, Inst](Value *Op) {
2427 switch (Inst->getOpcode()) {
2428 case Instruction::FNeg:
2429 return Builder.CreateFNeg(Op);
2430 default:
2431 llvm_unreachable("Unsupported unary operator for matrix");
2432 }
2433 };
2434
2435 for (auto *Vector : M.vectors())
2436 Result.addVector(BuildVectorOp(Vector));
2437
2438 return Result.addNumComputeOps(getNumOps(Result.getVectorTy()) *
2439 Result.getNumVectors());
2440 }
2441
2442 /// Lower cast instructions.
2443 MatrixTy VisitCastInstruction(CastInst *Inst, const ShapeInfo &Shape,
2444 IRBuilder<> &Builder) {
2445 Value *Op = Inst->getOperand(0);
2446
2447 MatrixTy Result(isColumnMajor());
2448 MatrixTy M = getMatrix(Op, Shape, Builder);
2449
2450 Builder.setFastMathFlags(getFastMathFlags(Inst));
2451
2452 auto *OrigVTy = cast<VectorType>(Inst->getType());
2453 auto *NewVTy = VectorType::get(OrigVTy->getElementType(),
2454 ElementCount::getFixed(M.getStride()));
2455
2456 for (auto *Vector : M.vectors())
2457 Result.addVector(Builder.CreateCast(Inst->getOpcode(), Vector, NewVTy));
2458
2459 return Result.addNumComputeOps(getNumOps(Result.getVectorTy()) *
2460 Result.getNumVectors());
2461 }
2462
2463 /// Lower selects.
2464 MatrixTy VisitSelectInst(SelectInst *Inst, const ShapeInfo &Shape,
2465 IRBuilder<> &Builder) {
2466 Value *Cond = Inst->getOperand(0);
2467 Value *OpA = Inst->getOperand(1);
2468 Value *OpB = Inst->getOperand(2);
2469
2470 MatrixTy Result(isColumnMajor());
2471 MatrixTy A = getMatrix(OpA, Shape, Builder);
2472 MatrixTy B = getMatrix(OpB, Shape, Builder);
2473
2474 SmallVector<Value*> CondV;
2475 Instruction *MDFrom = nullptr;
2476 if (isa<FixedVectorType>(Cond->getType())) {
2477 MatrixTy C = getMatrix(Cond, Shape, Builder);
2478 llvm::copy(C.vectors(), std::back_inserter(CondV));
2479 } else {
2480 CondV.resize(A.getNumVectors());
2481 llvm::fill(CondV, Cond);
2482 MDFrom = Inst;
2483 }
2484
2485 for (auto [CV, AV, BV] : llvm::zip_equal(CondV, A.vectors(), B.vectors())) {
2486 assert(!(isa<VectorType>(CV->getType()) && static_cast<bool>(MDFrom)) &&
2487 "If we have a vector conditional, we should be propagating "
2488 "profile information.");
2489 Result.addVector(Builder.CreateSelect(CV, AV, BV, "", MDFrom));
2490 }
2491
2492 return Result.addNumComputeOps(getNumOps(Result.getVectorTy()) *
2493 Result.getNumVectors());
2494 }
2495
2496 /// Helper to linearize a matrix expression tree into a string. Currently
2497 /// matrix expressions are linarized by starting at an expression leaf and
2498 /// linearizing bottom up.
2499 struct ExprLinearizer {
2500 unsigned LengthToBreak = 100;
2501 std::string Str;
2502 raw_string_ostream Stream;
2503 unsigned LineLength = 0;
2504 const DataLayout &DL;
2505
2506 /// Mapping from instructions to matrixes. It is used to identify
2507 /// matrix instructions.
2508 const MapVector<Value *, MatrixTy> &Inst2Matrix;
2509
2510 /// Mapping from values to the leaves of all expressions that the value is
2511 /// part of.
2512 const DenseMap<Value *, SmallPtrSet<Value *, 2>> &Shared;
2513
2514 /// Set of matrix expressions in the scope of a given DISubprogram.
2515 const SmallSetVector<Value *, 32> &ExprsInSubprogram;
2516
2517 /// Leaf node of the expression to linearize.
2518 Value *Leaf;
2519
2520 /// Used to keep track of sub-expressions that get reused while linearizing
2521 /// the expression. Re-used sub-expressions are marked as (reused).
2522 SmallPtrSet<Value *, 8> ReusedExprs;
2523
2524 ExprLinearizer(const DataLayout &DL,
2525 const MapVector<Value *, MatrixTy> &Inst2Matrix,
2526 const DenseMap<Value *, SmallPtrSet<Value *, 2>> &Shared,
2527 const SmallSetVector<Value *, 32> &ExprsInSubprogram,
2528 Value *Leaf)
2529 : Stream(Str), DL(DL), Inst2Matrix(Inst2Matrix), Shared(Shared),
2530 ExprsInSubprogram(ExprsInSubprogram), Leaf(Leaf) {}
2531
2532 void indent(unsigned N) {
2533 LineLength += N;
2534 for (unsigned i = 0; i < N; i++)
2535 Stream << " ";
2536 }
2537
2538 void lineBreak() {
2539 Stream << "\n";
2540 LineLength = 0;
2541 }
2542
2543 void maybeIndent(unsigned Indent) {
2544 if (LineLength >= LengthToBreak)
2545 lineBreak();
2546
2547 if (LineLength == 0)
2548 indent(Indent);
2549 }
2550
2551 void write(StringRef S) {
2552 LineLength += S.size();
2553 Stream << S;
2554 }
2555
2556 Value *getUnderlyingObjectThroughLoads(Value *V) {
2557 if (Value *Ptr = getPointerOperand(V))
2558 return getUnderlyingObjectThroughLoads(Ptr);
2559 else if (V->getType()->isPointerTy())
2560 return getUnderlyingObject(V);
2561 return V;
2562 }
2563
2564 /// Returns true if \p V is a matrix value in the given subprogram.
2565 bool isMatrix(Value *V) const { return ExprsInSubprogram.count(V); }
2566
2567 /// If \p V is a matrix value, print its shape as NumRows x NumColumns to
2568 /// \p SS.
2569 void prettyPrintMatrixType(Value *V, raw_string_ostream &SS) {
2570 auto M = Inst2Matrix.find(V);
2571 if (M == Inst2Matrix.end())
2572 SS << "unknown";
2573 else {
2574 SS << M->second.getNumRows();
2575 SS << "x";
2576 SS << M->second.getNumColumns();
2577 }
2578 }
2579
2580 /// Write the called function name. Handles calls to llvm.matrix.*
2581 /// specially: we write the name, followed by the dimensions of the input
2582 /// matrixes, followed by the scalar type name.
2583 void writeFnName(CallInst *CI) {
2584 if (!CI->getCalledFunction())
2585 write("<no called fn>");
2586 else {
2587 StringRef Name = CI->getCalledFunction()->getName();
2588 if (!Name.starts_with("llvm.matrix")) {
2589 write(Name);
2590 return;
2591 }
2592 auto *II = cast<IntrinsicInst>(CI);
2593 write(Intrinsic::getBaseName(II->getIntrinsicID())
2594 .drop_front(StringRef("llvm.matrix.").size()));
2595 write(".");
2596 std::string Tmp;
2597 raw_string_ostream SS(Tmp);
2598
2599 switch (II->getIntrinsicID()) {
2600 case Intrinsic::matrix_multiply:
2601 prettyPrintMatrixType(II->getOperand(0), SS);
2602 SS << ".";
2603 prettyPrintMatrixType(II->getOperand(1), SS);
2604 SS << "." << *II->getType()->getScalarType();
2605 break;
2606 case Intrinsic::matrix_transpose:
2607 prettyPrintMatrixType(II->getOperand(0), SS);
2608 SS << "." << *II->getType()->getScalarType();
2609 break;
2610 case Intrinsic::matrix_column_major_load:
2611 prettyPrintMatrixType(II, SS);
2612 SS << "." << *II->getType()->getScalarType();
2613 break;
2614 case Intrinsic::matrix_column_major_store:
2615 prettyPrintMatrixType(II->getOperand(0), SS);
2616 SS << "." << *II->getOperand(0)->getType()->getScalarType();
2617 break;
2618 default:
2619 llvm_unreachable("Unhandled case");
2620 }
2621 write(Tmp);
2622 }
2623 }
2624
2625 unsigned getNumShapeArgs(CallInst *CI) const {
2626 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
2627 switch (II->getIntrinsicID()) {
2628 case Intrinsic::matrix_multiply:
2629 return 3;
2630 case Intrinsic::matrix_transpose:
2631 return 2;
2632 case Intrinsic::matrix_column_major_load:
2633 case Intrinsic::matrix_column_major_store:
2634 return 3;
2635 default:
2636 return 0;
2637 }
2638 }
2639 return 0;
2640 }
2641
2642 /// Special printing for values: for pointers, we print if they refer to an
2643 /// (function) external address or a stack address, for other values we
2644 /// either print the constant or "scalar"/"matrix" for other values.
2645 void write(Value *V) {
2646 V = getUnderlyingObjectThroughLoads(V);
2647 if (V->getType()->isPointerTy()) {
2648 if (isa<AllocaInst>(V)) {
2649 Stream << "stack addr";
2650 LineLength += StringRef("stack addr").size();
2651 } else {
2652 Stream << "addr";
2653 LineLength += StringRef("addr").size();
2654 }
2655 if (!V->getName().empty()) {
2656 Stream << " %" << V->getName() << "";
2657 LineLength += V->getName().size() + 2;
2658 }
2659 return;
2660 }
2661
2662 std::string Tmp;
2663 raw_string_ostream TmpStream(Tmp);
2664
2665 if (auto *CI = dyn_cast<ConstantInt>(V))
2666 TmpStream << CI->getValue();
2667 else if (isa<Constant>(V))
2668 TmpStream << "constant";
2669 else {
2670 if (isMatrix(V))
2671 TmpStream << "matrix";
2672 else
2673 TmpStream << "scalar";
2674 }
2675 Tmp = std::string(StringRef(Tmp).trim());
2676 LineLength += Tmp.size();
2677 Stream << Tmp;
2678 }
2679
2680 /// Linearize expression \p Expr starting at an indentation of \p Indent.
2681 /// Expressions that are re-used multiple times are prefixed with (reused)
2682 /// at the re-used root instruction.
2683 void linearizeExpr(Value *Expr, unsigned Indent, bool ParentReused,
2684 bool ParentShared) {
2685 auto *I = cast<Instruction>(Expr);
2686 maybeIndent(Indent);
2687 SmallVector<Value *, 8> Ops;
2688
2689 // Is Expr shared with other expression leaves?
2690 bool ExprShared = false;
2691
2692 // Deal with shared subtrees. Mark them as shared, if required.
2693 if (!ParentShared) {
2694 auto SI = Shared.find(Expr);
2695 assert(SI != Shared.end() && SI->second.count(Leaf));
2696
2697 for (Value *S : SI->second) {
2698 if (S == Leaf)
2699 continue;
2700 DebugLoc DL = cast<Instruction>(S)->getDebugLoc();
2701 write("shared with remark at line " + std::to_string(DL.getLine()) +
2702 " column " + std::to_string(DL.getCol()) + " (");
2703 }
2704 ExprShared = SI->second.size() > 1;
2705 }
2706
2707 bool Reused = !ReusedExprs.insert(Expr).second;
2708 if (Reused && !ParentReused)
2709 write("(reused) ");
2710
2711 if (auto *CI = dyn_cast<CallInst>(I)) {
2712 writeFnName(CI);
2713
2714 Ops.append(CI->arg_begin(), CI->arg_end() - getNumShapeArgs(CI));
2715 } else if (isa<BitCastInst>(Expr)) {
2716 // Special case bitcasts, which are used to materialize matrixes from
2717 // non-matrix ops.
2718 write("matrix");
2719 return;
2720 } else {
2721 Ops.append(I->value_op_begin(), I->value_op_end());
2722 write(I->getOpcodeName());
2723 }
2724
2725 write("(");
2726
2727 unsigned NumOpsToBreak = 1;
2729 NumOpsToBreak = 2;
2730
2731 for (Value *Op : Ops) {
2732 if (Ops.size() > NumOpsToBreak)
2733 lineBreak();
2734
2735 maybeIndent(Indent + 1);
2736 if (isMatrix(Op))
2737 linearizeExpr(Op, Indent + 1, Reused, ExprShared);
2738 else
2739 write(Op);
2740 if (Op != Ops.back())
2741 write(", ");
2742 }
2743
2744 write(")");
2745 }
2746
2747 const std::string &getResult() {
2748 return Str;
2749 }
2750 };
2751
2752 /// Generate remarks for matrix operations in a function. To generate remarks
2753 /// for matrix expressions, the following approach is used:
2754 /// 1. Use the inlined-at debug information to group matrix operations to the
2755 /// DISubprograms they are contained in.
2756 /// 2. Collect leaves of matrix expressions (done in
2757 /// RemarkGenerator::getExpressionLeaves) for each subprogram - expression
2758 // mapping. Leaves are lowered matrix instructions without other matrix
2759 // users (like stores) in the current subprogram.
2760 /// 3. For each leaf, create a remark containing a linearizied version of the
2761 /// matrix expression. The expression is linearized by a recursive
2762 /// bottom-up traversal of the matrix operands, starting at a leaf. Note
2763 /// that multiple leaves can share sub-expressions. Shared subexpressions
2764 /// are explicitly marked as shared().
2765 struct RemarkGenerator {
2766 const MapVector<Value *, MatrixTy> &Inst2Matrix;
2767 OptimizationRemarkEmitter &ORE;
2768 Function &Func;
2769 const DataLayout &DL;
2770
2771 RemarkGenerator(const MapVector<Value *, MatrixTy> &Inst2Matrix,
2772 OptimizationRemarkEmitter &ORE, Function &Func)
2773 : Inst2Matrix(Inst2Matrix), ORE(ORE), Func(Func),
2774 DL(Func.getDataLayout()) {}
2775
2776 /// Return all leaves of the expressions in \p ExprsInSubprogram. Those are
2777 /// instructions in Inst2Matrix returning void or without any users in
2778 /// \p ExprsInSubprogram. Currently that should only include stores.
2779 SmallVector<Value *, 4>
2780 getExpressionLeaves(const SmallSetVector<Value *, 32> &ExprsInSubprogram) {
2781 SmallVector<Value *, 4> Leaves;
2782 for (auto *Expr : ExprsInSubprogram)
2783 if (Expr->getType()->isVoidTy() ||
2784 !any_of(Expr->users(), [&ExprsInSubprogram](User *U) {
2785 return ExprsInSubprogram.count(U);
2786 }))
2787 Leaves.push_back(Expr);
2788 return Leaves;
2789 }
2790
2791 /// Recursively traverse expression \p V starting at \p Leaf and add \p Leaf
2792 /// to all visited expressions in \p Shared. Limit the matrix operations to
2793 /// the ones in \p ExprsInSubprogram.
2794 void collectSharedInfo(Value *Leaf, Value *V,
2795 const SmallSetVector<Value *, 32> &ExprsInSubprogram,
2796 DenseMap<Value *, SmallPtrSet<Value *, 2>> &Shared) {
2797
2798 if (!ExprsInSubprogram.count(V))
2799 return;
2800
2801 Shared[V].insert(Leaf);
2802
2803 for (Value *Op : cast<Instruction>(V)->operand_values())
2804 collectSharedInfo(Leaf, Op, ExprsInSubprogram, Shared);
2805 }
2806
2807 /// Calculate the number of exclusive and shared op counts for expression
2808 /// starting at \p V. Expressions used multiple times are counted once.
2809 /// Limit the matrix operations to the ones in \p ExprsInSubprogram.
2810 std::pair<OpInfoTy, OpInfoTy>
2811 sumOpInfos(Value *Root, SmallPtrSetImpl<Value *> &ReusedExprs,
2812 const SmallSetVector<Value *, 32> &ExprsInSubprogram,
2813 DenseMap<Value *, SmallPtrSet<Value *, 2>> &Shared) const {
2814 if (!ExprsInSubprogram.count(Root))
2815 return {};
2816
2817 // Already counted this expression. Stop.
2818 if (!ReusedExprs.insert(Root).second)
2819 return {};
2820
2821 OpInfoTy SharedCount;
2822 OpInfoTy Count;
2823
2824 auto I = Shared.find(Root);
2825 auto CM = Inst2Matrix.find(Root);
2826 if (I->second.size() == 1)
2827 Count = CM->second.getOpInfo();
2828 else
2829 SharedCount = CM->second.getOpInfo();
2830
2831 for (Value *Op : cast<Instruction>(Root)->operand_values()) {
2832 auto C = sumOpInfos(Op, ReusedExprs, ExprsInSubprogram, Shared);
2833 Count += C.first;
2834 SharedCount += C.second;
2835 }
2836 return {Count, SharedCount};
2837 }
2838
2839 void emitRemarks() {
2840 if (!ORE.allowExtraAnalysis(DEBUG_TYPE))
2841 return;
2842
2843 // Map matrix operations to their containting subprograms, by traversing
2844 // the inlinedAt chain. If the function does not have a DISubprogram, we
2845 // only map them to the containing function.
2846 MapVector<DISubprogram *, SmallVector<Value *, 8>> Subprog2Exprs;
2847 for (const auto &KV : Inst2Matrix) {
2848 if (Func.getSubprogram()) {
2849 auto *I = cast<Instruction>(KV.first);
2850 DILocation *Context = I->getDebugLoc();
2851 while (Context) {
2852 Subprog2Exprs[getSubprogram(Context->getScope())].push_back(
2853 KV.first);
2854 Context = DebugLoc(Context).getInlinedAt();
2855 }
2856 } else {
2857 Subprog2Exprs[nullptr].push_back(KV.first);
2858 }
2859 }
2860 for (auto &KV : Subprog2Exprs) {
2861 SmallSetVector<Value *, 32> ExprsInSubprogram(KV.second.begin(),
2862 KV.second.end());
2863 auto Leaves = getExpressionLeaves(ExprsInSubprogram);
2864
2865 DenseMap<Value *, SmallPtrSet<Value *, 2>> Shared;
2866 for (Value *Leaf : Leaves)
2867 collectSharedInfo(Leaf, Leaf, ExprsInSubprogram, Shared);
2868
2869 // Generate remarks for each leaf.
2870 for (auto *L : Leaves) {
2871
2872 DebugLoc Loc = cast<Instruction>(L)->getDebugLoc();
2873 DILocation *Context = cast<Instruction>(L)->getDebugLoc();
2874 while (Context) {
2875 if (getSubprogram(Context->getScope()) == KV.first) {
2876 Loc = Context;
2877 break;
2878 }
2879 Context = DebugLoc(Context).getInlinedAt();
2880 }
2881
2882 SmallPtrSet<Value *, 8> ReusedExprs;
2883 OpInfoTy Counts, SharedCounts;
2884 std::tie(Counts, SharedCounts) =
2885 sumOpInfos(L, ReusedExprs, ExprsInSubprogram, Shared);
2886
2887 OptimizationRemark Rem(DEBUG_TYPE, "matrix-lowered", Loc,
2889
2890 Rem << "Lowered with ";
2891 Rem << ore::NV("NumStores", Counts.NumStores) << " stores, "
2892 << ore::NV("NumLoads", Counts.NumLoads) << " loads, "
2893 << ore::NV("NumComputeOps", Counts.NumComputeOps)
2894 << " compute ops, "
2895 << ore::NV("NumExposedTransposes", Counts.NumExposedTransposes)
2896 << " exposed transposes";
2897
2898 if (SharedCounts.NumStores > 0 || SharedCounts.NumLoads > 0 ||
2899 SharedCounts.NumComputeOps > 0) {
2900 Rem << ",\nadditionally "
2901 << ore::NV("NumStores", SharedCounts.NumStores) << " stores, "
2902 << ore::NV("NumLoads", SharedCounts.NumLoads) << " loads, "
2903 << ore::NV("NumFPOps", SharedCounts.NumComputeOps)
2904 << " compute ops"
2905 << " are shared with other expressions";
2906 }
2907
2908 Rem << ("\n" + linearize(L, Shared, ExprsInSubprogram, DL));
2909 ORE.emit(Rem);
2910 }
2911 }
2912 }
2913
2914 std::string
2915 linearize(Value *L,
2916 const DenseMap<Value *, SmallPtrSet<Value *, 2>> &Shared,
2917 const SmallSetVector<Value *, 32> &ExprsInSubprogram,
2918 const DataLayout &DL) {
2919 ExprLinearizer Lin(DL, Inst2Matrix, Shared, ExprsInSubprogram, L);
2920 Lin.linearizeExpr(L, 0, false, false);
2921 return Lin.getResult();
2922 }
2923 };
2924};
2925} // namespace
2926
2929 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
2930
2931 const ScalarOptions &Opts = getScalarOptions(F);
2932 LowerMatrixIntrinsics LMT(Opts, F, TTI, Minimal ? nullptr : &AM);
2933 if (LMT.Visit()) {
2935 if (!Minimal) {
2936 PA.preserve<LoopAnalysis>();
2938 }
2939 return PA;
2940 }
2941 return PreservedAnalyses::all();
2942}
2943
2945 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
2946 static_cast<PassInfoMixin<LowerMatrixIntrinsicsPass> *>(this)->printPipeline(
2947 OS, MapClassName2PassName);
2948 OS << '<';
2949 if (Minimal)
2950 OS << "minimal";
2951 OS << '>';
2952}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
AMDGPU Register Bank Select
Rewrite undef for PHI
static const Function * getParent(const Value *V)
BitTracker BT
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:702
Hexagon Common GEP
static Type * getIndexType(Value *In)
hexagon Hexagon specific predictive commoning for HVX vectors
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv users
Definition IVUsers.cpp:48
const size_t AbstractManglingParser< Derived, Alloc >::NumOps
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition Lint.cpp:550
Live Register Matrix
static DISubprogram * getSubprogram(DIScope *Scope)
Helper function to either return Scope, if it is a subprogram or the attached subprogram for a local ...
static auto m_AnyAdd(const LTy &L, const RTy &R)
Match any add operation (fp or integer).
static bool isShapePreserving(Value *V)
static auto m_AnyMul(const LTy &L, const RTy &R)
Match any mul operation (fp or integer).
static bool isSplat(Value *V)
Return true if V is a splat of a value (which is used when multiplying a matrix with a scalar).
static std::optional< ShapeInfo > computeShapeInfoForInst(Instruction *I, const DenseMap< Value *, ShapeInfo > &ShapeMap)
Return the ShapeInfo for the result of I, it it can be determined.
#define DEBUG_TYPE
static iterator_range< Use * > getShapedOperandsForInst(Instruction *I)
Return an iterator over the operands of I that should share shape information with I.
static Value * computeVectorAddr(Value *BasePtr, Value *VecIdx, Value *Stride, unsigned NumElements, Type *EltType, IRBuilder<> &Builder)
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
#define T
#define T1
uint64_t IntrinsicInst * II
PowerPC Reduce CR logical Operation
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file contains the declarations for profiling metadata utility functions.
SmallVector< MachineOperand, 4 > Cond
static unsigned getFastMathFlags(const MachineInstr &I, const SPIRVSubtarget &ST)
static Value * extractVector(IRBuilderTy &IRB, Value *V, unsigned BeginIndex, unsigned EndIndex, const Twine &Name)
Definition SROA.cpp:2696
static Value * insertVector(IRBuilderTy &IRB, Value *Old, Value *V, unsigned BeginIndex, const Twine &Name)
Definition SROA.cpp:2717
This file contains some templates that are useful if you are working with the STL at all.
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
static SymbolRef::Type getType(const Symbol *Sym)
Definition TapiFile.cpp:39
static const int BlockSize
Definition TarWriter.cpp:33
This pass exposes codegen information to IR-level passes.
static SDValue LowerStore(SDValue Op, const X86Subtarget &Subtarget, SelectionDAG &DAG)
static SDValue LowerLoad(SDValue Op, const X86Subtarget &Subtarget, SelectionDAG &DAG)
Value * RHS
Value * LHS
Align getAlign() const
Return the alignment of the memory that is being allocated by the instruction.
void setAlignment(Align Align)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
iterator begin()
Instruction iterator methods.
Definition BasicBlock.h:440
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
reverse_iterator rbegin()
Definition BasicBlock.h:456
InstListType::reverse_iterator reverse_iterator
Definition BasicBlock.h:172
reverse_iterator rend()
Definition BasicBlock.h:458
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
BinaryOps getOpcode() const
Definition InstrTypes.h:409
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
MaybeAlign getParamAlign(unsigned ArgNo) const
Extract the alignment for a call or parameter (0=unknown).
Value * getArgOperand(unsigned i) const
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition InstrTypes.h:674
static LLVM_ABI ConstantAggregateZero * get(Type *Ty)
static ConstantFP * getNegativeZero(Type *Ty)
Definition Constants.h:458
LLVM_ABI DISubprogram * getSubprogram() const
Get the subprogram for this scope.
Base class for scope-like contexts.
Subprogram description. Uses SubclassData1.
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:766
iterator end()
Definition DenseMap.h:686
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Definition DenseMap.h:856
Analysis pass which computes a DominatorTree.
Definition Dominators.h:241
static constexpr ElementCount getFixed(ScalarTy MinVal)
Definition TypeSize.h:306
void setAllowContract(bool B=true)
Definition FMF.h:90
bool allowReassoc() const
Flag queries.
Definition FMF.h:64
bool allowContract() const
Definition FMF.h:69
unsigned getNumElements() const
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
Definition Type.cpp:838
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition Function.h:247
bool isIntrinsic() const
isIntrinsic - Returns true if the function's name starts with "llvm.".
Definition Function.h:252
static GEPNoWrapFlags inBounds()
static GEPNoWrapFlags noUnsignedWrap()
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition IRBuilder.h:2474
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Definition IRBuilder.h:2748
Value * CreatePtrAddWithUnsignedOffset(Value *Ptr, uint64_t Offset, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())
Create a ptradd with an unsigned constant offset.
Definition IRBuilder.h:2113
LLVM_ABI CallInst * CreateLifetimeStart(Value *Ptr)
Create a lifetime.start intrinsic.
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition IRBuilder.h:2736
LLVM_ABI CallInst * CreateLifetimeEnd(Value *Ptr)
Create a lifetime.end intrinsic.
LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)
Definition IRBuilder.h:1940
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Definition IRBuilder.h:2215
CallInst * CreateMemCpy(Value *Dst, MaybeAlign DstAlign, Value *Src, MaybeAlign SrcAlign, uint64_t Size, bool isVolatile=false, const AAMDNodes &AAInfo=AAMDNodes())
Create and insert a memcpy between the specified pointers.
Definition IRBuilder.h:657
CondBrInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
Definition IRBuilder.h:1218
Value * CreateFAdd(Value *L, Value *R, const Twine &Name="", MDNode *FPMD=nullptr)
Definition IRBuilder.h:1638
LLVM_ABI Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="", MDNode *FPMathTag=nullptr, FMFSource FMFSource={})
Definition IRBuilder.h:2360
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Definition IRBuilder.h:289
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Definition IRBuilder.h:2021
LLVM_ABI Value * CreateBinaryIntrinsic(Intrinsic::ID ID, Value *LHS, Value *RHS, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with 2 operands which is mangled on the first type.
void disableGEPCanonicalization()
Disable canonicalization of getelementptr instructions to ptradd form.
Definition IRBuilder.h:351
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition IRBuilder.h:2626
LLVM_ABI Value * CreateAddReduce(Value *Src)
Create a vector int add reduction intrinsic of the source vector.
ConstantInt * getIntN(unsigned N, uint64_t C)
Get a constant N-bit value, zero extended from a 64-bit value.
Definition IRBuilder.h:481
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition IRBuilder.h:2770
LLVM_ABI Value * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > OverloadTypes, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="", ArrayRef< OperandBundleDef > OpBundles={}, function_ref< void(CallInst *)> SetFn=[](CallInst *) {})
Variant to create a possibly constant-folded intrinsic.
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition IRBuilder.h:1424
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition IRBuilder.h:1733
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition IRBuilder.h:197
StoreInst * CreateAlignedStore(Value *Val, Value *Ptr, MaybeAlign Align, bool isVolatile=false)
Definition IRBuilder.h:1959
LLVM_ABI Value * CreateFAddReduce(Value *Acc, Value *Src)
Create a sequential vector fadd reduction intrinsic of the source vector.
Value * CreateFMul(Value *L, Value *R, const Twine &Name="", MDNode *FPMD=nullptr)
Definition IRBuilder.h:1676
Value * CreateFNeg(Value *V, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition IRBuilder.h:1841
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition IRBuilder.h:1458
LLVM_ABI Value * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *Op, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2990
static InstructionCost getInvalid(CostType Val=0)
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
iterator_range< user_iterator > users()
LLVM_ABI FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
user_iterator user_begin()
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Align getAlign() const
Return the alignment of the access that is being performed.
TypeSize getValue() const
Analysis pass that exposes the LoopInfo for a function.
Definition LoopInfo.h:598
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
CallInst * CreateMatrixTranspose(Value *Matrix, unsigned Rows, unsigned Columns, const Twine &Name="")
Create a llvm.matrix.transpose call, transposing Matrix with Rows rows and Columns columns.
CallInst * CreateMatrixMultiply(Value *LHS, Value *RHS, unsigned LHSRows, unsigned LHSColumns, unsigned RHSColumns, const Twine &Name="")
Create a llvm.matrix.multiply call, multiplying matrixes LHS and RHS.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
const Value * Ptr
The address of the start of the location.
static LLVM_ABI MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition Analysis.h:133
size_type size() const
Determine the number of elements in the SetVector.
Definition SetVector.h:103
void insert_range(Range &&R)
Definition SetVector.h:182
size_type count(const_arg_type key) const
Count the number of elements of a given key in the SetVector.
Definition SetVector.h:268
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition SetVector.h:157
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void resize(size_type N)
void push_back(const T &Elt)
Align getAlign() const
bool isVolatile() const
Return true if this is a store to a volatile memory location.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
StringRef drop_front(size_t N=1) const
Return a StringRef equal to 'this' but with the first N elements dropped.
Definition StringRef.h:627
constexpr size_t size() const
Get the string size.
Definition StringRef.h:144
Analysis pass providing the TargetTransformInfo.
TargetCostKind
The kind of cost model.
@ TCK_RecipThroughput
Reciprocal throughput.
@ SK_Splice
Concatenates elements from the first input vector with elements of the second input vector.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition Type.h:354
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition Type.h:370
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition Type.cpp:187
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
Definition Type.h:186
bool isVoidTy() const
Return true if this is 'void'.
Definition Type.h:141
UnaryOps getOpcode() const
Definition InstrTypes.h:163
Value * getOperand(unsigned i) const
Definition User.h:207
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition Value.h:441
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:548
iterator_range< user_iterator > users()
Definition Value.h:428
bool use_empty() const
Definition Value.h:348
iterator_range< use_iterator > uses()
Definition Value.h:382
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:314
Type * getElementType() const
constexpr ScalarTy getFixedValue() const
Definition TypeSize.h:201
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
Definition ilist_node.h:34
self_iterator getIterator()
Definition ilist_node.h:123
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char IsVolatile[]
Key for Kernel::Arg::Metadata::mIsVolatile.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
LLVM_ABI StringRef getBaseName(ID id)
Return the LLVM name for an intrinsic, without encoded types for overloading, such as "llvm....
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
TwoOps_match< ValueOpTy, PointerOpTy, Instruction::Store > m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp)
Matches StoreInst.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
auto m_BinOp()
Match an arbitrary binary operation and ignore it.
auto m_Value()
Match an arbitrary value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
OneOps_match< OpTy, Instruction::Load > m_Load(const OpTy &Op)
Matches LoadInst.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
ElementType
The element type of an SRV or UAV resource.
Definition DXILABI.h:68
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< PhiNode * > Phi
Definition RDFGraph.h:390
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition STLExtras.h:316
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
@ Offset
Definition DWP.cpp:577
void fill(R &&Range, T &&Value)
Provide wrappers to std::fill which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1775
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition STLExtras.h:1685
detail::zippy< detail::zip_first, T, U, Args... > zip_equal(T &&t, U &&u, Args &&...args)
zip iterator that assumes that all iteratees have the same length.
Definition STLExtras.h:856
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
Definition STLExtras.h:2575
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
bool operator!=(uint64_t V1, const APInt &V2)
Definition APInt.h:2139
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt & operator+=(DynamicAPInt &A, int64_t B)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:649
LLVM_ABI Value * concatenateVectors(IRBuilderBase &Builder, ArrayRef< Value * > Vecs)
Concatenate a list of vectors.
const ScalarOptions & getScalarOptions(const LLVMContext &C)
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
LLVM_ABI void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1652
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)
Definition Error.cpp:163
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ABI raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
TargetTransformInfo TTI
@ Mul
Product of integers.
@ Add
Sum of integers.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
Definition InstrProf.h:145
DWARFExpression::Operation Op
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
OutputIt copy(R &&Range, OutputIt Out)
Definition STLExtras.h:1901
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
Definition Alignment.h:206
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
AAResults AliasAnalysis
Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.
LLVM_ABI Error write(DWPWriter &Out, ArrayRef< std::string > Inputs, OnCuIndexOverflow OverflowOptValue, Dwarf64StrOffsetsPromotion StrOffsetsOptValue, raw_pwrite_stream *OS=nullptr)
Definition DWP.cpp:746
LLVM_ABI llvm::SmallVector< int, 16 > createSequentialMask(unsigned Start, unsigned NumInts, unsigned NumUndefs)
Create a sequential shuffle mask.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:881
#define N