tools/bugpoint/ExecutionDriver.cpp

   1 //===- ExecutionDriver.cpp - Allow execution of LLVM program --------------===//
   2 //
   3 // This file contains code used to execute the program utilizing one of the
   4 // various ways of running LLVM bytecode.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 /*
   9 BUGPOINT NOTES:
  10
  11 1. Bugpoint should not leave any files behind if the program works properly
  12 2. There should be an option to specify the program name, which specifies a
  13    unique string to put into output files.  This allows operation in the
  14    SingleSource directory, e.g. default to the first input filename.
  15 */
  16
  17 #include "BugDriver.h"
  18 #include "Support/CommandLine.h"
  19 #include "Support/Debug.h"
  20 #include "Support/FileUtilities.h"
  21 #include "Support/SystemUtils.h"
  22 #include <fstream>
  23 #include <iostream>
  24
  25 namespace {
  26   // OutputType - Allow the user to specify the way code should be run, to test
  27   // for miscompilation.
  28   //
  29   enum OutputType {
  30     RunLLI, RunJIT, RunLLC, RunCBE
  31   };
  32   cl::opt<OutputType>
  33   InterpreterSel(cl::desc("Specify how LLVM code should be executed:"),
  34                  cl::values(clEnumValN(RunLLI, "run-lli", "Execute with LLI"),
  35                             clEnumValN(RunJIT, "run-jit", "Execute with JIT"),
  36                             clEnumValN(RunLLC, "run-llc", "Compile with LLC"),
  37                             clEnumValN(RunCBE, "run-cbe", "Compile with CBE"),
  38                             0));
  39
  40   cl::opt<std::string>
  41   InputFile("input", cl::init("/dev/null"),
  42             cl::desc("Filename to pipe in as stdin (default: /dev/null)"));
  43
  44   enum FileType { AsmFile, CFile };
  45 }
  46
  47 // Anything specified after the --args option are taken as arguments to the
  48 // program being debugged.
  49 cl::list<std::string>
  50 InputArgv("args", cl::Positional, cl::desc("<program arguments>..."),
  51           cl::ZeroOrMore);
  52
  53 /// AbstractInterpreter Class - Subclasses of this class are used to execute
  54 /// LLVM bytecode in a variety of ways.  This abstract interface hides this
  55 /// complexity behind a simple interface.
  56 ///
  57 struct AbstractInterpreter {
  58
  59   virtual ~AbstractInterpreter() {}
  60
  61   /// ExecuteProgram - Run the specified bytecode file, emitting output to the
  62   /// specified filename.  This returns the exit code of the program.
  63   ///
  64   virtual int ExecuteProgram(const std::string &Bytecode,
  65                              const std::string &OutputFile,
  66                              const std::string &SharedLib = "") = 0;
  67 };
  68
  69
  70 //===----------------------------------------------------------------------===//
  71 // LLI Implementation of AbstractIntepreter interface
  72 //
  73 class LLI : public AbstractInterpreter {
  74   std::string LLIPath;          // The path to the LLI executable
  75 public:
  76   LLI(const std::string &Path) : LLIPath(Path) { }
  77
  78   // LLI create method - Try to find the LLI executable
  79   static LLI *create(BugDriver *BD, std::string &Message) {
  80     std::string LLIPath = FindExecutable("lli", BD->getToolName());
  81     if (!LLIPath.empty()) {
  82       Message = "Found lli: " + LLIPath + "\n";
  83       return new LLI(LLIPath);
  84     }
  85
  86     Message = "Cannot find `lli' in bugpoint executable directory or PATH!\n";
  87     return 0;
  88   }
  89   virtual int ExecuteProgram(const std::string &Bytecode,
  90                              const std::string &OutputFile,
  91                              const std::string &SharedLib = "");
  92 };
  93
  94 int LLI::ExecuteProgram(const std::string &Bytecode,
  95                         const std::string &OutputFile,
  96                         const std::string &SharedLib) {
  97   if (!SharedLib.empty()) {
  98     std::cerr << "LLI currently does not support loading shared libraries.\n"
  99               << "Exiting.\n";
 100     exit(1);
 101   }
 102
 103   std::vector<const char*> LLIArgs;
 104   LLIArgs.push_back(LLIPath.c_str());
 105   LLIArgs.push_back("-abort-on-exception");
 106   LLIArgs.push_back("-quiet");
 107   LLIArgs.push_back("-force-interpreter=true");
 108   LLIArgs.push_back(Bytecode.c_str());
 109   // Add optional parameters to the running program from Argv
 110   for (unsigned i=0, e = InputArgv.size(); i != e; ++i)
 111     LLIArgs.push_back(InputArgv[i].c_str());
 112   LLIArgs.push_back(0);
 113
 114   std::cout << "<lli>" << std::flush;
 115   DEBUG(std::cerr << "\nAbout to run:\n\t";
 116         for (unsigned i=0, e = LLIArgs.size(); i != e; ++i)
 117           std::cerr << " " << LLIArgs[i];
 118         std::cerr << "\n";
 119         );
 120   return RunProgramWithTimeout(LLIPath, &LLIArgs[0],
 121                                InputFile, OutputFile, OutputFile);
 122 }
 123
 124 //===----------------------------------------------------------------------===//
 125 // GCC abstraction
 126 //
 127 // This is not a *real* AbstractInterpreter as it does not accept bytecode
 128 // files, but only input acceptable to GCC, i.e. C, C++, and assembly files
 129 //
 130 class GCC {
 131   std::string GCCPath;          // The path to the gcc executable
 132 public:
 133   GCC(const std::string &gccPath) : GCCPath(gccPath) { }
 134   virtual ~GCC() {}
 135
 136   // GCC create method - Try to find the `gcc' executable
 137   static GCC *create(BugDriver *BD, std::string &Message) {
 138     std::string GCCPath = FindExecutable("gcc", BD->getToolName());
 139     if (GCCPath.empty()) {
 140       Message = "Cannot find `gcc' in bugpoint executable directory or PATH!\n";
 141       return 0;
 142     }
 143
 144     Message = "Found gcc: " + GCCPath + "\n";
 145     return new GCC(GCCPath);
 146   }
 147
 148   virtual int ExecuteProgram(const std::string &ProgramFile,
 149                              FileType fileType,
 150                              const std::string &OutputFile,
 151                              const std::string &SharedLib = "");
 152
 153   int MakeSharedObject(const std::string &InputFile,
 154                        FileType fileType,
 155                        std::string &OutputFile);
 156
 157   void ProcessFailure(const char **Args);
 158 };
 159
 160 int GCC::ExecuteProgram(const std::string &ProgramFile,
 161                         FileType fileType,
 162                         const std::string &OutputFile,
 163                         const std::string &SharedLib) {
 164   std::string OutputBinary = getUniqueFilename("bugpoint.gcc.exe");
 165   std::vector<const char*> GCCArgs;
 166
 167   GCCArgs.push_back(GCCPath.c_str());
 168   if (!SharedLib.empty()) // Specify the shared library to link in...
 169     GCCArgs.push_back(SharedLib.c_str());
 170   GCCArgs.push_back("-x");
 171   if (fileType == CFile) {
 172     GCCArgs.push_back("c");
 173     GCCArgs.push_back("-fno-strict-aliasing");
 174   } else {
 175     GCCArgs.push_back("assembler");
 176   }
 177
 178   GCCArgs.push_back(ProgramFile.c_str());  // Specify the input filename...
 179   GCCArgs.push_back("-o");
 180   GCCArgs.push_back(OutputBinary.c_str()); // Output to the right file...
 181   GCCArgs.push_back("-lm");                // Hard-code the math library...
 182   GCCArgs.push_back("-O2");                // Optimize the program a bit...
 183   GCCArgs.push_back(0);                    // NULL terminator
 184
 185   std::cout << "<gcc>" << std::flush;
 186   if (RunProgramWithTimeout(GCCPath, &GCCArgs[0], "/dev/null", "/dev/null",
 187                             "/dev/null")) {
 188     ProcessFailure(&GCCArgs[0]);
 189     exit(1);
 190   }
 191
 192   std::vector<const char*> ProgramArgs;
 193   ProgramArgs.push_back(OutputBinary.c_str());
 194   // Add optional parameters to the running program from Argv
 195   for (unsigned i=0, e = InputArgv.size(); i != e; ++i)
 196     ProgramArgs.push_back(InputArgv[i].c_str());
 197   ProgramArgs.push_back(0);                // NULL terminator
 198
 199   // Now that we have a binary, run it!
 200   std::cout << "<program>" << std::flush;
 201   DEBUG(std::cerr << "\nAbout to run:\n\t";
 202         for (unsigned i=0, e = ProgramArgs.size(); i != e; ++i)
 203           std::cerr << " " << ProgramArgs[i];
 204         std::cerr << "\n";
 205         );
 206   int ProgramResult = RunProgramWithTimeout(OutputBinary, &ProgramArgs[0],
 207                                             InputFile, OutputFile, OutputFile);
 208   removeFile(OutputBinary);
 209   return ProgramResult;
 210 }
 211
 212 int GCC::MakeSharedObject(const std::string &InputFile,
 213                           FileType fileType,
 214                           std::string &OutputFile) {
 215   OutputFile = getUniqueFilename("./bugpoint.so");
 216   // Compile the C/asm file into a shared object
 217   const char* GCCArgs[] = {
 218     GCCPath.c_str(),
 219     "-x", (fileType == AsmFile) ? "assembler" : "c",
 220     InputFile.c_str(),           // Specify the input filename...
 221 #if defined(sparc) || defined(__sparc__) || defined(__sparcv9)
 222     "-G",                        // Compile a shared library, `-G' for Sparc
 223 #else
 224     "-shared",                   // `-shared' for Linux/X86, maybe others
 225 #endif
 226     "-o", OutputFile.c_str(),    // Output to the right filename...
 227     "-O2",                       // Optimize the program a bit...
 228     0
 229   };
 230
 231   std::cout << "<gcc>" << std::flush;
 232   if(RunProgramWithTimeout(GCCPath, GCCArgs, "/dev/null", "/dev/null",
 233                            "/dev/null")) {
 234     ProcessFailure(GCCArgs);
 235     exit(1);
 236   }
 237   return 0;
 238 }
 239
 240 void GCC::ProcessFailure(const char** GCCArgs) {
 241   std::cerr << "\n*** bugpoint error: invocation of the C compiler failed!\n";
 242   for (const char **Arg = GCCArgs; *Arg; ++Arg)
 243     std::cerr << " " << *Arg;
 244   std::cerr << "\n";
 245
 246   // Rerun the compiler, capturing any error messages to print them.
 247   std::string ErrorFilename = getUniqueFilename("bugpoint.gcc.errors");
 248   RunProgramWithTimeout(GCCPath, GCCArgs, "/dev/null", ErrorFilename.c_str(),
 249                         ErrorFilename.c_str());
 250
 251   // Print out the error messages generated by GCC if possible...
 252   std::ifstream ErrorFile(ErrorFilename.c_str());
 253   if (ErrorFile) {
 254     std::copy(std::istreambuf_iterator<char>(ErrorFile),
 255               std::istreambuf_iterator<char>(),
 256               std::ostreambuf_iterator<char>(std::cerr));
 257     ErrorFile.close();
 258     std::cerr << "\n";
 259   }
 260
 261   removeFile(ErrorFilename);
 262 }
 263
 264 //===----------------------------------------------------------------------===//
 265 // LLC Implementation of AbstractIntepreter interface
 266 //
 267 class LLC : public AbstractInterpreter {
 268   std::string LLCPath;          // The path to the LLC executable
 269   GCC *gcc;
 270 public:
 271   LLC(const std::string &llcPath, GCC *Gcc)
 272     : LLCPath(llcPath), gcc(Gcc) { }
 273   ~LLC() { delete gcc; }
 274
 275   // LLC create method - Try to find the LLC executable
 276   static LLC *create(BugDriver *BD, std::string &Message) {
 277     std::string LLCPath = FindExecutable("llc", BD->getToolName());
 278     if (LLCPath.empty()) {
 279       Message = "Cannot find `llc' in bugpoint executable directory or PATH!\n";
 280       return 0;
 281     }
 282
 283     Message = "Found llc: " + LLCPath + "\n";
 284     GCC *gcc = GCC::create(BD, Message);
 285     if (!gcc) {
 286       std::cerr << Message << "\n";
 287       exit(1);
 288     }
 289     return new LLC(LLCPath, gcc);
 290   }
 291
 292   virtual int ExecuteProgram(const std::string &Bytecode,
 293                              const std::string &OutputFile,
 294                              const std::string &SharedLib = "");
 295
 296   int OutputAsm(const std::string &Bytecode,
 297                 std::string &OutputAsmFile);
 298 };
 299
 300 int LLC::OutputAsm(const std::string &Bytecode,
 301                    std::string &OutputAsmFile) {
 302   OutputAsmFile = "bugpoint.llc.s";
 303   const char *LLCArgs[] = {
 304     LLCPath.c_str(),
 305     "-o", OutputAsmFile.c_str(), // Output to the Asm file
 306     "-f",                        // Overwrite as necessary...
 307     Bytecode.c_str(),            // This is the input bytecode
 308     0
 309   };
 310
 311   std::cout << "<llc>" << std::flush;
 312   if (RunProgramWithTimeout(LLCPath, LLCArgs, "/dev/null", "/dev/null",
 313                             "/dev/null")) {
 314     // If LLC failed on the bytecode, print error...
 315     std::cerr << "bugpoint error: `llc' failed!\n";
 316     removeFile(OutputAsmFile);
 317     return 1;
 318   }
 319
 320   return 0;
 321 }
 322
 323 int LLC::ExecuteProgram(const std::string &Bytecode,
 324                         const std::string &OutputFile,
 325                         const std::string &SharedLib) {
 326
 327   std::string OutputAsmFile;
 328   if (OutputAsm(Bytecode, OutputAsmFile)) {
 329     std::cerr << "Could not generate asm code with `llc', exiting.\n";
 330     exit(1);
 331   }
 332
 333   // Assuming LLC worked, compile the result with GCC and run it.
 334   int Result = gcc->ExecuteProgram(OutputAsmFile,AsmFile,OutputFile,SharedLib);
 335   removeFile(OutputAsmFile);
 336   return Result;
 337 }
 338
 339
 340 //===----------------------------------------------------------------------===//
 341 // JIT Implementation of AbstractIntepreter interface
 342 //
 343 class JIT : public AbstractInterpreter {
 344   std::string LLIPath;          // The path to the LLI executable
 345 public:
 346   JIT(const std::string &Path) : LLIPath(Path) { }
 347
 348   // JIT create method - Try to find the LLI executable
 349   static JIT *create(BugDriver *BD, std::string &Message) {
 350     std::string LLIPath = FindExecutable("lli", BD->getToolName());
 351     if (!LLIPath.empty()) {
 352       Message = "Found lli: " + LLIPath + "\n";
 353       return new JIT(LLIPath);
 354     }
 355
 356     Message = "Cannot find `lli' in bugpoint executable directory or PATH!\n";
 357     return 0;
 358   }
 359   virtual int ExecuteProgram(const std::string &Bytecode,
 360                              const std::string &OutputFile,
 361                              const std::string &SharedLib = "");
 362 };
 363
 364 int JIT::ExecuteProgram(const std::string &Bytecode,
 365                         const std::string &OutputFile,
 366                         const std::string &SharedLib) {
 367   // Construct a vector of parameters, incorporating those from the command-line
 368   std::vector<const char*> JITArgs;
 369   JITArgs.push_back(LLIPath.c_str());
 370   JITArgs.push_back("-quiet");
 371   JITArgs.push_back("-force-interpreter=false");
 372   if (!SharedLib.empty()) {
 373     JITArgs.push_back("-load");
 374     JITArgs.push_back(SharedLib.c_str());
 375   }
 376   JITArgs.push_back(Bytecode.c_str());
 377   // Add optional parameters to the running program from Argv
 378   for (unsigned i=0, e = InputArgv.size(); i != e; ++i)
 379     JITArgs.push_back(InputArgv[i].c_str());
 380   JITArgs.push_back(0);
 381
 382   std::cout << "<jit>" << std::flush;
 383   DEBUG(std::cerr << "\nAbout to run:\n\t";
 384         for (unsigned i=0, e = JITArgs.size(); i != e; ++i)
 385           std::cerr << " " << JITArgs[i];
 386         std::cerr << "\n";
 387         );
 388   DEBUG(std::cerr << "\nSending output to " << OutputFile << "\n");
 389   return RunProgramWithTimeout(LLIPath, &JITArgs[0],
 390                                InputFile, OutputFile, OutputFile);
 391 }
 392
 393 //===----------------------------------------------------------------------===//
 394 // CBE Implementation of AbstractIntepreter interface
 395 //
 396 class CBE : public AbstractInterpreter {
 397   std::string DISPath;          // The path to the LLVM 'dis' executable
 398   GCC *gcc;
 399 public:
 400   CBE(const std::string &disPath, GCC *Gcc) : DISPath(disPath), gcc(Gcc) { }
 401   ~CBE() { delete gcc; }
 402
 403   // CBE create method - Try to find the 'dis' executable
 404   static CBE *create(BugDriver *BD, std::string &Message) {
 405     std::string DISPath = FindExecutable("dis", BD->getToolName());
 406     if (DISPath.empty()) {
 407       Message = "Cannot find `dis' in bugpoint executable directory or PATH!\n";
 408       return 0;
 409     }
 410
 411     Message = "Found dis: " + DISPath + "\n";
 412
 413     GCC *gcc = GCC::create(BD, Message);
 414     if (!gcc) {
 415       std::cerr << Message << "\n";
 416       exit(1);
 417     }
 418     return new CBE(DISPath, gcc);
 419   }
 420
 421   virtual int ExecuteProgram(const std::string &Bytecode,
 422                              const std::string &OutputFile,
 423                              const std::string &SharedLib = "");
 424
 425   // Sometimes we just want to go half-way and only generate the C file,
 426   // not necessarily compile it with GCC and run the program
 427   virtual int OutputC(const std::string &Bytecode,
 428                       std::string &OutputCFile);
 429
 430 };
 431
 432 int CBE::OutputC(const std::string &Bytecode,
 433                  std::string &OutputCFile) {
 434   OutputCFile = "bugpoint.cbe.c";
 435   const char *DisArgs[] = {
 436     DISPath.c_str(),
 437     "-o", OutputCFile.c_str(),   // Output to the C file
 438     "-c",                        // Output to C
 439     "-f",                        // Overwrite as necessary...
 440     Bytecode.c_str(),            // This is the input bytecode
 441     0
 442   };
 443
 444   std::cout << "<cbe>" << std::flush;
 445   if (RunProgramWithTimeout(DISPath, DisArgs, "/dev/null", "/dev/null",
 446                             "/dev/null")) {
 447     // If dis failed on the bytecode, print error...
 448     std::cerr << "bugpoint error: `dis -c' failed!\n";
 449     return 1;
 450   }
 451
 452   return 0;
 453 }
 454
 455
 456 int CBE::ExecuteProgram(const std::string &Bytecode,
 457                         const std::string &OutputFile,
 458                         const std::string &SharedLib) {
 459   std::string OutputCFile;
 460   if (OutputC(Bytecode, OutputCFile)) {
 461     std::cerr << "Could not generate C code with `dis', exiting.\n";
 462     exit(1);
 463   }
 464
 465   int Result = gcc->ExecuteProgram(OutputCFile, CFile, OutputFile, SharedLib);
 466   removeFile(OutputCFile);
 467
 468   return Result;
 469 }
 470
 471
 472 //===----------------------------------------------------------------------===//
 473 // BugDriver method implementation
 474 //
 475
 476 /// initializeExecutionEnvironment - This method is used to set up the
 477 /// environment for executing LLVM programs.
 478 ///
 479 bool BugDriver::initializeExecutionEnvironment() {
 480   std::cout << "Initializing execution environment: ";
 481
 482   // FIXME: This should default to searching for the best interpreter to use on
 483   // this platform, which would be JIT, then LLC, then CBE, then LLI.
 484
 485   // Create an instance of the AbstractInterpreter interface as specified on the
 486   // command line
 487   std::string Message;
 488   switch (InterpreterSel) {
 489   case RunLLI: Interpreter = LLI::create(this, Message); break;
 490   case RunLLC: Interpreter = LLC::create(this, Message); break;
 491   case RunJIT: Interpreter = JIT::create(this, Message); break;
 492   case RunCBE: Interpreter = CBE::create(this, Message); break;
 493   default:
 494     Message = " Sorry, this back-end is not supported by bugpoint right now!\n";
 495     break;
 496   }
 497
 498   std::cout << Message;
 499
 500   // Initialize auxiliary tools for debugging
 501   cbe = CBE::create(this, Message);
 502   if (!cbe) { std::cout << Message << "\nExiting.\n"; exit(1); }
 503   gcc = GCC::create(this, Message);
 504   if (!gcc) { std::cout << Message << "\nExiting.\n"; exit(1); }
 505
 506   // If there was an error creating the selected interpreter, quit with error.
 507   return Interpreter == 0;
 508 }
 509
 510
 511 /// executeProgram - This method runs "Program", capturing the output of the
 512 /// program to a file, returning the filename of the file.  A recommended
 513 /// filename may be optionally specified.
 514 ///
 515 std::string BugDriver::executeProgram(std::string OutputFile,
 516                                       std::string BytecodeFile,
 517                                       std::string SharedObject,
 518                                       AbstractInterpreter *AI) {
 519   assert((Interpreter || AI) &&"Interpreter should have been created already!");
 520   bool CreatedBytecode = false;
 521   if (BytecodeFile.empty()) {
 522     // Emit the program to a bytecode file...
 523     BytecodeFile = getUniqueFilename("bugpoint-test-program.bc");
 524
 525     if (writeProgramToFile(BytecodeFile, Program)) {
 526       std::cerr << ToolName << ": Error emitting bytecode to file '"
 527                 << BytecodeFile << "'!\n";
 528       exit(1);
 529     }
 530     CreatedBytecode = true;
 531   }
 532
 533   if (OutputFile.empty()) OutputFile = "bugpoint-execution-output";
 534
 535   // Check to see if this is a valid output filename...
 536   OutputFile = getUniqueFilename(OutputFile);
 537
 538   // Actually execute the program!
 539   int RetVal = (AI != 0) ?
 540     AI->ExecuteProgram(BytecodeFile, OutputFile, SharedObject) :
 541     Interpreter->ExecuteProgram(BytecodeFile, OutputFile, SharedObject);
 542
 543   // Remove the temporary bytecode file.
 544   if (CreatedBytecode) removeFile(BytecodeFile);
 545
 546   // Return the filename we captured the output to.
 547   return OutputFile;
 548 }
 549
 550 std::string BugDriver::executeProgramWithCBE(std::string OutputFile,
 551                                              std::string BytecodeFile,
 552                                              std::string SharedObject) {
 553   return executeProgram(OutputFile, BytecodeFile, SharedObject, cbe);
 554 }
 555
 556 int BugDriver::compileSharedObject(const std::string &BytecodeFile,
 557                                    std::string &SharedObject) {
 558   assert(Interpreter && "Interpreter should have been created already!");
 559   std::string Message, OutputCFile;
 560
 561   // Using CBE
 562   cbe->OutputC(BytecodeFile, OutputCFile);
 563
 564 #if 0 /* This is an alternative, as yet unimplemented */
 565   // Using LLC
 566   LLC *llc = LLC::create(this, Message);
 567   if (llc->OutputAsm(BytecodeFile, OutputFile)) {
 568     std::cerr << "Could not generate asm code with `llc', exiting.\n";
 569     exit(1);
 570   }
 571 #endif
 572
 573   gcc->MakeSharedObject(OutputCFile, CFile, SharedObject);
 574
 575   // Remove the intermediate C file
 576   removeFile(OutputCFile);
 577
 578   return 0;
 579 }
 580
 581
 582 /// diffProgram - This method executes the specified module and diffs the output
 583 /// against the file specified by ReferenceOutputFile.  If the output is
 584 /// different, true is returned.
 585 ///
 586 bool BugDriver::diffProgram(const std::string &BytecodeFile,
 587                             const std::string &SharedObject,
 588                             bool RemoveBytecode) {
 589   // Execute the program, generating an output file...
 590   std::string Output = executeProgram("", BytecodeFile, SharedObject);
 591
 592   std::string Error;
 593   bool FilesDifferent = false;
 594   if (DiffFiles(ReferenceOutputFile, Output, &Error)) {
 595     if (!Error.empty()) {
 596       std::cerr << "While diffing output: " << Error << "\n";
 597       exit(1);
 598     }
 599     FilesDifferent = true;
 600   }
 601
 602   if (RemoveBytecode) removeFile(BytecodeFile);
 603   return FilesDifferent;
 604 }
 605
 606 bool BugDriver::isExecutingJIT() {
 607   return InterpreterSel == RunJIT;
 608 }