blob: df952f95ea9fe7c245747bec3b828af14eb70bc7 [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"
MLIR Teamf85a6262018-06-27 11:03:08 -070024#include "mlir/IR/AffineMap.h"
Chris Lattnere79379a2018-06-22 10:39:19 -070025#include "mlir/IR/Module.h"
Chris Lattner4c95a502018-06-23 16:03:42 -070026#include "mlir/IR/CFGFunction.h"
Tatiana Shpeismanc96b5872018-06-28 17:02:32 -070027#include "mlir/IR/MLFunction.h"
Chris Lattnerf7e22732018-06-22 22:03:48 -070028#include "mlir/IR/Types.h"
Chris Lattnere79379a2018-06-22 10:39:19 -070029#include "llvm/Support/SourceMgr.h"
30using namespace mlir;
31using llvm::SourceMgr;
Chris Lattner4c95a502018-06-23 16:03:42 -070032using llvm::SMLoc;
Chris Lattnere79379a2018-06-22 10:39:19 -070033
34namespace {
Chris Lattner4c95a502018-06-23 16:03:42 -070035class CFGFunctionParserState;
36
Chris Lattnerf7e22732018-06-22 22:03:48 -070037/// Simple enum to make code read better in cases that would otherwise return a
38/// bool value. Failure is "true" in a boolean context.
Chris Lattnere79379a2018-06-22 10:39:19 -070039enum ParseResult {
40 ParseSuccess,
41 ParseFailure
42};
43
44/// Main parser implementation.
45class Parser {
46 public:
Jacques Pienaar9c411be2018-06-24 19:17:35 -070047 Parser(llvm::SourceMgr &sourceMgr, MLIRContext *context,
48 const SMDiagnosticHandlerTy &errorReporter)
49 : context(context),
50 lex(sourceMgr, errorReporter),
51 curToken(lex.lexToken()),
52 errorReporter(errorReporter) {
Chris Lattnere79379a2018-06-22 10:39:19 -070053 module.reset(new Module());
54 }
55
56 Module *parseModule();
57private:
58 // State.
Chris Lattnerf7e22732018-06-22 22:03:48 -070059 MLIRContext *const context;
60
61 // The lexer for the source file we're parsing.
Chris Lattnere79379a2018-06-22 10:39:19 -070062 Lexer lex;
63
64 // This is the next token that hasn't been consumed yet.
65 Token curToken;
66
Jacques Pienaar9c411be2018-06-24 19:17:35 -070067 // The diagnostic error reporter.
68 const SMDiagnosticHandlerTy &errorReporter;
69
Chris Lattnere79379a2018-06-22 10:39:19 -070070 // This is the result module we are parsing into.
71 std::unique_ptr<Module> module;
72
MLIR Teamf85a6262018-06-27 11:03:08 -070073 // A map from affine map identifier to AffineMap.
74 // TODO(andydavis) Remove use of unique_ptr when AffineMaps are bump pointer
75 // allocated.
76 llvm::StringMap<std::unique_ptr<AffineMap>> affineMaps;
77
Chris Lattnere79379a2018-06-22 10:39:19 -070078private:
79 // Helper methods.
80
81 /// Emit an error and return failure.
Chris Lattner4c95a502018-06-23 16:03:42 -070082 ParseResult emitError(const Twine &message) {
83 return emitError(curToken.getLoc(), message);
84 }
85 ParseResult emitError(SMLoc loc, const Twine &message);
Chris Lattnere79379a2018-06-22 10:39:19 -070086
87 /// Advance the current lexer onto the next token.
88 void consumeToken() {
89 assert(curToken.isNot(Token::eof, Token::error) &&
90 "shouldn't advance past EOF or errors");
91 curToken = lex.lexToken();
92 }
93
94 /// Advance the current lexer onto the next token, asserting what the expected
95 /// current token is. This is preferred to the above method because it leads
96 /// to more self-documenting code with better checking.
97 void consumeToken(Token::TokenKind kind) {
98 assert(curToken.is(kind) && "consumed an unexpected token");
99 consumeToken();
100 }
101
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700102 /// If the current token has the specified kind, consume it and return true.
103 /// If not, return false.
104 bool consumeIf(Token::TokenKind kind) {
105 if (curToken.isNot(kind))
106 return false;
107 consumeToken(kind);
108 return true;
109 }
110
111 ParseResult parseCommaSeparatedList(Token::TokenKind rightToken,
112 const std::function<ParseResult()> &parseElement,
113 bool allowEmptyList = true);
114
Chris Lattnerf7e22732018-06-22 22:03:48 -0700115 // We have two forms of parsing methods - those that return a non-null
116 // pointer on success, and those that return a ParseResult to indicate whether
117 // they returned a failure. The second class fills in by-reference arguments
118 // as the results of their action.
119
Chris Lattnere79379a2018-06-22 10:39:19 -0700120 // Type parsing.
Chris Lattnerf7e22732018-06-22 22:03:48 -0700121 PrimitiveType *parsePrimitiveType();
122 Type *parseElementType();
123 VectorType *parseVectorType();
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700124 ParseResult parseDimensionListRanked(SmallVectorImpl<int> &dimensions);
Chris Lattnerf7e22732018-06-22 22:03:48 -0700125 Type *parseTensorType();
126 Type *parseMemRefType();
127 Type *parseFunctionType();
128 Type *parseType();
129 ParseResult parseTypeList(SmallVectorImpl<Type*> &elements);
Chris Lattnere79379a2018-06-22 10:39:19 -0700130
MLIR Teamf85a6262018-06-27 11:03:08 -0700131 // Polyhedral structures
132 ParseResult parseAffineMapDef();
133
Chris Lattner4c95a502018-06-23 16:03:42 -0700134 // Functions.
Chris Lattnerf7e22732018-06-22 22:03:48 -0700135 ParseResult parseFunctionSignature(StringRef &name, FunctionType *&type);
Chris Lattnere79379a2018-06-22 10:39:19 -0700136 ParseResult parseExtFunc();
Chris Lattner4c95a502018-06-23 16:03:42 -0700137 ParseResult parseCFGFunc();
Tatiana Shpeismanc96b5872018-06-28 17:02:32 -0700138 ParseResult parseMLFunc();
Chris Lattner4c95a502018-06-23 16:03:42 -0700139 ParseResult parseBasicBlock(CFGFunctionParserState &functionState);
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700140 TerminatorInst *parseTerminator(BasicBlock *currentBB,
141 CFGFunctionParserState &functionState);
Tatiana Shpeismanc96b5872018-06-28 17:02:32 -0700142 MLStatement *parseMLStatement(MLFunction *currentFunction);
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700143
Chris Lattnere79379a2018-06-22 10:39:19 -0700144};
145} // end anonymous namespace
146
147//===----------------------------------------------------------------------===//
148// Helper methods.
149//===----------------------------------------------------------------------===//
150
Chris Lattner4c95a502018-06-23 16:03:42 -0700151ParseResult Parser::emitError(SMLoc loc, const Twine &message) {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700152 // If we hit a parse error in response to a lexer error, then the lexer
Jacques Pienaar9c411be2018-06-24 19:17:35 -0700153 // already reported the error.
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700154 if (curToken.is(Token::error))
155 return ParseFailure;
156
Jacques Pienaar9c411be2018-06-24 19:17:35 -0700157 errorReporter(
158 lex.getSourceMgr().GetMessage(loc, SourceMgr::DK_Error, message));
Chris Lattnere79379a2018-06-22 10:39:19 -0700159 return ParseFailure;
160}
161
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700162/// Parse a comma-separated list of elements, terminated with an arbitrary
163/// token. This allows empty lists if allowEmptyList is true.
164///
165/// abstract-list ::= rightToken // if allowEmptyList == true
166/// abstract-list ::= element (',' element)* rightToken
167///
168ParseResult Parser::
169parseCommaSeparatedList(Token::TokenKind rightToken,
170 const std::function<ParseResult()> &parseElement,
171 bool allowEmptyList) {
172 // Handle the empty case.
173 if (curToken.is(rightToken)) {
174 if (!allowEmptyList)
175 return emitError("expected list element");
176 consumeToken(rightToken);
177 return ParseSuccess;
178 }
179
180 // Non-empty case starts with an element.
181 if (parseElement())
182 return ParseFailure;
183
184 // Otherwise we have a list of comma separated elements.
185 while (consumeIf(Token::comma)) {
186 if (parseElement())
187 return ParseFailure;
188 }
189
190 // Consume the end character.
191 if (!consumeIf(rightToken))
192 return emitError("expected ',' or ')'");
193
194 return ParseSuccess;
195}
Chris Lattnere79379a2018-06-22 10:39:19 -0700196
197//===----------------------------------------------------------------------===//
198// Type Parsing
199//===----------------------------------------------------------------------===//
200
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700201/// Parse the low-level fixed dtypes in the system.
202///
203/// primitive-type
204/// ::= `f16` | `bf16` | `f32` | `f64` // Floating point
205/// | `i1` | `i8` | `i16` | `i32` | `i64` // Sized integers
206/// | `int`
207///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700208PrimitiveType *Parser::parsePrimitiveType() {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700209 switch (curToken.getKind()) {
Chris Lattnerf7e22732018-06-22 22:03:48 -0700210 default:
211 return (emitError("expected type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700212 case Token::kw_bf16:
213 consumeToken(Token::kw_bf16);
Chris Lattnerf7e22732018-06-22 22:03:48 -0700214 return Type::getBF16(context);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700215 case Token::kw_f16:
216 consumeToken(Token::kw_f16);
Chris Lattnerf7e22732018-06-22 22:03:48 -0700217 return Type::getF16(context);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700218 case Token::kw_f32:
219 consumeToken(Token::kw_f32);
Chris Lattnerf7e22732018-06-22 22:03:48 -0700220 return Type::getF32(context);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700221 case Token::kw_f64:
222 consumeToken(Token::kw_f64);
Chris Lattnerf7e22732018-06-22 22:03:48 -0700223 return Type::getF64(context);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700224 case Token::kw_i1:
225 consumeToken(Token::kw_i1);
Chris Lattnerf7e22732018-06-22 22:03:48 -0700226 return Type::getI1(context);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700227 case Token::kw_i8:
228 consumeToken(Token::kw_i8);
Chris Lattnerf7e22732018-06-22 22:03:48 -0700229 return Type::getI8(context);
230 case Token::kw_i16:
231 consumeToken(Token::kw_i16);
232 return Type::getI16(context);
233 case Token::kw_i32:
234 consumeToken(Token::kw_i32);
235 return Type::getI32(context);
236 case Token::kw_i64:
237 consumeToken(Token::kw_i64);
238 return Type::getI64(context);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700239 case Token::kw_int:
240 consumeToken(Token::kw_int);
Chris Lattnerf7e22732018-06-22 22:03:48 -0700241 return Type::getInt(context);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700242 }
243}
244
245/// Parse the element type of a tensor or memref type.
246///
247/// element-type ::= primitive-type | vector-type
248///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700249Type *Parser::parseElementType() {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700250 if (curToken.is(Token::kw_vector))
251 return parseVectorType();
252
253 return parsePrimitiveType();
254}
255
256/// Parse a vector type.
257///
258/// vector-type ::= `vector` `<` const-dimension-list primitive-type `>`
259/// const-dimension-list ::= (integer-literal `x`)+
260///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700261VectorType *Parser::parseVectorType() {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700262 consumeToken(Token::kw_vector);
263
264 if (!consumeIf(Token::less))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700265 return (emitError("expected '<' in vector type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700266
267 if (curToken.isNot(Token::integer))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700268 return (emitError("expected dimension size in vector type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700269
270 SmallVector<unsigned, 4> dimensions;
271 while (curToken.is(Token::integer)) {
272 // Make sure this integer value is in bound and valid.
273 auto dimension = curToken.getUnsignedIntegerValue();
274 if (!dimension.hasValue())
Chris Lattnerf7e22732018-06-22 22:03:48 -0700275 return (emitError("invalid dimension in vector type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700276 dimensions.push_back(dimension.getValue());
277
278 consumeToken(Token::integer);
279
280 // Make sure we have an 'x' or something like 'xbf32'.
281 if (curToken.isNot(Token::bare_identifier) ||
282 curToken.getSpelling()[0] != 'x')
Chris Lattnerf7e22732018-06-22 22:03:48 -0700283 return (emitError("expected 'x' in vector dimension list"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700284
285 // If we had a prefix of 'x', lex the next token immediately after the 'x'.
286 if (curToken.getSpelling().size() != 1)
287 lex.resetPointer(curToken.getSpelling().data()+1);
288
289 // Consume the 'x'.
290 consumeToken(Token::bare_identifier);
291 }
292
293 // Parse the element type.
Chris Lattnerf7e22732018-06-22 22:03:48 -0700294 auto *elementType = parsePrimitiveType();
295 if (!elementType)
296 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700297
298 if (!consumeIf(Token::greater))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700299 return (emitError("expected '>' in vector type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700300
Chris Lattnerf7e22732018-06-22 22:03:48 -0700301 return VectorType::get(dimensions, elementType);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700302}
303
304/// Parse a dimension list of a tensor or memref type. This populates the
305/// dimension list, returning -1 for the '?' dimensions.
306///
307/// dimension-list-ranked ::= (dimension `x`)*
308/// dimension ::= `?` | integer-literal
309///
310ParseResult Parser::parseDimensionListRanked(SmallVectorImpl<int> &dimensions) {
311 while (curToken.isAny(Token::integer, Token::question)) {
312 if (consumeIf(Token::question)) {
313 dimensions.push_back(-1);
314 } else {
315 // Make sure this integer value is in bound and valid.
316 auto dimension = curToken.getUnsignedIntegerValue();
317 if (!dimension.hasValue() || (int)dimension.getValue() < 0)
318 return emitError("invalid dimension");
319 dimensions.push_back((int)dimension.getValue());
320 consumeToken(Token::integer);
321 }
322
323 // Make sure we have an 'x' or something like 'xbf32'.
324 if (curToken.isNot(Token::bare_identifier) ||
325 curToken.getSpelling()[0] != 'x')
326 return emitError("expected 'x' in dimension list");
327
328 // If we had a prefix of 'x', lex the next token immediately after the 'x'.
329 if (curToken.getSpelling().size() != 1)
330 lex.resetPointer(curToken.getSpelling().data()+1);
331
332 // Consume the 'x'.
333 consumeToken(Token::bare_identifier);
334 }
335
336 return ParseSuccess;
337}
338
339/// Parse a tensor type.
340///
341/// tensor-type ::= `tensor` `<` dimension-list element-type `>`
342/// dimension-list ::= dimension-list-ranked | `??`
343///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700344Type *Parser::parseTensorType() {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700345 consumeToken(Token::kw_tensor);
346
347 if (!consumeIf(Token::less))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700348 return (emitError("expected '<' in tensor type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700349
350 bool isUnranked;
351 SmallVector<int, 4> dimensions;
352
353 if (consumeIf(Token::questionquestion)) {
354 isUnranked = true;
355 } else {
356 isUnranked = false;
357 if (parseDimensionListRanked(dimensions))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700358 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700359 }
360
361 // Parse the element type.
Chris Lattnerf7e22732018-06-22 22:03:48 -0700362 auto elementType = parseElementType();
363 if (!elementType)
364 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700365
366 if (!consumeIf(Token::greater))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700367 return (emitError("expected '>' in tensor type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700368
MLIR Team355ec862018-06-23 18:09:09 -0700369 if (isUnranked)
370 return UnrankedTensorType::get(elementType);
371 return RankedTensorType::get(dimensions, elementType);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700372}
373
374/// Parse a memref type.
375///
376/// memref-type ::= `memref` `<` dimension-list-ranked element-type
377/// (`,` semi-affine-map-composition)? (`,` memory-space)? `>`
378///
379/// semi-affine-map-composition ::= (semi-affine-map `,` )* semi-affine-map
380/// memory-space ::= integer-literal /* | TODO: address-space-id */
381///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700382Type *Parser::parseMemRefType() {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700383 consumeToken(Token::kw_memref);
384
385 if (!consumeIf(Token::less))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700386 return (emitError("expected '<' in memref type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700387
388 SmallVector<int, 4> dimensions;
389 if (parseDimensionListRanked(dimensions))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700390 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700391
392 // Parse the element type.
Chris Lattnerf7e22732018-06-22 22:03:48 -0700393 auto elementType = parseElementType();
394 if (!elementType)
395 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700396
397 // TODO: Parse semi-affine-map-composition.
398 // TODO: Parse memory-space.
399
400 if (!consumeIf(Token::greater))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700401 return (emitError("expected '>' in memref type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700402
Chris Lattnerf7e22732018-06-22 22:03:48 -0700403 // FIXME: Add an IR representation for memref types.
404 return Type::getI1(context);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700405}
406
407
408
409/// Parse a function type.
410///
411/// function-type ::= type-list-parens `->` type-list
412///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700413Type *Parser::parseFunctionType() {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700414 assert(curToken.is(Token::l_paren));
415
Chris Lattnerf7e22732018-06-22 22:03:48 -0700416 SmallVector<Type*, 4> arguments;
417 if (parseTypeList(arguments))
418 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700419
420 if (!consumeIf(Token::arrow))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700421 return (emitError("expected '->' in function type"), nullptr);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700422
Chris Lattnerf7e22732018-06-22 22:03:48 -0700423 SmallVector<Type*, 4> results;
424 if (parseTypeList(results))
425 return nullptr;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700426
Chris Lattnerf7e22732018-06-22 22:03:48 -0700427 return FunctionType::get(arguments, results, context);
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700428}
429
430
431/// Parse an arbitrary type.
432///
433/// type ::= primitive-type
434/// | vector-type
435/// | tensor-type
436/// | memref-type
437/// | function-type
438/// element-type ::= primitive-type | vector-type
439///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700440Type *Parser::parseType() {
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700441 switch (curToken.getKind()) {
442 case Token::kw_memref: return parseMemRefType();
443 case Token::kw_tensor: return parseTensorType();
444 case Token::kw_vector: return parseVectorType();
445 case Token::l_paren: return parseFunctionType();
446 default:
447 return parsePrimitiveType();
448 }
449}
450
451/// Parse a "type list", which is a singular type, or a parenthesized list of
452/// types.
453///
454/// type-list ::= type-list-parens | type
455/// type-list-parens ::= `(` `)`
456/// | `(` type (`,` type)* `)`
457///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700458ParseResult Parser::parseTypeList(SmallVectorImpl<Type*> &elements) {
459 auto parseElt = [&]() -> ParseResult {
460 auto elt = parseType();
461 elements.push_back(elt);
462 return elt ? ParseSuccess : ParseFailure;
463 };
464
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700465 // If there is no parens, then it must be a singular type.
466 if (!consumeIf(Token::l_paren))
Chris Lattnerf7e22732018-06-22 22:03:48 -0700467 return parseElt();
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700468
Chris Lattnerf7e22732018-06-22 22:03:48 -0700469 if (parseCommaSeparatedList(Token::r_paren, parseElt))
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700470 return ParseFailure;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700471
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700472 return ParseSuccess;
473}
474
Chris Lattner4c95a502018-06-23 16:03:42 -0700475//===----------------------------------------------------------------------===//
MLIR Teamf85a6262018-06-27 11:03:08 -0700476// Polyhedral structures.
477//===----------------------------------------------------------------------===//
478
479/// Affine map declaration.
480///
481/// affine-map-def ::= affine-map-id `=` affine-map-inline
482/// affine-map-inline ::= dim-and-symbol-id-lists `->` multi-dim-affine-expr
483/// ( `size` `(` dim-size (`,` dim-size)* `)` )?
484/// dim-size ::= affine-expr | `min` `(` affine-expr ( `,` affine-expr)+ `)`
485///
486ParseResult Parser::parseAffineMapDef() {
487 assert(curToken.is(Token::affine_map_id));
488
489 StringRef affineMapId = curToken.getSpelling().drop_front();
490 // Check that 'affineMapId' is unique.
491 // TODO(andydavis) Add a unit test for this case.
492 if (affineMaps.count(affineMapId) > 0)
493 return emitError("encountered non-unique affine map id");
494
495 consumeToken(Token::affine_map_id);
496
497 // TODO(andydavis,bondhugula) Parse affine map definition.
498 affineMaps[affineMapId].reset(new AffineMap(1, 0));
499 return ParseSuccess;
500}
501
502//===----------------------------------------------------------------------===//
Chris Lattner4c95a502018-06-23 16:03:42 -0700503// Functions
504//===----------------------------------------------------------------------===//
Chris Lattnere79379a2018-06-22 10:39:19 -0700505
Chris Lattnere79379a2018-06-22 10:39:19 -0700506
507/// Parse a function signature, starting with a name and including the parameter
508/// list.
509///
510/// argument-list ::= type (`,` type)* | /*empty*/
511/// function-signature ::= function-id `(` argument-list `)` (`->` type-list)?
512///
Chris Lattnerf7e22732018-06-22 22:03:48 -0700513ParseResult Parser::parseFunctionSignature(StringRef &name,
514 FunctionType *&type) {
Chris Lattnere79379a2018-06-22 10:39:19 -0700515 if (curToken.isNot(Token::at_identifier))
516 return emitError("expected a function identifier like '@foo'");
517
518 name = curToken.getSpelling().drop_front();
519 consumeToken(Token::at_identifier);
520
521 if (curToken.isNot(Token::l_paren))
522 return emitError("expected '(' in function signature");
Chris Lattnere79379a2018-06-22 10:39:19 -0700523
Chris Lattnerf7e22732018-06-22 22:03:48 -0700524 SmallVector<Type*, 4> arguments;
525 if (parseTypeList(arguments))
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700526 return ParseFailure;
Chris Lattnere79379a2018-06-22 10:39:19 -0700527
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700528 // Parse the return type if present.
Chris Lattnerf7e22732018-06-22 22:03:48 -0700529 SmallVector<Type*, 4> results;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700530 if (consumeIf(Token::arrow)) {
Chris Lattnerf7e22732018-06-22 22:03:48 -0700531 if (parseTypeList(results))
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700532 return ParseFailure;
Chris Lattnerbb8fafc2018-06-22 15:52:02 -0700533 }
Chris Lattnerf7e22732018-06-22 22:03:48 -0700534 type = FunctionType::get(arguments, results, context);
Chris Lattnere79379a2018-06-22 10:39:19 -0700535 return ParseSuccess;
536}
537
Chris Lattnere79379a2018-06-22 10:39:19 -0700538/// External function declarations.
539///
540/// ext-func ::= `extfunc` function-signature
541///
542ParseResult Parser::parseExtFunc() {
543 consumeToken(Token::kw_extfunc);
544
545 StringRef name;
Chris Lattnerf7e22732018-06-22 22:03:48 -0700546 FunctionType *type = nullptr;
547 if (parseFunctionSignature(name, type))
Chris Lattnere79379a2018-06-22 10:39:19 -0700548 return ParseFailure;
549
550
551 // Okay, the external function definition was parsed correctly.
Chris Lattner4c95a502018-06-23 16:03:42 -0700552 module->functionList.push_back(new ExtFunction(name, type));
Chris Lattnere79379a2018-06-22 10:39:19 -0700553 return ParseSuccess;
554}
555
556
Chris Lattner4c95a502018-06-23 16:03:42 -0700557namespace {
558/// This class represents the transient parser state for the internals of a
559/// function as we are parsing it, e.g. the names for basic blocks. It handles
560/// forward references.
561class CFGFunctionParserState {
562public:
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700563 CFGFunction *function;
564 llvm::StringMap<std::pair<BasicBlock*, SMLoc>> blocksByName;
565
Chris Lattner4c95a502018-06-23 16:03:42 -0700566 CFGFunctionParserState(CFGFunction *function) : function(function) {}
567
568 /// Get the basic block with the specified name, creating it if it doesn't
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700569 /// already exist. The location specified is the point of use, which allows
570 /// us to diagnose references to blocks that are not defined precisely.
571 BasicBlock *getBlockNamed(StringRef name, SMLoc loc) {
572 auto &blockAndLoc = blocksByName[name];
573 if (!blockAndLoc.first) {
574 blockAndLoc.first = new BasicBlock(function);
575 blockAndLoc.second = loc;
Chris Lattner4c95a502018-06-23 16:03:42 -0700576 }
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700577 return blockAndLoc.first;
Chris Lattner4c95a502018-06-23 16:03:42 -0700578 }
Chris Lattner4c95a502018-06-23 16:03:42 -0700579};
580} // end anonymous namespace
581
582
583/// CFG function declarations.
584///
585/// cfg-func ::= `cfgfunc` function-signature `{` basic-block+ `}`
586///
587ParseResult Parser::parseCFGFunc() {
588 consumeToken(Token::kw_cfgfunc);
589
590 StringRef name;
591 FunctionType *type = nullptr;
592 if (parseFunctionSignature(name, type))
593 return ParseFailure;
594
595 if (!consumeIf(Token::l_brace))
596 return emitError("expected '{' in CFG function");
597
598 // Okay, the CFG function signature was parsed correctly, create the function.
599 auto function = new CFGFunction(name, type);
600
601 // Make sure we have at least one block.
602 if (curToken.is(Token::r_brace))
603 return emitError("CFG functions must have at least one basic block");
604
605 CFGFunctionParserState functionState(function);
606
607 // Parse the list of blocks.
608 while (!consumeIf(Token::r_brace))
609 if (parseBasicBlock(functionState))
610 return ParseFailure;
611
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700612 // Verify that all referenced blocks were defined. Iteration over a
613 // StringMap isn't determinstic, but this is good enough for our purposes.
614 for (auto &elt : functionState.blocksByName) {
615 auto *bb = elt.second.first;
616 if (!bb->getTerminator())
617 return emitError(elt.second.second,
618 "reference to an undefined basic block '" +
619 elt.first() + "'");
620 }
621
Chris Lattner4c95a502018-06-23 16:03:42 -0700622 module->functionList.push_back(function);
623 return ParseSuccess;
624}
625
626/// Basic block declaration.
627///
628/// basic-block ::= bb-label instruction* terminator-stmt
629/// bb-label ::= bb-id bb-arg-list? `:`
630/// bb-id ::= bare-id
631/// bb-arg-list ::= `(` ssa-id-and-type-list? `)`
632///
633ParseResult Parser::parseBasicBlock(CFGFunctionParserState &functionState) {
634 SMLoc nameLoc = curToken.getLoc();
635 auto name = curToken.getSpelling();
636 if (!consumeIf(Token::bare_identifier))
637 return emitError("expected basic block name");
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700638
639 auto block = functionState.getBlockNamed(name, nameLoc);
Chris Lattner4c95a502018-06-23 16:03:42 -0700640
641 // If this block has already been parsed, then this is a redefinition with the
642 // same block name.
643 if (block->getTerminator())
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700644 return emitError(nameLoc, "redefinition of block '" + name.str() + "'");
645
646 // References to blocks can occur in any order, but we need to reassemble the
647 // function in the order that occurs in the source file. Do this by moving
648 // each block to the end of the list as it is defined.
649 // FIXME: This is inefficient for large functions given that blockList is a
650 // vector. blockList will eventually be an ilist, which will make this fast.
651 auto &blockList = functionState.function->blockList;
652 if (blockList.back() != block) {
653 auto it = std::find(blockList.begin(), blockList.end(), block);
654 assert(it != blockList.end() && "Block has to be in the blockList");
655 std::swap(*it, blockList.back());
656 }
Chris Lattner4c95a502018-06-23 16:03:42 -0700657
658 // TODO: parse bb argument list.
659
660 if (!consumeIf(Token::colon))
661 return emitError("expected ':' after basic block name");
662
663
664 // TODO(clattner): Verify block hasn't already been parsed (this would be a
665 // redefinition of the same name) once we have a body implementation.
666
667 // TODO(clattner): Move block to the end of the list, once we have a proper
668 // block list representation in CFGFunction.
669
670 // TODO: parse instruction list.
671
672 // TODO: Generalize this once instruction list parsing is built out.
Chris Lattner4c95a502018-06-23 16:03:42 -0700673
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700674 auto *termInst = parseTerminator(block, functionState);
675 if (!termInst)
676 return ParseFailure;
677 block->setTerminator(termInst);
Chris Lattner4c95a502018-06-23 16:03:42 -0700678
679 return ParseSuccess;
680}
681
682
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700683/// Parse the terminator instruction for a basic block.
684///
685/// terminator-stmt ::= `br` bb-id branch-use-list?
686/// branch-use-list ::= `(` ssa-use-and-type-list? `)`
687/// terminator-stmt ::=
688/// `cond_br` ssa-use `,` bb-id branch-use-list? `,` bb-id branch-use-list?
689/// terminator-stmt ::= `return` ssa-use-and-type-list?
690///
691TerminatorInst *Parser::parseTerminator(BasicBlock *currentBB,
692 CFGFunctionParserState &functionState) {
693 switch (curToken.getKind()) {
694 default:
695 return (emitError("expected terminator at end of basic block"), nullptr);
696
697 case Token::kw_return:
698 consumeToken(Token::kw_return);
699 return new ReturnInst(currentBB);
700
701 case Token::kw_br: {
702 consumeToken(Token::kw_br);
703 auto destBB = functionState.getBlockNamed(curToken.getSpelling(),
704 curToken.getLoc());
705 if (!consumeIf(Token::bare_identifier))
706 return (emitError("expected basic block name"), nullptr);
707 return new BranchInst(destBB, currentBB);
708 }
709 }
710}
711
Tatiana Shpeismanc96b5872018-06-28 17:02:32 -0700712/// ML function declarations.
713///
714/// ml-func ::= `mlfunc` ml-func-signature `{` ml-stmt* ml-return-stmt `}`
715///
716ParseResult Parser::parseMLFunc() {
717 consumeToken(Token::kw_mlfunc);
718
719 StringRef name;
720 FunctionType *type = nullptr;
721
722 // FIXME: Parse ML function signature (args + types)
723 // by passing pointer to SmallVector<identifier> into parseFunctionSignature
724 if (parseFunctionSignature(name, type))
725 return ParseFailure;
726
727 if (!consumeIf(Token::l_brace))
728 return emitError("expected '{' in ML function");
729
730 // Okay, the ML function signature was parsed correctly, create the function.
731 auto function = new MLFunction(name, type);
732
733 // Make sure we have at least one statement.
734 if (curToken.is(Token::r_brace))
735 return emitError("ML function must end with return statement");
736
737 // Parse the list of instructions.
738 while (!consumeIf(Token::kw_return)) {
739 auto *stmt = parseMLStatement(function);
740 if (!stmt)
741 return ParseFailure;
742 function->stmtList.push_back(stmt);
743 }
744
745 // TODO: parse return statement operands
746 if (!consumeIf(Token::r_brace))
747 emitError("expected '}' in ML function");
748
749 module->functionList.push_back(function);
750
751 return ParseSuccess;
752}
753
754/// Parse an MLStatement
755/// TODO
756///
757MLStatement *Parser::parseMLStatement(MLFunction *currentFunction) {
758 switch (curToken.getKind()) {
759 default:
760 return (emitError("expected ML statement"), nullptr);
761
762 // TODO: add parsing of ML statements
763 }
764}
Chris Lattnerf6d80a02018-06-24 11:18:29 -0700765
Chris Lattner4c95a502018-06-23 16:03:42 -0700766//===----------------------------------------------------------------------===//
767// Top-level entity parsing.
768//===----------------------------------------------------------------------===//
769
Chris Lattnere79379a2018-06-22 10:39:19 -0700770/// This is the top-level module parser.
771Module *Parser::parseModule() {
772 while (1) {
773 switch (curToken.getKind()) {
774 default:
775 emitError("expected a top level entity");
776 return nullptr;
777
778 // If we got to the end of the file, then we're done.
779 case Token::eof:
780 return module.release();
781
782 // If we got an error token, then the lexer already emitted an error, just
783 // stop. Someday we could introduce error recovery if there was demand for
784 // it.
785 case Token::error:
786 return nullptr;
787
788 case Token::kw_extfunc:
Chris Lattner4c95a502018-06-23 16:03:42 -0700789 if (parseExtFunc()) return nullptr;
Chris Lattnere79379a2018-06-22 10:39:19 -0700790 break;
791
Chris Lattner4c95a502018-06-23 16:03:42 -0700792 case Token::kw_cfgfunc:
793 if (parseCFGFunc()) return nullptr;
794 break;
MLIR Teamf85a6262018-06-27 11:03:08 -0700795 case Token::affine_map_id:
796 if (parseAffineMapDef()) return nullptr;
797 break;
Chris Lattner4c95a502018-06-23 16:03:42 -0700798
Tatiana Shpeismanc96b5872018-06-28 17:02:32 -0700799 case Token::kw_mlfunc:
800 if (parseMLFunc()) return nullptr;
801 break;
802
803 // TODO: affine entity declarations, etc.
Chris Lattnere79379a2018-06-22 10:39:19 -0700804 }
805 }
806}
807
808//===----------------------------------------------------------------------===//
809
810/// This parses the file specified by the indicated SourceMgr and returns an
811/// MLIR module if it was valid. If not, it emits diagnostics and returns null.
Jacques Pienaar9c411be2018-06-24 19:17:35 -0700812Module *mlir::parseSourceFile(llvm::SourceMgr &sourceMgr, MLIRContext *context,
813 const SMDiagnosticHandlerTy &errorReporter) {
814 return Parser(sourceMgr, context, errorReporter).parseModule();
Chris Lattnere79379a2018-06-22 10:39:19 -0700815}