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/StringSwitch.h"
16 #include "llvm/ADT/Twine.h"
17 #include <cctype>
18 
19 using namespace llvm;
20 
21 namespace {
22 
23 /// This class provides a way to iterate and get characters from the source
24 /// string.
25 class Cursor {
26   const char *Ptr;
27   const char *End;
28 
29 public:
30   Cursor(NoneType) : Ptr(nullptr), End(nullptr) {}
31 
32   explicit Cursor(StringRef Str) {
33     Ptr = Str.data();
34     End = Ptr + Str.size();
35   }
36 
37   bool isEOF() const { return Ptr == End; }
38 
39   char peek(int I = 0) const { return End - Ptr <= I ? 0 : Ptr[I]; }
40 
41   void advance(unsigned I = 1) { Ptr += I; }
42 
43   StringRef remaining() const { return StringRef(Ptr, End - Ptr); }
44 
45   StringRef upto(Cursor C) const {
46     assert(C.Ptr >= Ptr && C.Ptr <= End);
47     return StringRef(Ptr, C.Ptr - Ptr);
48   }
49 
50   StringRef::iterator location() const { return Ptr; }
51 
52   operator bool() const { return Ptr != nullptr; }
53 };
54 
55 } // end anonymous namespace
56 
57 /// Skip the leading whitespace characters and return the updated cursor.
58 static Cursor skipWhitespace(Cursor C) {
59   while (isspace(C.peek()))
60     C.advance();
61   return C;
62 }
63 
64 /// Return true if the given character satisfies the following regular
65 /// expression: [-a-zA-Z$._0-9]
66 static bool isIdentifierChar(char C) {
67   return isalpha(C) || isdigit(C) || C == '_' || C == '-' || C == '.' ||
68          C == '$';
69 }
70 
71 static MIToken::TokenKind getIdentifierKind(StringRef Identifier) {
72   return StringSwitch<MIToken::TokenKind>(Identifier)
73       .Case("_", MIToken::underscore)
74       .Case("implicit", MIToken::kw_implicit)
75       .Case("implicit-def", MIToken::kw_implicit_define)
76       .Case("dead", MIToken::kw_dead)
77       .Case("killed", MIToken::kw_killed)
78       .Case("undef", MIToken::kw_undef)
79       .Case("frame-setup", MIToken::kw_frame_setup)
80       .Default(MIToken::Identifier);
81 }
82 
83 static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) {
84   if (!isalpha(C.peek()) && C.peek() != '_')
85     return None;
86   auto Range = C;
87   while (isIdentifierChar(C.peek()))
88     C.advance();
89   auto Identifier = Range.upto(C);
90   Token = MIToken(getIdentifierKind(Identifier), Identifier);
91   return C;
92 }
93 
94 static Cursor maybeLexMachineBasicBlock(
95     Cursor C, MIToken &Token,
96     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
97   if (!C.remaining().startswith("%bb."))
98     return None;
99   auto Range = C;
100   C.advance(4); // Skip '%bb.'
101   if (!isdigit(C.peek())) {
102     Token = MIToken(MIToken::Error, C.remaining());
103     ErrorCallback(C.location(), "expected a number after '%bb.'");
104     return C;
105   }
106   auto NumberRange = C;
107   while (isdigit(C.peek()))
108     C.advance();
109   StringRef Number = NumberRange.upto(C);
110   unsigned StringOffset = 4 + Number.size(); // Drop '%bb.<id>'
111   if (C.peek() == '.') {
112     C.advance(); // Skip '.'
113     ++StringOffset;
114     while (isIdentifierChar(C.peek()))
115       C.advance();
116   }
117   Token = MIToken(MIToken::MachineBasicBlock, Range.upto(C), APSInt(Number),
118                   StringOffset);
119   return C;
120 }
121 
122 static Cursor maybeLexIndex(Cursor C, MIToken &Token, StringRef Rule,
123                             MIToken::TokenKind Kind) {
124   if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
125     return None;
126   auto Range = C;
127   C.advance(Rule.size());
128   auto NumberRange = C;
129   while (isdigit(C.peek()))
130     C.advance();
131   Token = MIToken(Kind, Range.upto(C), APSInt(NumberRange.upto(C)));
132   return C;
133 }
134 
135 static Cursor maybeLexIndexAndName(Cursor C, MIToken &Token, StringRef Rule,
136                                    MIToken::TokenKind Kind) {
137   if (!C.remaining().startswith(Rule) || !isdigit(C.peek(Rule.size())))
138     return None;
139   auto Range = C;
140   C.advance(Rule.size());
141   auto NumberRange = C;
142   while (isdigit(C.peek()))
143     C.advance();
144   StringRef Number = NumberRange.upto(C);
145   unsigned StringOffset = Rule.size() + Number.size();
146   if (C.peek() == '.') {
147     C.advance();
148     ++StringOffset;
149     while (isIdentifierChar(C.peek()))
150       C.advance();
151   }
152   Token = MIToken(Kind, Range.upto(C), APSInt(Number), StringOffset);
153   return C;
154 }
155 
156 static Cursor maybeLexJumpTableIndex(Cursor C, MIToken &Token) {
157   return maybeLexIndex(C, Token, "%jump-table.", MIToken::JumpTableIndex);
158 }
159 
160 static Cursor maybeLexStackObject(Cursor C, MIToken &Token) {
161   return maybeLexIndexAndName(C, Token, "%stack.", MIToken::StackObject);
162 }
163 
164 static Cursor maybeLexFixedStackObject(Cursor C, MIToken &Token) {
165   return maybeLexIndex(C, Token, "%fixed-stack.", MIToken::FixedStackObject);
166 }
167 
168 static Cursor lexVirtualRegister(Cursor C, MIToken &Token) {
169   auto Range = C;
170   C.advance(); // Skip '%'
171   auto NumberRange = C;
172   while (isdigit(C.peek()))
173     C.advance();
174   Token = MIToken(MIToken::VirtualRegister, Range.upto(C),
175                   APSInt(NumberRange.upto(C)));
176   return C;
177 }
178 
179 static Cursor maybeLexRegister(Cursor C, MIToken &Token) {
180   if (C.peek() != '%')
181     return None;
182   if (isdigit(C.peek(1)))
183     return lexVirtualRegister(C, Token);
184   auto Range = C;
185   C.advance(); // Skip '%'
186   while (isIdentifierChar(C.peek()))
187     C.advance();
188   Token = MIToken(MIToken::NamedRegister, Range.upto(C),
189                   /*StringOffset=*/1); // Drop the '%'
190   return C;
191 }
192 
193 static Cursor maybeLexGlobalValue(Cursor C, MIToken &Token) {
194   if (C.peek() != '@')
195     return None;
196   auto Range = C;
197   C.advance(); // Skip the '@'
198   // TODO: add support for quoted names.
199   if (!isdigit(C.peek())) {
200     while (isIdentifierChar(C.peek()))
201       C.advance();
202     Token = MIToken(MIToken::NamedGlobalValue, Range.upto(C),
203                     /*StringOffset=*/1); // Drop the '@'
204     return C;
205   }
206   auto NumberRange = C;
207   while (isdigit(C.peek()))
208     C.advance();
209   Token =
210       MIToken(MIToken::GlobalValue, Range.upto(C), APSInt(NumberRange.upto(C)));
211   return C;
212 }
213 
214 static Cursor maybeLexIntegerLiteral(Cursor C, MIToken &Token) {
215   if (!isdigit(C.peek()) && (C.peek() != '-' || !isdigit(C.peek(1))))
216     return None;
217   auto Range = C;
218   C.advance();
219   while (isdigit(C.peek()))
220     C.advance();
221   StringRef StrVal = Range.upto(C);
222   Token = MIToken(MIToken::IntegerLiteral, StrVal, APSInt(StrVal));
223   return C;
224 }
225 
226 static MIToken::TokenKind symbolToken(char C) {
227   switch (C) {
228   case ',':
229     return MIToken::comma;
230   case '=':
231     return MIToken::equal;
232   case ':':
233     return MIToken::colon;
234   default:
235     return MIToken::Error;
236   }
237 }
238 
239 static Cursor maybeLexSymbol(Cursor C, MIToken &Token) {
240   auto Kind = symbolToken(C.peek());
241   if (Kind == MIToken::Error)
242     return None;
243   auto Range = C;
244   C.advance();
245   Token = MIToken(Kind, Range.upto(C));
246   return C;
247 }
248 
249 StringRef llvm::lexMIToken(
250     StringRef Source, MIToken &Token,
251     function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
252   auto C = skipWhitespace(Cursor(Source));
253   if (C.isEOF()) {
254     Token = MIToken(MIToken::Eof, C.remaining());
255     return C.remaining();
256   }
257 
258   if (Cursor R = maybeLexIdentifier(C, Token))
259     return R.remaining();
260   if (Cursor R = maybeLexMachineBasicBlock(C, Token, ErrorCallback))
261     return R.remaining();
262   if (Cursor R = maybeLexJumpTableIndex(C, Token))
263     return R.remaining();
264   if (Cursor R = maybeLexStackObject(C, Token))
265     return R.remaining();
266   if (Cursor R = maybeLexFixedStackObject(C, Token))
267     return R.remaining();
268   if (Cursor R = maybeLexRegister(C, Token))
269     return R.remaining();
270   if (Cursor R = maybeLexGlobalValue(C, Token))
271     return R.remaining();
272   if (Cursor R = maybeLexIntegerLiteral(C, Token))
273     return R.remaining();
274   if (Cursor R = maybeLexSymbol(C, Token))
275     return R.remaining();
276 
277   Token = MIToken(MIToken::Error, C.remaining());
278   ErrorCallback(C.location(),
279                 Twine("unexpected character '") + Twine(C.peek()) + "'");
280   return C.remaining();
281 }
282