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