1 //===- MILexer.cpp - Machine instructions lexer implementation ----------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the lexing of machine instructions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "MILexer.h" 15 #include "llvm/ADT/None.h" 16 #include "llvm/ADT/StringExtras.h" 17 #include "llvm/ADT/StringSwitch.h" 18 #include "llvm/ADT/Twine.h" 19 #include <cctype> 20 21 using namespace llvm; 22 23 namespace { 24 25 typedef function_ref<void(StringRef::iterator Loc, const Twine &)> 26 ErrorCallbackType; 27 28 /// This class provides a way to iterate and get characters from the source 29 /// string. 30 class Cursor { 31 const char *Ptr; 32 const char *End; 33 34 public: 35 Cursor(NoneType) : Ptr(nullptr), End(nullptr) {} 36 37 explicit Cursor(StringRef Str) { 38 Ptr = Str.data(); 39 End = Ptr + Str.size(); 40 } 41 42 bool isEOF() const { return Ptr == End; } 43 44 char peek(int I = 0) const { return End - Ptr <= I ? 0 : Ptr[I]; } 45 46 void advance(unsigned I = 1) { Ptr += I; } 47 48 StringRef remaining() const { return StringRef(Ptr, End - Ptr); } 49 50 StringRef upto(Cursor C) const { 51 assert(C.Ptr >= Ptr && C.Ptr <= End); 52 return StringRef(Ptr, C.Ptr - Ptr); 53 } 54 55 StringRef::iterator location() const { return Ptr; } 56 57 operator bool() const { return Ptr != nullptr; } 58 }; 59 60 } // end anonymous namespace 61 62 MIToken &MIToken::reset(TokenKind Kind, StringRef Range) { 63 this->Kind = Kind; 64 this->Range = Range; 65 return *this; 66 } 67 68 MIToken &MIToken::setStringValue(StringRef StrVal) { 69 StringValue = StrVal; 70 return *this; 71 } 72 73 MIToken &MIToken::setOwnedStringValue(std::string StrVal) { 74 StringValueStorage = std::move(StrVal); 75 StringValue = StringValueStorage; 76 return *this; 77 } 78 79 MIToken &MIToken::setIntegerValue(APSInt IntVal) { 80 this->IntVal = std::move(IntVal); 81 return *this; 82 } 83 84 /// Skip the leading whitespace characters and return the updated cursor. 85 static Cursor skipWhitespace(Cursor C) { 86 while (isblank(C.peek())) 87 C.advance(); 88 return C; 89 } 90 91 static bool isNewlineChar(char C) { return C == '\n' || C == '\r'; } 92 93 /// Skip a line comment and return the updated cursor. 94 static Cursor skipComment(Cursor C) { 95 if (C.peek() != ';') 96 return C; 97 while (!isNewlineChar(C.peek()) && !C.isEOF()) 98 C.advance(); 99 return C; 100 } 101 102 /// Return true if the given character satisfies the following regular 103 /// expression: [-a-zA-Z$._0-9] 104 static bool isIdentifierChar(char C) { 105 return isalpha(C) || isdigit(C) || C == '_' || C == '-' || C == '.' || 106 C == '$'; 107 } 108 109 /// Unescapes the given string value. 110 /// 111 /// Expects the string value to be quoted. 112 static std::string unescapeQuotedString(StringRef Value) { 113 assert(Value.front() == '"' && Value.back() == '"'); 114 Cursor C = Cursor(Value.substr(1, Value.size() - 2)); 115 116 std::string Str; 117 Str.reserve(C.remaining().size()); 118 while (!C.isEOF()) { 119 char Char = C.peek(); 120 if (Char == '\\') { 121 if (C.peek(1) == '\\') { 122 // Two '\' become one 123 Str += '\\'; 124 C.advance(2); 125 continue; 126 } 127 if (isxdigit(C.peek(1)) && isxdigit(C.peek(2))) { 128 Str += hexDigitValue(C.peek(1)) * 16 + hexDigitValue(C.peek(2)); 129 C.advance(3); 130 continue; 131 } 132 } 133 Str += Char; 134 C.advance(); 135 } 136 return Str; 137 } 138 139 /// Lex a string constant using the following regular expression: \"[^\"]*\" 140 static Cursor lexStringConstant(Cursor C, ErrorCallbackType ErrorCallback) { 141 assert(C.peek() == '"'); 142 for (C.advance(); C.peek() != '"'; C.advance()) { 143 if (C.isEOF() || isNewlineChar(C.peek())) { 144 ErrorCallback( 145 C.location(), 146 "end of machine instruction reached before the closing '\"'"); 147 return None; 148 } 149 } 150 C.advance(); 151 return C; 152 } 153 154 static Cursor lexName(Cursor C, MIToken &Token, MIToken::TokenKind Type, 155 unsigned PrefixLength, ErrorCallbackType ErrorCallback) { 156 auto Range = C; 157 C.advance(PrefixLength); 158 if (C.peek() == '"') { 159 if (Cursor R = lexStringConstant(C, ErrorCallback)) { 160 StringRef String = Range.upto(R); 161 Token.reset(Type, String) 162 .setOwnedStringValue( 163 unescapeQuotedString(String.drop_front(PrefixLength))); 164 return R; 165 } 166 Token.reset(MIToken::Error, Range.remaining()); 167 return Range; 168 } 169 while (isIdentifierChar(C.peek())) 170 C.advance(); 171 Token.reset(Type, Range.upto(C)) 172 .setStringValue(Range.upto(C).drop_front(PrefixLength)); 173 return C; 174 } 175 176 static Cursor maybeLexIntegerType(Cursor C, MIToken &Token) { 177 if (C.peek() != 'i' || !isdigit(C.peek(1))) 178 return None; 179 auto Range = C; 180 C.advance(); // Skip 'i' 181 while (isdigit(C.peek())) 182 C.advance(); 183 Token.reset(MIToken::IntegerType, Range.upto(C)); 184 return C; 185 } 186 187 static MIToken::TokenKind getIdentifierKind(StringRef Identifier) { 188 return StringSwitch<MIToken::TokenKind>(Identifier) 189 .Case("_", MIToken::underscore) 190 .Case("implicit", MIToken::kw_implicit) 191 .Case("implicit-def", MIToken::kw_implicit_define) 192 .Case("def", MIToken::kw_def) 193 .Case("dead", MIToken::kw_dead) 194 .Case("killed", MIToken::kw_killed) 195 .Case("undef", MIToken::kw_undef) 196 .Case("internal", MIToken::kw_internal) 197 .Case("early-clobber", MIToken::kw_early_clobber) 198 .Case("debug-use", MIToken::kw_debug_use) 199 .Case("tied-def", MIToken::kw_tied_def) 200 .Case("frame-setup", MIToken::kw_frame_setup) 201 .Case("debug-location", MIToken::kw_debug_location) 202 .Case(".cfi_same_value", MIToken::kw_cfi_same_value) 203 .Case(".cfi_offset", MIToken::kw_cfi_offset) 204 .Case(".cfi_def_cfa_register", MIToken::kw_cfi_def_cfa_register) 205 .Case(".cfi_def_cfa_offset", MIToken::kw_cfi_def_cfa_offset) 206 .Case(".cfi_def_cfa", MIToken::kw_cfi_def_cfa) 207 .Case("blockaddress", MIToken::kw_blockaddress) 208 .Case("target-index", MIToken::kw_target_index) 209 .Case("half", MIToken::kw_half) 210 .Case("float", MIToken::kw_float) 211 .Case("double", MIToken::kw_double) 212 .Case("x86_fp80", MIToken::kw_x86_fp80) 213 .Case("fp128", MIToken::kw_fp128) 214 .Case("ppc_fp128", MIToken::kw_ppc_fp128) 215 .Case("target-flags", MIToken::kw_target_flags) 216 .Case("volatile", MIToken::kw_volatile) 217 .Case("non-temporal", MIToken::kw_non_temporal) 218 .Case("invariant", MIToken::kw_invariant) 219 .Case("align", MIToken::kw_align) 220 .Case("stack", MIToken::kw_stack) 221 .Case("got", MIToken::kw_got) 222 .Case("jump-table", MIToken::kw_jump_table) 223 .Case("constant-pool", MIToken::kw_constant_pool) 224 .Case("call-entry", MIToken::kw_call_entry) 225 .Case("liveout", MIToken::kw_liveout) 226 .Case("address-taken", MIToken::kw_address_taken) 227 .Case("landing-pad", MIToken::kw_landing_pad) 228 .Case("liveins", MIToken::kw_liveins) 229 .Case("successors", MIToken::kw_successors) 230 .Default(MIToken::Identifier); 231 } 232 233 static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) { 234 if (!isalpha(C.peek()) && C.peek() != '_' && C.peek() != '.') 235 return None; 236 auto Range = C; 237 while (isIdentifierChar(C.peek())) 238 C.advance(); 239 auto Identifier = Range.upto(C); 240 Token.reset(getIdentifierKind(Identifier), Identifier) 241 .setStringValue(Identifier); 242 return C; 243 } 244 245 static Cursor maybeLexMachineBasicBlock(Cursor C, MIToken &Token, 246 ErrorCallbackType ErrorCallback) { 247 bool IsReference = C.remaining().startswith("%bb."); 248 if (!IsReference && !C.remaining().startswith("bb.")) 249 return None; 250 auto Range = C; 251 unsigned PrefixLength = IsReference ? 4 : 3; 252 C.advance(PrefixLength); // Skip '%bb.' or 'bb.' 253 if (!isdigit(C.peek())) { 254 Token.reset(MIToken::Error, C.remaining()); 255 ErrorCallback(C.location(), "expected a number after '%bb.'"); 256 return C; 257 } 258 auto NumberRange = C; 259 while (isdigit(C.peek())) 260 C.advance(); 261 StringRef Number = NumberRange.upto(C); 262 unsigned StringOffset = PrefixLength + Number.size(); // Drop '%bb.<id>' 263 if (C.peek() == '.') { 264 C.advance(); // Skip '.' 265 ++StringOffset; 266 while (isIdentifierChar(C.peek())) 267 C.advance(); 268 } 269 Token.reset(IsReference ? MIToken::MachineBasicBlock 270 : MIToken::MachineBasicBlockLabel, 271 Range.upto(C)) 272 .setIntegerValue(APSInt(Number)) 273 .setStringValue(Range.upto(C).drop_front(StringOffset)); 274 return C; 275 } 276 277 static Cursor maybeLexIndex(Cursor C, MIToken &Token, StringRef Rule, 278 MIToken::TokenKind Kind) { 279 if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size()))) 280 return None; 281 auto Range = C; 282 C.advance(Rule.size()); 283 auto NumberRange = C; 284 while (isdigit(C.peek())) 285 C.advance(); 286 Token.reset(Kind, Range.upto(C)).setIntegerValue(APSInt(NumberRange.upto(C))); 287 return C; 288 } 289 290 static Cursor maybeLexIndexAndName(Cursor C, MIToken &Token, StringRef Rule, 291 MIToken::TokenKind Kind) { 292 if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size()))) 293 return None; 294 auto Range = C; 295 C.advance(Rule.size()); 296 auto NumberRange = C; 297 while (isdigit(C.peek())) 298 C.advance(); 299 StringRef Number = NumberRange.upto(C); 300 unsigned StringOffset = Rule.size() + Number.size(); 301 if (C.peek() == '.') { 302 C.advance(); 303 ++StringOffset; 304 while (isIdentifierChar(C.peek())) 305 C.advance(); 306 } 307 Token.reset(Kind, Range.upto(C)) 308 .setIntegerValue(APSInt(Number)) 309 .setStringValue(Range.upto(C).drop_front(StringOffset)); 310 return C; 311 } 312 313 static Cursor maybeLexJumpTableIndex(Cursor C, MIToken &Token) { 314 return maybeLexIndex(C, Token, "%jump-table.", MIToken::JumpTableIndex); 315 } 316 317 static Cursor maybeLexStackObject(Cursor C, MIToken &Token) { 318 return maybeLexIndexAndName(C, Token, "%stack.", MIToken::StackObject); 319 } 320 321 static Cursor maybeLexFixedStackObject(Cursor C, MIToken &Token) { 322 return maybeLexIndex(C, Token, "%fixed-stack.", MIToken::FixedStackObject); 323 } 324 325 static Cursor maybeLexConstantPoolItem(Cursor C, MIToken &Token) { 326 return maybeLexIndex(C, Token, "%const.", MIToken::ConstantPoolItem); 327 } 328 329 static Cursor maybeLexSubRegisterIndex(Cursor C, MIToken &Token, 330 ErrorCallbackType ErrorCallback) { 331 const StringRef Rule = "%subreg."; 332 if (!C.remaining().startswith(Rule)) 333 return None; 334 return lexName(C, Token, MIToken::SubRegisterIndex, Rule.size(), 335 ErrorCallback); 336 } 337 338 static Cursor maybeLexIRBlock(Cursor C, MIToken &Token, 339 ErrorCallbackType ErrorCallback) { 340 const StringRef Rule = "%ir-block."; 341 if (!C.remaining().startswith(Rule)) 342 return None; 343 if (isdigit(C.peek(Rule.size()))) 344 return maybeLexIndex(C, Token, Rule, MIToken::IRBlock); 345 return lexName(C, Token, MIToken::NamedIRBlock, Rule.size(), ErrorCallback); 346 } 347 348 static Cursor maybeLexIRValue(Cursor C, MIToken &Token, 349 ErrorCallbackType ErrorCallback) { 350 const StringRef Rule = "%ir."; 351 if (!C.remaining().startswith(Rule)) 352 return None; 353 if (isdigit(C.peek(Rule.size()))) 354 return maybeLexIndex(C, Token, Rule, MIToken::IRValue); 355 return lexName(C, Token, MIToken::NamedIRValue, Rule.size(), ErrorCallback); 356 } 357 358 static Cursor lexVirtualRegister(Cursor C, MIToken &Token) { 359 auto Range = C; 360 C.advance(); // Skip '%' 361 auto NumberRange = C; 362 while (isdigit(C.peek())) 363 C.advance(); 364 Token.reset(MIToken::VirtualRegister, Range.upto(C)) 365 .setIntegerValue(APSInt(NumberRange.upto(C))); 366 return C; 367 } 368 369 static Cursor maybeLexRegister(Cursor C, MIToken &Token) { 370 if (C.peek() != '%') 371 return None; 372 if (isdigit(C.peek(1))) 373 return lexVirtualRegister(C, Token); 374 auto Range = C; 375 C.advance(); // Skip '%' 376 while (isIdentifierChar(C.peek())) 377 C.advance(); 378 Token.reset(MIToken::NamedRegister, Range.upto(C)) 379 .setStringValue(Range.upto(C).drop_front(1)); // Drop the '%' 380 return C; 381 } 382 383 static Cursor maybeLexGlobalValue(Cursor C, MIToken &Token, 384 ErrorCallbackType ErrorCallback) { 385 if (C.peek() != '@') 386 return None; 387 if (!isdigit(C.peek(1))) 388 return lexName(C, Token, MIToken::NamedGlobalValue, /*PrefixLength=*/1, 389 ErrorCallback); 390 auto Range = C; 391 C.advance(1); // Skip the '@' 392 auto NumberRange = C; 393 while (isdigit(C.peek())) 394 C.advance(); 395 Token.reset(MIToken::GlobalValue, Range.upto(C)) 396 .setIntegerValue(APSInt(NumberRange.upto(C))); 397 return C; 398 } 399 400 static Cursor maybeLexExternalSymbol(Cursor C, MIToken &Token, 401 ErrorCallbackType ErrorCallback) { 402 if (C.peek() != '$') 403 return None; 404 return lexName(C, Token, MIToken::ExternalSymbol, /*PrefixLength=*/1, 405 ErrorCallback); 406 } 407 408 static bool isValidHexFloatingPointPrefix(char C) { 409 return C == 'H' || C == 'K' || C == 'L' || C == 'M'; 410 } 411 412 static Cursor maybeLexHexFloatingPointLiteral(Cursor C, MIToken &Token) { 413 if (C.peek() != '0' || C.peek(1) != 'x') 414 return None; 415 Cursor Range = C; 416 C.advance(2); // Skip '0x' 417 if (isValidHexFloatingPointPrefix(C.peek())) 418 C.advance(); 419 while (isxdigit(C.peek())) 420 C.advance(); 421 Token.reset(MIToken::FloatingPointLiteral, Range.upto(C)); 422 return C; 423 } 424 425 static Cursor lexFloatingPointLiteral(Cursor Range, Cursor C, MIToken &Token) { 426 C.advance(); 427 // Skip over [0-9]*([eE][-+]?[0-9]+)? 428 while (isdigit(C.peek())) 429 C.advance(); 430 if ((C.peek() == 'e' || C.peek() == 'E') && 431 (isdigit(C.peek(1)) || 432 ((C.peek(1) == '-' || C.peek(1) == '+') && isdigit(C.peek(2))))) { 433 C.advance(2); 434 while (isdigit(C.peek())) 435 C.advance(); 436 } 437 Token.reset(MIToken::FloatingPointLiteral, Range.upto(C)); 438 return C; 439 } 440 441 static Cursor maybeLexNumericalLiteral(Cursor C, MIToken &Token) { 442 if (!isdigit(C.peek()) && (C.peek() != '-' || !isdigit(C.peek(1)))) 443 return None; 444 auto Range = C; 445 C.advance(); 446 while (isdigit(C.peek())) 447 C.advance(); 448 if (C.peek() == '.') 449 return lexFloatingPointLiteral(Range, C, Token); 450 StringRef StrVal = Range.upto(C); 451 Token.reset(MIToken::IntegerLiteral, StrVal).setIntegerValue(APSInt(StrVal)); 452 return C; 453 } 454 455 static MIToken::TokenKind getMetadataKeywordKind(StringRef Identifier) { 456 return StringSwitch<MIToken::TokenKind>(Identifier) 457 .Case("!tbaa", MIToken::md_tbaa) 458 .Case("!alias.scope", MIToken::md_alias_scope) 459 .Case("!noalias", MIToken::md_noalias) 460 .Case("!range", MIToken::md_range) 461 .Default(MIToken::Error); 462 } 463 464 static Cursor maybeLexExlaim(Cursor C, MIToken &Token, 465 ErrorCallbackType ErrorCallback) { 466 if (C.peek() != '!') 467 return None; 468 auto Range = C; 469 C.advance(1); 470 if (isdigit(C.peek()) || !isIdentifierChar(C.peek())) { 471 Token.reset(MIToken::exclaim, Range.upto(C)); 472 return C; 473 } 474 while (isIdentifierChar(C.peek())) 475 C.advance(); 476 StringRef StrVal = Range.upto(C); 477 Token.reset(getMetadataKeywordKind(StrVal), StrVal); 478 if (Token.isError()) 479 ErrorCallback(Token.location(), 480 "use of unknown metadata keyword '" + StrVal + "'"); 481 return C; 482 } 483 484 static MIToken::TokenKind symbolToken(char C) { 485 switch (C) { 486 case ',': 487 return MIToken::comma; 488 case '=': 489 return MIToken::equal; 490 case ':': 491 return MIToken::colon; 492 case '(': 493 return MIToken::lparen; 494 case ')': 495 return MIToken::rparen; 496 case '{': 497 return MIToken::lbrace; 498 case '}': 499 return MIToken::rbrace; 500 case '+': 501 return MIToken::plus; 502 case '-': 503 return MIToken::minus; 504 case '<': 505 return MIToken::less; 506 case '>': 507 return MIToken::greater; 508 default: 509 return MIToken::Error; 510 } 511 } 512 513 static Cursor maybeLexSymbol(Cursor C, MIToken &Token) { 514 MIToken::TokenKind Kind; 515 unsigned Length = 1; 516 if (C.peek() == ':' && C.peek(1) == ':') { 517 Kind = MIToken::coloncolon; 518 Length = 2; 519 } else 520 Kind = symbolToken(C.peek()); 521 if (Kind == MIToken::Error) 522 return None; 523 auto Range = C; 524 C.advance(Length); 525 Token.reset(Kind, Range.upto(C)); 526 return C; 527 } 528 529 static Cursor maybeLexNewline(Cursor C, MIToken &Token) { 530 if (!isNewlineChar(C.peek())) 531 return None; 532 auto Range = C; 533 C.advance(); 534 Token.reset(MIToken::Newline, Range.upto(C)); 535 return C; 536 } 537 538 static Cursor maybeLexEscapedIRValue(Cursor C, MIToken &Token, 539 ErrorCallbackType ErrorCallback) { 540 if (C.peek() != '`') 541 return None; 542 auto Range = C; 543 C.advance(); 544 auto StrRange = C; 545 while (C.peek() != '`') { 546 if (C.isEOF() || isNewlineChar(C.peek())) { 547 ErrorCallback( 548 C.location(), 549 "end of machine instruction reached before the closing '`'"); 550 Token.reset(MIToken::Error, Range.remaining()); 551 return C; 552 } 553 C.advance(); 554 } 555 StringRef Value = StrRange.upto(C); 556 C.advance(); 557 Token.reset(MIToken::QuotedIRValue, Range.upto(C)).setStringValue(Value); 558 return C; 559 } 560 561 StringRef llvm::lexMIToken(StringRef Source, MIToken &Token, 562 ErrorCallbackType ErrorCallback) { 563 auto C = skipComment(skipWhitespace(Cursor(Source))); 564 if (C.isEOF()) { 565 Token.reset(MIToken::Eof, C.remaining()); 566 return C.remaining(); 567 } 568 569 if (Cursor R = maybeLexIntegerType(C, Token)) 570 return R.remaining(); 571 if (Cursor R = maybeLexMachineBasicBlock(C, Token, ErrorCallback)) 572 return R.remaining(); 573 if (Cursor R = maybeLexIdentifier(C, Token)) 574 return R.remaining(); 575 if (Cursor R = maybeLexJumpTableIndex(C, Token)) 576 return R.remaining(); 577 if (Cursor R = maybeLexStackObject(C, Token)) 578 return R.remaining(); 579 if (Cursor R = maybeLexFixedStackObject(C, Token)) 580 return R.remaining(); 581 if (Cursor R = maybeLexConstantPoolItem(C, Token)) 582 return R.remaining(); 583 if (Cursor R = maybeLexSubRegisterIndex(C, Token, ErrorCallback)) 584 return R.remaining(); 585 if (Cursor R = maybeLexIRBlock(C, Token, ErrorCallback)) 586 return R.remaining(); 587 if (Cursor R = maybeLexIRValue(C, Token, ErrorCallback)) 588 return R.remaining(); 589 if (Cursor R = maybeLexRegister(C, Token)) 590 return R.remaining(); 591 if (Cursor R = maybeLexGlobalValue(C, Token, ErrorCallback)) 592 return R.remaining(); 593 if (Cursor R = maybeLexExternalSymbol(C, Token, ErrorCallback)) 594 return R.remaining(); 595 if (Cursor R = maybeLexHexFloatingPointLiteral(C, Token)) 596 return R.remaining(); 597 if (Cursor R = maybeLexNumericalLiteral(C, Token)) 598 return R.remaining(); 599 if (Cursor R = maybeLexExlaim(C, Token, ErrorCallback)) 600 return R.remaining(); 601 if (Cursor R = maybeLexSymbol(C, Token)) 602 return R.remaining(); 603 if (Cursor R = maybeLexNewline(C, Token)) 604 return R.remaining(); 605 if (Cursor R = maybeLexEscapedIRValue(C, Token, ErrorCallback)) 606 return R.remaining(); 607 608 Token.reset(MIToken::Error, C.remaining()); 609 ErrorCallback(C.location(), 610 Twine("unexpected character '") + Twine(C.peek()) + "'"); 611 return C.remaining(); 612 } 613
