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("tied-def", MIToken::kw_tied_def)
 199       .Case("frame-setup", MIToken::kw_frame_setup)
 200       .Case("debug-location", MIToken::kw_debug_location)
 201       .Case(".cfi_same_value", MIToken::kw_cfi_same_value)
 202       .Case(".cfi_offset", MIToken::kw_cfi_offset)
 203       .Case(".cfi_def_cfa_register", MIToken::kw_cfi_def_cfa_register)
 204       .Case(".cfi_def_cfa_offset", MIToken::kw_cfi_def_cfa_offset)
 205       .Case(".cfi_def_cfa", MIToken::kw_cfi_def_cfa)
 206       .Case("blockaddress", MIToken::kw_blockaddress)
 207       .Case("target-index", MIToken::kw_target_index)
 208       .Case("half", MIToken::kw_half)
 209       .Case("float", MIToken::kw_float)
 210       .Case("double", MIToken::kw_double)
 211       .Case("x86_fp80", MIToken::kw_x86_fp80)
 212       .Case("fp128", MIToken::kw_fp128)
 213       .Case("ppc_fp128", MIToken::kw_ppc_fp128)
 214       .Case("target-flags", MIToken::kw_target_flags)
 215       .Case("volatile", MIToken::kw_volatile)
 216       .Case("non-temporal", MIToken::kw_non_temporal)
 217       .Case("invariant", MIToken::kw_invariant)
 218       .Case("align", MIToken::kw_align)
 219       .Case("stack", MIToken::kw_stack)
 220       .Case("got", MIToken::kw_got)
 221       .Case("jump-table", MIToken::kw_jump_table)
 222       .Case("constant-pool", MIToken::kw_constant_pool)
 223       .Case("call-entry", MIToken::kw_call_entry)
 224       .Case("liveout", MIToken::kw_liveout)
 225       .Case("address-taken", MIToken::kw_address_taken)
 226       .Case("landing-pad", MIToken::kw_landing_pad)
 227       .Case("liveins", MIToken::kw_liveins)
 228       .Case("successors", MIToken::kw_successors)
 229       .Default(MIToken::Identifier);
 230 }
 231
 232 static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) {
 233   if (!isalpha(C.peek()) && C.peek() != '_' && C.peek() != '.')
 234     return None;
 235   auto Range = C;
 236   while (isIdentifierChar(C.peek()))
 237     C.advance();
 238   auto Identifier = Range.upto(C);
 239   Token.reset(getIdentifierKind(Identifier), Identifier)
 240       .setStringValue(Identifier);
 241   return C;
 242 }
 243
 244 static Cursor maybeLexMachineBasicBlock(
 245     Cursor C, MIToken &Token,
 246     function_ref<void(StringRef::iterator Loc, const Twine &)> 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 maybeLexIRBlock(
 330     Cursor C, MIToken &Token,
 331     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 332   const StringRef Rule = "%ir-block.";
 333   if (!C.remaining().startswith(Rule))
 334     return None;
 335   if (isdigit(C.peek(Rule.size())))
 336     return maybeLexIndex(C, Token, Rule, MIToken::IRBlock);
 337   return lexName(C, Token, MIToken::NamedIRBlock, Rule.size(), ErrorCallback);
 338 }
 339
 340 static Cursor maybeLexIRValue(
 341     Cursor C, MIToken &Token,
 342     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 343   const StringRef Rule = "%ir.";
 344   if (!C.remaining().startswith(Rule))
 345     return None;
 346   if (isdigit(C.peek(Rule.size())))
 347     return maybeLexIndex(C, Token, Rule, MIToken::IRValue);
 348   return lexName(C, Token, MIToken::NamedIRValue, Rule.size(), ErrorCallback);
 349 }
 350
 351 static Cursor lexVirtualRegister(Cursor C, MIToken &Token) {
 352   auto Range = C;
 353   C.advance(); // Skip '%'
 354   auto NumberRange = C;
 355   while (isdigit(C.peek()))
 356     C.advance();
 357   Token.reset(MIToken::VirtualRegister, Range.upto(C))
 358       .setIntegerValue(APSInt(NumberRange.upto(C)));
 359   return C;
 360 }
 361
 362 static Cursor maybeLexRegister(Cursor C, MIToken &Token) {
 363   if (C.peek() != '%')
 364     return None;
 365   if (isdigit(C.peek(1)))
 366     return lexVirtualRegister(C, Token);
 367   auto Range = C;
 368   C.advance(); // Skip '%'
 369   while (isIdentifierChar(C.peek()))
 370     C.advance();
 371   Token.reset(MIToken::NamedRegister, Range.upto(C))
 372       .setStringValue(Range.upto(C).drop_front(1)); // Drop the '%'
 373   return C;
 374 }
 375
 376 static Cursor maybeLexGlobalValue(
 377     Cursor C, MIToken &Token,
 378     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 379   if (C.peek() != '@')
 380     return None;
 381   if (!isdigit(C.peek(1)))
 382     return lexName(C, Token, MIToken::NamedGlobalValue, /*PrefixLength=*/1,
 383                    ErrorCallback);
 384   auto Range = C;
 385   C.advance(1); // Skip the '@'
 386   auto NumberRange = C;
 387   while (isdigit(C.peek()))
 388     C.advance();
 389   Token.reset(MIToken::GlobalValue, Range.upto(C))
 390       .setIntegerValue(APSInt(NumberRange.upto(C)));
 391   return C;
 392 }
 393
 394 static Cursor maybeLexExternalSymbol(
 395     Cursor C, MIToken &Token,
 396     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 397   if (C.peek() != '$')
 398     return None;
 399   return lexName(C, Token, MIToken::ExternalSymbol, /*PrefixLength=*/1,
 400                  ErrorCallback);
 401 }
 402
 403 static bool isValidHexFloatingPointPrefix(char C) {
 404   return C == 'H' || C == 'K' || C == 'L' || C == 'M';
 405 }
 406
 407 static Cursor maybeLexHexFloatingPointLiteral(Cursor C, MIToken &Token) {
 408   if (C.peek() != '0' || C.peek(1) != 'x')
 409     return None;
 410   Cursor Range = C;
 411   C.advance(2); // Skip '0x'
 412   if (isValidHexFloatingPointPrefix(C.peek()))
 413     C.advance();
 414   while (isxdigit(C.peek()))
 415     C.advance();
 416   Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
 417   return C;
 418 }
 419
 420 static Cursor lexFloatingPointLiteral(Cursor Range, Cursor C, MIToken &Token) {
 421   C.advance();
 422   // Skip over [0-9]*([eE][-+]?[0-9]+)?
 423   while (isdigit(C.peek()))
 424     C.advance();
 425   if ((C.peek() == 'e' || C.peek() == 'E') &&
 426       (isdigit(C.peek(1)) ||
 427        ((C.peek(1) == '-' || C.peek(1) == '+') && isdigit(C.peek(2))))) {
 428     C.advance(2);
 429     while (isdigit(C.peek()))
 430       C.advance();
 431   }
 432   Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
 433   return C;
 434 }
 435
 436 static Cursor maybeLexNumericalLiteral(Cursor C, MIToken &Token) {
 437   if (!isdigit(C.peek()) && (C.peek() != '-' || !isdigit(C.peek(1))))
 438     return None;
 439   auto Range = C;
 440   C.advance();
 441   while (isdigit(C.peek()))
 442     C.advance();
 443   if (C.peek() == '.')
 444     return lexFloatingPointLiteral(Range, C, Token);
 445   StringRef StrVal = Range.upto(C);
 446   Token.reset(MIToken::IntegerLiteral, StrVal).setIntegerValue(APSInt(StrVal));
 447   return C;
 448 }
 449
 450 static MIToken::TokenKind getMetadataKeywordKind(StringRef Identifier) {
 451   return StringSwitch<MIToken::TokenKind>(Identifier)
 452       .Case("!tbaa", MIToken::md_tbaa)
 453       .Case("!alias.scope", MIToken::md_alias_scope)
 454       .Case("!noalias", MIToken::md_noalias)
 455       .Case("!range", MIToken::md_range)
 456       .Default(MIToken::Error);
 457 }
 458
 459 static Cursor maybeLexExlaim(
 460     Cursor C, MIToken &Token,
 461     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 462   if (C.peek() != '!')
 463     return None;
 464   auto Range = C;
 465   C.advance(1);
 466   if (isdigit(C.peek()) || !isIdentifierChar(C.peek())) {
 467     Token.reset(MIToken::exclaim, Range.upto(C));
 468     return C;
 469   }
 470   while (isIdentifierChar(C.peek()))
 471     C.advance();
 472   StringRef StrVal = Range.upto(C);
 473   Token.reset(getMetadataKeywordKind(StrVal), StrVal);
 474   if (Token.isError())
 475     ErrorCallback(Token.location(),
 476                   "use of unknown metadata keyword '" + StrVal + "'");
 477   return C;
 478 }
 479
 480 static MIToken::TokenKind symbolToken(char C) {
 481   switch (C) {
 482   case ',':
 483     return MIToken::comma;
 484   case '=':
 485     return MIToken::equal;
 486   case ':':
 487     return MIToken::colon;
 488   case '(':
 489     return MIToken::lparen;
 490   case ')':
 491     return MIToken::rparen;
 492   case '{':
 493     return MIToken::lbrace;
 494   case '}':
 495     return MIToken::rbrace;
 496   case '+':
 497     return MIToken::plus;
 498   case '-':
 499     return MIToken::minus;
 500   default:
 501     return MIToken::Error;
 502   }
 503 }
 504
 505 static Cursor maybeLexSymbol(Cursor C, MIToken &Token) {
 506   MIToken::TokenKind Kind;
 507   unsigned Length = 1;
 508   if (C.peek() == ':' && C.peek(1) == ':') {
 509     Kind = MIToken::coloncolon;
 510     Length = 2;
 511   } else
 512     Kind = symbolToken(C.peek());
 513   if (Kind == MIToken::Error)
 514     return None;
 515   auto Range = C;
 516   C.advance(Length);
 517   Token.reset(Kind, Range.upto(C));
 518   return C;
 519 }
 520
 521 static Cursor maybeLexNewline(Cursor C, MIToken &Token) {
 522   if (!isNewlineChar(C.peek()))
 523     return None;
 524   auto Range = C;
 525   C.advance();
 526   Token.reset(MIToken::Newline, Range.upto(C));
 527   return C;
 528 }
 529
 530 StringRef llvm::lexMIToken(
 531     StringRef Source, MIToken &Token,
 532     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 533   auto C = skipComment(skipWhitespace(Cursor(Source)));
 534   if (C.isEOF()) {
 535     Token.reset(MIToken::Eof, C.remaining());
 536     return C.remaining();
 537   }
 538
 539   if (Cursor R = maybeLexIntegerType(C, Token))
 540     return R.remaining();
 541   if (Cursor R = maybeLexMachineBasicBlock(C, Token, ErrorCallback))
 542     return R.remaining();
 543   if (Cursor R = maybeLexIdentifier(C, Token))
 544     return R.remaining();
 545   if (Cursor R = maybeLexJumpTableIndex(C, Token))
 546     return R.remaining();
 547   if (Cursor R = maybeLexStackObject(C, Token))
 548     return R.remaining();
 549   if (Cursor R = maybeLexFixedStackObject(C, Token))
 550     return R.remaining();
 551   if (Cursor R = maybeLexConstantPoolItem(C, Token))
 552     return R.remaining();
 553   if (Cursor R = maybeLexIRBlock(C, Token, ErrorCallback))
 554     return R.remaining();
 555   if (Cursor R = maybeLexIRValue(C, Token, ErrorCallback))
 556     return R.remaining();
 557   if (Cursor R = maybeLexRegister(C, Token))
 558     return R.remaining();
 559   if (Cursor R = maybeLexGlobalValue(C, Token, ErrorCallback))
 560     return R.remaining();
 561   if (Cursor R = maybeLexExternalSymbol(C, Token, ErrorCallback))
 562     return R.remaining();
 563   if (Cursor R = maybeLexHexFloatingPointLiteral(C, Token))
 564     return R.remaining();
 565   if (Cursor R = maybeLexNumericalLiteral(C, Token))
 566     return R.remaining();
 567   if (Cursor R = maybeLexExlaim(C, Token, ErrorCallback))
 568     return R.remaining();
 569   if (Cursor R = maybeLexSymbol(C, Token))
 570     return R.remaining();
 571   if (Cursor R = maybeLexNewline(C, Token))
 572     return R.remaining();
 573
 574   Token.reset(MIToken::Error, C.remaining());
 575   ErrorCallback(C.location(),
 576                 Twine("unexpected character '") + Twine(C.peek()) + "'");
 577   return C.remaining();
 578 }