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
20using namespace llvm;
21
22namespace {
23
24/// This class provides a way to iterate and get characters from the source
25/// string.
26class Cursor {
27  const char *Ptr;
28  const char *End;
29
30public:
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
58MIToken &MIToken::reset(TokenKind Kind, StringRef Range) {
59  this->Kind = Kind;
60  this->Range = Range;
61  return *this;
62}
63
64MIToken &MIToken::setStringValue(StringRef StrVal) {
65  StringValue = StrVal;
66  return *this;
67}
68
69MIToken &MIToken::setOwnedStringValue(std::string StrVal) {
70  StringValueStorage = std::move(StrVal);
71  StringValue = StringValueStorage;
72  return *this;
73}
74
75MIToken &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.
81static Cursor skipWhitespace(Cursor C) {
82  while (isblank(C.peek()))
83    C.advance();
84  return C;
85}
86
87static bool isNewlineChar(char C) { return C == '\n' || C == '\r'; }
88
89/// Skip a line comment and return the updated cursor.
90static Cursor skipComment(Cursor C) {
91  if (C.peek() != ';')
92    return C;
93  while (!isNewlineChar(C.peek()) && !C.isEOF())
94    C.advance();
95  return C;
96}
97
98/// Return true if the given character satisfies the following regular
99/// expression: [-a-zA-Z$._0-9]
100static bool isIdentifierChar(char C) {
101  return isalpha(C) || isdigit(C) || C == '_' || C == '-' || C == '.' ||
102         C == '$';
103}
104
105/// Unescapes the given string value.
106///
107/// Expects the string value to be quoted.
108static std::string unescapeQuotedString(StringRef Value) {
109  assert(Value.front() == '"' && Value.back() == '"');
110  Cursor C = Cursor(Value.substr(1, Value.size() - 2));
111
112  std::string Str;
113  Str.reserve(C.remaining().size());
114  while (!C.isEOF()) {
115    char Char = C.peek();
116    if (Char == '\\') {
117      if (C.peek(1) == '\\') {
118        // Two '\' become one
119        Str += '\\';
120        C.advance(2);
121        continue;
122      }
123      if (isxdigit(C.peek(1)) && isxdigit(C.peek(2))) {
124        Str += hexDigitValue(C.peek(1)) * 16 + hexDigitValue(C.peek(2));
125        C.advance(3);
126        continue;
127      }
128    }
129    Str += Char;
130    C.advance();
131  }
132  return Str;
133}
134
135/// Lex a string constant using the following regular expression: \"[^\"]*\"
136static Cursor lexStringConstant(
137    Cursor C,
138    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
139  assert(C.peek() == '"');
140  for (C.advance(); C.peek() != '"'; C.advance()) {
141    if (C.isEOF() || isNewlineChar(C.peek())) {
142      ErrorCallback(
143          C.location(),
144          "end of machine instruction reached before the closing '\"'");
145      return None;
146    }
147  }
148  C.advance();
149  return C;
150}
151
152static Cursor lexName(
153    Cursor C, MIToken &Token, MIToken::TokenKind Type, unsigned PrefixLength,
154    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
155  auto Range = C;
156  C.advance(PrefixLength);
157  if (C.peek() == '"') {
158    if (Cursor R = lexStringConstant(C, ErrorCallback)) {
159      StringRef String = Range.upto(R);
160      Token.reset(Type, String)
161          .setOwnedStringValue(
162              unescapeQuotedString(String.drop_front(PrefixLength)));
163      return R;
164    }
165    Token.reset(MIToken::Error, Range.remaining());
166    return Range;
167  }
168  while (isIdentifierChar(C.peek()))
169    C.advance();
170  Token.reset(Type, Range.upto(C))
171      .setStringValue(Range.upto(C).drop_front(PrefixLength));
172  return C;
173}
174
175static Cursor maybeLexIntegerType(Cursor C, MIToken &Token) {
176  if (C.peek() != 'i' || !isdigit(C.peek(1)))
177    return None;
178  auto Range = C;
179  C.advance(); // Skip 'i'
180  while (isdigit(C.peek()))
181    C.advance();
182  Token.reset(MIToken::IntegerType, Range.upto(C));
183  return C;
184}
185
186static MIToken::TokenKind getIdentifierKind(StringRef Identifier) {
187  return StringSwitch<MIToken::TokenKind>(Identifier)
188      .Case("_", MIToken::underscore)
189      .Case("implicit", MIToken::kw_implicit)
190      .Case("implicit-def", MIToken::kw_implicit_define)
191      .Case("def", MIToken::kw_def)
192      .Case("dead", MIToken::kw_dead)
193      .Case("killed", MIToken::kw_killed)
194      .Case("undef", MIToken::kw_undef)
195      .Case("internal", MIToken::kw_internal)
196      .Case("early-clobber", MIToken::kw_early_clobber)
197      .Case("debug-use", MIToken::kw_debug_use)
198      .Case("tied-def", MIToken::kw_tied_def)
199      .Case("frame-setup", MIToken::kw_frame_setup)
200      .Case("debug-location", MIToken::kw_debug_location)
201      .Case(".cfi_same_value", MIToken::kw_cfi_same_value)
202      .Case(".cfi_offset", MIToken::kw_cfi_offset)
203      .Case(".cfi_def_cfa_register", MIToken::kw_cfi_def_cfa_register)
204      .Case(".cfi_def_cfa_offset", MIToken::kw_cfi_def_cfa_offset)
205      .Case(".cfi_def_cfa", MIToken::kw_cfi_def_cfa)
206      .Case("blockaddress", MIToken::kw_blockaddress)
207      .Case("target-index", MIToken::kw_target_index)
208      .Case("half", MIToken::kw_half)
209      .Case("float", MIToken::kw_float)
210      .Case("double", MIToken::kw_double)
211      .Case("x86_fp80", MIToken::kw_x86_fp80)
212      .Case("fp128", MIToken::kw_fp128)
213      .Case("ppc_fp128", MIToken::kw_ppc_fp128)
214      .Case("target-flags", MIToken::kw_target_flags)
215      .Case("volatile", MIToken::kw_volatile)
216      .Case("non-temporal", MIToken::kw_non_temporal)
217      .Case("invariant", MIToken::kw_invariant)
218      .Case("align", MIToken::kw_align)
219      .Case("stack", MIToken::kw_stack)
220      .Case("got", MIToken::kw_got)
221      .Case("jump-table", MIToken::kw_jump_table)
222      .Case("constant-pool", MIToken::kw_constant_pool)
223      .Case("call-entry", MIToken::kw_call_entry)
224      .Case("liveout", MIToken::kw_liveout)
225      .Case("address-taken", MIToken::kw_address_taken)
226      .Case("landing-pad", MIToken::kw_landing_pad)
227      .Case("liveins", MIToken::kw_liveins)
228      .Case("successors", MIToken::kw_successors)
229      .Default(MIToken::Identifier);
230}
231
232static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) {
233  if (!isalpha(C.peek()) && C.peek() != '_' && C.peek() != '.')
234    return None;
235  auto Range = C;
236  while (isIdentifierChar(C.peek()))
237    C.advance();
238  auto Identifier = Range.upto(C);
239  Token.reset(getIdentifierKind(Identifier), Identifier)
240      .setStringValue(Identifier);
241  return C;
242}
243
244static Cursor maybeLexMachineBasicBlock(
245    Cursor C, MIToken &Token,
246    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
247  bool IsReference = C.remaining().startswith("%bb.");
248  if (!IsReference && !C.remaining().startswith("bb."))
249    return None;
250  auto Range = C;
251  unsigned PrefixLength = IsReference ? 4 : 3;
252  C.advance(PrefixLength); // Skip '%bb.' or 'bb.'
253  if (!isdigit(C.peek())) {
254    Token.reset(MIToken::Error, C.remaining());
255    ErrorCallback(C.location(), "expected a number after '%bb.'");
256    return C;
257  }
258  auto NumberRange = C;
259  while (isdigit(C.peek()))
260    C.advance();
261  StringRef Number = NumberRange.upto(C);
262  unsigned StringOffset = PrefixLength + Number.size(); // Drop '%bb.<id>'
263  if (C.peek() == '.') {
264    C.advance(); // Skip '.'
265    ++StringOffset;
266    while (isIdentifierChar(C.peek()))
267      C.advance();
268  }
269  Token.reset(IsReference ? MIToken::MachineBasicBlock
270                          : MIToken::MachineBasicBlockLabel,
271              Range.upto(C))
272      .setIntegerValue(APSInt(Number))
273      .setStringValue(Range.upto(C).drop_front(StringOffset));
274  return C;
275}
276
277static Cursor maybeLexIndex(Cursor C, MIToken &Token, StringRef Rule,
278                            MIToken::TokenKind Kind) {
279  if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
280    return None;
281  auto Range = C;
282  C.advance(Rule.size());
283  auto NumberRange = C;
284  while (isdigit(C.peek()))
285    C.advance();
286  Token.reset(Kind, Range.upto(C)).setIntegerValue(APSInt(NumberRange.upto(C)));
287  return C;
288}
289
290static Cursor maybeLexIndexAndName(Cursor C, MIToken &Token, StringRef Rule,
291                                   MIToken::TokenKind Kind) {
292  if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
293    return None;
294  auto Range = C;
295  C.advance(Rule.size());
296  auto NumberRange = C;
297  while (isdigit(C.peek()))
298    C.advance();
299  StringRef Number = NumberRange.upto(C);
300  unsigned StringOffset = Rule.size() + Number.size();
301  if (C.peek() == '.') {
302    C.advance();
303    ++StringOffset;
304    while (isIdentifierChar(C.peek()))
305      C.advance();
306  }
307  Token.reset(Kind, Range.upto(C))
308      .setIntegerValue(APSInt(Number))
309      .setStringValue(Range.upto(C).drop_front(StringOffset));
310  return C;
311}
312
313static Cursor maybeLexJumpTableIndex(Cursor C, MIToken &Token) {
314  return maybeLexIndex(C, Token, "%jump-table.", MIToken::JumpTableIndex);
315}
316
317static Cursor maybeLexStackObject(Cursor C, MIToken &Token) {
318  return maybeLexIndexAndName(C, Token, "%stack.", MIToken::StackObject);
319}
320
321static Cursor maybeLexFixedStackObject(Cursor C, MIToken &Token) {
322  return maybeLexIndex(C, Token, "%fixed-stack.", MIToken::FixedStackObject);
323}
324
325static Cursor maybeLexConstantPoolItem(Cursor C, MIToken &Token) {
326  return maybeLexIndex(C, Token, "%const.", MIToken::ConstantPoolItem);
327}
328
329static Cursor maybeLexIRBlock(
330    Cursor C, MIToken &Token,
331    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
332  const StringRef Rule = "%ir-block.";
333  if (!C.remaining().startswith(Rule))
334    return None;
335  if (isdigit(C.peek(Rule.size())))
336    return maybeLexIndex(C, Token, Rule, MIToken::IRBlock);
337  return lexName(C, Token, MIToken::NamedIRBlock, Rule.size(), ErrorCallback);
338}
339
340static Cursor maybeLexIRValue(
341    Cursor C, MIToken &Token,
342    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
343  const StringRef Rule = "%ir.";
344  if (!C.remaining().startswith(Rule))
345    return None;
346  if (isdigit(C.peek(Rule.size())))
347    return maybeLexIndex(C, Token, Rule, MIToken::IRValue);
348  return lexName(C, Token, MIToken::NamedIRValue, Rule.size(), ErrorCallback);
349}
350
351static Cursor lexVirtualRegister(Cursor C, MIToken &Token) {
352  auto Range = C;
353  C.advance(); // Skip '%'
354  auto NumberRange = C;
355  while (isdigit(C.peek()))
356    C.advance();
357  Token.reset(MIToken::VirtualRegister, Range.upto(C))
358      .setIntegerValue(APSInt(NumberRange.upto(C)));
359  return C;
360}
361
362static Cursor maybeLexRegister(Cursor C, MIToken &Token) {
363  if (C.peek() != '%')
364    return None;
365  if (isdigit(C.peek(1)))
366    return lexVirtualRegister(C, Token);
367  auto Range = C;
368  C.advance(); // Skip '%'
369  while (isIdentifierChar(C.peek()))
370    C.advance();
371  Token.reset(MIToken::NamedRegister, Range.upto(C))
372      .setStringValue(Range.upto(C).drop_front(1)); // Drop the '%'
373  return C;
374}
375
376static Cursor maybeLexGlobalValue(
377    Cursor C, MIToken &Token,
378    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
379  if (C.peek() != '@')
380    return None;
381  if (!isdigit(C.peek(1)))
382    return lexName(C, Token, MIToken::NamedGlobalValue, /*PrefixLength=*/1,
383                   ErrorCallback);
384  auto Range = C;
385  C.advance(1); // Skip the '@'
386  auto NumberRange = C;
387  while (isdigit(C.peek()))
388    C.advance();
389  Token.reset(MIToken::GlobalValue, Range.upto(C))
390      .setIntegerValue(APSInt(NumberRange.upto(C)));
391  return C;
392}
393
394static Cursor maybeLexExternalSymbol(
395    Cursor C, MIToken &Token,
396    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
397  if (C.peek() != '$')
398    return None;
399  return lexName(C, Token, MIToken::ExternalSymbol, /*PrefixLength=*/1,
400                 ErrorCallback);
401}
402
403static bool isValidHexFloatingPointPrefix(char C) {
404  return C == 'H' || C == 'K' || C == 'L' || C == 'M';
405}
406
407static Cursor maybeLexHexFloatingPointLiteral(Cursor C, MIToken &Token) {
408  if (C.peek() != '0' || C.peek(1) != 'x')
409    return None;
410  Cursor Range = C;
411  C.advance(2); // Skip '0x'
412  if (isValidHexFloatingPointPrefix(C.peek()))
413    C.advance();
414  while (isxdigit(C.peek()))
415    C.advance();
416  Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
417  return C;
418}
419
420static Cursor lexFloatingPointLiteral(Cursor Range, Cursor C, MIToken &Token) {
421  C.advance();
422  // Skip over [0-9]*([eE][-+]?[0-9]+)?
423  while (isdigit(C.peek()))
424    C.advance();
425  if ((C.peek() == 'e' || C.peek() == 'E') &&
426      (isdigit(C.peek(1)) ||
427       ((C.peek(1) == '-' || C.peek(1) == '+') && isdigit(C.peek(2))))) {
428    C.advance(2);
429    while (isdigit(C.peek()))
430      C.advance();
431  }
432  Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
433  return C;
434}
435
436static Cursor maybeLexNumericalLiteral(Cursor C, MIToken &Token) {
437  if (!isdigit(C.peek()) && (C.peek() != '-' || !isdigit(C.peek(1))))
438    return None;
439  auto Range = C;
440  C.advance();
441  while (isdigit(C.peek()))
442    C.advance();
443  if (C.peek() == '.')
444    return lexFloatingPointLiteral(Range, C, Token);
445  StringRef StrVal = Range.upto(C);
446  Token.reset(MIToken::IntegerLiteral, StrVal).setIntegerValue(APSInt(StrVal));
447  return C;
448}
449
450static MIToken::TokenKind getMetadataKeywordKind(StringRef Identifier) {
451  return StringSwitch<MIToken::TokenKind>(Identifier)
452      .Case("!tbaa", MIToken::md_tbaa)
453      .Case("!alias.scope", MIToken::md_alias_scope)
454      .Case("!noalias", MIToken::md_noalias)
455      .Case("!range", MIToken::md_range)
456      .Default(MIToken::Error);
457}
458
459static Cursor maybeLexExlaim(
460    Cursor C, MIToken &Token,
461    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
462  if (C.peek() != '!')
463    return None;
464  auto Range = C;
465  C.advance(1);
466  if (isdigit(C.peek()) || !isIdentifierChar(C.peek())) {
467    Token.reset(MIToken::exclaim, Range.upto(C));
468    return C;
469  }
470  while (isIdentifierChar(C.peek()))
471    C.advance();
472  StringRef StrVal = Range.upto(C);
473  Token.reset(getMetadataKeywordKind(StrVal), StrVal);
474  if (Token.isError())
475    ErrorCallback(Token.location(),
476                  "use of unknown metadata keyword '" + StrVal + "'");
477  return C;
478}
479
480static MIToken::TokenKind symbolToken(char C) {
481  switch (C) {
482  case ',':
483    return MIToken::comma;
484  case '=':
485    return MIToken::equal;
486  case ':':
487    return MIToken::colon;
488  case '(':
489    return MIToken::lparen;
490  case ')':
491    return MIToken::rparen;
492  case '{':
493    return MIToken::lbrace;
494  case '}':
495    return MIToken::rbrace;
496  case '+':
497    return MIToken::plus;
498  case '-':
499    return MIToken::minus;
500  default:
501    return MIToken::Error;
502  }
503}
504
505static Cursor maybeLexSymbol(Cursor C, MIToken &Token) {
506  MIToken::TokenKind Kind;
507  unsigned Length = 1;
508  if (C.peek() == ':' && C.peek(1) == ':') {
509    Kind = MIToken::coloncolon;
510    Length = 2;
511  } else
512    Kind = symbolToken(C.peek());
513  if (Kind == MIToken::Error)
514    return None;
515  auto Range = C;
516  C.advance(Length);
517  Token.reset(Kind, Range.upto(C));
518  return C;
519}
520
521static Cursor maybeLexNewline(Cursor C, MIToken &Token) {
522  if (!isNewlineChar(C.peek()))
523    return None;
524  auto Range = C;
525  C.advance();
526  Token.reset(MIToken::Newline, Range.upto(C));
527  return C;
528}
529
530static Cursor maybeLexEscapedIRValue(
531    Cursor C, MIToken &Token,
532    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
533  if (C.peek() != '`')
534    return None;
535  auto Range = C;
536  C.advance();
537  auto StrRange = C;
538  while (C.peek() != '`') {
539    if (C.isEOF() || isNewlineChar(C.peek())) {
540      ErrorCallback(
541          C.location(),
542          "end of machine instruction reached before the closing '`'");
543      Token.reset(MIToken::Error, Range.remaining());
544      return C;
545    }
546    C.advance();
547  }
548  StringRef Value = StrRange.upto(C);
549  C.advance();
550  Token.reset(MIToken::QuotedIRValue, Range.upto(C)).setStringValue(Value);
551  return C;
552}
553
554StringRef llvm::lexMIToken(
555    StringRef Source, MIToken &Token,
556    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
557  auto C = skipComment(skipWhitespace(Cursor(Source)));
558  if (C.isEOF()) {
559    Token.reset(MIToken::Eof, C.remaining());
560    return C.remaining();
561  }
562
563  if (Cursor R = maybeLexIntegerType(C, Token))
564    return R.remaining();
565  if (Cursor R = maybeLexMachineBasicBlock(C, Token, ErrorCallback))
566    return R.remaining();
567  if (Cursor R = maybeLexIdentifier(C, Token))
568    return R.remaining();
569  if (Cursor R = maybeLexJumpTableIndex(C, Token))
570    return R.remaining();
571  if (Cursor R = maybeLexStackObject(C, Token))
572    return R.remaining();
573  if (Cursor R = maybeLexFixedStackObject(C, Token))
574    return R.remaining();
575  if (Cursor R = maybeLexConstantPoolItem(C, Token))
576    return R.remaining();
577  if (Cursor R = maybeLexIRBlock(C, Token, ErrorCallback))
578    return R.remaining();
579  if (Cursor R = maybeLexIRValue(C, Token, ErrorCallback))
580    return R.remaining();
581  if (Cursor R = maybeLexRegister(C, Token))
582    return R.remaining();
583  if (Cursor R = maybeLexGlobalValue(C, Token, ErrorCallback))
584    return R.remaining();
585  if (Cursor R = maybeLexExternalSymbol(C, Token, ErrorCallback))
586    return R.remaining();
587  if (Cursor R = maybeLexHexFloatingPointLiteral(C, Token))
588    return R.remaining();
589  if (Cursor R = maybeLexNumericalLiteral(C, Token))
590    return R.remaining();
591  if (Cursor R = maybeLexExlaim(C, Token, ErrorCallback))
592    return R.remaining();
593  if (Cursor R = maybeLexSymbol(C, Token))
594    return R.remaining();
595  if (Cursor R = maybeLexNewline(C, Token))
596    return R.remaining();
597  if (Cursor R = maybeLexEscapedIRValue(C, Token, ErrorCallback))
598    return R.remaining();
599
600  Token.reset(MIToken::Error, C.remaining());
601  ErrorCallback(C.location(),
602                Twine("unexpected character '") + Twine(C.peek()) + "'");
603  return C.remaining();
604}
605