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