lib/CodeGen/MIRParser/MILexer.cpp

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