AffineStructures.cpp Source File (original) (raw)

24 #include "llvm/ADT/STLExtras.h"

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

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

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

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

29 #include

31 #define DEBUG_TYPE "affine-structures"

33 using namespace mlir;

34 using namespace affine;

35 using namespace presburger;

37 LogicalResult

39 if (containsVar(val))

40 return success();

45 LLVM_DEBUG(llvm::dbgs()

46 << "only valid terminal symbols and affine IVs supported\n");

47 return failure();

48 }

51 appendDimVar(val);

52 if (failed(this->addAffineForOpDomain(loop))) {

53 LLVM_DEBUG(

54 loop.emitWarning("failed to add domain info to constraint system"));

55 return failure();

56 }

57 return success();

58 }

61 appendDimVar(parallel.getIVs());

62 if (failed(this->addAffineParallelOpDomain(parallel))) {

63 LLVM_DEBUG(parallel.emitWarning(

64 "failed to add domain info to constraint system"));

65 return failure();

66 }

67 return success();

68 }

71 appendSymbolVar(val);

74 addBound(BoundType::EQ, val, constOp.value());

75 return success();

76 }

78 LogicalResult

80 unsigned pos;

82 if (!findVar(forOp.getInductionVar(), &pos)) {

83 assert(false && "Value not found");

84 return failure();

85 }

87 int64_t step = forOp.getStepAsInt();

88 if (step != 1) {

89 if (!forOp.hasConstantLowerBound())

90 LLVM_DEBUG(forOp.emitWarning("domain conservatively approximated"));

91 else {

98 int64_t lb = forOp.getConstantLowerBound();

99 dividend[pos] = 1;

100 dividend.back() -= lb;

101 addLocalFloorDiv(dividend, step);

102

104 eq[pos] = 1;

105 eq.back() -= lb;

106

107 eq[getNumCols() - 2] = -step;

108 addEquality(eq);

109 }

110 }

111

112 if (forOp.hasConstantLowerBound()) {

113 addBound(BoundType::LB, pos, forOp.getConstantLowerBound());

114 } else {

115

116 if (failed(addBound(BoundType::LB, pos, forOp.getLowerBoundMap(),

117 forOp.getLowerBoundOperands())))

118 return failure();

119 }

120

121 if (forOp.hasConstantUpperBound()) {

122 addBound(BoundType::UB, pos, forOp.getConstantUpperBound() - 1);

123 return success();

124 }

125

126 return addBound(BoundType::UB, pos, forOp.getUpperBoundMap(),

127 forOp.getUpperBoundOperands());

128 }

129

131 AffineParallelOp parallelOp) {

132 size_t ivPos = 0;

133 for (Value iv : parallelOp.getIVs()) {

134 unsigned pos;

135 if (!findVar(iv, &pos)) {

136 assert(false && "variable expected for the IV value");

137 return failure();

138 }

139

140 AffineMap lowerBound = parallelOp.getLowerBoundMap(ivPos);

143 else if (failed(addBound(BoundType::LB, pos, lowerBound,

144 parallelOp.getLowerBoundsOperands())))

145 return failure();

146

147 auto upperBound = parallelOp.getUpperBoundMap(ivPos);

148 if (upperBound.isConstant())

149 addBound(BoundType::UB, pos, upperBound.getSingleConstantResult() - 1);

150 else if (failed(addBound(BoundType::UB, pos, upperBound,

151 parallelOp.getUpperBoundsOperands())))

152 return failure();

153 ++ivPos;

154 }

155 return success();

156 }

157

158 LogicalResult

162 assert(lbMaps.size() == ubMaps.size());

163 assert(lbMaps.size() <= getNumDimVars());

164

165 for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {

168 assert(!lbMap || lbMap.getNumInputs() == operands.size());

169 assert(!ubMap || ubMap.getNumInputs() == operands.size());

170

171

172

173 if (lbMap && ubMap && lbMap.getNumResults() == 1 &&

176

177

178

179

180 !isa(lbMap.getResult(0))) {

181

182

184 if (!result)

185 return failure();

186

187 AffineForOp loop =

189 if (!loop)

190 return failure();

191

192 if (failed(addAffineForOpDomain(loop)))

193 return failure();

194 continue;

195 }

196

197

198

199

200 if (lbMap && failed(addBound(BoundType::LB, i, lbMap, operands)))

201 return failure();

202 if (ubMap && failed(addBound(BoundType::UB, i, ubMap, operands)))

203 return failure();

204 }

205 return success();

206 }

207

209 IntegerSet set = ifOp.getIntegerSet();

210

211

214

215

217

218

219

220

221 mergeAndAlignVarsWithOther(0, &cst);

222 append(cst);

223 }

224

228

229

230 auto map = boundMap;

235 for (Value operand : operands) {

236 if (failed(addInductionVarOrTerminalSymbol(operand)))

237 return failure();

238 }

239 return addBound(type, pos, computeAlignedMap(map, operands));

240 }

241

242

243

244

245

246

247

248

249

250

254 assert(values.size() == lbMaps.size());

255 assert(lbMaps.size() == ubMaps.size());

256

257 for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {

258 unsigned pos;

259 if (!findVar(values[i], &pos))

260 continue;

261

264 assert(!lbMap || lbMap.getNumInputs() == operands.size());

265 assert(!ubMap || ubMap.getNumInputs() == operands.size());

266

267

268 if (lbMap && ubMap && lbMap.getNumResults() == 1 &&

271 if (failed(addBound(BoundType::EQ, pos, lbMap, operands)))

272 return failure();

273 continue;

274 }

275

276

277

278

279 if (lbMap && lbMap.getNumResults() != 0 && ubMap &&

281 if (failed(addBound(BoundType::LB, pos, lbMap, operands)))

282 return failure();

283 if (failed(addBound(BoundType::UB, pos, ubMap, operands)))

284 return failure();

285 } else {

287 if (failed(this->addAffineForOpDomain(loop)))

288 return failure();

289 }

290 }

291 return success();

292 }

293

294 LogicalResult

296 return composeMatchingMap(

298 }

299

300

302 unsigned pos;

304 pos < cst->getNumDimAndSymbolVars()) {

307 }

308 }

309

310

312

314 for (unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++) {

316 loopIVs.push_back(getValue(i));

317 }

318

319 for (auto iv : loopIVs) {

321 }

322 }

323

325 unsigned pos, unsigned ineqPos, AffineValueMap &vmap,

327 unsigned numDims = getNumDimVars();

328 unsigned numSyms = getNumSymbolVars();

329

330 assert(pos < numDims && "invalid position");

331 assert(ineqPos < getNumInequalities() && "invalid inequality position");

332

333

335 if (failed(computeLocalVars(memo, context)))

336 assert(false &&

337 "one or more local exprs do not have an explicit representation");

339

340

343 bound.reserve(getNumCols() - 1);

344

345 bound.append(inequality.begin(), inequality.begin() + pos);

346 bound.append(inequality.begin() + pos + 1, inequality.end());

347

348 if (inequality[pos] > 0)

349

350 std::transform(bound.begin(), bound.end(), bound.begin(),

351 std::negate<int64_t>());

352 else

353

354 bound.back() += 1;

355

356

358 localExprs, context);

359

360

362 getValues(0, pos, &operands);

364 getValues(pos + 1, getNumDimAndSymbolVars(), &trailingOperands);

365 operands.append(trailingOperands.begin(), trailingOperands.end());

367 }

368

371

372 domain.convertToLocal(VarKind::SetDim, getNumDomainDims(),

373 getNumDomainDims() + getNumRangeDims());

374 return domain;

375 }

376

379

380 range.convertToLocal(VarKind::SetDim, 0, getNumDomainDims());

381 return range;

382 }

383

386 "Domain of this and range of other do not match");

388 "Values of domain of this and range of other do not match");

389

391

392

393

394

395

396

397

398

399

403

404

405 mergeSymbolVars(rel);

407

408

409

410

413

414

415

416 convertToLocal(VarKind::SetDim, getNumDomainDims() - removeDims,

417 getNumDomainDims());

418

419 auto thisMaybeValues = getMaybeValues(VarKind::SetDim);

420 auto relMaybeValues = rel.getMaybeValues(VarKind::SetDim);

421

422

424 if (relMaybeValues[i].has_value())

425 setValue(i, *relMaybeValues[i]);

426

427 for (unsigned i = 0, e = getNumRangeDims(); i < e; ++i) {

429 if (thisMaybeValues[rangeIdx].has_value())

430 rel.setValue(rangeIdx, *thisMaybeValues[rangeIdx]);

431 }

432

433

436

437 *this = rel;

438 }

439

441 unsigned oldDomain = getNumDomainDims();

442 unsigned oldRange = getNumRangeDims();

443

444 appendRangeVar(oldDomain);

445

446 for (unsigned i = 0; i < oldDomain; ++i)

447 swapVar(i, oldDomain + oldRange + i);

448

449 removeVarRange(0, oldDomain);

450

451 numDomainDims = oldRange;

452 numRangeDims = oldDomain;

453 }

454

456 assert(pos <= getNumDomainDims() &&

457 "Var cannot be inserted at invalid position");

458 insertDimVar(pos, num);

459 numDomainDims += num;

460 }

461

463 assert(pos <= getNumRangeDims() &&

464 "Var cannot be inserted at invalid position");

465 insertDimVar(getNumDomainDims() + pos, num);

466 numRangeDims += num;

467 }

468

470 insertDimVar(getNumDomainDims(), num);

471 numDomainDims += num;

472 }

473

475 insertDimVar(getNumDimVars(), num);

476 numRangeDims += num;

477 }

478

480 unsigned varLimit) {

481 assert(varLimit <= getNumVarKind(kind));

482 if (varStart >= varLimit)

483 return;

484

486

487

488 if (kind != VarKind::SetDim)

489 return;

490

491

492

493 unsigned intersectDomainLHS = std::min(varLimit, getNumDomainDims());

494 unsigned intersectDomainRHS = varStart;

495 unsigned intersectRangeLHS = std::min(varLimit, getNumDimVars());

496 unsigned intersectRangeRHS = std::max(varStart, getNumDomainDims());

497

498 if (intersectDomainLHS > intersectDomainRHS)

499 numDomainDims -= intersectDomainLHS - intersectDomainRHS;

500 if (intersectRangeLHS > intersectRangeRHS)

501 numRangeDims -= intersectRangeLHS - intersectRangeRHS;

502 }

503

506

507 std::vector<SmallVector<int64_t, 8>> flatExprs;

510 return failure();

511

512 const unsigned oldDimNum = localVarCst.getNumDimVars();

513 const unsigned oldCols = localVarCst.getNumCols();

514 const unsigned numRangeVars = map.getNumResults();

515 const unsigned numDomainVars = map.getNumDims();

516

517

519

520

521

524

525

527 for (unsigned i = 0, e = map.getNumResults(); i < e; ++i) {

528

529 std::fill(eq.begin(), eq.end(), 0);

530

531 for (unsigned j = 0, f = oldDimNum; j < f; ++j)

532 eq[j] = flatExprs[i][j];

533 for (unsigned j = oldDimNum, f = oldCols; j < f; ++j)

534 eq[j + numRangeVars] = flatExprs[i][j];

535

536 eq[numDomainVars + i] = -1;

538 }

539

540 rel = localVarCst;

541 return success();

542 }

543

546

549 return failure();

550

551

552 for (unsigned i = 0, e = affineMap.getNumDims(); i < e; ++i)

554

555 const unsigned mapNumResults = affineMap.getNumResults();

558 VarKind::Symbol, i,

560

561 return success();

562 }

static void turnSymbolIntoDim(FlatAffineValueConstraints *cst, Value value)

union mlir::linalg::@1203::ArityGroupAndKind::Kind kind

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.

int64_t getSingleConstantResult() const

Returns the constant result of this map.

bool isConstant() const

Returns true if this affine map has only constant results.

static AffineMap get(MLIRContext *context)

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

unsigned getNumDims() const

unsigned getNumResults() const

unsigned getNumInputs() const

AffineExpr getResult(unsigned idx) const

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

void removeVarRange(presburger::VarKind kind, unsigned varStart, unsigned varLimit) override

Removes variables in the column range [varStart, varLimit), and copies any remaining valid data into ...

unsigned appendDimVar(ValueRange vals)

bool findVar(Value val, unsigned *pos, unsigned offset=0) const

Looks up the position of the variable with the specified Value starting with variables at offset offs...

void setValue(unsigned pos, Value val)

Sets the Value associated with the pos^th variable.

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

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

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

Operation * getDefiningOp() const

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

An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes.

Value getOperand(unsigned i) const

ArrayRef< Value > getOperands() const

AffineMap getAffineMap() const

void reset(AffineMap map, ValueRange operands, ValueRange results={})

A FlatAffineRelation represents a set of ordered pairs (domain -> range) where "domain" and "range" a...

void appendDomainVar(unsigned num=1)

Append num variables of the specified kind after the last variable of that kind.

void compose(const FlatAffineRelation &other)

Given affine relation other: (domainOther -> rangeOther), this operation takes the composition of oth...

unsigned getNumDomainDims() const

Returns the number of variables corresponding to domain/range of relation.

void inverse()

Swap domain and range of the relation.

FlatAffineValueConstraints getDomainSet() const

Returns a set corresponding to the domain/range of the affine relation.

void removeVarRange(VarKind kind, unsigned varStart, unsigned varLimit) override

Removes variables in the column range [varStart, varLimit), and copies any remaining valid data into ...

void appendRangeVar(unsigned num=1)

unsigned getNumRangeDims() const

FlatAffineValueConstraints getRangeSet() const

void insertRangeVar(unsigned pos, unsigned num=1)

void insertDomainVar(unsigned pos, unsigned num=1)

Insert num variables of the specified kind after the pos variable of that kind.

FlatAffineValueConstraints is an extension of FlatLinearValueConstraints with helper functions for Af...

void addAffineIfOpDomain(AffineIfOp ifOp)

Adds constraints imposed by the affine.if operation.

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 addAffineParallelOpDomain(AffineParallelOp parallelOp)

Add constraints (lower and upper bounds) for the specified 'affine.parallel' operation's Value using ...

LogicalResult addAffineForOpDomain(AffineForOp forOp)

Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR i...

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

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

void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos, AffineValueMap &vmap, MLIRContext *context) const

Returns the bound for the variable at pos from the inequality at ineqPos as a 1-d affine value map (a...

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

LogicalResult composeMap(const AffineValueMap *vMap)

Composes the affine value map with this FlatAffineValueConstrains, adding the results of the map as d...

LogicalResult addInductionVarOrTerminalSymbol(Value val)

Add the specified values as a dim or symbol var depending on its nature, if it already doesn't exist ...

An Identifier stores a pointer to an object, such as a Value or an Operation.

An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...

void setId(VarKind kind, unsigned i, Identifier id)

Set the identifier for the ith variable of the specified kind of the IntegerRelation's PresburgerSpac...

virtual void swapVar(unsigned posA, unsigned posB)

Swap the posA^th variable with the posB^th variable.

unsigned getNumSymbolVars() const

void convertToLocal(VarKind kind, unsigned varStart, unsigned varLimit)

void append(const IntegerRelation &other)

Appends constraints from other into this.

void addEquality(ArrayRef< DynamicAPInt > eq)

Adds an equality from the coefficients specified in eq.

void setDimSymbolSeparation(unsigned newSymbolCount)

Changes the partition between dimensions and symbols.

unsigned getNumDimAndSymbolVars() const

unsigned getNumCols() const

Returns the number of columns in the constraint system.

void removeRedundantLocalVars()

Removes local variables using equalities.

const PresburgerSpace & getSpace() const

Returns a reference to the underlying space.

unsigned getNumDimVars() const

PresburgerSpace getRangeSpace() const

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

Given an affine map map and its input operands, this method composes into map, maps of AffineApplyOps...

bool isAffineInductionVar(Value val)

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

AffineForOp getForInductionVarOwner(Value val)

Returns the loop parent of an induction variable.

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

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

void canonicalizeSetAndOperands(IntegerSet *set, SmallVectorImpl< Value > *operands)

Canonicalizes an integer set the same way canonicalizeMapAndOperands does for affine maps.

LogicalResult getRelationFromMap(AffineMap &map, presburger::IntegerRelation &rel)

Builds a relation from the given AffineMap/AffineValueMap map, containing all pairs of the form opera...

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

AffineParallelOp getAffineParallelInductionVarOwner(Value val)

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

BoundType

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

void mergeLocalVars(IntegerRelation &relA, IntegerRelation &relB, llvm::function_ref< bool(unsigned i, unsigned j)> merge)

Given two relations, A and B, add additional local vars to the sets such that both have the union of ...

Include the generated interface declarations.

AffineMap simplifyAffineMap(AffineMap map)

Simplifies an affine map by simplifying its underlying AffineExpr results.

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

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

AffineExpr getAffineExprFromFlatForm(ArrayRef< int64_t > flatExprs, unsigned numDims, unsigned numSymbols, ArrayRef< AffineExpr > localExprs, MLIRContext *context)

Constructs an affine expression from a flat ArrayRef.

LogicalResult getFlattenedAffineExprs(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *cst=nullptr, bool addConservativeSemiAffineBounds=false)

Flattens the result expressions of the map to their corresponding flattened forms and set in 'flatten...

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