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