ValueBoundsOpInterface.cpp Source File (original) (raw)

9#include

17#include "llvm/ADT/APSInt.h"

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

19#include "llvm/Support/DebugLog.h"

21#define DEBUG_TYPE "value-bounds-op-interface"

23using namespace mlir;

27namespace mlir {

28#include "mlir/Interfaces/ValueBoundsOpInterface.cpp.inc"

29}

32 if (auto bbArg = dyn_cast(value))

35}

40 : mixedOffsets(offsets), mixedSizes(sizes), mixedStrides(strides) {

41 assert(offsets.size() == sizes.size() &&

42 "expected same number of offsets, sizes, strides");

43 assert(offsets.size() == strides.size() &&

44 "expected same number of offsets, sizes, strides");

45}

49 : mixedOffsets(offsets), mixedSizes(sizes) {

50 assert(offsets.size() == sizes.size() &&

51 "expected same number of offsets and sizes");

53 if (offsets.empty())

54 return;

55 MLIRContext *ctx = offsets.front().getContext();

56 mixedStrides.append(offsets.size(), Builder(ctx).getIndexAttr(1));

57}

66 if (auto val = llvm::dyn_cast_if_present(ofr)) {

67 APSInt intVal;

69 return intVal.getSExtValue();

70 return std::nullopt;

71 }

73 Attribute attr = llvm::dyn_cast_if_present(ofr);

74 if (auto intAttr = dyn_cast_or_null(attr))

75 return intAttr.getValue().getSExtValue();

76 return std::nullopt;

77}

89 std::optional<int64_t> dim) {

92 assert(!dim && "expected no dim for index-typed values");

93 map = AffineMap::get(0, 0,

94 b.getAffineConstantExpr(*constInt));

95 return;

96 }

97 Value value = cast(ofr);

98#ifndef NDEBUG

99 if (dim) {

100 assert(isa(value.getType()) && "expected shaped type");

101 } else {

102 assert(value.getType().isIndex() && "expected index type");

103 }

104#endif

105 map = AffineMap::get(0, 1,

106 b.getAffineSymbolExpr(0));

107 mapOperands.emplace_back(value, dim);

108}

109

112 assert(map.getNumResults() == 1 && "expected single result");

113

114

117 for (int64_t i = 0, e = map.getNumDims(); i < e; ++i)

118 dimReplacements.push_back(b.getAffineSymbolExpr(i));

119 for (int64_t i = 0, e = map.getNumSymbols(); i < e; ++i)

120 symReplacements.push_back(b.getAffineSymbolExpr(i + map.getNumDims()));

122 dimReplacements, symReplacements, 0,

123 map.getNumSymbols() + map.getNumDims());

124

125

127 for (auto [index, var] : llvm::enumerate(mapOperands)) {

128 assert(var.map.getNumResults() == 1 && "expected single result");

129 assert(var.map.getNumDims() == 0 && "expected only symbols");

131 for (auto valueDim : var.mapOperands) {

132 auto *it = llvm::find(this->mapOperands, valueDim);

133 if (it != this->mapOperands.end()) {

134

135 symReplacements.push_back(b.getAffineSymbolExpr(

136 std::distance(this->mapOperands.begin(), it)));

137 } else {

138

139 symReplacements.push_back(

140 b.getAffineSymbolExpr(this->mapOperands.size()));

141 this->mapOperands.push_back(valueDim);

142 }

143 }

144 replacements[b.getAffineSymbolExpr(index)] =

145 var.map.getResult(0).replaceSymbols(symReplacements);

146 }

147 this->map = tmpMap.replace(replacements, 0,

148 this->mapOperands.size());

149}

150

155

161 assert(stopCondition && "expected non-null stop condition");

162}

163

165

166#ifndef NDEBUG

169 assert(!dim.has_value() && "invalid dim value");

170 } else if (auto shapedType = dyn_cast(value.getType())) {

171 assert(*dim >= 0 && "invalid dim value");

172 if (shapedType.hasRank())

173 assert(*dim < shapedType.getRank() && "invalid dim value");

174 } else {

175 llvm_unreachable("unsupported type");

176 }

177}

178#endif

179

182

183

184

185

186

187 LogicalResult status = cstr.addBound(

188 type, pos,

193 if (failed(status)) {

194

195

196

197

198

199 LDBG() << "Failed to add bound: " << expr << "\n";

200 }

201}

202

204 std::optional<int64_t> dim) {

205#ifndef NDEBUG

207#endif

208

209

210

211

212

213 std::optional<int64_t> constSize = std::nullopt;

214 auto shapedType = dyn_cast(value.getType());

215 if (shapedType) {

216 if (shapedType.hasRank() && !shapedType.isDynamicDim(*dim))

217 constSize = shapedType.getDimSize(*dim);

219 constSize = *constInt;

220 }

221

222

223

226

227

228

229 if (constSize)

230 return builder.getAffineConstantExpr(*constSize);

232 }

233

234 if (constSize) {

235

236

237

238 (void)insert(value, dim, true, false);

239 if (shapedType)

240 bound(value)[*dim] == *constSize;

241 else

242 bound(value) == *constSize;

243 return builder.getAffineConstantExpr(*constSize);

244 }

245

246

247

248

250}

251

253 if (Value value = llvm::dyn_cast_if_present(ofr))

254 return getExpr(value, std::nullopt);

256 assert(constInt.has_value() && "expected Integer constant");

257 return builder.getAffineConstantExpr(*constInt);

258}

259

261 return builder.getAffineConstantExpr(constant);

262}

263

265 std::optional<int64_t> dim,

266 bool isSymbol, bool addToWorklist) {

267#ifndef NDEBUG

269#endif

270

273 int64_t pos = isSymbol ? cstr.appendVar(VarKind::Symbol)

274 : cstr.appendVar(VarKind::SetDim);

275 LDBG() << "Inserting constraint set column " << pos << " for: " << value

276 << " (dim: " << dim.value_or(kIndexValue)

279

283

284 if (addToWorklist) {

285 LDBG() << "Push to worklist: " << value

286 << " (dim: " << dim.value_or(kIndexValue) << ")";

288 }

289

290 return pos;

291}

292

294 int64_t pos = isSymbol ? cstr.appendVar(VarKind::Symbol)

295 : cstr.appendVar(VarKind::SetDim);

296 LDBG() << "Inserting anonymous constraint set column " << pos;

298

302 return pos;

303}

304

307 bool isSymbol) {

308 assert(map.getNumResults() == 1 && "expected affine map with one result");

310

311

312

313

314 auto mapper = [&](std::pair<Value, std::optional<int64_t>> v) {

315 return getExpr(v.first, v.second);

316 };

318 llvm::map_range(ArrayRef(operands).take_front(map.getNumDims()), mapper));

320 llvm::map_range(ArrayRef(operands).drop_front(map.getNumDims()), mapper));

324

325 return pos;

326}

327

329 return insert(var.map, var.mapOperands, isSymbol);

330}

331

333 std::optional<int64_t> dim) const {

334#ifndef NDEBUG

336 assert((isa(value) ||

337 cast(value).getOwner()->isEntryBlock()) &&

338 "unstructured control flow is not supported");

339#endif

340 LDBG() << "Getting pos for: " << value

341 << " (dim: " << dim.value_or(kIndexValue)

343 auto it =

346 return it->second;

347}

348

350 assert(pos >= 0 && pos < cstr.getNumDimAndSymbolVars() && "invalid position");

351 return pos < cstr.getNumDimVars()

352 ? builder.getAffineDimExpr(pos)

353 : builder.getAffineSymbolExpr(pos - cstr.getNumDimVars());

354}

355

357 std::optional<int64_t> dim) const {

358 auto it =

361}

362

364 LDBG() << "Processing value bounds worklist...";

369 "did not expect std::nullopt on worklist");

371 Value value = valueDim.first;

372 int64_t dim = valueDim.second;

373

374

376 auto shapedType = cast(value.getType());

377 if (shapedType.hasRank() && !shapedType.isDynamicDim(dim)) {

378 bound(value)[dim] == getExpr(shapedType.getDimSize(dim));

379 continue;

380 }

381 }

382

383

384 auto maybeDim = dim == kIndexValue ? std::nullopt : std::make_optional(dim);

386 LDBG() << "Stop condition met for: " << value << " (dim: " << maybeDim

387 << ")";

388 continue;

389 }

390

391

392

393 auto valueBoundsOp =

394 dyn_cast(getOwnerOfValue(value));

395 LDBG() << "Query value bounds for: " << value

397 if (valueBoundsOp) {

399 valueBoundsOp.populateBoundsForIndexValue(value, *this);

400 } else {

401 valueBoundsOp.populateBoundsForShapedValueDim(value, dim, *this);

402 }

403 continue;

404 }

405 LDBG() << "--> ValueBoundsOpInterface not implemented";

406

407

408

409

410 auto dstOp = value.getDefiningOp();

412 continue;

413 Value tiedOperand = dstOp.getTiedOpOperand(cast(value))->get();

414 bound(value)[dim] == getExpr(tiedOperand, dim);

415 }

416}

417

420 "invalid position");

421 cstr.projectOut(pos);

424 (void)erased;

425 assert(erased && "inconsistent reverse mapping");

426 }

428

432}

433

441

442

443 } else {

444 ++nextPos;

445 }

446 }

447}

448

450 std::optional<int64_t> except) {

454 ++nextPos;

455 } else {

457

458

459 }

460 }

461}

462

467 int64_t ubAdjustment = closedUB ? 0 : 1;

469 mapOperands.clear();

470

471

472

474 int64_t pos = cstr.insert(var, false);

475 assert(pos == 0 && "expected first column");

476 cstr.processWorklist();

477

478

479

481 auto maybeDim =

482 p.second == kIndexValue ? std::nullopt : std::make_optional(p.second);

484 });

485 cstr.projectOutAnonymous(pos);

486

487

489 cstr.cstr.getSliceBounds(pos, 1, ctx, &lb, &ub,

490 true);

491

492

493

494

495 if ((type != BoundType::LB) &&

496 (ub.empty() || [0] || ub[0].getNumResults() == 0))

497 return failure();

498

499 if ((type != BoundType::UB) &&

500 (lb.empty() || !lb[0] || lb[0].getNumResults() == 0))

501 return failure();

502

503

504 if (type != BoundType::LB)

505 assert(ub.size() == 1 && ub[0].getNumResults() == 1 &&

506 "multiple bounds not supported");

507 if (type != BoundType::UB)

508 assert(lb.size() == 1 && lb[0].getNumResults() == 1 &&

509 "multiple bounds not supported");

510

511

512 if (type == BoundType::EQ && ub[0] != lb[0])

513 return failure();

514

516 if (type == BoundType::EQ || type == BoundType::LB) {

518 } else {

519

521 ub[0].getResult(0) + ubAdjustment);

522 }

523

524

525 assert(cstr.cstr.getNumDimAndSymbolVars() == cstr.positionToValueDim.size() &&

526 "inconsistent mapping state");

528 int64_t numDims = 0, numSymbols = 0;

529 for (int64_t i = 0; i < cstr.cstr.getNumDimAndSymbolVars(); ++i) {

530

531 if (i == pos)

532 continue;

533

534

535 bool used = false;

536 bool isDim = i < cstr.cstr.getNumDimVars();

537 if (isDim) {

538 if (bound.isFunctionOfDim(i))

539 used = true;

540 } else {

541 if (bound.isFunctionOfSymbol(i - cstr.cstr.getNumDimVars()))

542 used = true;

543 }

544

545 if (!used) {

546

547 if (isDim) {

548 replacementDims.push_back(b.getAffineConstantExpr(0));

549 } else {

550 replacementSymbols.push_back(b.getAffineConstantExpr(0));

551 }

552 continue;

553 }

554

555 if (isDim) {

556 replacementDims.push_back(b.getAffineDimExpr(numDims++));

557 } else {

558 replacementSymbols.push_back(b.getAffineSymbolExpr(numSymbols++));

559 }

560

561 assert(cstr.positionToValueDim[i].has_value() &&

562 "cannot build affine map in terms of anonymous column");

564 Value value = valueDim.first;

565 int64_t dim = valueDim.second;

567

568

569 assert(value.getType().isIndex() && "expected index type");

570 mapOperands.push_back(std::make_pair(value, std::nullopt));

571 continue;

572 }

573

574 assert(cast(value.getType()).isDynamicDim(dim) &&

575 "expected dynamic dim");

576 mapOperands.push_back(std::make_pair(value, dim));

577 }

578

579 resultMap = bound.replaceDimsAndSymbols(replacementDims, replacementSymbols,

580 numDims, numSymbols);

582}

583

588 resultMap, mapOperands, type, var,

590 return llvm::is_contained(dependencies, std::make_pair(v, d));

591 },

592 closedUB);

593}

594

598

599

600

601 auto isIndependent = [&](Value v) {

607 if (!visited.insert(next).second)

608 continue;

609 if (llvm::is_contained(independencies, next))

610 return false;

611

613 if (!op)

614 continue;

616 }

617 return true;

618 };

619

620

622 resultMap, mapOperands, type, var,

624 return isIndependent(v);

625 },

626 closedUB);

627}

628

632

633

635 auto defaultStopCondition = [&](Value v, std::optional<int64_t> dim,

637 return cstr.cstr.getConstantBound64(type, pos).has_value();

638 };

639

642 pos = cstr.populateConstraints(var.map, var.mapOperands);

643 assert(pos == 0 && "expected `map` is the first column");

644

645

646 int64_t ubAdjustment = closedUB ? 0 : 1;

647 if (auto bound = cstr.cstr.getConstantBound64(type, pos))

648 return type == BoundType::UB ? *bound + ubAdjustment : *bound;

649 return failure();

650}

651

653 std::optional<int64_t> dim) {

654#ifndef NDEBUG

656#endif

657

658

659

661

662

664}

665

668 int64_t pos = insert(map, std::move(operands), false);

669

670

672 return pos;

673}

674

675FailureOr<int64_t>

677 std::optional<int64_t> dim1,

678 std::optional<int64_t> dim2) {

679#ifndef NDEBUG

682#endif

683

686 b.getAffineDimExpr(0) - b.getAffineDimExpr(1));

688 Variable(map, {{value1, dim1}, {value2, dim2}}));

689}

690

694

695

696

697

698

699

700

701

702

703 if (cstr.isEmpty()) {

704 LDBG() << "cannot compare value/dims: constraint system is already empty";

705 return false;

706 }

707

708

709 if (cmp == EQ)

712

713

715 if (cmp == LT || cmp == LE) {

716 ++eq[lhsPos];

717 --eq[rhsPos];

718 } else if (cmp == GT || cmp == GE) {

719 --eq[lhsPos];

720 ++eq[rhsPos];

721 } else {

722 llvm_unreachable("unsupported comparison operator");

723 }

724 if (cmp == LE || cmp == GE)

725 eq[cstr.getNumCols() - 1] -= 1;

726

727

728

729 int64_t ineqPos = cstr.getNumInequalities();

730 cstr.addInequality(eq);

731 bool isEmpty = cstr.isEmpty();

732 cstr.removeInequality(ineqPos);

733 return isEmpty;

734}

735

741 return true;

742 if (comparePos(lhsPos, negCmp, rhsPos))

743 return false;

744 return failure();

745 };

746 switch (cmp) {

756 std::optional le =

758 if (!le)

759 return failure();

760 if (!*le)

761 return false;

762 std::optional ge =

764 if (!ge)

765 return failure();

766 if (!*ge)

767 return false;

768 return true;

769 }

770 }

771 llvm_unreachable("invalid comparison operator");

772}

773

781

785 int64_t lhsPos = -1, rhsPos = -1;

788

789 if (size_t(lhsPos) >= cstr.positionToValueDim.size() ||

790 size_t(rhsPos) >= cstr.positionToValueDim.size())

791 return false;

792

793 return cstr.comparePos(lhsPos, cmp, rhsPos);

794 };

796 lhsPos = cstr.populateConstraints(lhs.map, lhs.mapOperands);

797 rhsPos = cstr.populateConstraints(rhs.map, rhs.mapOperands);

798 return cstr.comparePos(lhsPos, cmp, rhsPos);

799}

800

804 int64_t lhsPos = -1, rhsPos = -1;

807

808 if (size_t(lhsPos) >= cstr.positionToValueDim.size() ||

809 size_t(rhsPos) >= cstr.positionToValueDim.size())

810 return false;

811

812 FailureOr ordered = cstr.strongComparePos(lhsPos, cmp, rhsPos);

813 return failed(ordered);

814 };

816 lhsPos = cstr.populateConstraints(lhs.map, lhs.mapOperands);

817 rhsPos = cstr.populateConstraints(rhs.map, rhs.mapOperands);

818 return cstr.strongComparePos(lhsPos, cmp, rhsPos);

819}

820

825

830 "expected slices of same rank");

832 "expected slices of same rank");

834 "expected slices of same rank");

835

837 bool foundUnknownBound = false;

841 b.getAffineSymbolExpr(0) +

842 b.getAffineSymbolExpr(1) * b.getAffineSymbolExpr(2) -

843 b.getAffineSymbolExpr(3));

844 {

845

846

849 ofrOperands.push_back(slice1.getMixedSizes()[i]);

857 foundUnknownBound |= failed(constBound);

858 if (succeeded(constBound) && *constBound <= 0)

859 return false;

860 }

861 {

862

863

866 ofrOperands.push_back(slice2.getMixedSizes()[i]);

874 foundUnknownBound |= failed(constBound);

875 if (succeeded(constBound) && *constBound <= 0)

876 return false;

877 }

878 }

879

880

881

882 if (foundUnknownBound)

883 return failure();

884

885

886

887 return true;

888}

889

894 "expected slices of same rank");

896 "expected slices of same rank");

898 "expected slices of same rank");

899

900

901

902

903

904 for (auto [offset1, offset2] :

906 FailureOr equal = areEqual(offset1, offset2);

907 if (failed(equal))

908 return failure();

909 if (!equal.value())

910 return false;

911 }

912 for (auto [size1, size2] :

914 FailureOr equal = areEqual(size1, size2);

915 if (failed(equal))

916 return failure();

917 if (!equal.value())

918 return false;

919 }

920 for (auto [stride1, stride2] :

922 FailureOr equal = areEqual(stride1, stride2);

923 if (failed(equal))

924 return failure();

925 if (!equal.value())

926 return false;

927 }

928 return true;

929}

930

932 llvm::errs() << "==========\nColumns:\n";

933 llvm::errs() << "(column\tdim\tvalue)\n";

935 llvm::errs() << " " << index << "\t";

936 if (valueDim) {

938 llvm::errs() << "n/a\t";

939 } else {

940 llvm::errs() << valueDim->second << "\t";

941 }

943 if (OpResult result = dyn_cast(valueDim->first)) {

944 llvm::errs() << "(result " << result.getResultNumber() << ")";

945 } else {

946 llvm::errs() << "(bbarg "

947 << cast(valueDim->first).getArgNumber()

948 << ")";

949 }

950 llvm::errs() << "\n";

951 } else {

952 llvm::errs() << "n/a\tn/a\n";

953 }

954 }

955 llvm::errs() << "\nConstraint set:\n";

957 llvm::errs() << "==========\n";

958}

959

962 assert(!this->dim.has_value() && "dim was already set");

963 this->dim = dim;

964#ifndef NDEBUG

966#endif

967 return *this;

968}

969

971#ifndef NDEBUG

973#endif

974 cstr.addBound(BoundType::UB, cstr.getPos(value, this->dim), expr);

975}

976

980

984

986#ifndef NDEBUG

988#endif

989 cstr.addBound(BoundType::LB, cstr.getPos(value, this->dim), expr);

990}

991

993#ifndef NDEBUG

995#endif

996 cstr.addBound(BoundType::EQ, cstr.getPos(value, this->dim), expr);

997}

998

1002

1006

1010

1014

1018

1022

1026

1030

1034

Return true if permutation is a valid permutation of the outer_dims_perm (case OuterOrInnerPerm::Oute...

static Operation * getOwnerOfValue(Value value)

Definition ValueBoundsOpInterface.cpp:31

static void assertValidValueDim(Value value, std::optional< int64_t > dim)

Definition ValueBoundsOpInterface.cpp:167

Base type for affine expression.

AffineExpr replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements) const

This method substitutes any uses of dimensions and symbols (e.g.

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

static AffineMap get(MLIRContext *context)

Returns a zero result affine map with no dimensions or symbols: () -> ().

unsigned getNumDims() const

unsigned getNumResults() const

AffineMap replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements, unsigned numResultDims, unsigned numResultSyms) const

This method substitutes any uses of dimensions and symbols (e.g.

AffineExpr getResult(unsigned idx) const

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

Sparse replace method.

Attributes are known-constant values of operations.

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

A hyperrectangular slice, represented as a list of offsets, sizes and strides.

HyperrectangularSlice(ArrayRef< OpFoldResult > offsets, ArrayRef< OpFoldResult > sizes, ArrayRef< OpFoldResult > strides)

Definition ValueBoundsOpInterface.cpp:37

ArrayRef< OpFoldResult > getMixedStrides() const

ArrayRef< OpFoldResult > getMixedSizes() const

ArrayRef< OpFoldResult > getMixedOffsets() const

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

This class represents a single result from folding an operation.

MLIRContext * getContext() const

This is a value defined by a result of an operation.

Operation is the basic unit of execution within MLIR.

Operation * getParentOp()

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

OperationName getName()

The name of an operation is the key identifier for it.

operand_range getOperands()

Returns an iterator on the underlying Value's.

Helper class that builds a bound for a shaped value dimension or index-typed value.

void operator>(AffineExpr expr)

Definition ValueBoundsOpInterface.cpp:981

BoundBuilder & operator[](int64_t dim)

Specify a dimension, assuming that the underlying value is a shaped value.

Definition ValueBoundsOpInterface.cpp:961

void operator<=(AffineExpr expr)

Definition ValueBoundsOpInterface.cpp:977

void operator==(AffineExpr expr)

Definition ValueBoundsOpInterface.cpp:992

void operator<(AffineExpr expr)

Definition ValueBoundsOpInterface.cpp:970

void operator>=(AffineExpr expr)

Definition ValueBoundsOpInterface.cpp:985

A variable that can be added to the constraint set as a "column".

Variable(OpFoldResult ofr)

Construct a variable for an index-typed attribute or SSA value.

Definition ValueBoundsOpInterface.cpp:79

MLIRContext * getContext() const

static bool compare(const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)

Return "true" if "lhs cmp rhs" was proven to hold.

Definition ValueBoundsOpInterface.cpp:782

static FailureOr< bool > areEqual(const Variable &var1, const Variable &var2)

Compute whether the given variables are equal.

Definition ValueBoundsOpInterface.cpp:821

DenseMap< ValueDim, int64_t > valueDimToPosition

Reverse mapping of values/shape dimensions to columns.

void processWorklist()

Iteratively process all elements on the worklist until an index-typed value or shaped value meets sto...

Definition ValueBoundsOpInterface.cpp:363

bool addConservativeSemiAffineBounds

Should conservative bounds be added for semi-affine expressions.

AffineExpr getExpr(Value value, std::optional< int64_t > dim=std::nullopt)

Return an expression that represents the given index-typed value or shaped value dimension.

Definition ValueBoundsOpInterface.cpp:203

SmallVector< std::optional< ValueDim > > positionToValueDim

Mapping of columns to values/shape dimensions.

static LogicalResult computeIndependentBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, ValueRange independencies, bool closedUB=false)

Compute a bound in that is independent of all values in independencies.

Definition ValueBoundsOpInterface.cpp:595

static FailureOr< bool > areEquivalentSlices(MLIRContext *ctx, const HyperrectangularSlice &slice1, const HyperrectangularSlice &slice2)

Return "true" if the given slices are guaranteed to be equivalent.

Definition ValueBoundsOpInterface.cpp:890

void projectOut(int64_t pos)

Project out the given column in the constraint set.

Definition ValueBoundsOpInterface.cpp:418

std::function< bool( Value, std::optional< int64_t >, ValueBoundsConstraintSet &cstr)> StopConditionFn

The stop condition when traversing the backward slice of a shaped value/ index-type value.

ValueBoundsConstraintSet(MLIRContext *ctx, const StopConditionFn &stopCondition, bool addConservativeSemiAffineBounds=false)

Definition ValueBoundsOpInterface.cpp:156

static FailureOr< int64_t > computeConstantDelta(Value value1, Value value2, std::optional< int64_t > dim1=std::nullopt, std::optional< int64_t > dim2=std::nullopt)

Compute a constant delta between the given two values.

Definition ValueBoundsOpInterface.cpp:676

static llvm::FailureOr< bool > strongCompare(const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)

This function is similar to ValueBoundsConstraintSet::compare, except that it returns false if !...

Definition ValueBoundsOpInterface.cpp:801

void addBound(presburger::BoundType type, int64_t pos, AffineExpr expr)

Bound the given column in the underlying constraint set by the given expression.

Definition ValueBoundsOpInterface.cpp:180

StopConditionFn stopCondition

The current stop condition function.

ComparisonOperator

Comparison operator for ValueBoundsConstraintSet::compare.

BoundBuilder bound(Value value)

Add a bound for the given index-typed value or shaped value.

static LogicalResult computeBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, StopConditionFn stopCondition, bool closedUB=false)

Compute a bound for the given variable.

Definition ValueBoundsOpInterface.cpp:463

int64_t getPos(Value value, std::optional< int64_t > dim=std::nullopt) const

Return the column position of the given value/dimension.

Definition ValueBoundsOpInterface.cpp:332

int64_t insert(Value value, std::optional< int64_t > dim, bool isSymbol=true, bool addToWorklist=true)

Insert a value/dimension into the constraint set.

Definition ValueBoundsOpInterface.cpp:264

bool comparePos(int64_t lhsPos, ComparisonOperator cmp, int64_t rhsPos)

Return "true" if, based on the current state of the constraint system, "lhs cmp rhs" was proven to ho...

Definition ValueBoundsOpInterface.cpp:691

void dump() const

Debugging only: Dump the constraint set and the column-to-value/dim mapping to llvm::errs.

Definition ValueBoundsOpInterface.cpp:931

std::queue< int64_t > worklist

Worklist of values/shape dimensions that have not been processed yet.

FlatLinearConstraints cstr

Constraint system of equalities and inequalities.

bool isMapped(Value value, std::optional< int64_t > dim=std::nullopt) const

Return "true" if the given value/dim is mapped (i.e., has a corresponding column in the constraint sy...

Definition ValueBoundsOpInterface.cpp:356

llvm::FailureOr< bool > strongComparePos(int64_t lhsPos, ComparisonOperator cmp, int64_t rhsPos)

Return "true" if, based on the current state of the constraint system, "lhs cmp rhs" was proven to ho...

Definition ValueBoundsOpInterface.cpp:736

AffineExpr getPosExpr(int64_t pos)

Return an affine expression that represents column pos in the constraint set.

Definition ValueBoundsOpInterface.cpp:349

void projectOutAnonymous(std::optional< int64_t > except=std::nullopt)

Definition ValueBoundsOpInterface.cpp:449

static FailureOr< bool > areOverlappingSlices(MLIRContext *ctx, const HyperrectangularSlice &slice1, const HyperrectangularSlice &slice2)

Return "true" if the given slices are guaranteed to be overlapping.

Definition ValueBoundsOpInterface.cpp:826

std::pair< Value, int64_t > ValueDim

An index-typed value or the dimension of a shaped-type value.

void populateConstraints(Value value, std::optional< int64_t > dim)

Traverse the IR starting from the given value/dim and populate constraints as long as the stop condit...

Definition ValueBoundsOpInterface.cpp:652

Builder builder

Builder for constructing affine expressions.

bool populateAndCompare(const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)

Populate constraints for lhs/rhs (until the stop condition is met).

Definition ValueBoundsOpInterface.cpp:774

static FailureOr< int64_t > computeConstantBound(presburger::BoundType type, const Variable &var, const StopConditionFn &stopCondition=nullptr, bool closedUB=false)

Compute a constant bound for the given variable.

Definition ValueBoundsOpInterface.cpp:629

static constexpr int64_t kIndexValue

Dimension identifier to indicate a value is index-typed.

static LogicalResult computeDependentBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, ValueDimList dependencies, bool closedUB=false)

Compute a bound in terms of the values/dimensions in dependencies.

Definition ValueBoundsOpInterface.cpp:584

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

MLIRContext * getContext() const

Utility to get the associated MLIRContext that this value is defined in.

Type getType() const

Return the type of this value.

Operation * getDefiningOp() const

If this value is the result of an operation, return the operation that defines it.

The OpAsmOpInterface, see OpAsmInterface.td for more details.

BoundType

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

Include the generated interface declarations.

bool matchPattern(Value value, const Pattern &pattern)

Entry point for matching a pattern over a Value.

detail::constant_int_value_binder m_ConstantInt(IntegerAttr::ValueType *bind_value)

Matches a constant holding a scalar/vector/tensor integer (splat) and writes the integer value to bin...

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

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

llvm::DenseSet< ValueT, ValueInfoT > DenseSet

bool operator==(StringAttr lhs, std::nullptr_t)

Define comparisons for StringAttr against nullptr and itself to avoid the StringRef overloads from be...

llvm::DenseMap< KeyT, ValueT, KeyInfoT, BucketT > DenseMap

SmallVector< std::pair< Value, std::optional< int64_t > > > ValueDimList

AffineMap foldAttributesIntoMap(Builder &b, AffineMap map, ArrayRef< OpFoldResult > operands, SmallVector< Value > &remainingValues)

Fold all attributes among the given operands into the affine map.

llvm::function_ref< Fn > function_ref