Utils.cpp Source File (original) (raw)

25 #include "llvm/ADT/SetVector.h"

26 #include "llvm/ADT/SmallPtrSet.h"

27 #include "llvm/Support/Debug.h"

28 #include "llvm/Support/raw_ostream.h"

29 #include

31 #define DEBUG_TYPE "analysis-utils"

33 using namespace mlir;

34 using namespace affine;

35 using namespace presburger;

37 using llvm::SmallDenseMap;

46 if (auto forOp = dyn_cast(op)) {

47 forOps.push_back(forOp);

48 } else if (isa(op)) {

49 loadOpInsts.push_back(op);

50 } else if (isa(op)) {

51 storeOpInsts.push_back(op);

52 } else {

53 auto memInterface = dyn_cast(op);

54 if (!memInterface) {

57 return;

60 if (!isa(v.getType()))

61 continue;

63 memrefLoads.push_back(op);

64 memrefStores.push_back(op);

65 }

66 } else {

68 if (hasEffectMemoryEffects::Read(op))

69 memrefLoads.push_back(op);

70 if (hasEffectMemoryEffects::Write(op))

71 memrefStores.push_back(op);

72 if (hasEffectMemoryEffects::Free(op))

73 memrefFrees.push_back(op);

74 }

75 }

76 });

77 }

79 unsigned Node::getLoadOpCount(Value memref) const {

80 unsigned loadOpCount = 0;

83 if (auto affineLoad = dyn_cast(loadOp)) {

84 if (memref == affineLoad.getMemRef())

85 ++loadOpCount;

86 } else if (hasEffectMemoryEffects::Read(loadOp, memref)) {

87 ++loadOpCount;

88 }

89 }

90 return loadOpCount;

91 }

94 unsigned Node::getStoreOpCount(Value memref) const {

95 unsigned storeOpCount = 0;

96 for (auto *storeOp : llvm::concat<Operation *const>(stores, memrefStores)) {

98 if (auto affineStore = dyn_cast(storeOp)) {

99 if (memref == affineStore.getMemRef())

100 ++storeOpCount;

101 } else if (hasEffectMemoryEffects::Write(const_cast<Operation *>(storeOp),

102 memref)) {

103 ++storeOpCount;

104 }

105 }

106 return storeOpCount;

107 }

108

109

110 unsigned Node::hasStore(Value memref) const {

111 return llvm::any_of(

112 llvm::concat<Operation *const>(stores, memrefStores),

114 if (auto affineStore = dyn_cast(storeOp)) {

115 if (memref == affineStore.getMemRef())

116 return true;

117 } else if (hasEffectMemoryEffects::Write(storeOp, memref)) {

118 return true;

119 }

120 return false;

121 });

122 }

123

124 unsigned Node::hasFree(Value memref) const {

125 return llvm::any_of(memrefFrees, [&](Operation *freeOp) {

126 return hasEffectMemoryEffects::Free(freeOp, memref);

127 });

128 }

129

130

131 void Node::getStoreOpsForMemref(Value memref,

133 for (Operation *storeOp : stores) {

134 if (memref == cast(storeOp).getMemRef())

135 storeOps->push_back(storeOp);

136 }

137 }

138

139

140 void Node::getLoadOpsForMemref(Value memref,

142 for (Operation *loadOp : loads) {

143 if (memref == cast(loadOp).getMemRef())

144 loadOps->push_back(loadOp);

145 }

146 }

147

148

149

150 void Node::getLoadAndStoreMemrefSet(

152 llvm::SmallDenseSet<Value, 2> loadMemrefs;

153 for (Operation *loadOp : loads) {

154 loadMemrefs.insert(cast(loadOp).getMemRef());

155 }

156 for (Operation *storeOp : stores) {

157 auto memref = cast(storeOp).getMemRef();

158 if (loadMemrefs.count(memref) > 0)

159 loadAndStoreMemrefSet->insert(memref);

160 }

161 }

162

163

164

165 template <typename... EffectTys>

167 auto memOp = dyn_cast(op);

168 if (!memOp) {

170

171 return;

172

174 if (isa(operand.getType()))

175 values.push_back(operand);

176 }

177 return;

178 }

180 memOp.getEffects(effects);

181 for (auto &effect : effects) {

182 Value effectVal = effect.getValue();

183 if (isa<EffectTys...>(effect.getEffect()) && effectVal &&

184 isa(effectVal.getType()))

185 values.push_back(effectVal);

186 };

187 }

188

189

190

191 static Node *

194 auto &nodes = mdg.nodes;

195

196

198 collector.collect(nodeOp);

199 unsigned newNodeId = mdg.nextNodeId++;

200 Node &node = nodes.insert({newNodeId, Node(newNodeId, nodeOp)}).first->second;

202 node.loads.push_back(op);

203 auto memref = cast(op).getMemRef();

204 memrefAccesses[memref].insert(node.id);

205 }

207 node.stores.push_back(op);

208 auto memref = cast(op).getMemRef();

209 memrefAccesses[memref].insert(node.id);

210 }

213 getEffectedValuesMemoryEffects::Read(op, effectedValues);

214 if (llvm::any_of(((ValueRange)effectedValues).getTypes(),

215 [](Type type) { return !isa(type); }))

216

217 return nullptr;

218 for (Value memref : effectedValues)

219 memrefAccesses[memref].insert(node.id);

220 node.memrefLoads.push_back(op);

221 }

224 getEffectedValuesMemoryEffects::Write(op, effectedValues);

225 if (llvm::any_of((ValueRange(effectedValues)).getTypes(),

226 [](Type type) { return !isa(type); }))

227 return nullptr;

228 for (Value memref : effectedValues)

229 memrefAccesses[memref].insert(node.id);

230 node.memrefStores.push_back(op);

231 }

234 getEffectedValuesMemoryEffects::Free(op, effectedValues);

235 if (llvm::any_of((ValueRange(effectedValues)).getTypes(),

236 [](Type type) { return !isa(type); }))

237 return nullptr;

238 for (Value memref : effectedValues)

239 memrefAccesses[memref].insert(node.id);

240 node.memrefFrees.push_back(op);

241 }

242

243 return &node;

244 }

245

247 LLVM_DEBUG(llvm::dbgs() << "--- Initializing MDG ---\n");

248

249

251

252

255 if (auto forOp = dyn_cast(op)) {

257 if (!node)

258 return false;

259 forToNodeMap[&op] = node->id;

260 } else if (isa(op)) {

261

262 Node node(nextNodeId++, &op);

263 node.loads.push_back(&op);

264 auto memref = cast(op).getMemRef();

265 memrefAccesses[memref].insert(node.id);

266 nodes.insert({node.id, node});

267 } else if (isa(op)) {

268

269 Node node(nextNodeId++, &op);

270 node.stores.push_back(&op);

271 auto memref = cast(op).getMemRef();

272 memrefAccesses[memref].insert(node.id);

273 nodes.insert({node.id, node});

274 } else if (op.getNumResults() > 0 && !op.use_empty()) {

275

276

278 if (!node)

279 return false;

281 (op.getNumRegions() == 0 || isa(op))) {

282

283

284

285

286

288 if (!node)

289 return false;

290 } else if (op.getNumRegions() != 0 && !isa(op)) {

291

292

293

294 LLVM_DEBUG(llvm::dbgs()

295 << "MDG init failed; unknown region-holding op found!\n");

296 return false;

297 }

298

299

300

301 }

302

303 LLVM_DEBUG(llvm::dbgs() << "Created " << nodes.size() << " nodes\n");

304

305

306

307 for (auto &idAndNode : nodes) {

308 const Node &node = idAndNode.second;

309

310 if (!node.stores.empty())

311 continue;

315

316 if (block.getParent()->findAncestorOpInRegion(*user)->getBlock() !=

317 &block)

318 continue;

321

322

323 auto *it = llvm::find_if(loops, [&](AffineForOp loop) {

324 return loop->getBlock() == █

325 });

326 if (it == loops.end())

327 continue;

328 assert(forToNodeMap.count(*it) > 0 && "missing mapping");

329 unsigned userLoopNestId = forToNodeMap[*it];

330 addEdge(node.id, userLoopNestId, value);

331 }

332 }

333 }

334

335

336 for (auto &memrefAndList : memrefAccesses) {

337 unsigned n = memrefAndList.second.size();

338 Value srcMemRef = memrefAndList.first;

339

340 for (unsigned i = 0; i < n; ++i) {

341 unsigned srcId = memrefAndList.second[i];

342 Node *srcNode = getNode(srcId);

343 bool srcHasStoreOrFree =

344 srcNode->hasStore(srcMemRef) || srcNode->hasFree(srcMemRef);

345 for (unsigned j = i + 1; j < n; ++j) {

346 unsigned dstId = memrefAndList.second[j];

347 Node *dstNode = getNode(dstId);

348 bool dstHasStoreOrFree =

349 dstNode->hasStore(srcMemRef) || dstNode->hasFree(srcMemRef);

350 if (srcHasStoreOrFree || dstHasStoreOrFree)

351 addEdge(srcId, dstId, srcMemRef);

352 }

353 }

354 }

355 return true;

356 }

357

358

360 auto it = nodes.find(id);

361 assert(it != nodes.end());

362 return &it->second;

363 }

364

365

367 for (auto &idAndNode : nodes)

368 if (idAndNode.second.op == forOp)

369 return &idAndNode.second;

370 return nullptr;

371 }

372

373

375 Node node(nextNodeId++, op);

376 nodes.insert({node.id, node});

377 return node.id;

378 }

379

380

382

383 if (inEdges.count(id) > 0) {

385 for (auto &inEdge : oldInEdges) {

386 removeEdge(inEdge.id, id, inEdge.value);

387 }

388 }

389

390 if (outEdges.contains(id)) {

392 for (auto &outEdge : oldOutEdges) {

393 removeEdge(id, outEdge.id, outEdge.value);

394 }

395 }

396

397 inEdges.erase(id);

398 outEdges.erase(id);

399 nodes.erase(id);

400 }

401

402

403

405 const Node *node = getNode(id);

406 for (auto *storeOpInst : node->stores) {

407 auto memref = cast(storeOpInst).getMemRef();

408 auto *op = memref.getDefiningOp();

409

410 if (!op)

411 return true;

412

413

414 for (auto *user : memref.getUsers())

415 if (!isa(*user))

416 return true;

417 }

418 return false;

419 }

420

421

422

423

425 Value value) const {

426 if (!outEdges.contains(srcId) || !inEdges.contains(dstId)) {

427 return false;

428 }

429 bool hasOutEdge = llvm::any_of(outEdges.lookup(srcId), [=](const Edge &edge) {

430 return edge.id == dstId && (!value || edge.value == value);

431 });

432 bool hasInEdge = llvm::any_of(inEdges.lookup(dstId), [=](const Edge &edge) {

433 return edge.id == srcId && (!value || edge.value == value);

434 });

435 return hasOutEdge && hasInEdge;

436 }

437

438

441 if (!hasEdge(srcId, dstId, value)) {

442 outEdges[srcId].push_back({dstId, value});

443 inEdges[dstId].push_back({srcId, value});

444 if (isa(value.getType()))

445 memrefEdgeCount[value]++;

446 }

447 }

448

449

452 assert(inEdges.count(dstId) > 0);

453 assert(outEdges.count(srcId) > 0);

454 if (isa(value.getType())) {

455 assert(memrefEdgeCount.count(value) > 0);

456 memrefEdgeCount[value]--;

457 }

458

459 for (auto *it = inEdges[dstId].begin(); it != inEdges[dstId].end(); ++it) {

460 if ((*it).id == srcId && (*it).value == value) {

461 inEdges[dstId].erase(it);

462 break;

463 }

464 }

465

466 for (auto *it = outEdges[srcId].begin(); it != outEdges[srcId].end(); ++it) {

467 if ((*it).id == dstId && (*it).value == value) {

468 outEdges[srcId].erase(it);

469 break;

470 }

471 }

472 }

473

474

475

476

478 unsigned dstId) const {

479

481 worklist.push_back({srcId, 0});

482 Operation *dstOp = getNode(dstId)->op;

483

484 while (!worklist.empty()) {

485 auto &idAndIndex = worklist.back();

486

487 if (idAndIndex.first == dstId)

488 return true;

489

490

491 if (!outEdges.contains(idAndIndex.first) ||

492 idAndIndex.second == outEdges.lookup(idAndIndex.first).size()) {

493 worklist.pop_back();

494 continue;

495 }

496

497 const Edge edge = outEdges.lookup(idAndIndex.first)[idAndIndex.second];

498

499 ++idAndIndex.second;

500

501

502

504 if (!afterDst && edge.id != idAndIndex.first)

505 worklist.push_back({edge.id, 0});

506 }

507 return false;

508 }

509

510

511

513 Value memref) const {

514 unsigned inEdgeCount = 0;

515 for (const Edge &inEdge : inEdges.lookup(id)) {

516 if (inEdge.value == memref) {

517 const Node *srcNode = getNode(inEdge.id);

518

520 ++inEdgeCount;

521 }

522 }

523 return inEdgeCount;

524 }

525

526

527

529 Value memref) const {

530 unsigned outEdgeCount = 0;

531 for (const auto &outEdge : outEdges.lookup(id))

532 if (!memref || outEdge.value == memref)

533 ++outEdgeCount;

534 return outEdgeCount;

535 }

536

537

540 for (const Edge &edge : inEdges.lookup(id))

541

542

543

544 if (!isa(edge.value.getType()))

545 definingNodes.insert(edge.id);

546 }

547

548

549

550

553 unsigned dstId) const {

554 if (!outEdges.contains(srcId))

555 return getNode(dstId)->op;

556

557

559 gatherDefiningNodes(dstId, definingNodes);

560 if (llvm::any_of(definingNodes,

561 [&](unsigned id) { return hasDependencePath(srcId, id); })) {

562 LLVM_DEBUG(llvm::dbgs()

563 << "Can't fuse: a defining op with a user in the dst "

564 "loop has dependence from the src loop\n");

565 return nullptr;

566 }

567

568

570 for (auto &outEdge : outEdges.lookup(srcId))

571 if (outEdge.id != dstId)

572 srcDepInsts.insert(getNode(outEdge.id)->op);

573

574

576 for (auto &inEdge : inEdges.lookup(dstId))

577 if (inEdge.id != srcId)

578 dstDepInsts.insert(getNode(inEdge.id)->op);

579

580 Operation *srcNodeInst = getNode(srcId)->op;

581 Operation *dstNodeInst = getNode(dstId)->op;

582

583

584

585

586

587

588

589

590

591

592

594 std::optional firstSrcDepPos;

595 std::optional lastDstDepPos;

596 unsigned pos = 0;

600 if (srcDepInsts.count(op) > 0 && firstSrcDepPos == std::nullopt)

601 firstSrcDepPos = pos;

602 if (dstDepInsts.count(op) > 0)

603 lastDstDepPos = pos;

604 depInsts.push_back(op);

605 ++pos;

606 }

607

608 if (firstSrcDepPos.has_value()) {

609 if (lastDstDepPos.has_value()) {

610 if (*firstSrcDepPos <= *lastDstDepPos) {

611

612 return nullptr;

613 }

614 }

615

616 return depInsts[*firstSrcDepPos];

617 }

618

619

620 return dstNodeInst;

621 }

622

623

624

625

626

627

630 bool removeSrcId) {

631

632 if (inEdges.count(srcId) > 0) {

634 for (auto &inEdge : oldInEdges) {

635

636 if (!privateMemRefs.contains(inEdge.value))

637 addEdge(inEdge.id, dstId, inEdge.value);

638 }

639 }

640

641

642 if (outEdges.count(srcId) > 0) {

644 for (auto &outEdge : oldOutEdges) {

645

646 if (outEdge.id == dstId)

647 removeEdge(srcId, outEdge.id, outEdge.value);

648 else if (removeSrcId) {

649 addEdge(dstId, outEdge.id, outEdge.value);

650 removeEdge(srcId, outEdge.id, outEdge.value);

651 }

652 }

653 }

654

655

656

657 if (inEdges.count(dstId) > 0 && !privateMemRefs.empty()) {

659 for (auto &inEdge : oldInEdges)

660 if (privateMemRefs.count(inEdge.value) > 0)

661 removeEdge(inEdge.id, dstId, inEdge.value);

662 }

663 }

664

665

666

668

669

670

671 if (inEdges.count(sibId) > 0) {

673 for (auto &inEdge : oldInEdges) {

674 addEdge(inEdge.id, dstId, inEdge.value);

675 removeEdge(inEdge.id, sibId, inEdge.value);

676 }

677 }

678

679

680

681

682 if (outEdges.count(sibId) > 0) {

684 for (auto &outEdge : oldOutEdges) {

685 addEdge(dstId, outEdge.id, outEdge.value);

686 removeEdge(sibId, outEdge.id, outEdge.value);

687 }

688 }

689 }

690

691

697 Node *node = getNode(id);

698 llvm::append_range(node->loads, loads);

699 llvm::append_range(node->stores, stores);

700 llvm::append_range(node->memrefLoads, memrefLoads);

701 llvm::append_range(node->memrefStores, memrefStores);

702 llvm::append_range(node->memrefFrees, memrefFrees);

703 }

704

706 Node *node = getNode(id);

707 node->loads.clear();

708 node->stores.clear();

709 }

710

711

712

714 unsigned id, const std::function<void(Edge)> &callback) {

715 if (inEdges.count(id) > 0)

716 forEachMemRefEdge(inEdges[id], callback);

717 }

718

719

720

722 unsigned id, const std::function<void(Edge)> &callback) {

723 if (outEdges.count(id) > 0)

724 forEachMemRefEdge(outEdges[id], callback);

725 }

726

727

728

731 for (const auto &edge : edges) {

732

733 if (!isa(edge.value.getType()))

734 continue;

735 assert(nodes.count(edge.id) > 0);

736

737 if (!isa(getNode(edge.id)->op))

738 continue;

739

740 callback(edge);

741 }

742 }

743

745 os << "\nMemRefDependenceGraph\n";

746 os << "\nNodes:\n";

747 for (const auto &idAndNode : nodes) {

748 os << "Node: " << idAndNode.first << "\n";

749 auto it = inEdges.find(idAndNode.first);

750 if (it != inEdges.end()) {

751 for (const auto &e : it->second)

752 os << " InEdge: " << e.id << " " << e.value << "\n";

753 }

754 it = outEdges.find(idAndNode.first);

755 if (it != outEdges.end()) {

756 for (const auto &e : it->second)

757 os << " OutEdge: " << e.id << " " << e.value << "\n";

758 }

759 }

760 }

761

765 AffineForOp currAffineForOp;

766

767

769 if (auto currAffineForOp = dyn_cast(currOp))

770 loops->push_back(currAffineForOp);

771 currOp = currOp->getParentOp();

772 }

773 std::reverse(loops->begin(), loops->end());

774 }

775

778 ops->clear();

780

781

782

784 if (isa<AffineIfOp, AffineForOp, AffineParallelOp>(currOp))

785 ops->push_back(currOp);

787 }

788 std::reverse(ops->begin(), ops->end());

789 }

790

791

792

795 assert(!ivs.empty() && "Cannot have a slice without its IVs");

797 0, ivs);

798 for (Value iv : ivs) {

800 assert(loop && "Expected affine for");

802 return failure();

803 }

804 return success();

805 }

806

807

808 LogicalResult

810 assert(!lbOperands.empty());

811

812 unsigned numDims = ivs.size();

813

814 unsigned numSymbols = lbOperands[0].size();

815

817

818 values.append(lbOperands[0].begin(), lbOperands[0].end());

820

821

822

823 for (unsigned i = numDims, end = values.size(); i < end; ++i) {

824 Value value = values[i];

825 assert(cst->containsVar(value) && "value expected to be present");

827

829 cst->addBound(BoundType::EQ, value, cOp.value());

832 return failure();

833 }

834 }

835

836

837 LogicalResult ret = cst->addSliceBounds(ivs, lbs, ubs, lbOperands[0]);

838 assert(succeeded(ret) &&

839 "should not fail as we never have semi-affine slice maps");

840 (void)ret;

841 return success();

842 }

843

844

846 lbs.clear();

847 ubs.clear();

848 lbOperands.clear();

849 ubOperands.clear();

850 }

851

853 llvm::errs() << "\tIVs:\n";

854 for (Value iv : ivs)

855 llvm::errs() << "\t\t" << iv << "\n";

856

857 llvm::errs() << "\tLBs:\n";

859 llvm::errs() << "\t\t" << en.value() << "\n";

860 llvm::errs() << "\t\tOperands:\n";

861 for (Value lbOp : lbOperands[en.index()])

862 llvm::errs() << "\t\t\t" << lbOp << "\n";

863 }

864

865 llvm::errs() << "\tUBs:\n";

867 llvm::errs() << "\t\t" << en.value() << "\n";

868 llvm::errs() << "\t\tOperands:\n";

869 for (Value ubOp : ubOperands[en.index()])

870 llvm::errs() << "\t\t\t" << ubOp << "\n";

871 }

872 }

873

874

875

876

877

878

879 std::optional ComputationSliceState::isSliceMaximalFastCheck() const {

880 assert(lbs.size() == ubs.size() && !lbs.empty() && !ivs.empty() &&

881 "Unexpected number of lbs, ubs and ivs in slice");

882

883 for (unsigned i = 0, end = lbs.size(); i < end; ++i) {

886

887

888 if (!lbMap || !ubMap || lbMap.getNumResults() != 1 ||

891

892

893

894

895 isa(lbMap.getResult(0)))

896 return std::nullopt;

897

898

899

901 if (!result)

902 return std::nullopt;

903

904

905 AffineForOp dstLoop =

907 if (!dstLoop)

908 return std::nullopt;

909 AffineMap dstLbMap = dstLoop.getLowerBoundMap();

910 AffineMap dstUbMap = dstLoop.getUpperBoundMap();

911

912

914 assert(srcLoop && "Expected affine for");

915 AffineMap srcLbMap = srcLoop.getLowerBoundMap();

916 AffineMap srcUbMap = srcLoop.getUpperBoundMap();

917

918

919

922 return std::nullopt;

923

928 if (!isa(srcLbResult) ||

929 !isa(srcUbResult) ||

930 !isa(dstLbResult) ||

931 !isa(dstUbResult))

932 return std::nullopt;

933

934

935

936 if (srcLbResult != dstLbResult || srcUbResult != dstUbResult ||

937 srcLoop.getStep() != dstLoop.getStep())

938 return false;

939 }

940

941 return true;

942 }

943

944

945

946

948

949

950

951

952

953

954

955

956

957

958 std::optional isValidFastCheck = isSliceMaximalFastCheck();

959 if (isValidFastCheck && *isValidFastCheck)

960 return true;

961

962

964

965 if (failed(getSourceAsConstraints(srcConstraints))) {

966 LLVM_DEBUG(llvm::dbgs() << "Unable to compute source's domain\n");

967 return std::nullopt;

968 }

969

970

972 LLVM_DEBUG(llvm::dbgs() << "Cannot handle symbols in source domain\n");

973 return std::nullopt;

974 }

975

976

977

979 LLVM_DEBUG(llvm::dbgs() << "Cannot handle locals in source domain\n");

980 return std::nullopt;

981 }

982

983

984

986 if (failed(getAsConstraints(&sliceConstraints))) {

987 LLVM_DEBUG(llvm::dbgs() << "Unable to compute slice's domain\n");

988 return std::nullopt;

989 }

990

991

992

993 sliceConstraints.projectOut(ivs.size(),

994 sliceConstraints.getNumVars() - ivs.size());

995

996 LLVM_DEBUG(llvm::dbgs() << "Domain of the source of the slice:\n");

997 LLVM_DEBUG(srcConstraints.dump());

998 LLVM_DEBUG(llvm::dbgs() << "Domain of the slice if this fusion succeeds "

999 "(expressed in terms of its source's IVs):\n");

1000 LLVM_DEBUG(sliceConstraints.dump());

1001

1002

1006

1008 LLVM_DEBUG(llvm::dbgs() << "Incorrect slice\n");

1009 return false;

1010 }

1011 return true;

1012 }

1013

1014

1015

1016

1018

1019

1020 std::optional isMaximalFastCheck = isSliceMaximalFastCheck();

1021 if (isMaximalFastCheck)

1022 return isMaximalFastCheck;

1023

1024

1026 0,

1027 0, ivs);

1028 for (Value iv : ivs) {

1030 assert(loop && "Expected affine for");

1032 return std::nullopt;

1033 }

1034

1035

1036

1038 for (Value lbOp : lbOperands[0])

1040 consumerIVs.push_back(lbOp);

1041

1042

1043

1044 for (int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)

1045 consumerIVs.push_back(Value());

1046

1048 0,

1049 0, consumerIVs);

1050

1052 return std::nullopt;

1053

1055

1056

1057 return std::nullopt;

1058

1059

1060

1065 }

1066

1068 return cast(memref.getType()).getRank();

1069 }

1070

1073 auto memRefType = cast(memref.getType());

1074 MLIRContext *context = memref.getContext();

1075 unsigned rank = memRefType.getRank();

1076 if (shape)

1077 shape->reserve(rank);

1078

1079 assert(rank == cst.getNumDimVars() && "inconsistent memref region");

1080

1081

1082

1083

1084

1085

1087 for (unsigned r = 0; r < rank; r++) {

1088 cstWithShapeBounds.addBound(BoundType::LB, r, 0);

1089 int64_t dimSize = memRefType.getDimSize(r);

1090 if (ShapedType::isDynamic(dimSize))

1091 continue;

1092 cstWithShapeBounds.addBound(BoundType::UB, r, dimSize - 1);

1093 }

1094

1095

1096

1097 int64_t numElements = 1;

1098 int64_t diffConstant;

1099 for (unsigned d = 0; d < rank; d++) {

1101 std::optional<int64_t> diff =

1103 if (diff.has_value()) {

1104 diffConstant = *diff;

1105 assert(diffConstant >= 0 && "dim size bound cannot be negative");

1106 } else {

1107

1108

1109 auto dimSize = memRefType.getDimSize(d);

1110 if (ShapedType::isDynamic(dimSize))

1111 return std::nullopt;

1112 diffConstant = dimSize;

1113

1116 }

1117 numElements *= diffConstant;

1118

1119 if (lbs)

1120 lbs->push_back(lb);

1121 if (shape)

1122 shape->push_back(diffConstant);

1123 }

1124 return numElements;

1125 }

1126

1129 assert(pos < cst.getNumDimVars() && "invalid position");

1130 auto memRefType = cast(memref.getType());

1131 unsigned rank = memRefType.getRank();

1132

1133 assert(rank == cst.getNumDimVars() && "inconsistent memref region");

1134

1135 auto boundPairs = cst.getLowerAndUpperBound(

1136 pos, 0, rank, cst.getNumDimAndSymbolVars(),

1137 {}, memRefType.getContext());

1138 lbMap = boundPairs.first;

1139 ubMap = boundPairs.second;

1140 assert(lbMap && "lower bound for a region must exist");

1141 assert(ubMap && "upper bound for a region must exist");

1142 assert(lbMap.getNumInputs() == cst.getNumDimAndSymbolVars() - rank);

1143 assert(ubMap.getNumInputs() == cst.getNumDimAndSymbolVars() - rank);

1144 }

1145

1147 assert(memref == other.memref);

1148 return cst.unionBoundingBox(*other.getConstraints());

1149 }

1150

1151

1152

1153

1154

1155

1156

1157

1158

1159

1160

1161

1162

1163

1164

1165

1166

1167

1170 bool addMemRefDimBounds, bool dropLocalVars,

1171 bool dropOuterIvs) {

1172 assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&

1173 "affine read/write op expected");

1174

1176 memref = access.memref;

1177 write = access.isStore();

1178

1179 unsigned rank = access.getRank();

1180

1181 LLVM_DEBUG(llvm::dbgs() << "MemRefRegion::compute: " << *op

1182 << "\ndepth: " << loopDepth << "\n";);

1183

1184

1185 if (rank == 0) {

1188 assert(loopDepth <= ivs.size() && "invalid 'loopDepth'");

1189

1190 ivs.resize(loopDepth);

1191

1193 return success();

1194 }

1195

1196

1200

1201 unsigned numDims = accessMap.getNumDims();

1202 unsigned numSymbols = accessMap.getNumSymbols();

1203 unsigned numOperands = accessValueMap.getNumOperands();

1204

1206 operands.resize(numOperands);

1207 for (unsigned i = 0; i < numOperands; ++i)

1208 operands[i] = accessValueMap.getOperand(i);

1209

1210 if (sliceState != nullptr) {

1211 operands.reserve(operands.size() + sliceState->lbOperands[0].size());

1212

1213 for (auto extraOperand : sliceState->lbOperands[0]) {

1214 if (!llvm::is_contained(operands, extraOperand)) {

1215 operands.push_back(extraOperand);

1216 numSymbols++;

1217 }

1218 }

1219 }

1220

1221

1222

1224

1225

1226

1227 for (unsigned i = 0; i < numDims + numSymbols; ++i) {

1228 auto operand = operands[i];

1230

1231

1232

1233

1234 if (failed(cst.addAffineForOpDomain(affineFor)))

1235 return failure();

1237 if (failed(cst.addAffineParallelOpDomain(parallelOp)))

1238 return failure();

1240

1241 Value symbol = operand;

1243 cst.addBound(BoundType::EQ, symbol, constVal.value());

1244 } else {

1245 LLVM_DEBUG(llvm::dbgs() << "unknown affine dimensional value");

1246 return failure();

1247 }

1248 }

1249

1250

1251 if (sliceState != nullptr) {

1252

1253 for (auto operand : sliceState->lbOperands[0]) {

1254 if (failed(cst.addInductionVarOrTerminalSymbol(operand)))

1255 return failure();

1256 }

1257

1258 LogicalResult ret =

1259 cst.addSliceBounds(sliceState->ivs, sliceState->lbs, sliceState->ubs,

1261 assert(succeeded(ret) &&

1262 "should not fail as we never have semi-affine slice maps");

1263 (void)ret;

1264 }

1265

1266

1267 if (failed(cst.composeMap(&accessValueMap))) {

1268 op->emitError("getMemRefRegion: compose affine map failed");

1270 return failure();

1271 }

1272

1273

1274

1275

1276 cst.setDimSymbolSeparation(cst.getNumDimAndSymbolVars() - rank);

1277

1278

1279

1282 assert(loopDepth <= enclosingIVs.size() && "invalid loop depth");

1283 enclosingIVs.resize(loopDepth);

1285 cst.getValues(cst.getNumDimVars(), cst.getNumDimAndSymbolVars(), &vars);

1288 !llvm::is_contained(enclosingIVs, en.value())) {

1289 if (dropOuterIvs) {

1290 cst.projectOut(en.value());

1291 } else {

1292 unsigned varPosition;

1293 cst.findVar(en.value(), &varPosition);

1294 auto varKind = cst.getVarKindAt(varPosition);

1295 varPosition -= cst.getNumDimVars();

1296 cst.convertToLocal(varKind, varPosition, varPosition + 1);

1297 }

1298 }

1299 }

1300

1301

1302

1303 if (dropLocalVars)

1304 cst.projectOut(cst.getNumDimAndSymbolVars(), cst.getNumLocalVars());

1305

1306

1307 cst.constantFoldVarRange(cst.getNumDimVars(),

1308 cst.getNumSymbolVars());

1309

1310 assert(cst.getNumDimVars() == rank && "unexpected MemRefRegion format");

1311

1312

1313

1314

1315 if (addMemRefDimBounds) {

1316 auto memRefType = cast(memref.getType());

1317 for (unsigned r = 0; r < rank; r++) {

1318 cst.addBound(BoundType::LB, r, 0);

1319 if (memRefType.isDynamicDim(r))

1320 continue;

1321 cst.addBound(BoundType::UB, r, memRefType.getDimSize(r) - 1);

1322 }

1323 }

1324 cst.removeTrivialRedundancy();

1325

1326 LLVM_DEBUG(llvm::dbgs() << "Memory region:\n");

1327 LLVM_DEBUG(cst.dump());

1328 return success();

1329 }

1330

1331 std::optional<int64_t>

1333 auto elementType = memRefType.getElementType();

1334

1335 unsigned sizeInBits;

1336 if (elementType.isIntOrFloat()) {

1337 sizeInBits = elementType.getIntOrFloatBitWidth();

1338 } else if (auto vectorType = dyn_cast(elementType)) {

1339 if (vectorType.getElementType().isIntOrFloat())

1340 sizeInBits =

1341 vectorType.getElementTypeBitWidth() * vectorType.getNumElements();

1342 else

1343 return std::nullopt;

1344 } else {

1345 return std::nullopt;

1346 }

1348 }

1349

1350

1352 auto memRefType = cast(memref.getType());

1353

1354 if (!memRefType.getLayout().isIdentity()) {

1355 LLVM_DEBUG(llvm::dbgs() << "Non-identity layout map not yet supported\n");

1356 return false;

1357 }

1358

1359

1360 std::optional<int64_t> numElements = getConstantBoundingSizeAndShape();

1361 if (!numElements) {

1362 LLVM_DEBUG(llvm::dbgs() << "Dynamic shapes not yet supported\n");

1363 return std::nullopt;

1364 }

1366 if (!eltSize)

1367 return std::nullopt;

1368 return *eltSize * *numElements;

1369 }

1370

1371

1372

1373

1374

1375 std::optional<uint64_t>

1377 if (!memRefType.hasStaticShape())

1378 return std::nullopt;

1379 auto elementType = memRefType.getElementType();

1380 if (!elementType.isIntOrFloat() && !isa(elementType))

1381 return std::nullopt;

1382

1384 if (!sizeInBytes)

1385 return std::nullopt;

1386 for (unsigned i = 0, e = memRefType.getRank(); i < e; i++) {

1387 sizeInBytes = *sizeInBytes * memRefType.getDimSize(i);

1388 }

1389 return sizeInBytes;

1390 }

1391

1392 template

1395 static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,

1396 AffineWriteOpInterface>::value,

1397 "argument should be either a AffineReadOpInterface or a "

1398 "AffineWriteOpInterface");

1399

1400 Operation *op = loadOrStoreOp.getOperation();

1402 if (failed(region.compute(op, 0, nullptr,

1403 false)))

1404 return success();

1405

1406 LLVM_DEBUG(llvm::dbgs() << "Memory region");

1407 LLVM_DEBUG(region.getConstraints()->dump());

1408

1409 bool outOfBounds = false;

1410 unsigned rank = loadOrStoreOp.getMemRefType().getRank();

1411

1412

1413 for (unsigned r = 0; r < rank; r++) {

1415

1416

1417

1418

1420 int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);

1421

1422 if (dimSize == -1)

1423 continue;

1424

1425

1426 ucst.addBound(BoundType::LB, r, dimSize);

1427 outOfBounds = !ucst.isEmpty();

1429 loadOrStoreOp.emitOpError()

1430 << "memref out of upper bound access along dimension #" << (r + 1);

1431 }

1432

1433

1435 std::fill(ineq.begin(), ineq.end(), 0);

1436

1437 lcst.addBound(BoundType::UB, r, -1);

1438 outOfBounds = !lcst.isEmpty();

1440 loadOrStoreOp.emitOpError()

1441 << "memref out of lower bound access along dimension #" << (r + 1);

1442 }

1443 }

1444 return failure(outOfBounds);

1445 }

1446

1447

1448 template LogicalResult

1451 template LogicalResult

1454

1455

1456

1460 while (block != limitBlock) {

1461

1462

1463 int instPosInBlock = std::distance(block->begin(), op->getIterator());

1464 positions->push_back(instPosInBlock);

1467 }

1468 std::reverse(positions->begin(), positions->end());

1469 }

1470

1471

1472

1473

1475 unsigned level, Block *block) {

1476 unsigned i = 0;

1477 for (auto &op : *block) {

1478 if (i != positions[level]) {

1479 ++i;

1480 continue;

1481 }

1482 if (level == positions.size() - 1)

1483 return &op;

1484 if (auto childAffineForOp = dyn_cast(op))

1486 childAffineForOp.getBody());

1487

1488 for (auto &region : op.getRegions()) {

1489 for (auto &b : region)

1491 return ret;

1492 }

1493 return nullptr;

1494 }

1495 return nullptr;

1496 }

1497

1498

1501 for (unsigned i = 0, e = cst->getNumDimVars(); i < e; ++i) {

1502 auto value = cst->getValue(i);

1503 if (ivs.count(value) == 0) {

1507 return failure();

1508 }

1509 }

1510 return success();

1511 }

1512

1513

1514

1517 unsigned numOps = ops.size();

1518 assert(numOps > 0 && "Expected at least one operation");

1519

1520 std::vector<SmallVector<AffineForOp, 4>> loops(numOps);

1522 for (unsigned i = 0; i < numOps; ++i) {

1524 loopDepthLimit =

1525 std::min(loopDepthLimit, static_cast<unsigned>(loops[i].size()));

1526 }

1527

1528 unsigned loopDepth = 0;

1529 for (unsigned d = 0; d < loopDepthLimit; ++d) {

1530 unsigned i;

1531 for (i = 1; i < numOps; ++i) {

1532 if (loops[i - 1][d] != loops[i][d])

1533 return loopDepth;

1534 }

1535 if (surroundingLoops)

1536 surroundingLoops->push_back(loops[i - 1][d]);

1537 ++loopDepth;

1538 }

1539 return loopDepth;

1540 }

1541

1542

1543

1544

1545

1549 unsigned numCommonLoops, bool isBackwardSlice,

1551

1552

1555 std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;

1561 continue;

1562

1563 if ((!isBackwardSlice && loopDepth > getNestingDepth(i)) ||

1565 LLVM_DEBUG(llvm::dbgs() << "Invalid loop depth\n");

1567 }

1568

1569 bool readReadAccesses = isa(srcAccess.opInst) &&

1570 isa(dstAccess.opInst);

1572

1574 srcAccess, dstAccess, numCommonLoops + 1,

1575 &dependenceConstraints, nullptr,

1576 readReadAccesses);

1578 LLVM_DEBUG(llvm::dbgs() << "Dependence check failed\n");

1580 }

1582 continue;

1583 dependentOpPairs.emplace_back(i, j);

1584

1585

1588 loopDepth, isBackwardSlice,

1589 &tmpSliceState);

1590

1592

1593 if (failed(tmpSliceState.getAsConstraints(&sliceUnionCst))) {

1594 LLVM_DEBUG(llvm::dbgs()

1595 << "Unable to compute slice bound constraints\n");

1597 }

1599 continue;

1600 }

1601

1602

1605 LLVM_DEBUG(llvm::dbgs()

1606 << "Unable to compute slice bound constraints\n");

1608 }

1609

1610

1612

1613

1614

1616 for (unsigned k = 0, l = sliceUnionCst.getNumDimVars(); k < l; ++k)

1617 sliceUnionIVs.insert(sliceUnionCst.getValue(k));

1619 for (unsigned k = 0, l = tmpSliceCst.getNumDimVars(); k < l; ++k)

1620 tmpSliceIVs.insert(tmpSliceCst.getValue(k));

1621

1623

1624

1625

1626

1627

1628

1633 }

1634

1638 LLVM_DEBUG(llvm::dbgs()

1639 << "Unable to compute union bounding box of slice bounds\n");

1641 }

1642 }

1643 }

1644

1645

1647 LLVM_DEBUG(llvm::dbgs() << "empty slice union - unexpected\n");

1649 }

1650

1651

1653 for (auto &dep : dependentOpPairs) {

1654 ops.push_back(isBackwardSlice ? dep.second : dep.first);

1655 }

1657 unsigned innermostCommonLoopDepth =

1659 if (loopDepth > innermostCommonLoopDepth) {

1660 LLVM_DEBUG(llvm::dbgs() << "Exceeds max loop depth\n");

1662 }

1663

1664

1665 unsigned numSliceLoopIVs = sliceUnionCst.getNumDimVars();

1666

1667

1670 sliceUnion->lbs.resize(numSliceLoopIVs, AffineMap());

1671 sliceUnion->ubs.resize(numSliceLoopIVs, AffineMap());

1672

1673

1674 sliceUnionCst.getSliceBounds(0, numSliceLoopIVs,

1676 &sliceUnion->ubs);

1677

1678

1680 sliceUnionCst.getValues(numSliceLoopIVs,

1682 &sliceBoundOperands);

1683

1684

1685 sliceUnion->ivs.clear();

1686 sliceUnionCst.getValues(0, numSliceLoopIVs, &sliceUnion->ivs);

1687

1688

1689

1691 isBackwardSlice

1692 ? surroundingLoops[loopDepth - 1].getBody()->begin()

1693 : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());

1694

1695

1696

1697 sliceUnion->lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);

1698 sliceUnion->ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);

1699

1700

1701

1702 std::optional isSliceValid = sliceUnion->isSliceValid();

1703 if (!isSliceValid) {

1704 LLVM_DEBUG(llvm::dbgs() << "Cannot determine if the slice is valid\n");

1706 }

1707 if (!*isSliceValid)

1709

1711 }

1712

1713

1716 assert(lbMap.getNumResults() == 1 && "expected single result bound map");

1717 assert(ubMap.getNumResults() == 1 && "expected single result bound map");

1724 auto cExpr = dyn_cast(loopSpanExpr);

1725 if (!cExpr)

1726 return std::nullopt;

1727 return cExpr.getValue();

1728 }

1729

1730

1731

1732

1733

1736 llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {

1737 unsigned numSrcLoopIVs = slice.ivs.size();

1738

1739 for (unsigned i = 0; i < numSrcLoopIVs; ++i) {

1741 auto *op = forOp.getOperation();

1744

1745

1746

1747 if (!lbMap || lbMap.getNumResults() == 0 || !ubMap ||

1749

1750 if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {

1751 (*tripCountMap)[op] =

1752 forOp.getConstantUpperBound() - forOp.getConstantLowerBound();

1753 continue;

1754 }

1756 if (maybeConstTripCount.has_value()) {

1757 (*tripCountMap)[op] = *maybeConstTripCount;

1758 continue;

1759 }

1760 return false;

1761 }

1762 std::optional<uint64_t> tripCount = getConstDifference(lbMap, ubMap);

1763

1764 if (!tripCount.has_value())

1765 return false;

1766 (*tripCountMap)[op] = *tripCount;

1767 }

1768 return true;

1769 }

1770

1771

1773 const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {

1774 uint64_t iterCount = 1;

1775 for (const auto &count : sliceTripCountMap) {

1776 iterCount *= count.second;

1777 }

1778 return iterCount;

1779 }

1780

1782

1783

1784

1785

1790

1793 unsigned numSrcLoopIVs = srcLoopIVs.size();

1794

1795

1798 unsigned numDstLoopIVs = dstLoopIVs.size();

1799

1800 assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||

1801 (isBackwardSlice && loopDepth <= numDstLoopIVs));

1802

1803

1804 unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;

1805 unsigned num =

1806 isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;

1809

1810

1811 unsigned offset = isBackwardSlice ? 0 : loopDepth;

1812 unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;

1813 sliceCst.getValues(offset, offset + numSliceLoopIVs, &sliceState->ivs);

1814

1815

1816 sliceState->lbs.resize(numSliceLoopIVs, AffineMap());

1817 sliceState->ubs.resize(numSliceLoopIVs, AffineMap());

1818

1819

1821 &sliceState->lbs, &sliceState->ubs);

1822

1823

1826 for (unsigned i = 0; i < numDimsAndSymbols; ++i) {

1827 if (i < offset || i >= offset + numSliceLoopIVs)

1828 sliceBoundOperands.push_back(sliceCst.getValue(i));

1829 }

1830

1831

1832

1833 sliceState->lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);

1834 sliceState->ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);

1835

1836

1838 isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()

1839 : std::prev(srcLoopIVs[loopDepth - 1].getBody()->end());

1840

1841 llvm::SmallDenseSet<Value, 8> sequentialLoops;

1842 if (isa(depSourceOp) &&

1843 isa(depSinkOp)) {

1844

1845

1847 &sequentialLoops);

1848 }

1849 auto getSliceLoop = [&](unsigned i) {

1850 return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];

1851 };

1852 auto isInnermostInsertion = [&]() {

1853 return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()

1854 : loopDepth >= dstLoopIVs.size());

1855 };

1856 llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;

1857 auto srcIsUnitSlice = [&]() {

1860 };

1861

1862

1863

1864 for (unsigned i = 0; i < numSliceLoopIVs; ++i) {

1865 Value iv = getSliceLoop(i).getInductionVar();

1866 if (sequentialLoops.count(iv) == 0 &&

1868 continue;

1869

1870

1871

1872

1873

1874 std::optional isMaximal = sliceState->isMaximal();

1876 isInnermostInsertion() && srcIsUnitSlice() && isMaximal && *isMaximal)

1877 continue;

1878 for (unsigned j = i; j < numSliceLoopIVs; ++j) {

1881 }

1882 break;

1883 }

1884 }

1885

1886

1887

1888

1889

1890

1891

1892

1893

1894

1895

1896

1897

1901

1904 unsigned numSrcLoopIVs = srcLoopIVs.size();

1905

1906

1909 unsigned dstLoopIVsSize = dstLoopIVs.size();

1910 if (dstLoopDepth > dstLoopIVsSize) {

1911 dstOpInst->emitError("invalid destination loop depth");

1912 return AffineForOp();

1913 }

1914

1915

1917

1918 findInstPosition(srcOpInst, srcLoopIVs[0]->getBlock(), &positions);

1919

1920

1921

1922 auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];

1923 OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());

1924 auto sliceLoopNest =

1925 cast(b.clone(*srcLoopIVs[0].getOperation()));

1926

1928 getInstAtPosition(positions, 0, sliceLoopNest.getBody());

1929

1932

1933

1934 unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();

1935 (void)sliceSurroundingLoopsSize;

1936 assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);

1937 unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;

1938 (void)sliceLoopLimit;

1939 assert(sliceLoopLimit >= sliceSurroundingLoopsSize);

1940

1941

1942 for (unsigned i = 0; i < numSrcLoopIVs; ++i) {

1943 auto forOp = sliceSurroundingLoops[dstLoopDepth + i];

1945 forOp.setLowerBound(sliceState->lbOperands[i], lbMap);

1947 forOp.setUpperBound(sliceState->ubOperands[i], ubMap);

1948 }

1949 return sliceLoopNest;

1950 }

1951

1952

1953

1955 if (auto loadOp = dyn_cast(loadOrStoreOpInst)) {

1956 memref = loadOp.getMemRef();

1957 opInst = loadOrStoreOpInst;

1958 llvm::append_range(indices, loadOp.getMapOperands());

1959 } else {

1960 assert(isa(loadOrStoreOpInst) &&

1961 "Affine read/write op expected");

1962 auto storeOp = cast(loadOrStoreOpInst);

1963 opInst = loadOrStoreOpInst;

1964 memref = storeOp.getMemRef();

1965 llvm::append_range(indices, storeOp.getMapOperands());

1966 }

1967 }

1968

1970 return cast(memref.getType()).getRank();

1971 }

1972

1974 return isa(opInst);

1975 }

1976

1977

1978

1981 unsigned depth = 0;

1982 while ((currOp = currOp->getParentOp())) {

1983 if (isa(currOp))

1984 depth++;

1985 if (auto parOp = dyn_cast(currOp))

1986 depth += parOp.getNumDims();

1987 }

1988 return depth;

1989 }

1990

1991

1992

1993

1994

1995

1996

1998 if (memref != rhs.memref)

1999 return false;

2000

2002 getAccessMap(&thisMap);

2004 return thisMap == rhsMap;

2005 }

2006

2009 AffineForOp currAffineForOp;

2010

2011

2012 while (currOp) {

2013 if (AffineForOp currAffineForOp = dyn_cast(currOp))

2014 ivs.push_back(currAffineForOp.getInductionVar());

2015 else if (auto parOp = dyn_cast(currOp))

2016 llvm::append_range(ivs, parOp.getIVs());

2017 currOp = currOp->getParentOp();

2018 }

2019 std::reverse(ivs.begin(), ivs.end());

2020 }

2021

2022

2023

2029

2030 unsigned minNumLoops = std::min(loopsA.size(), loopsB.size());

2031 unsigned numCommonLoops = 0;

2032 for (unsigned i = 0; i < minNumLoops; ++i) {

2033 if (loopsA[i] != loopsB[i])

2034 break;

2035 ++numCommonLoops;

2036 }

2037 return numCommonLoops;

2038 }

2039

2043 int memorySpace) {

2044 SmallDenseMap<Value, std::unique_ptr, 4> regions;

2045

2046

2048 if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst)) {

2049

2051 }

2052

2053

2054 auto region = std::make_unique(opInst->getLoc());

2055 if (failed(

2056 region->compute(opInst,

2058 LLVM_DEBUG(opInst->emitError("error obtaining memory region"));

2059 return failure();

2060 }

2061

2062 auto [it, inserted] = regions.try_emplace(region->memref);

2063 if (inserted) {

2064 it->second = std::move(region);

2065 } else if (failed(it->second->unionBoundingBox(*region))) {

2067 "getMemoryFootprintBytes: unable to perform a union on a memory "

2068 "region"));

2069 return failure();

2070 }

2072 });

2073 if (result.wasInterrupted())

2074 return std::nullopt;

2075

2076 int64_t totalSizeInBytes = 0;

2077 for (const auto &region : regions) {

2078 std::optional<int64_t> size = region.second->getRegionSize();

2079 if (!size.has_value())

2080 return std::nullopt;

2081 totalSizeInBytes += *size;

2082 }

2083 return totalSizeInBytes;

2084 }

2085

2087 int memorySpace) {

2088 auto *forInst = forOp.getOperation();

2092 }

2093

2094

2098 return false;

2099 return !reductions.empty();

2100 }

2101

2102

2103

2105 AffineForOp forOp, llvm::SmallDenseSet<Value, 8> *sequentialLoops) {

2106 forOp->walk([&](Operation *op) {

2107 if (auto innerFor = dyn_cast(op))

2109 sequentialLoops->insert(innerFor.getInductionVar());

2110 });

2111 }

2112

2119

2121 assert(simplifiedSet && "guaranteed to succeed while roundtripping");

2122 return simplifiedSet;

2123 }

2124

2127 target =

2128 llvm::to_vector<4>(llvm::map_range(source, [](std::optional val) {

2129 return val.has_value() ? *val : Value();

2130 }));

2131 }

2132

2133

2134

2135

2136

2137

2138

2145

2148 for (unsigned i = syms.size(); i < newSyms.size(); ++i)

2150 return constraints.addBound(type, pos, alignedMap);

2151 }

2152

2153

2157 newResults.push_back(r + val);

2160 }

2161

2162

2163

2164

2165

2166

2167

2168

2169

2170

2171

2172

2173

2174

2175

2176

2177

2178

2179

2180

2181

2182

2183

2184

2185

2186

2187

2188

2189

2190

2191

2192

2193

2194

2195

2196

2197

2198

2201 bool isMin = isa(op);

2202 assert((isMin || isa(op)) && "expect AffineMin/MaxOp");

2206 isMin ? cast(op).getMap() : cast(op).getMap();

2209

2210

2211 unsigned dimOp = constraints.appendDimVar();

2212 unsigned dimOpBound = constraints.appendDimVar();

2213 unsigned resultDimStart = constraints.appendDimVar(numResults);

2214

2215

2216

2217 auto boundType = isMin ? BoundType::UB : BoundType::LB;

2218

2220 if (failed(

2221 alignAndAddBound(constraints, boundType, dimOp, mapLbUb, operands)))

2222 return failure();

2223

2224

2225

2227 constraints.getSliceBounds(dimOp, 1, ctx, &opLb, &opUb);

2228 AffineMap sliceBound = isMin ? opUb[0] : opLb[0];

2229

2230

2231 if (!sliceBound || sliceBound.getNumResults() != 1)

2232 return failure();

2233

2235

2236

2237

2238 AffineMap alignedBoundMap = boundMap.shiftDims(1, dimOp);

2239 if (failed(constraints.addBound(BoundType::EQ, dimOpBound, alignedBoundMap)))

2240 return failure();

2241

2242

2243

2244 if (constraints.isEmpty())

2245 return failure();

2246

2247

2248

2249

2250

2251

2252

2253

2254

2255

2256

2257 for (unsigned i = resultDimStart; i < resultDimStart + numResults; ++i) {

2259

2260

2261

2262

2263

2265 map.getSubMap({i - resultDimStart}), operands)))

2266 return failure();

2267

2268

2269

2270

2271

2273 ineq[dimOpBound] = isMin ? 1 : -1;

2274 ineq[i] = isMin ? -1 : 1;

2275 ineq[newConstr.getNumCols() - 1] = -1;

2277 if (!newConstr.isEmpty())

2278 return failure();

2279 }

2280

2281

2282 AffineMap newMap = alignedBoundMap;

2285

2286

2288

2290 continue;

2291 if (auto bound = constraints.getConstantBound64(BoundType::EQ, i)) {

2298 }

2299 }

2302 }

2303

2308 if (aScope != bScope)

2309 return nullptr;

2310

2311

2312

2313 auto getBlockAncestry = [&](Operation *op,

2316 do {

2317 ancestry.push_back(curOp->getBlock());

2319 break;

2321 } while (curOp);

2322 assert(curOp && "can't reach root op without passing through affine scope");

2323 std::reverse(ancestry.begin(), ancestry.end());

2324 };

2325

2327 getBlockAncestry(a, aAncestors);

2328 getBlockAncestry(b, bAncestors);

2329 assert(!aAncestors.empty() && !bAncestors.empty() &&

2330 "at least one Block ancestor expected");

2331

2332 Block *innermostCommonBlock = nullptr;

2333 for (unsigned a = 0, b = 0, e = aAncestors.size(), f = bAncestors.size();

2334 a < e && b < f; ++a, ++b) {

2335 if (aAncestors[a] != bAncestors[b])

2336 break;

2337 innermostCommonBlock = aAncestors[a];

2338 }

2339 return innermostCommonBlock;

2340 }

static std::optional< uint64_t > getConstDifference(AffineMap lbMap, AffineMap ubMap)

static void findInstPosition(Operation *op, Block *limitBlock, SmallVectorImpl< unsigned > *positions)

static Node * addNodeToMDG(Operation *nodeOp, MemRefDependenceGraph &mdg, DenseMap< Value, SetVector< unsigned >> &memrefAccesses)

Add op to MDG creating a new node and adding its memory accesses (affine or non-affine to memrefAcces...

const char *const kSliceFusionBarrierAttrName

static LogicalResult addMissingLoopIVBounds(SmallPtrSet< Value, 8 > &ivs, FlatAffineValueConstraints *cst)

static void getEffectedValues(Operation *op, SmallVectorImpl< Value > &values)

Returns the values that this op has a memref effect of type EffectTys on, not considering recursive e...

MemRefDependenceGraph::Node Node

static Operation * getInstAtPosition(ArrayRef< unsigned > positions, unsigned level, Block *block)

static std::optional< int64_t > getMemoryFootprintBytes(Block &block, Block::iterator start, Block::iterator end, int memorySpace)

static AffineMap addConstToResults(AffineMap map, int64_t val)

Add val to each result of map.

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...

static void unpackOptionalValues(ArrayRef< std::optional< Value >> source, SmallVector< Value > &target)

static MLIRContext * getContext(OpFoldResult val)

static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)

static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)

A dimensional identifier appearing in an affine expression.

unsigned getPosition() const

Base type for affine expression.

A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.

MLIRContext * getContext() const

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 ...

unsigned getNumSymbols() const

unsigned getNumDims() const

ArrayRef< AffineExpr > getResults() const

unsigned getNumResults() const

unsigned getNumInputs() const

AffineExpr getResult(unsigned idx) const

AffineMap replace(AffineExpr expr, AffineExpr replacement, unsigned numResultDims, unsigned numResultSyms) const

Sparse replace method.

AffineMap getSubMap(ArrayRef< unsigned > resultPos) const

Returns the map consisting of the resultPos subset.

Block represents an ordered list of Operations.

OpListType::iterator iterator

RetT walk(FnT &&callback)

Walk all nested operations, blocks (including this block) or regions, depending on the type of callba...

Operation * getParentOp()

Returns the closest surrounding operation that contains this block.

This class is a general helper class for creating context-global objects like types,...

AffineExpr getAffineSymbolExpr(unsigned position)

AffineExpr getAffineConstantExpr(int64_t constant)

AffineExpr getAffineDimExpr(unsigned position)

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...

std::optional< int64_t > getConstantBoundOnDimSize(MLIRContext *context, unsigned pos, AffineMap *lb=nullptr, AffineMap *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const

Returns a non-negative constant bound on the extent (upper bound - lower bound) of the specified vari...

FlatLinearValueConstraints represents an extension of FlatLinearConstraints where each non-local vari...

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...

SmallVector< std::optional< Value > > getMaybeValues() const

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.

void addBound(presburger::BoundType type, Value val, int64_t value)

Adds a constant bound for the variable associated with the given Value.

unsigned appendDimVar(ValueRange vals)

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).

unsigned appendSymbolVar(ValueRange vals)

An integer set representing a conjunction of one or more affine equalities and inequalities.

unsigned getNumDims() const

MLIRContext * getContext() const

static IntegerSet getEmptySet(unsigned numDims, unsigned numSymbols, MLIRContext *context)

unsigned getNumSymbols() const

MLIRContext is the top-level object for a collection of MLIR operations.

This class helps build Operations.

Operation * clone(Operation &op, IRMapping &mapper)

Creates a deep copy of the specified operation, remapping any operands that use values outside of the...

A trait of region holding operations that defines a new scope for polyhedral optimization purposes.

This trait indicates that the memory effects of an operation includes the effects of operations neste...

Operation is the basic unit of execution within MLIR.

bool hasTrait()

Returns true if the operation was registered with a particular trait, e.g.

bool isBeforeInBlock(Operation *other)

Given an operation 'other' that is within the same parent block, return whether the current operation...

InFlightDiagnostic emitWarning(const Twine &message={})

Emit a warning about this operation, reporting up to any diagnostic handlers that may be listening.

std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)

Walk the operation by calling the callback for each nested operation (including this one),...

MLIRContext * getContext()

Return the context this operation is associated with.

Location getLoc()

The source location the operation was defined or derived from.

Operation * getParentOp()

Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...

InFlightDiagnostic emitError(const Twine &message={})

Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...

Block * getBlock()

Returns the operation block that contains this operation.

MutableArrayRef< Region > getRegions()

Returns the regions held by this operation.

operand_range getOperands()

Returns an iterator on the underlying Value's.

user_range getUsers()

Returns a range of all users.

Region * getParentRegion()

Returns the region to which the instruction belongs.

result_range getResults()

This class contains a list of basic blocks and a link to the parent operation it is attached to.

Instances of the Type class are uniqued, have an immutable identifier and an optional mutable compone...

This class provides an abstraction over the different types of ranges over Values.

This class represents an instance of an SSA value in the MLIR system, representing a computable value...

Type getType() const

Return the type of this value.

A utility result that is used to signal how to proceed with an ongoing walk:

static WalkResult advance()

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

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...

void removeTrivialRedundancy()

Removes duplicate constraints, trivially true constraints, and constraints that can be detected as re...

unsigned getNumSymbolVars() const

std::optional< int64_t > getConstantBound64(BoundType type, unsigned pos) const

The same, but casts to int64_t.

unsigned getNumVars() const

unsigned getNumLocalVars() const

unsigned getNumDimAndSymbolVars() const

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.

void addInequality(ArrayRef< DynamicAPInt > inEq)

Adds an inequality (>= 0) from the coefficients specified in inEq.

unsigned getNumDimVars() const

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

std::optional< uint64_t > getConstantTripCount(AffineForOp forOp)

Returns the trip count of the loop if it's a constant, std::nullopt otherwise.

IntegerSet simplifyIntegerSet(IntegerSet set)

Simplify the integer set by simplifying the underlying affine expressions by flattening and some simp...

void getEnclosingAffineOps(Operation &op, SmallVectorImpl< Operation * > *ops)

Populates 'ops' with affine operations enclosing op ordered from outermost to innermost while stoppin...

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 ...

bool isAffineInductionVar(Value val)

Returns true if the provided value is the induction variable of an AffineForOp or AffineParallelOp.

bool isLoopParallelAndContainsReduction(AffineForOp forOp)

Returns whether a loop is a parallel loop and contains a reduction loop.

unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)

Returns the number of surrounding loops common to both A and B.

AffineForOp getForInductionVarOwner(Value val)

Returns the loop parent of an induction variable.

void getAffineIVs(Operation &op, SmallVectorImpl< Value > &ivs)

Populates 'ivs' with IVs of the surrounding affine.for and affine.parallel ops ordered from the outer...

void getSequentialLoops(AffineForOp forOp, llvm::SmallDenseSet< Value, 8 > *sequentialLoops)

Returns in 'sequentialLoops' all sequential loops in loop nest rooted at 'forOp'.

DependenceResult checkMemrefAccessDependence(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints=nullptr, SmallVector< DependenceComponent, 2 > *dependenceComponents=nullptr, bool allowRAR=false)

void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)

Modifies both map and operands in-place so as to:

bool isAffineForInductionVar(Value val)

Returns true if the provided value is the induction variable of an AffineForOp.

Region * getAffineAnalysisScope(Operation *op)

Returns the closest region enclosing op that is held by a non-affine operation; nullptr if there is n...

void getAffineForIVs(Operation &op, SmallVectorImpl< AffineForOp > *loops)

Populates 'loops' with IVs of the affine.for ops surrounding 'op' ordered from the outermost 'affine....

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...

unsigned getInnermostCommonLoopDepth(ArrayRef< Operation * > ops, SmallVectorImpl< AffineForOp > *surroundingLoops=nullptr)

Returns the innermost common loop depth for the set of operations in 'ops'.

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...

void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp, const 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 ...

AffineParallelOp getAffineParallelInductionVarOwner(Value val)

Returns true if the provided value is among the induction variables of an AffineParallelOp.

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,...

unsigned getNestingDepth(Operation *op)

Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation.

uint64_t getSliceIterationCount(const llvm::SmallDenseMap< Operation *, uint64_t, 8 > &sliceTripCountMap)

Return the number of iterations for the slicetripCountMap provided.

bool isLoopParallel(AffineForOp forOp, SmallVectorImpl< LoopReduction > *parallelReductions=nullptr)

Returns true if ‘forOp’ is a parallel loop.

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 ...

mlir::Block * findInnermostCommonBlockInScope(mlir::Operation *a, mlir::Operation *b)

Find the innermost common Block of a and b in the affine scope that a and b are part of.

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...

AffineForOp insertBackwardComputationSlice(Operation *srcOpInst, Operation *dstOpInst, unsigned dstLoopDepth, ComputationSliceState *sliceState)

Creates a clone of the computation contained in the loop nest surrounding 'srcOpInst',...

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...

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...

constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)

llvm::TypeSize divideCeil(llvm::TypeSize numerator, uint64_t denominator)

Divides the known min value of the numerator by the denominator and rounds the result up to the next ...

BoundType

The type of bound: equal, lower bound or upper bound.

Include the generated interface declarations.

std::optional< int64_t > getConstantIntValue(OpFoldResult ofr)

If ofr is a constant integer or an IntegerAttr, return the integer.

InFlightDiagnostic emitError(Location loc)

Utility method to emit an error message using this location.

bool isMemoryEffectFree(Operation *op)

Returns true if the given operation is free of memory effects.

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 ...

AffineExpr getAffineConstantExpr(int64_t constant, MLIRContext *context)

AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)

Simplify an affine expression by flattening and some amount of simple analysis.

ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their associated operands for a ...

std::optional< bool > isSliceValid() const

Checks the validity of the slice computed.

SmallVector< Value, 4 > ivs

LogicalResult getAsConstraints(FlatAffineValueConstraints *cst) const

LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst) const

Adds to 'cst' constraints which represent the original loop bounds on 'ivs' in 'this'.

std::vector< SmallVector< Value, 4 > > ubOperands

SmallVector< AffineMap, 4 > ubs

std::optional< bool > isMaximal() const

Returns true if the computation slice encloses all the iterations of the sliced loop nest.

SmallVector< AffineMap, 4 > lbs

Block::iterator insertPoint

std::vector< SmallVector< Value, 4 > > lbOperands

Checks whether two accesses to the same memref access the same element.

enum mlir::affine::DependenceResult::ResultEnum value

SmallVector< Operation *, 4 > memrefFrees

SmallVector< Operation *, 4 > loadOpInsts

SmallVector< Operation *, 4 > memrefStores

void collect(Operation *opToWalk)

SmallVector< Operation *, 4 > memrefLoads

SmallVector< Operation *, 4 > storeOpInsts

Encapsulates a memref load or store access information.

MemRefAccess(Operation *opInst)

Constructs a MemRefAccess from a load or store operation.

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...

SmallVector< Operation *, 4 > loads

SmallVector< Operation *, 4 > stores

unsigned hasFree(Value memref) const

SmallVector< Operation *, 4 > memrefLoads

SmallVector< Operation *, 4 > memrefStores

unsigned getStoreOpCount(Value memref) const

unsigned hasStore(Value memref) const

Returns true if there exists an operation with a write memory effect to memref in this node.

SmallVector< Operation *, 4 > memrefFrees

unsigned addNode(Operation *op)

bool writesToLiveInOrEscapingMemrefs(unsigned id) const

void removeEdge(unsigned srcId, unsigned dstId, Value value)

void addEdge(unsigned srcId, unsigned dstId, Value value)

DenseMap< unsigned, Node > nodes

void gatherDefiningNodes(unsigned id, DenseSet< unsigned > &definingNodes) const

Return all nodes which define SSA values used in node 'id'.

bool hasDependencePath(unsigned srcId, unsigned dstId) const

void clearNodeLoadAndStores(unsigned id)

const Node * getForOpNode(AffineForOp forOp) const

Operation * getFusedLoopNestInsertionPoint(unsigned srcId, unsigned dstId) const

void updateEdges(unsigned srcId, unsigned dstId, const DenseSet< Value > &privateMemRefs, bool removeSrcId)

void forEachMemRefInputEdge(unsigned id, const std::function< void(Edge)> &callback)

unsigned getOutEdgeCount(unsigned id, Value memref=nullptr) const

const Node * getNode(unsigned id) const

void removeNode(unsigned id)

void forEachMemRefOutputEdge(unsigned id, const std::function< void(Edge)> &callback)

void forEachMemRefEdge(ArrayRef< Edge > edges, const std::function< void(Edge)> &callback)

void addToNode(unsigned id, ArrayRef< Operation * > loads, ArrayRef< Operation * > stores, ArrayRef< Operation * > memrefLoads, ArrayRef< Operation * > memrefStores, ArrayRef< Operation * > memrefFrees)

unsigned getIncomingMemRefAccesses(unsigned id, Value memref) const

bool hasEdge(unsigned srcId, unsigned dstId, Value value=nullptr) const

void print(raw_ostream &os) const

A region of a memref's data space; this is typically constructed by analyzing load/store op's on this...

std::optional< int64_t > getConstantBoundingSizeAndShape(SmallVectorImpl< int64_t > *shape=nullptr, SmallVectorImpl< AffineMap > *lbs=nullptr) const

Returns a constant upper bound on the number of elements in this region if bounded by a known constan...

FlatAffineValueConstraints * getConstraints()

unsigned getRank() const

Returns the rank of the memref that this region corresponds to.

LogicalResult compute(Operation *op, unsigned loopDepth, const ComputationSliceState *sliceState=nullptr, bool addMemRefDimBounds=true, bool dropLocalVars=true, bool dropOuterIVs=true)

Computes the memory region accessed by this memref with the region represented as constraints symboli...

void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap, AffineMap &ubMap) const

Gets the lower and upper bound map for the dimensional variable at pos.

std::optional< int64_t > getRegionSize()

Returns the size of this MemRefRegion in bytes.

LogicalResult unionBoundingBox(const MemRefRegion &other)

Value memref

Memref that this region corresponds to.

Enumerates different result statuses of slice computation by computeSliceUnion

Eliminates variable at the specified position using Fourier-Motzkin variable elimination.