MLIR  16.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 
21 #include "mlir/IR/IntegerSet.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/raw_ostream.h"
25 
26 #define DEBUG_TYPE "analysis-utils"
27 
28 using namespace mlir;
29 using namespace presburger;
30 
31 using llvm::SmallDenseMap;
32 
33 /// Populates 'loops' with IVs of the loops surrounding 'op' ordered from
34 /// the outermost 'affine.for' operation to the innermost one.
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.reset(/*numDims=*/ivs.size(), /*numSymbols=*/0, /*numLocals=*/0, ivs);
69  for (Value iv : ivs) {
70  AffineForOp loop = getForInductionVarOwner(iv);
71  assert(loop && "Expected affine for");
72  if (failed(cst.addAffineForOpDomain(loop)))
73  return failure();
74  }
75  return success();
76 }
77 
78 // Populates 'cst' with FlatAffineValueConstraints which represent slice bounds.
81  assert(!lbOperands.empty());
82  // Adds src 'ivs' as dimension variables in 'cst'.
83  unsigned numDims = ivs.size();
84  // Adds operands (dst ivs and symbols) as symbols in 'cst'.
85  unsigned numSymbols = lbOperands[0].size();
86 
87  SmallVector<Value, 4> values(ivs);
88  // Append 'ivs' then 'operands' to 'values'.
89  values.append(lbOperands[0].begin(), lbOperands[0].end());
90  cst->reset(numDims, numSymbols, 0, values);
91 
92  // Add loop bound constraints for values which are loop IVs of the destination
93  // of fusion and equality constraints for symbols which are constants.
94  for (unsigned i = numDims, end = values.size(); i < end; ++i) {
95  Value value = values[i];
96  assert(cst->containsVar(value) && "value expected to be present");
97  if (isValidSymbol(value)) {
98  // Check if the symbol is a constant.
99  if (auto cOp = value.getDefiningOp<arith::ConstantIndexOp>())
100  cst->addBound(FlatAffineValueConstraints::EQ, value, cOp.value());
101  } else if (auto loop = getForInductionVarOwner(value)) {
102  if (failed(cst->addAffineForOpDomain(loop)))
103  return failure();
104  }
105  }
106 
107  // Add slices bounds on 'ivs' using maps 'lbs'/'ubs' with 'lbOperands[0]'
108  LogicalResult ret = cst->addSliceBounds(ivs, lbs, ubs, lbOperands[0]);
109  assert(succeeded(ret) &&
110  "should not fail as we never have semi-affine slice maps");
111  (void)ret;
112  return success();
113 }
114 
115 // Clears state bounds and operand state.
117  lbs.clear();
118  ubs.clear();
119  lbOperands.clear();
120  ubOperands.clear();
121 }
122 
124  llvm::errs() << "\tIVs:\n";
125  for (Value iv : ivs)
126  llvm::errs() << "\t\t" << iv << "\n";
127 
128  llvm::errs() << "\tLBs:\n";
129  for (auto &en : llvm::enumerate(lbs)) {
130  llvm::errs() << "\t\t" << en.value() << "\n";
131  llvm::errs() << "\t\tOperands:\n";
132  for (Value lbOp : lbOperands[en.index()])
133  llvm::errs() << "\t\t\t" << lbOp << "\n";
134  }
135 
136  llvm::errs() << "\tUBs:\n";
137  for (auto &en : llvm::enumerate(ubs)) {
138  llvm::errs() << "\t\t" << en.value() << "\n";
139  llvm::errs() << "\t\tOperands:\n";
140  for (Value ubOp : ubOperands[en.index()])
141  llvm::errs() << "\t\t\t" << ubOp << "\n";
142  }
143 }
144 
145 /// Fast check to determine if the computation slice is maximal. Returns true if
146 /// each slice dimension maps to an existing dst dimension and both the src
147 /// and the dst loops for those dimensions have the same bounds. Returns false
148 /// if both the src and the dst loops don't have the same bounds. Returns
149 /// llvm::None if none of the above can be proven.
150 Optional<bool> ComputationSliceState::isSliceMaximalFastCheck() const {
151  assert(lbs.size() == ubs.size() && !lbs.empty() && !ivs.empty() &&
152  "Unexpected number of lbs, ubs and ivs in slice");
153 
154  for (unsigned i = 0, end = lbs.size(); i < end; ++i) {
155  AffineMap lbMap = lbs[i];
156  AffineMap ubMap = ubs[i];
157 
158  // Check if this slice is just an equality along this dimension.
159  if (!lbMap || !ubMap || lbMap.getNumResults() != 1 ||
160  ubMap.getNumResults() != 1 ||
161  lbMap.getResult(0) + 1 != ubMap.getResult(0) ||
162  // The condition above will be true for maps describing a single
163  // iteration (e.g., lbMap.getResult(0) = 0, ubMap.getResult(0) = 1).
164  // Make sure we skip those cases by checking that the lb result is not
165  // just a constant.
166  lbMap.getResult(0).isa<AffineConstantExpr>())
167  return llvm::None;
168 
169  // Limited support: we expect the lb result to be just a loop dimension for
170  // now.
171  AffineDimExpr result = lbMap.getResult(0).dyn_cast<AffineDimExpr>();
172  if (!result)
173  return llvm::None;
174 
175  // Retrieve dst loop bounds.
176  AffineForOp dstLoop =
177  getForInductionVarOwner(lbOperands[i][result.getPosition()]);
178  if (!dstLoop)
179  return llvm::None;
180  AffineMap dstLbMap = dstLoop.getLowerBoundMap();
181  AffineMap dstUbMap = dstLoop.getUpperBoundMap();
182 
183  // Retrieve src loop bounds.
184  AffineForOp srcLoop = getForInductionVarOwner(ivs[i]);
185  assert(srcLoop && "Expected affine for");
186  AffineMap srcLbMap = srcLoop.getLowerBoundMap();
187  AffineMap srcUbMap = srcLoop.getUpperBoundMap();
188 
189  // Limited support: we expect simple src and dst loops with a single
190  // constant component per bound for now.
191  if (srcLbMap.getNumResults() != 1 || srcUbMap.getNumResults() != 1 ||
192  dstLbMap.getNumResults() != 1 || dstUbMap.getNumResults() != 1)
193  return llvm::None;
194 
195  AffineExpr srcLbResult = srcLbMap.getResult(0);
196  AffineExpr dstLbResult = dstLbMap.getResult(0);
197  AffineExpr srcUbResult = srcUbMap.getResult(0);
198  AffineExpr dstUbResult = dstUbMap.getResult(0);
199  if (!srcLbResult.isa<AffineConstantExpr>() ||
200  !srcUbResult.isa<AffineConstantExpr>() ||
201  !dstLbResult.isa<AffineConstantExpr>() ||
202  !dstUbResult.isa<AffineConstantExpr>())
203  return llvm::None;
204 
205  // Check if src and dst loop bounds are the same. If not, we can guarantee
206  // that the slice is not maximal.
207  if (srcLbResult != dstLbResult || srcUbResult != dstUbResult ||
208  srcLoop.getStep() != dstLoop.getStep())
209  return false;
210  }
211 
212  return true;
213 }
214 
215 /// Returns true if it is deterministically verified that the original iteration
216 /// space of the slice is contained within the new iteration space that is
217 /// created after fusing 'this' slice into its destination.
219  // Fast check to determine if the slice is valid. If the following conditions
220  // are verified to be true, slice is declared valid by the fast check:
221  // 1. Each slice loop is a single iteration loop bound in terms of a single
222  // destination loop IV.
223  // 2. Loop bounds of the destination loop IV (from above) and those of the
224  // source loop IV are exactly the same.
225  // If the fast check is inconclusive or false, we proceed with a more
226  // expensive analysis.
227  // TODO: Store the result of the fast check, as it might be used again in
228  // `canRemoveSrcNodeAfterFusion`.
229  Optional<bool> isValidFastCheck = isSliceMaximalFastCheck();
230  if (isValidFastCheck && *isValidFastCheck)
231  return true;
232 
233  // Create constraints for the source loop nest using which slice is computed.
234  FlatAffineValueConstraints srcConstraints;
235  // TODO: Store the source's domain to avoid computation at each depth.
236  if (failed(getSourceAsConstraints(srcConstraints))) {
237  LLVM_DEBUG(llvm::dbgs() << "Unable to compute source's domain\n");
238  return llvm::None;
239  }
240  // As the set difference utility currently cannot handle symbols in its
241  // operands, validity of the slice cannot be determined.
242  if (srcConstraints.getNumSymbolVars() > 0) {
243  LLVM_DEBUG(llvm::dbgs() << "Cannot handle symbols in source domain\n");
244  return llvm::None;
245  }
246  // TODO: Handle local vars in the source domains while using the 'projectOut'
247  // utility below. Currently, aligning is not done assuming that there will be
248  // no local vars in the source domain.
249  if (srcConstraints.getNumLocalVars() != 0) {
250  LLVM_DEBUG(llvm::dbgs() << "Cannot handle locals in source domain\n");
251  return llvm::None;
252  }
253 
254  // Create constraints for the slice loop nest that would be created if the
255  // fusion succeeds.
256  FlatAffineValueConstraints sliceConstraints;
257  if (failed(getAsConstraints(&sliceConstraints))) {
258  LLVM_DEBUG(llvm::dbgs() << "Unable to compute slice's domain\n");
259  return llvm::None;
260  }
261 
262  // Projecting out every dimension other than the 'ivs' to express slice's
263  // domain completely in terms of source's IVs.
264  sliceConstraints.projectOut(ivs.size(),
265  sliceConstraints.getNumVars() - ivs.size());
266 
267  LLVM_DEBUG(llvm::dbgs() << "Domain of the source of the slice:\n");
268  LLVM_DEBUG(srcConstraints.dump());
269  LLVM_DEBUG(llvm::dbgs() << "Domain of the slice if this fusion succeeds "
270  "(expressed in terms of its source's IVs):\n");
271  LLVM_DEBUG(sliceConstraints.dump());
272 
273  // TODO: Store 'srcSet' to avoid recalculating for each depth.
274  PresburgerSet srcSet(srcConstraints);
275  PresburgerSet sliceSet(sliceConstraints);
276  PresburgerSet diffSet = sliceSet.subtract(srcSet);
277 
278  if (!diffSet.isIntegerEmpty()) {
279  LLVM_DEBUG(llvm::dbgs() << "Incorrect slice\n");
280  return false;
281  }
282  return true;
283 }
284 
285 /// Returns true if the computation slice encloses all the iterations of the
286 /// sliced loop nest. Returns false if it does not. Returns llvm::None if it
287 /// cannot determine if the slice is maximal or not.
289  // Fast check to determine if the computation slice is maximal. If the result
290  // is inconclusive, we proceed with a more expensive analysis.
291  Optional<bool> isMaximalFastCheck = isSliceMaximalFastCheck();
292  if (isMaximalFastCheck)
293  return isMaximalFastCheck;
294 
295  // Create constraints for the src loop nest being sliced.
296  FlatAffineValueConstraints srcConstraints;
297  srcConstraints.reset(/*numDims=*/ivs.size(), /*numSymbols=*/0,
298  /*numLocals=*/0, ivs);
299  for (Value iv : ivs) {
300  AffineForOp loop = getForInductionVarOwner(iv);
301  assert(loop && "Expected affine for");
302  if (failed(srcConstraints.addAffineForOpDomain(loop)))
303  return llvm::None;
304  }
305 
306  // Create constraints for the slice using the dst loop nest information. We
307  // retrieve existing dst loops from the lbOperands.
308  SmallVector<Value, 8> consumerIVs;
309  for (Value lbOp : lbOperands[0])
310  if (getForInductionVarOwner(lbOp))
311  consumerIVs.push_back(lbOp);
312 
313  // Add empty IV Values for those new loops that are not equalities and,
314  // therefore, are not yet materialized in the IR.
315  for (int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)
316  consumerIVs.push_back(Value());
317 
318  FlatAffineValueConstraints sliceConstraints;
319  sliceConstraints.reset(/*numDims=*/consumerIVs.size(), /*numSymbols=*/0,
320  /*numLocals=*/0, consumerIVs);
321 
322  if (failed(sliceConstraints.addDomainFromSliceMaps(lbs, ubs, lbOperands[0])))
323  return llvm::None;
324 
325  if (srcConstraints.getNumDimVars() != sliceConstraints.getNumDimVars())
326  // Constraint dims are different. The integer set difference can't be
327  // computed so we don't know if the slice is maximal.
328  return llvm::None;
329 
330  // Compute the difference between the src loop nest and the slice integer
331  // sets.
332  PresburgerSet srcSet(srcConstraints);
333  PresburgerSet sliceSet(sliceConstraints);
334  PresburgerSet diffSet = srcSet.subtract(sliceSet);
335  return diffSet.isIntegerEmpty();
336 }
337 
338 unsigned MemRefRegion::getRank() const {
339  return memref.getType().cast<MemRefType>().getRank();
340 }
341 
343  SmallVectorImpl<int64_t> *shape, std::vector<SmallVector<int64_t, 4>> *lbs,
344  SmallVectorImpl<int64_t> *lbDivisors) const {
345  auto memRefType = memref.getType().cast<MemRefType>();
346  unsigned rank = memRefType.getRank();
347  if (shape)
348  shape->reserve(rank);
349 
350  assert(rank == cst.getNumDimVars() && "inconsistent memref region");
351 
352  // Use a copy of the region constraints that has upper/lower bounds for each
353  // memref dimension with static size added to guard against potential
354  // over-approximation from projection or union bounding box. We may not add
355  // this on the region itself since they might just be redundant constraints
356  // that will need non-trivials means to eliminate.
357  FlatAffineValueConstraints cstWithShapeBounds(cst);
358  for (unsigned r = 0; r < rank; r++) {
359  cstWithShapeBounds.addBound(FlatAffineValueConstraints::LB, r, 0);
360  int64_t dimSize = memRefType.getDimSize(r);
361  if (ShapedType::isDynamic(dimSize))
362  continue;
363  cstWithShapeBounds.addBound(FlatAffineValueConstraints::UB, r, dimSize - 1);
364  }
365 
366  // Find a constant upper bound on the extent of this memref region along each
367  // dimension.
368  int64_t numElements = 1;
369  int64_t diffConstant;
370  int64_t lbDivisor;
371  for (unsigned d = 0; d < rank; d++) {
373  Optional<int64_t> diff =
374  cstWithShapeBounds.getConstantBoundOnDimSize64(d, &lb, &lbDivisor);
375  if (diff.has_value()) {
376  diffConstant = diff.value();
377  assert(diffConstant >= 0 && "Dim size bound can't be negative");
378  assert(lbDivisor > 0);
379  } else {
380  // If no constant bound is found, then it can always be bound by the
381  // memref's dim size if the latter has a constant size along this dim.
382  auto dimSize = memRefType.getDimSize(d);
383  if (dimSize == -1)
384  return None;
385  diffConstant = dimSize;
386  // Lower bound becomes 0.
387  lb.resize(cstWithShapeBounds.getNumSymbolVars() + 1, 0);
388  lbDivisor = 1;
389  }
390  numElements *= diffConstant;
391  if (lbs) {
392  lbs->push_back(lb);
393  assert(lbDivisors && "both lbs and lbDivisor or none");
394  lbDivisors->push_back(lbDivisor);
395  }
396  if (shape) {
397  shape->push_back(diffConstant);
398  }
399  }
400  return numElements;
401 }
402 
404  AffineMap &ubMap) const {
405  assert(pos < cst.getNumDimVars() && "invalid position");
406  auto memRefType = memref.getType().cast<MemRefType>();
407  unsigned rank = memRefType.getRank();
408 
409  assert(rank == cst.getNumDimVars() && "inconsistent memref region");
410 
411  auto boundPairs = cst.getLowerAndUpperBound(
412  pos, /*offset=*/0, /*num=*/rank, cst.getNumDimAndSymbolVars(),
413  /*localExprs=*/{}, memRefType.getContext());
414  lbMap = boundPairs.first;
415  ubMap = boundPairs.second;
416  assert(lbMap && "lower bound for a region must exist");
417  assert(ubMap && "upper bound for a region must exist");
418  assert(lbMap.getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
419  assert(ubMap.getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
420 }
421 
423  assert(memref == other.memref);
424  return cst.unionBoundingBox(*other.getConstraints());
425 }
426 
427 /// Computes the memory region accessed by this memref with the region
428 /// represented as constraints symbolic/parametric in 'loopDepth' loops
429 /// surrounding opInst and any additional Function symbols.
430 // For example, the memref region for this load operation at loopDepth = 1 will
431 // be as below:
432 //
433 // affine.for %i = 0 to 32 {
434 // affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
435 // load %A[%ii]
436 // }
437 // }
438 //
439 // region: {memref = %A, write = false, {%i <= m0 <= %i + 7} }
440 // The last field is a 2-d FlatAffineValueConstraints symbolic in %i.
441 //
442 // TODO: extend this to any other memref dereferencing ops
443 // (dma_start, dma_wait).
445  const ComputationSliceState *sliceState,
446  bool addMemRefDimBounds) {
447  assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
448  "affine read/write op expected");
449 
450  MemRefAccess access(op);
451  memref = access.memref;
452  write = access.isStore();
453 
454  unsigned rank = access.getRank();
455 
456  LLVM_DEBUG(llvm::dbgs() << "MemRefRegion::compute: " << *op
457  << "depth: " << loopDepth << "\n";);
458 
459  // 0-d memrefs.
460  if (rank == 0) {
462  getLoopIVs(*op, &ivs);
463  assert(loopDepth <= ivs.size() && "invalid 'loopDepth'");
464  // The first 'loopDepth' IVs are symbols for this region.
465  ivs.resize(loopDepth);
466  SmallVector<Value, 4> regionSymbols;
467  extractForInductionVars(ivs, &regionSymbols);
468  // A 0-d memref has a 0-d region.
469  cst.reset(rank, loopDepth, /*numLocals=*/0, regionSymbols);
470  return success();
471  }
472 
473  // Build the constraints for this region.
474  AffineValueMap accessValueMap;
475  access.getAccessMap(&accessValueMap);
476  AffineMap accessMap = accessValueMap.getAffineMap();
477 
478  unsigned numDims = accessMap.getNumDims();
479  unsigned numSymbols = accessMap.getNumSymbols();
480  unsigned numOperands = accessValueMap.getNumOperands();
481  // Merge operands with slice operands.
482  SmallVector<Value, 4> operands;
483  operands.resize(numOperands);
484  for (unsigned i = 0; i < numOperands; ++i)
485  operands[i] = accessValueMap.getOperand(i);
486 
487  if (sliceState != nullptr) {
488  operands.reserve(operands.size() + sliceState->lbOperands[0].size());
489  // Append slice operands to 'operands' as symbols.
490  for (auto extraOperand : sliceState->lbOperands[0]) {
491  if (!llvm::is_contained(operands, extraOperand)) {
492  operands.push_back(extraOperand);
493  numSymbols++;
494  }
495  }
496  }
497  // We'll first associate the dims and symbols of the access map to the dims
498  // and symbols resp. of cst. This will change below once cst is
499  // fully constructed out.
500  cst.reset(numDims, numSymbols, 0, operands);
501 
502  // Add equality constraints.
503  // Add inequalities for loop lower/upper bounds.
504  for (unsigned i = 0; i < numDims + numSymbols; ++i) {
505  auto operand = operands[i];
506  if (auto loop = getForInductionVarOwner(operand)) {
507  // Note that cst can now have more dimensions than accessMap if the
508  // bounds expressions involve outer loops or other symbols.
509  // TODO: rewrite this to use getInstIndexSet; this way
510  // conditionals will be handled when the latter supports it.
511  if (failed(cst.addAffineForOpDomain(loop)))
512  return failure();
513  } else {
514  // Has to be a valid symbol.
515  auto symbol = operand;
516  assert(isValidSymbol(symbol));
517  // Check if the symbol is a constant.
518  if (auto *op = symbol.getDefiningOp()) {
519  if (auto constOp = dyn_cast<arith::ConstantIndexOp>(op)) {
520  cst.addBound(FlatAffineValueConstraints::EQ, symbol, constOp.value());
521  }
522  }
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<AffineForOp, 4> enclosingIVs;
556  getLoopIVs(*op, &enclosingIVs);
557  assert(loopDepth <= enclosingIVs.size() && "invalid loop depth");
558  enclosingIVs.resize(loopDepth);
560  cst.getValues(cst.getNumDimVars(), cst.getNumDimAndSymbolVars(), &vars);
561  for (auto var : vars) {
562  AffineForOp iv;
563  if ((iv = getForInductionVarOwner(var)) &&
564  !llvm::is_contained(enclosingIVs, iv)) {
565  cst.projectOut(var);
566  }
567  }
568 
569  // Project out any local variables (these would have been added for any
570  // mod/divs).
571  cst.projectOut(cst.getNumDimAndSymbolVars(), cst.getNumLocalVars());
572 
573  // Constant fold any symbolic variables.
574  cst.constantFoldVarRange(/*pos=*/cst.getNumDimVars(),
575  /*num=*/cst.getNumSymbolVars());
576 
577  assert(cst.getNumDimVars() == rank && "unexpected MemRefRegion format");
578 
579  // Add upper/lower bounds for each memref dimension with static size
580  // to guard against potential over-approximation from projection.
581  // TODO: Support dynamic memref dimensions.
582  if (addMemRefDimBounds) {
583  auto memRefType = memref.getType().cast<MemRefType>();
584  for (unsigned r = 0; r < rank; r++) {
585  cst.addBound(FlatAffineValueConstraints::LB, /*pos=*/r, /*value=*/0);
586  if (memRefType.isDynamicDim(r))
587  continue;
588  cst.addBound(FlatAffineValueConstraints::UB, /*pos=*/r,
589  memRefType.getDimSize(r) - 1);
590  }
591  }
592  cst.removeTrivialRedundancy();
593 
594  LLVM_DEBUG(llvm::dbgs() << "Memory region:\n");
595  LLVM_DEBUG(cst.dump());
596  return success();
597 }
598 
599 static unsigned getMemRefEltSizeInBytes(MemRefType memRefType) {
600  auto elementType = memRefType.getElementType();
601 
602  unsigned sizeInBits;
603  if (elementType.isIntOrFloat()) {
604  sizeInBits = elementType.getIntOrFloatBitWidth();
605  } else {
606  auto vectorType = elementType.cast<VectorType>();
607  sizeInBits =
608  vectorType.getElementTypeBitWidth() * vectorType.getNumElements();
609  }
610  return llvm::divideCeil(sizeInBits, 8);
611 }
612 
613 // Returns the size of the region.
615  auto memRefType = memref.getType().cast<MemRefType>();
616 
617  if (!memRefType.getLayout().isIdentity()) {
618  LLVM_DEBUG(llvm::dbgs() << "Non-identity layout map not yet supported\n");
619  return false;
620  }
621 
622  // Indices to use for the DmaStart op.
623  // Indices for the original memref being DMAed from/to.
624  SmallVector<Value, 4> memIndices;
625  // Indices for the faster buffer being DMAed into/from.
626  SmallVector<Value, 4> bufIndices;
627 
628  // Compute the extents of the buffer.
629  Optional<int64_t> numElements = getConstantBoundingSizeAndShape();
630  if (!numElements) {
631  LLVM_DEBUG(llvm::dbgs() << "Dynamic shapes not yet supported\n");
632  return None;
633  }
634  return getMemRefEltSizeInBytes(memRefType) * *numElements;
635 }
636 
637 /// Returns the size of memref data in bytes if it's statically shaped, None
638 /// otherwise. If the element of the memref has vector type, takes into account
639 /// size of the vector as well.
640 // TODO: improve/complete this when we have target data.
642  if (!memRefType.hasStaticShape())
643  return None;
644  auto elementType = memRefType.getElementType();
645  if (!elementType.isIntOrFloat() && !elementType.isa<VectorType>())
646  return None;
647 
648  uint64_t sizeInBytes = getMemRefEltSizeInBytes(memRefType);
649  for (unsigned i = 0, e = memRefType.getRank(); i < e; i++) {
650  sizeInBytes = sizeInBytes * memRefType.getDimSize(i);
651  }
652  return sizeInBytes;
653 }
654 
655 template <typename LoadOrStoreOp>
656 LogicalResult mlir::boundCheckLoadOrStoreOp(LoadOrStoreOp loadOrStoreOp,
657  bool emitError) {
658  static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,
660  "argument should be either a AffineReadOpInterface or a "
661  "AffineWriteOpInterface");
662 
663  Operation *op = loadOrStoreOp.getOperation();
664  MemRefRegion region(op->getLoc());
665  if (failed(region.compute(op, /*loopDepth=*/0, /*sliceState=*/nullptr,
666  /*addMemRefDimBounds=*/false)))
667  return success();
668 
669  LLVM_DEBUG(llvm::dbgs() << "Memory region");
670  LLVM_DEBUG(region.getConstraints()->dump());
671 
672  bool outOfBounds = false;
673  unsigned rank = loadOrStoreOp.getMemRefType().getRank();
674 
675  // For each dimension, check for out of bounds.
676  for (unsigned r = 0; r < rank; r++) {
677  FlatAffineValueConstraints ucst(*region.getConstraints());
678 
679  // Intersect memory region with constraint capturing out of bounds (both out
680  // of upper and out of lower), and check if the constraint system is
681  // feasible. If it is, there is at least one point out of bounds.
682  SmallVector<int64_t, 4> ineq(rank + 1, 0);
683  int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
684  // TODO: handle dynamic dim sizes.
685  if (dimSize == -1)
686  continue;
687 
688  // Check for overflow: d_i >= memref dim size.
689  ucst.addBound(FlatAffineValueConstraints::LB, r, dimSize);
690  outOfBounds = !ucst.isEmpty();
691  if (outOfBounds && emitError) {
692  loadOrStoreOp.emitOpError()
693  << "memref out of upper bound access along dimension #" << (r + 1);
694  }
695 
696  // Check for a negative index.
697  FlatAffineValueConstraints lcst(*region.getConstraints());
698  std::fill(ineq.begin(), ineq.end(), 0);
699  // d_i <= -1;
701  outOfBounds = !lcst.isEmpty();
702  if (outOfBounds && emitError) {
703  loadOrStoreOp.emitOpError()
704  << "memref out of lower bound access along dimension #" << (r + 1);
705  }
706  }
707  return failure(outOfBounds);
708 }
709 
710 // Explicitly instantiate the template so that the compiler knows we need them!
711 template LogicalResult
713 template LogicalResult
715 
716 // Returns in 'positions' the Block positions of 'op' in each ancestor
717 // Block from the Block containing operation, stopping at 'limitBlock'.
718 static void findInstPosition(Operation *op, Block *limitBlock,
719  SmallVectorImpl<unsigned> *positions) {
720  Block *block = op->getBlock();
721  while (block != limitBlock) {
722  // FIXME: This algorithm is unnecessarily O(n) and should be improved to not
723  // rely on linear scans.
724  int instPosInBlock = std::distance(block->begin(), op->getIterator());
725  positions->push_back(instPosInBlock);
726  op = block->getParentOp();
727  block = op->getBlock();
728  }
729  std::reverse(positions->begin(), positions->end());
730 }
731 
732 // Returns the Operation in a possibly nested set of Blocks, where the
733 // position of the operation is represented by 'positions', which has a
734 // Block position for each level of nesting.
736  unsigned level, Block *block) {
737  unsigned i = 0;
738  for (auto &op : *block) {
739  if (i != positions[level]) {
740  ++i;
741  continue;
742  }
743  if (level == positions.size() - 1)
744  return &op;
745  if (auto childAffineForOp = dyn_cast<AffineForOp>(op))
746  return getInstAtPosition(positions, level + 1,
747  childAffineForOp.getBody());
748 
749  for (auto &region : op.getRegions()) {
750  for (auto &b : region)
751  if (auto *ret = getInstAtPosition(positions, level + 1, &b))
752  return ret;
753  }
754  return nullptr;
755  }
756  return nullptr;
757 }
758 
759 // Adds loop IV bounds to 'cst' for loop IVs not found in 'ivs'.
762  for (unsigned i = 0, e = cst->getNumDimVars(); i < e; ++i) {
763  auto value = cst->getValue(i);
764  if (ivs.count(value) == 0) {
765  assert(isForInductionVar(value));
766  auto loop = getForInductionVarOwner(value);
767  if (failed(cst->addAffineForOpDomain(loop)))
768  return failure();
769  }
770  }
771  return success();
772 }
773 
774 /// Returns the innermost common loop depth for the set of operations in 'ops'.
775 // TODO: Move this to LoopUtils.
777  ArrayRef<Operation *> ops, SmallVectorImpl<AffineForOp> *surroundingLoops) {
778  unsigned numOps = ops.size();
779  assert(numOps > 0 && "Expected at least one operation");
780 
781  std::vector<SmallVector<AffineForOp, 4>> loops(numOps);
782  unsigned loopDepthLimit = std::numeric_limits<unsigned>::max();
783  for (unsigned i = 0; i < numOps; ++i) {
784  getLoopIVs(*ops[i], &loops[i]);
785  loopDepthLimit =
786  std::min(loopDepthLimit, static_cast<unsigned>(loops[i].size()));
787  }
788 
789  unsigned loopDepth = 0;
790  for (unsigned d = 0; d < loopDepthLimit; ++d) {
791  unsigned i;
792  for (i = 1; i < numOps; ++i) {
793  if (loops[i - 1][d] != loops[i][d])
794  return loopDepth;
795  }
796  if (surroundingLoops)
797  surroundingLoops->push_back(loops[i - 1][d]);
798  ++loopDepth;
799  }
800  return loopDepth;
801 }
802 
803 /// Computes in 'sliceUnion' the union of all slice bounds computed at
804 /// 'loopDepth' between all dependent pairs of ops in 'opsA' and 'opsB', and
805 /// then verifies if it is valid. Returns 'SliceComputationResult::Success' if
806 /// union was computed correctly, an appropriate failure otherwise.
809  unsigned loopDepth, unsigned numCommonLoops,
810  bool isBackwardSlice,
811  ComputationSliceState *sliceUnion) {
812  // Compute the union of slice bounds between all pairs in 'opsA' and
813  // 'opsB' in 'sliceUnionCst'.
814  FlatAffineValueConstraints sliceUnionCst;
815  assert(sliceUnionCst.getNumDimAndSymbolVars() == 0);
816  std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
817  for (auto *i : opsA) {
818  MemRefAccess srcAccess(i);
819  for (auto *j : opsB) {
820  MemRefAccess dstAccess(j);
821  if (srcAccess.memref != dstAccess.memref)
822  continue;
823  // Check if 'loopDepth' exceeds nesting depth of src/dst ops.
824  if ((!isBackwardSlice && loopDepth > getNestingDepth(i)) ||
825  (isBackwardSlice && loopDepth > getNestingDepth(j))) {
826  LLVM_DEBUG(llvm::dbgs() << "Invalid loop depth\n");
828  }
829 
830  bool readReadAccesses = isa<AffineReadOpInterface>(srcAccess.opInst) &&
831  isa<AffineReadOpInterface>(dstAccess.opInst);
832  FlatAffineValueConstraints dependenceConstraints;
833  // Check dependence between 'srcAccess' and 'dstAccess'.
835  srcAccess, dstAccess, /*loopDepth=*/numCommonLoops + 1,
836  &dependenceConstraints, /*dependenceComponents=*/nullptr,
837  /*allowRAR=*/readReadAccesses);
838  if (result.value == DependenceResult::Failure) {
839  LLVM_DEBUG(llvm::dbgs() << "Dependence check failed\n");
841  }
843  continue;
844  dependentOpPairs.emplace_back(i, j);
845 
846  // Compute slice bounds for 'srcAccess' and 'dstAccess'.
847  ComputationSliceState tmpSliceState;
848  mlir::getComputationSliceState(i, j, &dependenceConstraints, loopDepth,
849  isBackwardSlice, &tmpSliceState);
850 
851  if (sliceUnionCst.getNumDimAndSymbolVars() == 0) {
852  // Initialize 'sliceUnionCst' with the bounds computed in previous step.
853  if (failed(tmpSliceState.getAsConstraints(&sliceUnionCst))) {
854  LLVM_DEBUG(llvm::dbgs()
855  << "Unable to compute slice bound constraints\n");
857  }
858  assert(sliceUnionCst.getNumDimAndSymbolVars() > 0);
859  continue;
860  }
861 
862  // Compute constraints for 'tmpSliceState' in 'tmpSliceCst'.
863  FlatAffineValueConstraints tmpSliceCst;
864  if (failed(tmpSliceState.getAsConstraints(&tmpSliceCst))) {
865  LLVM_DEBUG(llvm::dbgs()
866  << "Unable to compute slice bound constraints\n");
868  }
869 
870  // Align coordinate spaces of 'sliceUnionCst' and 'tmpSliceCst' if needed.
871  if (!sliceUnionCst.areVarsAlignedWithOther(tmpSliceCst)) {
872 
873  // Pre-constraint var alignment: record loop IVs used in each constraint
874  // system.
875  SmallPtrSet<Value, 8> sliceUnionIVs;
876  for (unsigned k = 0, l = sliceUnionCst.getNumDimVars(); k < l; ++k)
877  sliceUnionIVs.insert(sliceUnionCst.getValue(k));
878  SmallPtrSet<Value, 8> tmpSliceIVs;
879  for (unsigned k = 0, l = tmpSliceCst.getNumDimVars(); k < l; ++k)
880  tmpSliceIVs.insert(tmpSliceCst.getValue(k));
881 
882  sliceUnionCst.mergeAndAlignVarsWithOther(/*offset=*/0, &tmpSliceCst);
883 
884  // Post-constraint var alignment: add loop IV bounds missing after
885  // var alignment to constraint systems. This can occur if one constraint
886  // system uses an loop IV that is not used by the other. The call
887  // to unionBoundingBox below expects constraints for each Loop IV, even
888  // if they are the unsliced full loop bounds added here.
889  if (failed(addMissingLoopIVBounds(sliceUnionIVs, &sliceUnionCst)))
891  if (failed(addMissingLoopIVBounds(tmpSliceIVs, &tmpSliceCst)))
893  }
894  // Compute union bounding box of 'sliceUnionCst' and 'tmpSliceCst'.
895  if (sliceUnionCst.getNumLocalVars() > 0 ||
896  tmpSliceCst.getNumLocalVars() > 0 ||
897  failed(sliceUnionCst.unionBoundingBox(tmpSliceCst))) {
898  LLVM_DEBUG(llvm::dbgs()
899  << "Unable to compute union bounding box of slice bounds\n");
901  }
902  }
903  }
904 
905  // Empty union.
906  if (sliceUnionCst.getNumDimAndSymbolVars() == 0)
908 
909  // Gather loops surrounding ops from loop nest where slice will be inserted.
911  for (auto &dep : dependentOpPairs) {
912  ops.push_back(isBackwardSlice ? dep.second : dep.first);
913  }
914  SmallVector<AffineForOp, 4> surroundingLoops;
915  unsigned innermostCommonLoopDepth =
916  getInnermostCommonLoopDepth(ops, &surroundingLoops);
917  if (loopDepth > innermostCommonLoopDepth) {
918  LLVM_DEBUG(llvm::dbgs() << "Exceeds max loop depth\n");
920  }
921 
922  // Store 'numSliceLoopIVs' before converting dst loop IVs to dims.
923  unsigned numSliceLoopIVs = sliceUnionCst.getNumDimVars();
924 
925  // Convert any dst loop IVs which are symbol variables to dim variables.
926  sliceUnionCst.convertLoopIVSymbolsToDims();
927  sliceUnion->clearBounds();
928  sliceUnion->lbs.resize(numSliceLoopIVs, AffineMap());
929  sliceUnion->ubs.resize(numSliceLoopIVs, AffineMap());
930 
931  // Get slice bounds from slice union constraints 'sliceUnionCst'.
932  sliceUnionCst.getSliceBounds(/*offset=*/0, numSliceLoopIVs,
933  opsA[0]->getContext(), &sliceUnion->lbs,
934  &sliceUnion->ubs);
935 
936  // Add slice bound operands of union.
937  SmallVector<Value, 4> sliceBoundOperands;
938  sliceUnionCst.getValues(numSliceLoopIVs,
939  sliceUnionCst.getNumDimAndSymbolVars(),
940  &sliceBoundOperands);
941 
942  // Copy src loop IVs from 'sliceUnionCst' to 'sliceUnion'.
943  sliceUnion->ivs.clear();
944  sliceUnionCst.getValues(0, numSliceLoopIVs, &sliceUnion->ivs);
945 
946  // Set loop nest insertion point to block start at 'loopDepth'.
947  sliceUnion->insertPoint =
948  isBackwardSlice
949  ? surroundingLoops[loopDepth - 1].getBody()->begin()
950  : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());
951 
952  // Give each bound its own copy of 'sliceBoundOperands' for subsequent
953  // canonicalization.
954  sliceUnion->lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
955  sliceUnion->ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
956 
957  // Check if the slice computed is valid. Return success only if it is verified
958  // that the slice is valid, otherwise return appropriate failure status.
959  Optional<bool> isSliceValid = sliceUnion->isSliceValid();
960  if (!isSliceValid) {
961  LLVM_DEBUG(llvm::dbgs() << "Cannot determine if the slice is valid\n");
963  }
964  if (!*isSliceValid)
966 
968 }
969 
970 // TODO: extend this to handle multiple result maps.
972  assert(lbMap.getNumResults() == 1 && "expected single result bound map");
973  assert(ubMap.getNumResults() == 1 && "expected single result bound map");
974  assert(lbMap.getNumDims() == ubMap.getNumDims());
975  assert(lbMap.getNumSymbols() == ubMap.getNumSymbols());
976  AffineExpr lbExpr(lbMap.getResult(0));
977  AffineExpr ubExpr(ubMap.getResult(0));
978  auto loopSpanExpr = simplifyAffineExpr(ubExpr - lbExpr, lbMap.getNumDims(),
979  lbMap.getNumSymbols());
980  auto cExpr = loopSpanExpr.dyn_cast<AffineConstantExpr>();
981  if (!cExpr)
982  return None;
983  return cExpr.getValue();
984 }
985 
986 // Builds a map 'tripCountMap' from AffineForOp to constant trip count for loop
987 // nest surrounding represented by slice loop bounds in 'slice'. Returns true
988 // on success, false otherwise (if a non-constant trip count was encountered).
989 // TODO: Make this work with non-unit step loops.
991  const ComputationSliceState &slice,
992  llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
993  unsigned numSrcLoopIVs = slice.ivs.size();
994  // Populate map from AffineForOp -> trip count
995  for (unsigned i = 0; i < numSrcLoopIVs; ++i) {
996  AffineForOp forOp = getForInductionVarOwner(slice.ivs[i]);
997  auto *op = forOp.getOperation();
998  AffineMap lbMap = slice.lbs[i];
999  AffineMap ubMap = slice.ubs[i];
1000  // If lower or upper bound maps are null or provide no results, it implies
1001  // that source loop was not at all sliced, and the entire loop will be a
1002  // part of the slice.
1003  if (!lbMap || lbMap.getNumResults() == 0 || !ubMap ||
1004  ubMap.getNumResults() == 0) {
1005  // The iteration of src loop IV 'i' was not sliced. Use full loop bounds.
1006  if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
1007  (*tripCountMap)[op] =
1008  forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
1009  continue;
1010  }
1011  Optional<uint64_t> maybeConstTripCount = getConstantTripCount(forOp);
1012  if (maybeConstTripCount.has_value()) {
1013  (*tripCountMap)[op] = maybeConstTripCount.value();
1014  continue;
1015  }
1016  return false;
1017  }
1018  Optional<uint64_t> tripCount = getConstDifference(lbMap, ubMap);
1019  // Slice bounds are created with a constant ub - lb difference.
1020  if (!tripCount.has_value())
1021  return false;
1022  (*tripCountMap)[op] = tripCount.value();
1023  }
1024  return true;
1025 }
1026 
1027 // Return the number of iterations in the given slice.
1029  const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {
1030  uint64_t iterCount = 1;
1031  for (const auto &count : sliceTripCountMap) {
1032  iterCount *= count.second;
1033  }
1034  return iterCount;
1035 }
1036 
1037 const char *const kSliceFusionBarrierAttrName = "slice_fusion_barrier";
1038 // Computes slice bounds by projecting out any loop IVs from
1039 // 'dependenceConstraints' at depth greater than 'loopDepth', and computes slice
1040 // bounds in 'sliceState' which represent the one loop nest's IVs in terms of
1041 // the other loop nest's IVs, symbols and constants (using 'isBackwardsSlice').
1043  Operation *depSourceOp, Operation *depSinkOp,
1044  FlatAffineValueConstraints *dependenceConstraints, unsigned loopDepth,
1045  bool isBackwardSlice, ComputationSliceState *sliceState) {
1046  // Get loop nest surrounding src operation.
1047  SmallVector<AffineForOp, 4> srcLoopIVs;
1048  getLoopIVs(*depSourceOp, &srcLoopIVs);
1049  unsigned numSrcLoopIVs = srcLoopIVs.size();
1050 
1051  // Get loop nest surrounding dst operation.
1052  SmallVector<AffineForOp, 4> dstLoopIVs;
1053  getLoopIVs(*depSinkOp, &dstLoopIVs);
1054  unsigned numDstLoopIVs = dstLoopIVs.size();
1055 
1056  assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||
1057  (isBackwardSlice && loopDepth <= numDstLoopIVs));
1058 
1059  // Project out dimensions other than those up to 'loopDepth'.
1060  unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;
1061  unsigned num =
1062  isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;
1063  dependenceConstraints->projectOut(pos, num);
1064 
1065  // Add slice loop IV values to 'sliceState'.
1066  unsigned offset = isBackwardSlice ? 0 : loopDepth;
1067  unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;
1068  dependenceConstraints->getValues(offset, offset + numSliceLoopIVs,
1069  &sliceState->ivs);
1070 
1071  // Set up lower/upper bound affine maps for the slice.
1072  sliceState->lbs.resize(numSliceLoopIVs, AffineMap());
1073  sliceState->ubs.resize(numSliceLoopIVs, AffineMap());
1074 
1075  // Get bounds for slice IVs in terms of other IVs, symbols, and constants.
1076  dependenceConstraints->getSliceBounds(offset, numSliceLoopIVs,
1077  depSourceOp->getContext(),
1078  &sliceState->lbs, &sliceState->ubs);
1079 
1080  // Set up bound operands for the slice's lower and upper bounds.
1081  SmallVector<Value, 4> sliceBoundOperands;
1082  unsigned numDimsAndSymbols = dependenceConstraints->getNumDimAndSymbolVars();
1083  for (unsigned i = 0; i < numDimsAndSymbols; ++i) {
1084  if (i < offset || i >= offset + numSliceLoopIVs) {
1085  sliceBoundOperands.push_back(dependenceConstraints->getValue(i));
1086  }
1087  }
1088 
1089  // Give each bound its own copy of 'sliceBoundOperands' for subsequent
1090  // canonicalization.
1091  sliceState->lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1092  sliceState->ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1093 
1094  // Set destination loop nest insertion point to block start at 'dstLoopDepth'.
1095  sliceState->insertPoint =
1096  isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()
1097  : std::prev(srcLoopIVs[loopDepth - 1].getBody()->end());
1098 
1099  llvm::SmallDenseSet<Value, 8> sequentialLoops;
1100  if (isa<AffineReadOpInterface>(depSourceOp) &&
1101  isa<AffineReadOpInterface>(depSinkOp)) {
1102  // For read-read access pairs, clear any slice bounds on sequential loops.
1103  // Get sequential loops in loop nest rooted at 'srcLoopIVs[0]'.
1104  getSequentialLoops(isBackwardSlice ? srcLoopIVs[0] : dstLoopIVs[0],
1105  &sequentialLoops);
1106  }
1107  auto getSliceLoop = [&](unsigned i) {
1108  return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];
1109  };
1110  auto isInnermostInsertion = [&]() {
1111  return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()
1112  : loopDepth >= dstLoopIVs.size());
1113  };
1114  llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;
1115  auto srcIsUnitSlice = [&]() {
1116  return (buildSliceTripCountMap(*sliceState, &sliceTripCountMap) &&
1117  (getSliceIterationCount(sliceTripCountMap) == 1));
1118  };
1119  // Clear all sliced loop bounds beginning at the first sequential loop, or
1120  // first loop with a slice fusion barrier attribute..
1121 
1122  for (unsigned i = 0; i < numSliceLoopIVs; ++i) {
1123  Value iv = getSliceLoop(i).getInductionVar();
1124  if (sequentialLoops.count(iv) == 0 &&
1125  getSliceLoop(i)->getAttr(kSliceFusionBarrierAttrName) == nullptr)
1126  continue;
1127  // Skip reset of bounds of reduction loop inserted in the destination loop
1128  // that meets the following conditions:
1129  // 1. Slice is single trip count.
1130  // 2. Loop bounds of the source and destination match.
1131  // 3. Is being inserted at the innermost insertion point.
1132  Optional<bool> isMaximal = sliceState->isMaximal();
1133  if (isLoopParallelAndContainsReduction(getSliceLoop(i)) &&
1134  isInnermostInsertion() && srcIsUnitSlice() && isMaximal && *isMaximal)
1135  continue;
1136  for (unsigned j = i; j < numSliceLoopIVs; ++j) {
1137  sliceState->lbs[j] = AffineMap();
1138  sliceState->ubs[j] = AffineMap();
1139  }
1140  break;
1141  }
1142 }
1143 
1144 /// Creates a computation slice of the loop nest surrounding 'srcOpInst',
1145 /// updates the slice loop bounds with any non-null bound maps specified in
1146 /// 'sliceState', and inserts this slice into the loop nest surrounding
1147 /// 'dstOpInst' at loop depth 'dstLoopDepth'.
1148 // TODO: extend the slicing utility to compute slices that
1149 // aren't necessarily a one-to-one relation b/w the source and destination. The
1150 // relation between the source and destination could be many-to-many in general.
1151 // TODO: the slice computation is incorrect in the cases
1152 // where the dependence from the source to the destination does not cover the
1153 // entire destination index set. Subtract out the dependent destination
1154 // iterations from destination index set and check for emptiness --- this is one
1155 // solution.
1156 AffineForOp
1158  unsigned dstLoopDepth,
1159  ComputationSliceState *sliceState) {
1160  // Get loop nest surrounding src operation.
1161  SmallVector<AffineForOp, 4> srcLoopIVs;
1162  getLoopIVs(*srcOpInst, &srcLoopIVs);
1163  unsigned numSrcLoopIVs = srcLoopIVs.size();
1164 
1165  // Get loop nest surrounding dst operation.
1166  SmallVector<AffineForOp, 4> dstLoopIVs;
1167  getLoopIVs(*dstOpInst, &dstLoopIVs);
1168  unsigned dstLoopIVsSize = dstLoopIVs.size();
1169  if (dstLoopDepth > dstLoopIVsSize) {
1170  dstOpInst->emitError("invalid destination loop depth");
1171  return AffineForOp();
1172  }
1173 
1174  // Find the op block positions of 'srcOpInst' within 'srcLoopIVs'.
1175  SmallVector<unsigned, 4> positions;
1176  // TODO: This code is incorrect since srcLoopIVs can be 0-d.
1177  findInstPosition(srcOpInst, srcLoopIVs[0]->getBlock(), &positions);
1178 
1179  // Clone src loop nest and insert it a the beginning of the operation block
1180  // of the loop at 'dstLoopDepth' in 'dstLoopIVs'.
1181  auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];
1182  OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());
1183  auto sliceLoopNest =
1184  cast<AffineForOp>(b.clone(*srcLoopIVs[0].getOperation()));
1185 
1186  Operation *sliceInst =
1187  getInstAtPosition(positions, /*level=*/0, sliceLoopNest.getBody());
1188  // Get loop nest surrounding 'sliceInst'.
1189  SmallVector<AffineForOp, 4> sliceSurroundingLoops;
1190  getLoopIVs(*sliceInst, &sliceSurroundingLoops);
1191 
1192  // Sanity check.
1193  unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();
1194  (void)sliceSurroundingLoopsSize;
1195  assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);
1196  unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;
1197  (void)sliceLoopLimit;
1198  assert(sliceLoopLimit >= sliceSurroundingLoopsSize);
1199 
1200  // Update loop bounds for loops in 'sliceLoopNest'.
1201  for (unsigned i = 0; i < numSrcLoopIVs; ++i) {
1202  auto forOp = sliceSurroundingLoops[dstLoopDepth + i];
1203  if (AffineMap lbMap = sliceState->lbs[i])
1204  forOp.setLowerBound(sliceState->lbOperands[i], lbMap);
1205  if (AffineMap ubMap = sliceState->ubs[i])
1206  forOp.setUpperBound(sliceState->ubOperands[i], ubMap);
1207  }
1208  return sliceLoopNest;
1209 }
1210 
1211 // Constructs MemRefAccess populating it with the memref, its indices and
1212 // opinst from 'loadOrStoreOpInst'.
1214  if (auto loadOp = dyn_cast<AffineReadOpInterface>(loadOrStoreOpInst)) {
1215  memref = loadOp.getMemRef();
1216  opInst = loadOrStoreOpInst;
1217  llvm::append_range(indices, loadOp.getMapOperands());
1218  } else {
1219  assert(isa<AffineWriteOpInterface>(loadOrStoreOpInst) &&
1220  "Affine read/write op expected");
1221  auto storeOp = cast<AffineWriteOpInterface>(loadOrStoreOpInst);
1222  opInst = loadOrStoreOpInst;
1223  memref = storeOp.getMemRef();
1224  llvm::append_range(indices, storeOp.getMapOperands());
1225  }
1226 }
1227 
1228 unsigned MemRefAccess::getRank() const {
1229  return memref.getType().cast<MemRefType>().getRank();
1230 }
1231 
1233  return isa<AffineWriteOpInterface>(opInst);
1234 }
1235 
1236 /// Returns the nesting depth of this statement, i.e., the number of loops
1237 /// surrounding this statement.
1239  Operation *currOp = op;
1240  unsigned depth = 0;
1241  while ((currOp = currOp->getParentOp())) {
1242  if (isa<AffineForOp>(currOp))
1243  depth++;
1244  }
1245  return depth;
1246 }
1247 
1248 /// Equal if both affine accesses are provably equivalent (at compile
1249 /// time) when considering the memref, the affine maps and their respective
1250 /// operands. The equality of access functions + operands is checked by
1251 /// subtracting fully composed value maps, and then simplifying the difference
1252 /// using the expression flattener.
1253 /// TODO: this does not account for aliasing of memrefs.
1254 bool MemRefAccess::operator==(const MemRefAccess &rhs) const {
1255  if (memref != rhs.memref)
1256  return false;
1257 
1258  AffineValueMap diff, thisMap, rhsMap;
1259  getAccessMap(&thisMap);
1260  rhs.getAccessMap(&rhsMap);
1261  AffineValueMap::difference(thisMap, rhsMap, &diff);
1262  return llvm::all_of(diff.getAffineMap().getResults(),
1263  [](AffineExpr e) { return e == 0; });
1264 }
1265 
1266 /// Returns the number of surrounding loops common to 'loopsA' and 'loopsB',
1267 /// where each lists loops from outer-most to inner-most in loop nest.
1269  SmallVector<AffineForOp, 4> loopsA, loopsB;
1270  getLoopIVs(a, &loopsA);
1271  getLoopIVs(b, &loopsB);
1272 
1273  unsigned minNumLoops = std::min(loopsA.size(), loopsB.size());
1274  unsigned numCommonLoops = 0;
1275  for (unsigned i = 0; i < minNumLoops; ++i) {
1276  if (loopsA[i].getOperation() != loopsB[i].getOperation())
1277  break;
1278  ++numCommonLoops;
1279  }
1280  return numCommonLoops;
1281 }
1282 
1284  Block::iterator start,
1285  Block::iterator end,
1286  int memorySpace) {
1287  SmallDenseMap<Value, std::unique_ptr<MemRefRegion>, 4> regions;
1288 
1289  // Walk this 'affine.for' operation to gather all memory regions.
1290  auto result = block.walk(start, end, [&](Operation *opInst) -> WalkResult {
1291  if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst)) {
1292  // Neither load nor a store op.
1293  return WalkResult::advance();
1294  }
1295 
1296  // Compute the memref region symbolic in any IVs enclosing this block.
1297  auto region = std::make_unique<MemRefRegion>(opInst->getLoc());
1298  if (failed(
1299  region->compute(opInst,
1300  /*loopDepth=*/getNestingDepth(&*block.begin())))) {
1301  return opInst->emitError("error obtaining memory region\n");
1302  }
1303 
1304  auto it = regions.find(region->memref);
1305  if (it == regions.end()) {
1306  regions[region->memref] = std::move(region);
1307  } else if (failed(it->second->unionBoundingBox(*region))) {
1308  return opInst->emitWarning(
1309  "getMemoryFootprintBytes: unable to perform a union on a memory "
1310  "region");
1311  }
1312  return WalkResult::advance();
1313  });
1314  if (result.wasInterrupted())
1315  return None;
1316 
1317  int64_t totalSizeInBytes = 0;
1318  for (const auto &region : regions) {
1319  Optional<int64_t> size = region.second->getRegionSize();
1320  if (!size.has_value())
1321  return None;
1322  totalSizeInBytes += size.value();
1323  }
1324  return totalSizeInBytes;
1325 }
1326 
1328  int memorySpace) {
1329  auto *forInst = forOp.getOperation();
1331  *forInst->getBlock(), Block::iterator(forInst),
1332  std::next(Block::iterator(forInst)), memorySpace);
1333 }
1334 
1335 /// Returns whether a loop is parallel and contains a reduction loop.
1337  SmallVector<LoopReduction> reductions;
1338  if (!isLoopParallel(forOp, &reductions))
1339  return false;
1340  return !reductions.empty();
1341 }
1342 
1343 /// Returns in 'sequentialLoops' all sequential loops in loop nest rooted
1344 /// at 'forOp'.
1345 void mlir::getSequentialLoops(AffineForOp forOp,
1346  llvm::SmallDenseSet<Value, 8> *sequentialLoops) {
1347  forOp->walk([&](Operation *op) {
1348  if (auto innerFor = dyn_cast<AffineForOp>(op))
1349  if (!isLoopParallel(innerFor))
1350  sequentialLoops->insert(innerFor.getInductionVar());
1351  });
1352 }
1353 
1355  FlatAffineValueConstraints fac(set);
1356  if (fac.isEmpty())
1357  return IntegerSet::getEmptySet(set.getNumDims(), set.getNumSymbols(),
1358  set.getContext());
1360 
1361  auto simplifiedSet = fac.getAsIntegerSet(set.getContext());
1362  assert(simplifiedSet && "guaranteed to succeed while roundtripping");
1363  return simplifiedSet;
1364 }
DependenceResult checkMemrefAccessDependence(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints, SmallVector< DependenceComponent, 2 > *dependenceComponents, bool allowRAR=false)
static Optional< int64_t > getMemoryFootprintBytes(Block &block, Block::iterator start, Block::iterator end, int memorySpace)
Definition: Utils.cpp:1283
Include the generated interface declarations.
bool isIntegerEmpty() const
Return true if all the sets in the union are known to be integer empty false otherwise.
iterator begin()
Definition: Block.h:132
void reset(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals=0)
Clears any existing data and reserves memory for the specified constraints.
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:30
unsigned getNumSymbols() const
Definition: AffineMap.cpp:310
unsigned getNumDims() const
Definition: AffineMap.cpp:306
Block represents an ordered list of Operations.
Definition: Block.h:29
SmallVector< Value, 4 > ivs
Definition: Utils.h:81
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:1327
void convertLoopIVSymbolsToDims()
Changes all symbol variables which are loop IVs to dim variables.
bool isLoopParallelAndContainsReduction(AffineForOp forOp)
Returns whether a loop is a parallel loop and contains a reduction loop.
Definition: Utils.cpp:1336
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value...
Definition: LogicalResult.h:72
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:1254
bool containsVar(Value mayBeVar) const
Returns true if an variable with the specified Value exists, false otherwise.
static Operation * getInstAtPosition(ArrayRef< unsigned > positions, unsigned level, Block *block)
Definition: Utils.cpp:735
bool buildSliceTripCountMap(const ComputationSliceState &slice, llvm::SmallDenseMap< Operation *, uint64_t, 8 > *tripCountMap)
Builds a map &#39;tripCountMap&#39; from AffineForOp to constant trip count for loop nest surrounding represe...
Definition: Utils.cpp:990
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value...
Definition: LogicalResult.h:68
bool isLoopParallel(AffineForOp forOp, SmallVectorImpl< LoopReduction > *parallelReductions=nullptr)
Returns true if `forOp&#39; is a parallel loop.
void getAccessMap(AffineValueMap *accessMap) const
Populates &#39;accessMap&#39; with composition of AffineApplyOps reachable from &#39;indices&#39;.
void getLoopIVs(Operation &op, SmallVectorImpl< AffineForOp > *loops)
Populates &#39;loops&#39; with IVs of the loops surrounding &#39;op&#39; ordered from the outermost &#39;affine...
Definition: Utils.cpp:35
unsigned getPosition() const
Definition: AffineExpr.cpp:311
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:144
static void difference(const AffineValueMap &a, const AffineValueMap &b, AffineValueMap *res)
Return the value map that is the difference of value maps &#39;a&#39; and &#39;b&#39;, represented as an affine map a...
Checks whether two accesses to the same memref access the same element.
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:342
unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)
Returns the number of surrounding loops common to both A and B.
Definition: Utils.cpp:1268
An integer constant appearing in affine expression.
Definition: AffineExpr.h:232
Operation::operand_range getMapOperands()
Returns affine map operands.
Enumerates different result statuses of slice computation by computeSliceUnion
Definition: Utils.h:65
void extractForInductionVars(ArrayRef< AffineForOp > forInsts, SmallVectorImpl< Value > *ivs)
Extracts the induction variables from a list of AffineForOps and places them in the output argument i...
Definition: AffineOps.cpp:2317
void mergeAndAlignVarsWithOther(unsigned offset, FlatAffineValueConstraints *other)
Merge and align the variables of this and other starting at offset, so that both constraint systems g...
static constexpr const bool value
Optional< bool > isMaximal() const
Returns true if the computation slice encloses all the iterations of the sliced loop nest...
Definition: Utils.cpp:288
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
Optional< uint64_t > getMemRefSizeInBytes(MemRefType memRefType)
Returns the size of memref data in bytes if it&#39;s statically shaped, None otherwise.
Definition: Utils.cpp:641
AffineExpr getResult(unsigned idx) const
Definition: AffineMap.cpp:323
MLIRContext * getContext()
Return the context this operation is associated with.
Definition: Operation.h:147
unsigned getNumInputs() const
Definition: AffineMap.cpp:315
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...
unsigned getInnermostCommonLoopDepth(ArrayRef< Operation *> ops, SmallVectorImpl< AffineForOp > *surroundingLoops=nullptr)
Returns the innermost common loop depth for the set of operations in &#39;ops&#39;.
Definition: Utils.cpp:776
U dyn_cast() const
Definition: AffineExpr.h:281
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
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:444
LogicalResult getAsConstraints(FlatAffineValueConstraints *cst)
Definition: Utils.cpp:80
OpListType::iterator iterator
Definition: Block.h:129
ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their associated operands for a ...
Definition: Utils.h:78
static LogicalResult addMissingLoopIVBounds(SmallPtrSet< Value, 8 > &ivs, FlatAffineValueConstraints *cst)
Definition: Utils.cpp:760
SmallVector< AffineMap, 4 > lbs
Definition: Utils.h:83
Optional< bool > isSliceValid()
Checks the validity of the slice computed.
Definition: Utils.cpp:218
static Optional< uint64_t > getConstDifference(AffineMap lbMap, AffineMap ubMap)
Definition: Utils.cpp:971
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:356
unsigned getNumOperands() const
static void findInstPosition(Operation *op, Block *limitBlock, SmallVectorImpl< unsigned > *positions)
Definition: Utils.cpp:718
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:165
Block::iterator insertPoint
Definition: Utils.h:91
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:232
static unsigned getMemRefEltSizeInBytes(MemRefType memRefType)
Definition: Utils.cpp:599
enum mlir::DependenceResult::ResultEnum value
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 ...
Operation::operand_range getMapOperands()
Returns affine map operands.
Base type for affine expression.
Definition: AffineExpr.h:68
unsigned getRank() const
Definition: Utils.cpp:1228
static WalkResult advance()
Definition: Visitors.h:51
unsigned getNumResults() const
Definition: AffineMap.cpp:314
Location getLoc()
The source location the operation was defined or derived from.
Definition: Operation.h:154
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
Value getMemRef()
Returns the memref operand to write to.
LogicalResult unionBoundingBox(const MemRefRegion &other)
Definition: Utils.cpp:422
void getEnclosingAffineOps(Operation &op, SmallVectorImpl< Operation *> *ops)
Populates &#39;ops&#39; with affine operations enclosing op ordered from outermost to innermost.
Definition: Utils.cpp:48
A multi-dimensional affine map Affine map&#39;s are immutable like Type&#39;s, and they are uniqued...
Definition: AffineMap.h:42
bool isForInductionVar(Value val)
Returns true if the provided value is the induction variable of a AffineForOp.
Definition: AffineOps.cpp:2298
RetT walk(FnT &&callback)
Walk the operations in this block.
Definition: Block.h:271
AffineMap getAffineMap() const
InFlightDiagnostic emitWarning(const Twine &message={})
Emit a warning about this operation, reporting up to any diagnostic handlers that may be listening...
Definition: Operation.cpp:237
A utility result that is used to signal how to proceed with an ongoing walk:
Definition: Visitors.h:34
ArrayRef< AffineExpr > getResults() const
Definition: AffineMap.cpp:319
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.
void getSequentialLoops(AffineForOp forOp, llvm::SmallDenseSet< Value, 8 > *sequentialLoops)
Returns in &#39;sequentialLoops&#39; all sequential loops in loop nest rooted at &#39;forOp&#39;. ...
Definition: Utils.cpp:1345
void removeTrivialRedundancy()
Removes duplicate constraints, trivially true constraints, and constraints that can be detected as re...
bool isa() const
Definition: AffineExpr.h:270
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
void projectOut(Value val)
Projects out the variable that is associate with Value.
LogicalResult unionBoundingBox(const FlatAffineValueConstraints &other)
Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this ...
AffineForOp getForInductionVarOwner(Value val)
Returns the loop parent of an induction variable.
Definition: AffineOps.cpp:2304
FlatAffineValueConstraints * getConstraints()
Definition: Utils.h:289
MemRefAccess(Operation *opInst)
Constructs a MemRefAccess from a load or store operation.
Definition: Utils.cpp:1213
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
SmallVector< AffineMap, 4 > ubs
Definition: Utils.h:85
SliceComputationResult computeSliceUnion(ArrayRef< Operation *> opsA, ArrayRef< Operation *> opsB, unsigned loopDepth, unsigned numCommonLoops, bool isBackwardSlice, ComputationSliceState *sliceUnion)
Computes in &#39;sliceUnion&#39; the union of all slice bounds computed at &#39;loopDepth&#39; between all dependent ...
Definition: Utils.cpp:808
const char *const kSliceFusionBarrierAttrName
Definition: Utils.cpp:1037
Optional< int64_t > getRegionSize()
Returns the size of this MemRefRegion in bytes.
Definition: Utils.cpp:614
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&#39;s ...
Definition: Utils.cpp:1042
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 ...
InFlightDiagnostic emitError(Location loc)
Utility method to emit an error message using this location.
bool isStore() const
Definition: Utils.cpp:1232
std::vector< SmallVector< Value, 4 > > ubOperands
Definition: Utils.h:89
PresburgerSet subtract(const PresburgerRelation &set) const
FlatAffineValueConstraints represents an extension of IntegerPolyhedron where each non-local variable...
uint64_t getSliceIterationCount(const llvm::SmallDenseMap< Operation *, uint64_t, 8 > &sliceTripCountMap)
Return the number of iterations for the slicetripCountMap provided.
Definition: Utils.cpp:1028
A dimensional identifier appearing in an affine expression.
Definition: AffineExpr.h:216
Specialization of arith.constant op that returns an integer of index type.
Definition: Arith.h:80
static VectorType vectorType(CodeGen &codegen, Type etp)
Constructs vector type.
bool isEmpty() const
Checks for emptiness by performing variable elimination on all variables, running the GCD test on eac...
LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst)
Adds to &#39;cst&#39; constraints which represent the original loop bounds on &#39;ivs&#39; in &#39;this&#39;.
Definition: Utils.cpp:66
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified &#39;affine.for&#39; operation&#39;s Value using IR i...
AffineForOp insertBackwardComputationSlice(Operation *srcOpInst, Operation *dstOpInst, unsigned dstLoopDepth, ComputationSliceState *sliceState)
Creates a clone of the computation contained in the loop nest surrounding &#39;srcOpInst&#39;, slices the iteration space of src loop based on slice bounds in &#39;sliceState&#39;, and inserts the computation slice at the beginning of the operation block of the loop at &#39;dstLoopDepth&#39; in the loop nest surrounding &#39;dstOpInst&#39;.
Definition: Utils.cpp:1157
Encapsulates a memref load or store access information.
Optional< uint64_t > getConstantTripCount(AffineForOp forOp)
Returns the trip count of the loop if it&#39;s a constant, None otherwise.
Value memref
Memref that this region corresponds to.
Definition: Utils.h:336
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th variable.
void dump() const
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes...
unsigned getRank() const
Returns the rank of the memref that this region corresponds to.
Definition: Utils.cpp:338
unsigned getNestingDepth(Operation *op)
Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation...
Definition: Utils.cpp:1238
A region of a memref&#39;s data space; this is typically constructed by analyzing load/store op&#39;s on this...
Definition: Utils.h:250
std::vector< SmallVector< Value, 4 > > lbOperands
Definition: Utils.h:87
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:403
static IntegerSet getEmptySet(unsigned numDims, unsigned numSymbols, MLIRContext *context)
Definition: IntegerSet.h:56
bool areVarsAlignedWithOther(const FlatAffineValueConstraints &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).
InFlightDiagnostic emitError(const Twine &message={})
Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...
Definition: Operation.cpp:225
This class helps build Operations.
Definition: Builders.h:197
IntegerSet simplifyIntegerSet(IntegerSet set)
Simplify the integer set by simplifying the underlying affine expressions by flattening and some simp...
Definition: Utils.cpp:1354
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool getClosedUB=false)
Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an...
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
Operation * opInst
Value getMemRef()
Returns the memref operand to read from.
Value getOperand(unsigned i) const
LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
An integer set representing a conjunction of one or more affine equalities and inequalities.
Definition: IntegerSet.h:44