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("dead", MIToken::kw_dead)
 192       .Case("killed", MIToken::kw_killed)
 193       .Case("undef", MIToken::kw_undef)
 194       .Case("early-clobber", MIToken::kw_early_clobber)
 195       .Case("debug-use", MIToken::kw_debug_use)
 196       .Case("frame-setup", MIToken::kw_frame_setup)
 197       .Case("debug-location", MIToken::kw_debug_location)
 198       .Case(".cfi_offset", MIToken::kw_cfi_offset)
 199       .Case(".cfi_def_cfa_register", MIToken::kw_cfi_def_cfa_register)
 200       .Case(".cfi_def_cfa_offset", MIToken::kw_cfi_def_cfa_offset)
 201       .Case(".cfi_def_cfa", MIToken::kw_cfi_def_cfa)
 202       .Case("blockaddress", MIToken::kw_blockaddress)
 203       .Case("target-index", MIToken::kw_target_index)
 204       .Case("half", MIToken::kw_half)
 205       .Case("float", MIToken::kw_float)
 206       .Case("double", MIToken::kw_double)
 207       .Case("x86_fp80", MIToken::kw_x86_fp80)
 208       .Case("fp128", MIToken::kw_fp128)
 209       .Case("ppc_fp128", MIToken::kw_ppc_fp128)
 210       .Case("target-flags", MIToken::kw_target_flags)
 211       .Case("volatile", MIToken::kw_volatile)
 212       .Case("non-temporal", MIToken::kw_non_temporal)
 213       .Case("invariant", MIToken::kw_invariant)
 214       .Case("align", MIToken::kw_align)
 215       .Case("stack", MIToken::kw_stack)
 216       .Case("got", MIToken::kw_got)
 217       .Case("jump-table", MIToken::kw_jump_table)
 218       .Case("constant-pool", MIToken::kw_constant_pool)
 219       .Case("liveout", MIToken::kw_liveout)
 220       .Case("address-taken", MIToken::kw_address_taken)
 221       .Case("landing-pad", MIToken::kw_landing_pad)
 222       .Case("liveins", MIToken::kw_liveins)
 223       .Case("successors", MIToken::kw_successors)
 224       .Default(MIToken::Identifier);
 225 }
 226
 227 static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) {
 228   if (!isalpha(C.peek()) && C.peek() != '_' && C.peek() != '.')
 229     return None;
 230   auto Range = C;
 231   while (isIdentifierChar(C.peek()))
 232     C.advance();
 233   auto Identifier = Range.upto(C);
 234   Token.reset(getIdentifierKind(Identifier), Identifier)
 235       .setStringValue(Identifier);
 236   return C;
 237 }
 238
 239 static Cursor maybeLexMachineBasicBlock(
 240     Cursor C, MIToken &Token,
 241     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 242   bool IsReference = C.remaining().startswith("%bb.");
 243   if (!IsReference && !C.remaining().startswith("bb."))
 244     return None;
 245   auto Range = C;
 246   unsigned PrefixLength = IsReference ? 4 : 3;
 247   C.advance(PrefixLength); // Skip '%bb.' or 'bb.'
 248   if (!isdigit(C.peek())) {
 249     Token.reset(MIToken::Error, C.remaining());
 250     ErrorCallback(C.location(), "expected a number after '%bb.'");
 251     return C;
 252   }
 253   auto NumberRange = C;
 254   while (isdigit(C.peek()))
 255     C.advance();
 256   StringRef Number = NumberRange.upto(C);
 257   unsigned StringOffset = PrefixLength + Number.size(); // Drop '%bb.<id>'
 258   if (C.peek() == '.') {
 259     C.advance(); // Skip '.'
 260     ++StringOffset;
 261     while (isIdentifierChar(C.peek()))
 262       C.advance();
 263   }
 264   Token.reset(IsReference ? MIToken::MachineBasicBlock
 265                           : MIToken::MachineBasicBlockLabel,
 266               Range.upto(C))
 267       .setIntegerValue(APSInt(Number))
 268       .setStringValue(Range.upto(C).drop_front(StringOffset));
 269   return C;
 270 }
 271
 272 static Cursor maybeLexIndex(Cursor C, MIToken &Token, StringRef Rule,
 273                             MIToken::TokenKind Kind) {
 274   if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
 275     return None;
 276   auto Range = C;
 277   C.advance(Rule.size());
 278   auto NumberRange = C;
 279   while (isdigit(C.peek()))
 280     C.advance();
 281   Token.reset(Kind, Range.upto(C)).setIntegerValue(APSInt(NumberRange.upto(C)));
 282   return C;
 283 }
 284
 285 static Cursor maybeLexIndexAndName(Cursor C, MIToken &Token, StringRef Rule,
 286                                    MIToken::TokenKind Kind) {
 287   if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
 288     return None;
 289   auto Range = C;
 290   C.advance(Rule.size());
 291   auto NumberRange = C;
 292   while (isdigit(C.peek()))
 293     C.advance();
 294   StringRef Number = NumberRange.upto(C);
 295   unsigned StringOffset = Rule.size() + Number.size();
 296   if (C.peek() == '.') {
 297     C.advance();
 298     ++StringOffset;
 299     while (isIdentifierChar(C.peek()))
 300       C.advance();
 301   }
 302   Token.reset(Kind, Range.upto(C))
 303       .setIntegerValue(APSInt(Number))
 304       .setStringValue(Range.upto(C).drop_front(StringOffset));
 305   return C;
 306 }
 307
 308 static Cursor maybeLexJumpTableIndex(Cursor C, MIToken &Token) {
 309   return maybeLexIndex(C, Token, "%jump-table.", MIToken::JumpTableIndex);
 310 }
 311
 312 static Cursor maybeLexStackObject(Cursor C, MIToken &Token) {
 313   return maybeLexIndexAndName(C, Token, "%stack.", MIToken::StackObject);
 314 }
 315
 316 static Cursor maybeLexFixedStackObject(Cursor C, MIToken &Token) {
 317   return maybeLexIndex(C, Token, "%fixed-stack.", MIToken::FixedStackObject);
 318 }
 319
 320 static Cursor maybeLexConstantPoolItem(Cursor C, MIToken &Token) {
 321   return maybeLexIndex(C, Token, "%const.", MIToken::ConstantPoolItem);
 322 }
 323
 324 static Cursor maybeLexIRBlock(
 325     Cursor C, MIToken &Token,
 326     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 327   const StringRef Rule = "%ir-block.";
 328   if (!C.remaining().startswith(Rule))
 329     return None;
 330   if (isdigit(C.peek(Rule.size())))
 331     return maybeLexIndex(C, Token, Rule, MIToken::IRBlock);
 332   return lexName(C, Token, MIToken::NamedIRBlock, Rule.size(), ErrorCallback);
 333 }
 334
 335 static Cursor maybeLexIRValue(
 336     Cursor C, MIToken &Token,
 337     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 338   const StringRef Rule = "%ir.";
 339   if (!C.remaining().startswith(Rule))
 340     return None;
 341   return lexName(C, Token, MIToken::NamedIRValue, Rule.size(), ErrorCallback);
 342 }
 343
 344 static Cursor lexVirtualRegister(Cursor C, MIToken &Token) {
 345   auto Range = C;
 346   C.advance(); // Skip '%'
 347   auto NumberRange = C;
 348   while (isdigit(C.peek()))
 349     C.advance();
 350   Token.reset(MIToken::VirtualRegister, Range.upto(C))
 351       .setIntegerValue(APSInt(NumberRange.upto(C)));
 352   return C;
 353 }
 354
 355 static Cursor maybeLexRegister(Cursor C, MIToken &Token) {
 356   if (C.peek() != '%')
 357     return None;
 358   if (isdigit(C.peek(1)))
 359     return lexVirtualRegister(C, Token);
 360   auto Range = C;
 361   C.advance(); // Skip '%'
 362   while (isIdentifierChar(C.peek()))
 363     C.advance();
 364   Token.reset(MIToken::NamedRegister, Range.upto(C))
 365       .setStringValue(Range.upto(C).drop_front(1)); // Drop the '%'
 366   return C;
 367 }
 368
 369 static Cursor maybeLexGlobalValue(
 370     Cursor C, MIToken &Token,
 371     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 372   if (C.peek() != '@')
 373     return None;
 374   if (!isdigit(C.peek(1)))
 375     return lexName(C, Token, MIToken::NamedGlobalValue, /*PrefixLength=*/1,
 376                    ErrorCallback);
 377   auto Range = C;
 378   C.advance(1); // Skip the '@'
 379   auto NumberRange = C;
 380   while (isdigit(C.peek()))
 381     C.advance();
 382   Token.reset(MIToken::GlobalValue, Range.upto(C))
 383       .setIntegerValue(APSInt(NumberRange.upto(C)));
 384   return C;
 385 }
 386
 387 static Cursor maybeLexExternalSymbol(
 388     Cursor C, MIToken &Token,
 389     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 390   if (C.peek() != '$')
 391     return None;
 392   return lexName(C, Token, MIToken::ExternalSymbol, /*PrefixLength=*/1,
 393                  ErrorCallback);
 394 }
 395
 396 static bool isValidHexFloatingPointPrefix(char C) {
 397   return C == 'H' || C == 'K' || C == 'L' || C == 'M';
 398 }
 399
 400 static Cursor maybeLexHexFloatingPointLiteral(Cursor C, MIToken &Token) {
 401   if (C.peek() != '0' || C.peek(1) != 'x')
 402     return None;
 403   Cursor Range = C;
 404   C.advance(2); // Skip '0x'
 405   if (isValidHexFloatingPointPrefix(C.peek()))
 406     C.advance();
 407   while (isxdigit(C.peek()))
 408     C.advance();
 409   Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
 410   return C;
 411 }
 412
 413 static Cursor lexFloatingPointLiteral(Cursor Range, Cursor C, MIToken &Token) {
 414   C.advance();
 415   // Skip over [0-9]*([eE][-+]?[0-9]+)?
 416   while (isdigit(C.peek()))
 417     C.advance();
 418   if ((C.peek() == 'e' || C.peek() == 'E') &&
 419       (isdigit(C.peek(1)) ||
 420        ((C.peek(1) == '-' || C.peek(1) == '+') && isdigit(C.peek(2))))) {
 421     C.advance(2);
 422     while (isdigit(C.peek()))
 423       C.advance();
 424   }
 425   Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
 426   return C;
 427 }
 428
 429 static Cursor maybeLexNumericalLiteral(Cursor C, MIToken &Token) {
 430   if (!isdigit(C.peek()) && (C.peek() != '-' || !isdigit(C.peek(1))))
 431     return None;
 432   auto Range = C;
 433   C.advance();
 434   while (isdigit(C.peek()))
 435     C.advance();
 436   if (C.peek() == '.')
 437     return lexFloatingPointLiteral(Range, C, Token);
 438   StringRef StrVal = Range.upto(C);
 439   Token.reset(MIToken::IntegerLiteral, StrVal).setIntegerValue(APSInt(StrVal));
 440   return C;
 441 }
 442
 443 static MIToken::TokenKind symbolToken(char C) {
 444   switch (C) {
 445   case ',':
 446     return MIToken::comma;
 447   case '=':
 448     return MIToken::equal;
 449   case ':':
 450     return MIToken::colon;
 451   case '!':
 452     return MIToken::exclaim;
 453   case '(':
 454     return MIToken::lparen;
 455   case ')':
 456     return MIToken::rparen;
 457   case '+':
 458     return MIToken::plus;
 459   case '-':
 460     return MIToken::minus;
 461   default:
 462     return MIToken::Error;
 463   }
 464 }
 465
 466 static Cursor maybeLexSymbol(Cursor C, MIToken &Token) {
 467   MIToken::TokenKind Kind;
 468   unsigned Length = 1;
 469   if (C.peek() == ':' && C.peek(1) == ':') {
 470     Kind = MIToken::coloncolon;
 471     Length = 2;
 472   } else
 473     Kind = symbolToken(C.peek());
 474   if (Kind == MIToken::Error)
 475     return None;
 476   auto Range = C;
 477   C.advance(Length);
 478   Token.reset(Kind, Range.upto(C));
 479   return C;
 480 }
 481
 482 static Cursor maybeLexNewline(Cursor C, MIToken &Token) {
 483   if (!isNewlineChar(C.peek()))
 484     return None;
 485   auto Range = C;
 486   C.advance();
 487   Token.reset(MIToken::Newline, Range.upto(C));
 488   return C;
 489 }
 490
 491 StringRef llvm::lexMIToken(
 492     StringRef Source, MIToken &Token,
 493     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 494   auto C = skipComment(skipWhitespace(Cursor(Source)));
 495   if (C.isEOF()) {
 496     Token.reset(MIToken::Eof, C.remaining());
 497     return C.remaining();
 498   }
 499
 500   if (Cursor R = maybeLexIntegerType(C, Token))
 501     return R.remaining();
 502   if (Cursor R = maybeLexMachineBasicBlock(C, Token, ErrorCallback))
 503     return R.remaining();
 504   if (Cursor R = maybeLexIdentifier(C, Token))
 505     return R.remaining();
 506   if (Cursor R = maybeLexJumpTableIndex(C, Token))
 507     return R.remaining();
 508   if (Cursor R = maybeLexStackObject(C, Token))
 509     return R.remaining();
 510   if (Cursor R = maybeLexFixedStackObject(C, Token))
 511     return R.remaining();
 512   if (Cursor R = maybeLexConstantPoolItem(C, Token))
 513     return R.remaining();
 514   if (Cursor R = maybeLexIRBlock(C, Token, ErrorCallback))
 515     return R.remaining();
 516   if (Cursor R = maybeLexIRValue(C, Token, ErrorCallback))
 517     return R.remaining();
 518   if (Cursor R = maybeLexRegister(C, Token))
 519     return R.remaining();
 520   if (Cursor R = maybeLexGlobalValue(C, Token, ErrorCallback))
 521     return R.remaining();
 522   if (Cursor R = maybeLexExternalSymbol(C, Token, ErrorCallback))
 523     return R.remaining();
 524   if (Cursor R = maybeLexHexFloatingPointLiteral(C, Token))
 525     return R.remaining();
 526   if (Cursor R = maybeLexNumericalLiteral(C, Token))
 527     return R.remaining();
 528   if (Cursor R = maybeLexSymbol(C, Token))
 529     return R.remaining();
 530   if (Cursor R = maybeLexNewline(C, Token))
 531     return R.remaining();
 532
 533   Token.reset(MIToken::Error, C.remaining());
 534   ErrorCallback(C.location(),
 535                 Twine("unexpected character '") + Twine(C.peek()) + "'");
 536   return C.remaining();
 537 }