lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp

   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 "llvm/MC/MCContext.h"
  12 #include "llvm/MC/MCDisassembler.h"
  13 #include "llvm/MC/MCInst.h"
  14 #include "llvm/Support/StringRefMemoryObject.h"
  15 #include "RuntimeDyldImpl.h"
  16 #include <cctype>
  17 #include <memory>
  18
  19 #define DEBUG_TYPE "rtdyld"
  20
  21 using namespace llvm;
  22
  23 namespace llvm {
  24
  25   // Helper class that implements the language evaluated by RuntimeDyldChecker.
  26   class RuntimeDyldCheckerExprEval {
  27   public:
  28
  29     RuntimeDyldCheckerExprEval(const RuntimeDyldChecker &Checker,
  30                                llvm::raw_ostream &ErrStream)
  31       : Checker(Checker), ErrStream(ErrStream) {}
  32
  33     bool evaluate(StringRef Expr) const {
  34       // Expect equality expression of the form 'LHS = RHS'.
  35       Expr = Expr.trim();
  36       size_t EQIdx = Expr.find('=');
  37
  38       // Evaluate LHS.
  39       StringRef LHSExpr = Expr.substr(0, EQIdx).rtrim();
  40       StringRef RemainingExpr;
  41       EvalResult LHSResult;
  42       std::tie(LHSResult, RemainingExpr) =
  43         evalComplexExpr(evalSimpleExpr(LHSExpr));
  44       if (LHSResult.hasError())
  45         return handleError(Expr, LHSResult);
  46       if (RemainingExpr != "")
  47         return handleError(Expr, unexpectedToken(RemainingExpr, LHSExpr, ""));
  48
  49       // Evaluate RHS.
  50       StringRef RHSExpr = Expr.substr(EQIdx + 1).ltrim();
  51       EvalResult RHSResult;
  52       std::tie(RHSResult, RemainingExpr) =
  53         evalComplexExpr(evalSimpleExpr(RHSExpr));
  54       if (RHSResult.hasError())
  55         return handleError(Expr, RHSResult);
  56       if (RemainingExpr != "")
  57         return handleError(Expr, unexpectedToken(RemainingExpr, RHSExpr, ""));
  58
  59       if (LHSResult.getValue() != RHSResult.getValue()) {
  60         ErrStream << "Expression '" << Expr << "' is false: "
  61                   << format("0x%lx", LHSResult.getValue()) << " != "
  62                   << format("0x%lx", RHSResult.getValue()) << "\n";
  63         return false;
  64       }
  65       return true;
  66     }
  67
  68   private:
  69     const RuntimeDyldChecker &Checker;
  70     llvm::raw_ostream &ErrStream;
  71
  72     enum class BinOpToken : unsigned { Invalid, Add, Sub, BitwiseAnd,
  73                                        BitwiseOr, ShiftLeft, ShiftRight };
  74
  75     class EvalResult {
  76     public:
  77       EvalResult()
  78         : Value(0), ErrorMsg("") {}
  79       EvalResult(uint64_t Value)
  80         : Value(Value), ErrorMsg("") {}
  81       EvalResult(std::string ErrorMsg)
  82         : Value(0), ErrorMsg(ErrorMsg) {}
  83       uint64_t getValue() const { return Value; }
  84       bool hasError() const { return ErrorMsg != ""; }
  85       const std::string& getErrorMsg() const { return ErrorMsg; }
  86     private:
  87       uint64_t Value;
  88       std::string ErrorMsg;
  89     };
  90
  91     StringRef getTokenForError(StringRef Expr) const {
  92       if (Expr.empty())
  93         return "";
  94
  95       StringRef Token, Remaining;
  96       if (isalpha(Expr[0]))
  97         std::tie(Token, Remaining) = parseSymbol(Expr);
  98       else if (isdigit(Expr[0]))
  99         std::tie(Token, Remaining) = parseNumberString(Expr);
 100       else {
 101         unsigned TokLen = 1;
 102         if (Expr.startswith("<<") || Expr.startswith(">>"))
 103           TokLen = 2;
 104         Token = Expr.substr(0, TokLen);
 105       }
 106       return Token;
 107     }
 108
 109     EvalResult unexpectedToken(StringRef TokenStart,
 110                                StringRef SubExpr,
 111                                StringRef ErrText) const {
 112       std::string ErrorMsg("Encountered unexpected token '");
 113       ErrorMsg += getTokenForError(TokenStart);
 114       if (SubExpr != "") {
 115         ErrorMsg += "' while parsing subexpression '";
 116         ErrorMsg += SubExpr;
 117       }
 118       ErrorMsg += "'";
 119       if (ErrText != "") {
 120         ErrorMsg += " ";
 121         ErrorMsg += ErrText;
 122       }
 123       return EvalResult(std::move(ErrorMsg));
 124     }
 125
 126     bool handleError(StringRef Expr, const EvalResult &R) const {
 127       assert(R.hasError() && "Not an error result.");
 128       ErrStream << "Error evaluating expression '" << Expr << "': "
 129                 << R.getErrorMsg() << "\n";
 130       return false;
 131     }
 132
 133     std::pair<BinOpToken, StringRef> parseBinOpToken(StringRef Expr) const {
 134       if (Expr.empty())
 135         return std::make_pair(BinOpToken::Invalid, "");
 136
 137       // Handle the two 2-character tokens.
 138       if (Expr.startswith("<<"))
 139         return std::make_pair(BinOpToken::ShiftLeft,
 140                               Expr.substr(2).ltrim());
 141       if (Expr.startswith(">>"))
 142         return std::make_pair(BinOpToken::ShiftRight,
 143                               Expr.substr(2).ltrim());
 144
 145       // Handle one-character tokens.
 146       BinOpToken Op;
 147       switch (Expr[0]) {
 148         default: return std::make_pair(BinOpToken::Invalid, Expr);
 149         case '+': Op = BinOpToken::Add; break;
 150         case '-': Op = BinOpToken::Sub; break;
 151         case '&': Op = BinOpToken::BitwiseAnd; break;
 152         case '|': Op = BinOpToken::BitwiseOr; break;
 153       }
 154
 155       return std::make_pair(Op, Expr.substr(1).ltrim());
 156     }
 157
 158     EvalResult computeBinOpResult(BinOpToken Op, const EvalResult &LHSResult,
 159                                   const EvalResult &RHSResult) const {
 160       switch (Op) {
 161       default: llvm_unreachable("Tried to evaluate unrecognized operation.");
 162       case BinOpToken::Add:
 163         return EvalResult(LHSResult.getValue() + RHSResult.getValue());
 164       case BinOpToken::Sub:
 165         return EvalResult(LHSResult.getValue() - RHSResult.getValue());
 166       case BinOpToken::BitwiseAnd:
 167         return EvalResult(LHSResult.getValue() & RHSResult.getValue());
 168       case BinOpToken::BitwiseOr:
 169         return EvalResult(LHSResult.getValue() | RHSResult.getValue());
 170       case BinOpToken::ShiftLeft:
 171         return EvalResult(LHSResult.getValue() << RHSResult.getValue());
 172       case BinOpToken::ShiftRight:
 173         return EvalResult(LHSResult.getValue() >> RHSResult.getValue());
 174       }
 175     }
 176
 177     // Parse a symbol and return a (string, string) pair representing the symbol
 178     // name and expression remaining to be parsed.
 179     std::pair<StringRef, StringRef> parseSymbol(StringRef Expr) const {
 180       size_t FirstNonSymbol =
 181         Expr.find_first_not_of("0123456789"
 182                                "abcdefghijklmnopqrstuvwxyz"
 183                                "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 184                                ":_");
 185       return std::make_pair(Expr.substr(0, FirstNonSymbol),
 186                             Expr.substr(FirstNonSymbol).ltrim());
 187     }
 188
 189     // Evaluate a call to decode_operand. Decode the instruction operand at the
 190     // given symbol and get the value of the requested operand.
 191     // Returns an error if the instruction cannot be decoded, or the requested
 192     // operand is not an immediate.
 193     // On success, retuns a pair containing the value of the operand, plus
 194     // the expression remaining to be evaluated.
 195     std::pair<EvalResult, StringRef> evalDecodeOperand(StringRef Expr) const {
 196       if (!Expr.startswith("("))
 197         return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
 198       StringRef RemainingExpr = Expr.substr(1).ltrim();
 199       StringRef Symbol;
 200       std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
 201
 202       if (!Checker.isSymbolValid(Symbol))
 203         return std::make_pair(EvalResult(("Cannot decode unknown symbol '" +
 204                                           Symbol + "'").str()),
 205                               "");
 206
 207       if (!RemainingExpr.startswith(","))
 208         return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
 209                                               "expected ','"),
 210                               "");
 211       RemainingExpr = RemainingExpr.substr(1).ltrim();
 212
 213       EvalResult OpIdxExpr;
 214       std::tie(OpIdxExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
 215       if (OpIdxExpr.hasError())
 216         return std::make_pair(OpIdxExpr, "");
 217
 218       if (!RemainingExpr.startswith(")"))
 219         return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
 220                                               "expected ')'"),
 221                               "");
 222       RemainingExpr = RemainingExpr.substr(1).ltrim();
 223
 224       MCInst Inst;
 225       uint64_t Size;
 226       if (!decodeInst(Symbol, Inst, Size))
 227         return std::make_pair(EvalResult(("Couldn't decode instruction at '" +
 228                                           Symbol + "'").str()),
 229                               "");
 230
 231       unsigned OpIdx = OpIdxExpr.getValue();
 232       if (OpIdx >= Inst.getNumOperands()) {
 233         std::string ErrMsg;
 234         raw_string_ostream ErrMsgStream(ErrMsg);
 235         ErrMsgStream << "Invalid operand index '" << format("%i", OpIdx)
 236                      << "' for instruction '" << Symbol
 237                      << "'. Instruction has only "
 238                      << format("%i", Inst.getNumOperands())
 239                      << " operands.\nInstruction is:\n  ";
 240         Inst.dump_pretty(ErrMsgStream,
 241                          Checker.Disassembler->getContext().getAsmInfo(),
 242                          Checker.InstPrinter);
 243         return std::make_pair(EvalResult(ErrMsgStream.str()), "");
 244       }
 245
 246       const MCOperand &Op = Inst.getOperand(OpIdx);
 247       if (!Op.isImm()) {
 248         std::string ErrMsg;
 249         raw_string_ostream ErrMsgStream(ErrMsg);
 250         ErrMsgStream << "Operand '" << format("%i", OpIdx)
 251                      << "' of instruction '" << Symbol
 252                      << "' is not an immediate.\nInstruction is:\n  ";
 253         Inst.dump_pretty(ErrMsgStream,
 254                          Checker.Disassembler->getContext().getAsmInfo(),
 255                          Checker.InstPrinter);
 256
 257         return std::make_pair(EvalResult(ErrMsgStream.str()), "");
 258       }
 259
 260       return std::make_pair(EvalResult(Op.getImm()), RemainingExpr);
 261     }
 262
 263     // Evaluate a call to next_pc. Decode the instruction at the given
 264     // symbol and return the following program counter..
 265     // Returns an error if the instruction cannot be decoded.
 266     // On success, returns a pair containing the next PC, plus the length of the
 267     // expression remaining to be evaluated.
 268     std::pair<EvalResult, StringRef> evalNextPC(StringRef Expr) const {
 269       if (!Expr.startswith("("))
 270         return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
 271       StringRef RemainingExpr = Expr.substr(1).ltrim();
 272       StringRef Symbol;
 273       std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
 274
 275       if (!Checker.isSymbolValid(Symbol))
 276         return std::make_pair(EvalResult(("Cannot decode unknown symbol '"
 277                                           + Symbol + "'").str()),
 278                               "");
 279
 280       if (!RemainingExpr.startswith(")"))
 281         return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
 282                                               "expected ')'"),
 283                               "");
 284       RemainingExpr = RemainingExpr.substr(1).ltrim();
 285
 286       MCInst Inst;
 287       uint64_t Size;
 288       if (!decodeInst(Symbol, Inst, Size))
 289         return std::make_pair(EvalResult(("Couldn't decode instruction at '" +
 290                                           Symbol + "'").str()),
 291                               "");
 292       uint64_t NextPC = Checker.getSymbolAddress(Symbol) + Size;
 293
 294       return std::make_pair(EvalResult(NextPC), RemainingExpr);
 295     }
 296
 297     // Evaluate an identiefer expr, which may be a symbol, or a call to
 298     // one of the builtin functions: get_insn_opcode or get_insn_length.
 299     // Return the result, plus the expression remaining to be parsed.
 300     std::pair<EvalResult, StringRef> evalIdentifierExpr(StringRef Expr) const {
 301       StringRef Symbol;
 302       StringRef RemainingExpr;
 303       std::tie(Symbol, RemainingExpr) = parseSymbol(Expr);
 304
 305       // Check for builtin function calls.
 306       if (Symbol == "decode_operand")
 307         return evalDecodeOperand(RemainingExpr);
 308       else if (Symbol == "next_pc")
 309         return evalNextPC(RemainingExpr);
 310
 311       if (!Checker.isSymbolValid(Symbol)) {
 312         std::string ErrMsg("No known address for symbol '");
 313         ErrMsg += Symbol;
 314         ErrMsg += "'";
 315         if (Symbol.startswith("L"))
 316           ErrMsg += " (this appears to be an assembler local label - "
 317                     " perhaps drop the 'L'?)";
 318
 319         return std::make_pair(EvalResult(ErrMsg), "");
 320       }
 321
 322       // Looks like a plain symbol reference.
 323       return std::make_pair(EvalResult(Checker.getSymbolAddress(Symbol)),
 324                             RemainingExpr);
 325     }
 326
 327     // Parse a number (hexadecimal or decimal) and return a (string, string)
 328     // pair representing the number and the expression remaining to be parsed.
 329     std::pair<StringRef, StringRef> parseNumberString(StringRef Expr) const {
 330       size_t FirstNonDigit = StringRef::npos;
 331       if (Expr.startswith("0x")) {
 332         FirstNonDigit = Expr.find_first_not_of("0123456789abcdefABCDEF", 2);
 333         if (FirstNonDigit == StringRef::npos)
 334           FirstNonDigit = Expr.size();
 335       } else {
 336         FirstNonDigit = Expr.find_first_not_of("0123456789");
 337         if (FirstNonDigit == StringRef::npos)
 338           FirstNonDigit = Expr.size();
 339       }
 340       return std::make_pair(Expr.substr(0, FirstNonDigit),
 341                             Expr.substr(FirstNonDigit));
 342     }
 343
 344     // Evaluate a constant numeric expression (hexidecimal or decimal) and
 345     // return a pair containing the result, and the expression remaining to be
 346     // evaluated.
 347     std::pair<EvalResult, StringRef> evalNumberExpr(StringRef Expr) const {
 348       StringRef ValueStr;
 349       StringRef RemainingExpr;
 350       std::tie(ValueStr, RemainingExpr) = parseNumberString(Expr);
 351
 352       if (ValueStr.empty() || !isdigit(ValueStr[0]))
 353         return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
 354                                               "expected number"),
 355                               "");
 356       uint64_t Value;
 357       ValueStr.getAsInteger(0, Value);
 358       return std::make_pair(EvalResult(Value), RemainingExpr);
 359     }
 360
 361     // Evaluate an expression of the form "(<expr>)" and return a pair
 362     // containing the result of evaluating <expr>, plus the expression
 363     // remaining to be parsed.
 364     std::pair<EvalResult, StringRef> evalParensExpr(StringRef Expr) const {
 365       assert(Expr.startswith("(") && "Not a parenthesized expression");
 366       EvalResult SubExprResult;
 367       StringRef RemainingExpr;
 368       std::tie(SubExprResult, RemainingExpr) =
 369         evalComplexExpr(evalSimpleExpr(Expr.substr(1).ltrim()));
 370       if (SubExprResult.hasError())
 371         return std::make_pair(SubExprResult, "");
 372       if (!RemainingExpr.startswith(")"))
 373         return std::make_pair(unexpectedToken(RemainingExpr, Expr,
 374                                               "expected ')'"),
 375                               "");
 376       RemainingExpr = RemainingExpr.substr(1).ltrim();
 377       return std::make_pair(SubExprResult, RemainingExpr);
 378     }
 379
 380     // Evaluate an expression in one of the following forms:
 381     //   *{<number>}<symbol>
 382     //   *{<number>}(<symbol> + <number>)
 383     //   *{<number>}(<symbol> - <number>)
 384     // Return a pair containing the result, plus the expression remaining to be
 385     // parsed.
 386     std::pair<EvalResult, StringRef> evalLoadExpr(StringRef Expr) const {
 387       assert(Expr.startswith("*") && "Not a load expression");
 388       StringRef RemainingExpr = Expr.substr(1).ltrim();
 389       // Parse read size.
 390       if (!RemainingExpr.startswith("{"))
 391         return std::make_pair(EvalResult("Expected '{' following '*'."), "");
 392       RemainingExpr = RemainingExpr.substr(1).ltrim();
 393       EvalResult ReadSizeExpr;
 394       std::tie(ReadSizeExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
 395       if (ReadSizeExpr.hasError())
 396         return std::make_pair(ReadSizeExpr, RemainingExpr);
 397       uint64_t ReadSize = ReadSizeExpr.getValue();
 398       if (ReadSize < 1 || ReadSize > 8)
 399         return std::make_pair(EvalResult("Invalid size for dereference."), "");
 400       if (!RemainingExpr.startswith("}"))
 401         return std::make_pair(EvalResult("Missing '}' for dereference."), "");
 402       RemainingExpr = RemainingExpr.substr(1).ltrim();
 403
 404       // Check for '(symbol +/- constant)' form.
 405       bool SymbolPlusConstant = false;
 406       if (RemainingExpr.startswith("(")) {
 407         SymbolPlusConstant = true;
 408         RemainingExpr = RemainingExpr.substr(1).ltrim();
 409       }
 410
 411       // Read symbol.
 412       StringRef Symbol;
 413       std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
 414
 415       if (!Checker.isSymbolValid(Symbol))
 416         return std::make_pair(EvalResult(("Cannot dereference unknown symbol '"
 417                                           + Symbol + "'").str()),
 418                               "");
 419
 420       // Set up defaut offset.
 421       int64_t Offset = 0;
 422
 423       // Handle "+/- constant)" portion if necessary.
 424       if (SymbolPlusConstant) {
 425         char OpChar = RemainingExpr[0];
 426         if (OpChar != '+' && OpChar != '-')
 427           return std::make_pair(EvalResult("Invalid operator in load address."),
 428                                 "");
 429         RemainingExpr = RemainingExpr.substr(1).ltrim();
 430
 431         EvalResult OffsetExpr;
 432         std::tie(OffsetExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
 433
 434         Offset = (OpChar == '+') ?
 435                    OffsetExpr.getValue() : -1 * OffsetExpr.getValue();
 436
 437         if (!RemainingExpr.startswith(")"))
 438           return std::make_pair(EvalResult("Missing ')' in load address."),
 439                                 "");
 440
 441         RemainingExpr = RemainingExpr.substr(1).ltrim();
 442       }
 443
 444       return std::make_pair(
 445                EvalResult(Checker.readMemoryAtSymbol(Symbol, Offset, ReadSize)),
 446                RemainingExpr);
 447     }
 448
 449     // Evaluate a "simple" expression. This is any expression that _isn't_ an
 450     // un-parenthesized binary expression.
 451     //
 452     // "Simple" expressions can be optionally bit-sliced. See evalSlicedExpr.
 453     //
 454     // Returns a pair containing the result of the evaluation, plus the
 455     // expression remaining to be parsed.
 456     std::pair<EvalResult, StringRef> evalSimpleExpr(StringRef Expr) const {
 457       EvalResult SubExprResult;
 458       StringRef RemainingExpr;
 459
 460       if (Expr.empty())
 461         return std::make_pair(EvalResult("Unexpected end of expression"), "");
 462
 463       if (Expr[0] == '(')
 464         std::tie(SubExprResult, RemainingExpr) = evalParensExpr(Expr);
 465       else if (Expr[0] == '*')
 466         std::tie(SubExprResult, RemainingExpr) = evalLoadExpr(Expr);
 467       else if (isalpha(Expr[0]))
 468         std::tie(SubExprResult, RemainingExpr) = evalIdentifierExpr(Expr);
 469       else if (isdigit(Expr[0]))
 470         std::tie(SubExprResult, RemainingExpr) = evalNumberExpr(Expr);
 471
 472       if (SubExprResult.hasError())
 473         return std::make_pair(SubExprResult, RemainingExpr);
 474
 475       // Evaluate bit-slice if present.
 476       if (RemainingExpr.startswith("["))
 477         std::tie(SubExprResult, RemainingExpr) =
 478           evalSliceExpr(std::make_pair(SubExprResult, RemainingExpr));
 479
 480       return std::make_pair(SubExprResult, RemainingExpr);
 481     }
 482
 483     // Evaluate a bit-slice of an expression.
 484     // A bit-slice has the form "<expr>[high:low]". The result of evaluating a
 485     // slice is the bits between high and low (inclusive) in the original
 486     // expression, right shifted so that the "low" bit is in position 0 in the
 487     // result.
 488     // Returns a pair containing the result of the slice operation, plus the
 489     // expression remaining to be parsed.
 490     std::pair<EvalResult, StringRef> evalSliceExpr(
 491                                     std::pair<EvalResult, StringRef> Ctx) const{
 492       EvalResult SubExprResult;
 493       StringRef RemainingExpr;
 494       std::tie(SubExprResult, RemainingExpr) = Ctx;
 495
 496       assert(RemainingExpr.startswith("[") && "Not a slice expr.");
 497       RemainingExpr = RemainingExpr.substr(1).ltrim();
 498
 499       EvalResult HighBitExpr;
 500       std::tie(HighBitExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
 501
 502       if (HighBitExpr.hasError())
 503         return std::make_pair(HighBitExpr, RemainingExpr);
 504
 505       if (!RemainingExpr.startswith(":"))
 506         return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
 507                                               "expected ':'"),
 508                               "");
 509       RemainingExpr = RemainingExpr.substr(1).ltrim();
 510
 511       EvalResult LowBitExpr;
 512       std::tie(LowBitExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
 513
 514       if (LowBitExpr.hasError())
 515         return std::make_pair(LowBitExpr, RemainingExpr);
 516
 517       if (!RemainingExpr.startswith("]"))
 518         return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
 519                                               "expected ']'"),
 520                               "");
 521       RemainingExpr = RemainingExpr.substr(1).ltrim();
 522
 523       unsigned HighBit = HighBitExpr.getValue();
 524       unsigned LowBit = LowBitExpr.getValue();
 525       uint64_t Mask = ((uint64_t)1 << (HighBit - LowBit + 1)) - 1;
 526       uint64_t SlicedValue = (SubExprResult.getValue() >> LowBit) & Mask;
 527       return std::make_pair(EvalResult(SlicedValue), RemainingExpr);
 528     }
 529
 530     // Evaluate a "complex" expression.
 531     // Takes an already evaluated subexpression and checks for the presence of a
 532     // binary operator, computing the result of the binary operation if one is
 533     // found. Used to make arithmetic expressions left-associative.
 534     // Returns a pair containing the ultimate result of evaluating the
 535     // expression, plus the expression remaining to be evaluated.
 536     std::pair<EvalResult, StringRef> evalComplexExpr(
 537                                    std::pair<EvalResult, StringRef> Ctx) const {
 538       EvalResult LHSResult;
 539       StringRef RemainingExpr;
 540       std::tie(LHSResult, RemainingExpr) = Ctx;
 541
 542       // If there was an error, or there's nothing left to evaluate, return the
 543       // result.
 544       if (LHSResult.hasError() || RemainingExpr == "")
 545         return std::make_pair(LHSResult, RemainingExpr);
 546
 547       // Otherwise check if this is a binary expressioan.
 548       BinOpToken BinOp;
 549       std::tie(BinOp, RemainingExpr) = parseBinOpToken(RemainingExpr);
 550
 551       // If this isn't a recognized expression just return.
 552       if (BinOp == BinOpToken::Invalid)
 553         return std::make_pair(LHSResult, RemainingExpr);
 554
 555       // This is a recognized bin-op. Evaluate the RHS, then evaluate the binop.
 556       EvalResult RHSResult;
 557       std::tie(RHSResult, RemainingExpr) = evalSimpleExpr(RemainingExpr);
 558
 559       // If there was an error evaluating the RHS, return it.
 560       if (RHSResult.hasError())
 561         return std::make_pair(RHSResult, RemainingExpr);
 562
 563       // This is a binary expression - evaluate and try to continue as a
 564       // complex expr.
 565       EvalResult ThisResult(computeBinOpResult(BinOp, LHSResult, RHSResult));
 566
 567       return evalComplexExpr(std::make_pair(ThisResult, RemainingExpr));
 568     }
 569
 570     bool decodeInst(StringRef Symbol, MCInst &Inst, uint64_t &Size) const {
 571       MCDisassembler *Dis = Checker.Disassembler;
 572       StringRef SectionMem = Checker.getSubsectionStartingAt(Symbol);
 573       StringRefMemoryObject SectionBytes(SectionMem, 0);
 574
 575       MCDisassembler::DecodeStatus S =
 576         Dis->getInstruction(Inst, Size, SectionBytes, 0, nulls(), nulls());
 577
 578       return (S == MCDisassembler::Success);
 579     }
 580
 581   };
 582
 583 }
 584
 585 bool RuntimeDyldChecker::check(StringRef CheckExpr) const {
 586   CheckExpr = CheckExpr.trim();
 587   DEBUG(llvm::dbgs() << "RuntimeDyldChecker: Checking '" << CheckExpr
 588                      << "'...\n");
 589   RuntimeDyldCheckerExprEval P(*this, ErrStream);
 590   bool Result = P.evaluate(CheckExpr);
 591   (void)Result;
 592   DEBUG(llvm::dbgs() << "RuntimeDyldChecker: '" << CheckExpr << "' "
 593                      << (Result ? "passed" : "FAILED") << ".\n");
 594   return Result;
 595 }
 596
 597 bool RuntimeDyldChecker::checkAllRulesInBuffer(StringRef RulePrefix,
 598                                                MemoryBuffer* MemBuf) const {
 599   bool DidAllTestsPass = true;
 600   unsigned NumRules = 0;
 601
 602   const char *LineStart = MemBuf->getBufferStart();
 603
 604   // Eat whitespace.
 605   while (LineStart != MemBuf->getBufferEnd() &&
 606          std::isspace(*LineStart))
 607     ++LineStart;
 608
 609   while (LineStart != MemBuf->getBufferEnd() && *LineStart != '\0') {
 610     const char *LineEnd = LineStart;
 611     while (LineEnd != MemBuf->getBufferEnd() &&
 612            *LineEnd != '\r' && *LineEnd != '\n')
 613       ++LineEnd;
 614
 615     StringRef Line(LineStart, LineEnd - LineStart);
 616     if (Line.startswith(RulePrefix)) {
 617       DidAllTestsPass &= check(Line.substr(RulePrefix.size()));
 618       ++NumRules;
 619     }
 620
 621     // Eat whitespace.
 622     LineStart = LineEnd;
 623     while (LineStart != MemBuf->getBufferEnd() &&
 624            std::isspace(*LineStart))
 625       ++LineStart;
 626   }
 627   return DidAllTestsPass && (NumRules != 0);
 628 }
 629
 630 bool RuntimeDyldChecker::isSymbolValid(StringRef Symbol) const {
 631   return RTDyld.getSymbolAddress(Symbol) != nullptr;
 632 }
 633
 634 uint64_t RuntimeDyldChecker::getSymbolAddress(StringRef Symbol) const {
 635   return RTDyld.getAnySymbolRemoteAddress(Symbol);
 636 }
 637
 638 uint64_t RuntimeDyldChecker::readMemoryAtSymbol(StringRef Symbol,
 639                                                 int64_t Offset,
 640                                                 unsigned Size) const {
 641   uint8_t *Src = RTDyld.getSymbolAddress(Symbol);
 642   uint64_t Result = 0;
 643   memcpy(&Result, Src + Offset, Size);
 644   return Result;
 645 }
 646
 647 StringRef RuntimeDyldChecker::getSubsectionStartingAt(StringRef Name) const {
 648   RuntimeDyldImpl::SymbolTableMap::const_iterator pos =
 649     RTDyld.GlobalSymbolTable.find(Name);
 650   if (pos == RTDyld.GlobalSymbolTable.end())
 651     return StringRef();
 652   RuntimeDyldImpl::SymbolLoc Loc = pos->second;
 653   uint8_t *SectionAddr = RTDyld.getSectionAddress(Loc.first);
 654   return StringRef(reinterpret_cast<const char*>(SectionAddr) + Loc.second,
 655                    RTDyld.Sections[Loc.first].Size - Loc.second);
 656 }