Index: llvm/include/llvm/IR/ChangeReporters.h =================================================================== --- llvm/include/llvm/IR/ChangeReporters.h +++ llvm/include/llvm/IR/ChangeReporters.h @@ -12,8 +12,8 @@ /// //===----------------------------------------------------------------------===// -#ifndef LLVM_SUPPORT_CHANGEREPORTERS_H -#define LLVM_SUPPORT_CHANGEREPORTERS_H +#ifndef LLVM_IR_CHANGEREPORTERS_H +#define LLVM_IR_CHANGEREPORTERS_H #include "llvm/ADT/Any.h" #include "llvm/ADT/SmallVector.h" @@ -243,7 +243,15 @@ bool operator!=(const IRDataTemplate &that) const { return !(*this == that); } }; -enum IRChangeDiffType { InBefore, InAfter, IsCommon }; +enum IRChangeDiffType { InBefore, InAfter, IsCommon, NumIRChangeDiffTypes }; + +// Perform a linux based diff between \p Before and \p After, using +// \p OldLineFormat, \p NewLineFormat, and \p UnchangedLineFormat +// to control the formatting of the output. +std::string doLinuxDiff(llvm::StringRef Before, llvm::StringRef After, + llvm::StringRef OldLineFormat, + llvm::StringRef NewLineFormat, + llvm::StringRef UnchangedLineFormat); // Template base class for a class that compares two IRs. The class is // created with the 2 IRs to compare and then compare is called. The @@ -317,6 +325,84 @@ llvm::raw_ostream &Out; }; +class BlockSuccessors : private llvm::StringMap { +public: + BlockSuccessors() {} + void populate(const llvm::BasicBlock &B); + + // Return an iterator to the names of the successor blocks. + using llvm::StringMap::begin; + using llvm::StringMap::end; + + // Return the label of the basic block reached on a transition on \p S. + const llvm::StringRef getSuccessorLabel(llvm::StringRef S) const { + assert(count(S) == 1 && "Expected to find successor."); + return find(S)->getValue(); + } + + static void initialize(BlockSuccessors &S, const llvm::BasicBlock &B) { + S.populate(B); + } + +protected: + // Add a transition to \p Succ on \p Label + void addSuccessorLabel(llvm::StringRef Succ, llvm::StringRef Label) { + std::pair SS{Succ, Label}; + insert(SS); + } +}; + +using BlockSuccessorsBlockData = BlockDataTemplate; +using BlockSuccessorsFuncData = FuncDataTemplate; +using BlockSuccessorsIRData = IRDataTemplate; + +// Class that compares two IRs and creates a graphical representation of +// the differences between the two IRs. It produces a web page with links +// to pdf files showing the differences between functions in the IRs. +class CFGDotComparer + : public IRComparer { + +public: + // Output html on \p OS, storing the file in \p Directory, using a suffix + // of \p N in the filename. + CFGDotComparer(llvm::raw_fd_ostream &OS, unsigned N, + llvm::StringRef Directory, const BlockSuccessorsIRData &Before, + const BlockSuccessorsIRData &After); + + // Replace '<' and '>' in \p SR with "<" and ">", respectively + static std::string makeHTMLReady(llvm::StringRef SR); + + // Compare \p Before and \After and create the pdf name using + // \p Major and \p Minor (if present) as part of the name. Call genHTML + // to create the html using \p Name and \PassID. + void handleSingleFunctionCompare(llvm::StringRef Name, llvm::StringRef Prefix, + llvm::StringRef PassID, unsigned, unsigned *, + const BlockSuccessorsFuncData &Before, + const BlockSuccessorsFuncData &After); + // Called by base class + void handleFunctionInModuleCompare(llvm::StringRef Name, + llvm::StringRef Prefix, + llvm::StringRef PassID, unsigned Major, + unsigned *Minor, + const BlockSuccessorsFuncData &Before, + const BlockSuccessorsFuncData &After) { + handleSingleFunctionCompare(Name, Prefix, PassID, Major, Minor, Before, + After); + } + +protected: + // Generate the pdf file into \p Dir / \p PDFFileName using \p DotFile as + // input and return the html tag with \Text as the content, possibly + // indented, based on \p Indent. + static std::string genHTML(llvm::StringRef Text, llvm::StringRef DotFile, + llvm::StringRef PDFFileName, llvm::StringRef Dir, + bool Indent); + + std::string Directory; + llvm::raw_fd_ostream &HTML; +}; + extern template class ChangeReporter; extern template class TextChangeReporter; @@ -328,6 +414,14 @@ extern template class IRComparer; +extern template class BlockDataTemplate; +extern template class FuncDataTemplate; +extern template class IRDataTemplate; +extern template class ChangeReporter; +extern template class IRComparer; + } // namespace cr #endif Index: llvm/include/llvm/Passes/StandardInstrumentations.h =================================================================== --- llvm/include/llvm/Passes/StandardInstrumentations.h +++ llvm/include/llvm/Passes/StandardInstrumentations.h @@ -144,6 +144,19 @@ void registerCallbacks(PassInstrumentationCallbacks &PIC); }; +class CFGDotChangeReporter + : public cr::ChangeReporter { +public: + CFGDotChangeReporter(); + ~CFGDotChangeReporter(); + void registerCallbacks(PassInstrumentationCallbacks &PIC); + +protected: + unsigned N; + raw_fd_ostream HTML; + std::error_code EC; +}; + /// This class provides an interface to register all the standard pass /// instrumentations and manages their state (if any). class StandardInstrumentations { @@ -153,6 +166,7 @@ OptNoneInstrumentation OptNone; IRChangedPrinter PrintChangedIR; InLineChangePrinter PrintChanges; + CFGDotChangeReporter CFGDotDiffGenerator; public: StandardInstrumentations(bool DebugLogging) : PrintPass(DebugLogging) {} Index: llvm/lib/IR/ChangeReporters.cpp =================================================================== --- llvm/lib/IR/ChangeReporters.cpp +++ llvm/lib/IR/ChangeReporters.cpp @@ -26,12 +26,15 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/GraphWriter.h" #include "llvm/Support/raw_ostream.h" +#include #include #include #include using namespace llvm; +using namespace cr; // A hidden option that supports the -print-changed option. See // the description for -print-changed for an explanation of the use @@ -42,6 +45,36 @@ "match for the print-changed option"), cl::CommaSeparated, cl::Hidden); +cl::opt BeforeColour("before-color", + cl::desc("Color for before elements."), + cl::Hidden, cl::init("red")); +cl::opt AfterColour("after-color", + cl::desc("Color for after elements."), + cl::Hidden, cl::init("forestgreen")); +cl::opt CommonColour("common-color", + cl::desc("Color for common elements."), + cl::Hidden, cl::init("black")); + +namespace { + +// Copied/Modified from FuzzerUtilPosix.cpp +// Return true on success, false otherwise. +bool ExecuteCommand(const StringRef Cmd, std::string *CmdOutput) { + FILE *Pipe = popen(Cmd.str().c_str(), "r"); + if (!Pipe) + return false; + + if (CmdOutput) { + char TmpBuffer[128]; + while (fgets(TmpBuffer, sizeof(TmpBuffer), Pipe)) + CmdOutput->append(TmpBuffer); + } + + return pclose(Pipe) == 0; +} + +} // namespace + namespace cr { template @@ -361,6 +394,795 @@ return false; } +// Perform a linux based diff between \p Before and \p After, using +// \p OldLineFormat, \p NewLineFormat, and \p UnchangedLineFormat +// to control the formatting of the output. +std::string doLinuxDiff(StringRef Before, StringRef After, + StringRef OldLineFormat, StringRef NewLineFormat, + StringRef UnchangedLineFormat) { + StringRef SR[2]{Before, After}; + // Store the 2 bodies into temporary files and call diff on them + // to get the body of the node. + static std::string FileName[2]; + static int FD[2]{-1, -1}; + for (int I = 0; I < 2; ++I) { + if (FD[I] == -1) { + SmallVector SV; + std::error_code EC = + sys::fs::createTemporaryFile("tmpdiff", "txt", FD[I], SV); + assert(!EC && "Unable to create temporary file."); + FileName[I] = Twine(SV).str(); + } + + std::error_code EC = sys::fs::openFileForWrite(FileName[I], FD[I]); + assert(!EC && "Unable to open temporary file for writing."); + + llvm::raw_fd_ostream OutStream(FD[I], /*shouldClose=*/true); + assert(FD[I] != -1 && "Error opening file for writing."); + OutStream << SR[I]; + } + + SmallString<512> DiffCall = + formatv("diff -w -d --old-line-format='{2}' --new-line-format='{3}' " + "--unchanged-line-format='{4}' {0} {1}", + FileName[0], FileName[1], OldLineFormat, NewLineFormat, + UnchangedLineFormat); + std::string Diff; + ExecuteCommand(DiffCall, &Diff); + // Clean up. + for (unsigned I = 0; I < 2; ++I) { + std::error_code EC = sys::fs::remove(FileName[I]); + assert(!EC && "Unable to remove temporary file."); + } + return Diff; +} + +} // namespace cr + +namespace { + +// Describe where a given element exists. +std::string Colours[NumIRChangeDiffTypes]; + +class DisplayNode; +class CFGDotDiffDisplayGraph; + +class DisplayElement { +public: + IRChangeDiffType getType() const { return Type; } + +protected: + DisplayElement(IRChangeDiffType T) : Type(T) {} + const IRChangeDiffType Type; +}; + +class DisplayEdge : public DisplayElement { +public: + DisplayEdge(std::string V, DisplayNode &Node, IRChangeDiffType T) + : DisplayElement(T), Value(V), Node(Node) {} + std::string getValue() const { return Value; } + const DisplayNode &getDestinationNode() const { return Node; } + +protected: + std::string Value; + const DisplayNode &Node; +}; + +class DisplayNode : public DisplayElement { +public: + DisplayNode(std::string C, IRChangeDiffType T, CFGDotDiffDisplayGraph &G) + : DisplayElement(T), Content(C) {} + + // Iterator to the child nodes. Required by GraphWriter. + using ChildIterator = std::unordered_set::const_iterator; + ChildIterator children_begin() const { return Children.cbegin(); } + ChildIterator children_end() const { return Children.cend(); } + + using EdgeIterator = std::vector::const_iterator; + EdgeIterator edges_begin() const { return EdgePtrs.cbegin(); } + EdgeIterator edges_end() const { return EdgePtrs.cend(); } + + void createEdge(StringRef V, DisplayNode &Node, IRChangeDiffType T); + std::string getContent() const { return Content; } + + // Return the type of the edge to node \p S. + const DisplayEdge &getEdge(const DisplayNode &To) const { + assert(EdgeMap.find(&To) != EdgeMap.end() && "Expected to find edge."); + return *EdgeMap.find(&To)->second; + } + + // Return the value for the transition to basic block \p S. + // Required by GraphWriter. + std::string getEdgeSourceLabel(const DisplayNode &Sink) const { + return getEdge(Sink).getValue(); + } + + void createEdgeMap(); + +protected: + const std::string Content; + + // TODO Needed? + std::vector Edges; + + std::vector EdgePtrs; + std::unordered_set Children; + std::unordered_map EdgeMap; +}; + +class CFGDotDiffDisplayGraph { +public: + CFGDotDiffDisplayGraph(std::string Name) { + NodeGenerationComplete = false; + GraphName = Name; + assert(Nodes.size() == 0 && "Expected Nodes to be empty."); + assert(NodePtrs.size() == 0 && "Expected NodePtrs to be empty."); + assert(EntryNode == nullptr && "Expected EntryNode to be null."); + } + ~CFGDotDiffDisplayGraph() { + // Due to opt bug we have static members. Clear them out. + GraphName = ""; + Nodes.clear(); + NodePtrs.clear(); + EntryNode = nullptr; + } + + void generateDotFile(StringRef DotFile); + + // Iterator to the nodes. Required by GraphWriter. + using NodeIterator = std::vector::const_iterator; + NodeIterator nodes_begin() const { + assert(NodeGenerationComplete && "Unexpected children iterator creation"); + return NodePtrs.cbegin(); + } + NodeIterator nodes_end() const { + assert(NodeGenerationComplete && "Unexpected children iterator creation"); + return NodePtrs.cend(); + } + + void setEntryNode(unsigned N) { + // At this point, there will be no new nodes. + assert(!NodeGenerationComplete && "Unexpected node creation"); + NodeGenerationComplete = true; + for (auto &N : Nodes) + NodePtrs.emplace_back(&N); + + EntryNode = NodePtrs[N]; + } + + void createNode(std::string C, IRChangeDiffType T) { + assert(!NodeGenerationComplete && "Unexpected node creation"); + Nodes.emplace_back(C, T, *this); + } + DisplayNode &getNode(unsigned N) { + assert(N < Nodes.size() && "Node is out of bounds"); + return Nodes[N]; + } + unsigned size() const { + assert(NodeGenerationComplete && "Unexpected children iterator creation"); + return Nodes.size(); + } + + // Return the name of the graph. Required by GraphWriter. + std::string getGraphName() const { return GraphName; } + + // Return the string representing the differences for basic block \p Node. + // Required by GraphWriter. + std::string getNodeLabel(const DisplayNode &Node) const { + return Node.getContent(); + } + + // Return a string with colour information for Dot. Required by GraphWriter. + std::string getNodeAttributes(const DisplayNode &Node) const { + return attribute(Node.getType()); + } + + // Return a string with colour information for Dot. Required by GraphWriter. + std::string getEdgeColorAttr(const DisplayNode &From, + const DisplayNode &To) const { + return attribute(From.getEdge(To).getType()); + } + + // Get the starting basic block. Required by GraphWriter. + DisplayNode *getEntryNode() const { + assert(NodeGenerationComplete && "Unexpected children iterator creation"); + return EntryNode; + } + +protected: + // Return the string containing the colour to use as a Dot attribute. + std::string attribute(IRChangeDiffType T) const; + + // There appears to be an optimization bug in the build compiler in + // that when begin() and end() are called from GraphWriter, the pointer to + // CFGDotDiff (the G member of GraphWriter) is changed to refer to the + // stack. This does not happen in a non-release build and I do not see + // any code that should cause a copy to be made (in fact, the copy + // constructor and operator= are deleted). Because of this, these members + // have to be static or else the program will crash. + // It can be shown by adding + // "dbgs() << __FUNCTION__ << " " << (void*)this << "\n";" into the ctor + // and begin/end functions. They should match because only 1 object is + // created. + // TODO verify the bug and make a bug report. + static bool NodeGenerationComplete; + static std::string GraphName; + static std::vector Nodes; + static std::vector NodePtrs; + static DisplayNode *EntryNode; +}; + +bool CFGDotDiffDisplayGraph::NodeGenerationComplete; +std::string CFGDotDiffDisplayGraph::GraphName; +std::vector CFGDotDiffDisplayGraph::Nodes; +std::vector CFGDotDiffDisplayGraph::NodePtrs; +DisplayNode *CFGDotDiffDisplayGraph::EntryNode; + +void DisplayNode::createEdge(StringRef V, DisplayNode &Node, + IRChangeDiffType T) { + Edges.emplace_back(V.str(), Node, T); + Children.insert(&Node); +} + +void DisplayNode::createEdgeMap() { + for (auto &E : Edges) + EdgeMap.insert({&E.getDestinationNode(), &E}); +} + +class CFGDotDiffNode; +class CFGDotDiff; +class CFGDotDiff; + +// A class representing a basic block in the Dot difference graph. +class CFGDotDiffNode { +public: + CFGDotDiffNode() = delete; + + // Create a node in Dot difference graph \p G representing the basic block + // represented by \p BD with type \p T (where it exists). + CFGDotDiffNode(CFGDotDiff &G, unsigned N, const BlockSuccessorsBlockData &BD, + IRChangeDiffType T) + : Graph(G), N(N), Data{&BD, nullptr}, Type(T) {} + CFGDotDiffNode(const CFGDotDiffNode &DN) + : Graph(DN.Graph), N(DN.N), Data{DN.Data[0], DN.Data[1]}, Type(DN.Type), + EdgesMap(DN.EdgesMap), Children(DN.Children), Edges(DN.Edges) {} + + unsigned getIndex() const { return N; } + + // The label of the basic block + StringRef getLabel() const { + assert(Data[0] && "Expected Data[0] to be set."); + return Data[0]->getLabel(); + } + // Return where this block exists. + IRChangeDiffType getType() const { return Type; } + // Change this basic block from being only in before to being common. + // Save the pointer to \p Other. + void setCommon(const BlockSuccessorsBlockData &Other) { + assert(!Data[1] && "Expected only one block datum"); + Data[1] = &Other; + Type = IsCommon; + } + // Add an edge to \p E of type {\p Value, \p T}. + void addEdge(unsigned E, StringRef Value, IRChangeDiffType T) { + // This is a new edge or it is an edge being made common. + assert((EdgesMap.count(E) == 0 || T == IsCommon) && + "Unexpected edge count and type."); + EdgesMap[E] = {Value.str(), T}; + } + // Record the children and create edges. + void finalize(CFGDotDiff &G); + + // Return the type of the edge to node \p S. + std::pair getEdge(const unsigned S) const { + assert(EdgesMap.count(S) == 1 && "Expected to find edge."); + return EdgesMap.at(S); + } + + // Return the string representing the basic block. + std::string getBodyContent() const; + + void createDisplayEdges(CFGDotDiffDisplayGraph &Graph, unsigned DisplayNode, + std::map &NodeMap); + +protected: + CFGDotDiff &Graph; + const unsigned N; + const BlockSuccessorsBlockData *Data[2]; + IRChangeDiffType Type; + std::map> EdgesMap; + std::vector Children; + std::vector Edges; +}; + +// Class representing the difference graph between two functions. +class CFGDotDiff { +public: + // \p Title is the title given to the graph. \p EntryNodeName is the + // entry node for the function. \p Before and \p After are the before + // after versions of the function, respectively. \p Dir is the directory + // in which to store the results. + CFGDotDiff(StringRef Title, const BlockSuccessorsFuncData &Before, + const BlockSuccessorsFuncData &After, StringRef Dir); + // Only needed because of opt bug... + ~CFGDotDiff() { + // Due to opt bug we have static members. Clear them out. + Nodes.clear(); + NodePosition.clear(); + GraphName = ""; + } + + CFGDotDiff(const CFGDotDiff &) = delete; + CFGDotDiff &operator=(const CFGDotDiff &) = delete; + + CFGDotDiffDisplayGraph createDisplayGraph(StringRef Title, + StringRef EntryNodeName); + + // Return a string consisting of the labels for the \p Source and \p Sink. + // The combination allows distinguishing changing transitions on the + // same value (ie, a transition went to X before and goes to Y after). + // Required by GraphWriter. + StringRef getEdgeSourceLabel(const unsigned &Source, + const unsigned &Sink) const { + std::string S = + getNode(Source).getLabel().str() + " " + getNode(Sink).getLabel().str(); + assert(EdgeLabels.count(S) == 1 && "Expected to find edge label."); + return EdgeLabels.find(S)->getValue(); + } + + // Return the number of basic blocks (nodes). Required by GraphWriter. + unsigned size() const { return Nodes.size(); } + + CFGDotDiffNode &getNode(unsigned N) const { + assert(N < Nodes.size() && "Unexpected index for node reference"); + return Nodes[N]; + } + +protected: + // Return the string surrounded by HTML to make it the appropriate colour. + std::string colourize(std::string S, IRChangeDiffType T) const; + // Return the string containing the colour to use as a Dot attribute. + std::string attribute(IRChangeDiffType T) const; + + void createNode(StringRef Label, const BlockSuccessorsBlockData &BD, + IRChangeDiffType T) { + unsigned Pos = Nodes.size(); + Nodes.emplace_back(*this, Pos, BD, T); + NodePosition.insert({Label, Pos}); + } + + // There appears to be an optimization bug in the build compiler in + // that when begin() and end() are called from GraphWriter, the pointer to + // CFGDotDiff (the G member of GraphWriter) is changed to refer to the + // stack. This does not happen in a non-release build and I do not see + // any code that should cause a copy to be made (in fact, the copy + // constructor and operator= are deleted). Because of this, these members + // have to be static or else the program will crash. + // It can be shown by adding + // "dbgs() << __FUNCTION__ << " " << (void*)this << "\n";" into the ctor + // and begin/end functions. They should match because only 1 object is + // created. + // TODO verify the bug and make a bug report. + static std::vector Nodes; + static StringMap NodePosition; + static std::string GraphName; + + CFGDotDiffNode *EntryNode; + StringMap EdgeLabels; +}; + +std::string CFGDotDiffNode::getBodyContent() const { + if (Type == IsCommon) { + assert(Data[1] && "Expected Data[1] to be set."); + + StringRef SR[2]; + for (int I = 0; I < 2; ++I) { + SR[I] = Data[I]->getBody(); + // drop initial '\n' if present + if (SR[I][0] == '\n') + SR[I] = SR[I].drop_front(); + // drop predecessors as they can be big and are redundant + SR[I] = SR[I].drop_until([](char c) { return c == '\n'; }).drop_front(); + } + + SmallString<80> OldLineFormat = formatv( + "%l
", Colours[InBefore]); + SmallString<80> NewLineFormat = formatv( + "%l
", Colours[InAfter]); + SmallString<80> UnchangedLineFormat = formatv( + "%l
", Colours[IsCommon]); + std::string Diff = Data[0]->getLabel().str(); + Diff = Diff + ":\n
" + + doLinuxDiff(CFGDotComparer::makeHTMLReady(SR[0]), + CFGDotComparer::makeHTMLReady(SR[1]), OldLineFormat, + NewLineFormat, UnchangedLineFormat); + + // Diff adds in some empty colour changes which are not valid HTML + // so remove them. + for (unsigned I = InBefore; I <= IsCommon; ++I) { + std::string S = formatv("", Colours[I]); + size_t P = Diff.find(S); + while (P != std::string::npos) { + Diff.erase(P, S.length()); + P = Diff.find(S, P); + } + } + return Diff; + } + + // Put node out in the appropriate colour. + assert(!Data[1] && "Data[1] is set unexpectedly."); + std::string Body = CFGDotComparer::makeHTMLReady(Data[0]->getBody()); + const StringRef BS = Body; + StringRef BS1 = BS; + // Drop leading newline, if present. + if (BS.front() == '\n') + BS1 = BS1.drop_front(1); + // Get label. + StringRef Label = BS1.take_until([](char c) { return c == ':'; }); + // drop predecessors as they can be big and are redundant + BS1 = BS1.drop_until([](char c) { return c == '\n'; }).drop_front(); + + std::string S(""); + S.append(Label.str()); + S.append(":"); + + // align each line to the left. + while (BS1.size()) { + S.append("
"); + StringRef Line = BS1.take_until([](char c) { return c == '\n'; }); + S.append(Line.str()); + BS1 = BS1.drop_front(Line.size() + 1); + } + S.append("
"); + S.append("
"); + return S; +} + +std::string CFGDotDiff::colourize(std::string S, IRChangeDiffType T) const { + if (S.length() == 0) + return S; + return "" + S + ""; +} + +std::string CFGDotDiff::attribute(IRChangeDiffType T) const { + return "color=" + Colours[T]; +} + +std::string CFGDotDiffDisplayGraph::attribute(IRChangeDiffType T) const { + return "color=" + Colours[T]; +} + +CFGDotDiff::CFGDotDiff(StringRef Title, const BlockSuccessorsFuncData &Before, + const BlockSuccessorsFuncData &After, StringRef Dir) { + // Due to opt bug we have static members. Ensure that they are empty. + assert(Nodes.empty() && "Expected Nodes to be empty."); + assert(NodePosition.empty() && "Expected NodePosition to be empty."); + assert(GraphName.size() == 0 && "Expected GraphName to be empty."); + + GraphName = Title.str(); + StringMap EdgesMap; + + // Handle each basic block in the before IR. + for (auto &B : Before) { + StringRef Label = B.getKey(); + const BlockSuccessorsBlockData &BD = B.getValue(); + createNode(Label, BD, InBefore); + + // Create transitions with names made up of the from block label, the value + // on which the transition is made and the to block label. + for (StringMap::const_iterator Sink = BD.getData().begin(), + E = BD.getData().end(); + Sink != E; ++Sink) { + std::string Key = (Label + " " + Sink->getKey().str()).str() + " " + + BD.getData().getSuccessorLabel(Sink->getKey()).str(); + EdgesMap.insert({Key, InBefore}); + } + } + + // Handle each basic block in the after IR + for (auto &A : After) { + StringRef Label = A.getKey(); + const BlockSuccessorsBlockData &BD = A.getValue(); + unsigned C = NodePosition.count(Label); + if (C == 0) + // This only exists in the after IR. Create the node. + createNode(Label, BD, InAfter); + else { + assert(C == 1 && "Unexpected multiple nodes."); + Nodes[NodePosition[Label]].setCommon(BD); + } + // Add in the edges between the nodes (as common or only in after). + for (StringMap::const_iterator Sink = BD.getData().begin(), + E = BD.getData().end(); + Sink != E; ++Sink) { + std::string Key = (Label + " " + Sink->getKey().str()).str() + " " + + BD.getData().getSuccessorLabel(Sink->getKey()).str(); + unsigned C = EdgesMap.count(Key); + if (C == 0) + EdgesMap.insert({Key, InAfter}); + else { + EdgesMap[Key] = IsCommon; + } + } + } + + // Now go through the map of edges and add them to the node. + for (auto &E : EdgesMap) { + // Extract the source, sink and value from the edge key. + StringRef S = E.getKey(); + auto SP1 = S.rsplit(' '); + auto &SourceSink = SP1.first; + auto SP2 = SourceSink.split(' '); + StringRef Source = SP2.first; + StringRef Sink = SP2.second; + StringRef Value = SP1.second; + + assert(NodePosition.count(Source) == 1 && "Expected to find node."); + CFGDotDiffNode &SourceNode = Nodes[NodePosition[Source]]; + assert(NodePosition.count(Sink) == 1 && "Expected to find node."); + unsigned SinkNode = NodePosition[Sink]; + IRChangeDiffType T = E.second; + + // Look for an edge from Source to Sink + if (EdgeLabels.count(SourceSink) == 0) + EdgeLabels.insert({SourceSink, colourize(Value.str(), T)}); + else { + StringRef V = EdgeLabels.find(SourceSink)->getValue(); + std::string NV = colourize(V.str() + " " + Value.str(), T); + T = IsCommon; + EdgeLabels[SourceSink] = NV; + } + SourceNode.addEdge(SinkNode, Value, T); + } + for (auto &I : Nodes) + I.finalize(*this); +} + +CFGDotDiffDisplayGraph CFGDotDiff::createDisplayGraph(StringRef Title, + StringRef EntryNodeName) { + assert(NodePosition.count(EntryNodeName) == 1 && + "Expected to find entry block in map."); + unsigned Entry = NodePosition[EntryNodeName]; + assert(Entry < Nodes.size() && "Expected to find entry node"); + CFGDotDiffDisplayGraph G(Title.str()); + + std::map NodeMap; + + int EntryIndex = -1; + unsigned Index = 0; + for (auto &I : Nodes) { + if (I.getIndex() == Entry) + EntryIndex = Index; + G.createNode(I.getBodyContent(), I.getType()); + NodeMap.insert({I.getIndex(), Index++}); + } + assert(EntryIndex >= 0 && "Expected entry node index to be set."); + G.setEntryNode(EntryIndex); + + for (auto &I : NodeMap) { + unsigned SourceNode = I.first; + unsigned DisplayNode = I.second; + getNode(SourceNode).createDisplayEdges(G, DisplayNode, NodeMap); + } + return G; +} + +void CFGDotDiffNode::createDisplayEdges( + CFGDotDiffDisplayGraph &DisplayGraph, unsigned DisplayNodeIndex, + std::map &NodeMap) { + + DisplayNode &SourceDisplayNode = DisplayGraph.getNode(DisplayNodeIndex); + + for (auto I : Edges) { + unsigned SinkNodeIndex = I; + IRChangeDiffType Type = getEdge(SinkNodeIndex).second; + const CFGDotDiffNode *SinkNode = &Graph.getNode(SinkNodeIndex); + + StringRef Label = Graph.getEdgeSourceLabel(getIndex(), SinkNodeIndex); + DisplayNode &SinkDisplayNode = DisplayGraph.getNode(SinkNode->getIndex()); + SourceDisplayNode.createEdge(Label, SinkDisplayNode, Type); + } + SourceDisplayNode.createEdgeMap(); +} + +// TODO Nodes should probably be a StringMap after the +// display graph is separated out, which would remove the need for NodePosition. +std::vector CFGDotDiff::Nodes; +StringMap CFGDotDiff::NodePosition; +std::string CFGDotDiff::GraphName; + +void CFGDotDiffNode::finalize(CFGDotDiff &G) { + for (auto E : EdgesMap) { + Children.emplace_back(E.first); + Edges.emplace_back(E.first); + } +} + +} // namespace + +namespace llvm { + +template <> struct GraphTraits { + using NodeRef = const DisplayNode *; + using ChildIteratorType = DisplayNode::ChildIterator; + using nodes_iterator = CFGDotDiffDisplayGraph::NodeIterator; + using EdgeRef = const DisplayEdge *; + using ChildEdgeIterator = DisplayNode::EdgeIterator; + + static NodeRef getEntryNode(const CFGDotDiffDisplayGraph *G) { + return G->getEntryNode(); + } + static ChildIteratorType child_begin(NodeRef N) { + return N->children_begin(); + } + static ChildIteratorType child_end(NodeRef N) { return N->children_end(); } + static nodes_iterator nodes_begin(const CFGDotDiffDisplayGraph *G) { + return G->nodes_begin(); + } + static nodes_iterator nodes_end(const CFGDotDiffDisplayGraph *G) { + return G->nodes_end(); + } + static ChildEdgeIterator child_edge_begin(NodeRef N) { + return N->edges_begin(); + } + static ChildEdgeIterator child_edge_end(NodeRef N) { return N->edges_end(); } + static NodeRef edge_dest(EdgeRef E) { return &E->getDestinationNode(); } + static unsigned size(const CFGDotDiffDisplayGraph *G) { return G->size(); } +}; + +template <> +struct DOTGraphTraits : public DefaultDOTGraphTraits { + explicit DOTGraphTraits(bool simple = false) + : DefaultDOTGraphTraits(simple) {} + + static bool renderNodeUsingHTML(const DisplayNode *Node) { return true; } + static std::string getGraphName(const CFGDotDiffDisplayGraph *DiffData) { + return DiffData->getGraphName(); + } + static std::string + getGraphProperties(const CFGDotDiffDisplayGraph *DiffData) { + return "\tsize=\"190, 190\";\n"; + } + static std::string getNodeLabel(const DisplayNode *Node, + const CFGDotDiffDisplayGraph *DiffData) { + return DiffData->getNodeLabel(*Node); + } + static std::string getNodeAttributes(const DisplayNode *Node, + const CFGDotDiffDisplayGraph *DiffData) { + return DiffData->getNodeAttributes(*Node); + } + static std::string getEdgeSourceLabel(const DisplayNode *From, + DisplayNode::ChildIterator &To) { + return From->getEdgeSourceLabel(**To); + } + static std::string getEdgeAttributes(const DisplayNode *From, + DisplayNode::ChildIterator &To, + const CFGDotDiffDisplayGraph *DiffData) { + return DiffData->getEdgeColorAttr(*From, **To); + } +}; + +} // namespace llvm + +namespace { + +void CFGDotDiffDisplayGraph::generateDotFile(StringRef DotFile) { + std::error_code EC; + llvm::raw_fd_ostream OutStream(DotFile, EC); + if (EC) { + errs() << "Error: " << EC.message() << "\n"; + return; + } + GraphWriter W(OutStream, this, false); + W.writeGraph(""); + OutStream.flush(); + OutStream.close(); +} + +} // namespace + +namespace cr { + +void BlockSuccessors::populate(const BasicBlock &B) { + // Build up transition labels. + const Instruction *Term = B.getTerminator(); + if (const BranchInst *Br = dyn_cast(Term)) + if (Br->isUnconditional()) + addSuccessorLabel(Br->getSuccessor(0)->getName().str(), ""); + else { + addSuccessorLabel(Br->getSuccessor(0)->getName().str(), "true"); + addSuccessorLabel(Br->getSuccessor(1)->getName().str(), "false"); + } + else if (const SwitchInst *Sw = dyn_cast(Term)) { + addSuccessorLabel(Sw->case_default()->getCaseSuccessor()->getName().str(), + "default"); + for (auto &C : Sw->cases()) { + assert(C.getCaseValue() && "Expected to find case value."); + SmallString<20> Value = formatv("{0}", C.getCaseValue()->getSExtValue()); + addSuccessorLabel(C.getCaseSuccessor()->getName().str(), Value); + } + } else + for (const_succ_iterator I = succ_begin(&B), E = succ_end(&B); I != E; ++I) + addSuccessorLabel((*I)->getName().str(), ""); +} + +std::string CFGDotComparer::makeHTMLReady(StringRef SR) { + std::string S; + while (true) { + StringRef Clean = + SR.take_until([](char C) { return C == '<' || C == '>'; }); + S.append(Clean.str()); + SR = SR.drop_front(Clean.size()); + if (SR.size() == 0) + return S; + S.append(SR[0] == '<' ? "<" : ">"); + SR = SR.drop_front(); + } + llvm_unreachable("problems converting string to HTML"); +} + +CFGDotComparer::CFGDotComparer(raw_fd_ostream &OS, unsigned N, StringRef Dir, + const BlockSuccessorsIRData &Before, + const BlockSuccessorsIRData &After) + : IRComparer(Before, After, N), Directory(Dir.str()), HTML(OS) { + // Set up the colours based on the hidden options. + Colours[InBefore] = BeforeColour; + Colours[InAfter] = AfterColour; + Colours[IsCommon] = CommonColour; +} + +void CFGDotComparer::handleSingleFunctionCompare( + StringRef Name, StringRef Prefix, StringRef PassID, unsigned Major, + unsigned *Minor, const BlockSuccessorsFuncData &Before, + const BlockSuccessorsFuncData &After) { + SmallString<8> Extender; + SmallString<8> Number; + // Handle numbering and file names. + if (Minor) { + Extender = formatv("{0}_{1}", Major, *Minor); + Number = formatv("{0}.{1}", Major, *Minor); + } else { + Extender = formatv("{0}", Major); + Number = formatv("{0}", Major); + } + // Create a temporary file name for the dot file. + SmallVector SV; + sys::fs::createUniquePath("cfgdot-%%%%%%.dot", SV, true); + std::string DotFile = Twine(SV).str(); + + SmallString<20> PDFFileName = formatv("diff_{0}.pdf", Extender); + SmallString<200> Text; + + Text = formatv("{0}.{1}{2} {3}", Number, Prefix, makeHTMLReady(PassID), Name); + + CFGDotDiff Diff(Text, Before, After, Directory); + CFGDotDiffDisplayGraph DG = + Diff.createDisplayGraph(Text, After.getEntryBlockName()); + DG.generateDotFile(DotFile); + + HTML << genHTML(Text, DotFile, PDFFileName, Directory, Minor != nullptr); + std::error_code EC = sys::fs::remove(DotFile); + if (EC) + errs() << "Error: " << EC.message() << "\n"; +} + +std::string CFGDotComparer::genHTML(StringRef Text, StringRef DotFile, + StringRef PDFFileName, StringRef Directory, + bool Indent) { + SmallString<20> PDFFile = formatv("{0}/{1}", Directory, PDFFileName); + // Create the PDF file. + SmallString<200> Command = formatv("dot -Tpdf -o {0} {1}", PDFFile, DotFile); + system(Command.c_str()); + // Create the HTML tag refering to the PDF file. + SmallString<200> S = + formatv("
{1}
\n", + PDFFileName, Text, Indent ? "style=\"margin-left:2em\" " : ""); + return S.c_str(); +} + template class ChangeReporter; template class TextChangeReporter; @@ -372,4 +1194,11 @@ template class IRComparer; +template class BlockDataTemplate; +template class FuncDataTemplate; +template class IRDataTemplate; +template class ChangeReporter; +template class IRComparer; + } // namespace cr Index: llvm/lib/Passes/StandardInstrumentations.cpp =================================================================== --- llvm/lib/Passes/StandardInstrumentations.cpp +++ llvm/lib/Passes/StandardInstrumentations.cpp @@ -77,6 +77,11 @@ "print-changes", cl::Hidden, cl::init(false), cl::desc("Print in-line differences of changes made by a pass")); +static cl::opt CFGDotChanged( + "cfg-dot-changed", + cl::desc("Generate dot files into specified directory for changed IRs"), + cl::Hidden, cl::init("")); + namespace { void printIR(raw_ostream &OS, const Function *F, StringRef Banner, @@ -141,65 +146,6 @@ llvm::printLoop(const_cast(*L), OS, std::string(Banner)); } -// Copied/Modified from FuzzerUtilPosix.cpp -// Return true on success, false otherwise. -bool ExecuteCommand(const StringRef Cmd, std::string *CmdOutput) { - FILE *Pipe = popen(Cmd.str().c_str(), "r"); - if (!Pipe) - return false; - - if (CmdOutput) { - char TmpBuffer[128]; - while (fgets(TmpBuffer, sizeof(TmpBuffer), Pipe)) - CmdOutput->append(TmpBuffer); - } - - return pclose(Pipe) == 0; -} - -// Perform a linux based diff between \p Before and \p After, using -// \p OldLineFormat, \p NewLineFormat, and \p UnchangedLineFormat -// to control the formatting of the output. -std::string doLinuxDiff(StringRef Before, StringRef After, - StringRef OldLineFormat, StringRef NewLineFormat, - StringRef UnchangedLineFormat) { - StringRef SR[2]{Before, After}; - // Store the 2 bodies into temporary files and call diff on them - // to get the body of the node. - static std::string FileName[2]; - static int FD[2]{-1, -1}; - for (int I = 0; I < 2; ++I) { - if (FD[I] == -1) { - SmallVector SV; - std::error_code EC = - sys::fs::createTemporaryFile("tmpdiff", "txt", FD[I], SV); - assert(!EC && "Unable to create temporary file."); - FileName[I] = Twine(SV).str(); - } - - std::error_code EC = sys::fs::openFileForWrite(FileName[I], FD[I]); - assert(!EC && "Unable to open temporary file for writing."); - - llvm::raw_fd_ostream OutStream(FD[I], /*shouldClose=*/true); - assert(FD[I] != -1 && "Error opening file for writing."); - OutStream << SR[I]; - } - - SmallString<512> DiffCall = - formatv("diff -w -d --old-line-format='{2}' --new-line-format='{3}' " - "--unchanged-line-format='{4}' {0} {1}", - FileName[0], FileName[1], OldLineFormat, NewLineFormat, - UnchangedLineFormat); - std::string Diff; - ExecuteCommand(DiffCall, &Diff); - // Clean up. - for (unsigned I = 0; I < 2; ++I) { - std::error_code EC = sys::fs::remove(FileName[I]); - assert(!EC && "Unable to remove temporary file."); - } - return Diff; -} - } // namespace Optional> llvm::unwrapModule(Any IR) { @@ -511,6 +457,103 @@ TextChangeReporter::registerCallbacks(PIC); } +CFGDotChangeReporter::CFGDotChangeReporter() + : ChangeReporter( + // HandleInitialIR + [&](Any IR) -> void { + HTML << "\n
\n" + "

\n"; + // Create representation of IR + BlockSuccessorsIRData Data; + bool B = CFGDotComparer::analyzeIR(IR, Data); + (void)B; + assert(B && "Problems generating data for initial IR"); + // Now compare it against itself, which will have everything the + // same and will generate the files. + CFGDotComparer Comparer(HTML, N, CFGDotChanged, Data, Data); + Comparer.compare(IR, " ", "Initial IR", ""); + HTML << "

\n

\n"; + ++N; + }, + // GenerateOutput + [](Any IR, StringRef PassID, BlockSuccessorsIRData &Data) -> bool { + return CFGDotComparer::analyzeIR(IR, Data); + }, + // OmitAfter + [&](StringRef PassID, std::string &Name) -> void { + SmallString<20> Banner = formatv( + " {0}. After {1}{2} omitted because no change
\n", + N, CFGDotComparer::makeHTMLReady(PassID), Name); + HTML << Banner; + ++N; + }, + // HandleAfter + [&](StringRef PassID, std::string &Name, + const BlockSuccessorsIRData &Before, + const BlockSuccessorsIRData &After, Any IR) -> void { + CFGDotComparer Comparer(HTML, N, CFGDotChanged, Before, After); + Comparer.compare(IR, " After ", PassID, Name); + HTML << "

\n"; + ++N; + }, + // HandleInvalidated + [&](StringRef PassID) -> void { + SmallString<20> Banner = + formatv(" {0}. {1} invalidated
\n", N, + CFGDotComparer::makeHTMLReady(PassID)); + HTML << Banner; + ++N; + }, + // HandleFiltered + [&](StringRef PassID, std::string &Name) -> void { + SmallString<20> Banner = + formatv(" {0}. After {1}{2} filtered out
\n", N, + CFGDotComparer::makeHTMLReady(PassID), Name); + HTML << Banner; + ++N; + }, + // HandleIgnored + [&](StringRef PassID, std::string &Name) -> void { + SmallString<20> Banner = + formatv(" {0}. {1}{2} ignored
\n", N, + CFGDotComparer::makeHTMLReady(PassID), Name); + HTML << Banner; + ++N; + }, + // Same + [](const BlockSuccessorsIRData &Before, + const BlockSuccessorsIRData &After) -> bool { + return Before == After; + }), + N(0), HTML(CFGDotChanged + "/passes.html", EC) { + HTML << "passes.html\n"; +} + +CFGDotChangeReporter::~CFGDotChangeReporter() { + HTML << "\n"; + HTML.flush(); + HTML.close(); +} + +void CFGDotChangeReporter::registerCallbacks( + PassInstrumentationCallbacks &PIC) { + if (CFGDotChanged.length() != 0) + ChangeReporter::registerCallbacks(PIC); +} + void StandardInstrumentations::registerCallbacks( PassInstrumentationCallbacks &PIC) { PrintIR.registerCallbacks(PIC); @@ -519,4 +562,5 @@ OptNone.registerCallbacks(PIC); PrintChangedIR.registerCallbacks(PIC); PrintChanges.registerCallbacks(PIC); + CFGDotDiffGenerator.registerCallbacks(PIC); }