 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
49.7% |
221 / 445 |
| Generated: |
2009-05-17 22:47 |
|
Branches Executed: |
79.3% |
353 / 445 |
| |
|
Line Coverage: |
65.2% |
380 / 583 |
| |
 |
|
 |
1 : //===- Parser.cpp - --*- C++ -*-===//
2 :
3 : #include "expr/Parser.h"
4 :
5 : #include "expr/Lexer.h"
6 :
7 : #include "klee/Constraints.h"
8 :
9 : // FIXME: This should not be here.
10 : #include "klee/Memory.h"
11 : #include "klee/Solver.h"
12 : #include "klee/util/ExprPPrinter.h"
13 :
14 : #include "llvm/ADT/APInt.h"
15 : #include "llvm/Support/MemoryBuffer.h"
16 : #include "llvm/Support/Streams.h"
17 :
18 : #include <cassert>
19 : #include <iostream>
20 : #include <map>
21 :
22 : using namespace llvm;
23 : using namespace klee;
24 : using namespace klee::expr;
25 :
26 : // FIXME: This is a complete and total hack.
27 : #include "klee/Memory.h"
28 : int MemoryObject::counter;
29 :
30 : namespace {
31 : /// ParseResult - Represent a possibly invalid parse result.
32 : template<typename T>
33 11636: struct ParseResult {
34 : bool IsValid;
35 : T Value;
36 :
37 : public:
38 2581: ParseResult() : IsValid(false) {}
39 2775: ParseResult(T _Value) : IsValid(true), Value(_Value) {}
40 0: ParseResult(bool _IsValid, T _Value) : IsValid(_IsValid), Value(_Value) {}
41 :
42 : bool isValid() {
43 4251: return IsValid;
44 : }
45 3951: T get() {
0: branch 0 not taken
906: branch 1 taken
0: branch 3 not taken
2733: branch 4 taken
0: branch 6 not taken
18: branch 7 taken
0: branch 9 not taken
294: branch 10 taken
46 3951: assert(IsValid && "get() on invalid ParseResult!");
47 3951: return Value;
48 : }
49 : };
50 :
51 : typedef ParseResult<Decl*> DeclResult;
52 : typedef ParseResult<ExprHandle> ExprResult;
53 : typedef ParseResult<Expr::Width> TypeResult;
54 : typedef ParseResult<VersionHandle> VersionResult;
55 :
56 : /// NumberOrExprResult - Represent a number or expression. This is used to
57 : /// wrap an expression production which may be a number, but for
58 : /// which the type width is unknown.
59 9502: class NumberOrExprResult {
60 : Token AsNumber;
61 : ExprResult AsExpr;
62 : bool IsNumber;
63 :
64 : public:
65 : NumberOrExprResult() : IsNumber(false) {}
66 : explicit NumberOrExprResult(Token _AsNumber) : AsNumber(_AsNumber),
67 1566: IsNumber(true) {}
68 : explicit NumberOrExprResult(ExprResult _AsExpr) : AsExpr(_AsExpr),
69 362: IsNumber(false) {}
70 :
71 964: bool isNumber() const { return IsNumber; }
72 783: const Token &getNumber() const {
0: branch 0 not taken
783: branch 1 taken
73 783: assert(IsNumber && "Invalid accessor call.");
74 783: return AsNumber;
75 : }
76 181: const ExprResult &getExpr() const {
0: branch 0 not taken
181: branch 1 taken
77 181: assert(!IsNumber && "Invalid accessor call.");
78 181: return AsExpr;
79 : }
80 : };
81 :
82 : /// ParserImpl - Parser implementation.
2: branch 3 taken
0: branch 4 not taken
0: branch 9 not taken
0: branch 10 not taken
83 10: class ParserImpl : public Parser {
84 : typedef std::map<const std::string, const Identifier*> IdentifierTabTy;
85 : typedef std::map<const Identifier*, ExprHandle> ExprSymTabTy;
86 : typedef std::map<const Identifier*, VersionHandle> VersionSymTabTy;
87 :
88 : const std::string Filename;
89 : const MemoryBuffer *TheMemoryBuffer;
90 : Lexer TheLexer;
91 : unsigned MaxErrors;
92 : unsigned NumErrors;
93 :
94 : // FIXME: Use LLVM symbol tables?
95 : IdentifierTabTy IdentifierTab;
96 :
97 : std::map<const Identifier*, const ArrayDecl*> ArraySymTab;
98 : ExprSymTabTy ExprSymTab;
99 : VersionSymTabTy VersionSymTab;
100 :
101 : /// Tok - The currently lexed token.
102 : Token Tok;
103 :
104 : /// ParenLevel - The current depth of matched '(' tokens.
105 : unsigned ParenLevel;
106 : /// SquareLevel - The current depth of matched '[' tokens.
107 : unsigned SquareLevel;
108 :
109 : /* Core parsing functionality */
110 :
111 : const Identifier *GetOrCreateIdentifier(const Token &Tok);
112 :
113 : void GetNextNonCommentToken() {
55: branch 0 taken
1510: branch 1 taken
4: branch 2 taken
2903: branch 3 taken
114 4472: do {
115 4472: TheLexer.Lex(Tok);
116 : } while (Tok.kind == Token::Comment);
117 : }
118 :
119 : /// ConsumeToken - Consume the current 'peek token' and lex the next one.
120 2903: void ConsumeToken() {
0: branch 0 not taken
2903: branch 1 taken
121 2903: assert(Tok.kind != Token::LParen && Tok.kind != Token::RParen);
122 : GetNextNonCommentToken();
123 2903: }
124 :
125 : /// ConsumeExpectedToken - Check that the current token is of the
126 : /// expected kind and consume it.
127 1510: void ConsumeExpectedToken(Token::Kind k) {
0: branch 0 not taken
1510: branch 1 taken
128 1510: assert(Tok.kind == k && "Unexpected token!");
129 : GetNextNonCommentToken();
130 1510: }
131 :
132 : void ConsumeLParen() {
133 647: ++ParenLevel;
134 647: ConsumeExpectedToken(Token::LParen);
135 : }
136 :
137 647: void ConsumeRParen() {
647: branch 0 taken
0: branch 1 not taken
138 647: if (ParenLevel) // Cannot go below zero.
139 647: --ParenLevel;
140 647: ConsumeExpectedToken(Token::RParen);
141 647: }
142 :
143 : void ConsumeLSquare() {
144 13: ++SquareLevel;
145 13: ConsumeExpectedToken(Token::LSquare);
146 : }
147 :
148 31: void ConsumeRSquare() {
13: branch 0 taken
18: branch 1 taken
149 31: if (SquareLevel) // Cannot go below zero.
150 13: --SquareLevel;
151 31: ConsumeExpectedToken(Token::RSquare);
152 31: }
153 :
154 2: void ConsumeAnyToken() {
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
2: branch 4 taken
155 2: switch (Tok.kind) {
156 : case Token::LParen: return ConsumeLParen();
157 0: case Token::RParen: return ConsumeRParen();
158 : case Token::LSquare: return ConsumeLSquare();
159 0: case Token::RSquare: return ConsumeRSquare();
160 : default:
161 2: return ConsumeToken();
162 : }
163 : }
164 :
165 : /* Utility functions */
166 :
167 : /// SkipUntilRParen - Scan forward to the next token following an
168 : /// rparen at the given level, or EOF, whichever is first.
169 0: void SkipUntilRParen(unsigned Level) {
170 : // FIXME: I keep wavering on whether it is an error to call this
171 : // with the current token an rparen. In most cases this should
172 : // have been handled differently (error reported,
173 : // whatever). Audit & resolve.
174 : assert(Level <= ParenLevel &&
0: branch 0 not taken
0: branch 1 not taken
175 0: "Refusing to skip until rparen at higher level.");
0: branch 0 not taken
0: branch 1 not taken
176 0: while (Tok.kind != Token::EndOfFile) {
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
177 0: if (Tok.kind == Token::RParen && ParenLevel == Level) {
178 0: ConsumeRParen();
179 0: break;
180 : }
181 0: ConsumeAnyToken();
182 : }
183 0: }
184 :
185 : /// SkipUntilRParen - Scan forward until reaching an rparen token
186 : /// at the current level (or EOF).
187 : void SkipUntilRParen() {
188 0: SkipUntilRParen(ParenLevel);
189 : }
190 :
191 : /// ExpectRParen - Utility method to close an sexp. This expects to
192 : /// eat an rparen, and emits a diagnostic and skips to the next one
193 : /// (or EOF) if it cannot.
194 510: void ExpectRParen(const char *Msg) {
0: branch 0 not taken
510: branch 1 taken
195 510: if (Tok.kind == Token::EndOfFile) {
196 : // FIXME: Combine with Msg
197 0: Error("expected ')' but found end-of-file.", Tok);
0: branch 0 not taken
510: branch 1 taken
198 510: } else if (Tok.kind != Token::RParen) {
199 0: Error(Msg, Tok);
200 : SkipUntilRParen();
201 : } else {
202 510: ConsumeRParen();
203 : }
204 510: }
205 :
206 : /// SkipUntilRSquare - Scan forward to the next token following an
207 : /// rsquare at the given level, or EOF, whichever is first.
208 0: void SkipUntilRSquare(unsigned Level) {
209 : // FIXME: I keep wavering on whether it is an error to call this
210 : // with the current token an rparen. In most cases this should
211 : // have been handled differently (error reported,
212 : // whatever). Audit & resolve.
213 : assert(Level <= ParenLevel &&
0: branch 0 not taken
0: branch 1 not taken
214 0: "Refusing to skip until rparen at higher level.");
0: branch 0 not taken
0: branch 1 not taken
215 0: while (Tok.kind != Token::EndOfFile) {
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
216 0: if (Tok.kind == Token::RSquare && ParenLevel == Level) {
217 0: ConsumeRSquare();
218 0: break;
219 : }
220 0: ConsumeAnyToken();
221 : }
222 0: }
223 :
224 : /// SkipUntilRSquare - Scan forward until reaching an rsquare token
225 : /// at the current level (or EOF).
226 : void SkipUntilRSquare() {
227 0: SkipUntilRSquare(ParenLevel);
228 : }
229 :
230 : /// ExpectRSquare - Utility method to close an array. This expects
231 : /// to eat an rparen, and emits a diagnostic and skips to the next
232 : /// one (or EOF) if it cannot.
233 : void ExpectRSquare(const char *Msg) {
0: branch 0 not taken
13: branch 1 taken
234 13: if (Tok.kind == Token::EndOfFile) {
235 : // FIXME: Combine with Msg
236 0: Error("expected ']' but found end-of-file.", Tok);
0: branch 0 not taken
13: branch 1 taken
237 13: } else if (Tok.kind != Token::RSquare) {
238 0: Error(Msg, Tok);
239 : SkipUntilRSquare();
240 : } else {
241 13: ConsumeRSquare();
242 : }
243 : }
244 :
245 : /*** Grammar productions ****/
246 :
247 : /* Top level decls */
248 :
249 : DeclResult ParseArrayDecl();
250 : DeclResult ParseExprVarDecl();
251 : DeclResult ParseVersionVarDecl();
252 : DeclResult ParseCommandDecl();
253 :
254 : /* Commands */
255 :
256 : DeclResult ParseQueryCommand();
257 :
258 : /* Etc. */
259 :
260 : NumberOrExprResult ParseNumberOrExpr();
261 :
262 : ExprResult ParseExpr(TypeResult ExpectedType);
263 : ExprResult ParseParenExpr(TypeResult ExpectedType);
264 : ExprResult ParseUnaryParenExpr(const Token &Name,
265 : unsigned Kind, bool IsFixed,
266 : Expr::Width ResTy);
267 : ExprResult ParseBinaryParenExpr(const Token &Name,
268 : unsigned Kind, bool IsFixed,
269 : Expr::Width ResTy);
270 : ExprResult ParseSelectParenExpr(const Token &Name, Expr::Width ResTy);
271 : ExprResult ParseConcatParenExpr(const Token &Name, Expr::Width ResTy);
272 : ExprResult ParseExtractParenExpr(const Token &Name, Expr::Width ResTy);
273 : ExprResult ParseAnyReadParenExpr(const Token &Name,
274 : unsigned Kind,
275 : Expr::Width ResTy);
276 : void ParseMatchedBinaryArgs(const Token &Name,
277 : TypeResult ExpectType,
278 : ExprResult &LHS, ExprResult &RHS);
279 : ExprResult ParseNumber(Expr::Width Width);
280 : ExprResult ParseNumberToken(Expr::Width Width, const Token &Tok);
281 :
282 : VersionResult ParseVersionSpecifier();
283 : VersionResult ParseVersion();
284 :
285 : TypeResult ParseTypeSpecifier();
286 :
287 : /*** Diagnostics ***/
288 :
289 : void Error(const char *Message, const Token &At);
290 0: void Error(const char *Message) { Error(Message, Tok); }
291 :
292 : public:
293 : ParserImpl(const std::string _Filename,
294 : const MemoryBuffer *MB) : Filename(_Filename),
295 : TheMemoryBuffer(MB),
296 : TheLexer(MB),
297 : MaxErrors(~0u),
298 8: NumErrors(0) {}
299 :
300 : /// Initialize - Initialize the parsing state. This must be called
301 : /// prior to the start of parsing.
302 : void Initialize() {
303 2: ParenLevel = SquareLevel = 0;
304 :
305 2: ConsumeAnyToken();
306 : }
307 :
308 : /* Parser interface implementation */
309 :
310 : virtual Decl *ParseTopLevelDecl();
311 :
312 2: virtual void SetMaxErrors(unsigned N) {
313 2: MaxErrors = N;
314 2: }
315 :
316 20: virtual unsigned GetNumErrors() const {
317 20: return NumErrors;
318 : }
319 : };
320 : }
321 :
322 386: const Identifier *ParserImpl::GetOrCreateIdentifier(const Token &Tok) {
323 : // FIXME: Make not horribly inefficient please.
0: branch 0 not taken
386: branch 1 taken
324 386: assert(Tok.kind == Token::Identifier && "Expected only identifier tokens.");
325 386: std::string Name(Tok.start, Tok.length);
326 386: IdentifierTabTy::iterator it = IdentifierTab.find(Name);
350: branch 0 taken
36: branch 1 taken
327 772: if (it != IdentifierTab.end())
328 350: return it->second;
329 :
330 72: Identifier *I = new Identifier(Name);
331 144: IdentifierTab.insert(std::make_pair(Name, I));
332 :
333 36: return I;
334 : }
335 :
336 20: Decl *ParserImpl::ParseTopLevelDecl() {
337 : // Repeat until success or EOF.
18: branch 0 taken
2: branch 1 taken
338 40: while (Tok.kind != Token::EndOfFile) {
339 : // Only handle commands for now.
18: branch 0 taken
0: branch 1 not taken
340 18: if (Tok.kind == Token::LParen) {
341 18: DeclResult Res = ParseCommandDecl();
18: branch 0 taken
0: branch 1 not taken
342 18: if (Res.isValid())
343 18: return Res.get();
344 : } else {
345 : Error("expected '(' token.");
346 0: ConsumeAnyToken();
347 : }
348 : }
349 :
350 2: return 0;
351 : }
352 :
353 : /// ParseCommandDecl - Parse a command declaration. The lexer should
354 : /// be positioned at the opening '('.
355 : ///
356 : /// command = '(' name ... ')'
357 18: DeclResult ParserImpl::ParseCommandDecl() {
358 : ConsumeLParen();
359 :
0: branch 0 not taken
18: branch 1 taken
360 36: if (!Tok.isKeyword()) {
361 : Error("malformed command.");
362 : SkipUntilRParen();
363 0: return DeclResult();
364 : }
365 :
18: branch 0 taken
0: branch 1 not taken
366 18: switch (Tok.kind) {
367 : case Token::KWQuery:
368 18: return ParseQueryCommand();
369 :
370 : default:
371 : Error("malformed command (unexpected keyword).");
372 : SkipUntilRParen();
373 0: return DeclResult();
374 : }
375 : }
376 :
377 : /// ParseQueryCommand - Parse query command. The lexer should be
378 : /// positioned at the 'query' keyword.
379 : ///
380 : /// 'query' expressions-list expression [expression-list [array-list]]
381 18: DeclResult ParserImpl::ParseQueryCommand() {
382 : // FIXME: We need a command for this. Or something.
383 18: ExprSymTab.clear();
384 18: VersionSymTab.clear();
385 :
386 : std::vector<ExprHandle> Constraints;
387 18: ConsumeExpectedToken(Token::KWQuery);
0: branch 0 not taken
18: branch 1 taken
388 18: if (Tok.kind != Token::LSquare) {
389 : Error("malformed query, expected constraint list.");
390 : SkipUntilRParen();
391 : return DeclResult();
392 : }
393 :
394 18: ConsumeExpectedToken(Token::LSquare);
395 : // FIXME: Should avoid reading past unbalanced parens here.
64: branch 0 taken
18: branch 1 taken
396 100: while (Tok.kind != Token::RSquare) {
0: branch 0 not taken
64: branch 1 taken
397 64: if (Tok.kind == Token::EndOfFile) {
398 : Error("unexpected end of file.");
399 : return new QueryCommand(Constraints.begin(), Constraints.end(),
400 0: ref<Expr>(false, Expr::Bool));
401 : }
402 :
403 64: ExprResult Res = ParseExpr(TypeResult(Expr::Bool));
64: branch 0 taken
0: branch 1 not taken
404 64: if (Res.isValid())
405 64: Constraints.push_back(Res.get());
406 : }
407 :
408 18: ConsumeRSquare();
409 :
410 18: ExprResult Res = ParseExpr(TypeResult());
0: branch 0 not taken
18: branch 1 taken
411 18: if (!Res.isValid()) // Error emitted by ParseExpr.
412 0: Res = ExprResult(ref<Expr>(0, Expr::Bool));
413 :
414 18: ExpectRParen("unexpected argument to 'query'.");
415 : return new QueryCommand(Constraints.begin(), Constraints.end(),
416 54: Res.get());
417 : }
418 :
419 : /// ParseNumberOrExpr - Parse an expression whose type cannot be
420 : /// predicted.
421 964: NumberOrExprResult ParserImpl::ParseNumberOrExpr() {
783: branch 0 taken
181: branch 1 taken
422 964: if (Tok.kind == Token::Number){
423 783: Token Num = Tok;
424 783: ConsumeToken();
425 783: return NumberOrExprResult(Num);
426 : } else {
427 362: return NumberOrExprResult(ParseExpr(TypeResult()));
428 : }
429 : }
430 :
431 : /// ParseExpr - Parse an expression with the given \arg
432 : /// ExpectedType. \arg ExpectedType can be invalid if the type cannot
433 : /// be inferred from the context.
434 : ///
435 : /// expr = false | true
436 : /// expr = <constant>
437 : /// expr = <identifier>
438 : /// expr = [<identifier>:] paren-expr
439 843: ExprResult ParserImpl::ParseExpr(TypeResult ExpectedType) {
440 : // FIXME: Is it right to need to do this here?
0: branch 0 not taken
843: branch 1 taken
441 843: if (Tok.kind == Token::EndOfFile) {
442 : Error("unexpected end of file.");
443 0: return ExprResult();
444 : }
445 :
2: branch 0 taken
841: branch 1 taken
446 843: if (Tok.kind == Token::KWFalse || Tok.kind == Token::KWTrue) {
447 2: bool Value = Tok.kind == Token::KWTrue;
448 2: ConsumeToken();
449 4: return ExprResult(ref<Expr>(Value, Expr::Bool));
450 : }
451 :
99: branch 0 taken
742: branch 1 taken
452 841: if (Tok.kind == Token::Number) {
0: branch 0 not taken
99: branch 1 taken
453 99: if (!ExpectedType.isValid()) {
454 : Error("cannot infer type of number.");
455 0: ConsumeToken();
456 0: return ExprResult();
457 : }
458 :
459 99: return ParseNumber(ExpectedType.get());
460 : }
461 :
462 742: const Identifier *Label = 0;
166: branch 0 taken
576: branch 1 taken
463 742: if (Tok.kind == Token::Identifier) {
464 166: Token LTok = Tok;
465 166: Label = GetOrCreateIdentifier(Tok);
466 166: ConsumeToken();
467 :
113: branch 0 taken
53: branch 1 taken
468 166: if (Tok.kind != Token::Colon) {
469 113: ExprSymTabTy::iterator it = ExprSymTab.find(Label);
470 :
0: branch 0 not taken
113: branch 1 taken
471 226: if (it == ExprSymTab.end()) {
472 0: Error("invalid expression label reference.", LTok);
473 0: return ExprResult();
474 : }
475 :
476 339: return it->second;
477 : }
478 :
479 53: ConsumeToken();
0: branch 0 not taken
53: branch 1 taken
480 106: if (ExprSymTab.count(Label)) {
481 0: Error("duplicate expression label definition.", LTok);
482 0: Label = 0;
483 : }
484 : }
485 :
486 629: Token Start = Tok;
487 629: ExprResult Res = ParseParenExpr(ExpectedType);
0: branch 0 not taken
629: branch 1 taken
488 629: if (!Res.isValid()) {
489 : // If we know the type, define the identifier just so we don't get
490 : // use-of-undef errors.
491 : // FIXME: Maybe we should let the symbol table map to invalid
492 : // entries?
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
493 0: if (Label && ExpectedType.isValid())
494 : ExprSymTab.insert(std::make_pair(Label,
495 0: ref<Expr>(0, ExpectedType.get())));
496 0: return Res;
178: branch 0 taken
451: branch 1 taken
497 629: } else if (ExpectedType.isValid()) {
498 : // Type check result.
0: branch 4 not taken
178: branch 5 taken
499 178: if (Res.get().getWidth() != ExpectedType.get()) {
500 : // FIXME: Need more info, and range
501 0: Error("expression has incorrect type.", Start);
502 0: return ExprResult();
503 : }
504 : }
505 :
53: branch 0 taken
576: branch 1 taken
506 629: if (Label)
507 159: ExprSymTab.insert(std::make_pair(Label, Res.get()));
508 629: return Res;
509 : }
510 :
511 : // Additional kinds for macro forms.
512 : enum MacroKind {
513 : eMacroKind_Not = Expr::LastKind + 1, // false == x
514 : eMacroKind_Neg, // 0 - x
515 : eMacroKind_ReadLSB, // Multibyte read
516 : eMacroKind_ReadMSB, // Multibyte write
517 : eMacroKind_Concat, // Magic concatenation syntax
518 : eMacroKind_LastMacroKind = eMacroKind_ReadMSB
519 : };
520 :
521 : /// LookupExprInfo - Return information on the named token, if it is
522 : /// recognized.
523 : ///
524 : /// \param Kind [out] - The Expr::Kind or MacroKind of the identifier.
525 : /// \param IsFixed [out] - True if the given kinds result and
526 : /// (expression) arguments are all of the same width.
527 : /// \param NumArgs [out] - The number of expression arguments for this
528 : /// kind. -1 indicates the kind is variadic or has non-expression
529 : /// arguments.
530 : /// \return True if the token is a valid kind or macro name.
531 : static bool LookupExprInfo(const Token &Tok, unsigned &Kind,
532 624: bool &IsFixed, int &NumArgs) {
533 : #define SetOK(kind, isfixed, numargs) (Kind=kind, IsFixed=isfixed,\
534 : NumArgs=numargs, true)
0: branch 0 not taken
624: branch 1 taken
535 624: assert(Tok.kind == Token::Identifier && "Unexpected token.");
536 :
52: branch 0 taken
183: branch 1 taken
159: branch 2 taken
137: branch 3 taken
93: branch 4 taken
0: branch 5 not taken
537 624: switch (Tok.length) {
538 : case 2:
49: branch 1 taken
3: branch 2 taken
539 52: if (memcmp(Tok.start, "Eq", 2) == 0)
540 49: return SetOK(Expr::Eq, false, 2);
0: branch 1 not taken
3: branch 2 taken
541 3: if (memcmp(Tok.start, "Ne", 2) == 0)
542 0: return SetOK(Expr::Ne, false, 2);
543 :
3: branch 1 taken
0: branch 2 not taken
544 3: if (memcmp(Tok.start, "Or", 2) == 0)
545 3: return SetOK(Expr::Or, true, 2);
546 : break;
547 :
548 : case 3:
34: branch 1 taken
149: branch 2 taken
549 183: if (memcmp(Tok.start, "Add", 3) == 0)
550 34: return SetOK(Expr::Add, true, 2);
0: branch 1 not taken
149: branch 2 taken
551 149: if (memcmp(Tok.start, "Sub", 3) == 0)
552 0: return SetOK(Expr::Sub, true, 2);
17: branch 1 taken
132: branch 2 taken
553 149: if (memcmp(Tok.start, "Mul", 3) == 0)
554 17: return SetOK(Expr::Mul, true, 2);
555 :
27: branch 1 taken
105: branch 2 taken
556 132: if (memcmp(Tok.start, "And", 3) == 0)
557 27: return SetOK(Expr::And, true, 2);
0: branch 1 not taken
105: branch 2 taken
558 105: if (memcmp(Tok.start, "Shl", 3) == 0)
559 0: return SetOK(Expr::Shl, true, 2);
0: branch 1 not taken
105: branch 2 taken
560 105: if (memcmp(Tok.start, "Xor", 3) == 0)
561 0: return SetOK(Expr::Xor, true, 2);
562 :
52: branch 1 taken
53: branch 2 taken
563 105: if (memcmp(Tok.start, "Not", 3) == 0)
564 52: return SetOK(eMacroKind_Not, true, 1);
0: branch 1 not taken
53: branch 2 taken
565 53: if (memcmp(Tok.start, "Neg", 3) == 0)
566 0: return SetOK(eMacroKind_Neg, true, 1);
48: branch 1 taken
5: branch 2 taken
567 53: if (memcmp(Tok.start, "Ult", 3) == 0)
568 48: return SetOK(Expr::Ult, false, 2);
0: branch 1 not taken
5: branch 2 taken
569 5: if (memcmp(Tok.start, "Ule", 3) == 0)
570 0: return SetOK(Expr::Ule, false, 2);
0: branch 1 not taken
5: branch 2 taken
571 5: if (memcmp(Tok.start, "Ugt", 3) == 0)
572 0: return SetOK(Expr::Ugt, false, 2);
0: branch 1 not taken
5: branch 2 taken
573 5: if (memcmp(Tok.start, "Uge", 3) == 0)
574 0: return SetOK(Expr::Uge, false, 2);
5: branch 1 taken
0: branch 2 not taken
575 5: if (memcmp(Tok.start, "Slt", 3) == 0)
576 5: return SetOK(Expr::Slt, false, 2);
0: branch 1 not taken
0: branch 2 not taken
577 0: if (memcmp(Tok.start, "Sle", 3) == 0)
578 0: return SetOK(Expr::Sle, false, 2);
0: branch 1 not taken
0: branch 2 not taken
579 0: if (memcmp(Tok.start, "Sgt", 3) == 0)
580 0: return SetOK(Expr::Sgt, false, 2);
0: branch 1 not taken
0: branch 2 not taken
581 0: if (memcmp(Tok.start, "Sge", 3) == 0)
582 0: return SetOK(Expr::Sge, false, 2);
583 : break;
584 :
585 : case 4:
151: branch 1 taken
8: branch 2 taken
586 159: if (memcmp(Tok.start, "Read", 4) == 0)
587 151: return SetOK(Expr::Read, true, -1);
0: branch 1 not taken
8: branch 2 taken
588 8: if (memcmp(Tok.start, "AShr", 4) == 0)
589 0: return SetOK(Expr::AShr, true, 2);
0: branch 1 not taken
8: branch 2 taken
590 8: if (memcmp(Tok.start, "LShr", 4) == 0)
591 0: return SetOK(Expr::LShr, true, 2);
592 :
0: branch 1 not taken
8: branch 2 taken
593 8: if (memcmp(Tok.start, "UDiv", 4) == 0)
594 0: return SetOK(Expr::UDiv, true, 2);
0: branch 1 not taken
8: branch 2 taken
595 8: if (memcmp(Tok.start, "SDiv", 4) == 0)
596 0: return SetOK(Expr::SDiv, true, 2);
0: branch 1 not taken
8: branch 2 taken
597 8: if (memcmp(Tok.start, "URem", 4) == 0)
598 0: return SetOK(Expr::URem, true, 2);
0: branch 1 not taken
8: branch 2 taken
599 8: if (memcmp(Tok.start, "SRem", 4) == 0)
600 0: return SetOK(Expr::SRem, true, 2);
601 :
8: branch 1 taken
0: branch 2 not taken
602 8: if (memcmp(Tok.start, "SExt", 4) == 0)
603 8: return SetOK(Expr::SExt, false, 1);
0: branch 1 not taken
0: branch 2 not taken
604 0: if (memcmp(Tok.start, "ZExt", 4) == 0)
605 0: return SetOK(Expr::ZExt, false, 1);
606 : break;
607 :
608 : case 6:
137: branch 1 taken
0: branch 2 not taken
609 137: if (memcmp(Tok.start, "Concat", 6) == 0)
610 137: return SetOK(eMacroKind_Concat, false, -1);
0: branch 1 not taken
0: branch 2 not taken
611 0: if (memcmp(Tok.start, "Select", 6) == 0)
612 0: return SetOK(Expr::Select, false, 3);
613 : break;
614 :
615 : case 7:
32: branch 1 taken
61: branch 2 taken
616 93: if (memcmp(Tok.start, "Extract", 7) == 0)
617 32: return SetOK(Expr::Extract, false, -1);
61: branch 1 taken
0: branch 2 not taken
618 61: if (memcmp(Tok.start, "ReadLSB", 7) == 0)
619 61: return SetOK(eMacroKind_ReadLSB, true, -1);
0: branch 1 not taken
0: branch 2 not taken
620 0: if (memcmp(Tok.start, "ReadMSB", 7) == 0)
621 0: return SetOK(eMacroKind_ReadMSB, true, -1);
622 : break;
623 : }
624 :
625 0: return false;
626 : #undef SetOK
627 : }
628 :
629 : /// ParseParenExpr - Parse a parenthesized expression with the given
630 : /// \arg ExpectedType. \arg ExpectedType can be invalid if the type
631 : /// cannot be inferred from the context.
632 : ///
633 : /// paren-expr = '(' type number ')'
634 : /// paren-expr = '(' identifier [type] expr+ ')
635 : /// paren-expr = '(' ('Read' | 'ReadMSB' | 'ReadLSB') type expr update-list ')'
636 629: ExprResult ParserImpl::ParseParenExpr(TypeResult FIXME_UNUSED) {
0: branch 0 not taken
629: branch 1 taken
637 629: if (Tok.kind != Token::LParen) {
638 : Error("unexpected token.");
639 0: ConsumeAnyToken();
640 0: return ExprResult();
641 : }
642 :
643 : ConsumeLParen();
644 :
645 : // Check for coercion case (w32 11).
5: branch 0 taken
624: branch 1 taken
646 629: if (Tok.kind == Token::KWWidth) {
647 5: TypeResult ExpectedType = ParseTypeSpecifier();
648 :
0: branch 0 not taken
5: branch 1 taken
649 5: if (Tok.kind != Token::Number) {
650 : Error("coercion can only apply to a number.");
651 : SkipUntilRParen();
652 0: return ExprResult();
653 : }
654 :
655 : // Make sure this was a type specifier we support.
656 : ExprResult Res;
5: branch 0 taken
0: branch 1 not taken
657 5: if (ExpectedType.isValid())
658 5: Res = ParseNumber(ExpectedType.get());
659 : else
660 0: ConsumeToken();
661 :
662 5: ExpectRParen("unexpected argument in coercion.");
663 5: return Res;
664 : }
665 :
0: branch 0 not taken
624: branch 1 taken
666 624: if (Tok.kind != Token::Identifier) {
667 : Error("unexpected token, expected expression.");
668 : SkipUntilRParen();
669 0: return ExprResult();
670 : }
671 :
672 624: Token Name = Tok;
673 624: ConsumeToken();
674 :
675 : // FIXME: Use invalid type (i.e. width==0)?
676 624: Token TypeTok = Tok;
677 624: bool HasType = TypeTok.kind == Token::KWWidth;
440: branch 0 taken
184: branch 1 taken
678 624: TypeResult Type = HasType ? ParseTypeSpecifier() : Expr::Bool;
679 :
680 : // FIXME: For now just skip to rparen on error. It might be nice
681 : // to try and actually parse the child nodes though for error
682 : // messages & better recovery?
0: branch 0 not taken
624: branch 1 taken
683 624: if (!Type.isValid()) {
684 : SkipUntilRParen();
685 0: return ExprResult();
686 : }
687 624: Expr::Width ResTy = Type.get();
688 :
689 : unsigned ExprKind;
690 : bool IsFixed;
691 : int NumArgs;
0: branch 1 not taken
624: branch 2 taken
692 624: if (!LookupExprInfo(Name, ExprKind, IsFixed, NumArgs)) {
693 : // FIXME: For now just skip to rparen on error. It might be nice
694 : // to try and actually parse the child nodes though for error
695 : // messages & better recovery?
696 0: Error("unknown expression kind.", Name);
697 : SkipUntilRParen();
698 0: return ExprResult();
699 : }
700 :
701 : // See if we have to parse this form specially.
381: branch 0 taken
243: branch 1 taken
702 624: if (NumArgs == -1) {
137: branch 0 taken
32: branch 1 taken
212: branch 2 taken
0: branch 3 not taken
703 381: switch (ExprKind) {
704 : case eMacroKind_Concat:
705 137: return ParseConcatParenExpr(Name, ResTy);
706 :
707 : case Expr::Extract:
708 32: return ParseExtractParenExpr(Name, ResTy);
709 :
710 : case eMacroKind_ReadLSB:
711 : case eMacroKind_ReadMSB:
712 : case Expr::Read:
713 212: return ParseAnyReadParenExpr(Name, ExprKind, ResTy);
714 :
715 : default:
716 0: Error("internal error, unimplemented special form.", Name);
717 : SkipUntilRParen();
718 0: return ExprResult(ref<Expr>(0, ResTy));
719 : }
720 : }
721 :
60: branch 0 taken
183: branch 1 taken
0: branch 2 not taken
0: branch 3 not taken
722 243: switch (NumArgs) {
723 : case 1:
724 60: return ParseUnaryParenExpr(Name, ExprKind, IsFixed, ResTy);
725 : case 2:
726 183: return ParseBinaryParenExpr(Name, ExprKind, IsFixed, ResTy);
727 : case 3:
0: branch 0 not taken
0: branch 1 not taken
728 0: if (ExprKind == Expr::Select)
729 0: return ParseSelectParenExpr(Name, ResTy);
730 : default:
731 0: assert(0 && "Invalid argument kind (number of args).");
732 : return ExprResult();
733 : }
734 : }
735 :
736 : ExprResult ParserImpl::ParseUnaryParenExpr(const Token &Name,
737 : unsigned Kind, bool IsFixed,
738 60: Expr::Width ResTy) {
0: branch 0 not taken
60: branch 1 taken
739 60: if (Tok.kind == Token::RParen) {
740 0: Error("unexpected end of arguments.", Name);
741 0: ConsumeRParen();
742 0: return ref<Expr>(0, ResTy);
743 : }
744 :
52: branch 0 taken
8: branch 1 taken
745 120: ExprResult Arg = ParseExpr(IsFixed ? ResTy : TypeResult());
0: branch 0 not taken
60: branch 1 taken
746 60: if (!Arg.isValid())
747 0: Arg = ref<Expr>(0, ResTy);
748 :
749 60: ExpectRParen("unexpected argument in unary expression.");
750 60: ExprHandle E = Arg.get();
52: branch 0 taken
0: branch 1 not taken
8: branch 2 taken
0: branch 3 not taken
0: branch 4 not taken
751 60: switch (Kind) {
752 : case eMacroKind_Not:
753 156: return EqExpr::alloc(ref<Expr>(0, E.getWidth()), E);
754 : case eMacroKind_Neg:
755 0: return SubExpr::alloc(ref<Expr>(0, E.getWidth()), E);
756 : case Expr::SExt:
757 : // FIXME: Type check arguments.
758 16: return SExtExpr::alloc(E, ResTy);
759 : case Expr::ZExt:
760 : // FIXME: Type check arguments.
761 0: return ZExtExpr::alloc(E, ResTy);
762 : default:
763 0: Error("internal error, unhandled kind.", Name);
764 0: return ref<Expr>(0, ResTy);
765 60: }
766 : }
767 :
768 : /// ParseMatchedBinaryArgs - Parse a pair of arguments who are
769 : /// expected to be of the same type. Upon return, if both LHS and RHS
770 : /// are valid then they are guaranteed to have the same type.
771 : ///
772 : /// Name - The name token of the expression, for diagnostics.
773 : /// ExpectType - The expected type of the arguments, if known.
774 : void ParserImpl::ParseMatchedBinaryArgs(const Token &Name,
775 : TypeResult ExpectType,
776 183: ExprResult &LHS, ExprResult &RHS) {
0: branch 0 not taken
183: branch 1 taken
777 183: if (Tok.kind == Token::RParen) {
778 0: Error("unexpected end of arguments.", Name);
779 0: ConsumeRParen();
780 0: return;
781 : }
782 :
783 : // Avoid NumberOrExprResult overhead and give more precise
784 : // diagnostics when we know the type.
81: branch 0 taken
102: branch 1 taken
785 183: if (ExpectType.isValid()) {
786 81: LHS = ParseExpr(ExpectType);
0: branch 0 not taken
81: branch 1 taken
787 81: if (Tok.kind == Token::RParen) {
788 0: Error("unexpected end of arguments.", Name);
789 0: ConsumeRParen();
790 0: return;
791 : }
792 81: RHS = ParseExpr(ExpectType);
793 : } else {
794 102: NumberOrExprResult LHS_NOE = ParseNumberOrExpr();
795 :
0: branch 0 not taken
102: branch 1 taken
796 102: if (Tok.kind == Token::RParen) {
797 0: Error("unexpected end of arguments.", Name);
798 0: ConsumeRParen();
799 : return;
800 : }
801 :
50: branch 0 taken
52: branch 1 taken
802 102: if (LHS_NOE.isNumber()) {
803 50: NumberOrExprResult RHS_NOE = ParseNumberOrExpr();
804 :
0: branch 0 not taken
50: branch 1 taken
805 50: if (RHS_NOE.isNumber()) {
806 0: Error("ambiguous arguments to expression.", Name);
807 : } else {
808 50: RHS = RHS_NOE.getExpr();
50: branch 0 taken
0: branch 1 not taken
809 50: if (RHS.isValid())
810 100: LHS = ParseNumberToken(RHS.get().getWidth(), LHS_NOE.getNumber());
811 : }
812 : } else {
813 52: LHS = LHS_NOE.getExpr();
0: branch 0 not taken
52: branch 1 taken
814 52: if (!LHS.isValid()) {
815 : // FIXME: Should suppress ambiguity warnings here.
816 0: RHS = ParseExpr(TypeResult());
817 : } else {
818 156: RHS = ParseExpr(LHS.get().getWidth());
819 : }
820 : }
821 : }
822 :
823 183: ExpectRParen("unexpected argument to expression.");
824 : }
825 :
826 : ExprResult ParserImpl::ParseBinaryParenExpr(const Token &Name,
827 : unsigned Kind, bool IsFixed,
828 183: Expr::Width ResTy) {
829 : ExprResult LHS, RHS;
830 : ParseMatchedBinaryArgs(Name, IsFixed ? TypeResult(ResTy) : TypeResult(),
81: branch 0 taken
102: branch 1 taken
831 366: LHS, RHS);
183: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
183: branch 3 taken
0: branch 4 not taken
183: branch 5 taken
832 366: if (!LHS.isValid() || !RHS.isValid())
833 0: return ref<Expr>(0, ResTy);
834 :
835 183: ref<Expr> LHS_E = LHS.get(), RHS_E = RHS.get();
0: branch 2 not taken
183: branch 3 taken
836 183: assert(LHS_E.getWidth() == RHS_E.getWidth() && "Mismatched types!");
837 :
34: branch 0 taken
0: branch 1 not taken
17: branch 2 taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 7 not taken
0: branch 8 not taken
0: branch 9 not taken
27: branch 10 taken
3: branch 11 taken
0: branch 12 not taken
49: branch 13 taken
0: branch 14 not taken
48: branch 15 taken
0: branch 16 not taken
0: branch 17 not taken
0: branch 18 not taken
5: branch 19 taken
0: branch 20 not taken
0: branch 21 not taken
0: branch 22 not taken
0: branch 23 not taken
838 183: switch (Kind) {
839 68: case Expr::Add: return AddExpr::alloc(LHS_E, RHS_E);
840 0: case Expr::Sub: return SubExpr::alloc(LHS_E, RHS_E);
841 34: case Expr::Mul: return MulExpr::alloc(LHS_E, RHS_E);
842 0: case Expr::UDiv: return UDivExpr::alloc(LHS_E, RHS_E);
843 0: case Expr::SDiv: return SDivExpr::alloc(LHS_E, RHS_E);
844 0: case Expr::URem: return URemExpr::alloc(LHS_E, RHS_E);
845 0: case Expr::SRem: return SRemExpr::alloc(LHS_E, RHS_E);
846 :
847 0: case Expr::AShr: return AShrExpr::alloc(LHS_E, RHS_E);
848 0: case Expr::LShr: return LShrExpr::alloc(LHS_E, RHS_E);
849 0: case Expr::Shl: return AndExpr::alloc(LHS_E, RHS_E);
850 :
851 54: case Expr::And: return AndExpr::alloc(LHS_E, RHS_E);
852 6: case Expr::Or: return OrExpr::alloc(LHS_E, RHS_E);
853 0: case Expr::Xor: return XorExpr::alloc(LHS_E, RHS_E);
854 :
855 98: case Expr::Eq: return EqExpr::alloc(LHS_E, RHS_E);
856 0: case Expr::Ne: return NeExpr::alloc(LHS_E, RHS_E);
857 96: case Expr::Ult: return UltExpr::alloc(LHS_E, RHS_E);
858 0: case Expr::Ule: return UleExpr::alloc(LHS_E, RHS_E);
859 0: case Expr::Ugt: return UgtExpr::alloc(LHS_E, RHS_E);
860 0: case Expr::Uge: return UgeExpr::alloc(LHS_E, RHS_E);
861 10: case Expr::Slt: return SltExpr::alloc(LHS_E, RHS_E);
862 0: case Expr::Sle: return SleExpr::alloc(LHS_E, RHS_E);
863 0: case Expr::Sgt: return SgtExpr::alloc(LHS_E, RHS_E);
864 0: case Expr::Sge: return SgeExpr::alloc(LHS_E, RHS_E);
865 : default:
866 0: Error("FIXME: unhandled kind.", Name);
867 0: return ref<Expr>(0, ResTy);
868 183: }
869 : }
870 :
871 : ExprResult ParserImpl::ParseSelectParenExpr(const Token &Name,
872 0: Expr::Width ResTy) {
873 : // FIXME: Why does this need to be here?
0: branch 0 not taken
0: branch 1 not taken
874 0: if (Tok.kind == Token::RParen) {
875 0: Error("unexpected end of arguments.", Name);
876 0: ConsumeRParen();
877 0: return ref<Expr>(0, ResTy);
878 : }
879 :
880 0: ExprResult Cond = ParseExpr(Expr::Bool);
881 : ExprResult LHS, RHS;
882 0: ParseMatchedBinaryArgs(Name, ResTy, LHS, RHS);
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 7 not taken
883 0: if (!Cond.isValid() || !LHS.isValid() || !RHS.isValid())
884 0: return ref<Expr>(0, ResTy);
885 0: return SelectExpr::alloc(Cond.get(), LHS.get(), RHS.get());
886 : }
887 :
888 :
889 : // need to decide if we want to allow n-ary Concat expressions in the
890 : // language
891 : ExprResult ParserImpl::ParseConcatParenExpr(const Token &Name,
892 137: Expr::Width ResTy) {
893 : std::vector<ExprHandle> Kids;
894 :
895 137: unsigned Width = 0;
274: branch 0 taken
137: branch 1 taken
896 548: while (Tok.kind != Token::RParen) {
897 274: ExprResult E = ParseExpr(TypeResult());
898 :
899 : // Skip to end of expr on error.
0: branch 0 not taken
274: branch 1 taken
900 274: if (!E.isValid()) {
901 : SkipUntilRParen();
902 0: return ref<Expr>(0, ResTy);
903 : }
904 :
905 274: Kids.push_back(E.get());
906 274: Width += E.get().getWidth();
907 : }
908 :
909 137: ConsumeRParen();
910 :
0: branch 0 not taken
137: branch 1 taken
911 137: if (Width != ResTy) {
912 : Error("concat does not match expected result size.");
913 0: return ref<Expr>(0, ResTy);
914 : }
915 :
916 411: return ConcatExpr::createN(Kids.size(), &Kids[0]);
917 : }
918 :
919 : ExprResult ParserImpl::ParseExtractParenExpr(const Token &Name,
920 32: Expr::Width ResTy) {
921 : // FIXME: Pull out parse constant integer expression.
922 32: ExprResult OffsetExpr = ParseNumber(Expr::Int32);
923 32: ExprResult Child = ParseExpr(TypeResult());
924 :
925 32: ExpectRParen("unexpected argument to expression.");
926 :
32: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
32: branch 3 taken
0: branch 4 not taken
32: branch 5 taken
927 64: if (!OffsetExpr.isValid() || !Child.isValid())
928 0: return ref<Expr>(0, ResTy);
929 :
0: branch 1 not taken
32: branch 2 taken
32: branch 4 taken
0: branch 5 not taken
930 64: assert(OffsetExpr.get().isConstant() && "ParseNumber returned non-constant.");
931 64: unsigned Offset = (unsigned) OffsetExpr.get().getConstantValue();
932 :
0: branch 3 not taken
32: branch 4 taken
933 32: if (Offset + ResTy > Child.get().getWidth()) {
934 0: Error("extract out-of-range of child expression.", Name);
935 0: return ref<Expr>(0, ResTy);
936 : }
937 :
938 64: return ExtractExpr::alloc(Child.get(), Offset, ResTy);
939 : }
940 :
941 : ExprResult ParserImpl::ParseAnyReadParenExpr(const Token &Name,
942 : unsigned Kind,
943 212: Expr::Width ResTy) {
944 212: NumberOrExprResult Index = ParseNumberOrExpr();
945 212: VersionResult Array = ParseVersionSpecifier();
946 212: ExpectRParen("unexpected argument in read expression.");
947 :
0: branch 0 not taken
212: branch 1 taken
948 212: if (!Array.isValid())
949 0: return ref<Expr>(0, ResTy);
950 :
951 : // FIXME: Need generic way to get array width. Needs to work with
952 : // anonymous arrays.
953 212: Expr::Width ArrayDomainType = Expr::Int32;
954 212: Expr::Width ArrayRangeType = Expr::Int8;
955 :
956 : // Coerce number to correct type.
957 : ExprResult IndexExpr;
203: branch 0 taken
9: branch 1 taken
958 212: if (Index.isNumber())
959 203: IndexExpr = ParseNumberToken(ArrayDomainType, Index.getNumber());
960 : else
961 9: IndexExpr = Index.getExpr();
962 :
0: branch 0 not taken
212: branch 1 taken
963 212: if (!IndexExpr.isValid())
964 0: return ref<Expr>(0, ResTy);
0: branch 3 not taken
212: branch 4 taken
965 212: else if (IndexExpr.get().getWidth() != ArrayDomainType) {
966 : Error("index width does not match array domain.");
967 0: return ref<Expr>(0, ResTy);
968 : }
969 :
970 : // FIXME: Check range width.
971 :
0: branch 0 not taken
61: branch 1 taken
151: branch 2 taken
972 212: switch (Kind) {
973 : default:
974 0: assert(0 && "Invalid kind.");
975 : return ref<Expr>(0, ResTy);
976 : case eMacroKind_ReadLSB:
977 : case eMacroKind_ReadMSB: {
978 61: unsigned NumReads = ResTy / ArrayRangeType;
0: branch 0 not taken
61: branch 1 taken
979 61: if (ResTy != NumReads*ArrayRangeType) {
980 0: Error("invalid ordered read (not multiple of range type).", Name);
981 0: return ref<Expr>(0, ResTy);
982 : }
983 : std::vector<ExprHandle> Kids;
984 61: Kids.reserve(NumReads);
985 61: ExprHandle Index = IndexExpr.get();
122: branch 1 taken
61: branch 2 taken
986 183: for (unsigned i=0; i<NumReads; ++i) {
987 : // FIXME: using folding here
988 : ExprHandle OffsetIndex = AddExpr::create(IndexExpr.get(),
989 244: ref<Expr>(i, ArrayDomainType));
990 122: Kids.push_back(ReadExpr::alloc(Array.get(), OffsetIndex));
991 : }
61: branch 0 taken
0: branch 1 not taken
992 61: if (Kind == eMacroKind_ReadLSB)
993 61: std::reverse(Kids.begin(), Kids.end());
994 183: return ConcatExpr::createN(NumReads, &Kids[0]);
995 : }
996 : case Expr::Read:
997 302: return ReadExpr::alloc(Array.get(), IndexExpr.get());
998 : }
999 : }
1000 :
1001 : /// version-specifier = <identifier>
1002 : /// version-specifier = [<identifier>:] [ version ]
1003 221: VersionResult ParserImpl::ParseVersionSpecifier() {
1004 221: const Identifier *Label = 0;
220: branch 0 taken
1: branch 1 taken
1005 221: if (Tok.kind == Token::Identifier) {
1006 220: Token LTok = Tok;
1007 220: Label = GetOrCreateIdentifier(Tok);
1008 220: ConsumeToken();
1009 :
1010 : // FIXME: hack: add array declarations and ditch this.
176: branch 1 taken
44: branch 2 taken
1011 440: if (memcmp(Label->Name.c_str(), "arr", 3) == 0) {
1012 : // Declare or create array.
1013 352: const ArrayDecl *&Array = ArraySymTab[Label];
176: branch 0 taken
0: branch 1 not taken
1014 176: if (!Array) {
1015 : // Array = new ArrayDecl(Label, 0, 32, 8);
1016 352: MemoryObject *root = new MemoryObject(0);
1017 528: root->id = atoi(&Label->Name.c_str()[3]);
1018 : // Create update list mapping of name -> array.
1019 : VersionSymTab.insert(std::make_pair(Label,
1020 528: UpdateList(root, true, NULL)));
1021 : }
1022 : }
1023 :
208: branch 0 taken
12: branch 1 taken
1024 220: if (Tok.kind != Token::Colon) {
1025 208: VersionSymTabTy::iterator it = VersionSymTab.find(Label);
1026 :
0: branch 0 not taken
208: branch 1 taken
1027 416: if (it == VersionSymTab.end()) {
1028 0: Error("invalid update list label reference.", LTok);
1029 : return VersionResult(false,
1030 0: UpdateList(0, true, NULL));
1031 : }
1032 :
1033 624: return it->second;
1034 : }
1035 :
1036 12: ConsumeToken();
0: branch 0 not taken
12: branch 1 taken
1037 24: if (VersionSymTab.count(Label)) {
1038 0: Error("duplicate update list label definition.", LTok);
1039 0: Label = 0;
1040 : }
1041 : }
1042 :
1043 13: Token Start = Tok;
1044 13: VersionResult Res = ParseVersion();
1045 : // Define update list to avoid use-of-undef errors.
0: branch 0 not taken
13: branch 1 taken
1046 13: if (!Res.isValid())
1047 : Res = VersionResult(false,
1048 0: UpdateList(0, true, NULL));
1049 :
12: branch 0 taken
1: branch 1 taken
1050 13: if (Label)
1051 36: VersionSymTab.insert(std::make_pair(Label, Res.get()));
1052 13: return Res;
1053 : }
1054 :
1055 : /// version - '[' update-list? ']' ['@' version-specifier]
1056 : /// update-list - empty
1057 : /// update-list - lhs '=' rhs [',' update-list]
1058 13: VersionResult ParserImpl::ParseVersion() {
0: branch 0 not taken
13: branch 1 taken
1059 13: if (Tok.kind != Token::LSquare)
1060 0: return VersionResult(false, UpdateList(0, false, NULL));
1061 :
1062 : std::vector< std::pair<NumberOrExprResult, NumberOrExprResult> > Writes;
1063 : ConsumeLSquare();
1064 : for (;;) {
1065 : // FIXME: Type check exprs.
1066 :
1067 : // FIXME: We need to do this (the above) anyway just to handle
1068 : // implicit constants correctly.
1069 300: NumberOrExprResult LHS = ParseNumberOrExpr();
1070 :
0: branch 0 not taken
300: branch 1 taken
1071 300: if (Tok.kind != Token::Equals) {
1072 0: Error("expected '='.", Tok);
1073 : break;
1074 : }
1075 :
1076 300: ConsumeToken();
1077 300: NumberOrExprResult RHS = ParseNumberOrExpr();
1078 :
1079 600: Writes.push_back(std::make_pair(LHS, RHS));
1080 :
287: branch 0 taken
13: branch 1 taken
1081 300: if (Tok.kind == Token::Comma)
1082 287: ConsumeToken();
1083 : else
1084 : break;
1085 : }
1086 : ExpectRSquare("expected close of update list");
1087 :
1088 13: VersionHandle Base(0, false, NULL);
1089 :
1090 : // Anonymous array case.
4: branch 0 taken
9: branch 1 taken
1091 13: if (Tok.kind != Token::At) {
1092 8: MemoryObject *root = new MemoryObject(0);
1093 4: Base = UpdateList(root, false, NULL);
1094 : } else {
1095 9: ConsumeToken();
1096 :
1097 9: VersionResult BaseRes = ParseVersionSpecifier();
0: branch 0 not taken
9: branch 1 taken
1098 9: if (!BaseRes.isValid())
1099 0: return BaseRes;
1100 :
1101 9: Base = BaseRes.get();
1102 : }
1103 :
1104 13: Expr::Width ArrayDomainType = Expr::Int32;
1105 13: Expr::Width ArrayRangeType = Expr::Int8;
1106 :
300: branch 0 taken
13: branch 1 taken
1107 326: for (std::vector< std::pair<NumberOrExprResult, NumberOrExprResult> >::reverse_iterator
1108 : it = Writes.rbegin(), ie = Writes.rend(); it != ie; ++it) {
1109 : ExprResult LHS, RHS;
1110 : // FIXME: This can be factored into common helper for coercing a
1111 : // NumberOrExpr into an Expr.
262: branch 0 taken
38: branch 1 taken
1112 600: if (it->first.isNumber()) {
1113 262: LHS = ParseNumberToken(ArrayDomainType, it->first.getNumber());
1114 : } else {
1115 38: LHS = it->first.getExpr();
38: branch 0 taken
0: branch 1 not taken
0: branch 4 not taken
38: branch 5 taken
38: branch 6 taken
0: branch 7 not taken
0: branch 9 not taken
38: branch 10 taken
1116 76: if (LHS.isValid() && LHS.get().getWidth() != ArrayDomainType) {
1117 : // FIXME: bad token location. We should maybe try and know the
1118 : // array up-front?
1119 0: Error("invalid value in write index (doesn't match domain).", Tok);
1120 0: LHS = ExprResult();
1121 : }
1122 : }
1123 :
268: branch 0 taken
32: branch 1 taken
1124 600: if (it->second.isNumber()) {
1125 268: RHS = ParseNumberToken(ArrayRangeType, it->second.getNumber());
1126 : } else {
1127 32: RHS = it->second.getExpr();
32: branch 0 taken
0: branch 1 not taken
0: branch 4 not taken
32: branch 5 taken
32: branch 6 taken
0: branch 7 not taken
0: branch 9 not taken
32: branch 10 taken
1128 64: if (RHS.isValid() && RHS.get().getWidth() != ArrayRangeType) {
1129 : // FIXME: bad token location. We should maybe try and know the
1130 : // array up-front?
1131 0: Error("invalid value in write assignment (doesn't match range).", Tok);
1132 0: RHS = ExprResult();
1133 : }
1134 : }
1135 :
300: branch 0 taken
0: branch 1 not taken
300: branch 2 taken
0: branch 3 not taken
300: branch 4 taken
0: branch 5 not taken
1136 600: if (LHS.isValid() && RHS.isValid())
1137 300: Base.extend(LHS.get(), RHS.get());
1138 : }
1139 :
1140 26: return Base;
1141 : }
1142 :
1143 : /// ParseNumber - Parse a number of the given type.
1144 136: ExprResult ParserImpl::ParseNumber(Expr::Width Type) {
1145 136: ExprResult Res = ParseNumberToken(Type, Tok);
1146 136: ConsumeExpectedToken(Token::Number);
1147 : return Res;
1148 : }
1149 :
1150 : /// ParseNumberToken - Parse a number of the given type from the given
1151 : /// token.
1152 919: ExprResult ParserImpl::ParseNumberToken(Expr::Width Type, const Token &Tok) {
1153 919: const char *S = Tok.start;
1154 919: unsigned N = Tok.length;
1155 919: unsigned Radix = 10, RadixBits = 4;
1156 919: bool HasMinus = false;
1157 :
1158 : // Detect +/- (a number token cannot have both).
0: branch 0 not taken
919: branch 1 taken
1159 919: if (S[0] == '+') {
1160 0: ++S;
1161 0: --N;
0: branch 0 not taken
919: branch 1 taken
1162 919: } else if (S[0] == '-') {
1163 0: HasMinus = true;
1164 0: ++S;
1165 0: --N;
1166 : }
1167 :
1168 : // Detect 0[box].
348: branch 0 taken
571: branch 1 taken
0: branch 2 not taken
348: branch 3 taken
348: branch 4 taken
348: branch 5 taken
348: branch 6 taken
348: branch 7 taken
1169 919: if ((Tok.length >= 2 && S[0] == '0') &&
1170 : (S[1] == 'b' || S[1] == 'o' || S[1] == 'x')) {
0: branch 0 not taken
0: branch 1 not taken
1171 0: if (S[1] == 'b') {
1172 0: Radix = 2;
1173 0: RadixBits = 1;
0: branch 0 not taken
0: branch 1 not taken
1174 0: } else if (S[1] == 'o') {
1175 0: Radix = 8;
1176 0: RadixBits = 3;
1177 : } else {
1178 0: Radix = 16;
1179 0: RadixBits = 4;
1180 : }
1181 0: S += 2;
1182 0: N -= 2;
1183 :
1184 : // Diagnose 0[box] with no trailing digits.
0: branch 0 not taken
0: branch 1 not taken
1185 0: if (!N) {
1186 0: Error("invalid numeric token (no digits).", Tok);
1187 0: return ref<Expr>(0, Type);
1188 : }
1189 : }
1190 :
1191 : // This is a simple but slow way to handle overflow.
1192 1838: APInt Val(std::max(64U, RadixBits * N), 0);
1193 1838: APInt RadixVal(Val.getBitWidth(), Radix);
1194 919: APInt DigitVal(Val.getBitWidth(), 0);
1314: branch 0 taken
919: branch 1 taken
1195 2233: for (unsigned i=0; i<N; ++i) {
1196 1314: unsigned Digit, Char = S[i];
1197 :
0: branch 0 not taken
1314: branch 1 taken
1198 1314: if (Char == '_')
1199 0: continue;
1200 :
1314: branch 0 taken
0: branch 1 not taken
1201 1314: if ('0' <= Char && Char <= '9')
1202 1314: Digit = Char - '0';
0: branch 0 not taken
0: branch 1 not taken
1203 0: else if ('a' <= Char && Char <= 'z')
1204 0: Digit = Char - 'a' + 10;
0: branch 0 not taken
0: branch 1 not taken
1205 0: else if ('A' <= Char && Char <= 'Z')
1206 0: Digit = Char - 'A' + 10;
1207 : else {
1208 0: Error("invalid character in numeric token.", Tok);
1209 0: return ref<Expr>(0, Type);
1210 : }
1211 :
0: branch 0 not taken
1314: branch 1 taken
1212 1314: if (Digit >= Radix) {
1213 0: Error("invalid character in numeric token (out of range).", Tok);
1214 0: return ref<Expr>(0, Type);
1215 : }
1216 :
1217 1314: DigitVal = Digit;
1218 1314: Val = Val * RadixVal + DigitVal;
1219 : }
1220 :
1221 : // FIXME: Actually do the check for overflow.
0: branch 0 not taken
919: branch 1 taken
1222 919: if (HasMinus)
1223 0: Val = -Val;
1224 :
1225 1838: return ExprResult(ref<Expr>(Val.trunc(Type).getZExtValue(), Type));
1226 : }
1227 :
1228 : /// ParseTypeSpecifier - Parse a type specifier.
1229 : ///
1230 : /// type = w[0-9]+
1231 445: TypeResult ParserImpl::ParseTypeSpecifier() {
0: branch 0 not taken
445: branch 1 taken
1232 445: assert(Tok.kind == Token::KWWidth && "Unexpected token.");
1233 :
1234 : // FIXME: Need APInt technically.
1235 445: Token TypeTok = Tok;
1236 890: int width = atoi(std::string(Tok.start+1,Tok.length-1).c_str());
1237 445: ConsumeToken();
1238 :
1239 : // FIXME: We should impose some sort of maximum just for sanity?
1240 445: return TypeResult(width);
1241 : }
1242 :
1243 0: void ParserImpl::Error(const char *Message, const Token &At) {
1244 0: ++NumErrors;
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
1245 0: if (MaxErrors && NumErrors >= MaxErrors)
1246 0: return;
1247 :
1248 : llvm::cerr << Filename
1249 : << ":" << At.line << ":" << At.column
1250 0: << ": error: " << Message << "\n";
1251 :
1252 : // Skip carat diagnostics on EOF token.
0: branch 0 not taken
0: branch 1 not taken
1253 0: if (At.kind == Token::EndOfFile)
1254 0: return;
1255 :
1256 : // Simple caret style diagnostics.
1257 0: const char *LineBegin = At.start, *LineEnd = At.start,
1258 0: *BufferBegin = TheMemoryBuffer->getBufferStart(),
1259 0: *BufferEnd = TheMemoryBuffer->getBufferEnd();
1260 :
1261 : // Run line pointers forward and back.
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
1262 0: while (LineBegin > BufferBegin &&
1263 : LineBegin[-1] != '\r' && LineBegin[-1] != '\n')
1264 0: --LineBegin;
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
1265 0: while (LineEnd < BufferEnd &&
1266 : LineEnd[0] != '\r' && LineEnd[0] != '\n')
1267 0: ++LineEnd;
1268 :
1269 : // Show the line.
1270 0: llvm::cerr << std::string(LineBegin, LineEnd) << "\n";
1271 :
1272 : // Show the caret or squiggly, making sure to print back spaces the
1273 : // same.
0: branch 0 not taken
0: branch 1 not taken
1274 0: for (const char *S=LineBegin; S != At.start; ++S)
0: branch 1 not taken
0: branch 2 not taken
1275 0: llvm::cerr << (isspace(*S) ? *S : ' ');
0: branch 0 not taken
0: branch 1 not taken
1276 0: if (At.length > 1) {
0: branch 0 not taken
0: branch 1 not taken
1277 0: for (unsigned i=0; i<At.length; ++i)
1278 0: llvm::cerr << '~';
1279 : } else
1280 0: llvm::cerr << '^';
1281 0: llvm::cerr << '\n';
1282 : }
1283 :
1284 : // AST API
1285 : // FIXME: Move out of parser.
1286 :
1287 18: Decl::Decl() {}
1288 :
1289 18: void QueryCommand::dump() {
1290 : // FIXME: This is masking the difference between an actual query and
1291 : // a query decl.
1292 : ExprPPrinter::printQuery(std::cerr,
1293 : ConstraintManager(Constraints),
1294 36: Query);
1295 18: }
1296 :
1297 : // Public parser API
1298 :
1299 2: Parser::Parser() {
1300 2: }
1301 :
1302 2: Parser::~Parser() {
2: branch 0 taken
2: branch 1 taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 6 not taken
2: branch 7 taken
1303 2: }
1304 :
1305 : Parser *Parser::Create(const std::string Filename,
1306 2: const MemoryBuffer *MB) {
1307 4: ParserImpl *P = new ParserImpl(Filename, MB);
1308 : P->Initialize();
1309 2: return P;
5: branch 0 taken
0: branch 1 not taken
5: branch 2 taken
0: branch 3 not taken
1310 10: }
Generated: 2009-05-17 22:47 by zcov