1 //===--- RuntimeDyldChecker.cpp - RuntimeDyld tester framework --*- C++ -*-===//
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 #include "llvm/ExecutionEngine/RuntimeDyldChecker.h"
11 #include "RuntimeDyldCheckerImpl.h"
12 #include "RuntimeDyldImpl.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/MC/MCContext.h"
15 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
16 #include "llvm/MC/MCInst.h"
17 #include "llvm/Support/MSVCErrorWorkarounds.h"
18 #include "llvm/Support/Path.h"
19 #include <cctype>
20 #include <future>
21 #include <memory>
22 #include <utility>
23 
24 #define DEBUG_TYPE "rtdyld"
25 
26 using namespace llvm;
27 
28 namespace llvm {
29 
30 // Helper class that implements the language evaluated by RuntimeDyldChecker.
31 class RuntimeDyldCheckerExprEval {
32 public:
33   RuntimeDyldCheckerExprEval(const RuntimeDyldCheckerImpl &Checker,
34                              raw_ostream &ErrStream)
35       : Checker(Checker) {}
36 
37   bool evaluate(StringRef Expr) const {
38     // Expect equality expression of the form 'LHS = RHS'.
39     Expr = Expr.trim();
40     size_t EQIdx = Expr.find('=');
41 
42     ParseContext OutsideLoad(false);
43 
44     // Evaluate LHS.
45     StringRef LHSExpr = Expr.substr(0, EQIdx).rtrim();
46     StringRef RemainingExpr;
47     EvalResult LHSResult;
48     std::tie(LHSResult, RemainingExpr) =
49         evalComplexExpr(evalSimpleExpr(LHSExpr, OutsideLoad), OutsideLoad);
50     if (LHSResult.hasError())
51       return handleError(Expr, LHSResult);
52     if (RemainingExpr != "")
53       return handleError(Expr, unexpectedToken(RemainingExpr, LHSExpr, ""));
54 
55     // Evaluate RHS.
56     StringRef RHSExpr = Expr.substr(EQIdx + 1).ltrim();
57     EvalResult RHSResult;
58     std::tie(RHSResult, RemainingExpr) =
59         evalComplexExpr(evalSimpleExpr(RHSExpr, OutsideLoad), OutsideLoad);
60     if (RHSResult.hasError())
61       return handleError(Expr, RHSResult);
62     if (RemainingExpr != "")
63       return handleError(Expr, unexpectedToken(RemainingExpr, RHSExpr, ""));
64 
65     if (LHSResult.getValue() != RHSResult.getValue()) {
66       Checker.ErrStream << "Expression '" << Expr << "' is false: "
67                         << format("0x%" PRIx64, LHSResult.getValue())
68                         << " != " << format("0x%" PRIx64, RHSResult.getValue())
69                         << "\n";
70       return false;
71     }
72     return true;
73   }
74 
75 private:
76   // RuntimeDyldCheckerExprEval requires some context when parsing exprs. In
77   // particular, it needs to know whether a symbol is being evaluated in the
78   // context of a load, in which case we want the linker's local address for
79   // the symbol, or outside of a load, in which case we want the symbol's
80   // address in the remote target.
81 
82   struct ParseContext {
83     bool IsInsideLoad;
84     ParseContext(bool IsInsideLoad) : IsInsideLoad(IsInsideLoad) {}
85   };
86 
87   const RuntimeDyldCheckerImpl &Checker;
88 
89   enum class BinOpToken : unsigned {
90     Invalid,
91     Add,
92     Sub,
93     BitwiseAnd,
94     BitwiseOr,
95     ShiftLeft,
96     ShiftRight
97   };
98 
99   class EvalResult {
100   public:
101     EvalResult() : Value(0), ErrorMsg("") {}
102     EvalResult(uint64_t Value) : Value(Value), ErrorMsg("") {}
103     EvalResult(std::string ErrorMsg)
104         : Value(0), ErrorMsg(std::move(ErrorMsg)) {}
105     uint64_t getValue() const { return Value; }
106     bool hasError() const { return ErrorMsg != ""; }
107     const std::string &getErrorMsg() const { return ErrorMsg; }
108 
109   private:
110     uint64_t Value;
111     std::string ErrorMsg;
112   };
113 
114   StringRef getTokenForError(StringRef Expr) const {
115     if (Expr.empty())
116       return "";
117 
118     StringRef Token, Remaining;
119     if (isalpha(Expr[0]))
120       std::tie(Token, Remaining) = parseSymbol(Expr);
121     else if (isdigit(Expr[0]))
122       std::tie(Token, Remaining) = parseNumberString(Expr);
123     else {
124       unsigned TokLen = 1;
125       if (Expr.startswith("<<") || Expr.startswith(">>"))
126         TokLen = 2;
127       Token = Expr.substr(0, TokLen);
128     }
129     return Token;
130   }
131 
132   EvalResult unexpectedToken(StringRef TokenStart, StringRef SubExpr,
133                              StringRef ErrText) const {
134     std::string ErrorMsg("Encountered unexpected token '");
135     ErrorMsg += getTokenForError(TokenStart);
136     if (SubExpr != "") {
137       ErrorMsg += "' while parsing subexpression '";
138       ErrorMsg += SubExpr;
139     }
140     ErrorMsg += "'";
141     if (ErrText != "") {
142       ErrorMsg += " ";
143       ErrorMsg += ErrText;
144     }
145     return EvalResult(std::move(ErrorMsg));
146   }
147 
148   bool handleError(StringRef Expr, const EvalResult &R) const {
149     assert(R.hasError() && "Not an error result.");
150     Checker.ErrStream << "Error evaluating expression '" << Expr
151                       << "': " << R.getErrorMsg() << "\n";
152     return false;
153   }
154 
155   std::pair<BinOpToken, StringRef> parseBinOpToken(StringRef Expr) const {
156     if (Expr.empty())
157       return std::make_pair(BinOpToken::Invalid, "");
158 
159     // Handle the two 2-character tokens.
160     if (Expr.startswith("<<"))
161       return std::make_pair(BinOpToken::ShiftLeft, Expr.substr(2).ltrim());
162     if (Expr.startswith(">>"))
163       return std::make_pair(BinOpToken::ShiftRight, Expr.substr(2).ltrim());
164 
165     // Handle one-character tokens.
166     BinOpToken Op;
167     switch (Expr[0]) {
168     default:
169       return std::make_pair(BinOpToken::Invalid, Expr);
170     case '+':
171       Op = BinOpToken::Add;
172       break;
173     case '-':
174       Op = BinOpToken::Sub;
175       break;
176     case '&':
177       Op = BinOpToken::BitwiseAnd;
178       break;
179     case '|':
180       Op = BinOpToken::BitwiseOr;
181       break;
182     }
183 
184     return std::make_pair(Op, Expr.substr(1).ltrim());
185   }
186 
187   EvalResult computeBinOpResult(BinOpToken Op, const EvalResult &LHSResult,
188                                 const EvalResult &RHSResult) const {
189     switch (Op) {
190     default:
191       llvm_unreachable("Tried to evaluate unrecognized operation.");
192     case BinOpToken::Add:
193       return EvalResult(LHSResult.getValue() + RHSResult.getValue());
194     case BinOpToken::Sub:
195       return EvalResult(LHSResult.getValue() - RHSResult.getValue());
196     case BinOpToken::BitwiseAnd:
197       return EvalResult(LHSResult.getValue() & RHSResult.getValue());
198     case BinOpToken::BitwiseOr:
199       return EvalResult(LHSResult.getValue() | RHSResult.getValue());
200     case BinOpToken::ShiftLeft:
201       return EvalResult(LHSResult.getValue() << RHSResult.getValue());
202     case BinOpToken::ShiftRight:
203       return EvalResult(LHSResult.getValue() >> RHSResult.getValue());
204     }
205   }
206 
207   // Parse a symbol and return a (string, string) pair representing the symbol
208   // name and expression remaining to be parsed.
209   std::pair<StringRef, StringRef> parseSymbol(StringRef Expr) const {
210     size_t FirstNonSymbol = Expr.find_first_not_of("0123456789"
211                                                    "abcdefghijklmnopqrstuvwxyz"
212                                                    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
213                                                    ":_.$");
214     return std::make_pair(Expr.substr(0, FirstNonSymbol),
215                           Expr.substr(FirstNonSymbol).ltrim());
216   }
217 
218   // Evaluate a call to decode_operand. Decode the instruction operand at the
219   // given symbol and get the value of the requested operand.
220   // Returns an error if the instruction cannot be decoded, or the requested
221   // operand is not an immediate.
222   // On success, returns a pair containing the value of the operand, plus
223   // the expression remaining to be evaluated.
224   std::pair<EvalResult, StringRef> evalDecodeOperand(StringRef Expr) const {
225     if (!Expr.startswith("("))
226       return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
227     StringRef RemainingExpr = Expr.substr(1).ltrim();
228     StringRef Symbol;
229     std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
230 
231     if (!Checker.isSymbolValid(Symbol))
232       return std::make_pair(
233           EvalResult(("Cannot decode unknown symbol '" + Symbol + "'").str()),
234           "");
235 
236     if (!RemainingExpr.startswith(","))
237       return std::make_pair(
238           unexpectedToken(RemainingExpr, RemainingExpr, "expected ','"), "");
239     RemainingExpr = RemainingExpr.substr(1).ltrim();
240 
241     EvalResult OpIdxExpr;
242     std::tie(OpIdxExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
243     if (OpIdxExpr.hasError())
244       return std::make_pair(OpIdxExpr, "");
245 
246     if (!RemainingExpr.startswith(")"))
247       return std::make_pair(
248           unexpectedToken(RemainingExpr, RemainingExpr, "expected ')'"), "");
249     RemainingExpr = RemainingExpr.substr(1).ltrim();
250 
251     MCInst Inst;
252     uint64_t Size;
253     if (!decodeInst(Symbol, Inst, Size))
254       return std::make_pair(
255           EvalResult(("Couldn't decode instruction at '" + Symbol + "'").str()),
256           "");
257 
258     unsigned OpIdx = OpIdxExpr.getValue();
259     if (OpIdx >= Inst.getNumOperands()) {
260       std::string ErrMsg;
261       raw_string_ostream ErrMsgStream(ErrMsg);
262       ErrMsgStream << "Invalid operand index '" << format("%i", OpIdx)
263                    << "' for instruction '" << Symbol
264                    << "'. Instruction has only "
265                    << format("%i", Inst.getNumOperands())
266                    << " operands.\nInstruction is:\n  ";
267       Inst.dump_pretty(ErrMsgStream, Checker.InstPrinter);
268       return std::make_pair(EvalResult(ErrMsgStream.str()), "");
269     }
270 
271     const MCOperand &Op = Inst.getOperand(OpIdx);
272     if (!Op.isImm()) {
273       std::string ErrMsg;
274       raw_string_ostream ErrMsgStream(ErrMsg);
275       ErrMsgStream << "Operand '" << format("%i", OpIdx) << "' of instruction '"
276                    << Symbol << "' is not an immediate.\nInstruction is:\n  ";
277       Inst.dump_pretty(ErrMsgStream, Checker.InstPrinter);
278 
279       return std::make_pair(EvalResult(ErrMsgStream.str()), "");
280     }
281 
282     return std::make_pair(EvalResult(Op.getImm()), RemainingExpr);
283   }
284 
285   // Evaluate a call to next_pc.
286   // Decode the instruction at the given symbol and return the following program
287   // counter.
288   // Returns an error if the instruction cannot be decoded.
289   // On success, returns a pair containing the next PC, plus of the
290   // expression remaining to be evaluated.
291   std::pair<EvalResult, StringRef> evalNextPC(StringRef Expr,
292                                               ParseContext PCtx) const {
293     if (!Expr.startswith("("))
294       return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
295     StringRef RemainingExpr = Expr.substr(1).ltrim();
296     StringRef Symbol;
297     std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
298 
299     if (!Checker.isSymbolValid(Symbol))
300       return std::make_pair(
301           EvalResult(("Cannot decode unknown symbol '" + Symbol + "'").str()),
302           "");
303 
304     if (!RemainingExpr.startswith(")"))
305       return std::make_pair(
306           unexpectedToken(RemainingExpr, RemainingExpr, "expected ')'"), "");
307     RemainingExpr = RemainingExpr.substr(1).ltrim();
308 
309     MCInst Inst;
310     uint64_t InstSize;
311     if (!decodeInst(Symbol, Inst, InstSize))
312       return std::make_pair(
313           EvalResult(("Couldn't decode instruction at '" + Symbol + "'").str()),
314           "");
315 
316     uint64_t SymbolAddr = PCtx.IsInsideLoad
317                               ? Checker.getSymbolLocalAddr(Symbol)
318                               : Checker.getSymbolRemoteAddr(Symbol);
319     uint64_t NextPC = SymbolAddr + InstSize;
320 
321     return std::make_pair(EvalResult(NextPC), RemainingExpr);
322   }
323 
324   // Evaluate a call to stub_addr.
325   // Look up and return the address of the stub for the given
326   // (<file name>, <section name>, <symbol name>) tuple.
327   // On success, returns a pair containing the stub address, plus the expression
328   // remaining to be evaluated.
329   std::pair<EvalResult, StringRef> evalStubAddr(StringRef Expr,
330                                                 ParseContext PCtx) const {
331     if (!Expr.startswith("("))
332       return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
333     StringRef RemainingExpr = Expr.substr(1).ltrim();
334 
335     // Handle file-name specially, as it may contain characters that aren't
336     // legal for symbols.
337     StringRef FileName;
338     size_t ComaIdx = RemainingExpr.find(',');
339     FileName = RemainingExpr.substr(0, ComaIdx).rtrim();
340     RemainingExpr = RemainingExpr.substr(ComaIdx).ltrim();
341 
342     if (!RemainingExpr.startswith(","))
343       return std::make_pair(
344           unexpectedToken(RemainingExpr, Expr, "expected ','"), "");
345     RemainingExpr = RemainingExpr.substr(1).ltrim();
346 
347     StringRef SectionName;
348     std::tie(SectionName, RemainingExpr) = parseSymbol(RemainingExpr);
349 
350     if (!RemainingExpr.startswith(","))
351       return std::make_pair(
352           unexpectedToken(RemainingExpr, Expr, "expected ','"), "");
353     RemainingExpr = RemainingExpr.substr(1).ltrim();
354 
355     StringRef Symbol;
356     std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
357 
358     if (!RemainingExpr.startswith(")"))
359       return std::make_pair(
360           unexpectedToken(RemainingExpr, Expr, "expected ')'"), "");
361     RemainingExpr = RemainingExpr.substr(1).ltrim();
362 
363     uint64_t StubAddr;
364     std::string ErrorMsg = "";
365     std::tie(StubAddr, ErrorMsg) = Checker.getStubAddrFor(
366         FileName, SectionName, Symbol, PCtx.IsInsideLoad);
367 
368     if (ErrorMsg != "")
369       return std::make_pair(EvalResult(ErrorMsg), "");
370 
371     return std::make_pair(EvalResult(StubAddr), RemainingExpr);
372   }
373 
374   std::pair<EvalResult, StringRef> evalSectionAddr(StringRef Expr,
375                                                    ParseContext PCtx) const {
376     if (!Expr.startswith("("))
377       return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
378     StringRef RemainingExpr = Expr.substr(1).ltrim();
379 
380     // Handle file-name specially, as it may contain characters that aren't
381     // legal for symbols.
382     StringRef FileName;
383     size_t ComaIdx = RemainingExpr.find(',');
384     FileName = RemainingExpr.substr(0, ComaIdx).rtrim();
385     RemainingExpr = RemainingExpr.substr(ComaIdx).ltrim();
386 
387     if (!RemainingExpr.startswith(","))
388       return std::make_pair(
389           unexpectedToken(RemainingExpr, Expr, "expected ','"), "");
390     RemainingExpr = RemainingExpr.substr(1).ltrim();
391 
392     StringRef SectionName;
393     std::tie(SectionName, RemainingExpr) = parseSymbol(RemainingExpr);
394 
395     if (!RemainingExpr.startswith(")"))
396       return std::make_pair(
397           unexpectedToken(RemainingExpr, Expr, "expected ')'"), "");
398     RemainingExpr = RemainingExpr.substr(1).ltrim();
399 
400     uint64_t StubAddr;
401     std::string ErrorMsg = "";
402     std::tie(StubAddr, ErrorMsg) = Checker.getSectionAddr(
403         FileName, SectionName, PCtx.IsInsideLoad);
404 
405     if (ErrorMsg != "")
406       return std::make_pair(EvalResult(ErrorMsg), "");
407 
408     return std::make_pair(EvalResult(StubAddr), RemainingExpr);
409   }
410 
411   // Evaluate an identiefer expr, which may be a symbol, or a call to
412   // one of the builtin functions: get_insn_opcode or get_insn_length.
413   // Return the result, plus the expression remaining to be parsed.
414   std::pair<EvalResult, StringRef> evalIdentifierExpr(StringRef Expr,
415                                                       ParseContext PCtx) const {
416     StringRef Symbol;
417     StringRef RemainingExpr;
418     std::tie(Symbol, RemainingExpr) = parseSymbol(Expr);
419 
420     // Check for builtin function calls.
421     if (Symbol == "decode_operand")
422       return evalDecodeOperand(RemainingExpr);
423     else if (Symbol == "next_pc")
424       return evalNextPC(RemainingExpr, PCtx);
425     else if (Symbol == "stub_addr")
426       return evalStubAddr(RemainingExpr, PCtx);
427     else if (Symbol == "section_addr")
428       return evalSectionAddr(RemainingExpr, PCtx);
429 
430     if (!Checker.isSymbolValid(Symbol)) {
431       std::string ErrMsg("No known address for symbol '");
432       ErrMsg += Symbol;
433       ErrMsg += "'";
434       if (Symbol.startswith("L"))
435         ErrMsg += " (this appears to be an assembler local label - "
436                   " perhaps drop the 'L'?)";
437 
438       return std::make_pair(EvalResult(ErrMsg), "");
439     }
440 
441     // The value for the symbol depends on the context we're evaluating in:
442     // Inside a load this is the address in the linker's memory, outside a
443     // load it's the address in the target processes memory.
444     uint64_t Value = PCtx.IsInsideLoad ? Checker.getSymbolLocalAddr(Symbol)
445                                        : Checker.getSymbolRemoteAddr(Symbol);
446 
447     // Looks like a plain symbol reference.
448     return std::make_pair(EvalResult(Value), RemainingExpr);
449   }
450 
451   // Parse a number (hexadecimal or decimal) and return a (string, string)
452   // pair representing the number and the expression remaining to be parsed.
453   std::pair<StringRef, StringRef> parseNumberString(StringRef Expr) const {
454     size_t FirstNonDigit = StringRef::npos;
455     if (Expr.startswith("0x")) {
456       FirstNonDigit = Expr.find_first_not_of("0123456789abcdefABCDEF", 2);
457       if (FirstNonDigit == StringRef::npos)
458         FirstNonDigit = Expr.size();
459     } else {
460       FirstNonDigit = Expr.find_first_not_of("0123456789");
461       if (FirstNonDigit == StringRef::npos)
462         FirstNonDigit = Expr.size();
463     }
464     return std::make_pair(Expr.substr(0, FirstNonDigit),
465                           Expr.substr(FirstNonDigit));
466   }
467 
468   // Evaluate a constant numeric expression (hexadecimal or decimal) and
469   // return a pair containing the result, and the expression remaining to be
470   // evaluated.
471   std::pair<EvalResult, StringRef> evalNumberExpr(StringRef Expr) const {
472     StringRef ValueStr;
473     StringRef RemainingExpr;
474     std::tie(ValueStr, RemainingExpr) = parseNumberString(Expr);
475 
476     if (ValueStr.empty() || !isdigit(ValueStr[0]))
477       return std::make_pair(
478           unexpectedToken(RemainingExpr, RemainingExpr, "expected number"), "");
479     uint64_t Value;
480     ValueStr.getAsInteger(0, Value);
481     return std::make_pair(EvalResult(Value), RemainingExpr);
482   }
483 
484   // Evaluate an expression of the form "(<expr>)" and return a pair
485   // containing the result of evaluating <expr>, plus the expression
486   // remaining to be parsed.
487   std::pair<EvalResult, StringRef> evalParensExpr(StringRef Expr,
488                                                   ParseContext PCtx) const {
489     assert(Expr.startswith("(") && "Not a parenthesized expression");
490     EvalResult SubExprResult;
491     StringRef RemainingExpr;
492     std::tie(SubExprResult, RemainingExpr) =
493         evalComplexExpr(evalSimpleExpr(Expr.substr(1).ltrim(), PCtx), PCtx);
494     if (SubExprResult.hasError())
495       return std::make_pair(SubExprResult, "");
496     if (!RemainingExpr.startswith(")"))
497       return std::make_pair(
498           unexpectedToken(RemainingExpr, Expr, "expected ')'"), "");
499     RemainingExpr = RemainingExpr.substr(1).ltrim();
500     return std::make_pair(SubExprResult, RemainingExpr);
501   }
502 
503   // Evaluate an expression in one of the following forms:
504   //   *{<number>}<expr>
505   // Return a pair containing the result, plus the expression remaining to be
506   // parsed.
507   std::pair<EvalResult, StringRef> evalLoadExpr(StringRef Expr) const {
508     assert(Expr.startswith("*") && "Not a load expression");
509     StringRef RemainingExpr = Expr.substr(1).ltrim();
510 
511     // Parse read size.
512     if (!RemainingExpr.startswith("{"))
513       return std::make_pair(EvalResult("Expected '{' following '*'."), "");
514     RemainingExpr = RemainingExpr.substr(1).ltrim();
515     EvalResult ReadSizeExpr;
516     std::tie(ReadSizeExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
517     if (ReadSizeExpr.hasError())
518       return std::make_pair(ReadSizeExpr, RemainingExpr);
519     uint64_t ReadSize = ReadSizeExpr.getValue();
520     if (ReadSize < 1 || ReadSize > 8)
521       return std::make_pair(EvalResult("Invalid size for dereference."), "");
522     if (!RemainingExpr.startswith("}"))
523       return std::make_pair(EvalResult("Missing '}' for dereference."), "");
524     RemainingExpr = RemainingExpr.substr(1).ltrim();
525 
526     // Evaluate the expression representing the load address.
527     ParseContext LoadCtx(true);
528     EvalResult LoadAddrExprResult;
529     std::tie(LoadAddrExprResult, RemainingExpr) =
530         evalComplexExpr(evalSimpleExpr(RemainingExpr, LoadCtx), LoadCtx);
531 
532     if (LoadAddrExprResult.hasError())
533       return std::make_pair(LoadAddrExprResult, "");
534 
535     uint64_t LoadAddr = LoadAddrExprResult.getValue();
536 
537     return std::make_pair(
538         EvalResult(Checker.readMemoryAtAddr(LoadAddr, ReadSize)),
539         RemainingExpr);
540   }
541 
542   // Evaluate a "simple" expression. This is any expression that _isn't_ an
543   // un-parenthesized binary expression.
544   //
545   // "Simple" expressions can be optionally bit-sliced. See evalSlicedExpr.
546   //
547   // Returns a pair containing the result of the evaluation, plus the
548   // expression remaining to be parsed.
549   std::pair<EvalResult, StringRef> evalSimpleExpr(StringRef Expr,
550                                                   ParseContext PCtx) const {
551     EvalResult SubExprResult;
552     StringRef RemainingExpr;
553 
554     if (Expr.empty())
555       return std::make_pair(EvalResult("Unexpected end of expression"), "");
556 
557     if (Expr[0] == '(')
558       std::tie(SubExprResult, RemainingExpr) = evalParensExpr(Expr, PCtx);
559     else if (Expr[0] == '*')
560       std::tie(SubExprResult, RemainingExpr) = evalLoadExpr(Expr);
561     else if (isalpha(Expr[0]) || Expr[0] == '_')
562       std::tie(SubExprResult, RemainingExpr) = evalIdentifierExpr(Expr, PCtx);
563     else if (isdigit(Expr[0]))
564       std::tie(SubExprResult, RemainingExpr) = evalNumberExpr(Expr);
565     else
566       return std::make_pair(
567           unexpectedToken(Expr, Expr,
568                           "expected '(', '*', identifier, or number"), "");
569 
570     if (SubExprResult.hasError())
571       return std::make_pair(SubExprResult, RemainingExpr);
572 
573     // Evaluate bit-slice if present.
574     if (RemainingExpr.startswith("["))
575       std::tie(SubExprResult, RemainingExpr) =
576           evalSliceExpr(std::make_pair(SubExprResult, RemainingExpr));
577 
578     return std::make_pair(SubExprResult, RemainingExpr);
579   }
580 
581   // Evaluate a bit-slice of an expression.
582   // A bit-slice has the form "<expr>[high:low]". The result of evaluating a
583   // slice is the bits between high and low (inclusive) in the original
584   // expression, right shifted so that the "low" bit is in position 0 in the
585   // result.
586   // Returns a pair containing the result of the slice operation, plus the
587   // expression remaining to be parsed.
588   std::pair<EvalResult, StringRef>
589   evalSliceExpr(const std::pair<EvalResult, StringRef> &Ctx) const {
590     EvalResult SubExprResult;
591     StringRef RemainingExpr;
592     std::tie(SubExprResult, RemainingExpr) = Ctx;
593 
594     assert(RemainingExpr.startswith("[") && "Not a slice expr.");
595     RemainingExpr = RemainingExpr.substr(1).ltrim();
596 
597     EvalResult HighBitExpr;
598     std::tie(HighBitExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
599 
600     if (HighBitExpr.hasError())
601       return std::make_pair(HighBitExpr, RemainingExpr);
602 
603     if (!RemainingExpr.startswith(":"))
604       return std::make_pair(
605           unexpectedToken(RemainingExpr, RemainingExpr, "expected ':'"), "");
606     RemainingExpr = RemainingExpr.substr(1).ltrim();
607 
608     EvalResult LowBitExpr;
609     std::tie(LowBitExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
610 
611     if (LowBitExpr.hasError())
612       return std::make_pair(LowBitExpr, RemainingExpr);
613 
614     if (!RemainingExpr.startswith("]"))
615       return std::make_pair(
616           unexpectedToken(RemainingExpr, RemainingExpr, "expected ']'"), "");
617     RemainingExpr = RemainingExpr.substr(1).ltrim();
618 
619     unsigned HighBit = HighBitExpr.getValue();
620     unsigned LowBit = LowBitExpr.getValue();
621     uint64_t Mask = ((uint64_t)1 << (HighBit - LowBit + 1)) - 1;
622     uint64_t SlicedValue = (SubExprResult.getValue() >> LowBit) & Mask;
623     return std::make_pair(EvalResult(SlicedValue), RemainingExpr);
624   }
625 
626   // Evaluate a "complex" expression.
627   // Takes an already evaluated subexpression and checks for the presence of a
628   // binary operator, computing the result of the binary operation if one is
629   // found. Used to make arithmetic expressions left-associative.
630   // Returns a pair containing the ultimate result of evaluating the
631   // expression, plus the expression remaining to be evaluated.
632   std::pair<EvalResult, StringRef>
633   evalComplexExpr(const std::pair<EvalResult, StringRef> &LHSAndRemaining,
634                   ParseContext PCtx) const {
635     EvalResult LHSResult;
636     StringRef RemainingExpr;
637     std::tie(LHSResult, RemainingExpr) = LHSAndRemaining;
638 
639     // If there was an error, or there's nothing left to evaluate, return the
640     // result.
641     if (LHSResult.hasError() || RemainingExpr == "")
642       return std::make_pair(LHSResult, RemainingExpr);
643 
644     // Otherwise check if this is a binary expressioan.
645     BinOpToken BinOp;
646     std::tie(BinOp, RemainingExpr) = parseBinOpToken(RemainingExpr);
647 
648     // If this isn't a recognized expression just return.
649     if (BinOp == BinOpToken::Invalid)
650       return std::make_pair(LHSResult, RemainingExpr);
651 
652     // This is a recognized bin-op. Evaluate the RHS, then evaluate the binop.
653     EvalResult RHSResult;
654     std::tie(RHSResult, RemainingExpr) = evalSimpleExpr(RemainingExpr, PCtx);
655 
656     // If there was an error evaluating the RHS, return it.
657     if (RHSResult.hasError())
658       return std::make_pair(RHSResult, RemainingExpr);
659 
660     // This is a binary expression - evaluate and try to continue as a
661     // complex expr.
662     EvalResult ThisResult(computeBinOpResult(BinOp, LHSResult, RHSResult));
663 
664     return evalComplexExpr(std::make_pair(ThisResult, RemainingExpr), PCtx);
665   }
666 
667   bool decodeInst(StringRef Symbol, MCInst &Inst, uint64_t &Size) const {
668     MCDisassembler *Dis = Checker.Disassembler;
669     StringRef SectionMem = Checker.getSubsectionStartingAt(Symbol);
670     ArrayRef<uint8_t> SectionBytes(
671         reinterpret_cast<const uint8_t *>(SectionMem.data()),
672         SectionMem.size());
673 
674     MCDisassembler::DecodeStatus S =
675         Dis->getInstruction(Inst, Size, SectionBytes, 0, nulls(), nulls());
676 
677     return (S == MCDisassembler::Success);
678   }
679 };
680 }
681 
682 RuntimeDyldCheckerImpl::RuntimeDyldCheckerImpl(RuntimeDyld &RTDyld,
683                                                MCDisassembler *Disassembler,
684                                                MCInstPrinter *InstPrinter,
685                                                raw_ostream &ErrStream)
686     : RTDyld(RTDyld), Disassembler(Disassembler), InstPrinter(InstPrinter),
687       ErrStream(ErrStream) {
688   RTDyld.Checker = this;
689 }
690 
691 bool RuntimeDyldCheckerImpl::check(StringRef CheckExpr) const {
692   CheckExpr = CheckExpr.trim();
693   LLVM_DEBUG(dbgs() << "RuntimeDyldChecker: Checking '" << CheckExpr
694                     << "'...\n");
695   RuntimeDyldCheckerExprEval P(*this, ErrStream);
696   bool Result = P.evaluate(CheckExpr);
697   (void)Result;
698   LLVM_DEBUG(dbgs() << "RuntimeDyldChecker: '" << CheckExpr << "' "
699                     << (Result ? "passed" : "FAILED") << ".\n");
700   return Result;
701 }
702 
703 bool RuntimeDyldCheckerImpl::checkAllRulesInBuffer(StringRef RulePrefix,
704                                                    MemoryBuffer *MemBuf) const {
705   bool DidAllTestsPass = true;
706   unsigned NumRules = 0;
707 
708   const char *LineStart = MemBuf->getBufferStart();
709 
710   // Eat whitespace.
711   while (LineStart != MemBuf->getBufferEnd() && std::isspace(*LineStart))
712     ++LineStart;
713 
714   while (LineStart != MemBuf->getBufferEnd() && *LineStart != '\0') {
715     const char *LineEnd = LineStart;
716     while (LineEnd != MemBuf->getBufferEnd() && *LineEnd != '\r' &&
717            *LineEnd != '\n')
718       ++LineEnd;
719 
720     StringRef Line(LineStart, LineEnd - LineStart);
721     if (Line.startswith(RulePrefix)) {
722       DidAllTestsPass &= check(Line.substr(RulePrefix.size()));
723       ++NumRules;
724     }
725 
726     // Eat whitespace.
727     LineStart = LineEnd;
728     while (LineStart != MemBuf->getBufferEnd() && std::isspace(*LineStart))
729       ++LineStart;
730   }
731   return DidAllTestsPass && (NumRules != 0);
732 }
733 
734 Expected<JITSymbolResolver::LookupResult> RuntimeDyldCheckerImpl::lookup(
735     const JITSymbolResolver::LookupSet &Symbols) const {
736 
737 #ifdef _MSC_VER
738   using ExpectedLookupResult = MSVCPExpected<JITSymbolResolver::LookupResult>;
739 #else
740   using ExpectedLookupResult = Expected<JITSymbolResolver::LookupResult>;
741 #endif
742 
743   auto ResultP = std::make_shared<std::promise<ExpectedLookupResult>>();
744   auto ResultF = ResultP->get_future();
745 
746   getRTDyld().Resolver.lookup(
747       Symbols, [=](Expected<JITSymbolResolver::LookupResult> Result) {
748         ResultP->set_value(std::move(Result));
749       });
750   return ResultF.get();
751 }
752 
753 bool RuntimeDyldCheckerImpl::isSymbolValid(StringRef Symbol) const {
754   if (getRTDyld().getSymbol(Symbol))
755     return true;
756   auto Result = lookup({Symbol});
757 
758   if (!Result) {
759     logAllUnhandledErrors(Result.takeError(), errs(), "RTDyldChecker: ");
760     return false;
761   }
762 
763   assert(Result->count(Symbol) && "Missing symbol result");
764   return true;
765 }
766 
767 uint64_t RuntimeDyldCheckerImpl::getSymbolLocalAddr(StringRef Symbol) const {
768   return static_cast<uint64_t>(
769       reinterpret_cast<uintptr_t>(getRTDyld().getSymbolLocalAddress(Symbol)));
770 }
771 
772 uint64_t RuntimeDyldCheckerImpl::getSymbolRemoteAddr(StringRef Symbol) const {
773   if (auto InternalSymbol = getRTDyld().getSymbol(Symbol))
774     return InternalSymbol.getAddress();
775 
776   auto Result = lookup({Symbol});
777   if (!Result) {
778     logAllUnhandledErrors(Result.takeError(), errs(), "RTDyldChecker: ");
779     return 0;
780   }
781   auto I = Result->find(Symbol);
782   assert(I != Result->end() && "Missing symbol result");
783   return I->second.getAddress();
784 }
785 
786 uint64_t RuntimeDyldCheckerImpl::readMemoryAtAddr(uint64_t SrcAddr,
787                                                   unsigned Size) const {
788   uintptr_t PtrSizedAddr = static_cast<uintptr_t>(SrcAddr);
789   assert(PtrSizedAddr == SrcAddr && "Linker memory pointer out-of-range.");
790   uint8_t *Src = reinterpret_cast<uint8_t*>(PtrSizedAddr);
791   return getRTDyld().readBytesUnaligned(Src, Size);
792 }
793 
794 
795 std::pair<const RuntimeDyldCheckerImpl::SectionAddressInfo*, std::string>
796 RuntimeDyldCheckerImpl::findSectionAddrInfo(StringRef FileName,
797                                             StringRef SectionName) const {
798 
799   auto SectionMapItr = Stubs.find(FileName);
800   if (SectionMapItr == Stubs.end()) {
801     std::string ErrorMsg = "File '";
802     ErrorMsg += FileName;
803     ErrorMsg += "' not found. ";
804     if (Stubs.empty())
805       ErrorMsg += "No stubs registered.";
806     else {
807       ErrorMsg += "Available files are:";
808       for (const auto& StubEntry : Stubs) {
809         ErrorMsg += " '";
810         ErrorMsg += StubEntry.first;
811         ErrorMsg += "'";
812       }
813     }
814     ErrorMsg += "\n";
815     return std::make_pair(nullptr, ErrorMsg);
816   }
817 
818   auto SectionInfoItr = SectionMapItr->second.find(SectionName);
819   if (SectionInfoItr == SectionMapItr->second.end())
820     return std::make_pair(nullptr,
821                           ("Section '" + SectionName + "' not found in file '" +
822                            FileName + "'\n").str());
823 
824   return std::make_pair(&SectionInfoItr->second, std::string(""));
825 }
826 
827 std::pair<uint64_t, std::string> RuntimeDyldCheckerImpl::getSectionAddr(
828     StringRef FileName, StringRef SectionName, bool IsInsideLoad) const {
829 
830   const SectionAddressInfo *SectionInfo = nullptr;
831   {
832     std::string ErrorMsg;
833     std::tie(SectionInfo, ErrorMsg) =
834       findSectionAddrInfo(FileName, SectionName);
835     if (ErrorMsg != "")
836       return std::make_pair(0, ErrorMsg);
837   }
838 
839   unsigned SectionID = SectionInfo->SectionID;
840   uint64_t Addr;
841   if (IsInsideLoad)
842     Addr = static_cast<uint64_t>(reinterpret_cast<uintptr_t>(
843         getRTDyld().Sections[SectionID].getAddress()));
844   else
845     Addr = getRTDyld().Sections[SectionID].getLoadAddress();
846 
847   return std::make_pair(Addr, std::string(""));
848 }
849 
850 std::pair<uint64_t, std::string> RuntimeDyldCheckerImpl::getStubAddrFor(
851     StringRef FileName, StringRef SectionName, StringRef SymbolName,
852     bool IsInsideLoad) const {
853 
854   const SectionAddressInfo *SectionInfo = nullptr;
855   {
856     std::string ErrorMsg;
857     std::tie(SectionInfo, ErrorMsg) =
858       findSectionAddrInfo(FileName, SectionName);
859     if (ErrorMsg != "")
860       return std::make_pair(0, ErrorMsg);
861   }
862 
863   unsigned SectionID = SectionInfo->SectionID;
864   const StubOffsetsMap &SymbolStubs = SectionInfo->StubOffsets;
865   auto StubOffsetItr = SymbolStubs.find(SymbolName);
866   if (StubOffsetItr == SymbolStubs.end())
867     return std::make_pair(0,
868                           ("Stub for symbol '" + SymbolName + "' not found. "
869                            "If '" + SymbolName + "' is an internal symbol this "
870                            "may indicate that the stub target offset is being "
871                            "computed incorrectly.\n").str());
872 
873   uint64_t StubOffset = StubOffsetItr->second;
874 
875   uint64_t Addr;
876   if (IsInsideLoad) {
877     uintptr_t SectionBase = reinterpret_cast<uintptr_t>(
878         getRTDyld().Sections[SectionID].getAddress());
879     Addr = static_cast<uint64_t>(SectionBase) + StubOffset;
880   } else {
881     uint64_t SectionBase = getRTDyld().Sections[SectionID].getLoadAddress();
882     Addr = SectionBase + StubOffset;
883   }
884 
885   return std::make_pair(Addr, std::string(""));
886 }
887 
888 StringRef
889 RuntimeDyldCheckerImpl::getSubsectionStartingAt(StringRef Name) const {
890   RTDyldSymbolTable::const_iterator pos =
891       getRTDyld().GlobalSymbolTable.find(Name);
892   if (pos == getRTDyld().GlobalSymbolTable.end())
893     return StringRef();
894   const auto &SymInfo = pos->second;
895   uint8_t *SectionAddr = getRTDyld().getSectionAddress(SymInfo.getSectionID());
896   return StringRef(reinterpret_cast<const char *>(SectionAddr) +
897                        SymInfo.getOffset(),
898                    getRTDyld().Sections[SymInfo.getSectionID()].getSize() -
899                        SymInfo.getOffset());
900 }
901 
902 Optional<uint64_t>
903 RuntimeDyldCheckerImpl::getSectionLoadAddress(void *LocalAddress) const {
904   for (auto &S : getRTDyld().Sections) {
905     if (S.getAddress() == LocalAddress)
906       return S.getLoadAddress();
907   }
908   return Optional<uint64_t>();
909 }
910 
911 void RuntimeDyldCheckerImpl::registerSection(
912     StringRef FilePath, unsigned SectionID) {
913   StringRef FileName = sys::path::filename(FilePath);
914   const SectionEntry &Section = getRTDyld().Sections[SectionID];
915   StringRef SectionName = Section.getName();
916 
917   Stubs[FileName][SectionName].SectionID = SectionID;
918 }
919 
920 void RuntimeDyldCheckerImpl::registerStubMap(
921     StringRef FilePath, unsigned SectionID,
922     const RuntimeDyldImpl::StubMap &RTDyldStubs) {
923   StringRef FileName = sys::path::filename(FilePath);
924   const SectionEntry &Section = getRTDyld().Sections[SectionID];
925   StringRef SectionName = Section.getName();
926 
927   Stubs[FileName][SectionName].SectionID = SectionID;
928 
929   for (auto &StubMapEntry : RTDyldStubs) {
930     std::string SymbolName = "";
931 
932     if (StubMapEntry.first.SymbolName)
933       SymbolName = StubMapEntry.first.SymbolName;
934     else {
935       // If this is a (Section, Offset) pair, do a reverse lookup in the
936       // global symbol table to find the name.
937       for (auto &GSTEntry : getRTDyld().GlobalSymbolTable) {
938         const auto &SymInfo = GSTEntry.second;
939         if (SymInfo.getSectionID() == StubMapEntry.first.SectionID &&
940             SymInfo.getOffset() ==
941               static_cast<uint64_t>(StubMapEntry.first.Offset)) {
942           SymbolName = GSTEntry.first();
943           break;
944         }
945       }
946     }
947 
948     if (SymbolName != "")
949       Stubs[FileName][SectionName].StubOffsets[SymbolName] =
950         StubMapEntry.second;
951   }
952 }
953 
954 RuntimeDyldChecker::RuntimeDyldChecker(RuntimeDyld &RTDyld,
955                                        MCDisassembler *Disassembler,
956                                        MCInstPrinter *InstPrinter,
957                                        raw_ostream &ErrStream)
958     : Impl(make_unique<RuntimeDyldCheckerImpl>(RTDyld, Disassembler,
959                                                InstPrinter, ErrStream)) {}
960 
961 RuntimeDyldChecker::~RuntimeDyldChecker() {}
962 
963 RuntimeDyld& RuntimeDyldChecker::getRTDyld() {
964   return Impl->RTDyld;
965 }
966 
967 const RuntimeDyld& RuntimeDyldChecker::getRTDyld() const {
968   return Impl->RTDyld;
969 }
970 
971 bool RuntimeDyldChecker::check(StringRef CheckExpr) const {
972   return Impl->check(CheckExpr);
973 }
974 
975 bool RuntimeDyldChecker::checkAllRulesInBuffer(StringRef RulePrefix,
976                                                MemoryBuffer *MemBuf) const {
977   return Impl->checkAllRulesInBuffer(RulePrefix, MemBuf);
978 }
979 
980 std::pair<uint64_t, std::string>
981 RuntimeDyldChecker::getSectionAddr(StringRef FileName, StringRef SectionName,
982                                    bool LocalAddress) {
983   return Impl->getSectionAddr(FileName, SectionName, LocalAddress);
984 }
985 
986 Optional<uint64_t>
987 RuntimeDyldChecker::getSectionLoadAddress(void *LocalAddress) const {
988   return Impl->getSectionLoadAddress(LocalAddress);
989 }
990