1//===- SMTOps.cpp ---------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "mlir/Dialect/SMT/IR/SMTOps.h"
10#include "mlir/IR/Builders.h"
11#include "mlir/IR/OpImplementation.h"
12#include "llvm/ADT/APSInt.h"
13
14using namespace mlir;
15using namespace smt;
16using namespace mlir;
17
18//===----------------------------------------------------------------------===//
19// BVConstantOp
20//===----------------------------------------------------------------------===//
21
22LogicalResult BVConstantOp::inferReturnTypes(
23 mlir::MLIRContext *context, std::optional<mlir::Location> location,
24 ::mlir::ValueRange operands, ::mlir::DictionaryAttr attributes,
25 ::mlir::PropertyRef properties, ::mlir::RegionRange regions,
26 ::llvm::SmallVectorImpl<::mlir::Type> &inferredReturnTypes) {
27 inferredReturnTypes.push_back(
28 Elt: properties.as<Properties *>()->getValue().getType());
29 return success();
30}
31
32void BVConstantOp::getAsmResultNames(
33 function_ref<void(Value, StringRef)> setNameFn) {
34 SmallVector<char, 128> specialNameBuffer;
35 llvm::raw_svector_ostream specialName(specialNameBuffer);
36 specialName << "c" << getValue().getValue() << "_bv"
37 << getValue().getValue().getBitWidth();
38 setNameFn(getResult(), specialName.str());
39}
40
41OpFoldResult BVConstantOp::fold(FoldAdaptor adaptor) {
42 assert(adaptor.getOperands().empty() && "constant has no operands");
43 return getValueAttr();
44}
45
46//===----------------------------------------------------------------------===//
47// DeclareFunOp
48//===----------------------------------------------------------------------===//
49
50void DeclareFunOp::getAsmResultNames(
51 function_ref<void(Value, StringRef)> setNameFn) {
52 setNameFn(getResult(), getNamePrefix().has_value() ? *getNamePrefix() : "");
53}
54
55//===----------------------------------------------------------------------===//
56// SolverOp
57//===----------------------------------------------------------------------===//
58
59LogicalResult SolverOp::verifyRegions() {
60 if (getBody()->getTerminator()->getOperands().getTypes() != getResultTypes())
61 return emitOpError() << "types of yielded values must match return values";
62 if (getBody()->getArgumentTypes() != getInputs().getTypes())
63 return emitOpError()
64 << "block argument types must match the types of the 'inputs'";
65
66 return success();
67}
68
69//===----------------------------------------------------------------------===//
70// CheckOp
71//===----------------------------------------------------------------------===//
72
73LogicalResult CheckOp::verifyRegions() {
74 if (getSatRegion().front().getTerminator()->getOperands().getTypes() !=
75 getResultTypes())
76 return emitOpError() << "types of yielded values in 'sat' region must "
77 "match return values";
78 if (getUnknownRegion().front().getTerminator()->getOperands().getTypes() !=
79 getResultTypes())
80 return emitOpError() << "types of yielded values in 'unknown' region must "
81 "match return values";
82 if (getUnsatRegion().front().getTerminator()->getOperands().getTypes() !=
83 getResultTypes())
84 return emitOpError() << "types of yielded values in 'unsat' region must "
85 "match return values";
86
87 return success();
88}
89
90//===----------------------------------------------------------------------===//
91// EqOp
92//===----------------------------------------------------------------------===//
93
94static LogicalResult
95parseSameOperandTypeVariadicToBoolOp(OpAsmParser &parser,
96 OperationState &result) {
97 SmallVector<OpAsmParser::UnresolvedOperand, 4> inputs;
98 SMLoc loc = parser.getCurrentLocation();
99 Type type;
100
101 if (parser.parseOperandList(result&: inputs) ||
102 parser.parseOptionalAttrDict(result&: result.attributes) || parser.parseColon() ||
103 parser.parseType(result&: type))
104 return failure();
105
106 result.addTypes(newTypes: BoolType::get(ctx: parser.getContext()));
107 if (parser.resolveOperands(operands&: inputs, types: SmallVector<Type>(inputs.size(), type),
108 loc, result&: result.operands))
109 return failure();
110
111 return success();
112}
113
114ParseResult EqOp::parse(OpAsmParser &parser, OperationState &result) {
115 return parseSameOperandTypeVariadicToBoolOp(parser, result);
116}
117
118void EqOp::print(OpAsmPrinter &printer) {
119 printer << ' ' << getInputs();
120 printer.printOptionalAttrDict(
121 attrs: getOperation()->getDiscardableAttrDictionary().getValue());
122 printer << " : " << getInputs().front().getType();
123}
124
125LogicalResult EqOp::verify() {
126 if (getInputs().size() < 2)
127 return emitOpError() << "'inputs' must have at least size 2, but got "
128 << getInputs().size();
129
130 return success();
131}
132
133//===----------------------------------------------------------------------===//
134// DistinctOp
135//===----------------------------------------------------------------------===//
136
137ParseResult DistinctOp::parse(OpAsmParser &parser, OperationState &result) {
138 return parseSameOperandTypeVariadicToBoolOp(parser, result);
139}
140
141void DistinctOp::print(OpAsmPrinter &printer) {
142 printer << ' ' << getInputs();
143 printer.printOptionalAttrDict(
144 attrs: getOperation()->getDiscardableAttrDictionary().getValue());
145 printer << " : " << getInputs().front().getType();
146}
147
148LogicalResult DistinctOp::verify() {
149 if (getInputs().size() < 2)
150 return emitOpError() << "'inputs' must have at least size 2, but got "
151 << getInputs().size();
152
153 return success();
154}
155
156//===----------------------------------------------------------------------===//
157// ExtractOp
158//===----------------------------------------------------------------------===//
159
160LogicalResult ExtractOp::verify() {
161 unsigned rangeWidth = getType().getWidth();
162 unsigned inputWidth = cast<BitVectorType>(Val: getInput().getType()).getWidth();
163 if (getLowBit() + rangeWidth > inputWidth)
164 return emitOpError(message: "range to be extracted is too big, expected range "
165 "starting at index ")
166 << getLowBit() << " of length " << rangeWidth
167 << " requires input width of at least " << (getLowBit() + rangeWidth)
168 << ", but the input width is only " << inputWidth;
169 return success();
170}
171
172//===----------------------------------------------------------------------===//
173// ConcatOp
174//===----------------------------------------------------------------------===//
175
176LogicalResult ConcatOp::inferReturnTypes(
177 MLIRContext *context, std::optional<Location> location, ValueRange operands,
178 DictionaryAttr attributes, PropertyRef properties, RegionRange regions,
179 SmallVectorImpl<Type> &inferredReturnTypes) {
180 inferredReturnTypes.push_back(Elt: BitVectorType::get(
181 context, width: cast<BitVectorType>(Val: operands[0].getType()).getWidth() +
182 cast<BitVectorType>(Val: operands[1].getType()).getWidth()));
183 return success();
184}
185
186//===----------------------------------------------------------------------===//
187// RepeatOp
188//===----------------------------------------------------------------------===//
189
190LogicalResult RepeatOp::verify() {
191 unsigned inputWidth = cast<BitVectorType>(Val: getInput().getType()).getWidth();
192 unsigned resultWidth = getType().getWidth();
193 if (resultWidth % inputWidth != 0)
194 return emitOpError() << "result bit-vector width must be a multiple of the "
195 "input bit-vector width";
196
197 return success();
198}
199
200unsigned RepeatOp::getCount() {
201 unsigned inputWidth = cast<BitVectorType>(Val: getInput().getType()).getWidth();
202 unsigned resultWidth = getType().getWidth();
203 return resultWidth / inputWidth;
204}
205
206void RepeatOp::build(OpBuilder &builder, OperationState &state, unsigned count,
207 Value input) {
208 unsigned inputWidth = cast<BitVectorType>(Val: input.getType()).getWidth();
209 Type resultTy = BitVectorType::get(context: builder.getContext(), width: inputWidth * count);
210 build(odsBuilder&: builder, odsState&: state, result: resultTy, input);
211}
212
213ParseResult RepeatOp::parse(OpAsmParser &parser, OperationState &result) {
214 OpAsmParser::UnresolvedOperand input;
215 Type inputType;
216 llvm::SMLoc countLoc = parser.getCurrentLocation();
217
218 APInt count;
219 if (parser.parseInteger(result&: count) || parser.parseKeyword(keyword: "times"))
220 return failure();
221
222 if (count.isNonPositive())
223 return parser.emitError(loc: countLoc) << "integer must be positive";
224
225 llvm::SMLoc inputLoc = parser.getCurrentLocation();
226 if (parser.parseOperand(result&: input) ||
227 parser.parseOptionalAttrDict(result&: result.attributes) || parser.parseColon() ||
228 parser.parseType(result&: inputType))
229 return failure();
230
231 if (parser.resolveOperand(operand: input, type: inputType, result&: result.operands))
232 return failure();
233
234 auto bvInputTy = dyn_cast<BitVectorType>(Val&: inputType);
235 if (!bvInputTy)
236 return parser.emitError(loc: inputLoc) << "input must have bit-vector type";
237
238 // Make sure no assertions can trigger and no silent overflows can happen
239 // Bit-width is stored as 'int64_t' parameter in 'BitVectorType'
240 const unsigned maxBw = 63;
241 if (count.getActiveBits() > maxBw)
242 return parser.emitError(loc: countLoc)
243 << "integer must fit into " << maxBw << " bits";
244
245 // Store multiplication in an APInt twice the size to not have any overflow
246 // and check if it can be truncated to 'maxBw' bits without cutting of
247 // important bits.
248 APInt resultBw = bvInputTy.getWidth() * count.zext(width: 2 * maxBw);
249 if (resultBw.getActiveBits() > maxBw)
250 return parser.emitError(loc: countLoc)
251 << "result bit-width (provided integer times bit-width of the input "
252 "type) must fit into "
253 << maxBw << " bits";
254
255 Type resultTy =
256 BitVectorType::get(context: parser.getContext(), width: resultBw.getZExtValue());
257 result.addTypes(newTypes: resultTy);
258 return success();
259}
260
261void RepeatOp::print(OpAsmPrinter &printer) {
262 printer << " " << getCount() << " times " << getInput();
263 printer.printOptionalAttrDict(
264 attrs: (*this)->getDiscardableAttrDictionary().getValue());
265 printer << " : " << getInput().getType();
266}
267
268//===----------------------------------------------------------------------===//
269// BoolConstantOp
270//===----------------------------------------------------------------------===//
271
272void BoolConstantOp::getAsmResultNames(
273 function_ref<void(Value, StringRef)> setNameFn) {
274 setNameFn(getResult(), getValue() ? "true" : "false");
275}
276
277OpFoldResult BoolConstantOp::fold(FoldAdaptor adaptor) {
278 assert(adaptor.getOperands().empty() && "constant has no operands");
279 return getValueAttr();
280}
281
282//===----------------------------------------------------------------------===//
283// IntConstantOp
284//===----------------------------------------------------------------------===//
285
286void IntConstantOp::getAsmResultNames(
287 function_ref<void(Value, StringRef)> setNameFn) {
288 SmallVector<char, 32> specialNameBuffer;
289 llvm::raw_svector_ostream specialName(specialNameBuffer);
290 specialName << "c" << getValue();
291 setNameFn(getResult(), specialName.str());
292}
293
294OpFoldResult IntConstantOp::fold(FoldAdaptor adaptor) {
295 assert(adaptor.getOperands().empty() && "constant has no operands");
296 return getValueAttr();
297}
298
299void IntConstantOp::print(OpAsmPrinter &p) {
300 p << " " << getValue();
301 p.printOptionalAttrDict(attrs: (*this)->getDiscardableAttrDictionary().getValue());
302}
303
304ParseResult IntConstantOp::parse(OpAsmParser &parser, OperationState &result) {
305 APInt value;
306 if (parser.parseInteger(result&: value))
307 return failure();
308
309 result.getOrAddProperties<Properties>().setValue(
310 IntegerAttr::get(context: parser.getContext(), value: APSInt(value)));
311
312 if (parser.parseOptionalAttrDict(result&: result.attributes))
313 return failure();
314
315 result.addTypes(newTypes: smt::IntType::get(ctx: parser.getContext()));
316 return success();
317}
318
319//===----------------------------------------------------------------------===//
320// ForallOp
321//===----------------------------------------------------------------------===//
322
323template <typename QuantifierOp>
324static LogicalResult verifyQuantifierRegions(QuantifierOp op) {
325 if (op.getBoundVarNames() &&
326 op.getBody().getNumArguments() != op.getBoundVarNames()->size())
327 return op.emitOpError(
328 "number of bound variable names must match number of block arguments");
329 if (!llvm::all_of(op.getBody().getArgumentTypes(), isAnyNonFuncSMTValueType))
330 return op.emitOpError()
331 << "bound variables must by any non-function SMT value";
332
333 if (op.getBody().front().getTerminator()->getNumOperands() != 1)
334 return op.emitOpError("must have exactly one yielded value");
335 if (!isa<BoolType>(
336 op.getBody().front().getTerminator()->getOperand(0).getType()))
337 return op.emitOpError("yielded value must be of '!smt.bool' type");
338
339 for (auto regionWithIndex : llvm::enumerate(op.getPatterns())) {
340 unsigned i = regionWithIndex.index();
341 Region &region = regionWithIndex.value();
342
343 if (op.getBody().getArgumentTypes() != region.getArgumentTypes())
344 return op.emitOpError()
345 << "block argument number and types of the 'body' "
346 "and 'patterns' region #"
347 << i << " must match";
348 if (region.front().getTerminator()->getNumOperands() < 1)
349 return op.emitOpError() << "'patterns' region #" << i
350 << " must have at least one yielded value";
351
352 // All operations in the 'patterns' region must be SMT operations.
353 auto result = region.walk([&](Operation *childOp) {
354 if (!isa<SMTDialect>(Val: childOp->getDialect())) {
355 auto diag = op.emitOpError()
356 << "the 'patterns' region #" << i
357 << " may only contain SMT dialect operations";
358 diag.attachNote(childOp->getLoc()) << "first non-SMT operation here";
359 return WalkResult::interrupt();
360 }
361
362 // There may be no quantifier (or other variable binding) operations in
363 // the 'patterns' region.
364 if (isa<ForallOp, ExistsOp>(Val: childOp)) {
365 auto diag = op.emitOpError() << "the 'patterns' region #" << i
366 << " must not contain "
367 "any variable binding operations";
368 diag.attachNote(childOp->getLoc()) << "first violating operation here";
369 return WalkResult::interrupt();
370 }
371
372 return WalkResult::advance();
373 });
374 if (result.wasInterrupted())
375 return failure();
376 }
377
378 return success();
379}
380
381template <typename Properties>
382static void buildQuantifier(
383 OpBuilder &odsBuilder, OperationState &odsState, TypeRange boundVarTypes,
384 function_ref<Value(OpBuilder &, Location, ValueRange)> bodyBuilder,
385 std::optional<ArrayRef<StringRef>> boundVarNames,
386 function_ref<ValueRange(OpBuilder &, Location, ValueRange)> patternBuilder,
387 uint32_t weight, bool noPattern) {
388 odsState.addTypes(newTypes: BoolType::get(ctx: odsBuilder.getContext()));
389 if (weight != 0)
390 odsState.getOrAddProperties<Properties>().weight =
391 odsBuilder.getIntegerAttr(type: odsBuilder.getIntegerType(width: 32), value: weight);
392 if (noPattern)
393 odsState.getOrAddProperties<Properties>().noPattern =
394 odsBuilder.getUnitAttr();
395 if (boundVarNames.has_value()) {
396 SmallVector<Attribute> boundVarNamesList;
397 for (StringRef str : *boundVarNames)
398 boundVarNamesList.emplace_back(Args: odsBuilder.getStringAttr(bytes: str));
399 odsState.getOrAddProperties<Properties>().boundVarNames =
400 odsBuilder.getArrayAttr(value: boundVarNamesList);
401 }
402 {
403 OpBuilder::InsertionGuard guard(odsBuilder);
404 Region *region = odsState.addRegion();
405 Block *block = odsBuilder.createBlock(parent: region);
406 block->addArguments(
407 types: boundVarTypes,
408 locs: SmallVector<Location>(boundVarTypes.size(), odsState.location));
409 Value returnVal =
410 bodyBuilder(odsBuilder, odsState.location, block->getArguments());
411 smt::YieldOp::create(builder&: odsBuilder, location: odsState.location, values: returnVal);
412 }
413 if (patternBuilder) {
414 Region *region = odsState.addRegion();
415 OpBuilder::InsertionGuard guard(odsBuilder);
416 Block *block = odsBuilder.createBlock(parent: region);
417 block->addArguments(
418 types: boundVarTypes,
419 locs: SmallVector<Location>(boundVarTypes.size(), odsState.location));
420 ValueRange returnVals =
421 patternBuilder(odsBuilder, odsState.location, block->getArguments());
422 smt::YieldOp::create(builder&: odsBuilder, location: odsState.location, values: returnVals);
423 }
424}
425
426LogicalResult ForallOp::verify() {
427 if (!getPatterns().empty() && getNoPattern())
428 return emitOpError() << "patterns and the no_pattern attribute must not be "
429 "specified at the same time";
430
431 return success();
432}
433
434LogicalResult ForallOp::verifyRegions() {
435 return verifyQuantifierRegions(op: *this);
436}
437
438void ForallOp::build(
439 OpBuilder &odsBuilder, OperationState &odsState, TypeRange boundVarTypes,
440 function_ref<Value(OpBuilder &, Location, ValueRange)> bodyBuilder,
441 std::optional<ArrayRef<StringRef>> boundVarNames,
442 function_ref<ValueRange(OpBuilder &, Location, ValueRange)> patternBuilder,
443 uint32_t weight, bool noPattern) {
444 buildQuantifier<Properties>(odsBuilder, odsState, boundVarTypes, bodyBuilder,
445 boundVarNames, patternBuilder, weight, noPattern);
446}
447
448//===----------------------------------------------------------------------===//
449// ExistsOp
450//===----------------------------------------------------------------------===//
451
452LogicalResult ExistsOp::verify() {
453 if (!getPatterns().empty() && getNoPattern())
454 return emitOpError() << "patterns and the no_pattern attribute must not be "
455 "specified at the same time";
456
457 return success();
458}
459
460LogicalResult ExistsOp::verifyRegions() {
461 return verifyQuantifierRegions(op: *this);
462}
463
464void ExistsOp::build(
465 OpBuilder &odsBuilder, OperationState &odsState, TypeRange boundVarTypes,
466 function_ref<Value(OpBuilder &, Location, ValueRange)> bodyBuilder,
467 std::optional<ArrayRef<StringRef>> boundVarNames,
468 function_ref<ValueRange(OpBuilder &, Location, ValueRange)> patternBuilder,
469 uint32_t weight, bool noPattern) {
470 buildQuantifier<Properties>(odsBuilder, odsState, boundVarTypes, bodyBuilder,
471 boundVarNames, patternBuilder, weight, noPattern);
472}
473
474#define GET_OP_CLASSES
475#include "mlir/Dialect/SMT/IR/SMT.cpp.inc"
476