MLIR  17.0.0git
Utils.cpp
Go to the documentation of this file.
1 //===- Utils.cpp ---- Misc utilities for analysis -------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements miscellaneous analysis routines for non-loop IR
10 // structures.
11 //
12 //===----------------------------------------------------------------------===//
13 
22 #include "mlir/IR/IntegerSet.h"
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include <optional>
27 
28 #define DEBUG_TYPE "analysis-utils"
29 
30 using namespace mlir;
31 using namespace presburger;
32 
33 using llvm::SmallDenseMap;
34 
36  auto *currOp = op.getParentOp();
37  AffineForOp currAffineForOp;
38  // Traverse up the hierarchy collecting all 'affine.for' operation while
39  // skipping over 'affine.if' operations.
40  while (currOp) {
41  if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(currOp))
42  loops->push_back(currAffineForOp);
43  currOp = currOp->getParentOp();
44  }
45  std::reverse(loops->begin(), loops->end());
46 }
47 
50  ops->clear();
51  Operation *currOp = op.getParentOp();
52 
53  // Traverse up the hierarchy collecting all `affine.for`, `affine.if`, and
54  // affine.parallel operations.
55  while (currOp) {
56  if (isa<AffineIfOp, AffineForOp, AffineParallelOp>(currOp))
57  ops->push_back(currOp);
58  currOp = currOp->getParentOp();
59  }
60  std::reverse(ops->begin(), ops->end());
61 }
62 
63 // Populates 'cst' with FlatAffineValueConstraints which represent original
64 // domain of the loop bounds that define 'ivs'.
67  assert(!ivs.empty() && "Cannot have a slice without its IVs");
68  cst = FlatAffineValueConstraints(/*numDims=*/ivs.size(), /*numSymbols=*/0,
69  /*numLocals=*/0, ivs);
70  for (Value iv : ivs) {
71  AffineForOp loop = getForInductionVarOwner(iv);
72  assert(loop && "Expected affine for");
73  if (failed(cst.addAffineForOpDomain(loop)))
74  return failure();
75  }
76  return success();
77 }
78 
79 // Populates 'cst' with FlatAffineValueConstraints which represent slice bounds.
82  assert(!lbOperands.empty());
83  // Adds src 'ivs' as dimension variables in 'cst'.
84  unsigned numDims = ivs.size();
85  // Adds operands (dst ivs and symbols) as symbols in 'cst'.
86  unsigned numSymbols = lbOperands[0].size();
87 
88  SmallVector<Value, 4> values(ivs);
89  // Append 'ivs' then 'operands' to 'values'.
90  values.append(lbOperands[0].begin(), lbOperands[0].end());
91  *cst = FlatAffineValueConstraints(numDims, numSymbols, 0, values);
92 
93  // Add loop bound constraints for values which are loop IVs of the destination
94  // of fusion and equality constraints for symbols which are constants.
95  for (unsigned i = numDims, end = values.size(); i < end; ++i) {
96  Value value = values[i];
97  assert(cst->containsVar(value) && "value expected to be present");
98  if (isValidSymbol(value)) {
99  // Check if the symbol is a constant.
100  if (auto cOp = value.getDefiningOp<arith::ConstantIndexOp>())
101  cst->addBound(BoundType::EQ, value, cOp.value());
102  } else if (auto loop = getForInductionVarOwner(value)) {
103  if (failed(cst->addAffineForOpDomain(loop)))
104  return failure();
105  }
106  }
107 
108  // Add slices bounds on 'ivs' using maps 'lbs'/'ubs' with 'lbOperands[0]'
109  LogicalResult ret = cst->addSliceBounds(ivs, lbs, ubs, lbOperands[0]);
110  assert(succeeded(ret) &&
111  "should not fail as we never have semi-affine slice maps");
112  (void)ret;
113  return success();
114 }
115 
116 // Clears state bounds and operand state.
118  lbs.clear();
119  ubs.clear();
120  lbOperands.clear();
121  ubOperands.clear();
122 }
123 
125  llvm::errs() << "\tIVs:\n";
126  for (Value iv : ivs)
127  llvm::errs() << "\t\t" << iv << "\n";
128 
129  llvm::errs() << "\tLBs:\n";
130  for (auto en : llvm::enumerate(lbs)) {
131  llvm::errs() << "\t\t" << en.value() << "\n";
132  llvm::errs() << "\t\tOperands:\n";
133  for (Value lbOp : lbOperands[en.index()])
134  llvm::errs() << "\t\t\t" << lbOp << "\n";
135  }
136 
137  llvm::errs() << "\tUBs:\n";
138  for (auto en : llvm::enumerate(ubs)) {
139  llvm::errs() << "\t\t" << en.value() << "\n";
140  llvm::errs() << "\t\tOperands:\n";
141  for (Value ubOp : ubOperands[en.index()])
142  llvm::errs() << "\t\t\t" << ubOp << "\n";
143  }
144 }
145 
146 /// Fast check to determine if the computation slice is maximal. Returns true if
147 /// each slice dimension maps to an existing dst dimension and both the src
148 /// and the dst loops for those dimensions have the same bounds. Returns false
149 /// if both the src and the dst loops don't have the same bounds. Returns
150 /// std::nullopt if none of the above can be proven.
151 std::optional<bool> ComputationSliceState::isSliceMaximalFastCheck() const {
152  assert(lbs.size() == ubs.size() && !lbs.empty() && !ivs.empty() &&
153  "Unexpected number of lbs, ubs and ivs in slice");
154 
155  for (unsigned i = 0, end = lbs.size(); i < end; ++i) {
156  AffineMap lbMap = lbs[i];
157  AffineMap ubMap = ubs[i];
158 
159  // Check if this slice is just an equality along this dimension.
160  if (!lbMap || !ubMap || lbMap.getNumResults() != 1 ||
161  ubMap.getNumResults() != 1 ||
162  lbMap.getResult(0) + 1 != ubMap.getResult(0) ||
163  // The condition above will be true for maps describing a single
164  // iteration (e.g., lbMap.getResult(0) = 0, ubMap.getResult(0) = 1).
165  // Make sure we skip those cases by checking that the lb result is not
166  // just a constant.
167  lbMap.getResult(0).isa<AffineConstantExpr>())
168  return std::nullopt;
169 
170  // Limited support: we expect the lb result to be just a loop dimension for
171  // now.
172  AffineDimExpr result = lbMap.getResult(0).dyn_cast<AffineDimExpr>();
173  if (!result)
174  return std::nullopt;
175 
176  // Retrieve dst loop bounds.
177  AffineForOp dstLoop =
178  getForInductionVarOwner(lbOperands[i][result.getPosition()]);
179  if (!dstLoop)
180  return std::nullopt;
181  AffineMap dstLbMap = dstLoop.getLowerBoundMap();
182  AffineMap dstUbMap = dstLoop.getUpperBoundMap();
183 
184  // Retrieve src loop bounds.
185  AffineForOp srcLoop = getForInductionVarOwner(ivs[i]);
186  assert(srcLoop && "Expected affine for");
187  AffineMap srcLbMap = srcLoop.getLowerBoundMap();
188  AffineMap srcUbMap = srcLoop.getUpperBoundMap();
189 
190  // Limited support: we expect simple src and dst loops with a single
191  // constant component per bound for now.
192  if (srcLbMap.getNumResults() != 1 || srcUbMap.getNumResults() != 1 ||
193  dstLbMap.getNumResults() != 1 || dstUbMap.getNumResults() != 1)
194  return std::nullopt;
195 
196  AffineExpr srcLbResult = srcLbMap.getResult(0);
197  AffineExpr dstLbResult = dstLbMap.getResult(0);
198  AffineExpr srcUbResult = srcUbMap.getResult(0);
199  AffineExpr dstUbResult = dstUbMap.getResult(0);
200  if (!srcLbResult.isa<AffineConstantExpr>() ||
201  !srcUbResult.isa<AffineConstantExpr>() ||
202  !dstLbResult.isa<AffineConstantExpr>() ||
203  !dstUbResult.isa<AffineConstantExpr>())
204  return std::nullopt;
205 
206  // Check if src and dst loop bounds are the same. If not, we can guarantee
207  // that the slice is not maximal.
208  if (srcLbResult != dstLbResult || srcUbResult != dstUbResult ||
209  srcLoop.getStep() != dstLoop.getStep())
210  return false;
211  }
212 
213  return true;
214 }
215 
216 /// Returns true if it is deterministically verified that the original iteration
217 /// space of the slice is contained within the new iteration space that is
218 /// created after fusing 'this' slice into its destination.
219 std::optional<bool> ComputationSliceState::isSliceValid() {
220  // Fast check to determine if the slice is valid. If the following conditions
221  // are verified to be true, slice is declared valid by the fast check:
222  // 1. Each slice loop is a single iteration loop bound in terms of a single
223  // destination loop IV.
224  // 2. Loop bounds of the destination loop IV (from above) and those of the
225  // source loop IV are exactly the same.
226  // If the fast check is inconclusive or false, we proceed with a more
227  // expensive analysis.
228  // TODO: Store the result of the fast check, as it might be used again in
229  // `canRemoveSrcNodeAfterFusion`.
230  std::optional<bool> isValidFastCheck = isSliceMaximalFastCheck();
231  if (isValidFastCheck && *isValidFastCheck)
232  return true;
233 
234  // Create constraints for the source loop nest using which slice is computed.
235  FlatAffineValueConstraints srcConstraints;
236  // TODO: Store the source's domain to avoid computation at each depth.
237  if (failed(getSourceAsConstraints(srcConstraints))) {
238  LLVM_DEBUG(llvm::dbgs() << "Unable to compute source's domain\n");
239  return std::nullopt;
240  }
241  // As the set difference utility currently cannot handle symbols in its
242  // operands, validity of the slice cannot be determined.
243  if (srcConstraints.getNumSymbolVars() > 0) {
244  LLVM_DEBUG(llvm::dbgs() << "Cannot handle symbols in source domain\n");
245  return std::nullopt;
246  }
247  // TODO: Handle local vars in the source domains while using the 'projectOut'
248  // utility below. Currently, aligning is not done assuming that there will be
249  // no local vars in the source domain.
250  if (srcConstraints.getNumLocalVars() != 0) {
251  LLVM_DEBUG(llvm::dbgs() << "Cannot handle locals in source domain\n");
252  return std::nullopt;
253  }
254 
255  // Create constraints for the slice loop nest that would be created if the
256  // fusion succeeds.
257  FlatAffineValueConstraints sliceConstraints;
258  if (failed(getAsConstraints(&sliceConstraints))) {
259  LLVM_DEBUG(llvm::dbgs() << "Unable to compute slice's domain\n");
260  return std::nullopt;
261  }
262 
263  // Projecting out every dimension other than the 'ivs' to express slice's
264  // domain completely in terms of source's IVs.
265  sliceConstraints.projectOut(ivs.size(),
266  sliceConstraints.getNumVars() - ivs.size());
267 
268  LLVM_DEBUG(llvm::dbgs() << "Domain of the source of the slice:\n");
269  LLVM_DEBUG(srcConstraints.dump());
270  LLVM_DEBUG(llvm::dbgs() << "Domain of the slice if this fusion succeeds "
271  "(expressed in terms of its source's IVs):\n");
272  LLVM_DEBUG(sliceConstraints.dump());
273 
274  // TODO: Store 'srcSet' to avoid recalculating for each depth.
275  PresburgerSet srcSet(srcConstraints);
276  PresburgerSet sliceSet(sliceConstraints);
277  PresburgerSet diffSet = sliceSet.subtract(srcSet);
278 
279  if (!diffSet.isIntegerEmpty()) {
280  LLVM_DEBUG(llvm::dbgs() << "Incorrect slice\n");
281  return false;
282  }
283  return true;
284 }
285 
286 /// Returns true if the computation slice encloses all the iterations of the
287 /// sliced loop nest. Returns false if it does not. Returns std::nullopt if it
288 /// cannot determine if the slice is maximal or not.
289 std::optional<bool> ComputationSliceState::isMaximal() const {
290  // Fast check to determine if the computation slice is maximal. If the result
291  // is inconclusive, we proceed with a more expensive analysis.
292  std::optional<bool> isMaximalFastCheck = isSliceMaximalFastCheck();
293  if (isMaximalFastCheck)
294  return isMaximalFastCheck;
295 
296  // Create constraints for the src loop nest being sliced.
297  FlatAffineValueConstraints srcConstraints(/*numDims=*/ivs.size(),
298  /*numSymbols=*/0,
299  /*numLocals=*/0, ivs);
300  for (Value iv : ivs) {
301  AffineForOp loop = getForInductionVarOwner(iv);
302  assert(loop && "Expected affine for");
303  if (failed(srcConstraints.addAffineForOpDomain(loop)))
304  return std::nullopt;
305  }
306 
307  // Create constraints for the slice using the dst loop nest information. We
308  // retrieve existing dst loops from the lbOperands.
309  SmallVector<Value> consumerIVs;
310  for (Value lbOp : lbOperands[0])
311  if (getForInductionVarOwner(lbOp))
312  consumerIVs.push_back(lbOp);
313 
314  // Add empty IV Values for those new loops that are not equalities and,
315  // therefore, are not yet materialized in the IR.
316  for (int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)
317  consumerIVs.push_back(Value());
318 
319  FlatAffineValueConstraints sliceConstraints(/*numDims=*/consumerIVs.size(),
320  /*numSymbols=*/0,
321  /*numLocals=*/0, consumerIVs);
322 
323  if (failed(sliceConstraints.addDomainFromSliceMaps(lbs, ubs, lbOperands[0])))
324  return std::nullopt;
325 
326  if (srcConstraints.getNumDimVars() != sliceConstraints.getNumDimVars())
327  // Constraint dims are different. The integer set difference can't be
328  // computed so we don't know if the slice is maximal.
329  return std::nullopt;
330 
331  // Compute the difference between the src loop nest and the slice integer
332  // sets.
333  PresburgerSet srcSet(srcConstraints);
334  PresburgerSet sliceSet(sliceConstraints);
335  PresburgerSet diffSet = srcSet.subtract(sliceSet);
336  return diffSet.isIntegerEmpty();
337 }
338 
339 unsigned MemRefRegion::getRank() const {
340  return memref.getType().cast<MemRefType>().getRank();
341 }
342 
344  SmallVectorImpl<int64_t> *shape, std::vector<SmallVector<int64_t, 4>> *lbs,
345  SmallVectorImpl<int64_t> *lbDivisors) const {
346  auto memRefType = memref.getType().cast<MemRefType>();
347  unsigned rank = memRefType.getRank();
348  if (shape)
349  shape->reserve(rank);
350 
351  assert(rank == cst.getNumDimVars() && "inconsistent memref region");
352 
353  // Use a copy of the region constraints that has upper/lower bounds for each
354  // memref dimension with static size added to guard against potential
355  // over-approximation from projection or union bounding box. We may not add
356  // this on the region itself since they might just be redundant constraints
357  // that will need non-trivials means to eliminate.
358  FlatAffineValueConstraints cstWithShapeBounds(cst);
359  for (unsigned r = 0; r < rank; r++) {
360  cstWithShapeBounds.addBound(BoundType::LB, r, 0);
361  int64_t dimSize = memRefType.getDimSize(r);
362  if (ShapedType::isDynamic(dimSize))
363  continue;
364  cstWithShapeBounds.addBound(BoundType::UB, r, dimSize - 1);
365  }
366 
367  // Find a constant upper bound on the extent of this memref region along each
368  // dimension.
369  int64_t numElements = 1;
370  int64_t diffConstant;
371  int64_t lbDivisor;
372  for (unsigned d = 0; d < rank; d++) {
374  std::optional<int64_t> diff =
375  cstWithShapeBounds.getConstantBoundOnDimSize64(d, &lb, &lbDivisor);
376  if (diff.has_value()) {
377  diffConstant = *diff;
378  assert(diffConstant >= 0 && "Dim size bound can't be negative");
379  assert(lbDivisor > 0);
380  } else {
381  // If no constant bound is found, then it can always be bound by the
382  // memref's dim size if the latter has a constant size along this dim.
383  auto dimSize = memRefType.getDimSize(d);
384  if (dimSize == ShapedType::kDynamic)
385  return std::nullopt;
386  diffConstant = dimSize;
387  // Lower bound becomes 0.
388  lb.resize(cstWithShapeBounds.getNumSymbolVars() + 1, 0);
389  lbDivisor = 1;
390  }
391  numElements *= diffConstant;
392  if (lbs) {
393  lbs->push_back(lb);
394  assert(lbDivisors && "both lbs and lbDivisor or none");
395  lbDivisors->push_back(lbDivisor);
396  }
397  if (shape) {
398  shape->push_back(diffConstant);
399  }
400  }
401  return numElements;
402 }
403 
405  AffineMap &ubMap) const {
406  assert(pos < cst.getNumDimVars() && "invalid position");
407  auto memRefType = memref.getType().cast<MemRefType>();
408  unsigned rank = memRefType.getRank();
409 
410  assert(rank == cst.getNumDimVars() && "inconsistent memref region");
411 
412  auto boundPairs = cst.getLowerAndUpperBound(
413  pos, /*offset=*/0, /*num=*/rank, cst.getNumDimAndSymbolVars(),
414  /*localExprs=*/{}, memRefType.getContext());
415  lbMap = boundPairs.first;
416  ubMap = boundPairs.second;
417  assert(lbMap && "lower bound for a region must exist");
418  assert(ubMap && "upper bound for a region must exist");
419  assert(lbMap.getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
420  assert(ubMap.getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
421 }
422 
424  assert(memref == other.memref);
425  return cst.unionBoundingBox(*other.getConstraints());
426 }
427 
428 /// Computes the memory region accessed by this memref with the region
429 /// represented as constraints symbolic/parametric in 'loopDepth' loops
430 /// surrounding opInst and any additional Function symbols.
431 // For example, the memref region for this load operation at loopDepth = 1 will
432 // be as below:
433 //
434 // affine.for %i = 0 to 32 {
435 // affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
436 // load %A[%ii]
437 // }
438 // }
439 //
440 // region: {memref = %A, write = false, {%i <= m0 <= %i + 7} }
441 // The last field is a 2-d FlatAffineValueConstraints symbolic in %i.
442 //
443 // TODO: extend this to any other memref dereferencing ops
444 // (dma_start, dma_wait).
446  const ComputationSliceState *sliceState,
447  bool addMemRefDimBounds) {
448  assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
449  "affine read/write op expected");
450 
451  MemRefAccess access(op);
452  memref = access.memref;
453  write = access.isStore();
454 
455  unsigned rank = access.getRank();
456 
457  LLVM_DEBUG(llvm::dbgs() << "MemRefRegion::compute: " << *op
458  << "\ndepth: " << loopDepth << "\n";);
459 
460  // 0-d memrefs.
461  if (rank == 0) {
463  getAffineIVs(*op, ivs);
464  assert(loopDepth <= ivs.size() && "invalid 'loopDepth'");
465  // The first 'loopDepth' IVs are symbols for this region.
466  ivs.resize(loopDepth);
467  // A 0-d memref has a 0-d region.
468  cst = FlatAffineValueConstraints(rank, loopDepth, /*numLocals=*/0, ivs);
469  return success();
470  }
471 
472  // Build the constraints for this region.
473  AffineValueMap accessValueMap;
474  access.getAccessMap(&accessValueMap);
475  AffineMap accessMap = accessValueMap.getAffineMap();
476 
477  unsigned numDims = accessMap.getNumDims();
478  unsigned numSymbols = accessMap.getNumSymbols();
479  unsigned numOperands = accessValueMap.getNumOperands();
480  // Merge operands with slice operands.
481  SmallVector<Value, 4> operands;
482  operands.resize(numOperands);
483  for (unsigned i = 0; i < numOperands; ++i)
484  operands[i] = accessValueMap.getOperand(i);
485 
486  if (sliceState != nullptr) {
487  operands.reserve(operands.size() + sliceState->lbOperands[0].size());
488  // Append slice operands to 'operands' as symbols.
489  for (auto extraOperand : sliceState->lbOperands[0]) {
490  if (!llvm::is_contained(operands, extraOperand)) {
491  operands.push_back(extraOperand);
492  numSymbols++;
493  }
494  }
495  }
496  // We'll first associate the dims and symbols of the access map to the dims
497  // and symbols resp. of cst. This will change below once cst is
498  // fully constructed out.
499  cst = FlatAffineValueConstraints(numDims, numSymbols, 0, operands);
500 
501  // Add equality constraints.
502  // Add inequalities for loop lower/upper bounds.
503  for (unsigned i = 0; i < numDims + numSymbols; ++i) {
504  auto operand = operands[i];
505  if (auto affineFor = getForInductionVarOwner(operand)) {
506  // Note that cst can now have more dimensions than accessMap if the
507  // bounds expressions involve outer loops or other symbols.
508  // TODO: rewrite this to use getInstIndexSet; this way
509  // conditionals will be handled when the latter supports it.
510  if (failed(cst.addAffineForOpDomain(affineFor)))
511  return failure();
512  } else if (auto parallelOp = getAffineParallelInductionVarOwner(operand)) {
513  if (failed(cst.addAffineParallelOpDomain(parallelOp)))
514  return failure();
515  } else if (isValidSymbol(operand)) {
516  // Check if the symbol is a constant.
517  Value symbol = operand;
518  if (auto constVal = getConstantIntValue(symbol))
519  cst.addBound(BoundType::EQ, symbol, constVal.value());
520  } else {
521  LLVM_DEBUG(llvm::dbgs() << "unknown affine dimensional value");
522  return failure();
523  }
524  }
525 
526  // Add lower/upper bounds on loop IVs using bounds from 'sliceState'.
527  if (sliceState != nullptr) {
528  // Add dim and symbol slice operands.
529  for (auto operand : sliceState->lbOperands[0]) {
530  cst.addInductionVarOrTerminalSymbol(operand);
531  }
532  // Add upper/lower bounds from 'sliceState' to 'cst'.
533  LogicalResult ret =
534  cst.addSliceBounds(sliceState->ivs, sliceState->lbs, sliceState->ubs,
535  sliceState->lbOperands[0]);
536  assert(succeeded(ret) &&
537  "should not fail as we never have semi-affine slice maps");
538  (void)ret;
539  }
540 
541  // Add access function equalities to connect loop IVs to data dimensions.
542  if (failed(cst.composeMap(&accessValueMap))) {
543  op->emitError("getMemRefRegion: compose affine map failed");
544  LLVM_DEBUG(accessValueMap.getAffineMap().dump());
545  return failure();
546  }
547 
548  // Set all variables appearing after the first 'rank' variables as
549  // symbolic variables - so that the ones corresponding to the memref
550  // dimensions are the dimensional variables for the memref region.
551  cst.setDimSymbolSeparation(cst.getNumDimAndSymbolVars() - rank);
552 
553  // Eliminate any loop IVs other than the outermost 'loopDepth' IVs, on which
554  // this memref region is symbolic.
555  SmallVector<Value, 4> enclosingIVs;
556  getAffineIVs(*op, enclosingIVs);
557  assert(loopDepth <= enclosingIVs.size() && "invalid loop depth");
558  enclosingIVs.resize(loopDepth);
560  cst.getValues(cst.getNumDimVars(), cst.getNumDimAndSymbolVars(), &vars);
561  for (Value var : vars) {
562  if ((isAffineInductionVar(var)) && !llvm::is_contained(enclosingIVs, var)) {
563  cst.projectOut(var);
564  }
565  }
566 
567  // Project out any local variables (these would have been added for any
568  // mod/divs).
569  cst.projectOut(cst.getNumDimAndSymbolVars(), cst.getNumLocalVars());
570 
571  // Constant fold any symbolic variables.
572  cst.constantFoldVarRange(/*pos=*/cst.getNumDimVars(),
573  /*num=*/cst.getNumSymbolVars());
574 
575  assert(cst.getNumDimVars() == rank && "unexpected MemRefRegion format");
576 
577  // Add upper/lower bounds for each memref dimension with static size
578  // to guard against potential over-approximation from projection.
579  // TODO: Support dynamic memref dimensions.
580  if (addMemRefDimBounds) {
581  auto memRefType = memref.getType().cast<MemRefType>();
582  for (unsigned r = 0; r < rank; r++) {
583  cst.addBound(BoundType::LB, /*pos=*/r, /*value=*/0);
584  if (memRefType.isDynamicDim(r))
585  continue;
586  cst.addBound(BoundType::UB, /*pos=*/r, memRefType.getDimSize(r) - 1);
587  }
588  }
589  cst.removeTrivialRedundancy();
590 
591  LLVM_DEBUG(llvm::dbgs() << "Memory region:\n");
592  LLVM_DEBUG(cst.dump());
593  return success();
594 }
595 
596 std::optional<int64_t>
598  auto elementType = memRefType.getElementType();
599 
600  unsigned sizeInBits;
601  if (elementType.isIntOrFloat()) {
602  sizeInBits = elementType.getIntOrFloatBitWidth();
603  } else if (auto vectorType = elementType.dyn_cast<VectorType>()) {
604  if (vectorType.getElementType().isIntOrFloat())
605  sizeInBits =
606  vectorType.getElementTypeBitWidth() * vectorType.getNumElements();
607  else
608  return std::nullopt;
609  } else {
610  return std::nullopt;
611  }
612  return llvm::divideCeil(sizeInBits, 8);
613 }
614 
615 // Returns the size of the region.
616 std::optional<int64_t> MemRefRegion::getRegionSize() {
617  auto memRefType = memref.getType().cast<MemRefType>();
618 
619  if (!memRefType.getLayout().isIdentity()) {
620  LLVM_DEBUG(llvm::dbgs() << "Non-identity layout map not yet supported\n");
621  return false;
622  }
623 
624  // Indices to use for the DmaStart op.
625  // Indices for the original memref being DMAed from/to.
626  SmallVector<Value, 4> memIndices;
627  // Indices for the faster buffer being DMAed into/from.
628  SmallVector<Value, 4> bufIndices;
629 
630  // Compute the extents of the buffer.
631  std::optional<int64_t> numElements = getConstantBoundingSizeAndShape();
632  if (!numElements) {
633  LLVM_DEBUG(llvm::dbgs() << "Dynamic shapes not yet supported\n");
634  return std::nullopt;
635  }
636  auto eltSize = getMemRefIntOrFloatEltSizeInBytes(memRefType);
637  if (!eltSize)
638  return std::nullopt;
639  return *eltSize * *numElements;
640 }
641 
642 /// Returns the size of memref data in bytes if it's statically shaped,
643 /// std::nullopt otherwise. If the element of the memref has vector type, takes
644 /// into account size of the vector as well.
645 // TODO: improve/complete this when we have target data.
646 std::optional<uint64_t>
647 mlir::getIntOrFloatMemRefSizeInBytes(MemRefType memRefType) {
648  if (!memRefType.hasStaticShape())
649  return std::nullopt;
650  auto elementType = memRefType.getElementType();
651  if (!elementType.isIntOrFloat() && !elementType.isa<VectorType>())
652  return std::nullopt;
653 
654  auto sizeInBytes = getMemRefIntOrFloatEltSizeInBytes(memRefType);
655  if (!sizeInBytes)
656  return std::nullopt;
657  for (unsigned i = 0, e = memRefType.getRank(); i < e; i++) {
658  sizeInBytes = *sizeInBytes * memRefType.getDimSize(i);
659  }
660  return sizeInBytes;
661 }
662 
663 template <typename LoadOrStoreOp>
664 LogicalResult mlir::boundCheckLoadOrStoreOp(LoadOrStoreOp loadOrStoreOp,
665  bool emitError) {
666  static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,
667  AffineWriteOpInterface>::value,
668  "argument should be either a AffineReadOpInterface or a "
669  "AffineWriteOpInterface");
670 
671  Operation *op = loadOrStoreOp.getOperation();
672  MemRefRegion region(op->getLoc());
673  if (failed(region.compute(op, /*loopDepth=*/0, /*sliceState=*/nullptr,
674  /*addMemRefDimBounds=*/false)))
675  return success();
676 
677  LLVM_DEBUG(llvm::dbgs() << "Memory region");
678  LLVM_DEBUG(region.getConstraints()->dump());
679 
680  bool outOfBounds = false;
681  unsigned rank = loadOrStoreOp.getMemRefType().getRank();
682 
683  // For each dimension, check for out of bounds.
684  for (unsigned r = 0; r < rank; r++) {
685  FlatAffineValueConstraints ucst(*region.getConstraints());
686 
687  // Intersect memory region with constraint capturing out of bounds (both out
688  // of upper and out of lower), and check if the constraint system is
689  // feasible. If it is, there is at least one point out of bounds.
690  SmallVector<int64_t, 4> ineq(rank + 1, 0);
691  int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
692  // TODO: handle dynamic dim sizes.
693  if (dimSize == -1)
694  continue;
695 
696  // Check for overflow: d_i >= memref dim size.
697  ucst.addBound(BoundType::LB, r, dimSize);
698  outOfBounds = !ucst.isEmpty();
699  if (outOfBounds && emitError) {
700  loadOrStoreOp.emitOpError()
701  << "memref out of upper bound access along dimension #" << (r + 1);
702  }
703 
704  // Check for a negative index.
705  FlatAffineValueConstraints lcst(*region.getConstraints());
706  std::fill(ineq.begin(), ineq.end(), 0);
707  // d_i <= -1;
708  lcst.addBound(BoundType::UB, r, -1);
709  outOfBounds = !lcst.isEmpty();
710  if (outOfBounds && emitError) {
711  loadOrStoreOp.emitOpError()
712  << "memref out of lower bound access along dimension #" << (r + 1);
713  }
714  }
715  return failure(outOfBounds);
716 }
717 
718 // Explicitly instantiate the template so that the compiler knows we need them!
719 template LogicalResult
720 mlir::boundCheckLoadOrStoreOp(AffineReadOpInterface loadOp, bool emitError);
721 template LogicalResult
722 mlir::boundCheckLoadOrStoreOp(AffineWriteOpInterface storeOp, bool emitError);
723 
724 // Returns in 'positions' the Block positions of 'op' in each ancestor
725 // Block from the Block containing operation, stopping at 'limitBlock'.
726 static void findInstPosition(Operation *op, Block *limitBlock,
727  SmallVectorImpl<unsigned> *positions) {
728  Block *block = op->getBlock();
729  while (block != limitBlock) {
730  // FIXME: This algorithm is unnecessarily O(n) and should be improved to not
731  // rely on linear scans.
732  int instPosInBlock = std::distance(block->begin(), op->getIterator());
733  positions->push_back(instPosInBlock);
734  op = block->getParentOp();
735  block = op->getBlock();
736  }
737  std::reverse(positions->begin(), positions->end());
738 }
739 
740 // Returns the Operation in a possibly nested set of Blocks, where the
741 // position of the operation is represented by 'positions', which has a
742 // Block position for each level of nesting.
744  unsigned level, Block *block) {
745  unsigned i = 0;
746  for (auto &op : *block) {
747  if (i != positions[level]) {
748  ++i;
749  continue;
750  }
751  if (level == positions.size() - 1)
752  return &op;
753  if (auto childAffineForOp = dyn_cast<AffineForOp>(op))
754  return getInstAtPosition(positions, level + 1,
755  childAffineForOp.getBody());
756 
757  for (auto &region : op.getRegions()) {
758  for (auto &b : region)
759  if (auto *ret = getInstAtPosition(positions, level + 1, &b))
760  return ret;
761  }
762  return nullptr;
763  }
764  return nullptr;
765 }
766 
767 // Adds loop IV bounds to 'cst' for loop IVs not found in 'ivs'.
770  for (unsigned i = 0, e = cst->getNumDimVars(); i < e; ++i) {
771  auto value = cst->getValue(i);
772  if (ivs.count(value) == 0) {
773  assert(isAffineForInductionVar(value));
774  auto loop = getForInductionVarOwner(value);
775  if (failed(cst->addAffineForOpDomain(loop)))
776  return failure();
777  }
778  }
779  return success();
780 }
781 
782 /// Returns the innermost common loop depth for the set of operations in 'ops'.
783 // TODO: Move this to LoopUtils.
785  ArrayRef<Operation *> ops, SmallVectorImpl<AffineForOp> *surroundingLoops) {
786  unsigned numOps = ops.size();
787  assert(numOps > 0 && "Expected at least one operation");
788 
789  std::vector<SmallVector<AffineForOp, 4>> loops(numOps);
790  unsigned loopDepthLimit = std::numeric_limits<unsigned>::max();
791  for (unsigned i = 0; i < numOps; ++i) {
792  getAffineForIVs(*ops[i], &loops[i]);
793  loopDepthLimit =
794  std::min(loopDepthLimit, static_cast<unsigned>(loops[i].size()));
795  }
796 
797  unsigned loopDepth = 0;
798  for (unsigned d = 0; d < loopDepthLimit; ++d) {
799  unsigned i;
800  for (i = 1; i < numOps; ++i) {
801  if (loops[i - 1][d] != loops[i][d])
802  return loopDepth;
803  }
804  if (surroundingLoops)
805  surroundingLoops->push_back(loops[i - 1][d]);
806  ++loopDepth;
807  }
808  return loopDepth;
809 }
810 
811 /// Computes in 'sliceUnion' the union of all slice bounds computed at
812 /// 'loopDepth' between all dependent pairs of ops in 'opsA' and 'opsB', and
813 /// then verifies if it is valid. Returns 'SliceComputationResult::Success' if
814 /// union was computed correctly, an appropriate failure otherwise.
817  unsigned loopDepth, unsigned numCommonLoops,
818  bool isBackwardSlice,
819  ComputationSliceState *sliceUnion) {
820  // Compute the union of slice bounds between all pairs in 'opsA' and
821  // 'opsB' in 'sliceUnionCst'.
822  FlatAffineValueConstraints sliceUnionCst;
823  assert(sliceUnionCst.getNumDimAndSymbolVars() == 0);
824  std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
825  for (auto *i : opsA) {
826  MemRefAccess srcAccess(i);
827  for (auto *j : opsB) {
828  MemRefAccess dstAccess(j);
829  if (srcAccess.memref != dstAccess.memref)
830  continue;
831  // Check if 'loopDepth' exceeds nesting depth of src/dst ops.
832  if ((!isBackwardSlice && loopDepth > getNestingDepth(i)) ||
833  (isBackwardSlice && loopDepth > getNestingDepth(j))) {
834  LLVM_DEBUG(llvm::dbgs() << "Invalid loop depth\n");
836  }
837 
838  bool readReadAccesses = isa<AffineReadOpInterface>(srcAccess.opInst) &&
839  isa<AffineReadOpInterface>(dstAccess.opInst);
840  FlatAffineValueConstraints dependenceConstraints;
841  // Check dependence between 'srcAccess' and 'dstAccess'.
843  srcAccess, dstAccess, /*loopDepth=*/numCommonLoops + 1,
844  &dependenceConstraints, /*dependenceComponents=*/nullptr,
845  /*allowRAR=*/readReadAccesses);
846  if (result.value == DependenceResult::Failure) {
847  LLVM_DEBUG(llvm::dbgs() << "Dependence check failed\n");
849  }
851  continue;
852  dependentOpPairs.emplace_back(i, j);
853 
854  // Compute slice bounds for 'srcAccess' and 'dstAccess'.
855  ComputationSliceState tmpSliceState;
856  mlir::getComputationSliceState(i, j, &dependenceConstraints, loopDepth,
857  isBackwardSlice, &tmpSliceState);
858 
859  if (sliceUnionCst.getNumDimAndSymbolVars() == 0) {
860  // Initialize 'sliceUnionCst' with the bounds computed in previous step.
861  if (failed(tmpSliceState.getAsConstraints(&sliceUnionCst))) {
862  LLVM_DEBUG(llvm::dbgs()
863  << "Unable to compute slice bound constraints\n");
865  }
866  assert(sliceUnionCst.getNumDimAndSymbolVars() > 0);
867  continue;
868  }
869 
870  // Compute constraints for 'tmpSliceState' in 'tmpSliceCst'.
871  FlatAffineValueConstraints tmpSliceCst;
872  if (failed(tmpSliceState.getAsConstraints(&tmpSliceCst))) {
873  LLVM_DEBUG(llvm::dbgs()
874  << "Unable to compute slice bound constraints\n");
876  }
877 
878  // Align coordinate spaces of 'sliceUnionCst' and 'tmpSliceCst' if needed.
879  if (!sliceUnionCst.areVarsAlignedWithOther(tmpSliceCst)) {
880 
881  // Pre-constraint var alignment: record loop IVs used in each constraint
882  // system.
883  SmallPtrSet<Value, 8> sliceUnionIVs;
884  for (unsigned k = 0, l = sliceUnionCst.getNumDimVars(); k < l; ++k)
885  sliceUnionIVs.insert(sliceUnionCst.getValue(k));
886  SmallPtrSet<Value, 8> tmpSliceIVs;
887  for (unsigned k = 0, l = tmpSliceCst.getNumDimVars(); k < l; ++k)
888  tmpSliceIVs.insert(tmpSliceCst.getValue(k));
889 
890  sliceUnionCst.mergeAndAlignVarsWithOther(/*offset=*/0, &tmpSliceCst);
891 
892  // Post-constraint var alignment: add loop IV bounds missing after
893  // var alignment to constraint systems. This can occur if one constraint
894  // system uses an loop IV that is not used by the other. The call
895  // to unionBoundingBox below expects constraints for each Loop IV, even
896  // if they are the unsliced full loop bounds added here.
897  if (failed(addMissingLoopIVBounds(sliceUnionIVs, &sliceUnionCst)))
899  if (failed(addMissingLoopIVBounds(tmpSliceIVs, &tmpSliceCst)))
901  }
902  // Compute union bounding box of 'sliceUnionCst' and 'tmpSliceCst'.
903  if (sliceUnionCst.getNumLocalVars() > 0 ||
904  tmpSliceCst.getNumLocalVars() > 0 ||
905  failed(sliceUnionCst.unionBoundingBox(tmpSliceCst))) {
906  LLVM_DEBUG(llvm::dbgs()
907  << "Unable to compute union bounding box of slice bounds\n");
909  }
910  }
911  }
912 
913  // Empty union.
914  if (sliceUnionCst.getNumDimAndSymbolVars() == 0)
916 
917  // Gather loops surrounding ops from loop nest where slice will be inserted.
919  for (auto &dep : dependentOpPairs) {
920  ops.push_back(isBackwardSlice ? dep.second : dep.first);
921  }
922  SmallVector<AffineForOp, 4> surroundingLoops;
923  unsigned innermostCommonLoopDepth =
924  getInnermostCommonLoopDepth(ops, &surroundingLoops);
925  if (loopDepth > innermostCommonLoopDepth) {
926  LLVM_DEBUG(llvm::dbgs() << "Exceeds max loop depth\n");
928  }
929 
930  // Store 'numSliceLoopIVs' before converting dst loop IVs to dims.
931  unsigned numSliceLoopIVs = sliceUnionCst.getNumDimVars();
932 
933  // Convert any dst loop IVs which are symbol variables to dim variables.
934  sliceUnionCst.convertLoopIVSymbolsToDims();
935  sliceUnion->clearBounds();
936  sliceUnion->lbs.resize(numSliceLoopIVs, AffineMap());
937  sliceUnion->ubs.resize(numSliceLoopIVs, AffineMap());
938 
939  // Get slice bounds from slice union constraints 'sliceUnionCst'.
940  sliceUnionCst.getSliceBounds(/*offset=*/0, numSliceLoopIVs,
941  opsA[0]->getContext(), &sliceUnion->lbs,
942  &sliceUnion->ubs);
943 
944  // Add slice bound operands of union.
945  SmallVector<Value, 4> sliceBoundOperands;
946  sliceUnionCst.getValues(numSliceLoopIVs,
947  sliceUnionCst.getNumDimAndSymbolVars(),
948  &sliceBoundOperands);
949 
950  // Copy src loop IVs from 'sliceUnionCst' to 'sliceUnion'.
951  sliceUnion->ivs.clear();
952  sliceUnionCst.getValues(0, numSliceLoopIVs, &sliceUnion->ivs);
953 
954  // Set loop nest insertion point to block start at 'loopDepth'.
955  sliceUnion->insertPoint =
956  isBackwardSlice
957  ? surroundingLoops[loopDepth - 1].getBody()->begin()
958  : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());
959 
960  // Give each bound its own copy of 'sliceBoundOperands' for subsequent
961  // canonicalization.
962  sliceUnion->lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
963  sliceUnion->ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
964 
965  // Check if the slice computed is valid. Return success only if it is verified
966  // that the slice is valid, otherwise return appropriate failure status.
967  std::optional<bool> isSliceValid = sliceUnion->isSliceValid();
968  if (!isSliceValid) {
969  LLVM_DEBUG(llvm::dbgs() << "Cannot determine if the slice is valid\n");
971  }
972  if (!*isSliceValid)
974 
976 }
977 
978 // TODO: extend this to handle multiple result maps.
979 static std::optional<uint64_t> getConstDifference(AffineMap lbMap,
980  AffineMap ubMap) {
981  assert(lbMap.getNumResults() == 1 && "expected single result bound map");
982  assert(ubMap.getNumResults() == 1 && "expected single result bound map");
983  assert(lbMap.getNumDims() == ubMap.getNumDims());
984  assert(lbMap.getNumSymbols() == ubMap.getNumSymbols());
985  AffineExpr lbExpr(lbMap.getResult(0));
986  AffineExpr ubExpr(ubMap.getResult(0));
987  auto loopSpanExpr = simplifyAffineExpr(ubExpr - lbExpr, lbMap.getNumDims(),
988  lbMap.getNumSymbols());
989  auto cExpr = loopSpanExpr.dyn_cast<AffineConstantExpr>();
990  if (!cExpr)
991  return std::nullopt;
992  return cExpr.getValue();
993 }
994 
995 // Builds a map 'tripCountMap' from AffineForOp to constant trip count for loop
996 // nest surrounding represented by slice loop bounds in 'slice'. Returns true
997 // on success, false otherwise (if a non-constant trip count was encountered).
998 // TODO: Make this work with non-unit step loops.
1000  const ComputationSliceState &slice,
1001  llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
1002  unsigned numSrcLoopIVs = slice.ivs.size();
1003  // Populate map from AffineForOp -> trip count
1004  for (unsigned i = 0; i < numSrcLoopIVs; ++i) {
1005  AffineForOp forOp = getForInductionVarOwner(slice.ivs[i]);
1006  auto *op = forOp.getOperation();
1007  AffineMap lbMap = slice.lbs[i];
1008  AffineMap ubMap = slice.ubs[i];
1009  // If lower or upper bound maps are null or provide no results, it implies
1010  // that source loop was not at all sliced, and the entire loop will be a
1011  // part of the slice.
1012  if (!lbMap || lbMap.getNumResults() == 0 || !ubMap ||
1013  ubMap.getNumResults() == 0) {
1014  // The iteration of src loop IV 'i' was not sliced. Use full loop bounds.
1015  if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
1016  (*tripCountMap)[op] =
1017  forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
1018  continue;
1019  }
1020  std::optional<uint64_t> maybeConstTripCount = getConstantTripCount(forOp);
1021  if (maybeConstTripCount.has_value()) {
1022  (*tripCountMap)[op] = *maybeConstTripCount;
1023  continue;
1024  }
1025  return false;
1026  }
1027  std::optional<uint64_t> tripCount = getConstDifference(lbMap, ubMap);
1028  // Slice bounds are created with a constant ub - lb difference.
1029  if (!tripCount.has_value())
1030  return false;
1031  (*tripCountMap)[op] = *tripCount;
1032  }
1033  return true;
1034 }
1035 
1036 // Return the number of iterations in the given slice.
1038  const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {
1039  uint64_t iterCount = 1;
1040  for (const auto &count : sliceTripCountMap) {
1041  iterCount *= count.second;
1042  }
1043  return iterCount;
1044 }
1045 
1046 const char *const kSliceFusionBarrierAttrName = "slice_fusion_barrier";
1047 // Computes slice bounds by projecting out any loop IVs from
1048 // 'dependenceConstraints' at depth greater than 'loopDepth', and computes slice
1049 // bounds in 'sliceState' which represent the one loop nest's IVs in terms of
1050 // the other loop nest's IVs, symbols and constants (using 'isBackwardsSlice').
1052  Operation *depSourceOp, Operation *depSinkOp,
1053  FlatAffineValueConstraints *dependenceConstraints, unsigned loopDepth,
1054  bool isBackwardSlice, ComputationSliceState *sliceState) {
1055  // Get loop nest surrounding src operation.
1056  SmallVector<AffineForOp, 4> srcLoopIVs;
1057  getAffineForIVs(*depSourceOp, &srcLoopIVs);
1058  unsigned numSrcLoopIVs = srcLoopIVs.size();
1059 
1060  // Get loop nest surrounding dst operation.
1061  SmallVector<AffineForOp, 4> dstLoopIVs;
1062  getAffineForIVs(*depSinkOp, &dstLoopIVs);
1063  unsigned numDstLoopIVs = dstLoopIVs.size();
1064 
1065  assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||
1066  (isBackwardSlice && loopDepth <= numDstLoopIVs));
1067 
1068  // Project out dimensions other than those up to 'loopDepth'.
1069  unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;
1070  unsigned num =
1071  isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;
1072  dependenceConstraints->projectOut(pos, num);
1073 
1074  // Add slice loop IV values to 'sliceState'.
1075  unsigned offset = isBackwardSlice ? 0 : loopDepth;
1076  unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;
1077  dependenceConstraints->getValues(offset, offset + numSliceLoopIVs,
1078  &sliceState->ivs);
1079 
1080  // Set up lower/upper bound affine maps for the slice.
1081  sliceState->lbs.resize(numSliceLoopIVs, AffineMap());
1082  sliceState->ubs.resize(numSliceLoopIVs, AffineMap());
1083 
1084  // Get bounds for slice IVs in terms of other IVs, symbols, and constants.
1085  dependenceConstraints->getSliceBounds(offset, numSliceLoopIVs,
1086  depSourceOp->getContext(),
1087  &sliceState->lbs, &sliceState->ubs);
1088 
1089  // Set up bound operands for the slice's lower and upper bounds.
1090  SmallVector<Value, 4> sliceBoundOperands;
1091  unsigned numDimsAndSymbols = dependenceConstraints->getNumDimAndSymbolVars();
1092  for (unsigned i = 0; i < numDimsAndSymbols; ++i) {
1093  if (i < offset || i >= offset + numSliceLoopIVs) {
1094  sliceBoundOperands.push_back(dependenceConstraints->getValue(i));
1095  }
1096  }
1097 
1098  // Give each bound its own copy of 'sliceBoundOperands' for subsequent
1099  // canonicalization.
1100  sliceState->lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1101  sliceState->ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1102 
1103  // Set destination loop nest insertion point to block start at 'dstLoopDepth'.
1104  sliceState->insertPoint =
1105  isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()
1106  : std::prev(srcLoopIVs[loopDepth - 1].getBody()->end());
1107 
1108  llvm::SmallDenseSet<Value, 8> sequentialLoops;
1109  if (isa<AffineReadOpInterface>(depSourceOp) &&
1110  isa<AffineReadOpInterface>(depSinkOp)) {
1111  // For read-read access pairs, clear any slice bounds on sequential loops.
1112  // Get sequential loops in loop nest rooted at 'srcLoopIVs[0]'.
1113  getSequentialLoops(isBackwardSlice ? srcLoopIVs[0] : dstLoopIVs[0],
1114  &sequentialLoops);
1115  }
1116  auto getSliceLoop = [&](unsigned i) {
1117  return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];
1118  };
1119  auto isInnermostInsertion = [&]() {
1120  return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()
1121  : loopDepth >= dstLoopIVs.size());
1122  };
1123  llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;
1124  auto srcIsUnitSlice = [&]() {
1125  return (buildSliceTripCountMap(*sliceState, &sliceTripCountMap) &&
1126  (getSliceIterationCount(sliceTripCountMap) == 1));
1127  };
1128  // Clear all sliced loop bounds beginning at the first sequential loop, or
1129  // first loop with a slice fusion barrier attribute..
1130 
1131  for (unsigned i = 0; i < numSliceLoopIVs; ++i) {
1132  Value iv = getSliceLoop(i).getInductionVar();
1133  if (sequentialLoops.count(iv) == 0 &&
1134  getSliceLoop(i)->getAttr(kSliceFusionBarrierAttrName) == nullptr)
1135  continue;
1136  // Skip reset of bounds of reduction loop inserted in the destination loop
1137  // that meets the following conditions:
1138  // 1. Slice is single trip count.
1139  // 2. Loop bounds of the source and destination match.
1140  // 3. Is being inserted at the innermost insertion point.
1141  std::optional<bool> isMaximal = sliceState->isMaximal();
1142  if (isLoopParallelAndContainsReduction(getSliceLoop(i)) &&
1143  isInnermostInsertion() && srcIsUnitSlice() && isMaximal && *isMaximal)
1144  continue;
1145  for (unsigned j = i; j < numSliceLoopIVs; ++j) {
1146  sliceState->lbs[j] = AffineMap();
1147  sliceState->ubs[j] = AffineMap();
1148  }
1149  break;
1150  }
1151 }
1152 
1153 /// Creates a computation slice of the loop nest surrounding 'srcOpInst',
1154 /// updates the slice loop bounds with any non-null bound maps specified in
1155 /// 'sliceState', and inserts this slice into the loop nest surrounding
1156 /// 'dstOpInst' at loop depth 'dstLoopDepth'.
1157 // TODO: extend the slicing utility to compute slices that
1158 // aren't necessarily a one-to-one relation b/w the source and destination. The
1159 // relation between the source and destination could be many-to-many in general.
1160 // TODO: the slice computation is incorrect in the cases
1161 // where the dependence from the source to the destination does not cover the
1162 // entire destination index set. Subtract out the dependent destination
1163 // iterations from destination index set and check for emptiness --- this is one
1164 // solution.
1165 AffineForOp
1167  unsigned dstLoopDepth,
1168  ComputationSliceState *sliceState) {
1169  // Get loop nest surrounding src operation.
1170  SmallVector<AffineForOp, 4> srcLoopIVs;
1171  getAffineForIVs(*srcOpInst, &srcLoopIVs);
1172  unsigned numSrcLoopIVs = srcLoopIVs.size();
1173 
1174  // Get loop nest surrounding dst operation.
1175  SmallVector<AffineForOp, 4> dstLoopIVs;
1176  getAffineForIVs(*dstOpInst, &dstLoopIVs);
1177  unsigned dstLoopIVsSize = dstLoopIVs.size();
1178  if (dstLoopDepth > dstLoopIVsSize) {
1179  dstOpInst->emitError("invalid destination loop depth");
1180  return AffineForOp();
1181  }
1182 
1183  // Find the op block positions of 'srcOpInst' within 'srcLoopIVs'.
1184  SmallVector<unsigned, 4> positions;
1185  // TODO: This code is incorrect since srcLoopIVs can be 0-d.
1186  findInstPosition(srcOpInst, srcLoopIVs[0]->getBlock(), &positions);
1187 
1188  // Clone src loop nest and insert it a the beginning of the operation block
1189  // of the loop at 'dstLoopDepth' in 'dstLoopIVs'.
1190  auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];
1191  OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());
1192  auto sliceLoopNest =
1193  cast<AffineForOp>(b.clone(*srcLoopIVs[0].getOperation()));
1194 
1195  Operation *sliceInst =
1196  getInstAtPosition(positions, /*level=*/0, sliceLoopNest.getBody());
1197  // Get loop nest surrounding 'sliceInst'.
1198  SmallVector<AffineForOp, 4> sliceSurroundingLoops;
1199  getAffineForIVs(*sliceInst, &sliceSurroundingLoops);
1200 
1201  // Sanity check.
1202  unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();
1203  (void)sliceSurroundingLoopsSize;
1204  assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);
1205  unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;
1206  (void)sliceLoopLimit;
1207  assert(sliceLoopLimit >= sliceSurroundingLoopsSize);
1208 
1209  // Update loop bounds for loops in 'sliceLoopNest'.
1210  for (unsigned i = 0; i < numSrcLoopIVs; ++i) {
1211  auto forOp = sliceSurroundingLoops[dstLoopDepth + i];
1212  if (AffineMap lbMap = sliceState->lbs[i])
1213  forOp.setLowerBound(sliceState->lbOperands[i], lbMap);
1214  if (AffineMap ubMap = sliceState->ubs[i])
1215  forOp.setUpperBound(sliceState->ubOperands[i], ubMap);
1216  }
1217  return sliceLoopNest;
1218 }
1219 
1220 // Constructs MemRefAccess populating it with the memref, its indices and
1221 // opinst from 'loadOrStoreOpInst'.
1223  if (auto loadOp = dyn_cast<AffineReadOpInterface>(loadOrStoreOpInst)) {
1224  memref = loadOp.getMemRef();
1225  opInst = loadOrStoreOpInst;
1226  llvm::append_range(indices, loadOp.getMapOperands());
1227  } else {
1228  assert(isa<AffineWriteOpInterface>(loadOrStoreOpInst) &&
1229  "Affine read/write op expected");
1230  auto storeOp = cast<AffineWriteOpInterface>(loadOrStoreOpInst);
1231  opInst = loadOrStoreOpInst;
1232  memref = storeOp.getMemRef();
1233  llvm::append_range(indices, storeOp.getMapOperands());
1234  }
1235 }
1236 
1237 unsigned MemRefAccess::getRank() const {
1238  return memref.getType().cast<MemRefType>().getRank();
1239 }
1240 
1242  return isa<AffineWriteOpInterface>(opInst);
1243 }
1244 
1245 /// Returns the nesting depth of this statement, i.e., the number of loops
1246 /// surrounding this statement.
1248  Operation *currOp = op;
1249  unsigned depth = 0;
1250  while ((currOp = currOp->getParentOp())) {
1251  if (isa<AffineForOp>(currOp))
1252  depth++;
1253  }
1254  return depth;
1255 }
1256 
1257 /// Equal if both affine accesses are provably equivalent (at compile
1258 /// time) when considering the memref, the affine maps and their respective
1259 /// operands. The equality of access functions + operands is checked by
1260 /// subtracting fully composed value maps, and then simplifying the difference
1261 /// using the expression flattener.
1262 /// TODO: this does not account for aliasing of memrefs.
1263 bool MemRefAccess::operator==(const MemRefAccess &rhs) const {
1264  if (memref != rhs.memref)
1265  return false;
1266 
1267  AffineValueMap diff, thisMap, rhsMap;
1268  getAccessMap(&thisMap);
1269  rhs.getAccessMap(&rhsMap);
1270  AffineValueMap::difference(thisMap, rhsMap, &diff);
1271  return llvm::all_of(diff.getAffineMap().getResults(),
1272  [](AffineExpr e) { return e == 0; });
1273 }
1274 
1276  auto *currOp = op.getParentOp();
1277  AffineForOp currAffineForOp;
1278  // Traverse up the hierarchy collecting all 'affine.for' and affine.parallel
1279  // operation while skipping over 'affine.if' operations.
1280  while (currOp) {
1281  if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(currOp))
1282  ivs.push_back(currAffineForOp.getInductionVar());
1283  else if (auto parOp = dyn_cast<AffineParallelOp>(currOp))
1284  llvm::append_range(ivs, parOp.getIVs());
1285  currOp = currOp->getParentOp();
1286  }
1287  std::reverse(ivs.begin(), ivs.end());
1288 }
1289 
1290 /// Returns the number of surrounding loops common to 'loopsA' and 'loopsB',
1291 /// where each lists loops from outer-most to inner-most in loop nest.
1293  SmallVector<Value, 4> loopsA, loopsB;
1294  getAffineIVs(a, loopsA);
1295  getAffineIVs(b, loopsB);
1296 
1297  unsigned minNumLoops = std::min(loopsA.size(), loopsB.size());
1298  unsigned numCommonLoops = 0;
1299  for (unsigned i = 0; i < minNumLoops; ++i) {
1300  if (loopsA[i] != loopsB[i])
1301  break;
1302  ++numCommonLoops;
1303  }
1304  return numCommonLoops;
1305 }
1306 
1307 static std::optional<int64_t> getMemoryFootprintBytes(Block &block,
1308  Block::iterator start,
1309  Block::iterator end,
1310  int memorySpace) {
1311  SmallDenseMap<Value, std::unique_ptr<MemRefRegion>, 4> regions;
1312 
1313  // Walk this 'affine.for' operation to gather all memory regions.
1314  auto result = block.walk(start, end, [&](Operation *opInst) -> WalkResult {
1315  if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst)) {
1316  // Neither load nor a store op.
1317  return WalkResult::advance();
1318  }
1319 
1320  // Compute the memref region symbolic in any IVs enclosing this block.
1321  auto region = std::make_unique<MemRefRegion>(opInst->getLoc());
1322  if (failed(
1323  region->compute(opInst,
1324  /*loopDepth=*/getNestingDepth(&*block.begin())))) {
1325  return opInst->emitError("error obtaining memory region\n");
1326  }
1327 
1328  auto it = regions.find(region->memref);
1329  if (it == regions.end()) {
1330  regions[region->memref] = std::move(region);
1331  } else if (failed(it->second->unionBoundingBox(*region))) {
1332  return opInst->emitWarning(
1333  "getMemoryFootprintBytes: unable to perform a union on a memory "
1334  "region");
1335  }
1336  return WalkResult::advance();
1337  });
1338  if (result.wasInterrupted())
1339  return std::nullopt;
1340 
1341  int64_t totalSizeInBytes = 0;
1342  for (const auto &region : regions) {
1343  std::optional<int64_t> size = region.second->getRegionSize();
1344  if (!size.has_value())
1345  return std::nullopt;
1346  totalSizeInBytes += *size;
1347  }
1348  return totalSizeInBytes;
1349 }
1350 
1351 std::optional<int64_t> mlir::getMemoryFootprintBytes(AffineForOp forOp,
1352  int memorySpace) {
1353  auto *forInst = forOp.getOperation();
1355  *forInst->getBlock(), Block::iterator(forInst),
1356  std::next(Block::iterator(forInst)), memorySpace);
1357 }
1358 
1359 /// Returns whether a loop is parallel and contains a reduction loop.
1361  SmallVector<LoopReduction> reductions;
1362  if (!isLoopParallel(forOp, &reductions))
1363  return false;
1364  return !reductions.empty();
1365 }
1366 
1367 /// Returns in 'sequentialLoops' all sequential loops in loop nest rooted
1368 /// at 'forOp'.
1369 void mlir::getSequentialLoops(AffineForOp forOp,
1370  llvm::SmallDenseSet<Value, 8> *sequentialLoops) {
1371  forOp->walk([&](Operation *op) {
1372  if (auto innerFor = dyn_cast<AffineForOp>(op))
1373  if (!isLoopParallel(innerFor))
1374  sequentialLoops->insert(innerFor.getInductionVar());
1375  });
1376 }
1377 
1379  FlatAffineValueConstraints fac(set);
1380  if (fac.isEmpty())
1381  return IntegerSet::getEmptySet(set.getNumDims(), set.getNumSymbols(),
1382  set.getContext());
1384 
1385  auto simplifiedSet = fac.getAsIntegerSet(set.getContext());
1386  assert(simplifiedSet && "guaranteed to succeed while roundtripping");
1387  return simplifiedSet;
1388 }
1389 
1390 static void unpackOptionalValues(ArrayRef<std::optional<Value>> source,
1391  SmallVector<Value> &target) {
1392  target =
1393  llvm::to_vector<4>(llvm::map_range(source, [](std::optional<Value> val) {
1394  return val.has_value() ? *val : Value();
1395  }));
1396 }
1397 
1398 /// Bound an identifier `pos` in a given FlatAffineValueConstraints with
1399 /// constraints drawn from an affine map. Before adding the constraint, the
1400 /// dimensions/symbols of the affine map are aligned with `constraints`.
1401 /// `operands` are the SSA Value operands used with the affine map.
1402 /// Note: This function adds a new symbol column to the `constraints` for each
1403 /// dimension/symbol that exists in the affine map but not in `constraints`.
1405  BoundType type, unsigned pos,
1406  AffineMap map, ValueRange operands) {
1407  SmallVector<Value> dims, syms, newSyms;
1410 
1411  AffineMap alignedMap =
1412  alignAffineMapWithValues(map, operands, dims, syms, &newSyms);
1413  for (unsigned i = syms.size(); i < newSyms.size(); ++i)
1414  constraints.appendSymbolVar(newSyms[i]);
1415  return constraints.addBound(type, pos, alignedMap);
1416 }
1417 
1418 /// Add `val` to each result of `map`.
1419 static AffineMap addConstToResults(AffineMap map, int64_t val) {
1420  SmallVector<AffineExpr> newResults;
1421  for (AffineExpr r : map.getResults())
1422  newResults.push_back(r + val);
1423  return AffineMap::get(map.getNumDims(), map.getNumSymbols(), newResults,
1424  map.getContext());
1425 }
1426 
1427 // Attempt to simplify the given min/max operation by proving that its value is
1428 // bounded by the same lower and upper bound.
1429 //
1430 // Bounds are computed by FlatAffineValueConstraints. Invariants required for
1431 // finding/proving bounds should be supplied via `constraints`.
1432 //
1433 // 1. Add dimensions for `op` and `opBound` (lower or upper bound of `op`).
1434 // 2. Compute an upper bound of `op` (in case of `isMin`) or a lower bound (in
1435 // case of `!isMin`) and bind it to `opBound`. SSA values that are used in
1436 // `op` but are not part of `constraints`, are added as extra symbols.
1437 // 3. For each result of `op`: Add result as a dimension `r_i`. Prove that:
1438 // * If `isMin`: r_i >= opBound
1439 // * If `isMax`: r_i <= opBound
1440 // If this is the case, ub(op) == lb(op).
1441 // 4. Replace `op` with `opBound`.
1442 //
1443 // In summary, the following constraints are added throughout this function.
1444 // Note: `invar` are dimensions added by the caller to express the invariants.
1445 // (Showing only the case where `isMin`.)
1446 //
1447 // invar | op | opBound | r_i | extra syms... | const | eq/ineq
1448 // ------+-------+---------+-----+---------------+-------+-------------------
1449 // (various eq./ineq. constraining `invar`, added by the caller)
1450 // ... | 0 | 0 | 0 | 0 | ... | ...
1451 // ------+-------+---------+-----+---------------+-------+-------------------
1452 // (various ineq. constraining `op` in terms of `op` operands (`invar` and
1453 // extra `op` operands "extra syms" that are not in `invar`)).
1454 // ... | -1 | 0 | 0 | ... | ... | >= 0
1455 // ------+-------+---------+-----+---------------+-------+-------------------
1456 // (set `opBound` to `op` upper bound in terms of `invar` and "extra syms")
1457 // ... | 0 | -1 | 0 | ... | ... | = 0
1458 // ------+-------+---------+-----+---------------+-------+-------------------
1459 // (for each `op` map result r_i: set r_i to corresponding map result,
1460 // prove that r_i >= minOpUb via contradiction)
1461 // ... | 0 | 0 | -1 | ... | ... | = 0
1462 // 0 | 0 | 1 | -1 | 0 | -1 | >= 0
1463 //
1466  FlatAffineValueConstraints constraints) {
1467  bool isMin = isa<AffineMinOp>(op);
1468  assert((isMin || isa<AffineMaxOp>(op)) && "expect AffineMin/MaxOp");
1469  MLIRContext *ctx = op->getContext();
1470  Builder builder(ctx);
1471  AffineMap map =
1472  isMin ? cast<AffineMinOp>(op).getMap() : cast<AffineMaxOp>(op).getMap();
1473  ValueRange operands = op->getOperands();
1474  unsigned numResults = map.getNumResults();
1475 
1476  // Add a few extra dimensions.
1477  unsigned dimOp = constraints.appendDimVar(); // `op`
1478  unsigned dimOpBound = constraints.appendDimVar(); // `op` lower/upper bound
1479  unsigned resultDimStart = constraints.appendDimVar(/*num=*/numResults);
1480 
1481  // Add an inequality for each result expr_i of map:
1482  // isMin: op <= expr_i, !isMin: op >= expr_i
1483  auto boundType = isMin ? BoundType::UB : BoundType::LB;
1484  // Upper bounds are exclusive, so add 1. (`affine.min` ops are inclusive.)
1485  AffineMap mapLbUb = isMin ? addConstToResults(map, 1) : map;
1486  if (failed(
1487  alignAndAddBound(constraints, boundType, dimOp, mapLbUb, operands)))
1488  return failure();
1489 
1490  // Try to compute a lower/upper bound for op, expressed in terms of the other
1491  // `dims` and extra symbols.
1492  SmallVector<AffineMap> opLb(1), opUb(1);
1493  constraints.getSliceBounds(dimOp, 1, ctx, &opLb, &opUb);
1494  AffineMap sliceBound = isMin ? opUb[0] : opLb[0];
1495  // TODO: `getSliceBounds` may return multiple bounds at the moment. This is
1496  // a TODO of `getSliceBounds` and not handled here.
1497  if (!sliceBound || sliceBound.getNumResults() != 1)
1498  return failure(); // No or multiple bounds found.
1499  // Recover the inclusive UB in the case of an `affine.min`.
1500  AffineMap boundMap = isMin ? addConstToResults(sliceBound, -1) : sliceBound;
1501 
1502  // Add an equality: Set dimOpBound to computed bound.
1503  // Add back dimension for op. (Was removed by `getSliceBounds`.)
1504  AffineMap alignedBoundMap = boundMap.shiftDims(/*shift=*/1, /*offset=*/dimOp);
1505  if (failed(constraints.addBound(BoundType::EQ, dimOpBound, alignedBoundMap)))
1506  return failure();
1507 
1508  // If the constraint system is empty, there is an inconsistency. (E.g., this
1509  // can happen if loop lb > ub.)
1510  if (constraints.isEmpty())
1511  return failure();
1512 
1513  // In the case of `isMin` (`!isMin` is inversed):
1514  // Prove that each result of `map` has a lower bound that is equal to (or
1515  // greater than) the upper bound of `op` (`dimOpBound`). In that case, `op`
1516  // can be replaced with the bound. I.e., prove that for each result
1517  // expr_i (represented by dimension r_i):
1518  //
1519  // r_i >= opBound
1520  //
1521  // To prove this inequality, add its negation to the constraint set and prove
1522  // that the constraint set is empty.
1523  for (unsigned i = resultDimStart; i < resultDimStart + numResults; ++i) {
1524  FlatAffineValueConstraints newConstr(constraints);
1525 
1526  // Add an equality: r_i = expr_i
1527  // Note: These equalities could have been added earlier and used to express
1528  // minOp <= expr_i. However, then we run the risk that `getSliceBounds`
1529  // computes minOpUb in terms of r_i dims, which is not desired.
1530  if (failed(alignAndAddBound(newConstr, BoundType::EQ, i,
1531  map.getSubMap({i - resultDimStart}), operands)))
1532  return failure();
1533 
1534  // If `isMin`: Add inequality: r_i < opBound
1535  // equiv.: opBound - r_i - 1 >= 0
1536  // If `!isMin`: Add inequality: r_i > opBound
1537  // equiv.: -opBound + r_i - 1 >= 0
1538  SmallVector<int64_t> ineq(newConstr.getNumCols(), 0);
1539  ineq[dimOpBound] = isMin ? 1 : -1;
1540  ineq[i] = isMin ? -1 : 1;
1541  ineq[newConstr.getNumCols() - 1] = -1;
1542  newConstr.addInequality(ineq);
1543  if (!newConstr.isEmpty())
1544  return failure();
1545  }
1546 
1547  // Lower and upper bound of `op` are equal. Replace `minOp` with its bound.
1548  AffineMap newMap = alignedBoundMap;
1549  SmallVector<Value> newOperands;
1550  unpackOptionalValues(constraints.getMaybeValues(), newOperands);
1551  // If dims/symbols have known constant values, use those in order to simplify
1552  // the affine map further.
1553  for (int64_t i = 0, e = constraints.getNumDimAndSymbolVars(); i < e; ++i) {
1554  // Skip unused operands and operands that are already constants.
1555  if (!newOperands[i] || getConstantIntValue(newOperands[i]))
1556  continue;
1557  if (auto bound = constraints.getConstantBound64(BoundType::EQ, i)) {
1558  AffineExpr expr =
1559  i < newMap.getNumDims()
1560  ? builder.getAffineDimExpr(i)
1561  : builder.getAffineSymbolExpr(i - newMap.getNumDims());
1562  newMap = newMap.replace(expr, builder.getAffineConstantExpr(*bound),
1563  newMap.getNumDims(), newMap.getNumSymbols());
1564  }
1565  }
1566  mlir::canonicalizeMapAndOperands(&newMap, &newOperands);
1567  return AffineValueMap(newMap, newOperands);
1568 }
static std::optional< uint64_t > getConstDifference(AffineMap lbMap, AffineMap ubMap)
Definition: Utils.cpp:979
static void findInstPosition(Operation *op, Block *limitBlock, SmallVectorImpl< unsigned > *positions)
Definition: Utils.cpp:726
const char *const kSliceFusionBarrierAttrName
Definition: Utils.cpp:1046
static LogicalResult addMissingLoopIVBounds(SmallPtrSet< Value, 8 > &ivs, FlatAffineValueConstraints *cst)
Definition: Utils.cpp:768
static Operation * getInstAtPosition(ArrayRef< unsigned > positions, unsigned level, Block *block)
Definition: Utils.cpp:743
static std::optional< int64_t > getMemoryFootprintBytes(Block &block, Block::iterator start, Block::iterator end, int memorySpace)
Definition: Utils.cpp:1307
static AffineMap addConstToResults(AffineMap map, int64_t val)
Add val to each result of map.
Definition: Utils.cpp:1419
static LogicalResult alignAndAddBound(FlatAffineValueConstraints &constraints, BoundType type, unsigned pos, AffineMap map, ValueRange operands)
Bound an identifier pos in a given FlatAffineValueConstraints with constraints drawn from an affine m...
Definition: Utils.cpp:1404
static void unpackOptionalValues(ArrayRef< std::optional< Value >> source, SmallVector< Value > &target)
Definition: Utils.cpp:1390
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
An integer constant appearing in affine expression.
Definition: AffineExpr.h:232
int64_t getValue() const
Definition: AffineExpr.cpp:519
A dimensional identifier appearing in an affine expression.
Definition: AffineExpr.h:216
unsigned getPosition() const
Definition: AffineExpr.cpp:325
Base type for affine expression.
Definition: AffineExpr.h:68
constexpr bool isa() const
Definition: AffineExpr.h:270
U dyn_cast() const
Definition: AffineExpr.h:281
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:43
MLIRContext * getContext() const
Definition: AffineMap.cpp:271
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
AffineMap shiftDims(unsigned shift, unsigned offset=0) const
Replace dims[offset ...
Definition: AffineMap.h:226
unsigned getNumSymbols() const
Definition: AffineMap.cpp:328
unsigned getNumDims() const
Definition: AffineMap.cpp:324
ArrayRef< AffineExpr > getResults() const
Definition: AffineMap.cpp:337
unsigned getNumResults() const
Definition: AffineMap.cpp:332
unsigned getNumInputs() const
Definition: AffineMap.cpp:333
AffineExpr getResult(unsigned idx) const
Definition: AffineMap.cpp:341
AffineMap replace(AffineExpr expr, AffineExpr replacement, unsigned numResultDims, unsigned numResultSyms) const
Sparse replace method.
Definition: AffineMap.cpp:441
void dump() const
AffineMap getSubMap(ArrayRef< unsigned > resultPos) const
Returns the map consisting of the resultPos subset.
Definition: AffineMap.cpp:557
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes.
Value getOperand(unsigned i) const
unsigned getNumOperands() const
AffineMap getAffineMap() const
static void difference(const AffineValueMap &a, const AffineValueMap &b, AffineValueMap *res)
Return the value map that is the difference of value maps 'a' and 'b', represented as an affine map a...
Block represents an ordered list of Operations.
Definition: Block.h:30
OpListType::iterator iterator
Definition: Block.h:129
RetT walk(FnT &&callback)
Walk the operations in this block.
Definition: Block.h:273
iterator begin()
Definition: Block.h:132
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:30
This class is a general helper class for creating context-global objects like types,...
Definition: Builders.h:50
AffineExpr getAffineSymbolExpr(unsigned position)
Definition: Builders.cpp:343
AffineExpr getAffineConstantExpr(int64_t constant)
Definition: Builders.cpp:347
AffineExpr getAffineDimExpr(unsigned position)
Definition: Builders.cpp:339
This class provides support for representing a failure result, or a valid value of type T.
Definition: LogicalResult.h:78
FlatAffineValueConstraints is an extension of FlatLinearValueConstraints with helper functions for Af...
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, ValueRange operands)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
void convertLoopIVSymbolsToDims()
Changes all symbol variables which are loop IVs to dim variables.
LogicalResult addDomainFromSliceMaps(ArrayRef< AffineMap > lbMaps, ArrayRef< AffineMap > ubMaps, ArrayRef< Value > operands)
Adds constraints (lower and upper bounds) for each loop in the loop nest described by the bound maps ...
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR i...
LogicalResult addSliceBounds(ArrayRef< Value > values, ArrayRef< AffineMap > lbMaps, ArrayRef< AffineMap > ubMaps, ArrayRef< Value > operands)
Adds slice lower bounds represented by lower bounds in lbMaps and upper bounds in ubMaps to each vari...
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool closedUB=false)
Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an...
LogicalResult unionBoundingBox(const FlatLinearValueConstraints &other)
Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this ...
void mergeAndAlignVarsWithOther(unsigned offset, FlatLinearValueConstraints *other)
Merge and align the variables of this and other starting at offset, so that both constraint systems g...
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th variable.
void projectOut(Value val)
Projects out the variable that is associate with Value.
bool containsVar(Value val) const
Returns true if a variable with the specified Value exists, false otherwise.
ArrayRef< std::optional< Value > > getMaybeValues() const
bool areVarsAlignedWithOther(const FlatLinearConstraints &other)
Returns true if this constraint system and other are in the same space, i.e., if they are associated ...
void getValues(unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
Returns the Values associated with variables in range [start, end).
An integer set representing a conjunction of one or more affine equalities and inequalities.
Definition: IntegerSet.h:44
unsigned getNumDims() const
Definition: IntegerSet.cpp:15
MLIRContext * getContext() const
Definition: IntegerSet.cpp:57
static IntegerSet getEmptySet(unsigned numDims, unsigned numSymbols, MLIRContext *context)
Definition: IntegerSet.h:56
unsigned getNumSymbols() const
Definition: IntegerSet.cpp:16
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:60
This class helps build Operations.
Definition: Builders.h:202
Operation * clone(Operation &op, IRMapping &mapper)
Creates a deep copy of the specified operation, remapping any operands that use values outside of the...
Definition: Builders.cpp:520
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:75
InFlightDiagnostic emitWarning(const Twine &message={})
Emit a warning about this operation, reporting up to any diagnostic handlers that may be listening.
Definition: Operation.cpp:246
MLIRContext * getContext()
Return the context this operation is associated with.
Definition: Operation.h:200
Location getLoc()
The source location the operation was defined or derived from.
Definition: Operation.h:207
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:218
InFlightDiagnostic emitError(const Twine &message={})
Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...
Definition: Operation.cpp:234
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:197
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:540
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:357
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:370
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:93
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
A utility result that is used to signal how to proceed with an ongoing walk:
Definition: Visitors.h:34
static WalkResult advance()
Definition: Visitors.h:52
Specialization of arith.constant op that returns an integer of index type.
Definition: Arith.h:89
void addInequality(ArrayRef< MPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
void removeTrivialRedundancy()
Removes duplicate constraints, trivially true constraints, and constraints that can be detected as re...
std::optional< int64_t > getConstantBoundOnDimSize64(unsigned pos, SmallVectorImpl< int64_t > *lb=nullptr, int64_t *boundFloorDivisor=nullptr, SmallVectorImpl< int64_t > *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const
The same, but casts to int64_t.
std::optional< int64_t > getConstantBound64(BoundType type, unsigned pos) const
The same, but casts to int64_t.
bool isEmpty() const
Checks for emptiness by performing variable elimination on all variables, running the GCD test on eac...
unsigned getNumCols() const
Returns the number of columns in the constraint system.
bool isIntegerEmpty() const
Return true if all the sets in the union are known to be integer empty false otherwise.
PresburgerSet subtract(const PresburgerRelation &set) const
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:223
BoundType
The type of bound: equal, lower bound or upper bound.
Include the generated interface declarations.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
bool isLoopParallelAndContainsReduction(AffineForOp forOp)
Returns whether a loop is a parallel loop and contains a reduction loop.
Definition: Utils.cpp:1360
IntegerSet simplifyIntegerSet(IntegerSet set)
Simplify the integer set by simplifying the underlying affine expressions by flattening and some simp...
Definition: Utils.cpp:1378
std::optional< uint64_t > getIntOrFloatMemRefSizeInBytes(MemRefType memRefType)
Returns the size of a memref with element type int or float in bytes if it's statically shaped,...
Definition: Utils.cpp:647
std::optional< int64_t > getMemRefIntOrFloatEltSizeInBytes(MemRefType memRefType)
Returns the memref's element type's size in bytes where the elemental type is an int or float or a ve...
Definition: Utils.cpp:597
std::optional< int64_t > getConstantIntValue(OpFoldResult ofr)
If ofr is a constant integer or an IntegerAttr, return the integer.
void getAffineIVs(Operation &op, SmallVectorImpl< Value > &ivs)
Populates 'ivs' with IVs of the surrounding affine.for and affine.parallel ops ordered from the outer...
Definition: Utils.cpp:1275
bool buildSliceTripCountMap(const ComputationSliceState &slice, llvm::SmallDenseMap< Operation *, uint64_t, 8 > *tripCountMap)
Builds a map 'tripCountMap' from AffineForOp to constant trip count for loop nest surrounding represe...
Definition: Utils.cpp:999
SliceComputationResult computeSliceUnion(ArrayRef< Operation * > opsA, ArrayRef< Operation * > opsB, unsigned loopDepth, unsigned numCommonLoops, bool isBackwardSlice, ComputationSliceState *sliceUnion)
Computes in 'sliceUnion' the union of all slice bounds computed at 'loopDepth' between all dependent ...
Definition: Utils.cpp:816
void getSequentialLoops(AffineForOp forOp, llvm::SmallDenseSet< Value, 8 > *sequentialLoops)
Returns in 'sequentialLoops' all sequential loops in loop nest rooted at 'forOp'.
Definition: Utils.cpp:1369
FailureOr< AffineValueMap > simplifyConstrainedMinMaxOp(Operation *op, FlatAffineValueConstraints constraints)
Try to simplify the given affine.min or affine.max op to an affine map with a single result and opera...
Definition: Utils.cpp:1465
bool isAffineInductionVar(Value val)
Returns true if the provided value is the induction variable of an AffineForOp or AffineParallelOp.
Definition: AffineOps.cpp:2529
InFlightDiagnostic emitError(Location loc)
Utility method to emit an error message using this location.
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value.
Definition: LogicalResult.h:68
AffineMap alignAffineMapWithValues(AffineMap map, ValueRange operands, ValueRange dims, ValueRange syms, SmallVector< Value > *newSyms=nullptr)
Re-indexes the dimensions and symbols of an affine map with given operands values to align with dims ...
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
bool isValidSymbol(Value value)
Returns true if the given value can be used as a symbol in the region of the closest surrounding op t...
Definition: AffineOps.cpp:361
AffineForOp getForInductionVarOwner(Value val)
Returns the loop parent of an induction variable.
Definition: AffineOps.cpp:2533
AffineParallelOp getAffineParallelInductionVarOwner(Value val)
Returns true if the provided value is among the induction variables of an AffineParallelOp.
Definition: AffineOps.cpp:2544
std::optional< uint64_t > getConstantTripCount(AffineForOp forOp)
Returns the trip count of the loop if it's a constant, std::nullopt otherwise.
void getEnclosingAffineOps(Operation &op, SmallVectorImpl< Operation * > *ops)
Populates 'ops' with affine operations enclosing op ordered from outermost to innermost.
Definition: Utils.cpp:48
AffineForOp insertBackwardComputationSlice(Operation *srcOpInst, Operation *dstOpInst, unsigned dstLoopDepth, ComputationSliceState *sliceState)
Creates a clone of the computation contained in the loop nest surrounding 'srcOpInst',...
Definition: Utils.cpp:1166
void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp, FlatAffineValueConstraints *dependenceConstraints, unsigned loopDepth, bool isBackwardSlice, ComputationSliceState *sliceState)
Computes the computation slice loop bounds for one loop nest as affine maps of the other loop nest's ...
Definition: Utils.cpp:1051
unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)
Returns the number of surrounding loops common to both A and B.
Definition: Utils.cpp:1292
unsigned getInnermostCommonLoopDepth(ArrayRef< Operation * > ops, SmallVectorImpl< AffineForOp > *surroundingLoops=nullptr)
Returns the innermost common loop depth for the set of operations in 'ops'.
Definition: Utils.cpp:784
std::optional< int64_t > getMemoryFootprintBytes(AffineForOp forOp, int memorySpace=-1)
Gets the memory footprint of all data touched in the specified memory space in bytes; if the memory s...
Definition: Utils.cpp:1351
unsigned getNestingDepth(Operation *op)
Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation.
Definition: Utils.cpp:1247
DependenceResult checkMemrefAccessDependence(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints=nullptr, SmallVector< DependenceComponent, 2 > *dependenceComponents=nullptr, bool allowRAR=false)
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
bool isAffineForInductionVar(Value val)
Returns true if the provided value is the induction variable of an AffineForOp.
Definition: AffineOps.cpp:2521
void getAffineForIVs(Operation &op, SmallVectorImpl< AffineForOp > *loops)
Populates 'loops' with IVs of the affine.for ops surrounding 'op' ordered from the outermost 'affine....
Definition: Utils.cpp:35
void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Modifies both map and operands in-place so as to:
Definition: AffineOps.cpp:1439
bool isLoopParallel(AffineForOp forOp, SmallVectorImpl< LoopReduction > *parallelReductions=nullptr)
Returns true if ‘forOp’ is a parallel loop.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:72
uint64_t getSliceIterationCount(const llvm::SmallDenseMap< Operation *, uint64_t, 8 > &sliceTripCountMap)
Return the number of iterations for the slicetripCountMap provided.
Definition: Utils.cpp:1037
LogicalResult boundCheckLoadOrStoreOp(LoadOrStoreOpPointer loadOrStoreOp, bool emitError=true)
Checks a load or store op for an out of bound access; returns failure if the access is out of bounds ...
ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their associated operands for a ...
Definition: Utils.h:83
SmallVector< AffineMap, 4 > ubs
Definition: Utils.h:90
SmallVector< AffineMap, 4 > lbs
Definition: Utils.h:88
std::vector< SmallVector< Value, 4 > > ubOperands
Definition: Utils.h:94
Block::iterator insertPoint
Definition: Utils.h:96
std::optional< bool > isMaximal() const
Returns true if the computation slice encloses all the iterations of the sliced loop nest.
Definition: Utils.cpp:289
std::vector< SmallVector< Value, 4 > > lbOperands
Definition: Utils.h:92
LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst)
Adds to 'cst' constraints which represent the original loop bounds on 'ivs' in 'this'.
Definition: Utils.cpp:66
SmallVector< Value, 4 > ivs
Definition: Utils.h:86
std::optional< bool > isSliceValid()
Checks the validity of the slice computed.
Definition: Utils.cpp:219
LogicalResult getAsConstraints(FlatAffineValueConstraints *cst)
Definition: Utils.cpp:81
Checks whether two accesses to the same memref access the same element.
enum mlir::DependenceResult::ResultEnum value
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
Encapsulates a memref load or store access information.
unsigned getRank() const
Definition: Utils.cpp:1237
MemRefAccess(Operation *opInst)
Constructs a MemRefAccess from a load or store operation.
Definition: Utils.cpp:1222
void getAccessMap(AffineValueMap *accessMap) const
Populates 'accessMap' with composition of AffineApplyOps reachable from 'indices'.
bool operator==(const MemRefAccess &rhs) const
Equal if both affine accesses can be proved to be equivalent at compile time (considering the memrefs...
Definition: Utils.cpp:1263
bool isStore() const
Definition: Utils.cpp:1241
Operation * opInst
A region of a memref's data space; this is typically constructed by analyzing load/store op's on this...
Definition: Utils.h:255
FlatAffineValueConstraints * getConstraints()
Definition: Utils.h:294
unsigned getRank() const
Returns the rank of the memref that this region corresponds to.
Definition: Utils.cpp:339
std::optional< int64_t > getConstantBoundingSizeAndShape(SmallVectorImpl< int64_t > *shape=nullptr, std::vector< SmallVector< int64_t, 4 >> *lbs=nullptr, SmallVectorImpl< int64_t > *lbDivisors=nullptr) const
Returns a constant upper bound on the number of elements in this region if bounded by a known constan...
Definition: Utils.cpp:343
void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap, AffineMap &ubMap) const
Gets the lower and upper bound map for the dimensional variable at pos.
Definition: Utils.cpp:404
std::optional< int64_t > getRegionSize()
Returns the size of this MemRefRegion in bytes.
Definition: Utils.cpp:616
LogicalResult unionBoundingBox(const MemRefRegion &other)
Definition: Utils.cpp:423
LogicalResult compute(Operation *op, unsigned loopDepth, const ComputationSliceState *sliceState=nullptr, bool addMemRefDimBounds=true)
Computes the memory region accessed by this memref with the region represented as constraints symboli...
Definition: Utils.cpp:445
Value memref
Memref that this region corresponds to.
Definition: Utils.h:342
Enumerates different result statuses of slice computation by computeSliceUnion
Definition: Utils.h:70
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.