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