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