mirror of
https://github.com/revng/revng
synced 2026-06-21 14:07:57 +00:00
Ivan Krysak
588 lines
22 KiB
C++
588 lines
22 KiB
C++
//
|
|
// This file is distributed under the MIT License. See LICENSE.md for details.
|
|
//
|
|
|
|
#include <algorithm>
|
|
#include <compare>
|
|
#include <cstdint>
|
|
#include <iterator>
|
|
|
|
#include "llvm/ADT/EquivalenceClasses.h"
|
|
#include "llvm/ADT/GraphTraits.h"
|
|
#include "llvm/ADT/PostOrderIterator.h"
|
|
#include "llvm/ADT/STLExtras.h"
|
|
#include "llvm/ADT/SetOperations.h"
|
|
#include "llvm/ADT/SetVector.h"
|
|
#include "llvm/ADT/SmallVector.h"
|
|
#include "llvm/Support/Debug.h"
|
|
|
|
#include "revng/DataLayoutAnalysis/DLATypeSystem.h"
|
|
#include "revng/Support/Assert.h"
|
|
#include "revng/Support/Debug.h"
|
|
|
|
#include "DLAStep.h"
|
|
|
|
using LTSN = dla::LayoutTypeSystemNode;
|
|
using order = std::strong_ordering;
|
|
using Link = dla::LayoutTypeSystemNode::Link;
|
|
using NodeVec = llvm::SmallVector<LTSN *>;
|
|
using EdgeVec = llvm::SmallVector<Link>;
|
|
using Tag = dla::TypeLinkTag;
|
|
using NonPointerFilterT = EdgeFilteredGraph<LTSN *, dla::isNotPointerEdge>;
|
|
|
|
using namespace llvm;
|
|
|
|
static Logger<> Log("dla-deduplicate-union-fields");
|
|
static Logger<> CmpLog("dla-duf-comparisons");
|
|
|
|
namespace dla {
|
|
|
|
/// Strong ordering for nodes: order by size, then by number of successors.
|
|
static std::weak_ordering weakOrderNodes(const LTSN *A, const LTSN *B) {
|
|
if (A == B)
|
|
return std::weak_ordering::equivalent;
|
|
|
|
if (not A)
|
|
return std::weak_ordering::less;
|
|
|
|
if (not B)
|
|
return std::weak_ordering::greater;
|
|
|
|
const auto SizeCmp = A->Size <=> B->Size;
|
|
if (SizeCmp != std::weak_ordering::equivalent) {
|
|
revng_log(CmpLog, "Different sizes");
|
|
return SizeCmp;
|
|
}
|
|
|
|
// If they have a different number of successors, order the one with less
|
|
// successor first;
|
|
size_t NChild1 = A->Successors.size();
|
|
size_t NChild2 = B->Successors.size();
|
|
const auto NChildCmp = NChild1 <=> NChild2;
|
|
if (NChildCmp != std::weak_ordering::equivalent) {
|
|
revng_log(CmpLog,
|
|
"Different number of successors: node "
|
|
<< A->ID << " has " << NChild1 << " successors, node " << B->ID
|
|
<< " has" << NChild2 << " successors");
|
|
return NChildCmp;
|
|
}
|
|
|
|
// If they have the same number of successors, consider them by kind.
|
|
size_t NInstanceChild1 = 0;
|
|
size_t NInstanceChild2 = 0;
|
|
size_t NPointerChild1 = 0;
|
|
size_t NPointerChild2 = 0;
|
|
for (const auto &[Child1, Child2] : llvm::zip(A->Successors, B->Successors)) {
|
|
if (isInstanceEdge(Child1))
|
|
++NInstanceChild1;
|
|
else
|
|
++NPointerChild1;
|
|
|
|
if (isInstanceEdge(Child2))
|
|
++NInstanceChild2;
|
|
else
|
|
++NPointerChild2;
|
|
}
|
|
|
|
if (auto Cmp = NInstanceChild1 <=> NInstanceChild2; Cmp != 0)
|
|
return Cmp;
|
|
|
|
if (auto Cmp = NPointerChild1 <=> NPointerChild2; Cmp != 0)
|
|
return Cmp;
|
|
|
|
// They are equivalent, but they are not equal, because they are actually 2
|
|
// different nodes with a different ID.
|
|
return std::weak_ordering::equivalent;
|
|
}
|
|
|
|
/// Strong ordering for nodes: order by size, then by number of successors, and
|
|
/// only at the end for ID.
|
|
static std::strong_ordering orderNodes(const LTSN *A, const LTSN *B) {
|
|
std::weak_ordering WeakNodeCmp = weakOrderNodes(A, B);
|
|
if (WeakNodeCmp != 0)
|
|
return (WeakNodeCmp < 0) ? std::strong_ordering::less :
|
|
std::strong_ordering::greater;
|
|
|
|
if (not A and not B)
|
|
return std::strong_ordering::equal;
|
|
|
|
return A->ID <=> B->ID;
|
|
}
|
|
|
|
/// Strong ordering for edges: order by kind, then by offset expression
|
|
static std::strong_ordering orderEdgeTags(const Tag *A, const Tag *B) {
|
|
if (A == B)
|
|
return std::strong_ordering::equal;
|
|
|
|
revng_assert(A != nullptr and B != nullptr);
|
|
|
|
auto KindA = A->getKind();
|
|
auto KindB = B->getKind();
|
|
|
|
// If they have different kind, only look at the kind
|
|
const auto KindCmp = KindA <=> KindB;
|
|
if (KindCmp != std::strong_ordering::equal)
|
|
return KindCmp;
|
|
|
|
OffsetExpression OffA = A->getOffsetExpr();
|
|
OffsetExpression OffB = B->getOffsetExpr();
|
|
|
|
// Smaller offsets go first
|
|
const auto OffsetCmp = OffA.Offset <=> OffB.Offset;
|
|
if (OffsetCmp != std::strong_ordering::equal)
|
|
return OffsetCmp;
|
|
|
|
// Smaller number of nested strides go first
|
|
const auto StrideSizeCmp = OffA.Strides.size() <=> OffB.Strides.size();
|
|
if (StrideSizeCmp != std::strong_ordering::equal)
|
|
return StrideSizeCmp;
|
|
|
|
// Lexical comparison of strides
|
|
for (const auto &[StrA, StrB] : llvm::zip(OffA.Strides, OffB.Strides)) {
|
|
const auto StrideCmp = StrA <=> StrB;
|
|
if (StrideCmp != std::strong_ordering::equal)
|
|
return StrideCmp;
|
|
}
|
|
|
|
// Smaller number of nested trip counts go first
|
|
const auto TCSizeCmp = OffA.TripCounts.size() <=> OffB.TripCounts.size();
|
|
if (TCSizeCmp != std::strong_ordering::equal)
|
|
return TCSizeCmp;
|
|
|
|
// Lexical comparison of nested trip counts
|
|
for (const auto &[TCA, TCB] : llvm::zip(OffA.TripCounts, OffB.TripCounts)) {
|
|
if (not TCA and not TCB)
|
|
continue;
|
|
if (TCA and not TCB)
|
|
return std::strong_ordering::less;
|
|
if (not TCA and TCB)
|
|
return std::strong_ordering::greater;
|
|
|
|
if (TCA and TCB) {
|
|
const auto TCCmp = *TCA <=> *TCB;
|
|
if (TCCmp != std::strong_ordering::equal)
|
|
return TCCmp;
|
|
}
|
|
}
|
|
|
|
return std::strong_ordering::equal;
|
|
}
|
|
|
|
/// Strong ordering for links: compare edge tags and destination node
|
|
static bool orderLinks(const Link &A, const Link &B) {
|
|
if (std::strong_ordering EdgeOrder = orderEdgeTags(A.second, B.second);
|
|
EdgeOrder != order::equal)
|
|
return EdgeOrder < 0;
|
|
|
|
return orderNodes(A.first, B.first) < 0;
|
|
}
|
|
|
|
/// Compare two subtrees, saving the visited nodes onto two stacks
|
|
static std::tuple<bool, NodeVec, NodeVec>
|
|
exploreAndCompare(const Link &Child1, const Link &Child2) {
|
|
|
|
if (orderEdgeTags(Child1.second, Child2.second) != 0) {
|
|
revng_log(CmpLog, "Different edges!");
|
|
return { false, {}, {} };
|
|
}
|
|
|
|
NodeVec VisitStack1{ Child1.first }, VisitStack2{ Child2.first };
|
|
|
|
for (size_t CurIdx = 0; CurIdx < VisitStack1.size(); ++CurIdx) {
|
|
revng_assert(VisitStack1.size() == VisitStack2.size());
|
|
|
|
const LTSN *Node1 = VisitStack1[CurIdx];
|
|
const LTSN *Node2 = VisitStack2[CurIdx];
|
|
|
|
revng_log(CmpLog, "Comparing " << Node1->ID << " with " << Node2->ID);
|
|
|
|
// If they are the same there's no need to recur. From here downwards the 2
|
|
// visits are guaranteed to always be the same.
|
|
if (Node1 == Node2)
|
|
continue;
|
|
|
|
// If the nodes have different sizes, or different number of successors
|
|
// we can already say they're not equivalent and bail out.
|
|
if (auto WeakNodeCmp = weakOrderNodes(Node1, Node2); WeakNodeCmp != 0) {
|
|
revng_log(CmpLog, "Not equivalent");
|
|
return { false, {}, {} };
|
|
}
|
|
|
|
// Enqueue the successors of the current nodes
|
|
EdgeVec NextToVisit1, NextToVisit2;
|
|
size_t NChildren = Node1->Successors.size();
|
|
revng_assert(NChildren == Node2->Successors.size());
|
|
|
|
NextToVisit1.reserve(NChildren);
|
|
NextToVisit2.reserve(NChildren);
|
|
llvm::copy(Node1->Successors, std::back_inserter(NextToVisit1));
|
|
llvm::copy(Node2->Successors, std::back_inserter(NextToVisit2));
|
|
|
|
// Sort the newly enqueued instance children
|
|
llvm::sort(NextToVisit1, orderLinks);
|
|
llvm::sort(NextToVisit2, orderLinks);
|
|
|
|
// Pointer edges could be traversed in principle, and make the
|
|
// tree-comparison even deeper. But for now we prevent that, otherwise
|
|
// the algorithm could end up running on very large parts of the graph,
|
|
// and we'll also have to detect loops to avoid infinite iterations.
|
|
// So for now we just compare pointers, that are always sorted at the
|
|
// back, and bail out if we find a pair of pointer edges that point to
|
|
// different nodes.
|
|
// NOTE: This relies on the fact that pointer edges are sorted after all
|
|
// other kinds of edges.
|
|
size_t FirstPointerIndex = NChildren;
|
|
size_t Index = 0;
|
|
for (const auto &[Link1, Link2] : llvm::zip(NextToVisit1, NextToVisit2)) {
|
|
if (isPointerEdge(Link1)) {
|
|
revng_assert(isPointerEdge(Link2));
|
|
if (Link1.first != Link2.first)
|
|
return { false, {}, {} };
|
|
if (FirstPointerIndex == NChildren)
|
|
FirstPointerIndex = Index;
|
|
}
|
|
++Index;
|
|
}
|
|
|
|
// Take note of the iterators pointing to the first pointer edge.
|
|
auto NextToVisit1End = std::next(NextToVisit1.begin(), FirstPointerIndex);
|
|
auto NextToVisit2End = std::next(NextToVisit2.begin(), FirstPointerIndex);
|
|
|
|
// Insert in the visit stack all the non-pointer edges.
|
|
// NOTE: if we ever want to make a deep traversal to compare pointers too,
|
|
// this should be the only place to change. Just allow the traversal to
|
|
// enqueue also all the pointer edges.
|
|
auto NonPointerRange1 = llvm::make_range(NextToVisit1.begin(),
|
|
NextToVisit1End);
|
|
auto NextNodeRange1 = llvm::make_first_range(NonPointerRange1);
|
|
VisitStack1.insert(VisitStack1.end(),
|
|
NextNodeRange1.begin(),
|
|
NextNodeRange1.end());
|
|
|
|
auto NonPointerRange2 = llvm::make_range(NextToVisit2.begin(),
|
|
NextToVisit2End);
|
|
auto NextNodeRange2 = llvm::make_first_range(NonPointerRange2);
|
|
VisitStack2.insert(VisitStack2.end(),
|
|
NextNodeRange2.begin(),
|
|
NextNodeRange2.end());
|
|
}
|
|
|
|
return { true, VisitStack1, VisitStack2 };
|
|
}
|
|
|
|
/// Check if two subtrees are equivalent, saving the visited nodes in the
|
|
/// order in which they were compared.
|
|
static std::tuple<bool, NodeVec, NodeVec> areEquivSubtrees(const Link &Child1,
|
|
const Link &Child2) {
|
|
return exploreAndCompare(Child1, Child2);
|
|
}
|
|
|
|
/// Visit the two subtrees of \a ToKeep and \a ToMerge. If they are
|
|
/// equivalent, merge each node with the one it has been compared to.
|
|
///
|
|
///\return true if the two nodes were merged, and merged subtree
|
|
///\param TS the graph in which the comparison should be performed
|
|
///\param ToKeep the root of the first subtree
|
|
///\param ToMerge the root of the second subtree, will be collapsed if
|
|
/// equivalent to the subtree of \a ToKeep
|
|
static std::tuple<bool, std::set<LTSN *>, std::set<LTSN *>>
|
|
mergeIfTopologicallyEq(LayoutTypeSystem &TS,
|
|
const Link &ToKeep,
|
|
const Link &ToMerge) {
|
|
|
|
auto &&[AreEquiv, Subtree1, Subtree2] = areEquivSubtrees(ToKeep, ToMerge);
|
|
if (not AreEquiv) {
|
|
revng_log(CmpLog, "Different!");
|
|
return { false, {}, {} };
|
|
}
|
|
|
|
revng_log(CmpLog, "Equivalent!");
|
|
|
|
// Compute equivalence classes of nodes that have to be merged together.
|
|
llvm::EquivalenceClasses<LTSN *> MergeClasses;
|
|
for (const auto &[N1, N2] : llvm::zip(Subtree1, Subtree2))
|
|
MergeClasses.unionSets(N1, N2);
|
|
|
|
LTSN *ChildToKeep = ToKeep.first;
|
|
std::set<LTSN *> ErasedNodes;
|
|
std::set<LTSN *> PreservedNodes;
|
|
for (EquivalenceClasses<LTSN *>::iterator I = MergeClasses.begin(),
|
|
E = MergeClasses.end();
|
|
I != E;
|
|
++I) {
|
|
|
|
if (!I->isLeader())
|
|
continue; // Ignore non-leader sets.
|
|
|
|
// Decide which node to keep for each equivalence class.
|
|
// This typically depends only on the order of insertions of stuff in the
|
|
// class, so it's deterministic. However, we want the NodeToKeep to always
|
|
// be preserved, so we have to enforce it manually.
|
|
LTSN *Keep = *MergeClasses.member_begin(I);
|
|
if (MergeClasses.isEquivalent(ChildToKeep, Keep))
|
|
Keep = ChildToKeep;
|
|
|
|
for (LTSN *Merge : llvm::make_range(MergeClasses.member_begin(I),
|
|
MergeClasses.member_end())) {
|
|
if (Keep == Merge) {
|
|
PreservedNodes.insert(Keep);
|
|
continue;
|
|
}
|
|
TS.mergeNodes({ Keep, Merge });
|
|
ErasedNodes.insert(Merge);
|
|
}
|
|
}
|
|
|
|
if (VerifyLog.isEnabled())
|
|
revng_assert(TS.verifyDAG());
|
|
|
|
// The root of Subtree1 should always be preserved
|
|
revng_assert(PreservedNodes.contains(ToKeep.first));
|
|
|
|
return { true, PreservedNodes, ErasedNodes };
|
|
}
|
|
|
|
static auto getSuccEdgesToChild(LTSN *Parent, LTSN *Child) {
|
|
auto &Succ = Parent->Successors;
|
|
using IDBasedKey = std::pair<uint64_t, const TypeLinkTag *>;
|
|
return llvm::iterator_range(Succ.lower_bound(IDBasedKey{ Child->ID,
|
|
nullptr }),
|
|
Succ.upper_bound(IDBasedKey{ Child->ID + 1,
|
|
nullptr }));
|
|
}
|
|
|
|
bool DeduplicateFields::runOnTypeSystem(LayoutTypeSystem &TS) {
|
|
bool TypeSystemChanged = false;
|
|
if (VerifyLog.isEnabled())
|
|
revng_assert(TS.verifyDAG());
|
|
|
|
llvm::SmallPtrSet<LTSN *, 16> VisitedNodes;
|
|
|
|
for (LTSN *Root : llvm::nodes(&TS)) {
|
|
revng_assert(Root != nullptr);
|
|
if (not isRoot(Root))
|
|
continue;
|
|
|
|
llvm::SmallVector<LTSN *, 8> PostOrderFromRoot;
|
|
for (LTSN *N : post_order_ext(NonPointerFilterT(Root), VisitedNodes)) {
|
|
|
|
size_t NumInstanceEdges = 0;
|
|
|
|
for ([[maybe_unused]] const auto &Edge :
|
|
llvm::children_edges<NonPointerFilterT>(N))
|
|
++NumInstanceEdges;
|
|
|
|
if (NumInstanceEdges < 2)
|
|
continue;
|
|
|
|
revng_log(Log, "****** Node with many fields found: " << N->ID);
|
|
PostOrderFromRoot.push_back(N);
|
|
}
|
|
|
|
// Visit all nodes with fields in post-order. The post-order needs to be
|
|
// cached because children can be merged during traversal, which would
|
|
// invalidate iterators in llvm::post_order if we use it vanilla.
|
|
for (LTSN *NodeWithFields : PostOrderFromRoot) {
|
|
revng_log(Log,
|
|
"****** Try to dedup children of NodeWithFields with ID: "
|
|
<< NodeWithFields->ID);
|
|
|
|
llvm::SmallSetVector<LTSN *, 8> FieldsToCompare;
|
|
llvm::SmallSet<LTSN *, 8> OriginalFields;
|
|
llvm::SmallSetVector<LTSN *, 8> AnalyzedNodesNotMerged;
|
|
|
|
// We keep a separate list of successors since we might need to re-enqueue
|
|
// some of them.
|
|
revng_log(Log, "Children are:");
|
|
LoggerIndent TmpIndent{ Log };
|
|
for (const Link &L : NodeWithFields->Successors) {
|
|
revng_log(Log, L.first->ID);
|
|
FieldsToCompare.insert(L.first);
|
|
OriginalFields.insert(L.first);
|
|
}
|
|
|
|
bool NodeWithFieldsChanged = false;
|
|
while (FieldsToCompare.size() > 0) {
|
|
LTSN *CurChild = FieldsToCompare.pop_back_val();
|
|
|
|
LoggerIndent Indent{ Log };
|
|
revng_log(Log, "Consider CurChild: " << CurChild->ID);
|
|
|
|
// The CurChild can be connected to NodeWithFields with more than one
|
|
// edge, so consider them all when comparing CurChild with the
|
|
// AnalyzedNotMerged.
|
|
bool FieldsMerged = false;
|
|
auto CurChildEdges = getSuccEdgesToChild(NodeWithFields, CurChild);
|
|
revng_log(Log,
|
|
"There are "
|
|
<< std::distance(CurChildEdges.begin(), CurChildEdges.end())
|
|
<< " edges from " << NodeWithFields->ID << " to "
|
|
<< CurChild->ID);
|
|
for (auto &CurLink : CurChildEdges) {
|
|
|
|
LoggerIndent MoreIndent{ Log };
|
|
revng_log(Log, "Edge: " << *CurLink.second);
|
|
|
|
if (isPointerEdge(CurLink)) {
|
|
revng_log(Log, "skip pointer edge");
|
|
continue;
|
|
}
|
|
|
|
// We want to compare CurChild with all the other nodes that we have
|
|
// looked at in previous iterations, and try to merge it with one of
|
|
// them.
|
|
for (LTSN *NotMergedNode : AnalyzedNodesNotMerged) {
|
|
LoggerIndent MoreMoreIndent{ Log };
|
|
revng_log(Log,
|
|
"Try to merge: " << CurLink.first->ID << " with "
|
|
<< NotMergedNode->ID);
|
|
|
|
auto NotMergedEdges = getSuccEdgesToChild(NodeWithFields,
|
|
NotMergedNode);
|
|
revng_log(Log,
|
|
"There are " << std::distance(NotMergedEdges.begin(),
|
|
NotMergedEdges.end())
|
|
<< " edges from " << NodeWithFields->ID
|
|
<< " to " << NotMergedNode->ID);
|
|
|
|
bool AnalyzedNotMergedInvalidated = false;
|
|
for (const Link &NotMergedLink : NotMergedEdges) {
|
|
const auto &[NotMergedNode, NotMergedTag] = NotMergedLink;
|
|
|
|
LoggerIndent MoreMoreIndent{ Log };
|
|
revng_log(Log, "Edge to merge with: " << *NotMergedTag);
|
|
|
|
if (isPointerEdge(NotMergedLink)) {
|
|
revng_log(Log, "skip pointer edge");
|
|
}
|
|
|
|
auto &&[IsMerged,
|
|
Preserved,
|
|
Erased] = mergeIfTopologicallyEq(TS,
|
|
NotMergedLink,
|
|
CurLink);
|
|
if (not IsMerged) {
|
|
revng_log(Log, "Edge not merged!");
|
|
continue;
|
|
}
|
|
revng_log(Log, "Edge merged!");
|
|
|
|
// If we merged something, there should be at least one preserved
|
|
// node and one erased node
|
|
revng_assert(not Preserved.empty());
|
|
revng_assert(not Erased.empty());
|
|
|
|
// Check that the node that was meant to be preserved was actually
|
|
// preserved, and not erased.
|
|
// Notice that later collapseSingle can remove even more nodes.
|
|
// In principle we should add them to Erased and remove them
|
|
// from Preserved.
|
|
// However, in the remainder of the code below, both Preserved
|
|
// and Erased are only used to update FieldsToCompare and
|
|
// AnalyzedNodesNotMerged, and to set boolean flags to control
|
|
// iteration.
|
|
// Hence, we can get away without updating Preserved and Erased.
|
|
revng_assert(not Erased.contains(NotMergedNode));
|
|
revng_assert(Preserved.contains(NotMergedNode));
|
|
|
|
// This should always be true, since whenever we merge we are at
|
|
// least erasing CurChild, merging it with NotMergedNode.
|
|
FieldsMerged |= Erased.contains(CurChild);
|
|
revng_assert(FieldsMerged);
|
|
|
|
TypeSystemChanged = true;
|
|
NodeWithFieldsChanged = true;
|
|
|
|
// Collapse new single children that could emerge while merging.
|
|
// Copy the post_order into a SmallVector, since collapseSingle
|
|
// might mutate the graph and screw up the po_iterator.
|
|
for (auto &N : llvm::SmallVector<LTSN *>{
|
|
post_order(NonPointerFilterT(NotMergedNode)) })
|
|
CollapseSingleChild::collapseSingle(TS, N);
|
|
|
|
revng_log(Log, "The merge has erased the following nodes:");
|
|
for (auto &ErasedNode : Erased) {
|
|
LoggerIndent MoreMoreMoreIndent{ Log };
|
|
revng_log(Log, ErasedNode->ID);
|
|
// The ErasedNode has been deleted while merging, so we never
|
|
// want it to be processed again.
|
|
bool Erased = FieldsToCompare.remove(ErasedNode);
|
|
FieldsMerged |= Erased;
|
|
Erased = AnalyzedNodesNotMerged.remove(ErasedNode);
|
|
AnalyzedNotMergedInvalidated |= Erased;
|
|
}
|
|
|
|
revng_log(Log, "The merge has preserved the following nodes:");
|
|
for (LTSN *PreservedNode : Preserved) {
|
|
LoggerIndent MoreMoreMoreIndent{ Log };
|
|
revng_log(Log, PreservedNode->ID);
|
|
// The PreservedNode is preserved (not erased) by merge, but
|
|
// the merge process might have changed it.
|
|
// So, if it'a an original children of the NodeWithFields, we
|
|
// need to re-process it, hence we add it to FieldsToCompare,
|
|
// then set NodeWithFieldsChanged, and remove it from
|
|
// AnalyzedNodesNotMerged.
|
|
if (OriginalFields.contains(PreservedNode)) {
|
|
LoggerIndent MaxIndent{ Log };
|
|
revng_log(Log,
|
|
"Is an original field. Re-enqueue it for "
|
|
"comparison");
|
|
FieldsToCompare.insert(PreservedNode);
|
|
bool Erased = AnalyzedNodesNotMerged.remove(PreservedNode);
|
|
AnalyzedNotMergedInvalidated |= Erased;
|
|
}
|
|
}
|
|
|
|
// This should always be true, since whenever we merge we are at
|
|
// least preserving the NotMergedNode, which might have been
|
|
// changed by the merge.
|
|
revng_assert(AnalyzedNotMergedInvalidated);
|
|
|
|
// We have merged the CurChild into NotMergedNode, we have to
|
|
// brake out of all the loops looking at CurChild and at
|
|
// AnalyzedNodesNotMerged, since both of these might have
|
|
// changed.
|
|
break;
|
|
}
|
|
|
|
if (AnalyzedNotMergedInvalidated) {
|
|
// If we just merged CurChild into NotMergedNode we have
|
|
// invalidated the AnalyzedNodesNotMerged iterators.
|
|
// So we have to exit this loop and re-start iterating on
|
|
// FieldsToCompare.
|
|
break;
|
|
}
|
|
}
|
|
|
|
// If the children of the NodeWithFields have been changed by the
|
|
// merge, the CurChildEdges iterator ranges have been invalidated. So
|
|
// we have to break out of this loop as well.
|
|
if (FieldsMerged) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
// If we haven't merged CurChild with anything we can mark it as
|
|
// analyzed and not merged.
|
|
if (not FieldsMerged) {
|
|
AnalyzedNodesNotMerged.insert(CurChild);
|
|
revng_log(Log, "CurChild " << CurChild->ID << " not merged");
|
|
}
|
|
}
|
|
|
|
// Collapse the union node if we are left with only one member
|
|
if (NodeWithFieldsChanged) {
|
|
bool Changed = CollapseSingleChild::collapseSingle(TS, NodeWithFields);
|
|
TypeSystemChanged |= Changed;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (VerifyLog.isEnabled())
|
|
revng_assert(TS.verifyDAG());
|
|
|
|
return TypeSystemChanged;
|
|
}
|
|
|
|
} // end namespace dla
|