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("constant-pool", MIToken::kw_constant_pool)
 207       .Case("liveout", MIToken::kw_liveout)
 208       .Default(MIToken::Identifier);
 209 }
 210
 211 static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) {
 212   if (!isalpha(C.peek()) && C.peek() != '_' && C.peek() != '.')
 213     return None;
 214   auto Range = C;
 215   while (isIdentifierChar(C.peek()))
 216     C.advance();
 217   auto Identifier = Range.upto(C);
 218   Token.reset(getIdentifierKind(Identifier), Identifier)
 219       .setStringValue(Identifier);
 220   return C;
 221 }
 222
 223 static Cursor maybeLexMachineBasicBlock(
 224     Cursor C, MIToken &Token,
 225     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 226   if (!C.remaining().startswith("%bb."))
 227     return None;
 228   auto Range = C;
 229   C.advance(4); // Skip '%bb.'
 230   if (!isdigit(C.peek())) {
 231     Token.reset(MIToken::Error, C.remaining());
 232     ErrorCallback(C.location(), "expected a number after '%bb.'");
 233     return C;
 234   }
 235   auto NumberRange = C;
 236   while (isdigit(C.peek()))
 237     C.advance();
 238   StringRef Number = NumberRange.upto(C);
 239   unsigned StringOffset = 4 + Number.size(); // Drop '%bb.<id>'
 240   if (C.peek() == '.') {
 241     C.advance(); // Skip '.'
 242     ++StringOffset;
 243     while (isIdentifierChar(C.peek()))
 244       C.advance();
 245   }
 246   Token.reset(MIToken::MachineBasicBlock, Range.upto(C))
 247       .setIntegerValue(APSInt(Number))
 248       .setStringValue(Range.upto(C).drop_front(StringOffset));
 249   return C;
 250 }
 251
 252 static Cursor maybeLexIndex(Cursor C, MIToken &Token, StringRef Rule,
 253                             MIToken::TokenKind Kind) {
 254   if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
 255     return None;
 256   auto Range = C;
 257   C.advance(Rule.size());
 258   auto NumberRange = C;
 259   while (isdigit(C.peek()))
 260     C.advance();
 261   Token.reset(Kind, Range.upto(C)).setIntegerValue(APSInt(NumberRange.upto(C)));
 262   return C;
 263 }
 264
 265 static Cursor maybeLexIndexAndName(Cursor C, MIToken &Token, StringRef Rule,
 266                                    MIToken::TokenKind Kind) {
 267   if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
 268     return None;
 269   auto Range = C;
 270   C.advance(Rule.size());
 271   auto NumberRange = C;
 272   while (isdigit(C.peek()))
 273     C.advance();
 274   StringRef Number = NumberRange.upto(C);
 275   unsigned StringOffset = Rule.size() + Number.size();
 276   if (C.peek() == '.') {
 277     C.advance();
 278     ++StringOffset;
 279     while (isIdentifierChar(C.peek()))
 280       C.advance();
 281   }
 282   Token.reset(Kind, Range.upto(C))
 283       .setIntegerValue(APSInt(Number))
 284       .setStringValue(Range.upto(C).drop_front(StringOffset));
 285   return C;
 286 }
 287
 288 static Cursor maybeLexJumpTableIndex(Cursor C, MIToken &Token) {
 289   return maybeLexIndex(C, Token, "%jump-table.", MIToken::JumpTableIndex);
 290 }
 291
 292 static Cursor maybeLexStackObject(Cursor C, MIToken &Token) {
 293   return maybeLexIndexAndName(C, Token, "%stack.", MIToken::StackObject);
 294 }
 295
 296 static Cursor maybeLexFixedStackObject(Cursor C, MIToken &Token) {
 297   return maybeLexIndex(C, Token, "%fixed-stack.", MIToken::FixedStackObject);
 298 }
 299
 300 static Cursor maybeLexConstantPoolItem(Cursor C, MIToken &Token) {
 301   return maybeLexIndex(C, Token, "%const.", MIToken::ConstantPoolItem);
 302 }
 303
 304 static Cursor maybeLexIRBlock(
 305     Cursor C, MIToken &Token,
 306     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 307   const StringRef Rule = "%ir-block.";
 308   if (!C.remaining().startswith(Rule))
 309     return None;
 310   if (isdigit(C.peek(Rule.size())))
 311     return maybeLexIndex(C, Token, Rule, MIToken::IRBlock);
 312   return lexName(C, Token, MIToken::NamedIRBlock, Rule.size(), ErrorCallback);
 313 }
 314
 315 static Cursor maybeLexIRValue(
 316     Cursor C, MIToken &Token,
 317     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 318   const StringRef Rule = "%ir.";
 319   if (!C.remaining().startswith(Rule))
 320     return None;
 321   return lexName(C, Token, MIToken::NamedIRValue, Rule.size(), ErrorCallback);
 322 }
 323
 324 static Cursor lexVirtualRegister(Cursor C, MIToken &Token) {
 325   auto Range = C;
 326   C.advance(); // Skip '%'
 327   auto NumberRange = C;
 328   while (isdigit(C.peek()))
 329     C.advance();
 330   Token.reset(MIToken::VirtualRegister, Range.upto(C))
 331       .setIntegerValue(APSInt(NumberRange.upto(C)));
 332   return C;
 333 }
 334
 335 static Cursor maybeLexRegister(Cursor C, MIToken &Token) {
 336   if (C.peek() != '%')
 337     return None;
 338   if (isdigit(C.peek(1)))
 339     return lexVirtualRegister(C, Token);
 340   auto Range = C;
 341   C.advance(); // Skip '%'
 342   while (isIdentifierChar(C.peek()))
 343     C.advance();
 344   Token.reset(MIToken::NamedRegister, Range.upto(C))
 345       .setStringValue(Range.upto(C).drop_front(1)); // Drop the '%'
 346   return C;
 347 }
 348
 349 static Cursor maybeLexGlobalValue(
 350     Cursor C, MIToken &Token,
 351     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 352   if (C.peek() != '@')
 353     return None;
 354   if (!isdigit(C.peek(1)))
 355     return lexName(C, Token, MIToken::NamedGlobalValue, /*PrefixLength=*/1,
 356                    ErrorCallback);
 357   auto Range = C;
 358   C.advance(1); // Skip the '@'
 359   auto NumberRange = C;
 360   while (isdigit(C.peek()))
 361     C.advance();
 362   Token.reset(MIToken::GlobalValue, Range.upto(C))
 363       .setIntegerValue(APSInt(NumberRange.upto(C)));
 364   return C;
 365 }
 366
 367 static Cursor maybeLexExternalSymbol(
 368     Cursor C, MIToken &Token,
 369     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 370   if (C.peek() != '$')
 371     return None;
 372   return lexName(C, Token, MIToken::ExternalSymbol, /*PrefixLength=*/1,
 373                  ErrorCallback);
 374 }
 375
 376 static bool isValidHexFloatingPointPrefix(char C) {
 377   return C == 'H' || C == 'K' || C == 'L' || C == 'M';
 378 }
 379
 380 static Cursor maybeLexHexFloatingPointLiteral(Cursor C, MIToken &Token) {
 381   if (C.peek() != '0' || C.peek(1) != 'x')
 382     return None;
 383   Cursor Range = C;
 384   C.advance(2); // Skip '0x'
 385   if (isValidHexFloatingPointPrefix(C.peek()))
 386     C.advance();
 387   while (isxdigit(C.peek()))
 388     C.advance();
 389   Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
 390   return C;
 391 }
 392
 393 static Cursor lexFloatingPointLiteral(Cursor Range, Cursor C, MIToken &Token) {
 394   C.advance();
 395   // Skip over [0-9]*([eE][-+]?[0-9]+)?
 396   while (isdigit(C.peek()))
 397     C.advance();
 398   if ((C.peek() == 'e' || C.peek() == 'E') &&
 399       (isdigit(C.peek(1)) ||
 400        ((C.peek(1) == '-' || C.peek(1) == '+') && isdigit(C.peek(2))))) {
 401     C.advance(2);
 402     while (isdigit(C.peek()))
 403       C.advance();
 404   }
 405   Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
 406   return C;
 407 }
 408
 409 static Cursor maybeLexNumericalLiteral(Cursor C, MIToken &Token) {
 410   if (!isdigit(C.peek()) && (C.peek() != '-' || !isdigit(C.peek(1))))
 411     return None;
 412   auto Range = C;
 413   C.advance();
 414   while (isdigit(C.peek()))
 415     C.advance();
 416   if (C.peek() == '.')
 417     return lexFloatingPointLiteral(Range, C, Token);
 418   StringRef StrVal = Range.upto(C);
 419   Token.reset(MIToken::IntegerLiteral, StrVal).setIntegerValue(APSInt(StrVal));
 420   return C;
 421 }
 422
 423 static MIToken::TokenKind symbolToken(char C) {
 424   switch (C) {
 425   case ',':
 426     return MIToken::comma;
 427   case '=':
 428     return MIToken::equal;
 429   case ':':
 430     return MIToken::colon;
 431   case '!':
 432     return MIToken::exclaim;
 433   case '(':
 434     return MIToken::lparen;
 435   case ')':
 436     return MIToken::rparen;
 437   case '+':
 438     return MIToken::plus;
 439   case '-':
 440     return MIToken::minus;
 441   default:
 442     return MIToken::Error;
 443   }
 444 }
 445
 446 static Cursor maybeLexSymbol(Cursor C, MIToken &Token) {
 447   MIToken::TokenKind Kind;
 448   unsigned Length = 1;
 449   if (C.peek() == ':' && C.peek(1) == ':') {
 450     Kind = MIToken::coloncolon;
 451     Length = 2;
 452   } else
 453     Kind = symbolToken(C.peek());
 454   if (Kind == MIToken::Error)
 455     return None;
 456   auto Range = C;
 457   C.advance(Length);
 458   Token.reset(Kind, Range.upto(C));
 459   return C;
 460 }
 461
 462 StringRef llvm::lexMIToken(
 463     StringRef Source, MIToken &Token,
 464     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
 465   auto C = skipWhitespace(Cursor(Source));
 466   if (C.isEOF()) {
 467     Token.reset(MIToken::Eof, C.remaining());
 468     return C.remaining();
 469   }
 470
 471   if (Cursor R = maybeLexIntegerType(C, Token))
 472     return R.remaining();
 473   if (Cursor R = maybeLexIdentifier(C, Token))
 474     return R.remaining();
 475   if (Cursor R = maybeLexMachineBasicBlock(C, Token, ErrorCallback))
 476     return R.remaining();
 477   if (Cursor R = maybeLexJumpTableIndex(C, Token))
 478     return R.remaining();
 479   if (Cursor R = maybeLexStackObject(C, Token))
 480     return R.remaining();
 481   if (Cursor R = maybeLexFixedStackObject(C, Token))
 482     return R.remaining();
 483   if (Cursor R = maybeLexConstantPoolItem(C, Token))
 484     return R.remaining();
 485   if (Cursor R = maybeLexIRBlock(C, Token, ErrorCallback))
 486     return R.remaining();
 487   if (Cursor R = maybeLexIRValue(C, Token, ErrorCallback))
 488     return R.remaining();
 489   if (Cursor R = maybeLexRegister(C, Token))
 490     return R.remaining();
 491   if (Cursor R = maybeLexGlobalValue(C, Token, ErrorCallback))
 492     return R.remaining();
 493   if (Cursor R = maybeLexExternalSymbol(C, Token, ErrorCallback))
 494     return R.remaining();
 495   if (Cursor R = maybeLexHexFloatingPointLiteral(C, Token))
 496     return R.remaining();
 497   if (Cursor R = maybeLexNumericalLiteral(C, Token))
 498     return R.remaining();
 499   if (Cursor R = maybeLexSymbol(C, Token))
 500     return R.remaining();
 501
 502   Token.reset(MIToken::Error, C.remaining());
 503   ErrorCallback(C.location(),
 504                 Twine("unexpected character '") + Twine(C.peek()) + "'");
 505   return C.remaining();
 506 }