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 (isblank(C.peek()))
83     C.advance();
84   return C;
85 }
86 
87 static bool isNewlineChar(char C) { return C == '\n' || C == '\r'; }
88 
89 /// Skip a line comment and return the updated cursor.
90 static 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]
100 static 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.
108 static 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: \"[^\"]*\"
136 static 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 
152 static 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 
175 static 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 
186 static 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("dead", MIToken::kw_dead)
192       .Case("killed", MIToken::kw_killed)
193       .Case("undef", MIToken::kw_undef)
194       .Case("early-clobber", MIToken::kw_early_clobber)
195       .Case("debug-use", MIToken::kw_debug_use)
196       .Case("frame-setup", MIToken::kw_frame_setup)
197       .Case("debug-location", MIToken::kw_debug_location)
198       .Case(".cfi_offset", MIToken::kw_cfi_offset)
199       .Case(".cfi_def_cfa_register", MIToken::kw_cfi_def_cfa_register)
200       .Case(".cfi_def_cfa_offset", MIToken::kw_cfi_def_cfa_offset)
201       .Case(".cfi_def_cfa", MIToken::kw_cfi_def_cfa)
202       .Case("blockaddress", MIToken::kw_blockaddress)
203       .Case("target-index", MIToken::kw_target_index)
204       .Case("half", MIToken::kw_half)
205       .Case("float", MIToken::kw_float)
206       .Case("double", MIToken::kw_double)
207       .Case("x86_fp80", MIToken::kw_x86_fp80)
208       .Case("fp128", MIToken::kw_fp128)
209       .Case("ppc_fp128", MIToken::kw_ppc_fp128)
210       .Case("target-flags", MIToken::kw_target_flags)
211       .Case("volatile", MIToken::kw_volatile)
212       .Case("non-temporal", MIToken::kw_non_temporal)
213       .Case("invariant", MIToken::kw_invariant)
214       .Case("align", MIToken::kw_align)
215       .Case("stack", MIToken::kw_stack)
216       .Case("got", MIToken::kw_got)
217       .Case("jump-table", MIToken::kw_jump_table)
218       .Case("constant-pool", MIToken::kw_constant_pool)
219       .Case("liveout", MIToken::kw_liveout)
220       .Case("address-taken", MIToken::kw_address_taken)
221       .Case("landing-pad", MIToken::kw_landing_pad)
222       .Case("liveins", MIToken::kw_liveins)
223       .Case("successors", MIToken::kw_successors)
224       .Default(MIToken::Identifier);
225 }
226 
227 static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) {
228   if (!isalpha(C.peek()) && C.peek() != '_' && C.peek() != '.')
229     return None;
230   auto Range = C;
231   while (isIdentifierChar(C.peek()))
232     C.advance();
233   auto Identifier = Range.upto(C);
234   Token.reset(getIdentifierKind(Identifier), Identifier)
235       .setStringValue(Identifier);
236   return C;
237 }
238 
239 static Cursor maybeLexMachineBasicBlock(
240     Cursor C, MIToken &Token,
241     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
242   bool IsReference = C.remaining().startswith("%bb.");
243   if (!IsReference && !C.remaining().startswith("bb."))
244     return None;
245   auto Range = C;
246   unsigned PrefixLength = IsReference ? 4 : 3;
247   C.advance(PrefixLength); // Skip '%bb.' or 'bb.'
248   if (!isdigit(C.peek())) {
249     Token.reset(MIToken::Error, C.remaining());
250     ErrorCallback(C.location(), "expected a number after '%bb.'");
251     return C;
252   }
253   auto NumberRange = C;
254   while (isdigit(C.peek()))
255     C.advance();
256   StringRef Number = NumberRange.upto(C);
257   unsigned StringOffset = PrefixLength + Number.size(); // Drop '%bb.<id>'
258   if (C.peek() == '.') {
259     C.advance(); // Skip '.'
260     ++StringOffset;
261     while (isIdentifierChar(C.peek()))
262       C.advance();
263   }
264   Token.reset(IsReference ? MIToken::MachineBasicBlock
265                           : MIToken::MachineBasicBlockLabel,
266               Range.upto(C))
267       .setIntegerValue(APSInt(Number))
268       .setStringValue(Range.upto(C).drop_front(StringOffset));
269   return C;
270 }
271 
272 static Cursor maybeLexIndex(Cursor C, MIToken &Token, StringRef Rule,
273                             MIToken::TokenKind Kind) {
274   if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
275     return None;
276   auto Range = C;
277   C.advance(Rule.size());
278   auto NumberRange = C;
279   while (isdigit(C.peek()))
280     C.advance();
281   Token.reset(Kind, Range.upto(C)).setIntegerValue(APSInt(NumberRange.upto(C)));
282   return C;
283 }
284 
285 static Cursor maybeLexIndexAndName(Cursor C, MIToken &Token, StringRef Rule,
286                                    MIToken::TokenKind Kind) {
287   if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
288     return None;
289   auto Range = C;
290   C.advance(Rule.size());
291   auto NumberRange = C;
292   while (isdigit(C.peek()))
293     C.advance();
294   StringRef Number = NumberRange.upto(C);
295   unsigned StringOffset = Rule.size() + Number.size();
296   if (C.peek() == '.') {
297     C.advance();
298     ++StringOffset;
299     while (isIdentifierChar(C.peek()))
300       C.advance();
301   }
302   Token.reset(Kind, Range.upto(C))
303       .setIntegerValue(APSInt(Number))
304       .setStringValue(Range.upto(C).drop_front(StringOffset));
305   return C;
306 }
307 
308 static Cursor maybeLexJumpTableIndex(Cursor C, MIToken &Token) {
309   return maybeLexIndex(C, Token, "%jump-table.", MIToken::JumpTableIndex);
310 }
311 
312 static Cursor maybeLexStackObject(Cursor C, MIToken &Token) {
313   return maybeLexIndexAndName(C, Token, "%stack.", MIToken::StackObject);
314 }
315 
316 static Cursor maybeLexFixedStackObject(Cursor C, MIToken &Token) {
317   return maybeLexIndex(C, Token, "%fixed-stack.", MIToken::FixedStackObject);
318 }
319 
320 static Cursor maybeLexConstantPoolItem(Cursor C, MIToken &Token) {
321   return maybeLexIndex(C, Token, "%const.", MIToken::ConstantPoolItem);
322 }
323 
324 static Cursor maybeLexIRBlock(
325     Cursor C, MIToken &Token,
326     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
327   const StringRef Rule = "%ir-block.";
328   if (!C.remaining().startswith(Rule))
329     return None;
330   if (isdigit(C.peek(Rule.size())))
331     return maybeLexIndex(C, Token, Rule, MIToken::IRBlock);
332   return lexName(C, Token, MIToken::NamedIRBlock, Rule.size(), ErrorCallback);
333 }
334 
335 static Cursor maybeLexIRValue(
336     Cursor C, MIToken &Token,
337     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
338   const StringRef Rule = "%ir.";
339   if (!C.remaining().startswith(Rule))
340     return None;
341   return lexName(C, Token, MIToken::NamedIRValue, Rule.size(), ErrorCallback);
342 }
343 
344 static Cursor lexVirtualRegister(Cursor C, MIToken &Token) {
345   auto Range = C;
346   C.advance(); // Skip '%'
347   auto NumberRange = C;
348   while (isdigit(C.peek()))
349     C.advance();
350   Token.reset(MIToken::VirtualRegister, Range.upto(C))
351       .setIntegerValue(APSInt(NumberRange.upto(C)));
352   return C;
353 }
354 
355 static Cursor maybeLexRegister(Cursor C, MIToken &Token) {
356   if (C.peek() != '%')
357     return None;
358   if (isdigit(C.peek(1)))
359     return lexVirtualRegister(C, Token);
360   auto Range = C;
361   C.advance(); // Skip '%'
362   while (isIdentifierChar(C.peek()))
363     C.advance();
364   Token.reset(MIToken::NamedRegister, Range.upto(C))
365       .setStringValue(Range.upto(C).drop_front(1)); // Drop the '%'
366   return C;
367 }
368 
369 static Cursor maybeLexGlobalValue(
370     Cursor C, MIToken &Token,
371     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
372   if (C.peek() != '@')
373     return None;
374   if (!isdigit(C.peek(1)))
375     return lexName(C, Token, MIToken::NamedGlobalValue, /*PrefixLength=*/1,
376                    ErrorCallback);
377   auto Range = C;
378   C.advance(1); // Skip the '@'
379   auto NumberRange = C;
380   while (isdigit(C.peek()))
381     C.advance();
382   Token.reset(MIToken::GlobalValue, Range.upto(C))
383       .setIntegerValue(APSInt(NumberRange.upto(C)));
384   return C;
385 }
386 
387 static Cursor maybeLexExternalSymbol(
388     Cursor C, MIToken &Token,
389     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
390   if (C.peek() != '$')
391     return None;
392   return lexName(C, Token, MIToken::ExternalSymbol, /*PrefixLength=*/1,
393                  ErrorCallback);
394 }
395 
396 static bool isValidHexFloatingPointPrefix(char C) {
397   return C == 'H' || C == 'K' || C == 'L' || C == 'M';
398 }
399 
400 static Cursor maybeLexHexFloatingPointLiteral(Cursor C, MIToken &Token) {
401   if (C.peek() != '0' || C.peek(1) != 'x')
402     return None;
403   Cursor Range = C;
404   C.advance(2); // Skip '0x'
405   if (isValidHexFloatingPointPrefix(C.peek()))
406     C.advance();
407   while (isxdigit(C.peek()))
408     C.advance();
409   Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
410   return C;
411 }
412 
413 static Cursor lexFloatingPointLiteral(Cursor Range, Cursor C, MIToken &Token) {
414   C.advance();
415   // Skip over [0-9]*([eE][-+]?[0-9]+)?
416   while (isdigit(C.peek()))
417     C.advance();
418   if ((C.peek() == 'e' || C.peek() == 'E') &&
419       (isdigit(C.peek(1)) ||
420        ((C.peek(1) == '-' || C.peek(1) == '+') && isdigit(C.peek(2))))) {
421     C.advance(2);
422     while (isdigit(C.peek()))
423       C.advance();
424   }
425   Token.reset(MIToken::FloatingPointLiteral, Range.upto(C));
426   return C;
427 }
428 
429 static Cursor maybeLexNumericalLiteral(Cursor C, MIToken &Token) {
430   if (!isdigit(C.peek()) && (C.peek() != '-' || !isdigit(C.peek(1))))
431     return None;
432   auto Range = C;
433   C.advance();
434   while (isdigit(C.peek()))
435     C.advance();
436   if (C.peek() == '.')
437     return lexFloatingPointLiteral(Range, C, Token);
438   StringRef StrVal = Range.upto(C);
439   Token.reset(MIToken::IntegerLiteral, StrVal).setIntegerValue(APSInt(StrVal));
440   return C;
441 }
442 
443 static MIToken::TokenKind symbolToken(char C) {
444   switch (C) {
445   case ',':
446     return MIToken::comma;
447   case '=':
448     return MIToken::equal;
449   case ':':
450     return MIToken::colon;
451   case '!':
452     return MIToken::exclaim;
453   case '(':
454     return MIToken::lparen;
455   case ')':
456     return MIToken::rparen;
457   case '+':
458     return MIToken::plus;
459   case '-':
460     return MIToken::minus;
461   default:
462     return MIToken::Error;
463   }
464 }
465 
466 static Cursor maybeLexSymbol(Cursor C, MIToken &Token) {
467   MIToken::TokenKind Kind;
468   unsigned Length = 1;
469   if (C.peek() == ':' && C.peek(1) == ':') {
470     Kind = MIToken::coloncolon;
471     Length = 2;
472   } else
473     Kind = symbolToken(C.peek());
474   if (Kind == MIToken::Error)
475     return None;
476   auto Range = C;
477   C.advance(Length);
478   Token.reset(Kind, Range.upto(C));
479   return C;
480 }
481 
482 static Cursor maybeLexNewline(Cursor C, MIToken &Token) {
483   if (!isNewlineChar(C.peek()))
484     return None;
485   auto Range = C;
486   C.advance();
487   Token.reset(MIToken::Newline, Range.upto(C));
488   return C;
489 }
490 
491 StringRef llvm::lexMIToken(
492     StringRef Source, MIToken &Token,
493     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
494   auto C = skipComment(skipWhitespace(Cursor(Source)));
495   if (C.isEOF()) {
496     Token.reset(MIToken::Eof, C.remaining());
497     return C.remaining();
498   }
499 
500   if (Cursor R = maybeLexIntegerType(C, Token))
501     return R.remaining();
502   if (Cursor R = maybeLexMachineBasicBlock(C, Token, ErrorCallback))
503     return R.remaining();
504   if (Cursor R = maybeLexIdentifier(C, Token))
505     return R.remaining();
506   if (Cursor R = maybeLexJumpTableIndex(C, Token))
507     return R.remaining();
508   if (Cursor R = maybeLexStackObject(C, Token))
509     return R.remaining();
510   if (Cursor R = maybeLexFixedStackObject(C, Token))
511     return R.remaining();
512   if (Cursor R = maybeLexConstantPoolItem(C, Token))
513     return R.remaining();
514   if (Cursor R = maybeLexIRBlock(C, Token, ErrorCallback))
515     return R.remaining();
516   if (Cursor R = maybeLexIRValue(C, Token, ErrorCallback))
517     return R.remaining();
518   if (Cursor R = maybeLexRegister(C, Token))
519     return R.remaining();
520   if (Cursor R = maybeLexGlobalValue(C, Token, ErrorCallback))
521     return R.remaining();
522   if (Cursor R = maybeLexExternalSymbol(C, Token, ErrorCallback))
523     return R.remaining();
524   if (Cursor R = maybeLexHexFloatingPointLiteral(C, Token))
525     return R.remaining();
526   if (Cursor R = maybeLexNumericalLiteral(C, Token))
527     return R.remaining();
528   if (Cursor R = maybeLexSymbol(C, Token))
529     return R.remaining();
530   if (Cursor R = maybeLexNewline(C, Token))
531     return R.remaining();
532 
533   Token.reset(MIToken::Error, C.remaining());
534   ErrorCallback(C.location(),
535                 Twine("unexpected character '") + Twine(C.peek()) + "'");
536   return C.remaining();
537 }
538