blob: 756f25d8bbd4fe28f3436394a652d27d4754f6af [file] [log] [blame]
Chris Lattnere79379a2018-06-22 10:39:19 -07001//===- Parser.cpp - MLIR Parser Implementation ----------------------------===//
2//
3// Copyright 2019 The MLIR Authors.
4//
5// Licensed under the Apache License, Version 2.0 (the "License");
6// you may not use this file except in compliance with the License.
7// You may obtain a copy of the License at
8//
9// http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the License is distributed on an "AS IS" BASIS,
13// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14// See the License for the specific language governing permissions and
15// limitations under the License.
16// =============================================================================
17//
18// This file implements the parser for the MLIR textual form.
19//
20//===----------------------------------------------------------------------===//
21
22#include "mlir/Parser.h"
23#include "Lexer.h"
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -070024#include "mlir/IR/AffineExpr.h"
MLIR Teamf85a6262018-06-27 11:03:08 -070025#include "mlir/IR/AffineMap.h"
Chris Lattner7121b802018-07-04 20:45:39 -070026#include "mlir/IR/Attributes.h"
Chris Lattner158e0a3e2018-07-08 20:51:38 -070027#include "mlir/IR/Builders.h"
Tatiana Shpeismanc96b5872018-06-28 17:02:32 -070028#include "mlir/IR/MLFunction.h"
Chris Lattnerea5c3dc2018-08-21 08:42:19 -070029#include "mlir/IR/MLIRContext.h"
Chris Lattner21e67f62018-07-06 10:46:19 -070030#include "mlir/IR/Module.h"
Chris Lattner85ee1512018-07-25 11:15:20 -070031#include "mlir/IR/OpImplementation.h"
Chris Lattner21e67f62018-07-06 10:46:19 -070032#include "mlir/IR/OperationSet.h"
Chris Lattnerea5c3dc2018-08-21 08:42:19 -070033#include "mlir/IR/StmtVisitor.h"
Chris Lattnerf7e22732018-06-22 22:03:48 -070034#include "mlir/IR/Types.h"
James Molloyf0d2f442018-08-03 01:54:46 -070035#include "llvm/ADT/DenseMap.h"
Chris Lattner1aa46322018-08-21 17:55:22 -070036#include "llvm/Support/PrettyStackTrace.h"
James Molloyf0d2f442018-08-03 01:54:46 -070037#include "llvm/Support/SourceMgr.h"
Chris Lattnere79379a2018-06-22 10:39:19 -070038using namespace mlir;
Chris Lattner4c95a502018-06-23 16:03:42 -070039using llvm::SMLoc;
James Molloy0ff71542018-07-23 16:56:32 -070040using llvm::SourceMgr;
Chris Lattnere79379a2018-06-22 10:39:19 -070041
Chris Lattnerf7e22732018-06-22 22:03:48 -070042/// Simple enum to make code read better in cases that would otherwise return a
43/// bool value. Failure is "true" in a boolean context.
James Molloy0ff71542018-07-23 16:56:32 -070044enum ParseResult { ParseSuccess, ParseFailure };
Chris Lattnere79379a2018-06-22 10:39:19 -070045
Chris Lattner48af7d12018-07-09 19:05:38 -070046namespace {
47class Parser;
48
49/// This class refers to all of the state maintained globally by the parser,
50/// such as the current lexer position etc. The Parser base class provides
51/// methods to access this.
52class ParserState {
Chris Lattnered65a732018-06-28 20:45:33 -070053public:
Chris Lattner2e595eb2018-07-10 10:08:27 -070054 ParserState(llvm::SourceMgr &sourceMgr, Module *module,
Chris Lattner48af7d12018-07-09 19:05:38 -070055 SMDiagnosticHandlerTy errorReporter)
Chris Lattner2e595eb2018-07-10 10:08:27 -070056 : context(module->getContext()), module(module),
57 lex(sourceMgr, errorReporter), curToken(lex.lexToken()),
Chris Lattner85ee1512018-07-25 11:15:20 -070058 errorReporter(errorReporter), operationSet(OperationSet::get(context)) {
59 }
Chris Lattner2e595eb2018-07-10 10:08:27 -070060
61 // A map from affine map identifier to AffineMap.
62 llvm::StringMap<AffineMap *> affineMapDefinitions;
Chris Lattner4613d9e2018-08-19 21:17:22 -070063
Uday Bondhugulabc535622018-08-07 14:24:38 -070064 // A map from integer set identifier to IntegerSet.
65 llvm::StringMap<IntegerSet *> integerSetDefinitions;
Chris Lattnere79379a2018-06-22 10:39:19 -070066
Chris Lattner4613d9e2018-08-19 21:17:22 -070067 // This keeps track of all forward references to functions along with the
68 // temporary function used to represent them and the location of the first
69 // reference.
70 llvm::DenseMap<Identifier, std::pair<Function *, SMLoc>> functionForwardRefs;
71
Chris Lattnere79379a2018-06-22 10:39:19 -070072private:
Chris Lattner48af7d12018-07-09 19:05:38 -070073 ParserState(const ParserState &) = delete;
74 void operator=(const ParserState &) = delete;
75
76 friend class Parser;
77
78 // The context we're parsing into.
Chris Lattner2e595eb2018-07-10 10:08:27 -070079 MLIRContext *const context;
80
81 // This is the module we are parsing into.
82 Module *const module;
Chris Lattnerf7e22732018-06-22 22:03:48 -070083
84 // The lexer for the source file we're parsing.
Chris Lattnere79379a2018-06-22 10:39:19 -070085 Lexer lex;
86
87 // This is the next token that hasn't been consumed yet.
88 Token curToken;
89
Jacques Pienaar9c411be2018-06-24 19:17:35 -070090 // The diagnostic error reporter.
Chris Lattner2e595eb2018-07-10 10:08:27 -070091 SMDiagnosticHandlerTy const errorReporter;
Chris Lattner85ee1512018-07-25 11:15:20 -070092
93 // The active OperationSet we're parsing with.
94 OperationSet &operationSet;
Chris Lattner48af7d12018-07-09 19:05:38 -070095};
96} // end anonymous namespace
MLIR Teamf85a6262018-06-27 11:03:08 -070097
Chris Lattner48af7d12018-07-09 19:05:38 -070098namespace {
99
Chris Lattner992a1272018-08-07 12:02:37 -0700100typedef std::function<Operation *(const OperationState &)>
Tatiana Shpeisman565b9642018-07-16 11:47:09 -0700101 CreateOperationFunction;
102
Chris Lattner48af7d12018-07-09 19:05:38 -0700103/// This class implement support for parsing global entities like types and
104/// shared entities like SSA names. It is intended to be subclassed by
105/// specialized subparsers that include state, e.g. when a local symbol table.
106class Parser {
107public:
Chris Lattner2e595eb2018-07-10 10:08:27 -0700108 Builder builder;
Chris Lattner48af7d12018-07-09 19:05:38 -0700109
Chris Lattner2e595eb2018-07-10 10:08:27 -0700110 Parser(ParserState &state) : builder(state.context), state(state) {}
111
112 // Helper methods to get stuff from the parser-global state.
113 ParserState &getState() const { return state; }
Chris Lattner48af7d12018-07-09 19:05:38 -0700114 MLIRContext *getContext() const { return state.context; }
Chris Lattner2e595eb2018-07-10 10:08:27 -0700115 Module *getModule() { return state.module; }
Chris Lattner85ee1512018-07-25 11:15:20 -0700116 OperationSet &getOperationSet() const { return state.operationSet; }
Chris Lattnerf7bdf952018-08-05 21:12:29 -0700117 llvm::SourceMgr &getSourceMgr() { return state.lex.getSourceMgr(); }
Chris Lattner48af7d12018-07-09 19:05:38 -0700118
119 /// Return the current token the parser is inspecting.
120 const Token &getToken() const { return state.curToken; }
121 StringRef getTokenSpelling() const { return state.curToken.getSpelling(); }
Chris Lattnere79379a2018-06-22 10:39:19 -0700122
Chris Lattner1628fa02018-08-23 14:32:25 -0700123 /// Encode the specified source location information into an attribute for
124 /// attachment to the IR.
125 Attribute *getEncodedSourceLocation(llvm::SMLoc loc);
126
Chris Lattnere79379a2018-06-22 10:39:19 -0700127 /// Emit an error and return failure.
Chris Lattner4c95a502018-06-23 16:03:42 -0700128 ParseResult emitError(const Twine &message) {
Chris Lattner48af7d12018-07-09 19:05:38 -0700129 return emitError(state.curToken.getLoc(), message);
Chris Lattner4c95a502018-06-23 16:03:42 -0700130 }
131 ParseResult emitError(SMLoc loc, const Twine &message);
Chris Lattnere79379a2018-06-22 10:39:19 -0700132
133 /// Advance the current lexer onto the next token.
134 void consumeToken() {
Chris Lattner48af7d12018-07-09 19:05:38 -0700135 assert(state.curToken.isNot(Token::eof, Token::error) &&
Chris Lattnere79379a2018-06-22 10:39:19 -0700136 "shouldn't advance past EOF or errors");
Chris Lattner48af7d12018-07-09 19:05:38 -0700137 state.curToken = state.lex.lexToken();
Chris Lattnere79379a2018-06-22 10:39:19 -0700138 }
139
140 /// Advance the current lexer onto the next token, asserting what the expected
141 /// current token is. This is preferred to the above method because it leads
142 /// to more self-documenting code with better checking.
Chris Lattner8da0c282018-06-29 11:15:56 -0700143 void consumeToken(Token::Kind kind) {
Chris Lattner48af7d12018-07-09 19:05:38 -0700144 assert(state.curToken.is(kind) && "consumed an unexpected token");
Chris Lattnere79379a2018-06-22 10:39:19 -0700145 consumeToken();
146 }
147
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700148 /// If the current token has the specified kind, consume it and return true.
149 /// If not, return false.
Chris Lattner8da0c282018-06-29 11:15:56 -0700150 bool consumeIf(Token::Kind kind) {
Chris Lattner48af7d12018-07-09 19:05:38 -0700151 if (state.curToken.isNot(kind))
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700152 return false;
153 consumeToken(kind);
154 return true;
155 }
156
Chris Lattnerf7702a62018-07-23 17:30:01 -0700157 /// Consume the specified token if present and return success. On failure,
158 /// output a diagnostic and return failure.
159 ParseResult parseToken(Token::Kind expectedToken, const Twine &message);
160
Chris Lattner40746442018-07-21 14:32:09 -0700161 /// Parse a comma-separated list of elements up until the specified end token.
162 ParseResult
163 parseCommaSeparatedListUntil(Token::Kind rightToken,
164 const std::function<ParseResult()> &parseElement,
165 bool allowEmptyList = true);
166
167 /// Parse a comma separated list of elements that must have at least one entry
168 /// in it.
169 ParseResult
170 parseCommaSeparatedList(const std::function<ParseResult()> &parseElement);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700171
Chris Lattnerf7e22732018-06-22 22:03:48 -0700172 // We have two forms of parsing methods - those that return a non-null
173 // pointer on success, and those that return a ParseResult to indicate whether
174 // they returned a failure. The second class fills in by-reference arguments
175 // as the results of their action.
176
Chris Lattnere79379a2018-06-22 10:39:19 -0700177 // Type parsing.
Chris Lattnerf7e22732018-06-22 22:03:48 -0700178 VectorType *parseVectorType();
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700179 ParseResult parseDimensionListRanked(SmallVectorImpl<int> &dimensions);
Chris Lattnerf7e22732018-06-22 22:03:48 -0700180 Type *parseTensorType();
181 Type *parseMemRefType();
182 Type *parseFunctionType();
183 Type *parseType();
Chris Lattner1604e472018-07-23 08:42:19 -0700184 ParseResult parseTypeListNoParens(SmallVectorImpl<Type *> &elements);
James Molloy0ff71542018-07-23 16:56:32 -0700185 ParseResult parseTypeList(SmallVectorImpl<Type *> &elements);
Chris Lattnere79379a2018-06-22 10:39:19 -0700186
Chris Lattner7121b802018-07-04 20:45:39 -0700187 // Attribute parsing.
Chris Lattner1aa46322018-08-21 17:55:22 -0700188 Function *resolveFunctionReference(StringRef nameStr, SMLoc nameLoc,
189 FunctionType *type);
Chris Lattner7121b802018-07-04 20:45:39 -0700190 Attribute *parseAttribute();
191 ParseResult parseAttributeDict(SmallVectorImpl<NamedAttribute> &attributes);
192
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700193 // Polyhedral structures.
Chris Lattner2e595eb2018-07-10 10:08:27 -0700194 AffineMap *parseAffineMapInline();
MLIR Team718c82f2018-07-16 09:45:22 -0700195 AffineMap *parseAffineMapReference();
Uday Bondhugulabc535622018-08-07 14:24:38 -0700196 IntegerSet *parseIntegerSetInline();
197 IntegerSet *parseIntegerSetReference();
MLIR Teamf85a6262018-06-27 11:03:08 -0700198
Chris Lattner48af7d12018-07-09 19:05:38 -0700199private:
200 // The Parser is subclassed and reinstantiated. Do not add additional
201 // non-trivial state here, add it to the ParserState class.
202 ParserState &state;
Chris Lattnere79379a2018-06-22 10:39:19 -0700203};
204} // end anonymous namespace
205
206//===----------------------------------------------------------------------===//
207// Helper methods.
208//===----------------------------------------------------------------------===//
209
Chris Lattner1628fa02018-08-23 14:32:25 -0700210/// Encode the specified source location information into an attribute for
211/// attachment to the IR.
212Attribute *Parser::getEncodedSourceLocation(llvm::SMLoc loc) {
213 // TODO(clattner): Switch to an more structured form that includes
214 // file/line/column instead of just byte offset in the file. This will
215 // eliminate this block of low level code poking at the SourceMgr directly.
216 auto &sourceMgr = getSourceMgr();
217 auto fileID = sourceMgr.FindBufferContainingLoc(loc);
218
219 auto *srcBuffer = sourceMgr.getMemoryBuffer(fileID);
220 unsigned locationEncoding = loc.getPointer() - srcBuffer->getBufferStart();
221 return builder.getIntegerAttr(locationEncoding);
222}
223
Chris Lattner4c95a502018-06-23 16:03:42 -0700224ParseResult Parser::emitError(SMLoc loc, const Twine &message) {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700225 // If we hit a parse error in response to a lexer error, then the lexer
Jacques Pienaar9c411be2018-06-24 19:17:35 -0700226 // already reported the error.
Chris Lattner48af7d12018-07-09 19:05:38 -0700227 if (getToken().is(Token::error))
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700228 return ParseFailure;
229
Chris Lattner48af7d12018-07-09 19:05:38 -0700230 auto &sourceMgr = state.lex.getSourceMgr();
231 state.errorReporter(sourceMgr.GetMessage(loc, SourceMgr::DK_Error, message));
Chris Lattnere79379a2018-06-22 10:39:19 -0700232 return ParseFailure;
233}
234
Chris Lattnerf7702a62018-07-23 17:30:01 -0700235/// Consume the specified token if present and return success. On failure,
236/// output a diagnostic and return failure.
237ParseResult Parser::parseToken(Token::Kind expectedToken,
238 const Twine &message) {
239 if (consumeIf(expectedToken))
240 return ParseSuccess;
241 return emitError(message);
242}
243
Chris Lattner40746442018-07-21 14:32:09 -0700244/// Parse a comma separated list of elements that must have at least one entry
245/// in it.
246ParseResult Parser::parseCommaSeparatedList(
247 const std::function<ParseResult()> &parseElement) {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700248 // Non-empty case starts with an element.
249 if (parseElement())
250 return ParseFailure;
251
252 // Otherwise we have a list of comma separated elements.
253 while (consumeIf(Token::comma)) {
254 if (parseElement())
255 return ParseFailure;
256 }
Chris Lattner40746442018-07-21 14:32:09 -0700257 return ParseSuccess;
258}
259
260/// Parse a comma-separated list of elements, terminated with an arbitrary
261/// token. This allows empty lists if allowEmptyList is true.
262///
263/// abstract-list ::= rightToken // if allowEmptyList == true
264/// abstract-list ::= element (',' element)* rightToken
265///
266ParseResult Parser::parseCommaSeparatedListUntil(
267 Token::Kind rightToken, const std::function<ParseResult()> &parseElement,
268 bool allowEmptyList) {
269 // Handle the empty case.
270 if (getToken().is(rightToken)) {
271 if (!allowEmptyList)
272 return emitError("expected list element");
273 consumeToken(rightToken);
274 return ParseSuccess;
275 }
276
Chris Lattnerf7702a62018-07-23 17:30:01 -0700277 if (parseCommaSeparatedList(parseElement) ||
278 parseToken(rightToken, "expected ',' or '" +
279 Token::getTokenSpelling(rightToken) + "'"))
Chris Lattner40746442018-07-21 14:32:09 -0700280 return ParseFailure;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700281
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700282 return ParseSuccess;
283}
Chris Lattnere79379a2018-06-22 10:39:19 -0700284
285//===----------------------------------------------------------------------===//
286// Type Parsing
287//===----------------------------------------------------------------------===//
288
Chris Lattnerc3251192018-07-27 13:09:58 -0700289/// Parse an arbitrary type.
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700290///
Chris Lattnerc3251192018-07-27 13:09:58 -0700291/// type ::= integer-type
292/// | float-type
293/// | other-type
294/// | vector-type
295/// | tensor-type
296/// | memref-type
297/// | function-type
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700298///
Chris Lattnerc3251192018-07-27 13:09:58 -0700299/// float-type ::= `f16` | `bf16` | `f32` | `f64`
300/// other-type ::= `affineint` | `tf_control`
301///
302Type *Parser::parseType() {
Chris Lattner48af7d12018-07-09 19:05:38 -0700303 switch (getToken().getKind()) {
Chris Lattnerf7e22732018-06-22 22:03:48 -0700304 default:
305 return (emitError("expected type"), nullptr);
Chris Lattnerc3251192018-07-27 13:09:58 -0700306 case Token::kw_memref:
307 return parseMemRefType();
308 case Token::kw_tensor:
309 return parseTensorType();
310 case Token::kw_vector:
311 return parseVectorType();
312 case Token::l_paren:
313 return parseFunctionType();
314 // integer-type
315 case Token::inttype: {
316 auto width = getToken().getIntTypeBitwidth();
317 if (!width.hasValue())
318 return (emitError("invalid integer width"), nullptr);
Nicolas Vasilache1b8c0842018-08-27 10:26:15 -0700319 if (width > IntegerType::kMaxWidth)
320 return (emitError("integer bitwidth is limited to " +
321 Twine(IntegerType::kMaxWidth) + " bits"),
322 nullptr);
Chris Lattnerc3251192018-07-27 13:09:58 -0700323 consumeToken(Token::inttype);
324 return builder.getIntegerType(width.getValue());
325 }
326
327 // float-type
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700328 case Token::kw_bf16:
329 consumeToken(Token::kw_bf16);
Chris Lattner158e0a3e2018-07-08 20:51:38 -0700330 return builder.getBF16Type();
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700331 case Token::kw_f16:
332 consumeToken(Token::kw_f16);
Chris Lattner158e0a3e2018-07-08 20:51:38 -0700333 return builder.getF16Type();
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700334 case Token::kw_f32:
335 consumeToken(Token::kw_f32);
Chris Lattner158e0a3e2018-07-08 20:51:38 -0700336 return builder.getF32Type();
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700337 case Token::kw_f64:
338 consumeToken(Token::kw_f64);
Chris Lattner158e0a3e2018-07-08 20:51:38 -0700339 return builder.getF64Type();
Chris Lattnerc3251192018-07-27 13:09:58 -0700340
341 // other-type
Chris Lattnerf958bbe2018-06-29 22:08:05 -0700342 case Token::kw_affineint:
343 consumeToken(Token::kw_affineint);
Chris Lattner158e0a3e2018-07-08 20:51:38 -0700344 return builder.getAffineIntType();
Jacques Pienaarc0d69302018-07-27 11:07:12 -0700345 case Token::kw_tf_control:
346 consumeToken(Token::kw_tf_control);
347 return builder.getTFControlType();
James Molloy72b0cbe2018-08-01 12:55:27 -0700348 case Token::kw_tf_string:
349 consumeToken(Token::kw_tf_string);
350 return builder.getTFStringType();
Chris Lattnerf958bbe2018-06-29 22:08:05 -0700351 }
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700352}
353
354/// Parse a vector type.
355///
356/// vector-type ::= `vector` `<` const-dimension-list primitive-type `>`
357/// const-dimension-list ::= (integer-literal `x`)+
358///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700359VectorType *Parser::parseVectorType() {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700360 consumeToken(Token::kw_vector);
361
Chris Lattnerf7702a62018-07-23 17:30:01 -0700362 if (parseToken(Token::less, "expected '<' in vector type"))
363 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700364
Chris Lattner48af7d12018-07-09 19:05:38 -0700365 if (getToken().isNot(Token::integer))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700366 return (emitError("expected dimension size in vector type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700367
368 SmallVector<unsigned, 4> dimensions;
Chris Lattner48af7d12018-07-09 19:05:38 -0700369 while (getToken().is(Token::integer)) {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700370 // Make sure this integer value is in bound and valid.
Chris Lattner48af7d12018-07-09 19:05:38 -0700371 auto dimension = getToken().getUnsignedIntegerValue();
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700372 if (!dimension.hasValue())
Chris Lattnerf7e22732018-06-22 22:03:48 -0700373 return (emitError("invalid dimension in vector type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700374 dimensions.push_back(dimension.getValue());
375
376 consumeToken(Token::integer);
377
378 // Make sure we have an 'x' or something like 'xbf32'.
Chris Lattner48af7d12018-07-09 19:05:38 -0700379 if (getToken().isNot(Token::bare_identifier) ||
380 getTokenSpelling()[0] != 'x')
Chris Lattnerf7e22732018-06-22 22:03:48 -0700381 return (emitError("expected 'x' in vector dimension list"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700382
383 // If we had a prefix of 'x', lex the next token immediately after the 'x'.
Chris Lattner48af7d12018-07-09 19:05:38 -0700384 if (getTokenSpelling().size() != 1)
385 state.lex.resetPointer(getTokenSpelling().data() + 1);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700386
387 // Consume the 'x'.
388 consumeToken(Token::bare_identifier);
389 }
390
391 // Parse the element type.
Chris Lattnerc3251192018-07-27 13:09:58 -0700392 auto typeLoc = getToken().getLoc();
393 auto *elementType = parseType();
394 if (!elementType || parseToken(Token::greater, "expected '>' in vector type"))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700395 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700396
Chris Lattnerc3251192018-07-27 13:09:58 -0700397 if (!isa<FloatType>(elementType) && !isa<IntegerType>(elementType))
398 return (emitError(typeLoc, "invalid vector element type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700399
Chris Lattnerf7e22732018-06-22 22:03:48 -0700400 return VectorType::get(dimensions, elementType);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700401}
402
403/// Parse a dimension list of a tensor or memref type. This populates the
404/// dimension list, returning -1 for the '?' dimensions.
405///
406/// dimension-list-ranked ::= (dimension `x`)*
407/// dimension ::= `?` | integer-literal
408///
409ParseResult Parser::parseDimensionListRanked(SmallVectorImpl<int> &dimensions) {
Chris Lattner48af7d12018-07-09 19:05:38 -0700410 while (getToken().isAny(Token::integer, Token::question)) {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700411 if (consumeIf(Token::question)) {
412 dimensions.push_back(-1);
413 } else {
414 // Make sure this integer value is in bound and valid.
Chris Lattner48af7d12018-07-09 19:05:38 -0700415 auto dimension = getToken().getUnsignedIntegerValue();
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700416 if (!dimension.hasValue() || (int)dimension.getValue() < 0)
417 return emitError("invalid dimension");
418 dimensions.push_back((int)dimension.getValue());
419 consumeToken(Token::integer);
420 }
421
422 // Make sure we have an 'x' or something like 'xbf32'.
Chris Lattner48af7d12018-07-09 19:05:38 -0700423 if (getToken().isNot(Token::bare_identifier) ||
424 getTokenSpelling()[0] != 'x')
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700425 return emitError("expected 'x' in dimension list");
426
427 // If we had a prefix of 'x', lex the next token immediately after the 'x'.
Chris Lattner48af7d12018-07-09 19:05:38 -0700428 if (getTokenSpelling().size() != 1)
429 state.lex.resetPointer(getTokenSpelling().data() + 1);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700430
431 // Consume the 'x'.
432 consumeToken(Token::bare_identifier);
433 }
434
435 return ParseSuccess;
436}
437
438/// Parse a tensor type.
439///
440/// tensor-type ::= `tensor` `<` dimension-list element-type `>`
441/// dimension-list ::= dimension-list-ranked | `??`
442///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700443Type *Parser::parseTensorType() {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700444 consumeToken(Token::kw_tensor);
445
Chris Lattnerf7702a62018-07-23 17:30:01 -0700446 if (parseToken(Token::less, "expected '<' in tensor type"))
447 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700448
449 bool isUnranked;
450 SmallVector<int, 4> dimensions;
451
452 if (consumeIf(Token::questionquestion)) {
453 isUnranked = true;
454 } else {
455 isUnranked = false;
456 if (parseDimensionListRanked(dimensions))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700457 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700458 }
459
460 // Parse the element type.
Chris Lattnerc3251192018-07-27 13:09:58 -0700461 auto typeLoc = getToken().getLoc();
462 auto *elementType = parseType();
463 if (!elementType || parseToken(Token::greater, "expected '>' in tensor type"))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700464 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700465
Chris Lattnerc3251192018-07-27 13:09:58 -0700466 if (!isa<IntegerType>(elementType) && !isa<FloatType>(elementType) &&
467 !isa<VectorType>(elementType))
468 return (emitError(typeLoc, "invalid tensor element type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700469
MLIR Team355ec862018-06-23 18:09:09 -0700470 if (isUnranked)
Chris Lattner158e0a3e2018-07-08 20:51:38 -0700471 return builder.getTensorType(elementType);
472 return builder.getTensorType(dimensions, elementType);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700473}
474
475/// Parse a memref type.
476///
477/// memref-type ::= `memref` `<` dimension-list-ranked element-type
478/// (`,` semi-affine-map-composition)? (`,` memory-space)? `>`
479///
480/// semi-affine-map-composition ::= (semi-affine-map `,` )* semi-affine-map
481/// memory-space ::= integer-literal /* | TODO: address-space-id */
482///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700483Type *Parser::parseMemRefType() {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700484 consumeToken(Token::kw_memref);
485
Chris Lattnerf7702a62018-07-23 17:30:01 -0700486 if (parseToken(Token::less, "expected '<' in memref type"))
487 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700488
489 SmallVector<int, 4> dimensions;
490 if (parseDimensionListRanked(dimensions))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700491 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700492
493 // Parse the element type.
Chris Lattnerc3251192018-07-27 13:09:58 -0700494 auto typeLoc = getToken().getLoc();
495 auto *elementType = parseType();
Chris Lattnerf7e22732018-06-22 22:03:48 -0700496 if (!elementType)
497 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700498
Chris Lattnerc3251192018-07-27 13:09:58 -0700499 if (!isa<IntegerType>(elementType) && !isa<FloatType>(elementType) &&
500 !isa<VectorType>(elementType))
501 return (emitError(typeLoc, "invalid memref element type"), nullptr);
502
MLIR Team718c82f2018-07-16 09:45:22 -0700503 // Parse semi-affine-map-composition.
James Molloy0ff71542018-07-23 16:56:32 -0700504 SmallVector<AffineMap *, 2> affineMapComposition;
Chris Lattner413db6a2018-07-25 12:55:50 -0700505 unsigned memorySpace = 0;
MLIR Team718c82f2018-07-16 09:45:22 -0700506 bool parsedMemorySpace = false;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700507
MLIR Team718c82f2018-07-16 09:45:22 -0700508 auto parseElt = [&]() -> ParseResult {
509 if (getToken().is(Token::integer)) {
510 // Parse memory space.
511 if (parsedMemorySpace)
512 return emitError("multiple memory spaces specified in memref type");
513 auto v = getToken().getUnsignedIntegerValue();
514 if (!v.hasValue())
515 return emitError("invalid memory space in memref type");
516 memorySpace = v.getValue();
517 consumeToken(Token::integer);
518 parsedMemorySpace = true;
519 } else {
520 // Parse affine map.
521 if (parsedMemorySpace)
522 return emitError("affine map after memory space in memref type");
James Molloy0ff71542018-07-23 16:56:32 -0700523 auto *affineMap = parseAffineMapReference();
MLIR Team718c82f2018-07-16 09:45:22 -0700524 if (affineMap == nullptr)
525 return ParseFailure;
526 affineMapComposition.push_back(affineMap);
527 }
528 return ParseSuccess;
529 };
530
Chris Lattner413db6a2018-07-25 12:55:50 -0700531 // Parse a list of mappings and address space if present.
532 if (consumeIf(Token::comma)) {
533 // Parse comma separated list of affine maps, followed by memory space.
534 if (parseCommaSeparatedListUntil(Token::greater, parseElt,
535 /*allowEmptyList=*/false)) {
536 return nullptr;
537 }
538 } else {
539 if (parseToken(Token::greater, "expected ',' or '>' in memref type"))
540 return nullptr;
MLIR Team718c82f2018-07-16 09:45:22 -0700541 }
MLIR Team718c82f2018-07-16 09:45:22 -0700542
543 return MemRefType::get(dimensions, elementType, affineMapComposition,
544 memorySpace);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700545}
546
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700547/// Parse a function type.
548///
549/// function-type ::= type-list-parens `->` type-list
550///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700551Type *Parser::parseFunctionType() {
Chris Lattner48af7d12018-07-09 19:05:38 -0700552 assert(getToken().is(Token::l_paren));
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700553
Chris Lattnerf7702a62018-07-23 17:30:01 -0700554 SmallVector<Type *, 4> arguments, results;
555 if (parseTypeList(arguments) ||
556 parseToken(Token::arrow, "expected '->' in function type") ||
557 parseTypeList(results))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700558 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700559
Chris Lattner158e0a3e2018-07-08 20:51:38 -0700560 return builder.getFunctionType(arguments, results);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700561}
562
Chris Lattner1604e472018-07-23 08:42:19 -0700563/// Parse a list of types without an enclosing parenthesis. The list must have
564/// at least one member.
565///
566/// type-list-no-parens ::= type (`,` type)*
567///
568ParseResult Parser::parseTypeListNoParens(SmallVectorImpl<Type *> &elements) {
569 auto parseElt = [&]() -> ParseResult {
570 auto elt = parseType();
571 elements.push_back(elt);
572 return elt ? ParseSuccess : ParseFailure;
573 };
574
575 return parseCommaSeparatedList(parseElt);
576}
577
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700578/// Parse a "type list", which is a singular type, or a parenthesized list of
579/// types.
580///
581/// type-list ::= type-list-parens | type
582/// type-list-parens ::= `(` `)`
Chris Lattner1604e472018-07-23 08:42:19 -0700583/// | `(` type-list-no-parens `)`
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700584///
James Molloy0ff71542018-07-23 16:56:32 -0700585ParseResult Parser::parseTypeList(SmallVectorImpl<Type *> &elements) {
Chris Lattnerf7e22732018-06-22 22:03:48 -0700586 auto parseElt = [&]() -> ParseResult {
587 auto elt = parseType();
588 elements.push_back(elt);
589 return elt ? ParseSuccess : ParseFailure;
590 };
591
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700592 // If there is no parens, then it must be a singular type.
593 if (!consumeIf(Token::l_paren))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700594 return parseElt();
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700595
Chris Lattner40746442018-07-21 14:32:09 -0700596 if (parseCommaSeparatedListUntil(Token::r_paren, parseElt))
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700597 return ParseFailure;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700598
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700599 return ParseSuccess;
600}
601
Chris Lattner4c95a502018-06-23 16:03:42 -0700602//===----------------------------------------------------------------------===//
Chris Lattner7121b802018-07-04 20:45:39 -0700603// Attribute parsing.
604//===----------------------------------------------------------------------===//
605
Chris Lattner1aa46322018-08-21 17:55:22 -0700606/// Given a parsed reference to a function name like @foo and a type that it
607/// corresponds to, resolve it to a concrete function object (possibly
608/// synthesizing a forward reference) or emit an error and return null on
609/// failure.
610Function *Parser::resolveFunctionReference(StringRef nameStr, SMLoc nameLoc,
611 FunctionType *type) {
612 Identifier name = builder.getIdentifier(nameStr.drop_front());
613
614 // See if the function has already been defined in the module.
615 Function *function = getModule()->getNamedFunction(name);
616
617 // If not, get or create a forward reference to one.
618 if (!function) {
619 auto &entry = state.functionForwardRefs[name];
620 if (!entry.first) {
621 entry.first = new ExtFunction(name, type);
622 entry.second = nameLoc;
623 }
624 function = entry.first;
625 }
626
627 if (function->getType() != type)
628 return (emitError(nameLoc, "reference to function with mismatched type"),
629 nullptr);
630 return function;
631}
632
Chris Lattner7121b802018-07-04 20:45:39 -0700633/// Attribute parsing.
634///
635/// attribute-value ::= bool-literal
636/// | integer-literal
637/// | float-literal
638/// | string-literal
James Molloyf0d2f442018-08-03 01:54:46 -0700639/// | type
Chris Lattner7121b802018-07-04 20:45:39 -0700640/// | `[` (attribute-value (`,` attribute-value)*)? `]`
Chris Lattner4613d9e2018-08-19 21:17:22 -0700641/// | function-id `:` function-type
Chris Lattner7121b802018-07-04 20:45:39 -0700642///
643Attribute *Parser::parseAttribute() {
Chris Lattner48af7d12018-07-09 19:05:38 -0700644 switch (getToken().getKind()) {
Chris Lattner7121b802018-07-04 20:45:39 -0700645 case Token::kw_true:
646 consumeToken(Token::kw_true);
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700647 return builder.getBoolAttr(true);
Chris Lattner7121b802018-07-04 20:45:39 -0700648 case Token::kw_false:
649 consumeToken(Token::kw_false);
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700650 return builder.getBoolAttr(false);
Chris Lattner7121b802018-07-04 20:45:39 -0700651
Jacques Pienaar84491092018-07-31 17:15:15 -0700652 case Token::floatliteral: {
653 auto val = getToken().getFloatingPointValue();
654 if (!val.hasValue())
655 return (emitError("floating point value too large for attribute"),
656 nullptr);
657 consumeToken(Token::floatliteral);
658 return builder.getFloatAttr(val.getValue());
659 }
Chris Lattner7121b802018-07-04 20:45:39 -0700660 case Token::integer: {
Chris Lattner48af7d12018-07-09 19:05:38 -0700661 auto val = getToken().getUInt64IntegerValue();
Chris Lattner7121b802018-07-04 20:45:39 -0700662 if (!val.hasValue() || (int64_t)val.getValue() < 0)
663 return (emitError("integer too large for attribute"), nullptr);
664 consumeToken(Token::integer);
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700665 return builder.getIntegerAttr((int64_t)val.getValue());
Chris Lattner7121b802018-07-04 20:45:39 -0700666 }
667
668 case Token::minus: {
669 consumeToken(Token::minus);
Chris Lattner48af7d12018-07-09 19:05:38 -0700670 if (getToken().is(Token::integer)) {
671 auto val = getToken().getUInt64IntegerValue();
Chris Lattner7121b802018-07-04 20:45:39 -0700672 if (!val.hasValue() || (int64_t)-val.getValue() >= 0)
673 return (emitError("integer too large for attribute"), nullptr);
674 consumeToken(Token::integer);
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700675 return builder.getIntegerAttr((int64_t)-val.getValue());
Chris Lattner7121b802018-07-04 20:45:39 -0700676 }
Jacques Pienaar84491092018-07-31 17:15:15 -0700677 if (getToken().is(Token::floatliteral)) {
678 auto val = getToken().getFloatingPointValue();
679 if (!val.hasValue())
680 return (emitError("floating point value too large for attribute"),
681 nullptr);
682 consumeToken(Token::floatliteral);
683 return builder.getFloatAttr(-val.getValue());
684 }
Chris Lattner7121b802018-07-04 20:45:39 -0700685
686 return (emitError("expected constant integer or floating point value"),
687 nullptr);
688 }
689
690 case Token::string: {
Chris Lattner48af7d12018-07-09 19:05:38 -0700691 auto val = getToken().getStringValue();
Chris Lattner7121b802018-07-04 20:45:39 -0700692 consumeToken(Token::string);
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700693 return builder.getStringAttr(val);
Chris Lattner7121b802018-07-04 20:45:39 -0700694 }
695
Chris Lattner85ee1512018-07-25 11:15:20 -0700696 case Token::l_square: {
697 consumeToken(Token::l_square);
James Molloy0ff71542018-07-23 16:56:32 -0700698 SmallVector<Attribute *, 4> elements;
Chris Lattner7121b802018-07-04 20:45:39 -0700699
700 auto parseElt = [&]() -> ParseResult {
701 elements.push_back(parseAttribute());
702 return elements.back() ? ParseSuccess : ParseFailure;
703 };
704
Chris Lattner85ee1512018-07-25 11:15:20 -0700705 if (parseCommaSeparatedListUntil(Token::r_square, parseElt))
Chris Lattner7121b802018-07-04 20:45:39 -0700706 return nullptr;
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700707 return builder.getArrayAttr(elements);
Chris Lattner7121b802018-07-04 20:45:39 -0700708 }
James Molloyf0d2f442018-08-03 01:54:46 -0700709 case Token::hash_identifier:
710 case Token::l_paren: {
MLIR Teamb61885d2018-07-18 16:29:21 -0700711 // Try to parse affine map reference.
James Molloyf0d2f442018-08-03 01:54:46 -0700712 if (auto *affineMap = parseAffineMapReference())
MLIR Teamb61885d2018-07-18 16:29:21 -0700713 return builder.getAffineMapAttr(affineMap);
Chris Lattner7121b802018-07-04 20:45:39 -0700714 return (emitError("expected constant attribute value"), nullptr);
715 }
Chris Lattner4613d9e2018-08-19 21:17:22 -0700716
717 case Token::at_identifier: {
718 auto nameLoc = getToken().getLoc();
Chris Lattner1aa46322018-08-21 17:55:22 -0700719 auto nameStr = getTokenSpelling();
Chris Lattner4613d9e2018-08-19 21:17:22 -0700720 consumeToken(Token::at_identifier);
721
722 if (parseToken(Token::colon, "expected ':' and function type"))
723 return nullptr;
724 auto typeLoc = getToken().getLoc();
725 Type *type = parseType();
726 if (!type)
727 return nullptr;
Chris Lattner1aa46322018-08-21 17:55:22 -0700728 auto *fnType = dyn_cast<FunctionType>(type);
Chris Lattner4613d9e2018-08-19 21:17:22 -0700729 if (!fnType)
730 return (emitError(typeLoc, "expected function type"), nullptr);
731
Chris Lattner1aa46322018-08-21 17:55:22 -0700732 auto *function = resolveFunctionReference(nameStr, nameLoc, fnType);
733 return function ? builder.getFunctionAttr(function) : nullptr;
Chris Lattner4613d9e2018-08-19 21:17:22 -0700734 }
735
James Molloyf0d2f442018-08-03 01:54:46 -0700736 default: {
737 if (Type *type = parseType())
738 return builder.getTypeAttr(type);
739 return nullptr;
740 }
741 }
Chris Lattner7121b802018-07-04 20:45:39 -0700742}
743
Chris Lattner7121b802018-07-04 20:45:39 -0700744/// Attribute dictionary.
745///
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700746/// attribute-dict ::= `{` `}`
747/// | `{` attribute-entry (`,` attribute-entry)* `}`
748/// attribute-entry ::= bare-id `:` attribute-value
Chris Lattner7121b802018-07-04 20:45:39 -0700749///
James Molloy0ff71542018-07-23 16:56:32 -0700750ParseResult
751Parser::parseAttributeDict(SmallVectorImpl<NamedAttribute> &attributes) {
Chris Lattner7121b802018-07-04 20:45:39 -0700752 consumeToken(Token::l_brace);
753
754 auto parseElt = [&]() -> ParseResult {
755 // We allow keywords as attribute names.
Chris Lattner48af7d12018-07-09 19:05:38 -0700756 if (getToken().isNot(Token::bare_identifier, Token::inttype) &&
757 !getToken().isKeyword())
Chris Lattner7121b802018-07-04 20:45:39 -0700758 return emitError("expected attribute name");
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700759 auto nameId = builder.getIdentifier(getTokenSpelling());
Chris Lattner7121b802018-07-04 20:45:39 -0700760 consumeToken();
761
Chris Lattnerf7702a62018-07-23 17:30:01 -0700762 if (parseToken(Token::colon, "expected ':' in attribute list"))
763 return ParseFailure;
Chris Lattner7121b802018-07-04 20:45:39 -0700764
765 auto attr = parseAttribute();
James Molloy0ff71542018-07-23 16:56:32 -0700766 if (!attr)
767 return ParseFailure;
Chris Lattner7121b802018-07-04 20:45:39 -0700768
769 attributes.push_back({nameId, attr});
770 return ParseSuccess;
771 };
772
Chris Lattner40746442018-07-21 14:32:09 -0700773 if (parseCommaSeparatedListUntil(Token::r_brace, parseElt))
Chris Lattner7121b802018-07-04 20:45:39 -0700774 return ParseFailure;
775
776 return ParseSuccess;
777}
778
779//===----------------------------------------------------------------------===//
MLIR Teamf85a6262018-06-27 11:03:08 -0700780// Polyhedral structures.
781//===----------------------------------------------------------------------===//
782
Chris Lattner2e595eb2018-07-10 10:08:27 -0700783/// Lower precedence ops (all at the same precedence level). LNoOp is false in
784/// the boolean sense.
785enum AffineLowPrecOp {
786 /// Null value.
787 LNoOp,
788 Add,
789 Sub
790};
MLIR Teamf85a6262018-06-27 11:03:08 -0700791
Chris Lattner2e595eb2018-07-10 10:08:27 -0700792/// Higher precedence ops - all at the same precedence level. HNoOp is false in
793/// the boolean sense.
794enum AffineHighPrecOp {
795 /// Null value.
796 HNoOp,
797 Mul,
798 FloorDiv,
799 CeilDiv,
800 Mod
801};
Chris Lattner7121b802018-07-04 20:45:39 -0700802
Chris Lattner2e595eb2018-07-10 10:08:27 -0700803namespace {
Uday Bondhugulabc535622018-08-07 14:24:38 -0700804/// This is a specialized parser for affine structures (affine maps, affine
805/// expressions, and integer sets), maintaining the state transient to their
806/// bodies.
807class AffineParser : public Parser {
Chris Lattner2e595eb2018-07-10 10:08:27 -0700808public:
Uday Bondhugulabc535622018-08-07 14:24:38 -0700809 explicit AffineParser(ParserState &state) : Parser(state) {}
Chris Lattner7121b802018-07-04 20:45:39 -0700810
Chris Lattner2e595eb2018-07-10 10:08:27 -0700811 AffineMap *parseAffineMapInline();
Uday Bondhugulabc535622018-08-07 14:24:38 -0700812 IntegerSet *parseIntegerSetInline();
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -0700813
Chris Lattner2e595eb2018-07-10 10:08:27 -0700814private:
Chris Lattner2e595eb2018-07-10 10:08:27 -0700815 // Binary affine op parsing.
816 AffineLowPrecOp consumeIfLowPrecOp();
817 AffineHighPrecOp consumeIfHighPrecOp();
MLIR Teamf85a6262018-06-27 11:03:08 -0700818
Chris Lattner2e595eb2018-07-10 10:08:27 -0700819 // Identifier lists for polyhedral structures.
Chris Lattner413db6a2018-07-25 12:55:50 -0700820 ParseResult parseDimIdList(unsigned &numDims);
821 ParseResult parseSymbolIdList(unsigned &numSymbols);
822 ParseResult parseIdentifierDefinition(AffineExpr *idExpr);
Chris Lattner2e595eb2018-07-10 10:08:27 -0700823
824 AffineExpr *parseAffineExpr();
825 AffineExpr *parseParentheticalExpr();
826 AffineExpr *parseNegateExpression(AffineExpr *lhs);
827 AffineExpr *parseIntegerExpr();
828 AffineExpr *parseBareIdExpr();
829
830 AffineExpr *getBinaryAffineOpExpr(AffineHighPrecOp op, AffineExpr *lhs,
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700831 AffineExpr *rhs, SMLoc opLoc);
Chris Lattner2e595eb2018-07-10 10:08:27 -0700832 AffineExpr *getBinaryAffineOpExpr(AffineLowPrecOp op, AffineExpr *lhs,
833 AffineExpr *rhs);
834 AffineExpr *parseAffineOperandExpr(AffineExpr *lhs);
835 AffineExpr *parseAffineLowPrecOpExpr(AffineExpr *llhs,
836 AffineLowPrecOp llhsOp);
837 AffineExpr *parseAffineHighPrecOpExpr(AffineExpr *llhs,
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700838 AffineHighPrecOp llhsOp,
839 SMLoc llhsOpLoc);
Uday Bondhugulabc535622018-08-07 14:24:38 -0700840 AffineExpr *parseAffineConstraint(bool *isEq);
Chris Lattner2e595eb2018-07-10 10:08:27 -0700841
842private:
Chris Lattner413db6a2018-07-25 12:55:50 -0700843 SmallVector<std::pair<StringRef, AffineExpr *>, 4> dimsAndSymbols;
Chris Lattner2e595eb2018-07-10 10:08:27 -0700844};
845} // end anonymous namespace
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -0700846
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700847/// Create an affine binary high precedence op expression (mul's, div's, mod).
848/// opLoc is the location of the op token to be used to report errors
849/// for non-conforming expressions.
Uday Bondhugulabc535622018-08-07 14:24:38 -0700850AffineExpr *AffineParser::getBinaryAffineOpExpr(AffineHighPrecOp op,
851 AffineExpr *lhs,
852 AffineExpr *rhs, SMLoc opLoc) {
Uday Bondhugula0115dbb2018-07-11 21:31:07 -0700853 // TODO: make the error location info accurate.
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700854 switch (op) {
855 case Mul:
Uday Bondhugulacbe4cca2018-07-19 13:07:16 -0700856 if (!lhs->isSymbolicOrConstant() && !rhs->isSymbolicOrConstant()) {
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700857 emitError(opLoc, "non-affine expression: at least one of the multiply "
858 "operands has to be either a constant or symbolic");
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700859 return nullptr;
860 }
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700861 return builder.getMulExpr(lhs, rhs);
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700862 case FloorDiv:
Uday Bondhugulacbe4cca2018-07-19 13:07:16 -0700863 if (!rhs->isSymbolicOrConstant()) {
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700864 emitError(opLoc, "non-affine expression: right operand of floordiv "
865 "has to be either a constant or symbolic");
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700866 return nullptr;
867 }
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700868 return builder.getFloorDivExpr(lhs, rhs);
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700869 case CeilDiv:
Uday Bondhugulacbe4cca2018-07-19 13:07:16 -0700870 if (!rhs->isSymbolicOrConstant()) {
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700871 emitError(opLoc, "non-affine expression: right operand of ceildiv "
872 "has to be either a constant or symbolic");
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700873 return nullptr;
874 }
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700875 return builder.getCeilDivExpr(lhs, rhs);
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700876 case Mod:
Uday Bondhugulacbe4cca2018-07-19 13:07:16 -0700877 if (!rhs->isSymbolicOrConstant()) {
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700878 emitError(opLoc, "non-affine expression: right operand of mod "
879 "has to be either a constant or symbolic");
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700880 return nullptr;
881 }
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700882 return builder.getModExpr(lhs, rhs);
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700883 case HNoOp:
884 llvm_unreachable("can't create affine expression for null high prec op");
885 return nullptr;
886 }
887}
888
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700889/// Create an affine binary low precedence op expression (add, sub).
Uday Bondhugulabc535622018-08-07 14:24:38 -0700890AffineExpr *AffineParser::getBinaryAffineOpExpr(AffineLowPrecOp op,
891 AffineExpr *lhs,
892 AffineExpr *rhs) {
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700893 switch (op) {
894 case AffineLowPrecOp::Add:
Chris Lattner1ac20cb2018-07-10 10:59:53 -0700895 return builder.getAddExpr(lhs, rhs);
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700896 case AffineLowPrecOp::Sub:
Uday Bondhugulac1faf662018-07-19 14:08:50 -0700897 return builder.getAddExpr(
898 lhs, builder.getMulExpr(rhs, builder.getConstantExpr(-1)));
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700899 case AffineLowPrecOp::LNoOp:
900 llvm_unreachable("can't create affine expression for null low prec op");
901 return nullptr;
902 }
903}
904
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700905/// Consume this token if it is a lower precedence affine op (there are only two
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700906/// precedence levels).
Uday Bondhugulabc535622018-08-07 14:24:38 -0700907AffineLowPrecOp AffineParser::consumeIfLowPrecOp() {
Chris Lattner48af7d12018-07-09 19:05:38 -0700908 switch (getToken().getKind()) {
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700909 case Token::plus:
910 consumeToken(Token::plus);
911 return AffineLowPrecOp::Add;
912 case Token::minus:
913 consumeToken(Token::minus);
914 return AffineLowPrecOp::Sub;
915 default:
916 return AffineLowPrecOp::LNoOp;
917 }
918}
919
920/// Consume this token if it is a higher precedence affine op (there are only
921/// two precedence levels)
Uday Bondhugulabc535622018-08-07 14:24:38 -0700922AffineHighPrecOp AffineParser::consumeIfHighPrecOp() {
Chris Lattner48af7d12018-07-09 19:05:38 -0700923 switch (getToken().getKind()) {
Uday Bondhugula015cbb12018-07-03 20:16:08 -0700924 case Token::star:
925 consumeToken(Token::star);
926 return Mul;
927 case Token::kw_floordiv:
928 consumeToken(Token::kw_floordiv);
929 return FloorDiv;
930 case Token::kw_ceildiv:
931 consumeToken(Token::kw_ceildiv);
932 return CeilDiv;
933 case Token::kw_mod:
934 consumeToken(Token::kw_mod);
935 return Mod;
936 default:
937 return HNoOp;
938 }
939}
940
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700941/// Parse a high precedence op expression list: mul, div, and mod are high
942/// precedence binary ops, i.e., parse a
943/// expr_1 op_1 expr_2 op_2 ... expr_n
944/// where op_1, op_2 are all a AffineHighPrecOp (mul, div, mod).
945/// All affine binary ops are left associative.
946/// Given llhs, returns (llhs llhsOp lhs) op rhs, or (lhs op rhs) if llhs is
947/// null. If no rhs can be found, returns (llhs llhsOp lhs) or lhs if llhs is
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700948/// null. llhsOpLoc is the location of the llhsOp token that will be used to
949/// report an error for non-conforming expressions.
Uday Bondhugulabc535622018-08-07 14:24:38 -0700950AffineExpr *AffineParser::parseAffineHighPrecOpExpr(AffineExpr *llhs,
951 AffineHighPrecOp llhsOp,
952 SMLoc llhsOpLoc) {
Chris Lattner2e595eb2018-07-10 10:08:27 -0700953 AffineExpr *lhs = parseAffineOperandExpr(llhs);
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700954 if (!lhs)
955 return nullptr;
956
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700957 // Found an LHS. Parse the remaining expression.
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700958 auto opLoc = getToken().getLoc();
Chris Lattner2e595eb2018-07-10 10:08:27 -0700959 if (AffineHighPrecOp op = consumeIfHighPrecOp()) {
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700960 if (llhs) {
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700961 AffineExpr *expr = getBinaryAffineOpExpr(llhsOp, llhs, lhs, opLoc);
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700962 if (!expr)
963 return nullptr;
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700964 return parseAffineHighPrecOpExpr(expr, op, opLoc);
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700965 }
966 // No LLHS, get RHS
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700967 return parseAffineHighPrecOpExpr(lhs, op, opLoc);
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700968 }
969
970 // This is the last operand in this expression.
971 if (llhs)
Uday Bondhugula851b8fd2018-07-20 14:57:21 -0700972 return getBinaryAffineOpExpr(llhsOp, llhs, lhs, llhsOpLoc);
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700973
974 // No llhs, 'lhs' itself is the expression.
975 return lhs;
976}
977
978/// Parse an affine expression inside parentheses.
979///
980/// affine-expr ::= `(` affine-expr `)`
Uday Bondhugulabc535622018-08-07 14:24:38 -0700981AffineExpr *AffineParser::parseParentheticalExpr() {
Chris Lattnerf7702a62018-07-23 17:30:01 -0700982 if (parseToken(Token::l_paren, "expected '('"))
983 return nullptr;
Chris Lattner48af7d12018-07-09 19:05:38 -0700984 if (getToken().is(Token::r_paren))
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700985 return (emitError("no expression inside parentheses"), nullptr);
Chris Lattnerf7702a62018-07-23 17:30:01 -0700986
Chris Lattner2e595eb2018-07-10 10:08:27 -0700987 auto *expr = parseAffineExpr();
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700988 if (!expr)
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700989 return nullptr;
Chris Lattnerf7702a62018-07-23 17:30:01 -0700990 if (parseToken(Token::r_paren, "expected ')'"))
991 return nullptr;
992
Uday Bondhugula3934d4d2018-07-09 09:00:25 -0700993 return expr;
994}
995
996/// Parse the negation expression.
997///
998/// affine-expr ::= `-` affine-expr
Uday Bondhugulabc535622018-08-07 14:24:38 -0700999AffineExpr *AffineParser::parseNegateExpression(AffineExpr *lhs) {
Chris Lattnerf7702a62018-07-23 17:30:01 -07001000 if (parseToken(Token::minus, "expected '-'"))
1001 return nullptr;
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001002
Chris Lattner2e595eb2018-07-10 10:08:27 -07001003 AffineExpr *operand = parseAffineOperandExpr(lhs);
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001004 // Since negation has the highest precedence of all ops (including high
1005 // precedence ops) but lower than parentheses, we are only going to use
1006 // parseAffineOperandExpr instead of parseAffineExpr here.
1007 if (!operand)
1008 // Extra error message although parseAffineOperandExpr would have
1009 // complained. Leads to a better diagnostic.
1010 return (emitError("missing operand of negation"), nullptr);
Chris Lattner1ac20cb2018-07-10 10:59:53 -07001011 auto *minusOne = builder.getConstantExpr(-1);
1012 return builder.getMulExpr(minusOne, operand);
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001013}
1014
1015/// Parse a bare id that may appear in an affine expression.
1016///
1017/// affine-expr ::= bare-id
Uday Bondhugulabc535622018-08-07 14:24:38 -07001018AffineExpr *AffineParser::parseBareIdExpr() {
Chris Lattner48af7d12018-07-09 19:05:38 -07001019 if (getToken().isNot(Token::bare_identifier))
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001020 return (emitError("expected bare identifier"), nullptr);
1021
Chris Lattner48af7d12018-07-09 19:05:38 -07001022 StringRef sRef = getTokenSpelling();
Chris Lattner413db6a2018-07-25 12:55:50 -07001023 for (auto entry : dimsAndSymbols) {
Chris Lattnera8e47672018-07-25 14:08:16 -07001024 if (entry.first == sRef) {
1025 consumeToken(Token::bare_identifier);
1026 return entry.second;
1027 }
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001028 }
Uday Bondhugula0115dbb2018-07-11 21:31:07 -07001029
1030 return (emitError("use of undeclared identifier"), nullptr);
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001031}
1032
1033/// Parse a positive integral constant appearing in an affine expression.
1034///
1035/// affine-expr ::= integer-literal
Uday Bondhugulabc535622018-08-07 14:24:38 -07001036AffineExpr *AffineParser::parseIntegerExpr() {
Chris Lattner48af7d12018-07-09 19:05:38 -07001037 auto val = getToken().getUInt64IntegerValue();
Chris Lattnerea5c3dc2018-08-21 08:42:19 -07001038 if (!val.hasValue() || (int64_t)val.getValue() < 0)
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001039 return (emitError("constant too large for affineint"), nullptr);
Chris Lattnerea5c3dc2018-08-21 08:42:19 -07001040
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001041 consumeToken(Token::integer);
Chris Lattner1ac20cb2018-07-10 10:59:53 -07001042 return builder.getConstantExpr((int64_t)val.getValue());
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001043}
1044
1045/// Parses an expression that can be a valid operand of an affine expression.
Uday Bondhugula76345202018-07-09 13:47:52 -07001046/// lhs: if non-null, lhs is an affine expression that is the lhs of a binary
1047/// operator, the rhs of which is being parsed. This is used to determine
1048/// whether an error should be emitted for a missing right operand.
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001049// Eg: for an expression without parentheses (like i + j + k + l), each
1050// of the four identifiers is an operand. For i + j*k + l, j*k is not an
1051// operand expression, it's an op expression and will be parsed via
1052// parseAffineHighPrecOpExpression(). However, for i + (j*k) + -l, (j*k) and -l
1053// are valid operands that will be parsed by this function.
Uday Bondhugulabc535622018-08-07 14:24:38 -07001054AffineExpr *AffineParser::parseAffineOperandExpr(AffineExpr *lhs) {
Chris Lattner48af7d12018-07-09 19:05:38 -07001055 switch (getToken().getKind()) {
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001056 case Token::bare_identifier:
Chris Lattner2e595eb2018-07-10 10:08:27 -07001057 return parseBareIdExpr();
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001058 case Token::integer:
Chris Lattner2e595eb2018-07-10 10:08:27 -07001059 return parseIntegerExpr();
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001060 case Token::l_paren:
Chris Lattner2e595eb2018-07-10 10:08:27 -07001061 return parseParentheticalExpr();
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001062 case Token::minus:
Chris Lattner2e595eb2018-07-10 10:08:27 -07001063 return parseNegateExpression(lhs);
Uday Bondhugula76345202018-07-09 13:47:52 -07001064 case Token::kw_ceildiv:
1065 case Token::kw_floordiv:
1066 case Token::kw_mod:
1067 case Token::plus:
1068 case Token::star:
1069 if (lhs)
1070 emitError("missing right operand of binary operator");
1071 else
1072 emitError("missing left operand of binary operator");
1073 return nullptr;
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001074 default:
1075 if (lhs)
Uday Bondhugula76345202018-07-09 13:47:52 -07001076 emitError("missing right operand of binary operator");
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001077 else
1078 emitError("expected affine expression");
1079 return nullptr;
1080 }
1081}
1082
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001083/// Parse affine expressions that are bare-id's, integer constants,
1084/// parenthetical affine expressions, and affine op expressions that are a
1085/// composition of those.
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001086///
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001087/// All binary op's associate from left to right.
1088///
1089/// {add, sub} have lower precedence than {mul, div, and mod}.
1090///
Uday Bondhugula76345202018-07-09 13:47:52 -07001091/// Add, sub'are themselves at the same precedence level. Mul, floordiv,
1092/// ceildiv, and mod are at the same higher precedence level. Negation has
1093/// higher precedence than any binary op.
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001094///
1095/// llhs: the affine expression appearing on the left of the one being parsed.
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001096/// This function will return ((llhs llhsOp lhs) op rhs) if llhs is non null,
1097/// and lhs op rhs otherwise; if there is no rhs, llhs llhsOp lhs is returned if
1098/// llhs is non-null; otherwise lhs is returned. This is to deal with left
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001099/// associativity.
1100///
1101/// Eg: when the expression is e1 + e2*e3 + e4, with e1 as llhs, this function
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001102/// will return the affine expr equivalent of (e1 + (e2*e3)) + e4, where (e2*e3)
1103/// will be parsed using parseAffineHighPrecOpExpr().
Uday Bondhugulabc535622018-08-07 14:24:38 -07001104AffineExpr *AffineParser::parseAffineLowPrecOpExpr(AffineExpr *llhs,
1105 AffineLowPrecOp llhsOp) {
Uday Bondhugula76345202018-07-09 13:47:52 -07001106 AffineExpr *lhs;
Chris Lattner2e595eb2018-07-10 10:08:27 -07001107 if (!(lhs = parseAffineOperandExpr(llhs)))
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001108 return nullptr;
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001109
1110 // Found an LHS. Deal with the ops.
Chris Lattner2e595eb2018-07-10 10:08:27 -07001111 if (AffineLowPrecOp lOp = consumeIfLowPrecOp()) {
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001112 if (llhs) {
Chris Lattner158e0a3e2018-07-08 20:51:38 -07001113 AffineExpr *sum = getBinaryAffineOpExpr(llhsOp, llhs, lhs);
Chris Lattner2e595eb2018-07-10 10:08:27 -07001114 return parseAffineLowPrecOpExpr(sum, lOp);
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001115 }
1116 // No LLHS, get RHS and form the expression.
Chris Lattner2e595eb2018-07-10 10:08:27 -07001117 return parseAffineLowPrecOpExpr(lhs, lOp);
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001118 }
Uday Bondhugula851b8fd2018-07-20 14:57:21 -07001119 auto opLoc = getToken().getLoc();
Chris Lattner2e595eb2018-07-10 10:08:27 -07001120 if (AffineHighPrecOp hOp = consumeIfHighPrecOp()) {
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001121 // We have a higher precedence op here. Get the rhs operand for the llhs
1122 // through parseAffineHighPrecOpExpr.
Uday Bondhugula851b8fd2018-07-20 14:57:21 -07001123 AffineExpr *highRes = parseAffineHighPrecOpExpr(lhs, hOp, opLoc);
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001124 if (!highRes)
1125 return nullptr;
Chris Lattner2e595eb2018-07-10 10:08:27 -07001126
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001127 // If llhs is null, the product forms the first operand of the yet to be
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001128 // found expression. If non-null, the op to associate with llhs is llhsOp.
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001129 AffineExpr *expr =
Chris Lattner158e0a3e2018-07-08 20:51:38 -07001130 llhs ? getBinaryAffineOpExpr(llhsOp, llhs, highRes) : highRes;
Chris Lattner2e595eb2018-07-10 10:08:27 -07001131
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001132 // Recurse for subsequent low prec op's after the affine high prec op
1133 // expression.
Chris Lattner2e595eb2018-07-10 10:08:27 -07001134 if (AffineLowPrecOp nextOp = consumeIfLowPrecOp())
1135 return parseAffineLowPrecOpExpr(expr, nextOp);
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001136 return expr;
1137 }
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001138 // Last operand in the expression list.
1139 if (llhs)
1140 return getBinaryAffineOpExpr(llhsOp, llhs, lhs);
1141 // No llhs, 'lhs' itself is the expression.
1142 return lhs;
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001143}
1144
1145/// Parse an affine expression.
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001146/// affine-expr ::= `(` affine-expr `)`
1147/// | `-` affine-expr
1148/// | affine-expr `+` affine-expr
1149/// | affine-expr `-` affine-expr
1150/// | affine-expr `*` affine-expr
1151/// | affine-expr `floordiv` affine-expr
1152/// | affine-expr `ceildiv` affine-expr
1153/// | affine-expr `mod` affine-expr
1154/// | bare-id
1155/// | integer-literal
1156///
1157/// Additional conditions are checked depending on the production. For eg., one
1158/// of the operands for `*` has to be either constant/symbolic; the second
1159/// operand for floordiv, ceildiv, and mod has to be a positive integer.
Uday Bondhugulabc535622018-08-07 14:24:38 -07001160AffineExpr *AffineParser::parseAffineExpr() {
Chris Lattner2e595eb2018-07-10 10:08:27 -07001161 return parseAffineLowPrecOpExpr(nullptr, AffineLowPrecOp::LNoOp);
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001162}
1163
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001164/// Parse a dim or symbol from the lists appearing before the actual expressions
Chris Lattner2e595eb2018-07-10 10:08:27 -07001165/// of the affine map. Update our state to store the dimensional/symbolic
Chris Lattner413db6a2018-07-25 12:55:50 -07001166/// identifier.
Uday Bondhugulabc535622018-08-07 14:24:38 -07001167ParseResult AffineParser::parseIdentifierDefinition(AffineExpr *idExpr) {
Chris Lattner48af7d12018-07-09 19:05:38 -07001168 if (getToken().isNot(Token::bare_identifier))
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001169 return emitError("expected bare identifier");
Chris Lattner413db6a2018-07-25 12:55:50 -07001170
1171 auto name = getTokenSpelling();
1172 for (auto entry : dimsAndSymbols) {
1173 if (entry.first == name)
1174 return emitError("redefinition of identifier '" + Twine(name) + "'");
1175 }
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001176 consumeToken(Token::bare_identifier);
Chris Lattner413db6a2018-07-25 12:55:50 -07001177
1178 dimsAndSymbols.push_back({name, idExpr});
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001179 return ParseSuccess;
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001180}
1181
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001182/// Parse the list of symbolic identifiers to an affine map.
Uday Bondhugulabc535622018-08-07 14:24:38 -07001183ParseResult AffineParser::parseSymbolIdList(unsigned &numSymbols) {
Chris Lattner413db6a2018-07-25 12:55:50 -07001184 consumeToken(Token::l_square);
1185 auto parseElt = [&]() -> ParseResult {
1186 auto *symbol = AffineSymbolExpr::get(numSymbols++, getContext());
1187 return parseIdentifierDefinition(symbol);
1188 };
Chris Lattner85ee1512018-07-25 11:15:20 -07001189 return parseCommaSeparatedListUntil(Token::r_square, parseElt);
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001190}
1191
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001192/// Parse the list of dimensional identifiers to an affine map.
Uday Bondhugulabc535622018-08-07 14:24:38 -07001193ParseResult AffineParser::parseDimIdList(unsigned &numDims) {
Chris Lattnerf7702a62018-07-23 17:30:01 -07001194 if (parseToken(Token::l_paren,
1195 "expected '(' at start of dimensional identifiers list"))
1196 return ParseFailure;
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001197
Chris Lattner413db6a2018-07-25 12:55:50 -07001198 auto parseElt = [&]() -> ParseResult {
1199 auto *dimension = AffineDimExpr::get(numDims++, getContext());
1200 return parseIdentifierDefinition(dimension);
1201 };
Chris Lattner40746442018-07-21 14:32:09 -07001202 return parseCommaSeparatedListUntil(Token::r_paren, parseElt);
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001203}
1204
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001205/// Parse an affine map definition.
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001206///
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001207/// affine-map-inline ::= dim-and-symbol-id-lists `->` multi-dim-affine-expr
1208/// (`size` `(` dim-size (`,` dim-size)* `)`)?
1209/// dim-size ::= affine-expr | `min` `(` affine-expr ( `,` affine-expr)+ `)`
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001210///
Uday Bondhugula3934d4d2018-07-09 09:00:25 -07001211/// multi-dim-affine-expr ::= `(` affine-expr (`,` affine-expr)* `)
Uday Bondhugulabc535622018-08-07 14:24:38 -07001212AffineMap *AffineParser::parseAffineMapInline() {
Chris Lattner413db6a2018-07-25 12:55:50 -07001213 unsigned numDims = 0, numSymbols = 0;
1214
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001215 // List of dimensional identifiers.
Chris Lattner413db6a2018-07-25 12:55:50 -07001216 if (parseDimIdList(numDims))
Chris Lattner7121b802018-07-04 20:45:39 -07001217 return nullptr;
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001218
1219 // Symbols are optional.
Chris Lattner85ee1512018-07-25 11:15:20 -07001220 if (getToken().is(Token::l_square)) {
Chris Lattner413db6a2018-07-25 12:55:50 -07001221 if (parseSymbolIdList(numSymbols))
Chris Lattner7121b802018-07-04 20:45:39 -07001222 return nullptr;
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001223 }
Chris Lattnerf7702a62018-07-23 17:30:01 -07001224
1225 if (parseToken(Token::arrow, "expected '->' or '['") ||
1226 parseToken(Token::l_paren, "expected '(' at start of affine map range"))
Chris Lattner7121b802018-07-04 20:45:39 -07001227 return nullptr;
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001228
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001229 SmallVector<AffineExpr *, 4> exprs;
1230 auto parseElt = [&]() -> ParseResult {
Chris Lattner2e595eb2018-07-10 10:08:27 -07001231 auto *elt = parseAffineExpr();
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001232 ParseResult res = elt ? ParseSuccess : ParseFailure;
1233 exprs.push_back(elt);
1234 return res;
1235 };
1236
1237 // Parse a multi-dimensional affine expression (a comma-separated list of 1-d
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001238 // affine expressions); the list cannot be empty.
1239 // Grammar: multi-dim-affine-expr ::= `(` affine-expr (`,` affine-expr)* `)
Chris Lattner40746442018-07-21 14:32:09 -07001240 if (parseCommaSeparatedListUntil(Token::r_paren, parseElt, false))
Chris Lattner7121b802018-07-04 20:45:39 -07001241 return nullptr;
Uday Bondhugulafaf37dd2018-06-29 18:09:29 -07001242
Uday Bondhugula0115dbb2018-07-11 21:31:07 -07001243 // Parse optional range sizes.
Uday Bondhugula1e500b42018-07-12 18:04:04 -07001244 // range-sizes ::= (`size` `(` dim-size (`,` dim-size)* `)`)?
1245 // dim-size ::= affine-expr | `min` `(` affine-expr (`,` affine-expr)+ `)`
1246 // TODO(bondhugula): support for min of several affine expressions.
Uday Bondhugula0115dbb2018-07-11 21:31:07 -07001247 // TODO: check if sizes are non-negative whenever they are constant.
1248 SmallVector<AffineExpr *, 4> rangeSizes;
1249 if (consumeIf(Token::kw_size)) {
1250 // Location of the l_paren token (if it exists) for error reporting later.
1251 auto loc = getToken().getLoc();
Chris Lattnerf7702a62018-07-23 17:30:01 -07001252 if (parseToken(Token::l_paren, "expected '(' at start of affine map range"))
1253 return nullptr;
Uday Bondhugula0115dbb2018-07-11 21:31:07 -07001254
1255 auto parseRangeSize = [&]() -> ParseResult {
Chris Lattner413db6a2018-07-25 12:55:50 -07001256 auto loc = getToken().getLoc();
Uday Bondhugula0115dbb2018-07-11 21:31:07 -07001257 auto *elt = parseAffineExpr();
Chris Lattner413db6a2018-07-25 12:55:50 -07001258 if (!elt)
1259 return ParseFailure;
1260
1261 if (!elt->isSymbolicOrConstant())
1262 return emitError(loc,
1263 "size expressions cannot refer to dimension values");
1264
Uday Bondhugula0115dbb2018-07-11 21:31:07 -07001265 rangeSizes.push_back(elt);
Chris Lattner413db6a2018-07-25 12:55:50 -07001266 return ParseSuccess;
Uday Bondhugula0115dbb2018-07-11 21:31:07 -07001267 };
1268
Chris Lattner40746442018-07-21 14:32:09 -07001269 if (parseCommaSeparatedListUntil(Token::r_paren, parseRangeSize, false))
Uday Bondhugula0115dbb2018-07-11 21:31:07 -07001270 return nullptr;
1271 if (exprs.size() > rangeSizes.size())
1272 return (emitError(loc, "fewer range sizes than range expressions"),
1273 nullptr);
1274 if (exprs.size() < rangeSizes.size())
1275 return (emitError(loc, "more range sizes than range expressions"),
1276 nullptr);
1277 }
1278
Uday Bondhugula015cbb12018-07-03 20:16:08 -07001279 // Parsed a valid affine map.
Chris Lattner413db6a2018-07-25 12:55:50 -07001280 return builder.getAffineMap(numDims, numSymbols, exprs, rangeSizes);
MLIR Teamf85a6262018-06-27 11:03:08 -07001281}
1282
Chris Lattner2e595eb2018-07-10 10:08:27 -07001283AffineMap *Parser::parseAffineMapInline() {
Uday Bondhugulabc535622018-08-07 14:24:38 -07001284 return AffineParser(state).parseAffineMapInline();
Chris Lattner2e595eb2018-07-10 10:08:27 -07001285}
1286
MLIR Team718c82f2018-07-16 09:45:22 -07001287AffineMap *Parser::parseAffineMapReference() {
1288 if (getToken().is(Token::hash_identifier)) {
1289 // Parse affine map identifier and verify that it exists.
1290 StringRef affineMapId = getTokenSpelling().drop_front();
1291 if (getState().affineMapDefinitions.count(affineMapId) == 0)
1292 return (emitError("undefined affine map id '" + affineMapId + "'"),
1293 nullptr);
1294 consumeToken(Token::hash_identifier);
1295 return getState().affineMapDefinitions[affineMapId];
1296 }
1297 // Try to parse inline affine map.
1298 return parseAffineMapInline();
1299}
1300
MLIR Teamf85a6262018-06-27 11:03:08 -07001301//===----------------------------------------------------------------------===//
Chris Lattner7f9cc272018-07-19 08:35:28 -07001302// FunctionParser
Chris Lattner4c95a502018-06-23 16:03:42 -07001303//===----------------------------------------------------------------------===//
Chris Lattnere79379a2018-06-22 10:39:19 -07001304
Chris Lattner7f9cc272018-07-19 08:35:28 -07001305namespace {
1306/// This class contains parser state that is common across CFG and ML functions,
1307/// notably for dealing with operations and SSA values.
1308class FunctionParser : public Parser {
1309public:
Tatiana Shpeisman60bf7be2018-07-26 18:09:20 -07001310 enum class Kind { CFGFunc, MLFunc };
1311
1312 Kind getKind() const { return kind; }
Chris Lattner7f9cc272018-07-19 08:35:28 -07001313
Chris Lattner6119d382018-07-20 18:41:34 -07001314 /// After the function is finished parsing, this function checks to see if
1315 /// there are any remaining issues.
Chris Lattner40746442018-07-21 14:32:09 -07001316 ParseResult finalizeFunction(Function *func, SMLoc loc);
Chris Lattner6119d382018-07-20 18:41:34 -07001317
1318 /// This represents a use of an SSA value in the program. The first two
1319 /// entries in the tuple are the name and result number of a reference. The
1320 /// third is the location of the reference, which is used in case this ends up
1321 /// being a use of an undefined value.
1322 struct SSAUseInfo {
1323 StringRef name; // Value name, e.g. %42 or %abc
1324 unsigned number; // Number, specified with #12
1325 SMLoc loc; // Location of first definition or use.
1326 };
Chris Lattner7f9cc272018-07-19 08:35:28 -07001327
1328 /// Given a reference to an SSA value and its type, return a reference. This
1329 /// returns null on failure.
1330 SSAValue *resolveSSAUse(SSAUseInfo useInfo, Type *type);
1331
1332 /// Register a definition of a value with the symbol table.
1333 ParseResult addDefinition(SSAUseInfo useInfo, SSAValue *value);
1334
1335 // SSA parsing productions.
1336 ParseResult parseSSAUse(SSAUseInfo &result);
Chris Lattner40746442018-07-21 14:32:09 -07001337 ParseResult parseOptionalSSAUseList(SmallVectorImpl<SSAUseInfo> &results);
James Molloy61a656c2018-07-22 15:45:24 -07001338
1339 template <typename ResultType>
1340 ResultType parseSSADefOrUseAndType(
1341 const std::function<ResultType(SSAUseInfo, Type *)> &action);
1342
1343 SSAValue *parseSSAUseAndType() {
1344 return parseSSADefOrUseAndType<SSAValue *>(
1345 [&](SSAUseInfo useInfo, Type *type) -> SSAValue * {
1346 return resolveSSAUse(useInfo, type);
1347 });
1348 }
Chris Lattner40746442018-07-21 14:32:09 -07001349
1350 template <typename ValueTy>
Chris Lattner7f9cc272018-07-19 08:35:28 -07001351 ParseResult
Chris Lattner2c402672018-07-23 11:56:17 -07001352 parseOptionalSSAUseAndTypeList(SmallVectorImpl<ValueTy *> &results,
1353 bool isParenthesized);
Chris Lattner7f9cc272018-07-19 08:35:28 -07001354
1355 // Operations
1356 ParseResult parseOperation(const CreateOperationFunction &createOpFunc);
Chris Lattner85ee1512018-07-25 11:15:20 -07001357 Operation *parseVerboseOperation(const CreateOperationFunction &createOpFunc);
1358 Operation *parseCustomOperation(const CreateOperationFunction &createOpFunc);
Chris Lattner7f9cc272018-07-19 08:35:28 -07001359
Tatiana Shpeisman60bf7be2018-07-26 18:09:20 -07001360protected:
1361 FunctionParser(ParserState &state, Kind kind) : Parser(state), kind(kind) {}
1362
Chris Lattner7f9cc272018-07-19 08:35:28 -07001363private:
Tatiana Shpeisman60bf7be2018-07-26 18:09:20 -07001364 /// Kind indicates if this is CFG or ML function parser.
1365 Kind kind;
Chris Lattner7f9cc272018-07-19 08:35:28 -07001366 /// This keeps track of all of the SSA values we are tracking, indexed by
Chris Lattner6119d382018-07-20 18:41:34 -07001367 /// their name. This has one entry per result number.
1368 llvm::StringMap<SmallVector<std::pair<SSAValue *, SMLoc>, 1>> values;
1369
1370 /// These are all of the placeholders we've made along with the location of
1371 /// their first reference, to allow checking for use of undefined values.
1372 DenseMap<SSAValue *, SMLoc> forwardReferencePlaceholders;
1373
1374 SSAValue *createForwardReferencePlaceholder(SMLoc loc, Type *type);
1375
1376 /// Return true if this is a forward reference.
1377 bool isForwardReferencePlaceholder(SSAValue *value) {
1378 return forwardReferencePlaceholders.count(value);
1379 }
Chris Lattner7f9cc272018-07-19 08:35:28 -07001380};
1381} // end anonymous namespace
1382
Chris Lattner6119d382018-07-20 18:41:34 -07001383/// Create and remember a new placeholder for a forward reference.
1384SSAValue *FunctionParser::createForwardReferencePlaceholder(SMLoc loc,
1385 Type *type) {
1386 // Forward references are always created as instructions, even in ML
1387 // functions, because we just need something with a def/use chain.
1388 //
1389 // We create these placeholders as having an empty name, which we know cannot
1390 // be created through normal user input, allowing us to distinguish them.
1391 auto name = Identifier::get("placeholder", getContext());
Chris Lattner1628fa02018-08-23 14:32:25 -07001392 auto *inst =
1393 // FIXME(clattner): encode the location into the placeholder instead of
1394 // into the forwardReferencePlaceholders map!
1395 OperationInst::create(/*location=*/nullptr, name, /*operands=*/{}, type,
1396 /*attrs=*/{}, getContext());
Chris Lattner6119d382018-07-20 18:41:34 -07001397 forwardReferencePlaceholders[inst->getResult(0)] = loc;
1398 return inst->getResult(0);
1399}
1400
Tatiana Shpeisman60bf7be2018-07-26 18:09:20 -07001401/// Given an unbound reference to an SSA value and its type, return the value
Chris Lattner7f9cc272018-07-19 08:35:28 -07001402/// it specifies. This returns null on failure.
1403SSAValue *FunctionParser::resolveSSAUse(SSAUseInfo useInfo, Type *type) {
Chris Lattner6119d382018-07-20 18:41:34 -07001404 auto &entries = values[useInfo.name];
1405
Chris Lattner7f9cc272018-07-19 08:35:28 -07001406 // If we have already seen a value of this name, return it.
Chris Lattner6119d382018-07-20 18:41:34 -07001407 if (useInfo.number < entries.size() && entries[useInfo.number].first) {
1408 auto *result = entries[useInfo.number].first;
Chris Lattner7f9cc272018-07-19 08:35:28 -07001409 // Check that the type matches the other uses.
Chris Lattner7f9cc272018-07-19 08:35:28 -07001410 if (result->getType() == type)
1411 return result;
1412
Chris Lattner6119d382018-07-20 18:41:34 -07001413 emitError(useInfo.loc, "use of value '" + useInfo.name.str() +
1414 "' expects different type than prior uses");
1415 emitError(entries[useInfo.number].second, "prior use here");
Chris Lattner7f9cc272018-07-19 08:35:28 -07001416 return nullptr;
1417 }
1418
Chris Lattner6119d382018-07-20 18:41:34 -07001419 // Make sure we have enough slots for this.
1420 if (entries.size() <= useInfo.number)
1421 entries.resize(useInfo.number + 1);
1422
1423 // If the value has already been defined and this is an overly large result
1424 // number, diagnose that.
1425 if (entries[0].first && !isForwardReferencePlaceholder(entries[0].first))
1426 return (emitError(useInfo.loc, "reference to invalid result number"),
1427 nullptr);
1428
Tatiana Shpeismand880b352018-07-31 23:14:16 -07001429 // Otherwise, this is a forward reference. If we are in ML function return
1430 // an error. In CFG function, create a placeholder and remember
1431 // that we did so.
Tatiana Shpeisman60bf7be2018-07-26 18:09:20 -07001432 if (getKind() == Kind::MLFunc)
1433 return (
1434 emitError(useInfo.loc, "use of undefined SSA value " + useInfo.name),
1435 nullptr);
1436
Chris Lattner6119d382018-07-20 18:41:34 -07001437 auto *result = createForwardReferencePlaceholder(useInfo.loc, type);
1438 entries[useInfo.number].first = result;
1439 entries[useInfo.number].second = useInfo.loc;
1440 return result;
Chris Lattner7f9cc272018-07-19 08:35:28 -07001441}
1442
1443/// Register a definition of a value with the symbol table.
1444ParseResult FunctionParser::addDefinition(SSAUseInfo useInfo, SSAValue *value) {
Chris Lattner6119d382018-07-20 18:41:34 -07001445 auto &entries = values[useInfo.name];
Chris Lattner7f9cc272018-07-19 08:35:28 -07001446
Chris Lattner6119d382018-07-20 18:41:34 -07001447 // Make sure there is a slot for this value.
1448 if (entries.size() <= useInfo.number)
1449 entries.resize(useInfo.number + 1);
Chris Lattner7f9cc272018-07-19 08:35:28 -07001450
Chris Lattner6119d382018-07-20 18:41:34 -07001451 // If we already have an entry for this, check to see if it was a definition
1452 // or a forward reference.
1453 if (auto *existing = entries[useInfo.number].first) {
1454 if (!isForwardReferencePlaceholder(existing)) {
1455 emitError(useInfo.loc,
1456 "redefinition of SSA value '" + useInfo.name + "'");
1457 return emitError(entries[useInfo.number].second,
1458 "previously defined here");
1459 }
1460
1461 // If it was a forward reference, update everything that used it to use the
1462 // actual definition instead, delete the forward ref, and remove it from our
1463 // set of forward references we track.
1464 existing->replaceAllUsesWith(value);
1465 existing->getDefiningInst()->destroy();
1466 forwardReferencePlaceholders.erase(existing);
1467 }
1468
1469 entries[useInfo.number].first = value;
1470 entries[useInfo.number].second = useInfo.loc;
1471 return ParseSuccess;
1472}
1473
1474/// After the function is finished parsing, this function checks to see if
1475/// there are any remaining issues.
Chris Lattner40746442018-07-21 14:32:09 -07001476ParseResult FunctionParser::finalizeFunction(Function *func, SMLoc loc) {
Chris Lattner6119d382018-07-20 18:41:34 -07001477 // Check for any forward references that are left. If we find any, error out.
1478 if (!forwardReferencePlaceholders.empty()) {
1479 SmallVector<std::pair<const char *, SSAValue *>, 4> errors;
1480 // Iteration over the map isn't determinstic, so sort by source location.
1481 for (auto entry : forwardReferencePlaceholders)
1482 errors.push_back({entry.second.getPointer(), entry.first});
1483 llvm::array_pod_sort(errors.begin(), errors.end());
1484
1485 for (auto entry : errors)
1486 emitError(SMLoc::getFromPointer(entry.first),
1487 "use of undeclared SSA value name");
1488 return ParseFailure;
1489 }
1490
1491 return ParseSuccess;
Chris Lattner7f9cc272018-07-19 08:35:28 -07001492}
1493
Chris Lattner78276e32018-07-07 15:48:26 -07001494/// Parse a SSA operand for an instruction or statement.
1495///
James Molloy61a656c2018-07-22 15:45:24 -07001496/// ssa-use ::= ssa-id
Chris Lattner78276e32018-07-07 15:48:26 -07001497///
Chris Lattner7f9cc272018-07-19 08:35:28 -07001498ParseResult FunctionParser::parseSSAUse(SSAUseInfo &result) {
Chris Lattner6119d382018-07-20 18:41:34 -07001499 result.name = getTokenSpelling();
1500 result.number = 0;
1501 result.loc = getToken().getLoc();
Chris Lattnerf7702a62018-07-23 17:30:01 -07001502 if (parseToken(Token::percent_identifier, "expected SSA operand"))
1503 return ParseFailure;
Chris Lattner6119d382018-07-20 18:41:34 -07001504
1505 // If we have an affine map ID, it is a result number.
1506 if (getToken().is(Token::hash_identifier)) {
1507 if (auto value = getToken().getHashIdentifierNumber())
1508 result.number = value.getValue();
1509 else
1510 return emitError("invalid SSA value result number");
1511 consumeToken(Token::hash_identifier);
1512 }
1513
Chris Lattner7f9cc272018-07-19 08:35:28 -07001514 return ParseSuccess;
Chris Lattner78276e32018-07-07 15:48:26 -07001515}
1516
1517/// Parse a (possibly empty) list of SSA operands.
1518///
1519/// ssa-use-list ::= ssa-use (`,` ssa-use)*
1520/// ssa-use-list-opt ::= ssa-use-list?
1521///
Chris Lattner7f9cc272018-07-19 08:35:28 -07001522ParseResult
Chris Lattner40746442018-07-21 14:32:09 -07001523FunctionParser::parseOptionalSSAUseList(SmallVectorImpl<SSAUseInfo> &results) {
Chris Lattner85ee1512018-07-25 11:15:20 -07001524 if (getToken().isNot(Token::percent_identifier))
Chris Lattner40746442018-07-21 14:32:09 -07001525 return ParseSuccess;
1526 return parseCommaSeparatedList([&]() -> ParseResult {
Chris Lattner7f9cc272018-07-19 08:35:28 -07001527 SSAUseInfo result;
1528 if (parseSSAUse(result))
1529 return ParseFailure;
1530 results.push_back(result);
1531 return ParseSuccess;
1532 });
Chris Lattner78276e32018-07-07 15:48:26 -07001533}
1534
1535/// Parse an SSA use with an associated type.
1536///
1537/// ssa-use-and-type ::= ssa-use `:` type
James Molloy61a656c2018-07-22 15:45:24 -07001538template <typename ResultType>
1539ResultType FunctionParser::parseSSADefOrUseAndType(
1540 const std::function<ResultType(SSAUseInfo, Type *)> &action) {
Chris Lattner78276e32018-07-07 15:48:26 -07001541
Chris Lattnerf7702a62018-07-23 17:30:01 -07001542 SSAUseInfo useInfo;
1543 if (parseSSAUse(useInfo) ||
1544 parseToken(Token::colon, "expected ':' and type for SSA operand"))
1545 return nullptr;
Chris Lattner78276e32018-07-07 15:48:26 -07001546
Chris Lattner7f9cc272018-07-19 08:35:28 -07001547 auto *type = parseType();
1548 if (!type)
1549 return nullptr;
Chris Lattner78276e32018-07-07 15:48:26 -07001550
James Molloy61a656c2018-07-22 15:45:24 -07001551 return action(useInfo, type);
Chris Lattner78276e32018-07-07 15:48:26 -07001552}
1553
Chris Lattner2c402672018-07-23 11:56:17 -07001554/// Parse a (possibly empty) list of SSA operands, followed by a colon, then
1555/// followed by a type list. If hasParens is true, then the operands are
1556/// surrounded by parens.
Chris Lattner78276e32018-07-07 15:48:26 -07001557///
Chris Lattner2c402672018-07-23 11:56:17 -07001558/// ssa-use-and-type-list[parens]
1559/// ::= `(` ssa-use-list `)` ':' type-list-no-parens
1560///
1561/// ssa-use-and-type-list[!parens]
1562/// ::= ssa-use-list ':' type-list-no-parens
Chris Lattner78276e32018-07-07 15:48:26 -07001563///
Chris Lattner40746442018-07-21 14:32:09 -07001564template <typename ValueTy>
Chris Lattner7f9cc272018-07-19 08:35:28 -07001565ParseResult FunctionParser::parseOptionalSSAUseAndTypeList(
Chris Lattner2c402672018-07-23 11:56:17 -07001566 SmallVectorImpl<ValueTy *> &results, bool isParenthesized) {
1567
1568 // If we are in the parenthesized form and no paren exists, then we succeed
1569 // with an empty list.
1570 if (isParenthesized && !consumeIf(Token::l_paren))
Chris Lattner40746442018-07-21 14:32:09 -07001571 return ParseSuccess;
1572
Chris Lattner2c402672018-07-23 11:56:17 -07001573 SmallVector<SSAUseInfo, 4> valueIDs;
1574 if (parseOptionalSSAUseList(valueIDs))
Chris Lattner7f9cc272018-07-19 08:35:28 -07001575 return ParseFailure;
Chris Lattner2c402672018-07-23 11:56:17 -07001576
1577 if (isParenthesized && !consumeIf(Token::r_paren))
1578 return emitError("expected ')' in operand list");
1579
1580 // If there were no operands, then there is no colon or type lists.
1581 if (valueIDs.empty())
1582 return ParseSuccess;
1583
Chris Lattner2c402672018-07-23 11:56:17 -07001584 SmallVector<Type *, 4> types;
Chris Lattnerf7702a62018-07-23 17:30:01 -07001585 if (parseToken(Token::colon, "expected ':' in operand list") ||
1586 parseTypeListNoParens(types))
Chris Lattner2c402672018-07-23 11:56:17 -07001587 return ParseFailure;
1588
1589 if (valueIDs.size() != types.size())
1590 return emitError("expected " + Twine(valueIDs.size()) +
1591 " types to match operand list");
1592
1593 results.reserve(valueIDs.size());
1594 for (unsigned i = 0, e = valueIDs.size(); i != e; ++i) {
1595 if (auto *value = resolveSSAUse(valueIDs[i], types[i]))
1596 results.push_back(cast<ValueTy>(value));
1597 else
1598 return ParseFailure;
1599 }
1600
1601 return ParseSuccess;
Chris Lattner78276e32018-07-07 15:48:26 -07001602}
1603
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07001604/// Parse the CFG or MLFunc operation.
1605///
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07001606/// operation ::=
1607/// (ssa-id `=`)? string '(' ssa-use-list? ')' attribute-dict?
1608/// `:` function-type
1609///
1610ParseResult
Chris Lattner7f9cc272018-07-19 08:35:28 -07001611FunctionParser::parseOperation(const CreateOperationFunction &createOpFunc) {
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07001612 auto loc = getToken().getLoc();
1613
1614 StringRef resultID;
1615 if (getToken().is(Token::percent_identifier)) {
Chris Lattner7f9cc272018-07-19 08:35:28 -07001616 resultID = getTokenSpelling();
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07001617 consumeToken(Token::percent_identifier);
Chris Lattnerf7702a62018-07-23 17:30:01 -07001618 if (parseToken(Token::equal, "expected '=' after SSA name"))
1619 return ParseFailure;
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07001620 }
1621
Chris Lattner85ee1512018-07-25 11:15:20 -07001622 Operation *op;
1623 if (getToken().is(Token::bare_identifier) || getToken().isKeyword())
1624 op = parseCustomOperation(createOpFunc);
1625 else if (getToken().is(Token::string))
1626 op = parseVerboseOperation(createOpFunc);
1627 else
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07001628 return emitError("expected operation name in quotes");
1629
Chris Lattner85ee1512018-07-25 11:15:20 -07001630 // If parsing of the basic operation failed, then this whole thing fails.
Chris Lattner7f9cc272018-07-19 08:35:28 -07001631 if (!op)
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07001632 return ParseFailure;
1633
1634 // We just parsed an operation. If it is a recognized one, verify that it
1635 // is structurally as we expect. If not, produce an error with a reasonable
1636 // source location.
Chris Lattner95865062018-08-01 10:18:59 -07001637 if (auto *opInfo = op->getAbstractOperation()) {
Chris Lattner7f9cc272018-07-19 08:35:28 -07001638 if (auto error = opInfo->verifyInvariants(op))
Chris Lattner9361fb32018-07-24 08:34:58 -07001639 return emitError(loc, Twine("'") + op->getName().str() + "' op " + error);
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07001640 }
1641
Chris Lattner7f9cc272018-07-19 08:35:28 -07001642 // If the instruction had a name, register it.
1643 if (!resultID.empty()) {
Tatiana Shpeisman60bf7be2018-07-26 18:09:20 -07001644 if (op->getNumResults() == 0)
1645 return emitError(loc, "cannot name an operation with no results");
Chris Lattner7f9cc272018-07-19 08:35:28 -07001646
Tatiana Shpeisman60bf7be2018-07-26 18:09:20 -07001647 for (unsigned i = 0, e = op->getNumResults(); i != e; ++i)
Chris Lattner2b97d502018-08-06 14:19:46 -07001648 if (addDefinition({resultID, i, loc}, op->getResult(i)))
1649 return ParseFailure;
Chris Lattner7f9cc272018-07-19 08:35:28 -07001650 }
1651
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07001652 return ParseSuccess;
1653}
Chris Lattnere79379a2018-06-22 10:39:19 -07001654
Chris Lattner85ee1512018-07-25 11:15:20 -07001655Operation *FunctionParser::parseVerboseOperation(
1656 const CreateOperationFunction &createOpFunc) {
Chris Lattner1628fa02018-08-23 14:32:25 -07001657
1658 // Get location information for the operation.
1659 auto *srcLocation = getEncodedSourceLocation(getToken().getLoc());
1660
Chris Lattner85ee1512018-07-25 11:15:20 -07001661 auto name = getToken().getStringValue();
1662 if (name.empty())
1663 return (emitError("empty operation name is invalid"), nullptr);
1664
1665 consumeToken(Token::string);
1666
Chris Lattner1628fa02018-08-23 14:32:25 -07001667 OperationState result(builder.getContext(), srcLocation, name);
Chris Lattner992a1272018-08-07 12:02:37 -07001668
Chris Lattner85ee1512018-07-25 11:15:20 -07001669 // Parse the operand list.
1670 SmallVector<SSAUseInfo, 8> operandInfos;
1671
1672 if (parseToken(Token::l_paren, "expected '(' to start operand list") ||
1673 parseOptionalSSAUseList(operandInfos) ||
1674 parseToken(Token::r_paren, "expected ')' to end operand list")) {
1675 return nullptr;
1676 }
1677
Chris Lattner85ee1512018-07-25 11:15:20 -07001678 if (getToken().is(Token::l_brace)) {
Chris Lattner992a1272018-08-07 12:02:37 -07001679 if (parseAttributeDict(result.attributes))
Chris Lattner85ee1512018-07-25 11:15:20 -07001680 return nullptr;
1681 }
1682
1683 if (parseToken(Token::colon, "expected ':' followed by instruction type"))
1684 return nullptr;
1685
1686 auto typeLoc = getToken().getLoc();
1687 auto type = parseType();
1688 if (!type)
1689 return nullptr;
1690 auto fnType = dyn_cast<FunctionType>(type);
1691 if (!fnType)
1692 return (emitError(typeLoc, "expected function type"), nullptr);
1693
Chris Lattner1eb77482018-08-22 19:25:49 -07001694 result.addTypes(fnType->getResults());
Chris Lattner992a1272018-08-07 12:02:37 -07001695
Chris Lattner85ee1512018-07-25 11:15:20 -07001696 // Check that we have the right number of types for the operands.
1697 auto operandTypes = fnType->getInputs();
1698 if (operandTypes.size() != operandInfos.size()) {
1699 auto plural = "s"[operandInfos.size() == 1];
1700 return (emitError(typeLoc, "expected " + llvm::utostr(operandInfos.size()) +
1701 " operand type" + plural + " but had " +
1702 llvm::utostr(operandTypes.size())),
1703 nullptr);
1704 }
1705
1706 // Resolve all of the operands.
Chris Lattner85ee1512018-07-25 11:15:20 -07001707 for (unsigned i = 0, e = operandInfos.size(); i != e; ++i) {
Chris Lattner992a1272018-08-07 12:02:37 -07001708 result.operands.push_back(resolveSSAUse(operandInfos[i], operandTypes[i]));
1709 if (!result.operands.back())
Chris Lattner85ee1512018-07-25 11:15:20 -07001710 return nullptr;
1711 }
1712
Chris Lattner992a1272018-08-07 12:02:37 -07001713 return createOpFunc(result);
Chris Lattner85ee1512018-07-25 11:15:20 -07001714}
1715
1716namespace {
1717class CustomOpAsmParser : public OpAsmParser {
1718public:
1719 CustomOpAsmParser(SMLoc nameLoc, StringRef opName, FunctionParser &parser)
1720 : nameLoc(nameLoc), opName(opName), parser(parser) {}
1721
Chris Lattner85ee1512018-07-25 11:15:20 -07001722 //===--------------------------------------------------------------------===//
1723 // High level parsing methods.
1724 //===--------------------------------------------------------------------===//
1725
Chris Lattner1aa46322018-08-21 17:55:22 -07001726 bool getCurrentLocation(llvm::SMLoc *loc) override {
1727 *loc = parser.getToken().getLoc();
1728 return false;
1729 }
Chris Lattner091a6b52018-08-23 14:58:27 -07001730 bool parseComma() override {
Chris Lattner85ee1512018-07-25 11:15:20 -07001731 return parser.parseToken(Token::comma, "expected ','");
1732 }
1733
Chris Lattner091a6b52018-08-23 14:58:27 -07001734 bool parseColonType(Type *&result) override {
1735 return parser.parseToken(Token::colon, "expected ':'") ||
1736 !(result = parser.parseType());
Chris Lattner85ee1512018-07-25 11:15:20 -07001737 }
1738
Chris Lattner091a6b52018-08-23 14:58:27 -07001739 bool parseColonTypeList(SmallVectorImpl<Type *> &result) override {
1740 if (parser.parseToken(Token::colon, "expected ':'"))
Chris Lattner85ee1512018-07-25 11:15:20 -07001741 return true;
1742
1743 do {
1744 if (auto *type = parser.parseType())
1745 result.push_back(type);
1746 else
1747 return true;
1748
1749 } while (parser.consumeIf(Token::comma));
1750 return false;
1751 }
1752
Chris Lattner85cf26d2018-08-02 16:54:36 -07001753 /// Parse an arbitrary attribute and return it in result. This also adds the
1754 /// attribute to the specified attribute list with the specified name. this
1755 /// captures the location of the attribute in 'loc' if it is non-null.
1756 bool parseAttribute(Attribute *&result, const char *attrName,
Chris Lattner091a6b52018-08-23 14:58:27 -07001757 SmallVectorImpl<NamedAttribute> &attrs) override {
Chris Lattner85ee1512018-07-25 11:15:20 -07001758 result = parser.parseAttribute();
Chris Lattner85cf26d2018-08-02 16:54:36 -07001759 if (!result)
1760 return true;
1761
1762 attrs.push_back(
1763 NamedAttribute(parser.builder.getIdentifier(attrName), result));
1764 return false;
1765 }
1766
1767 /// If a named attribute list is present, parse is into result.
Chris Lattner091a6b52018-08-23 14:58:27 -07001768 bool
1769 parseOptionalAttributeDict(SmallVectorImpl<NamedAttribute> &result) override {
Chris Lattner85cf26d2018-08-02 16:54:36 -07001770 if (parser.getToken().isNot(Token::l_brace))
1771 return false;
Chris Lattner85cf26d2018-08-02 16:54:36 -07001772 return parser.parseAttributeDict(result) == ParseFailure;
Chris Lattner85ee1512018-07-25 11:15:20 -07001773 }
1774
Chris Lattner1aa46322018-08-21 17:55:22 -07001775 /// Parse a function name like '@foo' and return the name in a form that can
1776 /// be passed to resolveFunctionName when a function type is available.
1777 virtual bool parseFunctionName(StringRef &result, llvm::SMLoc &loc) {
1778 loc = parser.getToken().getLoc();
1779
1780 if (parser.getToken().isNot(Token::at_identifier))
1781 return emitError(loc, "expected function name");
1782
1783 result = parser.getTokenSpelling();
1784 parser.consumeToken(Token::at_identifier);
1785 return false;
1786 }
1787
Chris Lattner85ee1512018-07-25 11:15:20 -07001788 bool parseOperand(OperandType &result) override {
1789 FunctionParser::SSAUseInfo useInfo;
1790 if (parser.parseSSAUse(useInfo))
1791 return true;
1792
1793 result = {useInfo.loc, useInfo.name, useInfo.number};
1794 return false;
1795 }
1796
1797 bool parseOperandList(SmallVectorImpl<OperandType> &result,
1798 int requiredOperandCount = -1,
Chris Lattner85cf26d2018-08-02 16:54:36 -07001799 Delimiter delimiter = Delimiter::None) override {
Chris Lattner85ee1512018-07-25 11:15:20 -07001800 auto startLoc = parser.getToken().getLoc();
1801
Chris Lattner85cf26d2018-08-02 16:54:36 -07001802 // Handle delimiters.
1803 switch (delimiter) {
1804 case Delimiter::None:
Chris Lattner85ee1512018-07-25 11:15:20 -07001805 break;
Chris Lattner85cf26d2018-08-02 16:54:36 -07001806 case Delimiter::OptionalParen:
Chris Lattner3164ae62018-07-28 09:36:25 -07001807 if (parser.getToken().isNot(Token::l_paren))
1808 return false;
1809 LLVM_FALLTHROUGH;
Chris Lattner85cf26d2018-08-02 16:54:36 -07001810 case Delimiter::Paren:
Chris Lattner85ee1512018-07-25 11:15:20 -07001811 if (parser.parseToken(Token::l_paren, "expected '(' in operand list"))
1812 return true;
1813 break;
Chris Lattner85cf26d2018-08-02 16:54:36 -07001814 case Delimiter::OptionalSquare:
Chris Lattner3164ae62018-07-28 09:36:25 -07001815 if (parser.getToken().isNot(Token::l_square))
1816 return false;
1817 LLVM_FALLTHROUGH;
Chris Lattner85cf26d2018-08-02 16:54:36 -07001818 case Delimiter::Square:
Chris Lattner85ee1512018-07-25 11:15:20 -07001819 if (parser.parseToken(Token::l_square, "expected '[' in operand list"))
1820 return true;
1821 break;
1822 }
1823
1824 // Check for zero operands.
1825 if (parser.getToken().is(Token::percent_identifier)) {
1826 do {
1827 OperandType operand;
1828 if (parseOperand(operand))
1829 return true;
1830 result.push_back(operand);
1831 } while (parser.consumeIf(Token::comma));
1832 }
1833
Chris Lattner85cf26d2018-08-02 16:54:36 -07001834 // Handle delimiters. If we reach here, the optional delimiters were
Chris Lattner3164ae62018-07-28 09:36:25 -07001835 // present, so we need to parse their closing one.
Chris Lattner85cf26d2018-08-02 16:54:36 -07001836 switch (delimiter) {
1837 case Delimiter::None:
Chris Lattner85ee1512018-07-25 11:15:20 -07001838 break;
Chris Lattner85cf26d2018-08-02 16:54:36 -07001839 case Delimiter::OptionalParen:
1840 case Delimiter::Paren:
Chris Lattner85ee1512018-07-25 11:15:20 -07001841 if (parser.parseToken(Token::r_paren, "expected ')' in operand list"))
1842 return true;
1843 break;
Chris Lattner85cf26d2018-08-02 16:54:36 -07001844 case Delimiter::OptionalSquare:
1845 case Delimiter::Square:
Chris Lattner85ee1512018-07-25 11:15:20 -07001846 if (parser.parseToken(Token::r_square, "expected ']' in operand list"))
1847 return true;
1848 break;
1849 }
1850
1851 if (requiredOperandCount != -1 && result.size() != requiredOperandCount)
1852 emitError(startLoc,
1853 "expected " + Twine(requiredOperandCount) + " operands");
1854 return false;
1855 }
1856
Chris Lattner1aa46322018-08-21 17:55:22 -07001857 /// Resolve a parse function name and a type into a function reference.
1858 virtual bool resolveFunctionName(StringRef name, FunctionType *type,
1859 llvm::SMLoc loc, Function *&result) {
1860 result = parser.resolveFunctionReference(name, loc, type);
1861 return result == nullptr;
1862 }
1863
Chris Lattner85ee1512018-07-25 11:15:20 -07001864 //===--------------------------------------------------------------------===//
1865 // Methods for interacting with the parser
1866 //===--------------------------------------------------------------------===//
1867
1868 Builder &getBuilder() const override { return parser.builder; }
1869
1870 llvm::SMLoc getNameLoc() const override { return nameLoc; }
1871
Chris Lattner1aa46322018-08-21 17:55:22 -07001872 bool resolveOperand(const OperandType &operand, Type *type,
Chris Lattner8bdbebf2018-08-08 11:02:58 -07001873 SmallVectorImpl<SSAValue *> &result) override {
Chris Lattner85ee1512018-07-25 11:15:20 -07001874 FunctionParser::SSAUseInfo operandInfo = {operand.name, operand.number,
1875 operand.location};
Chris Lattner8bdbebf2018-08-08 11:02:58 -07001876 if (auto *value = parser.resolveSSAUse(operandInfo, type)) {
1877 result.push_back(value);
1878 return false;
1879 }
1880 return true;
Chris Lattner85ee1512018-07-25 11:15:20 -07001881 }
1882
Chris Lattnereed6c4d2018-08-07 09:12:35 -07001883 /// Emit a diagnostic at the specified location and return true.
1884 bool emitError(llvm::SMLoc loc, const Twine &message) override {
Chris Lattner85ee1512018-07-25 11:15:20 -07001885 parser.emitError(loc, "custom op '" + Twine(opName) + "' " + message);
1886 emittedError = true;
Chris Lattnereed6c4d2018-08-07 09:12:35 -07001887 return true;
Chris Lattner85ee1512018-07-25 11:15:20 -07001888 }
1889
1890 bool didEmitError() const { return emittedError; }
1891
1892private:
1893 SMLoc nameLoc;
1894 StringRef opName;
1895 FunctionParser &parser;
1896 bool emittedError = false;
1897};
1898} // end anonymous namespace.
1899
1900Operation *FunctionParser::parseCustomOperation(
1901 const CreateOperationFunction &createOpFunc) {
1902 auto opLoc = getToken().getLoc();
1903 auto opName = getTokenSpelling();
1904 CustomOpAsmParser opAsmParser(opLoc, opName, *this);
1905
1906 auto *opDefinition = getOperationSet().lookup(opName);
1907 if (!opDefinition) {
1908 opAsmParser.emitError(opLoc, "is unknown");
1909 return nullptr;
1910 }
1911
1912 consumeToken();
1913
Chris Lattner1aa46322018-08-21 17:55:22 -07001914 // If the custom op parser crashes, produce some indication to help debugging.
1915 std::string opNameStr = opName.str();
1916 llvm::PrettyStackTraceFormat fmt("MLIR Parser: custom op parser '%s'",
1917 opNameStr.c_str());
1918
Chris Lattner1628fa02018-08-23 14:32:25 -07001919 // Get location information for the operation.
1920 auto *srcLocation = getEncodedSourceLocation(opLoc);
1921
Chris Lattner85ee1512018-07-25 11:15:20 -07001922 // Have the op implementation take a crack and parsing this.
Chris Lattner1628fa02018-08-23 14:32:25 -07001923 OperationState opState(builder.getContext(), srcLocation, opName);
Chris Lattnereed6c4d2018-08-07 09:12:35 -07001924 if (opDefinition->parseAssembly(&opAsmParser, &opState))
1925 return nullptr;
Chris Lattner85ee1512018-07-25 11:15:20 -07001926
1927 // If it emitted an error, we failed.
1928 if (opAsmParser.didEmitError())
1929 return nullptr;
1930
1931 // Otherwise, we succeeded. Use the state it parsed as our op information.
Chris Lattner992a1272018-08-07 12:02:37 -07001932 return createOpFunc(opState);
Chris Lattner85ee1512018-07-25 11:15:20 -07001933}
1934
Chris Lattner48af7d12018-07-09 19:05:38 -07001935//===----------------------------------------------------------------------===//
1936// CFG Functions
1937//===----------------------------------------------------------------------===//
Chris Lattnere79379a2018-06-22 10:39:19 -07001938
Chris Lattner4c95a502018-06-23 16:03:42 -07001939namespace {
Chris Lattner48af7d12018-07-09 19:05:38 -07001940/// This is a specialized parser for CFGFunction's, maintaining the state
1941/// transient to their bodies.
Chris Lattner7f9cc272018-07-19 08:35:28 -07001942class CFGFunctionParser : public FunctionParser {
Chris Lattner158e0a3e2018-07-08 20:51:38 -07001943public:
Chris Lattner2e595eb2018-07-10 10:08:27 -07001944 CFGFunctionParser(ParserState &state, CFGFunction *function)
Tatiana Shpeisman60bf7be2018-07-26 18:09:20 -07001945 : FunctionParser(state, Kind::CFGFunc), function(function),
1946 builder(function) {}
Chris Lattner2e595eb2018-07-10 10:08:27 -07001947
1948 ParseResult parseFunctionBody();
1949
1950private:
Chris Lattnerf6d80a02018-06-24 11:18:29 -07001951 CFGFunction *function;
James Molloy0ff71542018-07-23 16:56:32 -07001952 llvm::StringMap<std::pair<BasicBlock *, SMLoc>> blocksByName;
Chris Lattner48af7d12018-07-09 19:05:38 -07001953
1954 /// This builder intentionally shadows the builder in the base class, with a
1955 /// more specific builder type.
Chris Lattner158e0a3e2018-07-08 20:51:38 -07001956 CFGFuncBuilder builder;
Chris Lattnerf6d80a02018-06-24 11:18:29 -07001957
Chris Lattner4c95a502018-06-23 16:03:42 -07001958 /// Get the basic block with the specified name, creating it if it doesn't
Chris Lattnerf6d80a02018-06-24 11:18:29 -07001959 /// already exist. The location specified is the point of use, which allows
1960 /// us to diagnose references to blocks that are not defined precisely.
1961 BasicBlock *getBlockNamed(StringRef name, SMLoc loc) {
1962 auto &blockAndLoc = blocksByName[name];
1963 if (!blockAndLoc.first) {
Chris Lattner3a467cc2018-07-01 20:28:00 -07001964 blockAndLoc.first = new BasicBlock();
Chris Lattnerf6d80a02018-06-24 11:18:29 -07001965 blockAndLoc.second = loc;
Chris Lattner4c95a502018-06-23 16:03:42 -07001966 }
Chris Lattnerf6d80a02018-06-24 11:18:29 -07001967 return blockAndLoc.first;
Chris Lattner4c95a502018-06-23 16:03:42 -07001968 }
Chris Lattner48af7d12018-07-09 19:05:38 -07001969
James Molloy61a656c2018-07-22 15:45:24 -07001970 ParseResult
1971 parseOptionalBasicBlockArgList(SmallVectorImpl<BBArgument *> &results,
1972 BasicBlock *owner);
James Molloy4f788372018-07-24 15:01:27 -07001973 ParseResult parseBranchBlockAndUseList(BasicBlock *&block,
1974 SmallVectorImpl<CFGValue *> &values);
James Molloy61a656c2018-07-22 15:45:24 -07001975
Chris Lattner48af7d12018-07-09 19:05:38 -07001976 ParseResult parseBasicBlock();
Chris Lattner48af7d12018-07-09 19:05:38 -07001977 TerminatorInst *parseTerminator();
Chris Lattner4c95a502018-06-23 16:03:42 -07001978};
1979} // end anonymous namespace
1980
James Molloy61a656c2018-07-22 15:45:24 -07001981/// Parse a (possibly empty) list of SSA operands with types as basic block
Chris Lattner2c402672018-07-23 11:56:17 -07001982/// arguments.
James Molloy61a656c2018-07-22 15:45:24 -07001983///
1984/// ssa-id-and-type-list ::= ssa-id-and-type (`,` ssa-id-and-type)*
1985///
1986ParseResult CFGFunctionParser::parseOptionalBasicBlockArgList(
1987 SmallVectorImpl<BBArgument *> &results, BasicBlock *owner) {
1988 if (getToken().is(Token::r_brace))
1989 return ParseSuccess;
1990
1991 return parseCommaSeparatedList([&]() -> ParseResult {
1992 auto type = parseSSADefOrUseAndType<Type *>(
1993 [&](SSAUseInfo useInfo, Type *type) -> Type * {
1994 BBArgument *arg = owner->addArgument(type);
Chris Lattner2b97d502018-08-06 14:19:46 -07001995 if (addDefinition(useInfo, arg))
James Molloy61a656c2018-07-22 15:45:24 -07001996 return nullptr;
1997 return type;
1998 });
1999 return type ? ParseSuccess : ParseFailure;
2000 });
2001}
2002
Chris Lattner48af7d12018-07-09 19:05:38 -07002003ParseResult CFGFunctionParser::parseFunctionBody() {
Chris Lattner40746442018-07-21 14:32:09 -07002004 auto braceLoc = getToken().getLoc();
Chris Lattnerf7702a62018-07-23 17:30:01 -07002005 if (parseToken(Token::l_brace, "expected '{' in CFG function"))
2006 return ParseFailure;
Chris Lattner48af7d12018-07-09 19:05:38 -07002007
2008 // Make sure we have at least one block.
2009 if (getToken().is(Token::r_brace))
2010 return emitError("CFG functions must have at least one basic block");
Chris Lattner4c95a502018-06-23 16:03:42 -07002011
2012 // Parse the list of blocks.
2013 while (!consumeIf(Token::r_brace))
Chris Lattner48af7d12018-07-09 19:05:38 -07002014 if (parseBasicBlock())
Chris Lattner4c95a502018-06-23 16:03:42 -07002015 return ParseFailure;
2016
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002017 // Verify that all referenced blocks were defined. Iteration over a
2018 // StringMap isn't determinstic, but this is good enough for our purposes.
Chris Lattner48af7d12018-07-09 19:05:38 -07002019 for (auto &elt : blocksByName) {
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002020 auto *bb = elt.second.first;
Chris Lattner3a467cc2018-07-01 20:28:00 -07002021 if (!bb->getFunction())
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002022 return emitError(elt.second.second,
James Molloy0ff71542018-07-23 16:56:32 -07002023 "reference to an undefined basic block '" + elt.first() +
2024 "'");
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002025 }
2026
Chris Lattner40746442018-07-21 14:32:09 -07002027 return finalizeFunction(function, braceLoc);
Chris Lattner4c95a502018-06-23 16:03:42 -07002028}
2029
2030/// Basic block declaration.
2031///
2032/// basic-block ::= bb-label instruction* terminator-stmt
2033/// bb-label ::= bb-id bb-arg-list? `:`
2034/// bb-id ::= bare-id
2035/// bb-arg-list ::= `(` ssa-id-and-type-list? `)`
2036///
Chris Lattner48af7d12018-07-09 19:05:38 -07002037ParseResult CFGFunctionParser::parseBasicBlock() {
2038 SMLoc nameLoc = getToken().getLoc();
2039 auto name = getTokenSpelling();
Chris Lattnerf7702a62018-07-23 17:30:01 -07002040 if (parseToken(Token::bare_identifier, "expected basic block name"))
2041 return ParseFailure;
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002042
Chris Lattner48af7d12018-07-09 19:05:38 -07002043 auto *block = getBlockNamed(name, nameLoc);
Chris Lattner4c95a502018-06-23 16:03:42 -07002044
2045 // If this block has already been parsed, then this is a redefinition with the
2046 // same block name.
Chris Lattner3a467cc2018-07-01 20:28:00 -07002047 if (block->getFunction())
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002048 return emitError(nameLoc, "redefinition of block '" + name.str() + "'");
2049
Chris Lattner78276e32018-07-07 15:48:26 -07002050 // If an argument list is present, parse it.
2051 if (consumeIf(Token::l_paren)) {
James Molloy61a656c2018-07-22 15:45:24 -07002052 SmallVector<BBArgument *, 8> bbArgs;
Chris Lattnerf7702a62018-07-23 17:30:01 -07002053 if (parseOptionalBasicBlockArgList(bbArgs, block) ||
2054 parseToken(Token::r_paren, "expected ')' to end argument list"))
Chris Lattner78276e32018-07-07 15:48:26 -07002055 return ParseFailure;
Chris Lattner78276e32018-07-07 15:48:26 -07002056 }
Chris Lattner4c95a502018-06-23 16:03:42 -07002057
James Molloy61a656c2018-07-22 15:45:24 -07002058 // Add the block to the function.
2059 function->push_back(block);
2060
Chris Lattnerf7702a62018-07-23 17:30:01 -07002061 if (parseToken(Token::colon, "expected ':' after basic block name"))
2062 return ParseFailure;
Chris Lattner4c95a502018-06-23 16:03:42 -07002063
Chris Lattner158e0a3e2018-07-08 20:51:38 -07002064 // Set the insertion point to the block we want to insert new operations into.
Chris Lattner48af7d12018-07-09 19:05:38 -07002065 builder.setInsertionPoint(block);
Chris Lattner158e0a3e2018-07-08 20:51:38 -07002066
Chris Lattner992a1272018-08-07 12:02:37 -07002067 auto createOpFunc = [&](const OperationState &result) -> Operation * {
2068 return builder.createOperation(result);
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002069 };
2070
Chris Lattnered65a732018-06-28 20:45:33 -07002071 // Parse the list of operations that make up the body of the block.
James Molloy4f788372018-07-24 15:01:27 -07002072 while (getToken().isNot(Token::kw_return, Token::kw_br, Token::kw_cond_br)) {
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002073 if (parseOperation(createOpFunc))
Chris Lattnered65a732018-06-28 20:45:33 -07002074 return ParseFailure;
2075 }
Chris Lattner4c95a502018-06-23 16:03:42 -07002076
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002077 if (!parseTerminator())
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002078 return ParseFailure;
Chris Lattner4c95a502018-06-23 16:03:42 -07002079
2080 return ParseSuccess;
2081}
2082
James Molloy4f788372018-07-24 15:01:27 -07002083ParseResult CFGFunctionParser::parseBranchBlockAndUseList(
2084 BasicBlock *&block, SmallVectorImpl<CFGValue *> &values) {
2085 block = getBlockNamed(getTokenSpelling(), getToken().getLoc());
2086 if (parseToken(Token::bare_identifier, "expected basic block name"))
2087 return ParseFailure;
2088
2089 if (!consumeIf(Token::l_paren))
2090 return ParseSuccess;
2091 if (parseOptionalSSAUseAndTypeList(values, /*isParenthesized*/ false) ||
2092 parseToken(Token::r_paren, "expected ')' to close argument list"))
2093 return ParseFailure;
2094 return ParseSuccess;
2095}
2096
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002097/// Parse the terminator instruction for a basic block.
2098///
2099/// terminator-stmt ::= `br` bb-id branch-use-list?
Chris Lattner1604e472018-07-23 08:42:19 -07002100/// branch-use-list ::= `(` ssa-use-list `)` ':' type-list-no-parens
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002101/// terminator-stmt ::=
2102/// `cond_br` ssa-use `,` bb-id branch-use-list? `,` bb-id branch-use-list?
2103/// terminator-stmt ::= `return` ssa-use-and-type-list?
2104///
Chris Lattner48af7d12018-07-09 19:05:38 -07002105TerminatorInst *CFGFunctionParser::parseTerminator() {
Chris Lattner1628fa02018-08-23 14:32:25 -07002106 auto loc = getToken().getLoc();
2107
Chris Lattner48af7d12018-07-09 19:05:38 -07002108 switch (getToken().getKind()) {
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002109 default:
Chris Lattner3a467cc2018-07-01 20:28:00 -07002110 return (emitError("expected terminator at end of basic block"), nullptr);
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002111
Chris Lattner40746442018-07-21 14:32:09 -07002112 case Token::kw_return: {
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002113 consumeToken(Token::kw_return);
Chris Lattner40746442018-07-21 14:32:09 -07002114
Chris Lattner2c402672018-07-23 11:56:17 -07002115 // Parse any operands.
2116 SmallVector<CFGValue *, 8> operands;
2117 if (parseOptionalSSAUseAndTypeList(operands, /*isParenthesized*/ false))
2118 return nullptr;
Chris Lattner091a6b52018-08-23 14:58:27 -07002119 return builder.createReturn(getEncodedSourceLocation(loc), operands);
Chris Lattner40746442018-07-21 14:32:09 -07002120 }
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002121
2122 case Token::kw_br: {
2123 consumeToken(Token::kw_br);
James Molloy4f788372018-07-24 15:01:27 -07002124 BasicBlock *destBB;
2125 SmallVector<CFGValue *, 4> values;
2126 if (parseBranchBlockAndUseList(destBB, values))
Chris Lattnerf7702a62018-07-23 17:30:01 -07002127 return nullptr;
Chris Lattner091a6b52018-08-23 14:58:27 -07002128 auto branch = builder.createBranch(getEncodedSourceLocation(loc), destBB);
James Molloy4f788372018-07-24 15:01:27 -07002129 branch->addOperands(values);
Chris Lattner1604e472018-07-23 08:42:19 -07002130 return branch;
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002131 }
James Molloy4f788372018-07-24 15:01:27 -07002132
2133 case Token::kw_cond_br: {
2134 consumeToken(Token::kw_cond_br);
2135 SSAUseInfo ssaUse;
2136 if (parseSSAUse(ssaUse))
2137 return nullptr;
2138 auto *cond = resolveSSAUse(ssaUse, builder.getIntegerType(1));
2139 if (!cond)
2140 return (emitError("expected type was boolean (i1)"), nullptr);
2141 if (parseToken(Token::comma, "expected ',' in conditional branch"))
2142 return nullptr;
2143
2144 BasicBlock *trueBlock;
2145 SmallVector<CFGValue *, 4> trueOperands;
2146 if (parseBranchBlockAndUseList(trueBlock, trueOperands))
2147 return nullptr;
2148
2149 if (parseToken(Token::comma, "expected ',' in conditional branch"))
2150 return nullptr;
2151
2152 BasicBlock *falseBlock;
2153 SmallVector<CFGValue *, 4> falseOperands;
2154 if (parseBranchBlockAndUseList(falseBlock, falseOperands))
2155 return nullptr;
2156
Chris Lattner091a6b52018-08-23 14:58:27 -07002157 auto branch =
2158 builder.createCondBranch(getEncodedSourceLocation(loc),
2159 cast<CFGValue>(cond), trueBlock, falseBlock);
James Molloy4f788372018-07-24 15:01:27 -07002160 branch->addTrueOperands(trueOperands);
2161 branch->addFalseOperands(falseOperands);
2162 return branch;
2163 }
Chris Lattnerf6d80a02018-06-24 11:18:29 -07002164 }
2165}
2166
Chris Lattner48af7d12018-07-09 19:05:38 -07002167//===----------------------------------------------------------------------===//
2168// ML Functions
2169//===----------------------------------------------------------------------===//
2170
2171namespace {
2172/// Refined parser for MLFunction bodies.
Chris Lattner7f9cc272018-07-19 08:35:28 -07002173class MLFunctionParser : public FunctionParser {
Chris Lattner48af7d12018-07-09 19:05:38 -07002174public:
Chris Lattner48af7d12018-07-09 19:05:38 -07002175 MLFunctionParser(ParserState &state, MLFunction *function)
Tatiana Shpeisman60bf7be2018-07-26 18:09:20 -07002176 : FunctionParser(state, Kind::MLFunc), function(function),
Chris Lattnere787b322018-08-08 11:14:57 -07002177 builder(function, function->end()) {}
Chris Lattner48af7d12018-07-09 19:05:38 -07002178
2179 ParseResult parseFunctionBody();
Tatiana Shpeisman1bcfe982018-07-13 13:03:13 -07002180
2181private:
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002182 MLFunction *function;
2183
2184 /// This builder intentionally shadows the builder in the base class, with a
2185 /// more specific builder type.
2186 MLFuncBuilder builder;
2187
2188 ParseResult parseForStmt();
Tatiana Shpeismande8829f2018-08-24 23:38:14 -07002189 ParseResult parseIntConstant(int64_t &val);
2190 ParseResult parseDimAndSymbolList(SmallVectorImpl<MLValue *> &operands,
2191 const AffineMap *map);
2192 ParseResult parseBound(SmallVectorImpl<MLValue *> &operands, AffineMap *&map,
2193 bool isLower);
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002194 ParseResult parseIfStmt();
Tatiana Shpeisman1bcfe982018-07-13 13:03:13 -07002195 ParseResult parseElseClause(IfClause *elseClause);
Uday Bondhugulabc535622018-08-07 14:24:38 -07002196 IntegerSet *parseCondition();
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002197 ParseResult parseStatements(StmtBlock *block);
Tatiana Shpeisman1bcfe982018-07-13 13:03:13 -07002198 ParseResult parseStmtBlock(StmtBlock *block);
Chris Lattner48af7d12018-07-09 19:05:38 -07002199};
2200} // end anonymous namespace
2201
Chris Lattner48af7d12018-07-09 19:05:38 -07002202ParseResult MLFunctionParser::parseFunctionBody() {
Chris Lattner40746442018-07-21 14:32:09 -07002203 auto braceLoc = getToken().getLoc();
Tatiana Shpeismanc96b5872018-06-28 17:02:32 -07002204
Tatiana Shpeismand9b1d862018-08-09 12:28:58 -07002205 // Parse statements in this function.
2206 if (parseStmtBlock(function))
Chris Lattnerf7702a62018-07-23 17:30:01 -07002207 return ParseFailure;
Chris Lattner40746442018-07-21 14:32:09 -07002208
Chris Lattner40746442018-07-21 14:32:09 -07002209 return finalizeFunction(function, braceLoc);
Tatiana Shpeismanc96b5872018-06-28 17:02:32 -07002210}
2211
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002212/// For statement.
2213///
Chris Lattner48af7d12018-07-09 19:05:38 -07002214/// ml-for-stmt ::= `for` ssa-id `=` lower-bound `to` upper-bound
2215/// (`step` integer-literal)? `{` ml-stmt* `}`
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002216///
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002217ParseResult MLFunctionParser::parseForStmt() {
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002218 consumeToken(Token::kw_for);
2219
Uday Bondhugula67701712018-08-21 16:01:23 -07002220 // Parse induction variable.
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002221 if (getToken().isNot(Token::percent_identifier))
2222 return emitError("expected SSA identifier for the loop variable");
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002223
Tatiana Shpeisman3838db72018-07-30 15:18:10 -07002224 auto loc = getToken().getLoc();
Tatiana Shpeismand880b352018-07-31 23:14:16 -07002225 StringRef inductionVariableName = getTokenSpelling();
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002226 consumeToken(Token::percent_identifier);
2227
Tatiana Shpeismand9b1d862018-08-09 12:28:58 -07002228 if (parseToken(Token::equal, "expected '='"))
Chris Lattnerf7702a62018-07-23 17:30:01 -07002229 return ParseFailure;
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002230
Tatiana Shpeismande8829f2018-08-24 23:38:14 -07002231 // Parse lower bound.
2232 SmallVector<MLValue *, 4> lbOperands;
2233 AffineMap *lbMap = nullptr;
2234 if (parseBound(lbOperands, lbMap, /*isLower*/ true))
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002235 return ParseFailure;
2236
Chris Lattnerf7702a62018-07-23 17:30:01 -07002237 if (parseToken(Token::kw_to, "expected 'to' between bounds"))
2238 return ParseFailure;
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002239
Tatiana Shpeismande8829f2018-08-24 23:38:14 -07002240 // Parse upper bound.
2241 SmallVector<MLValue *, 4> ubOperands;
2242 AffineMap *ubMap = nullptr;
2243 if (parseBound(ubOperands, ubMap, /*isLower*/ false))
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002244 return ParseFailure;
2245
Uday Bondhugula67701712018-08-21 16:01:23 -07002246 // Parse step.
2247 int64_t step = 1;
Tatiana Shpeismande8829f2018-08-24 23:38:14 -07002248 if (consumeIf(Token::kw_step) && parseIntConstant(step))
2249 return ParseFailure;
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002250
2251 // Create for statement.
Tatiana Shpeismande8829f2018-08-24 23:38:14 -07002252 ForStmt *forStmt =
2253 builder.createFor(getEncodedSourceLocation(loc), lbOperands, lbMap,
2254 ubOperands, ubMap, step);
Tatiana Shpeisman3838db72018-07-30 15:18:10 -07002255
2256 // Create SSA value definition for the induction variable.
Chris Lattner2b97d502018-08-06 14:19:46 -07002257 if (addDefinition({inductionVariableName, 0, loc}, forStmt))
2258 return ParseFailure;
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002259
2260 // If parsing of the for statement body fails,
2261 // MLIR contains for statement with those nested statements that have been
2262 // successfully parsed.
Tatiana Shpeisman3838db72018-07-30 15:18:10 -07002263 if (parseStmtBlock(forStmt))
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002264 return ParseFailure;
2265
Tatiana Shpeisman3838db72018-07-30 15:18:10 -07002266 // Reset insertion point to the current block.
Chris Lattnere787b322018-08-08 11:14:57 -07002267 builder.setInsertionPointToEnd(forStmt->getBlock());
Tatiana Shpeismande8829f2018-08-24 23:38:14 -07002268
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002269 return ParseSuccess;
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002270}
2271
Tatiana Shpeismande8829f2018-08-24 23:38:14 -07002272/// Parse integer constant as affine constant expression.
2273ParseResult MLFunctionParser::parseIntConstant(int64_t &val) {
2274 bool negate = consumeIf(Token::minus);
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002275
Tatiana Shpeismande8829f2018-08-24 23:38:14 -07002276 if (getToken().isNot(Token::integer))
2277 return emitError("expected integer");
2278
2279 auto uval = getToken().getUInt64IntegerValue();
2280
2281 if (!uval.hasValue() || (int64_t)uval.getValue() < 0) {
2282 return emitError("bound or step is too large for affineint");
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002283 }
Tatiana Shpeismande8829f2018-08-24 23:38:14 -07002284
2285 val = (int64_t)uval.getValue();
2286 if (negate)
2287 val = -val;
2288 consumeToken();
2289
2290 return ParseSuccess;
2291}
2292
2293/// Dimensions and symbol use list.
2294///
2295/// dim-use-list ::= `(` ssa-use-list? `)`
2296/// symbol-use-list ::= `[` ssa-use-list? `]`
2297/// dim-and-symbol-use-list ::= dim-use-list symbol-use-list?
2298///
2299ParseResult
2300MLFunctionParser::parseDimAndSymbolList(SmallVectorImpl<MLValue *> &operands,
2301 const AffineMap *map) {
2302 if (parseToken(Token::l_paren, "expected '('"))
2303 return ParseFailure;
2304
2305 SmallVector<SSAUseInfo, 4> opInfo;
2306 parseOptionalSSAUseList(opInfo);
2307
2308 if (parseToken(Token::r_paren, "expected ')'"))
2309 return ParseFailure;
2310
2311 if (map->getNumDims() != opInfo.size())
2312 return emitError("dim operand count and affine map dim count must match");
2313
2314 if (consumeIf(Token::l_square)) {
2315 parseOptionalSSAUseList(opInfo);
2316 if (parseToken(Token::r_square, "expected ']'"))
2317 return ParseFailure;
2318 }
2319
2320 if (map->getNumOperands() != opInfo.size())
2321 return emitError(
2322 "symbol operand count and affine map symbol count must match");
2323
2324 // Resolve SSA uses.
2325 Type *affineIntType = builder.getAffineIntType();
2326 unsigned numDims = map->getNumDims();
2327 for (unsigned i = 0, e = opInfo.size(); i != e; ++i) {
2328 SSAValue *sval = resolveSSAUse(opInfo[i], affineIntType);
2329 if (!sval)
2330 return ParseFailure;
2331
2332 auto *v = cast<MLValue>(sval);
2333 if (i < numDims && !v->isValidDim())
2334 return emitError(opInfo[i].loc, "value '" + opInfo[i].name.str() +
2335 "' cannot be used as dimension id");
2336 if (i >= numDims && !v->isValidSymbol())
2337 return emitError(opInfo[i].loc, "value '" + opInfo[i].name.str() +
2338 "' cannot be used as symbol");
2339 operands.push_back(v);
2340 }
2341
2342 return ParseSuccess;
2343}
2344
2345// Loop bound.
2346///
2347/// lower-bound ::= `max`? affine-map dim-and-symbol-use-list | shorthand-bound
2348/// upper-bound ::= `min`? affine-map dim-and-symbol-use-list | shorthand-bound
2349/// shorthand-bound ::= ssa-id | `-`? integer-literal
2350///
2351ParseResult MLFunctionParser::parseBound(SmallVectorImpl<MLValue *> &operands,
2352 AffineMap *&map, bool isLower) {
2353 // 'min' / 'max' prefixes are syntactic sugar. Ignore them.
2354 if (isLower)
2355 consumeIf(Token::kw_max);
2356 else
2357 consumeIf(Token::kw_min);
2358
2359 // Parse full form - affine map followed by dim and symbol list.
2360 if (getToken().isAny(Token::hash_identifier, Token::l_paren)) {
2361 map = parseAffineMapReference();
2362 if (!map)
2363 return ParseFailure;
2364
2365 if (parseDimAndSymbolList(operands, map))
2366 return ParseFailure;
2367 return ParseSuccess;
2368 }
2369
2370 // Parse shorthand form.
2371 if (getToken().isAny(Token::minus, Token::integer)) {
2372 int64_t val;
2373 if (!parseIntConstant(val)) {
2374 map = builder.getConstantMap(val);
2375 return ParseSuccess;
2376 }
2377 return ParseFailure;
2378 }
2379
2380 // Parse ssa-id as identity map.
2381 SSAUseInfo opInfo;
2382 if (parseSSAUse(opInfo))
2383 return ParseFailure;
2384
2385 // TODO: improve error message when SSA value is not an affine integer.
2386 // Currently it is 'use of value ... expects different type than prior uses'
2387 if (auto *value = resolveSSAUse(opInfo, builder.getAffineIntType()))
2388 operands.push_back(cast<MLValue>(value));
2389 else
2390 return ParseFailure;
2391
2392 // Create an identity map using dim id for an induction variable and
2393 // symbol otherwise. This representation is optimized for storage.
2394 // Analysis passes may expand it into a multi-dimensional map if desired.
2395 if (isa<ForStmt>(operands[0]))
2396 map = builder.getDimIdentityMap();
2397 else
2398 map = builder.getSymbolIdentityMap();
2399
2400 return ParseSuccess;
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002401}
2402
Uday Bondhugulabc535622018-08-07 14:24:38 -07002403/// Parse condition.
2404IntegerSet *MLFunctionParser::parseCondition() {
2405 return parseIntegerSetReference();
2406
2407 // TODO: Parse operands to the integer set.
2408}
2409
2410/// Parse an affine constraint.
2411/// affine-constraint ::= affine-expr `>=` `0`
2412/// | affine-expr `==` `0`
2413///
2414/// isEq is set to true if the parsed constraint is an equality, false if it is
2415/// an inequality (greater than or equal).
2416///
2417AffineExpr *AffineParser::parseAffineConstraint(bool *isEq) {
2418 AffineExpr *expr = parseAffineExpr();
2419 if (!expr)
2420 return nullptr;
2421
2422 if (consumeIf(Token::greater) && consumeIf(Token::equal) &&
2423 getToken().is(Token::integer)) {
2424 auto dim = getToken().getUnsignedIntegerValue();
2425 if (dim.hasValue() && dim.getValue() == 0) {
2426 consumeToken(Token::integer);
2427 *isEq = false;
2428 return expr;
2429 }
2430 return (emitError("expected '0' after '>='"), nullptr);
2431 }
2432
2433 if (consumeIf(Token::equal) && consumeIf(Token::equal) &&
2434 getToken().is(Token::integer)) {
2435 auto dim = getToken().getUnsignedIntegerValue();
2436 if (dim.hasValue() && dim.getValue() == 0) {
2437 consumeToken(Token::integer);
2438 *isEq = true;
2439 return expr;
2440 }
2441 return (emitError("expected '0' after '=='"), nullptr);
2442 }
2443
2444 return (emitError("expected '== 0' or '>= 0' at end of affine constraint"),
2445 nullptr);
2446}
2447
2448/// Parse an integer set definition.
2449/// integer-set-inline
2450/// ::= dim-and-symbol-id-lists `:` affine-constraint-conjunction
2451/// affine-constraint-conjunction ::= /*empty*/
2452/// | affine-constraint (`,` affine-constraint)*
2453///
2454IntegerSet *AffineParser::parseIntegerSetInline() {
2455 unsigned numDims = 0, numSymbols = 0;
2456
2457 // List of dimensional identifiers.
2458 if (parseDimIdList(numDims))
2459 return nullptr;
2460
2461 // Symbols are optional.
2462 if (getToken().is(Token::l_square)) {
2463 if (parseSymbolIdList(numSymbols))
2464 return nullptr;
2465 }
2466
2467 if (parseToken(Token::colon, "expected ':' or '['") ||
2468 parseToken(Token::l_paren,
2469 "expected '(' at start of integer set constraint list"))
2470 return nullptr;
2471
2472 SmallVector<AffineExpr *, 4> constraints;
2473 SmallVector<bool, 4> isEqs;
2474 auto parseElt = [&]() -> ParseResult {
2475 bool isEq;
2476 auto *elt = parseAffineConstraint(&isEq);
2477 ParseResult res = elt ? ParseSuccess : ParseFailure;
2478 if (elt) {
2479 constraints.push_back(elt);
2480 isEqs.push_back(isEq);
2481 }
2482 return res;
2483 };
2484
2485 // Parse a list of affine constraints (comma-separated) .
2486 // Grammar: affine-constraint-conjunct ::= `(` affine-constraint (`,`
2487 // affine-constraint)* `)
2488 if (parseCommaSeparatedListUntil(Token::r_paren, parseElt, true))
2489 return nullptr;
2490
2491 // Parsed a valid integer set.
2492 return builder.getIntegerSet(numDims, numSymbols, constraints, isEqs);
2493}
2494
2495IntegerSet *Parser::parseIntegerSetInline() {
2496 return AffineParser(state).parseIntegerSetInline();
2497}
2498
2499/// Parse a reference to an integer set.
2500/// integer-set ::= integer-set-id | integer-set-inline
2501/// integer-set-id ::= `@@` suffix-id
2502///
2503IntegerSet *Parser::parseIntegerSetReference() {
2504 if (getToken().is(Token::double_at_identifier)) {
2505 // Parse integer set identifier and verify that it exists.
2506 StringRef integerSetId = getTokenSpelling().drop_front(2);
2507 if (getState().integerSetDefinitions.count(integerSetId) == 0)
2508 return (emitError("undefined integer set id '" + integerSetId + "'"),
2509 nullptr);
2510 consumeToken(Token::double_at_identifier);
2511 return getState().integerSetDefinitions[integerSetId];
2512 }
2513 // Try to parse an inline integer set definition.
2514 return parseIntegerSetInline();
2515}
2516
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002517/// If statement.
2518///
Chris Lattner48af7d12018-07-09 19:05:38 -07002519/// ml-if-head ::= `if` ml-if-cond `{` ml-stmt* `}`
2520/// | ml-if-head `else` `if` ml-if-cond `{` ml-stmt* `}`
2521/// ml-if-stmt ::= ml-if-head
2522/// | ml-if-head `else` `{` ml-stmt* `}`
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002523///
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002524ParseResult MLFunctionParser::parseIfStmt() {
Chris Lattner1628fa02018-08-23 14:32:25 -07002525 auto loc = getToken().getLoc();
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002526 consumeToken(Token::kw_if);
Uday Bondhugulabc535622018-08-07 14:24:38 -07002527
2528 if (parseToken(Token::l_paren, "expected '('"))
Chris Lattnerf7702a62018-07-23 17:30:01 -07002529 return ParseFailure;
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002530
Uday Bondhugulabc535622018-08-07 14:24:38 -07002531 IntegerSet *condition = parseCondition();
2532 if (!condition)
Chris Lattnerf7702a62018-07-23 17:30:01 -07002533 return ParseFailure;
Tatiana Shpeisman1bcfe982018-07-13 13:03:13 -07002534
Uday Bondhugulabc535622018-08-07 14:24:38 -07002535 if (parseToken(Token::r_paren, "expected ')'"))
2536 return ParseFailure;
2537
Chris Lattner1628fa02018-08-23 14:32:25 -07002538 IfStmt *ifStmt = builder.createIf(getEncodedSourceLocation(loc), condition);
Chris Lattnere787b322018-08-08 11:14:57 -07002539 IfClause *thenClause = ifStmt->getThen();
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002540
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002541 // When parsing of an if statement body fails, the IR contains
2542 // the if statement with the portion of the body that has been
2543 // successfully parsed.
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002544 if (parseStmtBlock(thenClause))
2545 return ParseFailure;
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002546
Tatiana Shpeisman1bcfe982018-07-13 13:03:13 -07002547 if (consumeIf(Token::kw_else)) {
Chris Lattnere787b322018-08-08 11:14:57 -07002548 auto *elseClause = ifStmt->createElse();
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002549 if (parseElseClause(elseClause))
2550 return ParseFailure;
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002551 }
2552
Tatiana Shpeisman3838db72018-07-30 15:18:10 -07002553 // Reset insertion point to the current block.
Chris Lattnere787b322018-08-08 11:14:57 -07002554 builder.setInsertionPointToEnd(ifStmt->getBlock());
Tatiana Shpeisman3838db72018-07-30 15:18:10 -07002555
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002556 return ParseSuccess;
Tatiana Shpeisman1bcfe982018-07-13 13:03:13 -07002557}
2558
2559ParseResult MLFunctionParser::parseElseClause(IfClause *elseClause) {
2560 if (getToken().is(Token::kw_if)) {
Chris Lattnere787b322018-08-08 11:14:57 -07002561 builder.setInsertionPointToEnd(elseClause);
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002562 return parseIfStmt();
Tatiana Shpeisman1bcfe982018-07-13 13:03:13 -07002563 }
2564
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002565 return parseStmtBlock(elseClause);
2566}
2567
2568///
2569/// Parse a list of statements ending with `return` or `}`
2570///
2571ParseResult MLFunctionParser::parseStatements(StmtBlock *block) {
Chris Lattner992a1272018-08-07 12:02:37 -07002572 auto createOpFunc = [&](const OperationState &state) -> Operation * {
2573 return builder.createOperation(state);
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002574 };
2575
Chris Lattnere787b322018-08-08 11:14:57 -07002576 builder.setInsertionPointToEnd(block);
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002577
Tatiana Shpeismand9b1d862018-08-09 12:28:58 -07002578 // Parse statements till we see '}' or 'return'.
2579 // Return statement is parsed separately to emit a more intuitive error
2580 // when '}' is missing after the return statement.
2581 while (getToken().isNot(Token::r_brace, Token::kw_return)) {
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002582 switch (getToken().getKind()) {
2583 default:
2584 if (parseOperation(createOpFunc))
2585 return ParseFailure;
2586 break;
2587 case Token::kw_for:
2588 if (parseForStmt())
2589 return ParseFailure;
2590 break;
2591 case Token::kw_if:
2592 if (parseIfStmt())
2593 return ParseFailure;
2594 break;
2595 } // end switch
2596 }
Tatiana Shpeisman1bcfe982018-07-13 13:03:13 -07002597
Tatiana Shpeismand9b1d862018-08-09 12:28:58 -07002598 // Parse the return statement.
2599 if (getToken().is(Token::kw_return))
2600 if (parseOperation(createOpFunc))
2601 return ParseFailure;
2602
Tatiana Shpeisman1bcfe982018-07-13 13:03:13 -07002603 return ParseSuccess;
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002604}
2605
2606///
2607/// Parse `{` ml-stmt* `}`
2608///
Tatiana Shpeisman1bcfe982018-07-13 13:03:13 -07002609ParseResult MLFunctionParser::parseStmtBlock(StmtBlock *block) {
Chris Lattnerf7702a62018-07-23 17:30:01 -07002610 if (parseToken(Token::l_brace, "expected '{' before statement list") ||
2611 parseStatements(block) ||
Tatiana Shpeismand9b1d862018-08-09 12:28:58 -07002612 parseToken(Token::r_brace, "expected '}' after statement list"))
Tatiana Shpeisman565b9642018-07-16 11:47:09 -07002613 return ParseFailure;
2614
Tatiana Shpeismanbf079c92018-07-03 17:51:28 -07002615 return ParseSuccess;
2616}
2617
Chris Lattner4c95a502018-06-23 16:03:42 -07002618//===----------------------------------------------------------------------===//
2619// Top-level entity parsing.
2620//===----------------------------------------------------------------------===//
2621
Chris Lattner2e595eb2018-07-10 10:08:27 -07002622namespace {
2623/// This parser handles entities that are only valid at the top level of the
2624/// file.
2625class ModuleParser : public Parser {
2626public:
2627 explicit ModuleParser(ParserState &state) : Parser(state) {}
2628
2629 ParseResult parseModule();
2630
2631private:
Chris Lattner4613d9e2018-08-19 21:17:22 -07002632 ParseResult finalizeModule();
2633
Chris Lattner2e595eb2018-07-10 10:08:27 -07002634 ParseResult parseAffineMapDef();
Uday Bondhugulabc535622018-08-07 14:24:38 -07002635 ParseResult parseIntegerSetDef();
Chris Lattner2e595eb2018-07-10 10:08:27 -07002636
2637 // Functions.
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002638 ParseResult parseMLArgumentList(SmallVectorImpl<Type *> &argTypes,
2639 SmallVectorImpl<StringRef> &argNames);
2640 ParseResult parseFunctionSignature(StringRef &name, FunctionType *&type,
2641 SmallVectorImpl<StringRef> *argNames);
Chris Lattner2e595eb2018-07-10 10:08:27 -07002642 ParseResult parseExtFunc();
2643 ParseResult parseCFGFunc();
2644 ParseResult parseMLFunc();
2645};
2646} // end anonymous namespace
2647
2648/// Affine map declaration.
2649///
2650/// affine-map-def ::= affine-map-id `=` affine-map-inline
2651///
2652ParseResult ModuleParser::parseAffineMapDef() {
2653 assert(getToken().is(Token::hash_identifier));
2654
2655 StringRef affineMapId = getTokenSpelling().drop_front();
2656
2657 // Check for redefinitions.
Nicolas Vasilache97298152018-08-27 10:10:42 -07002658 auto *&entry = getState().affineMapDefinitions[affineMapId];
2659 if (entry)
Chris Lattner2e595eb2018-07-10 10:08:27 -07002660 return emitError("redefinition of affine map id '" + affineMapId + "'");
2661
2662 consumeToken(Token::hash_identifier);
2663
2664 // Parse the '='
Chris Lattnerf7702a62018-07-23 17:30:01 -07002665 if (parseToken(Token::equal,
2666 "expected '=' in affine map outlined definition"))
2667 return ParseFailure;
Chris Lattner2e595eb2018-07-10 10:08:27 -07002668
Nicolas Vasilache97298152018-08-27 10:10:42 -07002669 entry = parseAffineMapInline();
2670 if (!entry)
Uday Bondhugulabc535622018-08-07 14:24:38 -07002671 return ParseFailure;
2672
2673 return ParseSuccess;
2674}
2675
2676/// Integer set declaration.
2677///
2678/// integer-set-decl ::= integer-set-id `=` integer-set-inline
2679///
2680ParseResult ModuleParser::parseIntegerSetDef() {
2681 assert(getToken().is(Token::double_at_identifier));
2682
2683 StringRef integerSetId = getTokenSpelling().drop_front(2);
2684
2685 // Check for redefinitions (a default entry is created if one doesn't exist)
Nicolas Vasilache97298152018-08-27 10:10:42 -07002686 auto *&entry = getState().integerSetDefinitions[integerSetId];
2687 if (entry)
Uday Bondhugulabc535622018-08-07 14:24:38 -07002688 return emitError("redefinition of integer set id '" + integerSetId + "'");
2689
2690 consumeToken(Token::double_at_identifier);
2691
2692 // Parse the '='
2693 if (parseToken(Token::equal,
2694 "expected '=' in outlined integer set definition"))
2695 return ParseFailure;
2696
Nicolas Vasilache97298152018-08-27 10:10:42 -07002697 entry = parseIntegerSetInline();
2698 if (!entry)
Chris Lattner2e595eb2018-07-10 10:08:27 -07002699 return ParseFailure;
2700
Chris Lattner2e595eb2018-07-10 10:08:27 -07002701 return ParseSuccess;
2702}
2703
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002704/// Parse a (possibly empty) list of MLFunction arguments with types.
2705///
2706/// ml-argument ::= ssa-id `:` type
2707/// ml-argument-list ::= ml-argument (`,` ml-argument)* | /*empty*/
2708///
2709ParseResult
2710ModuleParser::parseMLArgumentList(SmallVectorImpl<Type *> &argTypes,
2711 SmallVectorImpl<StringRef> &argNames) {
Chris Lattnerf7702a62018-07-23 17:30:01 -07002712 consumeToken(Token::l_paren);
2713
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002714 auto parseElt = [&]() -> ParseResult {
2715 // Parse argument name
2716 if (getToken().isNot(Token::percent_identifier))
2717 return emitError("expected SSA identifier");
2718
Tatiana Shpeismanbc3c7492018-08-06 11:54:39 -07002719 StringRef name = getTokenSpelling();
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002720 consumeToken(Token::percent_identifier);
2721 argNames.push_back(name);
2722
Chris Lattnerf7702a62018-07-23 17:30:01 -07002723 if (parseToken(Token::colon, "expected ':'"))
2724 return ParseFailure;
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002725
2726 // Parse argument type
2727 auto elt = parseType();
2728 if (!elt)
2729 return ParseFailure;
2730 argTypes.push_back(elt);
2731
2732 return ParseSuccess;
2733 };
2734
Chris Lattner40746442018-07-21 14:32:09 -07002735 return parseCommaSeparatedListUntil(Token::r_paren, parseElt);
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002736}
2737
Chris Lattner2e595eb2018-07-10 10:08:27 -07002738/// Parse a function signature, starting with a name and including the parameter
2739/// list.
2740///
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002741/// argument-list ::= type (`,` type)* | /*empty*/ | ml-argument-list
Chris Lattner2e595eb2018-07-10 10:08:27 -07002742/// function-signature ::= function-id `(` argument-list `)` (`->` type-list)?
2743///
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002744ParseResult
2745ModuleParser::parseFunctionSignature(StringRef &name, FunctionType *&type,
2746 SmallVectorImpl<StringRef> *argNames) {
Chris Lattner2e595eb2018-07-10 10:08:27 -07002747 if (getToken().isNot(Token::at_identifier))
2748 return emitError("expected a function identifier like '@foo'");
2749
2750 name = getTokenSpelling().drop_front();
2751 consumeToken(Token::at_identifier);
2752
2753 if (getToken().isNot(Token::l_paren))
2754 return emitError("expected '(' in function signature");
2755
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002756 SmallVector<Type *, 4> argTypes;
2757 ParseResult parseResult;
2758
2759 if (argNames)
2760 parseResult = parseMLArgumentList(argTypes, *argNames);
2761 else
2762 parseResult = parseTypeList(argTypes);
2763
2764 if (parseResult)
Chris Lattner2e595eb2018-07-10 10:08:27 -07002765 return ParseFailure;
2766
2767 // Parse the return type if present.
2768 SmallVector<Type *, 4> results;
2769 if (consumeIf(Token::arrow)) {
2770 if (parseTypeList(results))
2771 return ParseFailure;
2772 }
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002773 type = builder.getFunctionType(argTypes, results);
Chris Lattner2e595eb2018-07-10 10:08:27 -07002774 return ParseSuccess;
2775}
2776
2777/// External function declarations.
2778///
2779/// ext-func ::= `extfunc` function-signature
2780///
2781ParseResult ModuleParser::parseExtFunc() {
2782 consumeToken(Token::kw_extfunc);
Chris Lattner974a8762018-08-17 16:49:42 -07002783 auto loc = getToken().getLoc();
Chris Lattner2e595eb2018-07-10 10:08:27 -07002784
2785 StringRef name;
2786 FunctionType *type = nullptr;
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002787 if (parseFunctionSignature(name, type, /*arguments*/ nullptr))
Chris Lattner2e595eb2018-07-10 10:08:27 -07002788 return ParseFailure;
2789
2790 // Okay, the external function definition was parsed correctly.
Chris Lattner974a8762018-08-17 16:49:42 -07002791 auto *function = new ExtFunction(name, type);
2792 getModule()->getFunctions().push_back(function);
2793
2794 // Verify no name collision / redefinition.
Chris Lattner4613d9e2018-08-19 21:17:22 -07002795 if (function->getName() != name)
Chris Lattner974a8762018-08-17 16:49:42 -07002796 return emitError(loc,
2797 "redefinition of function named '" + name.str() + "'");
2798
Chris Lattner2e595eb2018-07-10 10:08:27 -07002799 return ParseSuccess;
2800}
2801
2802/// CFG function declarations.
2803///
2804/// cfg-func ::= `cfgfunc` function-signature `{` basic-block+ `}`
2805///
2806ParseResult ModuleParser::parseCFGFunc() {
2807 consumeToken(Token::kw_cfgfunc);
Chris Lattner974a8762018-08-17 16:49:42 -07002808 auto loc = getToken().getLoc();
Chris Lattner2e595eb2018-07-10 10:08:27 -07002809
2810 StringRef name;
2811 FunctionType *type = nullptr;
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002812 if (parseFunctionSignature(name, type, /*arguments*/ nullptr))
Chris Lattner2e595eb2018-07-10 10:08:27 -07002813 return ParseFailure;
2814
2815 // Okay, the CFG function signature was parsed correctly, create the function.
Chris Lattner974a8762018-08-17 16:49:42 -07002816 auto *function = new CFGFunction(name, type);
2817 getModule()->getFunctions().push_back(function);
2818
2819 // Verify no name collision / redefinition.
Chris Lattner4613d9e2018-08-19 21:17:22 -07002820 if (function->getName() != name)
Chris Lattner974a8762018-08-17 16:49:42 -07002821 return emitError(loc,
2822 "redefinition of function named '" + name.str() + "'");
Chris Lattner2e595eb2018-07-10 10:08:27 -07002823
2824 return CFGFunctionParser(getState(), function).parseFunctionBody();
2825}
2826
2827/// ML function declarations.
2828///
2829/// ml-func ::= `mlfunc` ml-func-signature `{` ml-stmt* ml-return-stmt `}`
2830///
2831ParseResult ModuleParser::parseMLFunc() {
2832 consumeToken(Token::kw_mlfunc);
2833
2834 StringRef name;
2835 FunctionType *type = nullptr;
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002836 SmallVector<StringRef, 4> argNames;
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002837
Tatiana Shpeismanbc3c7492018-08-06 11:54:39 -07002838 auto loc = getToken().getLoc();
Tatiana Shpeisman1da50c42018-07-19 09:52:39 -07002839 if (parseFunctionSignature(name, type, &argNames))
Chris Lattner2e595eb2018-07-10 10:08:27 -07002840 return ParseFailure;
2841
2842 // Okay, the ML function signature was parsed correctly, create the function.
Chris Lattner974a8762018-08-17 16:49:42 -07002843 auto *function = MLFunction::create(name, type);
2844 getModule()->getFunctions().push_back(function);
2845
2846 // Verify no name collision / redefinition.
Chris Lattner4613d9e2018-08-19 21:17:22 -07002847 if (function->getName() != name)
Chris Lattner974a8762018-08-17 16:49:42 -07002848 return emitError(loc,
2849 "redefinition of function named '" + name.str() + "'");
Chris Lattner2e595eb2018-07-10 10:08:27 -07002850
Tatiana Shpeismanbc3c7492018-08-06 11:54:39 -07002851 // Create the parser.
2852 auto parser = MLFunctionParser(getState(), function);
2853
2854 // Add definitions of the function arguments.
2855 for (unsigned i = 0, e = function->getNumArguments(); i != e; ++i) {
2856 if (parser.addDefinition({argNames[i], 0, loc}, function->getArgument(i)))
2857 return ParseFailure;
2858 }
2859
2860 return parser.parseFunctionBody();
Chris Lattner2e595eb2018-07-10 10:08:27 -07002861}
2862
Chris Lattnerea5c3dc2018-08-21 08:42:19 -07002863/// Given an attribute that could refer to a function attribute in the remapping
2864/// table, walk it and rewrite it to use the mapped function. If it doesn't
2865/// refer to anything in the table, then it is returned unmodified.
2866static Attribute *
2867remapFunctionAttrs(Attribute *input,
2868 DenseMap<FunctionAttr *, FunctionAttr *> &remappingTable,
2869 MLIRContext *context) {
2870 // Most attributes are trivially unrelated to function attributes, skip them
2871 // rapidly.
2872 if (!input->isOrContainsFunction())
2873 return input;
2874
2875 // If we have a function attribute, remap it.
2876 if (auto *fnAttr = dyn_cast<FunctionAttr>(input)) {
2877 auto it = remappingTable.find(fnAttr);
2878 return it != remappingTable.end() ? it->second : input;
2879 }
2880
2881 // Otherwise, we must have an array attribute, remap the elements.
2882 auto *arrayAttr = cast<ArrayAttr>(input);
2883 SmallVector<Attribute *, 8> remappedElts;
2884 bool anyChange = false;
2885 for (auto *elt : arrayAttr->getValue()) {
2886 auto *newElt = remapFunctionAttrs(elt, remappingTable, context);
2887 remappedElts.push_back(newElt);
2888 anyChange |= (elt != newElt);
2889 }
2890
2891 if (!anyChange)
2892 return input;
2893
2894 return ArrayAttr::get(remappedElts, context);
2895}
2896
2897/// Remap function attributes to resolve forward references to their actual
2898/// definition.
2899static void remapFunctionAttrsInOperation(
2900 Operation *op, DenseMap<FunctionAttr *, FunctionAttr *> &remappingTable) {
2901 for (auto attr : op->getAttrs()) {
2902 // Do the remapping, if we got the same thing back, then it must contain
2903 // functions that aren't getting remapped.
2904 auto *newVal =
2905 remapFunctionAttrs(attr.second, remappingTable, op->getContext());
2906 if (newVal == attr.second)
2907 continue;
2908
2909 // Otherwise, replace the existing attribute with the new one. It is safe
2910 // to mutate the attribute list while we walk it because underlying
2911 // attribute lists are uniqued and immortal.
2912 op->setAttr(attr.first, newVal);
2913 }
2914}
2915
Chris Lattner4613d9e2018-08-19 21:17:22 -07002916/// Finish the end of module parsing - when the result is valid, do final
2917/// checking.
2918ParseResult ModuleParser::finalizeModule() {
2919
Chris Lattnerea5c3dc2018-08-21 08:42:19 -07002920 // Resolve all forward references, building a remapping table of attributes.
2921 DenseMap<FunctionAttr *, FunctionAttr *> remappingTable;
Chris Lattner4613d9e2018-08-19 21:17:22 -07002922 for (auto forwardRef : getState().functionForwardRefs) {
2923 auto name = forwardRef.first;
2924
2925 // Resolve the reference.
2926 auto *resolvedFunction = getModule()->getNamedFunction(name);
2927 if (!resolvedFunction)
2928 return emitError(forwardRef.second.second,
2929 "reference to undefined function '" + name.str() + "'");
2930
Chris Lattnerea5c3dc2018-08-21 08:42:19 -07002931 remappingTable[builder.getFunctionAttr(forwardRef.second.first)] =
2932 builder.getFunctionAttr(resolvedFunction);
Chris Lattner4613d9e2018-08-19 21:17:22 -07002933 }
2934
Chris Lattnerea5c3dc2018-08-21 08:42:19 -07002935 // If there was nothing to remap, then we're done.
2936 if (remappingTable.empty())
2937 return ParseSuccess;
2938
2939 // Otherwise, walk the entire module replacing uses of one attribute set with
2940 // the correct ones.
2941 for (auto &fn : *getModule()) {
2942 if (auto *cfgFn = dyn_cast<CFGFunction>(&fn)) {
2943 for (auto &bb : *cfgFn) {
2944 for (auto &inst : bb) {
2945 remapFunctionAttrsInOperation(&inst, remappingTable);
2946 }
2947 }
2948 }
2949
2950 // Otherwise, look at MLFunctions. We ignore ExtFunctions.
2951 auto *mlFn = dyn_cast<MLFunction>(&fn);
2952 if (!mlFn)
2953 continue;
2954
2955 struct MLFnWalker : public StmtWalker<MLFnWalker> {
2956 MLFnWalker(DenseMap<FunctionAttr *, FunctionAttr *> &remappingTable)
2957 : remappingTable(remappingTable) {}
2958 void visitOperationStmt(OperationStmt *opStmt) {
2959 remapFunctionAttrsInOperation(opStmt, remappingTable);
2960 }
2961
2962 DenseMap<FunctionAttr *, FunctionAttr *> &remappingTable;
2963 };
2964
2965 MLFnWalker(remappingTable).walk(mlFn);
2966 }
2967
2968 // Now that all references to the forward definition placeholders are
2969 // resolved, we can deallocate the placeholders.
2970 for (auto forwardRef : getState().functionForwardRefs)
2971 forwardRef.second.first->destroy();
Chris Lattner4613d9e2018-08-19 21:17:22 -07002972 return ParseSuccess;
2973}
2974
Chris Lattnere79379a2018-06-22 10:39:19 -07002975/// This is the top-level module parser.
Chris Lattner2e595eb2018-07-10 10:08:27 -07002976ParseResult ModuleParser::parseModule() {
Chris Lattnere79379a2018-06-22 10:39:19 -07002977 while (1) {
Chris Lattner48af7d12018-07-09 19:05:38 -07002978 switch (getToken().getKind()) {
Chris Lattnere79379a2018-06-22 10:39:19 -07002979 default:
2980 emitError("expected a top level entity");
Chris Lattner2e595eb2018-07-10 10:08:27 -07002981 return ParseFailure;
Chris Lattnere79379a2018-06-22 10:39:19 -07002982
Uday Bondhugula015cbb12018-07-03 20:16:08 -07002983 // If we got to the end of the file, then we're done.
Chris Lattnere79379a2018-06-22 10:39:19 -07002984 case Token::eof:
Chris Lattner4613d9e2018-08-19 21:17:22 -07002985 return finalizeModule();
Chris Lattnere79379a2018-06-22 10:39:19 -07002986
2987 // If we got an error token, then the lexer already emitted an error, just
2988 // stop. Someday we could introduce error recovery if there was demand for
2989 // it.
2990 case Token::error:
Chris Lattner2e595eb2018-07-10 10:08:27 -07002991 return ParseFailure;
2992
2993 case Token::hash_identifier:
2994 if (parseAffineMapDef())
2995 return ParseFailure;
2996 break;
Chris Lattnere79379a2018-06-22 10:39:19 -07002997
Uday Bondhugulabc535622018-08-07 14:24:38 -07002998 case Token::double_at_identifier:
2999 if (parseIntegerSetDef())
3000 return ParseFailure;
3001 break;
3002
Chris Lattnere79379a2018-06-22 10:39:19 -07003003 case Token::kw_extfunc:
Chris Lattner2e595eb2018-07-10 10:08:27 -07003004 if (parseExtFunc())
3005 return ParseFailure;
Chris Lattnere79379a2018-06-22 10:39:19 -07003006 break;
3007
Chris Lattner4c95a502018-06-23 16:03:42 -07003008 case Token::kw_cfgfunc:
Chris Lattner2e595eb2018-07-10 10:08:27 -07003009 if (parseCFGFunc())
3010 return ParseFailure;
MLIR Teamf85a6262018-06-27 11:03:08 -07003011 break;
Chris Lattner4c95a502018-06-23 16:03:42 -07003012
Tatiana Shpeismanc96b5872018-06-28 17:02:32 -07003013 case Token::kw_mlfunc:
Chris Lattner2e595eb2018-07-10 10:08:27 -07003014 if (parseMLFunc())
3015 return ParseFailure;
Tatiana Shpeismanc96b5872018-06-28 17:02:32 -07003016 break;
Chris Lattnere79379a2018-06-22 10:39:19 -07003017 }
3018 }
3019}
3020
3021//===----------------------------------------------------------------------===//
3022
Jacques Pienaar7b829702018-07-03 13:24:09 -07003023void mlir::defaultErrorReporter(const llvm::SMDiagnostic &error) {
3024 const auto &sourceMgr = *error.getSourceMgr();
3025 sourceMgr.PrintMessage(error.getLoc(), error.getKind(), error.getMessage());
3026}
3027
Chris Lattnere79379a2018-06-22 10:39:19 -07003028/// This parses the file specified by the indicated SourceMgr and returns an
3029/// MLIR module if it was valid. If not, it emits diagnostics and returns null.
Jacques Pienaar9c411be2018-06-24 19:17:35 -07003030Module *mlir::parseSourceFile(llvm::SourceMgr &sourceMgr, MLIRContext *context,
Jacques Pienaar7b829702018-07-03 13:24:09 -07003031 SMDiagnosticHandlerTy errorReporter) {
Chris Lattnerea5c3dc2018-08-21 08:42:19 -07003032 if (!errorReporter)
3033 errorReporter = defaultErrorReporter;
3034
3035 // We are going to replace the context's handler and redirect it to use the
3036 // error reporter. Save the existing handler and reinstate it when we're
3037 // done.
3038 auto existingContextHandler = context->getDiagnosticHandler();
3039
3040 // Install a new handler that uses the error reporter.
3041 context->registerDiagnosticHandler([&](Attribute *location, StringRef message,
3042 MLIRContext::DiagnosticKind kind) {
3043 auto offset = cast<IntegerAttr>(location)->getValue();
3044 auto *mainBuffer = sourceMgr.getMemoryBuffer(sourceMgr.getMainFileID());
3045 auto ptr = mainBuffer->getBufferStart() + offset;
3046 SourceMgr::DiagKind diagKind;
3047 switch (kind) {
3048 case MLIRContext::DiagnosticKind::Error:
3049 diagKind = SourceMgr::DK_Error;
3050 break;
3051 case MLIRContext::DiagnosticKind::Warning:
3052 diagKind = SourceMgr::DK_Warning;
3053 break;
3054 case MLIRContext::DiagnosticKind::Note:
3055 diagKind = SourceMgr::DK_Note;
3056 break;
3057 }
3058 errorReporter(
3059 sourceMgr.GetMessage(SMLoc::getFromPointer(ptr), diagKind, message));
3060 });
3061
Chris Lattner2e595eb2018-07-10 10:08:27 -07003062 // This is the result module we are parsing into.
3063 std::unique_ptr<Module> module(new Module(context));
3064
Chris Lattnerea5c3dc2018-08-21 08:42:19 -07003065 ParserState state(sourceMgr, module.get(), errorReporter);
3066 if (ModuleParser(state).parseModule()) {
3067 context->registerDiagnosticHandler(existingContextHandler);
Chris Lattner2e595eb2018-07-10 10:08:27 -07003068 return nullptr;
Chris Lattnerea5c3dc2018-08-21 08:42:19 -07003069 }
Chris Lattner21e67f62018-07-06 10:46:19 -07003070
3071 // Make sure the parse module has no other structural problems detected by the
3072 // verifier.
Chris Lattnerea5c3dc2018-08-21 08:42:19 -07003073 std::string errorResult;
3074 module->verify(&errorResult);
3075
3076 // We don't have location information for general verifier errors, so emit the
3077 // error on the first line.
3078 if (!errorResult.empty()) {
3079 auto *mainBuffer = sourceMgr.getMemoryBuffer(sourceMgr.getMainFileID());
3080 errorReporter(sourceMgr.GetMessage(
3081 SMLoc::getFromPointer(mainBuffer->getBufferStart()),
3082 SourceMgr::DK_Error, errorResult));
3083 return nullptr;
3084 }
3085
3086 context->registerDiagnosticHandler(existingContextHandler);
Chris Lattner2e595eb2018-07-10 10:08:27 -07003087 return module.release();
Chris Lattnere79379a2018-06-22 10:39:19 -07003088}