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 (isspace(C.peek()))
  83     C.advance();
  84   return C;
  85 }
  86
  87 /// Return true if the given character satisfies the following regular
  88 /// expression: [-a-zA-Z$._0-9]
  89 static bool isIdentifierChar(char C) {
  90   return isalpha(C) || isdigit(C) || C == '_' || C == '-' || C == '.' ||
  91          C == '$';
  92 }
  93
  94 /// Unescapes the given string value.
  95 ///
  96 /// Expects the string value to be quoted.
  97 static std::string unescapeQuotedString(StringRef Value) {
  98   assert(Value.front() == '"' && Value.back() == '"');
  99   Cursor C = Cursor(Value.substr(1, Value.size() - 2));
 100
 101   std::string Str;
 102   Str.reserve(C.remaining().size());
 103   while (!C.isEOF()) {
 104     char Char = C.peek();
 105     if (Char == '\\') {
 106       if (C.peek(1) == '\\') {
 107         // Two '\' become one
 108         Str += '\\';
 109         C.advance(2);
 110         continue;
 111       }
 112       if (isxdigit(C.peek(1)) && isxdigit(C.peek(2))) {
 113         Str += hexDigitValue(C.peek(1)) * 16 + hexDigitValue(C.peek(2));
 114         C.advance(3);
 115         continue;
 116       }
 117     }
 118     Str += Char;
 119     C.advance();
 120   }
 121   return Str;
 122 }
 123
 124 /// Lex a string constant using the following regular expression: \"[^\"]*\"
 125 static Cursor lexStringConstant(
 126     Cursor C,
 127     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 128   assert(C.peek() == '"');
 129   for (C.advance(); C.peek() != '"'; C.advance()) {
 130     if (C.isEOF()) {
 131       ErrorCallback(
 132           C.location(),
 133           "end of machine instruction reached before the closing '\"'");
 134       return None;
 135     }
 136   }
 137   C.advance();
 138   return C;
 139 }
 140
 141 static Cursor lexName(
 142     Cursor C, MIToken &Token, MIToken::TokenKind Type, unsigned PrefixLength,
 143     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 144   auto Range = C;
 145   C.advance(PrefixLength);
 146   if (C.peek() == '"') {
 147     if (Cursor R = lexStringConstant(C, ErrorCallback)) {
 148       StringRef String = Range.upto(R);
 149       Token.reset(Type, String)
 150           .setOwnedStringValue(
 151               unescapeQuotedString(String.drop_front(PrefixLength)));
 152       return R;
 153     }
 154     Token.reset(MIToken::Error, Range.remaining());
 155     return Range;
 156   }
 157   while (isIdentifierChar(C.peek()))
 158     C.advance();
 159   Token.reset(Type, Range.upto(C))
 160       .setStringValue(Range.upto(C).drop_front(PrefixLength));
 161   return C;
 162 }
 163
 164 static Cursor maybeLexIntegerType(Cursor C, MIToken &Token) {
 165   if (C.peek() != 'i' || !isdigit(C.peek(1)))
 166     return None;
 167   auto Range = C;
 168   C.advance(); // Skip 'i'
 169   while (isdigit(C.peek()))
 170     C.advance();
 171   Token.reset(MIToken::IntegerType, Range.upto(C));
 172   return C;
 173 }
 174
 175 static MIToken::TokenKind getIdentifierKind(StringRef Identifier) {
 176   return StringSwitch<MIToken::TokenKind>(Identifier)
 177       .Case("_", MIToken::underscore)
 178       .Case("implicit", MIToken::kw_implicit)
 179       .Case("implicit-def", MIToken::kw_implicit_define)
 180       .Case("dead", MIToken::kw_dead)
 181       .Case("killed", MIToken::kw_killed)
 182       .Case("undef", MIToken::kw_undef)
 183       .Case("early-clobber", MIToken::kw_early_clobber)
 184       .Case("debug-use", MIToken::kw_debug_use)
 185       .Case("frame-setup", MIToken::kw_frame_setup)
 186       .Case("debug-location", MIToken::kw_debug_location)
 187       .Case(".cfi_offset", MIToken::kw_cfi_offset)
 188       .Case(".cfi_def_cfa_register", MIToken::kw_cfi_def_cfa_register)
 189       .Case(".cfi_def_cfa_offset", MIToken::kw_cfi_def_cfa_offset)
 190       .Case(".cfi_def_cfa", MIToken::kw_cfi_def_cfa)
 191       .Case("blockaddress", MIToken::kw_blockaddress)
 192       .Case("target-index", MIToken::kw_target_index)
 193       .Case("half", MIToken::kw_half)
 194       .Case("float", MIToken::kw_float)
 195       .Case("double", MIToken::kw_double)
 196       .Case("x86_fp80", MIToken::kw_x86_fp80)
 197       .Case("fp128", MIToken::kw_fp128)
 198       .Case("ppc_fp128", MIToken::kw_ppc_fp128)
 199       .Case("target-flags", MIToken::kw_target_flags)
 200       .Case("volatile", MIToken::kw_volatile)
 201       .Case("non-temporal", MIToken::kw_non_temporal)
 202       .Case("invariant", MIToken::kw_invariant)
 203       .Case("align", MIToken::kw_align)
 204       .Case("stack", MIToken::kw_stack)
 205       .Case("got", MIToken::kw_got)
 206       .Case("jump-table", MIToken::kw_jump_table)
 207       .Case("constant-pool", MIToken::kw_constant_pool)
 208       .Case("liveout", MIToken::kw_liveout)
 209       .Default(MIToken::Identifier);
 210 }
 211
 212 static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) {
 213   if (!isalpha(C.peek()) && C.peek() != '_' && C.peek() != '.')
 214     return None;
 215   auto Range = C;
 216   while (isIdentifierChar(C.peek()))
 217     C.advance();
 218   auto Identifier = Range.upto(C);
 219   Token.reset(getIdentifierKind(Identifier), Identifier)
 220       .setStringValue(Identifier);
 221   return C;
 222 }
 223
 224 static Cursor maybeLexMachineBasicBlock(
 225     Cursor C, MIToken &Token,
 226     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 227   if (!C.remaining().startswith("%bb."))
 228     return None;
 229   auto Range = C;
 230   C.advance(4); // Skip '%bb.'
 231   if (!isdigit(C.peek())) {
 232     Token.reset(MIToken::Error, C.remaining());
 233     ErrorCallback(C.location(), "expected a number after '%bb.'");
 234     return C;
 235   }
 236   auto NumberRange = C;
 237   while (isdigit(C.peek()))
 238     C.advance();
 239   StringRef Number = NumberRange.upto(C);
 240   unsigned StringOffset = 4 + Number.size(); // Drop '%bb.<id>'
 241   if (C.peek() == '.') {
 242     C.advance(); // Skip '.'
 243     ++StringOffset;
 244     while (isIdentifierChar(C.peek()))
 245       C.advance();
 246   }
 247   Token.reset(MIToken::MachineBasicBlock, Range.upto(C))
 248       .setIntegerValue(APSInt(Number))
 249       .setStringValue(Range.upto(C).drop_front(StringOffset));
 250   return C;
 251 }
 252
 253 static Cursor maybeLexIndex(Cursor C, MIToken &Token, StringRef Rule,
 254                             MIToken::TokenKind Kind) {
 255   if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
 256     return None;
 257   auto Range = C;
 258   C.advance(Rule.size());
 259   auto NumberRange = C;
 260   while (isdigit(C.peek()))
 261     C.advance();
 262   Token.reset(Kind, Range.upto(C)).setIntegerValue(APSInt(NumberRange.upto(C)));
 263   return C;
 264 }
 265
 266 static Cursor maybeLexIndexAndName(Cursor C, MIToken &Token, StringRef Rule,
 267                                    MIToken::TokenKind Kind) {
 268   if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
 269     return None;
 270   auto Range = C;
 271   C.advance(Rule.size());
 272   auto NumberRange = C;
 273   while (isdigit(C.peek()))
 274     C.advance();
 275   StringRef Number = NumberRange.upto(C);
 276   unsigned StringOffset = Rule.size() + Number.size();
 277   if (C.peek() == '.') {
 278     C.advance();
 279     ++StringOffset;
 280     while (isIdentifierChar(C.peek()))
 281       C.advance();
 282   }
 283   Token.reset(Kind, Range.upto(C))
 284       .setIntegerValue(APSInt(Number))
 285       .setStringValue(Range.upto(C).drop_front(StringOffset));
 286   return C;
 287 }
 288
 289 static Cursor maybeLexJumpTableIndex(Cursor C, MIToken &Token) {
 290   return maybeLexIndex(C, Token, "%jump-table.", MIToken::JumpTableIndex);
 291 }
 292
 293 static Cursor maybeLexStackObject(Cursor C, MIToken &Token) {
 294   return maybeLexIndexAndName(C, Token, "%stack.", MIToken::StackObject);
 295 }
 296
 297 static Cursor maybeLexFixedStackObject(Cursor C, MIToken &Token) {
 298   return maybeLexIndex(C, Token, "%fixed-stack.", MIToken::FixedStackObject);
 299 }
 300
 301 static Cursor maybeLexConstantPoolItem(Cursor C, MIToken &Token) {
 302   return maybeLexIndex(C, Token, "%const.", MIToken::ConstantPoolItem);
 303 }
 304
 305 static Cursor maybeLexIRBlock(
 306     Cursor C, MIToken &Token,
 307     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 308   const StringRef Rule = "%ir-block.";
 309   if (!C.remaining().startswith(Rule))
 310     return None;
 311   if (isdigit(C.peek(Rule.size())))
 312     return maybeLexIndex(C, Token, Rule, MIToken::IRBlock);
 313   return lexName(C, Token, MIToken::NamedIRBlock, Rule.size(), ErrorCallback);
 314 }
 315
 316 static Cursor maybeLexIRValue(
 317     Cursor C, MIToken &Token,
 318     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 319   const StringRef Rule = "%ir.";
 320   if (!C.remaining().startswith(Rule))
 321     return None;
 322   return lexName(C, Token, MIToken::NamedIRValue, Rule.size(), ErrorCallback);
 323 }
 324
 325 static Cursor lexVirtualRegister(Cursor C, MIToken &Token) {
 326   auto Range = C;
 327   C.advance(); // Skip '%'
 328   auto NumberRange = C;
 329   while (isdigit(C.peek()))
 330     C.advance();
 331   Token.reset(MIToken::VirtualRegister, Range.upto(C))
 332       .setIntegerValue(APSInt(NumberRange.upto(C)));
 333   return C;
 334 }
 335
 336 static Cursor maybeLexRegister(Cursor C, MIToken &Token) {
 337   if (C.peek() != '%')
 338     return None;
 339   if (isdigit(C.peek(1)))
 340     return lexVirtualRegister(C, Token);
 341   auto Range = C;
 342   C.advance(); // Skip '%'
 343   while (isIdentifierChar(C.peek()))
 344     C.advance();
 345   Token.reset(MIToken::NamedRegister, Range.upto(C))
 346       .setStringValue(Range.upto(C).drop_front(1)); // Drop the '%'
 347   return C;
 348 }
 349
 350 static Cursor maybeLexGlobalValue(
 351     Cursor C, MIToken &Token,
 352     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 353   if (C.peek() != '@')
 354     return None;
 355   if (!isdigit(C.peek(1)))
 356     return lexName(C, Token, MIToken::NamedGlobalValue, /*PrefixLength=*/1,
 357                    ErrorCallback);
 358   auto Range = C;
 359   C.advance(1); // Skip the '@'
 360   auto NumberRange = C;
 361   while (isdigit(C.peek()))
 362     C.advance();
 363   Token.reset(MIToken::GlobalValue, Range.upto(C))
 364       .setIntegerValue(APSInt(NumberRange.upto(C)));
 365   return C;
 366 }
 367
 368 static Cursor maybeLexExternalSymbol(
 369     Cursor C, MIToken &Token,
 370     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 371   if (C.peek() != '$')
 372     return None;
 373   return lexName(C, Token, MIToken::ExternalSymbol, /*PrefixLength=*/1,
 374                  ErrorCallback);
 375 }
 376
 377 static bool isValidHexFloatingPointPrefix(char C) {
 378   return C == 'H' || C == 'K' || C == 'L' || C == 'M';
 379 }
 380
 381 static Cursor maybeLexHexFloatingPointLiteral(Cursor C, MIToken &Token) {
 382   if (C.peek() != '0' || C.peek(1) != 'x')
 383     return None;
 384   Cursor Range = C;
 385   C.advance(2); // Skip '0x'
 386   if (isValidHexFloatingPointPrefix(C.peek()))
 387     C.advance();
 388   while (isxdigit(C.peek()))
 389     C.advance();
 390   Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
 391   return C;
 392 }
 393
 394 static Cursor lexFloatingPointLiteral(Cursor Range, Cursor C, MIToken &Token) {
 395   C.advance();
 396   // Skip over [0-9]*([eE][-+]?[0-9]+)?
 397   while (isdigit(C.peek()))
 398     C.advance();
 399   if ((C.peek() == 'e' || C.peek() == 'E') &&
 400       (isdigit(C.peek(1)) ||
 401        ((C.peek(1) == '-' || C.peek(1) == '+') && isdigit(C.peek(2))))) {
 402     C.advance(2);
 403     while (isdigit(C.peek()))
 404       C.advance();
 405   }
 406   Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
 407   return C;
 408 }
 409
 410 static Cursor maybeLexNumericalLiteral(Cursor C, MIToken &Token) {
 411   if (!isdigit(C.peek()) && (C.peek() != '-' || !isdigit(C.peek(1))))
 412     return None;
 413   auto Range = C;
 414   C.advance();
 415   while (isdigit(C.peek()))
 416     C.advance();
 417   if (C.peek() == '.')
 418     return lexFloatingPointLiteral(Range, C, Token);
 419   StringRef StrVal = Range.upto(C);
 420   Token.reset(MIToken::IntegerLiteral, StrVal).setIntegerValue(APSInt(StrVal));
 421   return C;
 422 }
 423
 424 static MIToken::TokenKind symbolToken(char C) {
 425   switch (C) {
 426   case ',':
 427     return MIToken::comma;
 428   case '=':
 429     return MIToken::equal;
 430   case ':':
 431     return MIToken::colon;
 432   case '!':
 433     return MIToken::exclaim;
 434   case '(':
 435     return MIToken::lparen;
 436   case ')':
 437     return MIToken::rparen;
 438   case '+':
 439     return MIToken::plus;
 440   case '-':
 441     return MIToken::minus;
 442   default:
 443     return MIToken::Error;
 444   }
 445 }
 446
 447 static Cursor maybeLexSymbol(Cursor C, MIToken &Token) {
 448   MIToken::TokenKind Kind;
 449   unsigned Length = 1;
 450   if (C.peek() == ':' && C.peek(1) == ':') {
 451     Kind = MIToken::coloncolon;
 452     Length = 2;
 453   } else
 454     Kind = symbolToken(C.peek());
 455   if (Kind == MIToken::Error)
 456     return None;
 457   auto Range = C;
 458   C.advance(Length);
 459   Token.reset(Kind, Range.upto(C));
 460   return C;
 461 }
 462
 463 StringRef llvm::lexMIToken(
 464     StringRef Source, MIToken &Token,
 465     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 466   auto C = skipWhitespace(Cursor(Source));
 467   if (C.isEOF()) {
 468     Token.reset(MIToken::Eof, C.remaining());
 469     return C.remaining();
 470   }
 471
 472   if (Cursor R = maybeLexIntegerType(C, Token))
 473     return R.remaining();
 474   if (Cursor R = maybeLexIdentifier(C, Token))
 475     return R.remaining();
 476   if (Cursor R = maybeLexMachineBasicBlock(C, Token, ErrorCallback))
 477     return R.remaining();
 478   if (Cursor R = maybeLexJumpTableIndex(C, Token))
 479     return R.remaining();
 480   if (Cursor R = maybeLexStackObject(C, Token))
 481     return R.remaining();
 482   if (Cursor R = maybeLexFixedStackObject(C, Token))
 483     return R.remaining();
 484   if (Cursor R = maybeLexConstantPoolItem(C, Token))
 485     return R.remaining();
 486   if (Cursor R = maybeLexIRBlock(C, Token, ErrorCallback))
 487     return R.remaining();
 488   if (Cursor R = maybeLexIRValue(C, Token, ErrorCallback))
 489     return R.remaining();
 490   if (Cursor R = maybeLexRegister(C, Token))
 491     return R.remaining();
 492   if (Cursor R = maybeLexGlobalValue(C, Token, ErrorCallback))
 493     return R.remaining();
 494   if (Cursor R = maybeLexExternalSymbol(C, Token, ErrorCallback))
 495     return R.remaining();
 496   if (Cursor R = maybeLexHexFloatingPointLiteral(C, Token))
 497     return R.remaining();
 498   if (Cursor R = maybeLexNumericalLiteral(C, Token))
 499     return R.remaining();
 500   if (Cursor R = maybeLexSymbol(C, Token))
 501     return R.remaining();
 502
 503   Token.reset(MIToken::Error, C.remaining());
 504   ErrorCallback(C.location(),
 505                 Twine("unexpected character '") + Twine(C.peek()) + "'");
 506   return C.remaining();
 507 }