contrib/llvm-project/llvm/lib/Passes/StandardInstrumentations.cpp

   1 //===- Standard pass instrumentations handling ----------------*- C++ -*--===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 /// \file
   9 ///
  10 /// This file defines IR-printing pass instrumentation callbacks as well as
  11 /// StandardInstrumentations class that manages standard pass instrumentations.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Passes/StandardInstrumentations.h"
  16 #include "llvm/ADT/Any.h"
  17 #include "llvm/ADT/Optional.h"
  18 #include "llvm/ADT/StringRef.h"
  19 #include "llvm/Analysis/CallGraphSCCPass.h"
  20 #include "llvm/Analysis/LazyCallGraph.h"
  21 #include "llvm/Analysis/LoopInfo.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/Function.h"
  24 #include "llvm/IR/LegacyPassManager.h"
  25 #include "llvm/IR/Module.h"
  26 #include "llvm/IR/PassInstrumentation.h"
  27 #include "llvm/IR/PassManager.h"
  28 #include "llvm/IR/PrintPasses.h"
  29 #include "llvm/IR/Verifier.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/CrashRecoveryContext.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/FormatVariadic.h"
  34 #include "llvm/Support/GraphWriter.h"
  35 #include "llvm/Support/MemoryBuffer.h"
  36 #include "llvm/Support/Program.h"
  37 #include "llvm/Support/Regex.h"
  38 #include "llvm/Support/Signals.h"
  39 #include "llvm/Support/raw_ostream.h"
  40 #include <unordered_map>
  41 #include <unordered_set>
  42 #include <utility>
  43 #include <vector>
  44
  45 using namespace llvm;
  46
  47 cl::opt<bool> PreservedCFGCheckerInstrumentation::VerifyPreservedCFG(
  48     "verify-cfg-preserved", cl::Hidden,
  49 #ifdef NDEBUG
  50     cl::init(false)
  51 #else
  52     cl::init(true)
  53 #endif
  54     );
  55
  56 // An option that prints out the IR after passes, similar to
  57 // -print-after-all except that it only prints the IR after passes that
  58 // change the IR.  Those passes that do not make changes to the IR are
  59 // reported as not making any changes.  In addition, the initial IR is
  60 // also reported.  Other hidden options affect the output from this
  61 // option.  -filter-passes will limit the output to the named passes
  62 // that actually change the IR and other passes are reported as filtered out.
  63 // The specified passes will either be reported as making no changes (with
  64 // no IR reported) or the changed IR will be reported.  Also, the
  65 // -filter-print-funcs and -print-module-scope options will do similar
  66 // filtering based on function name, reporting changed IRs as functions(or
  67 // modules if -print-module-scope is specified) for a particular function
  68 // or indicating that the IR has been filtered out.  The extra options
  69 // can be combined, allowing only changed IRs for certain passes on certain
  70 // functions to be reported in different formats, with the rest being
  71 // reported as filtered out.  The -print-before-changed option will print
  72 // the IR as it was before each pass that changed it.  The optional
  73 // value of quiet will only report when the IR changes, suppressing
  74 // all other messages, including the initial IR.  The values "diff" and
  75 // "diff-quiet" will present the changes in a form similar to a patch, in
  76 // either verbose or quiet mode, respectively.  The lines that are removed
  77 // and added are prefixed with '-' and '+', respectively.  The
  78 // -filter-print-funcs and -filter-passes can be used to filter the output.
  79 // This reporter relies on the linux diff utility to do comparisons and
  80 // insert the prefixes.  For systems that do not have the necessary
  81 // facilities, the error message will be shown in place of the expected output.
  82 //
  83 enum class ChangePrinter {
  84   None,
  85   Verbose,
  86   Quiet,
  87   DiffVerbose,
  88   DiffQuiet,
  89   ColourDiffVerbose,
  90   ColourDiffQuiet,
  91   DotCfgVerbose,
  92   DotCfgQuiet,
  93 };
  94 static cl::opt<ChangePrinter> PrintChanged(
  95     "print-changed", cl::desc("Print changed IRs"), cl::Hidden,
  96     cl::ValueOptional, cl::init(ChangePrinter::None),
  97     cl::values(
  98         clEnumValN(ChangePrinter::Quiet, "quiet", "Run in quiet mode"),
  99         clEnumValN(ChangePrinter::DiffVerbose, "diff",
 100                    "Display patch-like changes"),
 101         clEnumValN(ChangePrinter::DiffQuiet, "diff-quiet",
 102                    "Display patch-like changes in quiet mode"),
 103         clEnumValN(ChangePrinter::ColourDiffVerbose, "cdiff",
 104                    "Display patch-like changes with color"),
 105         clEnumValN(ChangePrinter::ColourDiffQuiet, "cdiff-quiet",
 106                    "Display patch-like changes in quiet mode with color"),
 107         clEnumValN(ChangePrinter::DotCfgVerbose, "dot-cfg",
 108                    "Create a website with graphical changes"),
 109         clEnumValN(ChangePrinter::DotCfgQuiet, "dot-cfg-quiet",
 110                    "Create a website with graphical changes in quiet mode"),
 111         // Sentinel value for unspecified option.
 112         clEnumValN(ChangePrinter::Verbose, "", "")));
 113
 114 // An option that supports the -print-changed option.  See
 115 // the description for -print-changed for an explanation of the use
 116 // of this option.  Note that this option has no effect without -print-changed.
 117 static cl::list<std::string>
 118     PrintPassesList("filter-passes", cl::value_desc("pass names"),
 119                     cl::desc("Only consider IR changes for passes whose names "
 120                              "match for the print-changed option"),
 121                     cl::CommaSeparated, cl::Hidden);
 122 // An option that supports the -print-changed option.  See
 123 // the description for -print-changed for an explanation of the use
 124 // of this option.  Note that this option has no effect without -print-changed.
 125 static cl::opt<bool>
 126     PrintChangedBefore("print-before-changed",
 127                        cl::desc("Print before passes that change them"),
 128                        cl::init(false), cl::Hidden);
 129
 130 // An option for specifying the diff used by print-changed=[diff | diff-quiet]
 131 static cl::opt<std::string>
 132     DiffBinary("print-changed-diff-path", cl::Hidden, cl::init("diff"),
 133                cl::desc("system diff used by change reporters"));
 134
 135 // An option for specifying the dot used by
 136 // print-changed=[dot-cfg | dot-cfg-quiet]
 137 static cl::opt<std::string>
 138     DotBinary("print-changed-dot-path", cl::Hidden, cl::init("dot"),
 139               cl::desc("system dot used by change reporters"));
 140
 141 // An option that determines the colour used for elements that are only
 142 // in the before part.  Must be a colour named in appendix J of
 143 // https://graphviz.org/pdf/dotguide.pdf
 144 cl::opt<std::string>
 145     BeforeColour("dot-cfg-before-color",
 146                  cl::desc("Color for dot-cfg before elements."), cl::Hidden,
 147                  cl::init("red"));
 148 // An option that determines the colour used for elements that are only
 149 // in the after part.  Must be a colour named in appendix J of
 150 // https://graphviz.org/pdf/dotguide.pdf
 151 cl::opt<std::string> AfterColour("dot-cfg-after-color",
 152                                  cl::desc("Color for dot-cfg after elements."),
 153                                  cl::Hidden, cl::init("forestgreen"));
 154 // An option that determines the colour used for elements that are in both
 155 // the before and after parts.  Must be a colour named in appendix J of
 156 // https://graphviz.org/pdf/dotguide.pdf
 157 cl::opt<std::string>
 158     CommonColour("dot-cfg-common-color",
 159                  cl::desc("Color for dot-cfg common elements."), cl::Hidden,
 160                  cl::init("black"));
 161
 162 // An option that determines where the generated website file (named
 163 // passes.html) and the associated pdf files (named diff_*.pdf) are saved.
 164 static cl::opt<std::string> DotCfgDir(
 165     "dot-cfg-dir",
 166     cl::desc("Generate dot files into specified directory for changed IRs"),
 167     cl::Hidden, cl::init("./"));
 168
 169 // An option to print the IR that was being processed when a pass crashes.
 170 static cl::opt<bool>
 171     PrintCrashIR("print-on-crash",
 172                  cl::desc("Print the last form of the IR before crash"),
 173                  cl::init(false), cl::Hidden);
 174
 175 namespace {
 176
 177 // Perform a system based diff between \p Before and \p After, using
 178 // \p OldLineFormat, \p NewLineFormat, and \p UnchangedLineFormat
 179 // to control the formatting of the output.  Return an error message
 180 // for any failures instead of the diff.
 181 std::string doSystemDiff(StringRef Before, StringRef After,
 182                          StringRef OldLineFormat, StringRef NewLineFormat,
 183                          StringRef UnchangedLineFormat) {
 184   StringRef SR[2]{Before, After};
 185   // Store the 2 bodies into temporary files and call diff on them
 186   // to get the body of the node.
 187   const unsigned NumFiles = 3;
 188   static std::string FileName[NumFiles];
 189   static int FD[NumFiles]{-1, -1, -1};
 190   for (unsigned I = 0; I < NumFiles; ++I) {
 191     if (FD[I] == -1) {
 192       SmallVector<char, 200> SV;
 193       std::error_code EC =
 194           sys::fs::createTemporaryFile("tmpdiff", "txt", FD[I], SV);
 195       if (EC)
 196         return "Unable to create temporary file.";
 197       FileName[I] = Twine(SV).str();
 198     }
 199     // The third file is used as the result of the diff.
 200     if (I == NumFiles - 1)
 201       break;
 202
 203     std::error_code EC = sys::fs::openFileForWrite(FileName[I], FD[I]);
 204     if (EC)
 205       return "Unable to open temporary file for writing.";
 206
 207     raw_fd_ostream OutStream(FD[I], /*shouldClose=*/true);
 208     if (FD[I] == -1)
 209       return "Error opening file for writing.";
 210     OutStream << SR[I];
 211   }
 212
 213   static ErrorOr<std::string> DiffExe = sys::findProgramByName(DiffBinary);
 214   if (!DiffExe)
 215     return "Unable to find diff executable.";
 216
 217   SmallString<128> OLF = formatv("--old-line-format={0}", OldLineFormat);
 218   SmallString<128> NLF = formatv("--new-line-format={0}", NewLineFormat);
 219   SmallString<128> ULF =
 220       formatv("--unchanged-line-format={0}", UnchangedLineFormat);
 221
 222   StringRef Args[] = {DiffBinary, "-w", "-d",        OLF,
 223                       NLF,        ULF,  FileName[0], FileName[1]};
 224   Optional<StringRef> Redirects[] = {None, StringRef(FileName[2]), None};
 225   int Result = sys::ExecuteAndWait(*DiffExe, Args, None, Redirects);
 226   if (Result < 0)
 227     return "Error executing system diff.";
 228   std::string Diff;
 229   auto B = MemoryBuffer::getFile(FileName[2]);
 230   if (B && *B)
 231     Diff = (*B)->getBuffer().str();
 232   else
 233     return "Unable to read result.";
 234
 235   // Clean up.
 236   for (const std::string &I : FileName) {
 237     std::error_code EC = sys::fs::remove(I);
 238     if (EC)
 239       return "Unable to remove temporary file.";
 240   }
 241   return Diff;
 242 }
 243
 244 /// Extract Module out of \p IR unit. May return nullptr if \p IR does not match
 245 /// certain global filters. Will never return nullptr if \p Force is true.
 246 const Module *unwrapModule(Any IR, bool Force = false) {
 247   if (any_isa<const Module *>(IR))
 248     return any_cast<const Module *>(IR);
 249
 250   if (any_isa<const Function *>(IR)) {
 251     const Function *F = any_cast<const Function *>(IR);
 252     if (!Force && !isFunctionInPrintList(F->getName()))
 253       return nullptr;
 254
 255     return F->getParent();
 256   }
 257
 258   if (any_isa<const LazyCallGraph::SCC *>(IR)) {
 259     const LazyCallGraph::SCC *C = any_cast<const LazyCallGraph::SCC *>(IR);
 260     for (const LazyCallGraph::Node &N : *C) {
 261       const Function &F = N.getFunction();
 262       if (Force || (!F.isDeclaration() && isFunctionInPrintList(F.getName()))) {
 263         return F.getParent();
 264       }
 265     }
 266     assert(!Force && "Expected a module");
 267     return nullptr;
 268   }
 269
 270   if (any_isa<const Loop *>(IR)) {
 271     const Loop *L = any_cast<const Loop *>(IR);
 272     const Function *F = L->getHeader()->getParent();
 273     if (!Force && !isFunctionInPrintList(F->getName()))
 274       return nullptr;
 275     return F->getParent();
 276   }
 277
 278   llvm_unreachable("Unknown IR unit");
 279 }
 280
 281 void printIR(raw_ostream &OS, const Function *F) {
 282   if (!isFunctionInPrintList(F->getName()))
 283     return;
 284   OS << *F;
 285 }
 286
 287 void printIR(raw_ostream &OS, const Module *M) {
 288   if (isFunctionInPrintList("*") || forcePrintModuleIR()) {
 289     M->print(OS, nullptr);
 290   } else {
 291     for (const auto &F : M->functions()) {
 292       printIR(OS, &F);
 293     }
 294   }
 295 }
 296
 297 void printIR(raw_ostream &OS, const LazyCallGraph::SCC *C) {
 298   for (const LazyCallGraph::Node &N : *C) {
 299     const Function &F = N.getFunction();
 300     if (!F.isDeclaration() && isFunctionInPrintList(F.getName())) {
 301       F.print(OS);
 302     }
 303   }
 304 }
 305
 306 void printIR(raw_ostream &OS, const Loop *L) {
 307   const Function *F = L->getHeader()->getParent();
 308   if (!isFunctionInPrintList(F->getName()))
 309     return;
 310   printLoop(const_cast<Loop &>(*L), OS);
 311 }
 312
 313 std::string getIRName(Any IR) {
 314   if (any_isa<const Module *>(IR))
 315     return "[module]";
 316
 317   if (any_isa<const Function *>(IR)) {
 318     const Function *F = any_cast<const Function *>(IR);
 319     return F->getName().str();
 320   }
 321
 322   if (any_isa<const LazyCallGraph::SCC *>(IR)) {
 323     const LazyCallGraph::SCC *C = any_cast<const LazyCallGraph::SCC *>(IR);
 324     return C->getName();
 325   }
 326
 327   if (any_isa<const Loop *>(IR)) {
 328     const Loop *L = any_cast<const Loop *>(IR);
 329     std::string S;
 330     raw_string_ostream OS(S);
 331     L->print(OS, /*Verbose*/ false, /*PrintNested*/ false);
 332     return OS.str();
 333   }
 334
 335   llvm_unreachable("Unknown wrapped IR type");
 336 }
 337
 338 bool moduleContainsFilterPrintFunc(const Module &M) {
 339   return any_of(M.functions(),
 340                 [](const Function &F) {
 341                   return isFunctionInPrintList(F.getName());
 342                 }) ||
 343          isFunctionInPrintList("*");
 344 }
 345
 346 bool sccContainsFilterPrintFunc(const LazyCallGraph::SCC &C) {
 347   return any_of(C,
 348                 [](const LazyCallGraph::Node &N) {
 349                   return isFunctionInPrintList(N.getName());
 350                 }) ||
 351          isFunctionInPrintList("*");
 352 }
 353
 354 bool shouldPrintIR(Any IR) {
 355   if (any_isa<const Module *>(IR)) {
 356     const Module *M = any_cast<const Module *>(IR);
 357     return moduleContainsFilterPrintFunc(*M);
 358   }
 359
 360   if (any_isa<const Function *>(IR)) {
 361     const Function *F = any_cast<const Function *>(IR);
 362     return isFunctionInPrintList(F->getName());
 363   }
 364
 365   if (any_isa<const LazyCallGraph::SCC *>(IR)) {
 366     const LazyCallGraph::SCC *C = any_cast<const LazyCallGraph::SCC *>(IR);
 367     return sccContainsFilterPrintFunc(*C);
 368   }
 369
 370   if (any_isa<const Loop *>(IR)) {
 371     const Loop *L = any_cast<const Loop *>(IR);
 372     return isFunctionInPrintList(L->getHeader()->getParent()->getName());
 373   }
 374   llvm_unreachable("Unknown wrapped IR type");
 375 }
 376
 377 /// Generic IR-printing helper that unpacks a pointer to IRUnit wrapped into
 378 /// llvm::Any and does actual print job.
 379 void unwrapAndPrint(raw_ostream &OS, Any IR) {
 380   if (!shouldPrintIR(IR))
 381     return;
 382
 383   if (forcePrintModuleIR()) {
 384     auto *M = unwrapModule(IR);
 385     assert(M && "should have unwrapped module");
 386     printIR(OS, M);
 387     return;
 388   }
 389
 390   if (any_isa<const Module *>(IR)) {
 391     const Module *M = any_cast<const Module *>(IR);
 392     printIR(OS, M);
 393     return;
 394   }
 395
 396   if (any_isa<const Function *>(IR)) {
 397     const Function *F = any_cast<const Function *>(IR);
 398     printIR(OS, F);
 399     return;
 400   }
 401
 402   if (any_isa<const LazyCallGraph::SCC *>(IR)) {
 403     const LazyCallGraph::SCC *C = any_cast<const LazyCallGraph::SCC *>(IR);
 404     printIR(OS, C);
 405     return;
 406   }
 407
 408   if (any_isa<const Loop *>(IR)) {
 409     const Loop *L = any_cast<const Loop *>(IR);
 410     printIR(OS, L);
 411     return;
 412   }
 413   llvm_unreachable("Unknown wrapped IR type");
 414 }
 415
 416 // Return true when this is a pass for which changes should be ignored
 417 bool isIgnored(StringRef PassID) {
 418   return isSpecialPass(PassID,
 419                        {"PassManager", "PassAdaptor", "AnalysisManagerProxy",
 420                         "DevirtSCCRepeatedPass", "ModuleInlinerWrapperPass"});
 421 }
 422
 423 std::string makeHTMLReady(StringRef SR) {
 424   std::string S;
 425   while (true) {
 426     StringRef Clean =
 427         SR.take_until([](char C) { return C == '<' || C == '>'; });
 428     S.append(Clean.str());
 429     SR = SR.drop_front(Clean.size());
 430     if (SR.size() == 0)
 431       return S;
 432     S.append(SR[0] == '<' ? "&lt;" : "&gt;");
 433     SR = SR.drop_front();
 434   }
 435   llvm_unreachable("problems converting string to HTML");
 436 }
 437
 438 // Return the module when that is the appropriate level of comparison for \p IR.
 439 const Module *getModuleForComparison(Any IR) {
 440   if (any_isa<const Module *>(IR))
 441     return any_cast<const Module *>(IR);
 442   if (any_isa<const LazyCallGraph::SCC *>(IR))
 443     return any_cast<const LazyCallGraph::SCC *>(IR)
 444         ->begin()
 445         ->getFunction()
 446         .getParent();
 447   return nullptr;
 448 }
 449
 450 bool isInterestingFunction(const Function &F) {
 451   return isFunctionInPrintList(F.getName());
 452 }
 453
 454 bool isInterestingPass(StringRef PassID) {
 455   if (isIgnored(PassID))
 456     return false;
 457
 458   static std::unordered_set<std::string> PrintPassNames(PrintPassesList.begin(),
 459                                                         PrintPassesList.end());
 460   return PrintPassNames.empty() || PrintPassNames.count(PassID.str());
 461 }
 462
 463 // Return true when this is a pass on IR for which printing
 464 // of changes is desired.
 465 bool isInteresting(Any IR, StringRef PassID) {
 466   if (!isInterestingPass(PassID))
 467     return false;
 468   if (any_isa<const Function *>(IR))
 469     return isInterestingFunction(*any_cast<const Function *>(IR));
 470   return true;
 471 }
 472
 473 } // namespace
 474
 475 template <typename T> ChangeReporter<T>::~ChangeReporter() {
 476   assert(BeforeStack.empty() && "Problem with Change Printer stack.");
 477 }
 478
 479 template <typename T>
 480 void ChangeReporter<T>::saveIRBeforePass(Any IR, StringRef PassID) {
 481   // Always need to place something on the stack because invalidated passes
 482   // are not given the IR so it cannot be determined whether the pass was for
 483   // something that was filtered out.
 484   BeforeStack.emplace_back();
 485
 486   if (!isInteresting(IR, PassID))
 487     return;
 488   // Is this the initial IR?
 489   if (InitialIR) {
 490     InitialIR = false;
 491     if (VerboseMode)
 492       handleInitialIR(IR);
 493   }
 494
 495   // Save the IR representation on the stack.
 496   T &Data = BeforeStack.back();
 497   generateIRRepresentation(IR, PassID, Data);
 498 }
 499
 500 template <typename T>
 501 void ChangeReporter<T>::handleIRAfterPass(Any IR, StringRef PassID) {
 502   assert(!BeforeStack.empty() && "Unexpected empty stack encountered.");
 503
 504   std::string Name = getIRName(IR);
 505
 506   if (isIgnored(PassID)) {
 507     if (VerboseMode)
 508       handleIgnored(PassID, Name);
 509   } else if (!isInteresting(IR, PassID)) {
 510     if (VerboseMode)
 511       handleFiltered(PassID, Name);
 512   } else {
 513     // Get the before rep from the stack
 514     T &Before = BeforeStack.back();
 515     // Create the after rep
 516     T After;
 517     generateIRRepresentation(IR, PassID, After);
 518
 519     // Was there a change in IR?
 520     if (Before == After) {
 521       if (VerboseMode)
 522         omitAfter(PassID, Name);
 523     } else
 524       handleAfter(PassID, Name, Before, After, IR);
 525   }
 526   BeforeStack.pop_back();
 527 }
 528
 529 template <typename T>
 530 void ChangeReporter<T>::handleInvalidatedPass(StringRef PassID) {
 531   assert(!BeforeStack.empty() && "Unexpected empty stack encountered.");
 532
 533   // Always flag it as invalidated as we cannot determine when
 534   // a pass for a filtered function is invalidated since we do not
 535   // get the IR in the call.  Also, the output is just alternate
 536   // forms of the banner anyway.
 537   if (VerboseMode)
 538     handleInvalidated(PassID);
 539   BeforeStack.pop_back();
 540 }
 541
 542 template <typename T>
 543 void ChangeReporter<T>::registerRequiredCallbacks(
 544     PassInstrumentationCallbacks &PIC) {
 545   PIC.registerBeforeNonSkippedPassCallback(
 546       [this](StringRef P, Any IR) { saveIRBeforePass(IR, P); });
 547
 548   PIC.registerAfterPassCallback(
 549       [this](StringRef P, Any IR, const PreservedAnalyses &) {
 550         handleIRAfterPass(IR, P);
 551       });
 552   PIC.registerAfterPassInvalidatedCallback(
 553       [this](StringRef P, const PreservedAnalyses &) {
 554         handleInvalidatedPass(P);
 555       });
 556 }
 557
 558 template <typename T>
 559 TextChangeReporter<T>::TextChangeReporter(bool Verbose)
 560     : ChangeReporter<T>(Verbose), Out(dbgs()) {}
 561
 562 template <typename T> void TextChangeReporter<T>::handleInitialIR(Any IR) {
 563   // Always print the module.
 564   // Unwrap and print directly to avoid filtering problems in general routines.
 565   auto *M = unwrapModule(IR, /*Force=*/true);
 566   assert(M && "Expected module to be unwrapped when forced.");
 567   Out << "*** IR Dump At Start ***\n";
 568   M->print(Out, nullptr);
 569 }
 570
 571 template <typename T>
 572 void TextChangeReporter<T>::omitAfter(StringRef PassID, std::string &Name) {
 573   Out << formatv("*** IR Dump After {0} on {1} omitted because no change ***\n",
 574                  PassID, Name);
 575 }
 576
 577 template <typename T>
 578 void TextChangeReporter<T>::handleInvalidated(StringRef PassID) {
 579   Out << formatv("*** IR Pass {0} invalidated ***\n", PassID);
 580 }
 581
 582 template <typename T>
 583 void TextChangeReporter<T>::handleFiltered(StringRef PassID,
 584                                            std::string &Name) {
 585   SmallString<20> Banner =
 586       formatv("*** IR Dump After {0} on {1} filtered out ***\n", PassID, Name);
 587   Out << Banner;
 588 }
 589
 590 template <typename T>
 591 void TextChangeReporter<T>::handleIgnored(StringRef PassID, std::string &Name) {
 592   Out << formatv("*** IR Pass {0} on {1} ignored ***\n", PassID, Name);
 593 }
 594
 595 IRChangedPrinter::~IRChangedPrinter() = default;
 596
 597 void IRChangedPrinter::registerCallbacks(PassInstrumentationCallbacks &PIC) {
 598   if (PrintChanged == ChangePrinter::Verbose ||
 599       PrintChanged == ChangePrinter::Quiet)
 600     TextChangeReporter<std::string>::registerRequiredCallbacks(PIC);
 601 }
 602
 603 void IRChangedPrinter::generateIRRepresentation(Any IR, StringRef PassID,
 604                                                 std::string &Output) {
 605   raw_string_ostream OS(Output);
 606   unwrapAndPrint(OS, IR);
 607   OS.str();
 608 }
 609
 610 void IRChangedPrinter::handleAfter(StringRef PassID, std::string &Name,
 611                                    const std::string &Before,
 612                                    const std::string &After, Any) {
 613   // Report the IR before the changes when requested.
 614   if (PrintChangedBefore)
 615     Out << "*** IR Dump Before " << PassID << " on " << Name << " ***\n"
 616         << Before;
 617
 618   // We might not get anything to print if we only want to print a specific
 619   // function but it gets deleted.
 620   if (After.empty()) {
 621     Out << "*** IR Deleted After " << PassID << " on " << Name << " ***\n";
 622     return;
 623   }
 624
 625   Out << "*** IR Dump After " << PassID << " on " << Name << " ***\n" << After;
 626 }
 627
 628 template <typename T>
 629 void OrderedChangedData<T>::report(
 630     const OrderedChangedData &Before, const OrderedChangedData &After,
 631     function_ref<void(const T *, const T *)> HandlePair) {
 632   const auto &BFD = Before.getData();
 633   const auto &AFD = After.getData();
 634   std::vector<std::string>::const_iterator BI = Before.getOrder().begin();
 635   std::vector<std::string>::const_iterator BE = Before.getOrder().end();
 636   std::vector<std::string>::const_iterator AI = After.getOrder().begin();
 637   std::vector<std::string>::const_iterator AE = After.getOrder().end();
 638
 639   auto HandlePotentiallyRemovedData = [&](std::string S) {
 640     // The order in LLVM may have changed so check if still exists.
 641     if (!AFD.count(S)) {
 642       // This has been removed.
 643       HandlePair(&BFD.find(*BI)->getValue(), nullptr);
 644     }
 645   };
 646   auto HandleNewData = [&](std::vector<const T *> &Q) {
 647     // Print out any queued up new sections
 648     for (const T *NBI : Q)
 649       HandlePair(nullptr, NBI);
 650     Q.clear();
 651   };
 652
 653   // Print out the data in the after order, with before ones interspersed
 654   // appropriately (ie, somewhere near where they were in the before list).
 655   // Start at the beginning of both lists.  Loop through the
 656   // after list.  If an element is common, then advance in the before list
 657   // reporting the removed ones until the common one is reached.  Report any
 658   // queued up new ones and then report the common one.  If an element is not
 659   // common, then enqueue it for reporting.  When the after list is exhausted,
 660   // loop through the before list, reporting any removed ones.  Finally,
 661   // report the rest of the enqueued new ones.
 662   std::vector<const T *> NewDataQueue;
 663   while (AI != AE) {
 664     if (!BFD.count(*AI)) {
 665       // This section is new so place it in the queue.  This will cause it
 666       // to be reported after deleted sections.
 667       NewDataQueue.emplace_back(&AFD.find(*AI)->getValue());
 668       ++AI;
 669       continue;
 670     }
 671     // This section is in both; advance and print out any before-only
 672     // until we get to it.
 673     while (*BI != *AI) {
 674       HandlePotentiallyRemovedData(*BI);
 675       ++BI;
 676     }
 677     // Report any new sections that were queued up and waiting.
 678     HandleNewData(NewDataQueue);
 679
 680     const T &AData = AFD.find(*AI)->getValue();
 681     const T &BData = BFD.find(*AI)->getValue();
 682     HandlePair(&BData, &AData);
 683     ++BI;
 684     ++AI;
 685   }
 686
 687   // Check any remaining before sections to see if they have been removed
 688   while (BI != BE) {
 689     HandlePotentiallyRemovedData(*BI);
 690     ++BI;
 691   }
 692
 693   HandleNewData(NewDataQueue);
 694 }
 695
 696 template <typename T>
 697 void IRComparer<T>::compare(
 698     bool CompareModule,
 699     std::function<void(bool InModule, unsigned Minor,
 700                        const FuncDataT<T> &Before, const FuncDataT<T> &After)>
 701         CompareFunc) {
 702   if (!CompareModule) {
 703     // Just handle the single function.
 704     assert(Before.getData().size() == 1 && After.getData().size() == 1 &&
 705            "Expected only one function.");
 706     CompareFunc(false, 0, Before.getData().begin()->getValue(),
 707                 After.getData().begin()->getValue());
 708     return;
 709   }
 710
 711   unsigned Minor = 0;
 712   FuncDataT<T> Missing("");
 713   IRDataT<T>::report(Before, After,
 714                      [&](const FuncDataT<T> *B, const FuncDataT<T> *A) {
 715                        assert((B || A) && "Both functions cannot be missing.");
 716                        if (!B)
 717                          B = &Missing;
 718                        else if (!A)
 719                          A = &Missing;
 720                        CompareFunc(true, Minor++, *B, *A);
 721                      });
 722 }
 723
 724 template <typename T> void IRComparer<T>::analyzeIR(Any IR, IRDataT<T> &Data) {
 725   if (const Module *M = getModuleForComparison(IR)) {
 726     // Create data for each existing/interesting function in the module.
 727     for (const Function &F : *M)
 728       generateFunctionData(Data, F);
 729     return;
 730   }
 731
 732   const Function *F = nullptr;
 733   if (any_isa<const Function *>(IR))
 734     F = any_cast<const Function *>(IR);
 735   else {
 736     assert(any_isa<const Loop *>(IR) && "Unknown IR unit.");
 737     const Loop *L = any_cast<const Loop *>(IR);
 738     F = L->getHeader()->getParent();
 739   }
 740   assert(F && "Unknown IR unit.");
 741   generateFunctionData(Data, *F);
 742 }
 743
 744 template <typename T>
 745 bool IRComparer<T>::generateFunctionData(IRDataT<T> &Data, const Function &F) {
 746   if (!F.isDeclaration() && isFunctionInPrintList(F.getName())) {
 747     FuncDataT<T> FD(F.getEntryBlock().getName().str());
 748     for (const auto &B : F) {
 749       FD.getOrder().emplace_back(B.getName());
 750       FD.getData().insert({B.getName(), B});
 751     }
 752     Data.getOrder().emplace_back(F.getName());
 753     Data.getData().insert({F.getName(), FD});
 754     return true;
 755   }
 756   return false;
 757 }
 758
 759 PrintIRInstrumentation::~PrintIRInstrumentation() {
 760   assert(ModuleDescStack.empty() && "ModuleDescStack is not empty at exit");
 761 }
 762
 763 void PrintIRInstrumentation::pushModuleDesc(StringRef PassID, Any IR) {
 764   const Module *M = unwrapModule(IR);
 765   ModuleDescStack.emplace_back(M, getIRName(IR), PassID);
 766 }
 767
 768 PrintIRInstrumentation::PrintModuleDesc
 769 PrintIRInstrumentation::popModuleDesc(StringRef PassID) {
 770   assert(!ModuleDescStack.empty() && "empty ModuleDescStack");
 771   PrintModuleDesc ModuleDesc = ModuleDescStack.pop_back_val();
 772   assert(std::get<2>(ModuleDesc).equals(PassID) && "malformed ModuleDescStack");
 773   return ModuleDesc;
 774 }
 775
 776 void PrintIRInstrumentation::printBeforePass(StringRef PassID, Any IR) {
 777   if (isIgnored(PassID))
 778     return;
 779
 780   // Saving Module for AfterPassInvalidated operations.
 781   // Note: here we rely on a fact that we do not change modules while
 782   // traversing the pipeline, so the latest captured module is good
 783   // for all print operations that has not happen yet.
 784   if (shouldPrintAfterPass(PassID))
 785     pushModuleDesc(PassID, IR);
 786
 787   if (!shouldPrintBeforePass(PassID))
 788     return;
 789
 790   if (!shouldPrintIR(IR))
 791     return;
 792
 793   dbgs() << "*** IR Dump Before " << PassID << " on " << getIRName(IR)
 794          << " ***\n";
 795   unwrapAndPrint(dbgs(), IR);
 796 }
 797
 798 void PrintIRInstrumentation::printAfterPass(StringRef PassID, Any IR) {
 799   if (isIgnored(PassID))
 800     return;
 801
 802   if (!shouldPrintAfterPass(PassID))
 803     return;
 804
 805   const Module *M;
 806   std::string IRName;
 807   StringRef StoredPassID;
 808   std::tie(M, IRName, StoredPassID) = popModuleDesc(PassID);
 809   assert(StoredPassID == PassID && "mismatched PassID");
 810
 811   if (!shouldPrintIR(IR))
 812     return;
 813
 814   dbgs() << "*** IR Dump After " << PassID << " on " << IRName << " ***\n";
 815   unwrapAndPrint(dbgs(), IR);
 816 }
 817
 818 void PrintIRInstrumentation::printAfterPassInvalidated(StringRef PassID) {
 819   StringRef PassName = PIC->getPassNameForClassName(PassID);
 820   if (!shouldPrintAfterPass(PassName))
 821     return;
 822
 823   if (isIgnored(PassID))
 824     return;
 825
 826   const Module *M;
 827   std::string IRName;
 828   StringRef StoredPassID;
 829   std::tie(M, IRName, StoredPassID) = popModuleDesc(PassID);
 830   assert(StoredPassID == PassID && "mismatched PassID");
 831   // Additional filtering (e.g. -filter-print-func) can lead to module
 832   // printing being skipped.
 833   if (!M)
 834     return;
 835
 836   SmallString<20> Banner =
 837       formatv("*** IR Dump After {0} on {1} (invalidated) ***", PassID, IRName);
 838   dbgs() << Banner << "\n";
 839   printIR(dbgs(), M);
 840 }
 841
 842 bool PrintIRInstrumentation::shouldPrintBeforePass(StringRef PassID) {
 843   if (shouldPrintBeforeAll())
 844     return true;
 845
 846   StringRef PassName = PIC->getPassNameForClassName(PassID);
 847   return is_contained(printBeforePasses(), PassName);
 848 }
 849
 850 bool PrintIRInstrumentation::shouldPrintAfterPass(StringRef PassID) {
 851   if (shouldPrintAfterAll())
 852     return true;
 853
 854   StringRef PassName = PIC->getPassNameForClassName(PassID);
 855   return is_contained(printAfterPasses(), PassName);
 856 }
 857
 858 void PrintIRInstrumentation::registerCallbacks(
 859     PassInstrumentationCallbacks &PIC) {
 860   this->PIC = &PIC;
 861
 862   // BeforePass callback is not just for printing, it also saves a Module
 863   // for later use in AfterPassInvalidated.
 864   if (shouldPrintBeforeSomePass() || shouldPrintAfterSomePass())
 865     PIC.registerBeforeNonSkippedPassCallback(
 866         [this](StringRef P, Any IR) { this->printBeforePass(P, IR); });
 867
 868   if (shouldPrintAfterSomePass()) {
 869     PIC.registerAfterPassCallback(
 870         [this](StringRef P, Any IR, const PreservedAnalyses &) {
 871           this->printAfterPass(P, IR);
 872         });
 873     PIC.registerAfterPassInvalidatedCallback(
 874         [this](StringRef P, const PreservedAnalyses &) {
 875           this->printAfterPassInvalidated(P);
 876         });
 877   }
 878 }
 879
 880 void OptNoneInstrumentation::registerCallbacks(
 881     PassInstrumentationCallbacks &PIC) {
 882   PIC.registerShouldRunOptionalPassCallback(
 883       [this](StringRef P, Any IR) { return this->shouldRun(P, IR); });
 884 }
 885
 886 bool OptNoneInstrumentation::shouldRun(StringRef PassID, Any IR) {
 887   const Function *F = nullptr;
 888   if (any_isa<const Function *>(IR)) {
 889     F = any_cast<const Function *>(IR);
 890   } else if (any_isa<const Loop *>(IR)) {
 891     F = any_cast<const Loop *>(IR)->getHeader()->getParent();
 892   }
 893   bool ShouldRun = !(F && F->hasOptNone());
 894   if (!ShouldRun && DebugLogging) {
 895     errs() << "Skipping pass " << PassID << " on " << F->getName()
 896            << " due to optnone attribute\n";
 897   }
 898   return ShouldRun;
 899 }
 900
 901 void OptBisectInstrumentation::registerCallbacks(
 902     PassInstrumentationCallbacks &PIC) {
 903   if (!getOptBisector().isEnabled())
 904     return;
 905   PIC.registerShouldRunOptionalPassCallback([](StringRef PassID, Any IR) {
 906     return isIgnored(PassID) ||
 907            getOptBisector().checkPass(PassID, getIRName(IR));
 908   });
 909 }
 910
 911 raw_ostream &PrintPassInstrumentation::print() {
 912   if (Opts.Indent) {
 913     assert(Indent >= 0);
 914     dbgs().indent(Indent);
 915   }
 916   return dbgs();
 917 }
 918
 919 void PrintPassInstrumentation::registerCallbacks(
 920     PassInstrumentationCallbacks &PIC) {
 921   if (!Enabled)
 922     return;
 923
 924   std::vector<StringRef> SpecialPasses;
 925   if (!Opts.Verbose) {
 926     SpecialPasses.emplace_back("PassManager");
 927     SpecialPasses.emplace_back("PassAdaptor");
 928   }
 929
 930   PIC.registerBeforeSkippedPassCallback([this, SpecialPasses](StringRef PassID,
 931                                                               Any IR) {
 932     assert(!isSpecialPass(PassID, SpecialPasses) &&
 933            "Unexpectedly skipping special pass");
 934
 935     print() << "Skipping pass: " << PassID << " on " << getIRName(IR) << "\n";
 936   });
 937   PIC.registerBeforeNonSkippedPassCallback([this, SpecialPasses](
 938                                                StringRef PassID, Any IR) {
 939     if (isSpecialPass(PassID, SpecialPasses))
 940       return;
 941
 942     auto &OS = print();
 943     OS << "Running pass: " << PassID << " on " << getIRName(IR);
 944     if (any_isa<const Function *>(IR)) {
 945       unsigned Count = any_cast<const Function *>(IR)->getInstructionCount();
 946       OS << " (" << Count << " instruction";
 947       if (Count != 1)
 948         OS << 's';
 949       OS << ')';
 950     } else if (any_isa<const LazyCallGraph::SCC *>(IR)) {
 951       int Count = any_cast<const LazyCallGraph::SCC *>(IR)->size();
 952       OS << " (" << Count << " node";
 953       if (Count != 1)
 954         OS << 's';
 955       OS << ')';
 956     }
 957     OS << "\n";
 958     Indent += 2;
 959   });
 960   PIC.registerAfterPassCallback(
 961       [this, SpecialPasses](StringRef PassID, Any IR,
 962                             const PreservedAnalyses &) {
 963         if (isSpecialPass(PassID, SpecialPasses))
 964           return;
 965
 966         Indent -= 2;
 967       });
 968   PIC.registerAfterPassInvalidatedCallback(
 969       [this, SpecialPasses](StringRef PassID, Any IR) {
 970         if (isSpecialPass(PassID, SpecialPasses))
 971           return;
 972
 973         Indent -= 2;
 974       });
 975
 976   if (!Opts.SkipAnalyses) {
 977     PIC.registerBeforeAnalysisCallback([this](StringRef PassID, Any IR) {
 978       print() << "Running analysis: " << PassID << " on " << getIRName(IR)
 979               << "\n";
 980       Indent += 2;
 981     });
 982     PIC.registerAfterAnalysisCallback(
 983         [this](StringRef PassID, Any IR) { Indent -= 2; });
 984     PIC.registerAnalysisInvalidatedCallback([this](StringRef PassID, Any IR) {
 985       print() << "Invalidating analysis: " << PassID << " on " << getIRName(IR)
 986               << "\n";
 987     });
 988     PIC.registerAnalysesClearedCallback([this](StringRef IRName) {
 989       print() << "Clearing all analysis results for: " << IRName << "\n";
 990     });
 991   }
 992 }
 993
 994 PreservedCFGCheckerInstrumentation::CFG::CFG(const Function *F,
 995                                              bool TrackBBLifetime) {
 996   if (TrackBBLifetime)
 997     BBGuards = DenseMap<intptr_t, BBGuard>(F->size());
 998   for (const auto &BB : *F) {
 999     if (BBGuards)
1000       BBGuards->try_emplace(intptr_t(&BB), &BB);
1001     for (auto *Succ : successors(&BB)) {
1002       Graph[&BB][Succ]++;
1003       if (BBGuards)
1004         BBGuards->try_emplace(intptr_t(Succ), Succ);
1005     }
1006   }
1007 }
1008
1009 static void printBBName(raw_ostream &out, const BasicBlock *BB) {
1010   if (BB->hasName()) {
1011     out << BB->getName() << "<" << BB << ">";
1012     return;
1013   }
1014
1015   if (!BB->getParent()) {
1016     out << "unnamed_removed<" << BB << ">";
1017     return;
1018   }
1019
1020   if (BB->isEntryBlock()) {
1021     out << "entry"
1022         << "<" << BB << ">";
1023     return;
1024   }
1025
1026   unsigned FuncOrderBlockNum = 0;
1027   for (auto &FuncBB : *BB->getParent()) {
1028     if (&FuncBB == BB)
1029       break;
1030     FuncOrderBlockNum++;
1031   }
1032   out << "unnamed_" << FuncOrderBlockNum << "<" << BB << ">";
1033 }
1034
1035 void PreservedCFGCheckerInstrumentation::CFG::printDiff(raw_ostream &out,
1036                                                         const CFG &Before,
1037                                                         const CFG &After) {
1038   assert(!After.isPoisoned());
1039   if (Before.isPoisoned()) {
1040     out << "Some blocks were deleted\n";
1041     return;
1042   }
1043
1044   // Find and print graph differences.
1045   if (Before.Graph.size() != After.Graph.size())
1046     out << "Different number of non-leaf basic blocks: before="
1047         << Before.Graph.size() << ", after=" << After.Graph.size() << "\n";
1048
1049   for (auto &BB : Before.Graph) {
1050     auto BA = After.Graph.find(BB.first);
1051     if (BA == After.Graph.end()) {
1052       out << "Non-leaf block ";
1053       printBBName(out, BB.first);
1054       out << " is removed (" << BB.second.size() << " successors)\n";
1055     }
1056   }
1057
1058   for (auto &BA : After.Graph) {
1059     auto BB = Before.Graph.find(BA.first);
1060     if (BB == Before.Graph.end()) {
1061       out << "Non-leaf block ";
1062       printBBName(out, BA.first);
1063       out << " is added (" << BA.second.size() << " successors)\n";
1064       continue;
1065     }
1066
1067     if (BB->second == BA.second)
1068       continue;
1069
1070     out << "Different successors of block ";
1071     printBBName(out, BA.first);
1072     out << " (unordered):\n";
1073     out << "- before (" << BB->second.size() << "): ";
1074     for (auto &SuccB : BB->second) {
1075       printBBName(out, SuccB.first);
1076       if (SuccB.second != 1)
1077         out << "(" << SuccB.second << "), ";
1078       else
1079         out << ", ";
1080     }
1081     out << "\n";
1082     out << "- after (" << BA.second.size() << "): ";
1083     for (auto &SuccA : BA.second) {
1084       printBBName(out, SuccA.first);
1085       if (SuccA.second != 1)
1086         out << "(" << SuccA.second << "), ";
1087       else
1088         out << ", ";
1089     }
1090     out << "\n";
1091   }
1092 }
1093
1094 // PreservedCFGCheckerInstrumentation uses PreservedCFGCheckerAnalysis to check
1095 // passes, that reported they kept CFG analyses up-to-date, did not actually
1096 // change CFG. This check is done as follows. Before every functional pass in
1097 // BeforeNonSkippedPassCallback a CFG snapshot (an instance of
1098 // PreservedCFGCheckerInstrumentation::CFG) is requested from
1099 // FunctionAnalysisManager as a result of PreservedCFGCheckerAnalysis. When the
1100 // functional pass finishes and reports that CFGAnalyses or AllAnalyses are
1101 // up-to-date then the cached result of PreservedCFGCheckerAnalysis (if
1102 // available) is checked to be equal to a freshly created CFG snapshot.
1103 struct PreservedCFGCheckerAnalysis
1104     : public AnalysisInfoMixin<PreservedCFGCheckerAnalysis> {
1105   friend AnalysisInfoMixin<PreservedCFGCheckerAnalysis>;
1106
1107   static AnalysisKey Key;
1108
1109 public:
1110   /// Provide the result type for this analysis pass.
1111   using Result = PreservedCFGCheckerInstrumentation::CFG;
1112
1113   /// Run the analysis pass over a function and produce CFG.
1114   Result run(Function &F, FunctionAnalysisManager &FAM) {
1115     return Result(&F, /* TrackBBLifetime */ true);
1116   }
1117 };
1118
1119 AnalysisKey PreservedCFGCheckerAnalysis::Key;
1120
1121 bool PreservedCFGCheckerInstrumentation::CFG::invalidate(
1122     Function &F, const PreservedAnalyses &PA,
1123     FunctionAnalysisManager::Invalidator &) {
1124   auto PAC = PA.getChecker<PreservedCFGCheckerAnalysis>();
1125   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
1126            PAC.preservedSet<CFGAnalyses>());
1127 }
1128
1129 void PreservedCFGCheckerInstrumentation::registerCallbacks(
1130     PassInstrumentationCallbacks &PIC, FunctionAnalysisManager &FAM) {
1131   if (!VerifyPreservedCFG)
1132     return;
1133
1134   FAM.registerPass([&] { return PreservedCFGCheckerAnalysis(); });
1135
1136   auto checkCFG = [](StringRef Pass, StringRef FuncName, const CFG &GraphBefore,
1137                      const CFG &GraphAfter) {
1138     if (GraphAfter == GraphBefore)
1139       return;
1140
1141     dbgs() << "Error: " << Pass
1142            << " does not invalidate CFG analyses but CFG changes detected in "
1143               "function @"
1144            << FuncName << ":\n";
1145     CFG::printDiff(dbgs(), GraphBefore, GraphAfter);
1146     report_fatal_error(Twine("CFG unexpectedly changed by ", Pass));
1147   };
1148
1149   PIC.registerBeforeNonSkippedPassCallback([this, &FAM](StringRef P, Any IR) {
1150 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
1151     assert(&PassStack.emplace_back(P));
1152 #endif
1153     (void)this;
1154     if (!any_isa<const Function *>(IR))
1155       return;
1156
1157     const auto *F = any_cast<const Function *>(IR);
1158     // Make sure a fresh CFG snapshot is available before the pass.
1159     FAM.getResult<PreservedCFGCheckerAnalysis>(*const_cast<Function *>(F));
1160   });
1161
1162   PIC.registerAfterPassInvalidatedCallback(
1163       [this](StringRef P, const PreservedAnalyses &PassPA) {
1164 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
1165         assert(PassStack.pop_back_val() == P &&
1166                "Before and After callbacks must correspond");
1167 #endif
1168         (void)this;
1169       });
1170
1171   PIC.registerAfterPassCallback([this, &FAM,
1172                                  checkCFG](StringRef P, Any IR,
1173                                            const PreservedAnalyses &PassPA) {
1174 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
1175     assert(PassStack.pop_back_val() == P &&
1176            "Before and After callbacks must correspond");
1177 #endif
1178     (void)this;
1179
1180     if (!any_isa<const Function *>(IR))
1181       return;
1182
1183     if (!PassPA.allAnalysesInSetPreserved<CFGAnalyses>() &&
1184         !PassPA.allAnalysesInSetPreserved<AllAnalysesOn<Function>>())
1185       return;
1186
1187     const auto *F = any_cast<const Function *>(IR);
1188     if (auto *GraphBefore = FAM.getCachedResult<PreservedCFGCheckerAnalysis>(
1189             *const_cast<Function *>(F)))
1190       checkCFG(P, F->getName(), *GraphBefore,
1191                CFG(F, /* TrackBBLifetime */ false));
1192   });
1193 }
1194
1195 void VerifyInstrumentation::registerCallbacks(
1196     PassInstrumentationCallbacks &PIC) {
1197   PIC.registerAfterPassCallback(
1198       [this](StringRef P, Any IR, const PreservedAnalyses &PassPA) {
1199         if (isIgnored(P) || P == "VerifierPass")
1200           return;
1201         if (any_isa<const Function *>(IR) || any_isa<const Loop *>(IR)) {
1202           const Function *F;
1203           if (any_isa<const Loop *>(IR))
1204             F = any_cast<const Loop *>(IR)->getHeader()->getParent();
1205           else
1206             F = any_cast<const Function *>(IR);
1207           if (DebugLogging)
1208             dbgs() << "Verifying function " << F->getName() << "\n";
1209
1210           if (verifyFunction(*F, &errs()))
1211             report_fatal_error("Broken function found, compilation aborted!");
1212         } else if (any_isa<const Module *>(IR) ||
1213                    any_isa<const LazyCallGraph::SCC *>(IR)) {
1214           const Module *M;
1215           if (any_isa<const LazyCallGraph::SCC *>(IR))
1216             M = any_cast<const LazyCallGraph::SCC *>(IR)
1217                     ->begin()
1218                     ->getFunction()
1219                     .getParent();
1220           else
1221             M = any_cast<const Module *>(IR);
1222           if (DebugLogging)
1223             dbgs() << "Verifying module " << M->getName() << "\n";
1224
1225           if (verifyModule(*M, &errs()))
1226             report_fatal_error("Broken module found, compilation aborted!");
1227         }
1228       });
1229 }
1230
1231 InLineChangePrinter::~InLineChangePrinter() = default;
1232
1233 void InLineChangePrinter::generateIRRepresentation(Any IR, StringRef PassID,
1234                                                    IRDataT<EmptyData> &D) {
1235   IRComparer<EmptyData>::analyzeIR(IR, D);
1236 }
1237
1238 void InLineChangePrinter::handleAfter(StringRef PassID, std::string &Name,
1239                                       const IRDataT<EmptyData> &Before,
1240                                       const IRDataT<EmptyData> &After, Any IR) {
1241   SmallString<20> Banner =
1242       formatv("*** IR Dump After {0} on {1} ***\n", PassID, Name);
1243   Out << Banner;
1244   IRComparer<EmptyData>(Before, After)
1245       .compare(getModuleForComparison(IR),
1246                [&](bool InModule, unsigned Minor,
1247                    const FuncDataT<EmptyData> &Before,
1248                    const FuncDataT<EmptyData> &After) -> void {
1249                  handleFunctionCompare(Name, "", PassID, " on ", InModule,
1250                                        Minor, Before, After);
1251                });
1252   Out << "\n";
1253 }
1254
1255 void InLineChangePrinter::handleFunctionCompare(
1256     StringRef Name, StringRef Prefix, StringRef PassID, StringRef Divider,
1257     bool InModule, unsigned Minor, const FuncDataT<EmptyData> &Before,
1258     const FuncDataT<EmptyData> &After) {
1259   // Print a banner when this is being shown in the context of a module
1260   if (InModule)
1261     Out << "\n*** IR for function " << Name << " ***\n";
1262
1263   FuncDataT<EmptyData>::report(
1264       Before, After,
1265       [&](const BlockDataT<EmptyData> *B, const BlockDataT<EmptyData> *A) {
1266         StringRef BStr = B ? B->getBody() : "\n";
1267         StringRef AStr = A ? A->getBody() : "\n";
1268         const std::string Removed =
1269             UseColour ? "\033[31m-%l\033[0m\n" : "-%l\n";
1270         const std::string Added = UseColour ? "\033[32m+%l\033[0m\n" : "+%l\n";
1271         const std::string NoChange = " %l\n";
1272         Out << doSystemDiff(BStr, AStr, Removed, Added, NoChange);
1273       });
1274 }
1275
1276 void InLineChangePrinter::registerCallbacks(PassInstrumentationCallbacks &PIC) {
1277   if (PrintChanged == ChangePrinter::DiffVerbose ||
1278       PrintChanged == ChangePrinter::DiffQuiet ||
1279       PrintChanged == ChangePrinter::ColourDiffVerbose ||
1280       PrintChanged == ChangePrinter::ColourDiffQuiet)
1281     TextChangeReporter<IRDataT<EmptyData>>::registerRequiredCallbacks(PIC);
1282 }
1283
1284 namespace {
1285
1286 class DisplayNode;
1287 class DotCfgDiffDisplayGraph;
1288
1289 // Base class for a node or edge in the dot-cfg-changes graph.
1290 class DisplayElement {
1291 public:
1292   // Is this in before, after, or both?
1293   StringRef getColour() const { return Colour; }
1294
1295 protected:
1296   DisplayElement(StringRef Colour) : Colour(Colour) {}
1297   const StringRef Colour;
1298 };
1299
1300 // An edge representing a transition between basic blocks in the
1301 // dot-cfg-changes graph.
1302 class DisplayEdge : public DisplayElement {
1303 public:
1304   DisplayEdge(std::string Value, DisplayNode &Node, StringRef Colour)
1305       : DisplayElement(Colour), Value(Value), Node(Node) {}
1306   // The value on which the transition is made.
1307   std::string getValue() const { return Value; }
1308   // The node (representing a basic block) reached by this transition.
1309   const DisplayNode &getDestinationNode() const { return Node; }
1310
1311 protected:
1312   std::string Value;
1313   const DisplayNode &Node;
1314 };
1315
1316 // A node in the dot-cfg-changes graph which represents a basic block.
1317 class DisplayNode : public DisplayElement {
1318 public:
1319   // \p C is the content for the node, \p T indicates the colour for the
1320   // outline of the node
1321   DisplayNode(std::string Content, StringRef Colour)
1322       : DisplayElement(Colour), Content(Content) {}
1323
1324   // Iterator to the child nodes.  Required by GraphWriter.
1325   using ChildIterator = std::unordered_set<DisplayNode *>::const_iterator;
1326   ChildIterator children_begin() const { return Children.cbegin(); }
1327   ChildIterator children_end() const { return Children.cend(); }
1328
1329   // Iterator for the edges.  Required by GraphWriter.
1330   using EdgeIterator = std::vector<DisplayEdge *>::const_iterator;
1331   EdgeIterator edges_begin() const { return EdgePtrs.cbegin(); }
1332   EdgeIterator edges_end() const { return EdgePtrs.cend(); }
1333
1334   // Create an edge to \p Node on value \p Value, with colour \p Colour.
1335   void createEdge(StringRef Value, DisplayNode &Node, StringRef Colour);
1336
1337   // Return the content of this node.
1338   std::string getContent() const { return Content; }
1339
1340   // Return the edge to node \p S.
1341   const DisplayEdge &getEdge(const DisplayNode &To) const {
1342     assert(EdgeMap.find(&To) != EdgeMap.end() && "Expected to find edge.");
1343     return *EdgeMap.find(&To)->second;
1344   }
1345
1346   // Return the value for the transition to basic block \p S.
1347   // Required by GraphWriter.
1348   std::string getEdgeSourceLabel(const DisplayNode &Sink) const {
1349     return getEdge(Sink).getValue();
1350   }
1351
1352   void createEdgeMap();
1353
1354 protected:
1355   const std::string Content;
1356
1357   // Place to collect all of the edges.  Once they are all in the vector,
1358   // the vector will not reallocate so then we can use pointers to them,
1359   // which are required by the graph writing routines.
1360   std::vector<DisplayEdge> Edges;
1361
1362   std::vector<DisplayEdge *> EdgePtrs;
1363   std::unordered_set<DisplayNode *> Children;
1364   std::unordered_map<const DisplayNode *, const DisplayEdge *> EdgeMap;
1365
1366   // Safeguard adding of edges.
1367   bool AllEdgesCreated = false;
1368 };
1369
1370 // Class representing a difference display (corresponds to a pdf file).
1371 class DotCfgDiffDisplayGraph {
1372 public:
1373   DotCfgDiffDisplayGraph(std::string Name) : GraphName(Name) {}
1374
1375   // Generate the file into \p DotFile.
1376   void generateDotFile(StringRef DotFile);
1377
1378   // Iterator to the nodes.  Required by GraphWriter.
1379   using NodeIterator = std::vector<DisplayNode *>::const_iterator;
1380   NodeIterator nodes_begin() const {
1381     assert(NodeGenerationComplete && "Unexpected children iterator creation");
1382     return NodePtrs.cbegin();
1383   }
1384   NodeIterator nodes_end() const {
1385     assert(NodeGenerationComplete && "Unexpected children iterator creation");
1386     return NodePtrs.cend();
1387   }
1388
1389   // Record the index of the entry node.  At this point, we can build up
1390   // vectors of pointers that are required by the graph routines.
1391   void setEntryNode(unsigned N) {
1392     // At this point, there will be no new nodes.
1393     assert(!NodeGenerationComplete && "Unexpected node creation");
1394     NodeGenerationComplete = true;
1395     for (auto &N : Nodes)
1396       NodePtrs.emplace_back(&N);
1397
1398     EntryNode = NodePtrs[N];
1399   }
1400
1401   // Create a node.
1402   void createNode(std::string C, StringRef Colour) {
1403     assert(!NodeGenerationComplete && "Unexpected node creation");
1404     Nodes.emplace_back(C, Colour);
1405   }
1406   // Return the node at index \p N to avoid problems with vectors reallocating.
1407   DisplayNode &getNode(unsigned N) {
1408     assert(N < Nodes.size() && "Node is out of bounds");
1409     return Nodes[N];
1410   }
1411   unsigned size() const {
1412     assert(NodeGenerationComplete && "Unexpected children iterator creation");
1413     return Nodes.size();
1414   }
1415
1416   // Return the name of the graph.  Required by GraphWriter.
1417   std::string getGraphName() const { return GraphName; }
1418
1419   // Return the string representing the differences for basic block \p Node.
1420   // Required by GraphWriter.
1421   std::string getNodeLabel(const DisplayNode &Node) const {
1422     return Node.getContent();
1423   }
1424
1425   // Return a string with colour information for Dot.  Required by GraphWriter.
1426   std::string getNodeAttributes(const DisplayNode &Node) const {
1427     return attribute(Node.getColour());
1428   }
1429
1430   // Return a string with colour information for Dot.  Required by GraphWriter.
1431   std::string getEdgeColorAttr(const DisplayNode &From,
1432                                const DisplayNode &To) const {
1433     return attribute(From.getEdge(To).getColour());
1434   }
1435
1436   // Get the starting basic block.  Required by GraphWriter.
1437   DisplayNode *getEntryNode() const {
1438     assert(NodeGenerationComplete && "Unexpected children iterator creation");
1439     return EntryNode;
1440   }
1441
1442 protected:
1443   // Return the string containing the colour to use as a Dot attribute.
1444   std::string attribute(StringRef Colour) const {
1445     return "color=" + Colour.str();
1446   }
1447
1448   bool NodeGenerationComplete = false;
1449   const std::string GraphName;
1450   std::vector<DisplayNode> Nodes;
1451   std::vector<DisplayNode *> NodePtrs;
1452   DisplayNode *EntryNode = nullptr;
1453 };
1454
1455 void DisplayNode::createEdge(StringRef Value, DisplayNode &Node,
1456                              StringRef Colour) {
1457   assert(!AllEdgesCreated && "Expected to be able to still create edges.");
1458   Edges.emplace_back(Value.str(), Node, Colour);
1459   Children.insert(&Node);
1460 }
1461
1462 void DisplayNode::createEdgeMap() {
1463   // No more edges will be added so we can now use pointers to the edges
1464   // as the vector will not grow and reallocate.
1465   AllEdgesCreated = true;
1466   for (auto &E : Edges)
1467     EdgeMap.insert({&E.getDestinationNode(), &E});
1468 }
1469
1470 class DotCfgDiffNode;
1471 class DotCfgDiff;
1472
1473 // A class representing a basic block in the Dot difference graph.
1474 class DotCfgDiffNode {
1475 public:
1476   DotCfgDiffNode() = delete;
1477
1478   // Create a node in Dot difference graph \p G representing the basic block
1479   // represented by \p BD with colour \p Colour (where it exists).
1480   DotCfgDiffNode(DotCfgDiff &G, unsigned N, const BlockDataT<DCData> &BD,
1481                  StringRef Colour)
1482       : Graph(G), N(N), Data{&BD, nullptr}, Colour(Colour) {}
1483   DotCfgDiffNode(const DotCfgDiffNode &DN)
1484       : Graph(DN.Graph), N(DN.N), Data{DN.Data[0], DN.Data[1]},
1485         Colour(DN.Colour), EdgesMap(DN.EdgesMap), Children(DN.Children),
1486         Edges(DN.Edges) {}
1487
1488   unsigned getIndex() const { return N; }
1489
1490   // The label of the basic block
1491   StringRef getLabel() const {
1492     assert(Data[0] && "Expected Data[0] to be set.");
1493     return Data[0]->getLabel();
1494   }
1495   // Return the colour for this block
1496   StringRef getColour() const { return Colour; }
1497   // Change this basic block from being only in before to being common.
1498   // Save the pointer to \p Other.
1499   void setCommon(const BlockDataT<DCData> &Other) {
1500     assert(!Data[1] && "Expected only one block datum");
1501     Data[1] = &Other;
1502     Colour = CommonColour;
1503   }
1504   // Add an edge to \p E of colour {\p Value, \p Colour}.
1505   void addEdge(unsigned E, StringRef Value, StringRef Colour) {
1506     // This is a new edge or it is an edge being made common.
1507     assert((EdgesMap.count(E) == 0 || Colour == CommonColour) &&
1508            "Unexpected edge count and color.");
1509     EdgesMap[E] = {Value.str(), Colour};
1510   }
1511   // Record the children and create edges.
1512   void finalize(DotCfgDiff &G);
1513
1514   // Return the colour of the edge to node \p S.
1515   StringRef getEdgeColour(const unsigned S) const {
1516     assert(EdgesMap.count(S) == 1 && "Expected to find edge.");
1517     return EdgesMap.at(S).second;
1518   }
1519
1520   // Return the string representing the basic block.
1521   std::string getBodyContent() const;
1522
1523   void createDisplayEdges(DotCfgDiffDisplayGraph &Graph, unsigned DisplayNode,
1524                           std::map<const unsigned, unsigned> &NodeMap) const;
1525
1526 protected:
1527   DotCfgDiff &Graph;
1528   const unsigned N;
1529   const BlockDataT<DCData> *Data[2];
1530   StringRef Colour;
1531   std::map<const unsigned, std::pair<std::string, StringRef>> EdgesMap;
1532   std::vector<unsigned> Children;
1533   std::vector<unsigned> Edges;
1534 };
1535
1536 // Class representing the difference graph between two functions.
1537 class DotCfgDiff {
1538 public:
1539   // \p Title is the title given to the graph.  \p EntryNodeName is the
1540   // entry node for the function.  \p Before and \p After are the before
1541   // after versions of the function, respectively.  \p Dir is the directory
1542   // in which to store the results.
1543   DotCfgDiff(StringRef Title, const FuncDataT<DCData> &Before,
1544              const FuncDataT<DCData> &After);
1545
1546   DotCfgDiff(const DotCfgDiff &) = delete;
1547   DotCfgDiff &operator=(const DotCfgDiff &) = delete;
1548
1549   DotCfgDiffDisplayGraph createDisplayGraph(StringRef Title,
1550                                             StringRef EntryNodeName);
1551
1552   // Return a string consisting of the labels for the \p Source and \p Sink.
1553   // The combination allows distinguishing changing transitions on the
1554   // same value (ie, a transition went to X before and goes to Y after).
1555   // Required by GraphWriter.
1556   StringRef getEdgeSourceLabel(const unsigned &Source,
1557                                const unsigned &Sink) const {
1558     std::string S =
1559         getNode(Source).getLabel().str() + " " + getNode(Sink).getLabel().str();
1560     assert(EdgeLabels.count(S) == 1 && "Expected to find edge label.");
1561     return EdgeLabels.find(S)->getValue();
1562   }
1563
1564   // Return the number of basic blocks (nodes).  Required by GraphWriter.
1565   unsigned size() const { return Nodes.size(); }
1566
1567   const DotCfgDiffNode &getNode(unsigned N) const {
1568     assert(N < Nodes.size() && "Unexpected index for node reference");
1569     return Nodes[N];
1570   }
1571
1572 protected:
1573   // Return the string surrounded by HTML to make it the appropriate colour.
1574   std::string colourize(std::string S, StringRef Colour) const;
1575
1576   void createNode(StringRef Label, const BlockDataT<DCData> &BD, StringRef C) {
1577     unsigned Pos = Nodes.size();
1578     Nodes.emplace_back(*this, Pos, BD, C);
1579     NodePosition.insert({Label, Pos});
1580   }
1581
1582   // TODO Nodes should probably be a StringMap<DotCfgDiffNode> after the
1583   // display graph is separated out, which would remove the need for
1584   // NodePosition.
1585   std::vector<DotCfgDiffNode> Nodes;
1586   StringMap<unsigned> NodePosition;
1587   const std::string GraphName;
1588
1589   StringMap<std::string> EdgeLabels;
1590 };
1591
1592 std::string DotCfgDiffNode::getBodyContent() const {
1593   if (Colour == CommonColour) {
1594     assert(Data[1] && "Expected Data[1] to be set.");
1595
1596     StringRef SR[2];
1597     for (unsigned I = 0; I < 2; ++I) {
1598       SR[I] = Data[I]->getBody();
1599       // drop initial '\n' if present
1600       if (SR[I][0] == '\n')
1601         SR[I] = SR[I].drop_front();
1602       // drop predecessors as they can be big and are redundant
1603       SR[I] = SR[I].drop_until([](char C) { return C == '\n'; }).drop_front();
1604     }
1605
1606     SmallString<80> OldLineFormat = formatv(
1607         "<FONT COLOR=\"{0}\">%l</FONT><BR align=\"left\"/>", BeforeColour);
1608     SmallString<80> NewLineFormat = formatv(
1609         "<FONT COLOR=\"{0}\">%l</FONT><BR align=\"left\"/>", AfterColour);
1610     SmallString<80> UnchangedLineFormat = formatv(
1611         "<FONT COLOR=\"{0}\">%l</FONT><BR align=\"left\"/>", CommonColour);
1612     std::string Diff = Data[0]->getLabel().str();
1613     Diff += ":\n<BR align=\"left\"/>" +
1614             doSystemDiff(makeHTMLReady(SR[0]), makeHTMLReady(SR[1]),
1615                          OldLineFormat, NewLineFormat, UnchangedLineFormat);
1616
1617     // Diff adds in some empty colour changes which are not valid HTML
1618     // so remove them.  Colours are all lowercase alpha characters (as
1619     // listed in https://graphviz.org/pdf/dotguide.pdf).
1620     Regex R("<FONT COLOR=\"\\w+\"></FONT>");
1621     while (true) {
1622       std::string Error;
1623       std::string S = R.sub("", Diff, &Error);
1624       if (Error != "")
1625         return Error;
1626       if (S == Diff)
1627         return Diff;
1628       Diff = S;
1629     }
1630     llvm_unreachable("Should not get here");
1631   }
1632
1633   // Put node out in the appropriate colour.
1634   assert(!Data[1] && "Data[1] is set unexpectedly.");
1635   std::string Body = makeHTMLReady(Data[0]->getBody());
1636   const StringRef BS = Body;
1637   StringRef BS1 = BS;
1638   // Drop leading newline, if present.
1639   if (BS.front() == '\n')
1640     BS1 = BS1.drop_front(1);
1641   // Get label.
1642   StringRef Label = BS1.take_until([](char C) { return C == ':'; });
1643   // drop predecessors as they can be big and are redundant
1644   BS1 = BS1.drop_until([](char C) { return C == '\n'; }).drop_front();
1645
1646   std::string S = "<FONT COLOR=\"" + Colour.str() + "\">" + Label.str() + ":";
1647
1648   // align each line to the left.
1649   while (BS1.size()) {
1650     S.append("<BR align=\"left\"/>");
1651     StringRef Line = BS1.take_until([](char C) { return C == '\n'; });
1652     S.append(Line.str());
1653     BS1 = BS1.drop_front(Line.size() + 1);
1654   }
1655   S.append("<BR align=\"left\"/></FONT>");
1656   return S;
1657 }
1658
1659 std::string DotCfgDiff::colourize(std::string S, StringRef Colour) const {
1660   if (S.length() == 0)
1661     return S;
1662   return "<FONT COLOR=\"" + Colour.str() + "\">" + S + "</FONT>";
1663 }
1664
1665 DotCfgDiff::DotCfgDiff(StringRef Title, const FuncDataT<DCData> &Before,
1666                        const FuncDataT<DCData> &After)
1667     : GraphName(Title.str()) {
1668   StringMap<StringRef> EdgesMap;
1669
1670   // Handle each basic block in the before IR.
1671   for (auto &B : Before.getData()) {
1672     StringRef Label = B.getKey();
1673     const BlockDataT<DCData> &BD = B.getValue();
1674     createNode(Label, BD, BeforeColour);
1675
1676     // Create transitions with names made up of the from block label, the value
1677     // on which the transition is made and the to block label.
1678     for (StringMap<std::string>::const_iterator Sink = BD.getData().begin(),
1679                                                 E = BD.getData().end();
1680          Sink != E; ++Sink) {
1681       std::string Key = (Label + " " + Sink->getKey().str()).str() + " " +
1682                         BD.getData().getSuccessorLabel(Sink->getKey()).str();
1683       EdgesMap.insert({Key, BeforeColour});
1684     }
1685   }
1686
1687   // Handle each basic block in the after IR
1688   for (auto &A : After.getData()) {
1689     StringRef Label = A.getKey();
1690     const BlockDataT<DCData> &BD = A.getValue();
1691     unsigned C = NodePosition.count(Label);
1692     if (C == 0)
1693       // This only exists in the after IR.  Create the node.
1694       createNode(Label, BD, AfterColour);
1695     else {
1696       assert(C == 1 && "Unexpected multiple nodes.");
1697       Nodes[NodePosition[Label]].setCommon(BD);
1698     }
1699     // Add in the edges between the nodes (as common or only in after).
1700     for (StringMap<std::string>::const_iterator Sink = BD.getData().begin(),
1701                                                 E = BD.getData().end();
1702          Sink != E; ++Sink) {
1703       std::string Key = (Label + " " + Sink->getKey().str()).str() + " " +
1704                         BD.getData().getSuccessorLabel(Sink->getKey()).str();
1705       unsigned C = EdgesMap.count(Key);
1706       if (C == 0)
1707         EdgesMap.insert({Key, AfterColour});
1708       else {
1709         EdgesMap[Key] = CommonColour;
1710       }
1711     }
1712   }
1713
1714   // Now go through the map of edges and add them to the node.
1715   for (auto &E : EdgesMap) {
1716     // Extract the source, sink and value from the edge key.
1717     StringRef S = E.getKey();
1718     auto SP1 = S.rsplit(' ');
1719     auto &SourceSink = SP1.first;
1720     auto SP2 = SourceSink.split(' ');
1721     StringRef Source = SP2.first;
1722     StringRef Sink = SP2.second;
1723     StringRef Value = SP1.second;
1724
1725     assert(NodePosition.count(Source) == 1 && "Expected to find node.");
1726     DotCfgDiffNode &SourceNode = Nodes[NodePosition[Source]];
1727     assert(NodePosition.count(Sink) == 1 && "Expected to find node.");
1728     unsigned SinkNode = NodePosition[Sink];
1729     StringRef Colour = E.second;
1730
1731     // Look for an edge from Source to Sink
1732     if (EdgeLabels.count(SourceSink) == 0)
1733       EdgeLabels.insert({SourceSink, colourize(Value.str(), Colour)});
1734     else {
1735       StringRef V = EdgeLabels.find(SourceSink)->getValue();
1736       std::string NV = colourize(V.str() + " " + Value.str(), Colour);
1737       Colour = CommonColour;
1738       EdgeLabels[SourceSink] = NV;
1739     }
1740     SourceNode.addEdge(SinkNode, Value, Colour);
1741   }
1742   for (auto &I : Nodes)
1743     I.finalize(*this);
1744 }
1745
1746 DotCfgDiffDisplayGraph DotCfgDiff::createDisplayGraph(StringRef Title,
1747                                                       StringRef EntryNodeName) {
1748   assert(NodePosition.count(EntryNodeName) == 1 &&
1749          "Expected to find entry block in map.");
1750   unsigned Entry = NodePosition[EntryNodeName];
1751   assert(Entry < Nodes.size() && "Expected to find entry node");
1752   DotCfgDiffDisplayGraph G(Title.str());
1753
1754   std::map<const unsigned, unsigned> NodeMap;
1755
1756   int EntryIndex = -1;
1757   unsigned Index = 0;
1758   for (auto &I : Nodes) {
1759     if (I.getIndex() == Entry)
1760       EntryIndex = Index;
1761     G.createNode(I.getBodyContent(), I.getColour());
1762     NodeMap.insert({I.getIndex(), Index++});
1763   }
1764   assert(EntryIndex >= 0 && "Expected entry node index to be set.");
1765   G.setEntryNode(EntryIndex);
1766
1767   for (auto &I : NodeMap) {
1768     unsigned SourceNode = I.first;
1769     unsigned DisplayNode = I.second;
1770     getNode(SourceNode).createDisplayEdges(G, DisplayNode, NodeMap);
1771   }
1772   return G;
1773 }
1774
1775 void DotCfgDiffNode::createDisplayEdges(
1776     DotCfgDiffDisplayGraph &DisplayGraph, unsigned DisplayNodeIndex,
1777     std::map<const unsigned, unsigned> &NodeMap) const {
1778
1779   DisplayNode &SourceDisplayNode = DisplayGraph.getNode(DisplayNodeIndex);
1780
1781   for (auto I : Edges) {
1782     unsigned SinkNodeIndex = I;
1783     StringRef Colour = getEdgeColour(SinkNodeIndex);
1784     const DotCfgDiffNode *SinkNode = &Graph.getNode(SinkNodeIndex);
1785
1786     StringRef Label = Graph.getEdgeSourceLabel(getIndex(), SinkNodeIndex);
1787     DisplayNode &SinkDisplayNode = DisplayGraph.getNode(SinkNode->getIndex());
1788     SourceDisplayNode.createEdge(Label, SinkDisplayNode, Colour);
1789   }
1790   SourceDisplayNode.createEdgeMap();
1791 }
1792
1793 void DotCfgDiffNode::finalize(DotCfgDiff &G) {
1794   for (auto E : EdgesMap) {
1795     Children.emplace_back(E.first);
1796     Edges.emplace_back(E.first);
1797   }
1798 }
1799
1800 } // namespace
1801
1802 namespace llvm {
1803
1804 template <> struct GraphTraits<DotCfgDiffDisplayGraph *> {
1805   using NodeRef = const DisplayNode *;
1806   using ChildIteratorType = DisplayNode::ChildIterator;
1807   using nodes_iterator = DotCfgDiffDisplayGraph::NodeIterator;
1808   using EdgeRef = const DisplayEdge *;
1809   using ChildEdgeIterator = DisplayNode::EdgeIterator;
1810
1811   static NodeRef getEntryNode(const DotCfgDiffDisplayGraph *G) {
1812     return G->getEntryNode();
1813   }
1814   static ChildIteratorType child_begin(NodeRef N) {
1815     return N->children_begin();
1816   }
1817   static ChildIteratorType child_end(NodeRef N) { return N->children_end(); }
1818   static nodes_iterator nodes_begin(const DotCfgDiffDisplayGraph *G) {
1819     return G->nodes_begin();
1820   }
1821   static nodes_iterator nodes_end(const DotCfgDiffDisplayGraph *G) {
1822     return G->nodes_end();
1823   }
1824   static ChildEdgeIterator child_edge_begin(NodeRef N) {
1825     return N->edges_begin();
1826   }
1827   static ChildEdgeIterator child_edge_end(NodeRef N) { return N->edges_end(); }
1828   static NodeRef edge_dest(EdgeRef E) { return &E->getDestinationNode(); }
1829   static unsigned size(const DotCfgDiffDisplayGraph *G) { return G->size(); }
1830 };
1831
1832 template <>
1833 struct DOTGraphTraits<DotCfgDiffDisplayGraph *> : public DefaultDOTGraphTraits {
1834   explicit DOTGraphTraits(bool Simple = false)
1835       : DefaultDOTGraphTraits(Simple) {}
1836
1837   static bool renderNodesUsingHTML() { return true; }
1838   static std::string getGraphName(const DotCfgDiffDisplayGraph *DiffData) {
1839     return DiffData->getGraphName();
1840   }
1841   static std::string
1842   getGraphProperties(const DotCfgDiffDisplayGraph *DiffData) {
1843     return "\tsize=\"190, 190\";\n";
1844   }
1845   static std::string getNodeLabel(const DisplayNode *Node,
1846                                   const DotCfgDiffDisplayGraph *DiffData) {
1847     return DiffData->getNodeLabel(*Node);
1848   }
1849   static std::string getNodeAttributes(const DisplayNode *Node,
1850                                        const DotCfgDiffDisplayGraph *DiffData) {
1851     return DiffData->getNodeAttributes(*Node);
1852   }
1853   static std::string getEdgeSourceLabel(const DisplayNode *From,
1854                                         DisplayNode::ChildIterator &To) {
1855     return From->getEdgeSourceLabel(**To);
1856   }
1857   static std::string getEdgeAttributes(const DisplayNode *From,
1858                                        DisplayNode::ChildIterator &To,
1859                                        const DotCfgDiffDisplayGraph *DiffData) {
1860     return DiffData->getEdgeColorAttr(*From, **To);
1861   }
1862 };
1863
1864 } // namespace llvm
1865
1866 namespace {
1867
1868 void DotCfgDiffDisplayGraph::generateDotFile(StringRef DotFile) {
1869   std::error_code EC;
1870   raw_fd_ostream OutStream(DotFile, EC);
1871   if (EC) {
1872     errs() << "Error: " << EC.message() << "\n";
1873     return;
1874   }
1875   WriteGraph(OutStream, this, false);
1876   OutStream.flush();
1877   OutStream.close();
1878 }
1879
1880 } // namespace
1881
1882 namespace llvm {
1883
1884 DCData::DCData(const BasicBlock &B) {
1885   // Build up transition labels.
1886   const Instruction *Term = B.getTerminator();
1887   if (const BranchInst *Br = dyn_cast<const BranchInst>(Term))
1888     if (Br->isUnconditional())
1889       addSuccessorLabel(Br->getSuccessor(0)->getName().str(), "");
1890     else {
1891       addSuccessorLabel(Br->getSuccessor(0)->getName().str(), "true");
1892       addSuccessorLabel(Br->getSuccessor(1)->getName().str(), "false");
1893     }
1894   else if (const SwitchInst *Sw = dyn_cast<const SwitchInst>(Term)) {
1895     addSuccessorLabel(Sw->case_default()->getCaseSuccessor()->getName().str(),
1896                       "default");
1897     for (auto &C : Sw->cases()) {
1898       assert(C.getCaseValue() && "Expected to find case value.");
1899       SmallString<20> Value = formatv("{0}", C.getCaseValue()->getSExtValue());
1900       addSuccessorLabel(C.getCaseSuccessor()->getName().str(), Value);
1901     }
1902   } else
1903     for (const_succ_iterator I = succ_begin(&B), E = succ_end(&B); I != E; ++I)
1904       addSuccessorLabel((*I)->getName().str(), "");
1905 }
1906
1907 DotCfgChangeReporter::DotCfgChangeReporter(bool Verbose)
1908     : ChangeReporter<IRDataT<DCData>>(Verbose) {}
1909
1910 void DotCfgChangeReporter::handleFunctionCompare(
1911     StringRef Name, StringRef Prefix, StringRef PassID, StringRef Divider,
1912     bool InModule, unsigned Minor, const FuncDataT<DCData> &Before,
1913     const FuncDataT<DCData> &After) {
1914   assert(HTML && "Expected outstream to be set");
1915   SmallString<8> Extender;
1916   SmallString<8> Number;
1917   // Handle numbering and file names.
1918   if (InModule) {
1919     Extender = formatv("{0}_{1}", N, Minor);
1920     Number = formatv("{0}.{1}", N, Minor);
1921   } else {
1922     Extender = formatv("{0}", N);
1923     Number = formatv("{0}", N);
1924   }
1925   // Create a temporary file name for the dot file.
1926   SmallVector<char, 128> SV;
1927   sys::fs::createUniquePath("cfgdot-%%%%%%.dot", SV, true);
1928   std::string DotFile = Twine(SV).str();
1929
1930   SmallString<20> PDFFileName = formatv("diff_{0}.pdf", Extender);
1931   SmallString<200> Text;
1932
1933   Text = formatv("{0}.{1}{2}{3}{4}", Number, Prefix, makeHTMLReady(PassID),
1934                  Divider, Name);
1935
1936   DotCfgDiff Diff(Text, Before, After);
1937   std::string EntryBlockName = After.getEntryBlockName();
1938   // Use the before entry block if the after entry block was removed.
1939   if (EntryBlockName == "")
1940     EntryBlockName = Before.getEntryBlockName();
1941   assert(EntryBlockName != "" && "Expected to find entry block");
1942
1943   DotCfgDiffDisplayGraph DG = Diff.createDisplayGraph(Text, EntryBlockName);
1944   DG.generateDotFile(DotFile);
1945
1946   *HTML << genHTML(Text, DotFile, PDFFileName);
1947   std::error_code EC = sys::fs::remove(DotFile);
1948   if (EC)
1949     errs() << "Error: " << EC.message() << "\n";
1950 }
1951
1952 std::string DotCfgChangeReporter::genHTML(StringRef Text, StringRef DotFile,
1953                                           StringRef PDFFileName) {
1954   SmallString<20> PDFFile = formatv("{0}/{1}", DotCfgDir, PDFFileName);
1955   // Create the PDF file.
1956   static ErrorOr<std::string> DotExe = sys::findProgramByName(DotBinary);
1957   if (!DotExe)
1958     return "Unable to find dot executable.";
1959
1960   StringRef Args[] = {DotBinary, "-Tpdf", "-o", PDFFile, DotFile};
1961   int Result = sys::ExecuteAndWait(*DotExe, Args, None);
1962   if (Result < 0)
1963     return "Error executing system dot.";
1964
1965   // Create the HTML tag refering to the PDF file.
1966   SmallString<200> S = formatv(
1967       "  <a href=\"{0}\" target=\"_blank\">{1}</a><br/>\n", PDFFileName, Text);
1968   return S.c_str();
1969 }
1970
1971 void DotCfgChangeReporter::handleInitialIR(Any IR) {
1972   assert(HTML && "Expected outstream to be set");
1973   *HTML << "<button type=\"button\" class=\"collapsible\">0. "
1974         << "Initial IR (by function)</button>\n"
1975         << "<div class=\"content\">\n"
1976         << "  <p>\n";
1977   // Create representation of IR
1978   IRDataT<DCData> Data;
1979   IRComparer<DCData>::analyzeIR(IR, Data);
1980   // Now compare it against itself, which will have everything the
1981   // same and will generate the files.
1982   IRComparer<DCData>(Data, Data)
1983       .compare(getModuleForComparison(IR),
1984                [&](bool InModule, unsigned Minor,
1985                    const FuncDataT<DCData> &Before,
1986                    const FuncDataT<DCData> &After) -> void {
1987                  handleFunctionCompare("", " ", "Initial IR", "", InModule,
1988                                        Minor, Before, After);
1989                });
1990   *HTML << "  </p>\n"
1991         << "</div><br/>\n";
1992   ++N;
1993 }
1994
1995 void DotCfgChangeReporter::generateIRRepresentation(Any IR, StringRef PassID,
1996                                                     IRDataT<DCData> &Data) {
1997   IRComparer<DCData>::analyzeIR(IR, Data);
1998 }
1999
2000 void DotCfgChangeReporter::omitAfter(StringRef PassID, std::string &Name) {
2001   assert(HTML && "Expected outstream to be set");
2002   SmallString<20> Banner =
2003       formatv("  <a>{0}. Pass {1} on {2} omitted because no change</a><br/>\n",
2004               N, makeHTMLReady(PassID), Name);
2005   *HTML << Banner;
2006   ++N;
2007 }
2008
2009 void DotCfgChangeReporter::handleAfter(StringRef PassID, std::string &Name,
2010                                        const IRDataT<DCData> &Before,
2011                                        const IRDataT<DCData> &After, Any IR) {
2012   assert(HTML && "Expected outstream to be set");
2013   IRComparer<DCData>(Before, After)
2014       .compare(getModuleForComparison(IR),
2015                [&](bool InModule, unsigned Minor,
2016                    const FuncDataT<DCData> &Before,
2017                    const FuncDataT<DCData> &After) -> void {
2018                  handleFunctionCompare(Name, " Pass ", PassID, " on ", InModule,
2019                                        Minor, Before, After);
2020                });
2021   *HTML << "    </p></div>\n";
2022   ++N;
2023 }
2024
2025 void DotCfgChangeReporter::handleInvalidated(StringRef PassID) {
2026   assert(HTML && "Expected outstream to be set");
2027   SmallString<20> Banner =
2028       formatv("  <a>{0}. {1} invalidated</a><br/>\n", N, makeHTMLReady(PassID));
2029   *HTML << Banner;
2030   ++N;
2031 }
2032
2033 void DotCfgChangeReporter::handleFiltered(StringRef PassID, std::string &Name) {
2034   assert(HTML && "Expected outstream to be set");
2035   SmallString<20> Banner =
2036       formatv("  <a>{0}. Pass {1} on {2} filtered out</a><br/>\n", N,
2037               makeHTMLReady(PassID), Name);
2038   *HTML << Banner;
2039   ++N;
2040 }
2041
2042 void DotCfgChangeReporter::handleIgnored(StringRef PassID, std::string &Name) {
2043   assert(HTML && "Expected outstream to be set");
2044   SmallString<20> Banner = formatv("  <a>{0}. {1} on {2} ignored</a><br/>\n", N,
2045                                    makeHTMLReady(PassID), Name);
2046   *HTML << Banner;
2047   ++N;
2048 }
2049
2050 bool DotCfgChangeReporter::initializeHTML() {
2051   std::error_code EC;
2052   HTML = std::make_unique<raw_fd_ostream>(DotCfgDir + "/passes.html", EC);
2053   if (EC) {
2054     HTML = nullptr;
2055     return false;
2056   }
2057
2058   *HTML << "<!doctype html>"
2059         << "<html>"
2060         << "<head>"
2061         << "<style>.collapsible { "
2062         << "background-color: #777;"
2063         << " color: white;"
2064         << " cursor: pointer;"
2065         << " padding: 18px;"
2066         << " width: 100%;"
2067         << " border: none;"
2068         << " text-align: left;"
2069         << " outline: none;"
2070         << " font-size: 15px;"
2071         << "} .active, .collapsible:hover {"
2072         << " background-color: #555;"
2073         << "} .content {"
2074         << " padding: 0 18px;"
2075         << " display: none;"
2076         << " overflow: hidden;"
2077         << " background-color: #f1f1f1;"
2078         << "}"
2079         << "</style>"
2080         << "<title>passes.html</title>"
2081         << "</head>\n"
2082         << "<body>";
2083   return true;
2084 }
2085
2086 DotCfgChangeReporter::~DotCfgChangeReporter() {
2087   if (!HTML)
2088     return;
2089   *HTML
2090       << "<script>var coll = document.getElementsByClassName(\"collapsible\");"
2091       << "var i;"
2092       << "for (i = 0; i < coll.length; i++) {"
2093       << "coll[i].addEventListener(\"click\", function() {"
2094       << " this.classList.toggle(\"active\");"
2095       << " var content = this.nextElementSibling;"
2096       << " if (content.style.display === \"block\"){"
2097       << " content.style.display = \"none\";"
2098       << " }"
2099       << " else {"
2100       << " content.style.display= \"block\";"
2101       << " }"
2102       << " });"
2103       << " }"
2104       << "</script>"
2105       << "</body>"
2106       << "</html>\n";
2107   HTML->flush();
2108   HTML->close();
2109 }
2110
2111 void DotCfgChangeReporter::registerCallbacks(
2112     PassInstrumentationCallbacks &PIC) {
2113   if (PrintChanged == ChangePrinter::DotCfgVerbose ||
2114        PrintChanged == ChangePrinter::DotCfgQuiet) {
2115     SmallString<128> OutputDir;
2116     sys::fs::expand_tilde(DotCfgDir, OutputDir);
2117     sys::fs::make_absolute(OutputDir);
2118     assert(!OutputDir.empty() && "expected output dir to be non-empty");
2119     DotCfgDir = OutputDir.c_str();
2120     if (initializeHTML()) {
2121       ChangeReporter<IRDataT<DCData>>::registerRequiredCallbacks(PIC);
2122       return;
2123     }
2124     dbgs() << "Unable to open output stream for -cfg-dot-changed\n";
2125   }
2126 }
2127
2128 StandardInstrumentations::StandardInstrumentations(
2129     bool DebugLogging, bool VerifyEach, PrintPassOptions PrintPassOpts)
2130     : PrintPass(DebugLogging, PrintPassOpts), OptNone(DebugLogging),
2131       PrintChangedIR(PrintChanged == ChangePrinter::Verbose),
2132       PrintChangedDiff(PrintChanged == ChangePrinter::DiffVerbose ||
2133                            PrintChanged == ChangePrinter::ColourDiffVerbose,
2134                        PrintChanged == ChangePrinter::ColourDiffVerbose ||
2135                            PrintChanged == ChangePrinter::ColourDiffQuiet),
2136       WebsiteChangeReporter(PrintChanged == ChangePrinter::DotCfgVerbose),
2137       Verify(DebugLogging), VerifyEach(VerifyEach) {}
2138
2139 PrintCrashIRInstrumentation *PrintCrashIRInstrumentation::CrashReporter =
2140     nullptr;
2141
2142 void PrintCrashIRInstrumentation::reportCrashIR() { dbgs() << SavedIR; }
2143
2144 void PrintCrashIRInstrumentation::SignalHandler(void *) {
2145   // Called by signal handlers so do not lock here
2146   // Is the PrintCrashIRInstrumentation still alive?
2147   if (!CrashReporter)
2148     return;
2149
2150   assert(PrintCrashIR && "Did not expect to get here without option set.");
2151   CrashReporter->reportCrashIR();
2152 }
2153
2154 PrintCrashIRInstrumentation::~PrintCrashIRInstrumentation() {
2155   if (!CrashReporter)
2156     return;
2157
2158   assert(PrintCrashIR && "Did not expect to get here without option set.");
2159   CrashReporter = nullptr;
2160 }
2161
2162 void PrintCrashIRInstrumentation::registerCallbacks(
2163     PassInstrumentationCallbacks &PIC) {
2164   if (!PrintCrashIR || CrashReporter)
2165     return;
2166
2167   sys::AddSignalHandler(SignalHandler, nullptr);
2168   CrashReporter = this;
2169
2170   PIC.registerBeforeNonSkippedPassCallback([this](StringRef PassID, Any IR) {
2171     SavedIR.clear();
2172     raw_string_ostream OS(SavedIR);
2173     OS << formatv("*** Dump of {0}IR Before Last Pass {1}",
2174                   llvm::forcePrintModuleIR() ? "Module " : "", PassID);
2175     if (!isInteresting(IR, PassID)) {
2176       OS << " Filtered Out ***\n";
2177       return;
2178     }
2179     OS << " Started ***\n";
2180     unwrapAndPrint(OS, IR);
2181   });
2182 }
2183
2184 void StandardInstrumentations::registerCallbacks(
2185     PassInstrumentationCallbacks &PIC, FunctionAnalysisManager *FAM) {
2186   PrintIR.registerCallbacks(PIC);
2187   PrintPass.registerCallbacks(PIC);
2188   TimePasses.registerCallbacks(PIC);
2189   OptNone.registerCallbacks(PIC);
2190   OptBisect.registerCallbacks(PIC);
2191   if (FAM)
2192     PreservedCFGChecker.registerCallbacks(PIC, *FAM);
2193   PrintChangedIR.registerCallbacks(PIC);
2194   PseudoProbeVerification.registerCallbacks(PIC);
2195   if (VerifyEach)
2196     Verify.registerCallbacks(PIC);
2197   PrintChangedDiff.registerCallbacks(PIC);
2198   WebsiteChangeReporter.registerCallbacks(PIC);
2199   PrintCrashIR.registerCallbacks(PIC);
2200 }
2201
2202 template class ChangeReporter<std::string>;
2203 template class TextChangeReporter<std::string>;
2204
2205 template class BlockDataT<EmptyData>;
2206 template class FuncDataT<EmptyData>;
2207 template class IRDataT<EmptyData>;
2208 template class ChangeReporter<IRDataT<EmptyData>>;
2209 template class TextChangeReporter<IRDataT<EmptyData>>;
2210 template class IRComparer<EmptyData>;
2211
2212 } // namespace llvm