# Characterizing the Impact of Graph-Processing Workloads on Modern CPU’s
Cache Hierarchy

Alexandre Valentin Jamet12, Lluc Alvarez12, Marc Casas12 E-mail:
{alexandre.jamet, lluc.alvarez<EMAIL_ADDRESS>
1Barcelona Supercomputing Center, Barcelona, Spain  2Universitat Politècnica
de Catalunya, Barcelona, Spain

###### Index Terms:

cache management, cache bypassing, big data, graph processing, workload
evaluation, irregular workloads, micro-architecture

##  I Extended Abstract

In recent years, graph-processing has become an essential class of workloads
with applications in a rapidly growing number of fields. Graph-processing
typically uses large input sets, often in multi-gigabyte scale, and data-
dependent graph traversal methods exhibiting irregular memory access patterns.
Recent work [1] demonstrates that, due to the highly irregular memory access
patterns of data-dependent graph traversals, state-of-the-art graph-processing
workloads spend up to 80 % of the total execution time waiting for memory
accesses to be served by the DRAM. The vast disparity between the Last Level
Cache (LLC) and main memory latencies is a problem that has been addressed for
years in computer architecture. One of the prevailing approaches when it comes
to mitigating this performance gap between modern CPUs and DRAM is cache
replacement policies.

In this work, we characterize the challenges drawn by graph-processing
workloads and evaluate the most relevant cache replacement policies.

###  I-A Graph-processing Workloads

Graph-processing is a class of emerging workloads that, nowadays, can be found
in various applications. Graph-processing can be found in both industry and
academia, from social network analytics to web search engines and biomedical
applications.

Graph-processing typically uses sparse data formats such as Compressed Sparse
Row/Column (CSR/CSC) to manage a large amount of data. The CSR/CSC format is
used to encode the graph adjacency matrix using two data structures: 1) the
Offset Array (OA) and; 2) the Neighbours Array (NA). Finally, additional data
structures contain numerical data corresponding to a graph’s vertices called
Property Arrays (PA).

Manipulating these sparse data structures often produces irregular memory
access patterns. For example, when computing the Sparse Matrix-Vector (SpMV)
multiplication $y=A\cdot x$, accesses to vector $x$ are indexed by the column
indices of matrix $A$, which are non-contiguous and constitute an irregular
access stream. Graph-processing workloads also display highly irregular memory
access patterns driven by operations like graph traversals that require
visiting all the vertices $V$ of a graph, that is, scanning the adjacency
matrix rows following the graph’s connectivity.

Figure 1: Example of a graph representation in memory using the CSR/CSC
formats.

Figure 1 shows an example graph along with its adjacency matrix and its
representation using either the CSR or the CSC formats.

###  I-B Cache Replacement Policies

For this work, we evaluate six of the most relevant replacement policies for
the LLC. SRRIP, DRRIP [2] hahandleshe replacement process by predicting reuse
distances. SHiP [3] leverages SRRIP and extends it with the addition of a PC
feature. Hawkeye [4], Glider [5] a,nd MPPPB [6] further improve by making the
addition of machine learning inspired techniques (e.g.: perceptron, SVM,
etc.). Specifically, these advanced cache replacement policies leverage micro-
architectural features based on bits extracted from the program counters and
virtual/physical addresses to establish correlations and produce predictions.

###  I-C Experimental Setup

Our evaluation considers ChampSim, a detailed trace-based simulator that
models a Cascade Lake micro-architecture. The micro-architecture simulated has
only one core, L1 instruction, and data cache of 32KB each, an L2 cache of
1MB, and an L3 cache of 1.375MB. The system also includes an 8GB main memory
based on DDR4 SDRAM with a data rate of 2.933GT/s.

###  I-D Experimental results

Figure 2 shows the MPKI rates in all three cache hierarchy levels for
workloads of the GAP [7] benchmark suite. This figure shows that graph-
processing workloads suffer from a large number of misses at all levels of the
cache hierarchy. The average MPKI rates of these workloads in the L1D, L2C,
and LLC are 53.2, 44.2 and 41.8. We can further observe that a considerable
portion (78.6%) of the accesses that trigger L1D misses also miss in the lower
levels of the cache hierarchy and require a DRAM access.

Figure 2: Misses-Per-Kilo-Instruction (MPKI) across the different levels of
the cache hierarchy triggered by graph-processing workloads.

Cache replacement policy is an obvious topic when it comes to improving the
behavior of the cache hierarchy for certain types of workloads. As such, we
evaluated the replacement policies presented in I-B to understand their impact
on performance.

Figure 3 shows the geometric mean speed-up of the state-of-the-art cache
replacement policies evaluated over the baseline LRU policy for various
benchmark suites, including SPEC 2006 & 2017, along with the GAP workloads.
The results show that the different policies can catch different kinds of
access patterns and benefit different workloads.

Figure 3: Geometric mean speed-up over LRU of state-of-the-art LLC replacement
policies for the different benchmark suites.

These results show that more complex replacement policies such as Hawkeye,
Glider, and MPPPB have difficulties generalizing to benchmark suites beyond
SPEC 2006 & 2017\. This is due to the underlying assumptions on memory access
patterns used to build these complex cache replacement policies. As shown in
I-A, graph-processing is a prime example where the number of PC is very
limited and where each PC maps to a very large number of addresses making
correlations nearly impossible to establish.

###  I-E Conclusion

Overall, this work highlights the poor ability of state-of-the-art cache
replacement policies to leverage significant benefits against a baseline using
an LRU policy for graph-processing workloads, despite the very high hardware
complexity of such techniques. We show pieces of evidence that this bleak
outlook stems from two factors: i) the very distinct nature of graph-
processing workloads and; ii) the immense pressure these workloads create on
the cache hierarchy.

##  II Acknowledgment

This work has been published in Proceedings of the International Symposium on
Workload Characterization (IISWC), 2020 [8].

## References

  * [1] Y. Zhang, V. Kiriansky, C. Mendis, S. Amarasinghe, and M. Zaharia, “Making caches work for graph analytics,” in _2017 IEEE International Conference on Big Data (Big Data)_ , 2017, pp. 293–302.
  * [2] A. Jaleel, K. B. Theobald, S. C. S. Jr, and J. Emer, “High performance cache replacement using re-reference interval prediction (RRIP),” in _Proceedings of the 37th annual international symposium on Computer architecture_ , vol. ISCA’10. IEEE, pp. 60–71. [Online]. Available: https://dl.acm.org/citation.cfm?doid=1815961.1815971
  * [3] C.-J. Wu, A. Jaleel, W. Hasenplaugh, M. Martonosi, S. C. Steely, and J. Emer, “SHiP: signature-based hit predictor for high performance caching,” in _Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture - MICRO-44 ’11_. ACM Press, p. 430. [Online]. Available: http://dl.acm.org/citation.cfm?doid=2155620.2155671
  * [4] A. Jain and C. Lin, “Back to the future: Leveraging belady’s algorithm for improved cache replacement,” in _Proceedings of the 43rd International Symposium on Computer Architecture_ , ser. ISCA ’16. IEEE, pp. 78–89. [Online]. Available: https://dl.acm.org/citation.cfm?doid=3007787.3001146
  * [5] Z. Shi, X. Huang, A. Jain, and C. Lin, “Applying deep learning to the cache replacement problem,” in _Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture_. ACM, pp. 413–425. [Online]. Available: https://dl.acm.org/doi/10.1145/3352460.3358319
  * [6] D. A. Jiménez and E. Teran, “Multiperspective reuse prediction,” in _Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture - MICRO-50 ’17_ , ser. MICRO ’17. IEEE, pp. 436–448. [Online]. Available: http://dl.acm.org/citation.cfm?doid=3123939.3123942
  * [7] S. Beamer, K. Asanović, and D. Patterson, “The GAP benchmark suite.” [Online]. Available: http://arxiv.org/abs/1508.03619
  * [8] A. V. Jamet, L. Alvarez, D. A. Jiménez, and M. Casas, “Characterizing the impact of last-level cache replacement policies on big-data workloads,” in _2020 IEEE International Symposium on Workload Characterization (IISWC)_ , pp. 134–144. [Online]. Available: https://upcommons.upc.edu/bitstream/handle/2117/343622/IISWC20-paper.pdf?sequence=1

|  Alexandre Valentin Jamet studied two years of Higher School Preparatory
Classes with a Physics and Engineering Sciences major at LGT Baimbridge,
Guadeloupe. In the following years, he pursued his MSc degree in parallel with
an Engineer Diploma from TELECOM Nancy with a major in Embedded Computing. He
concluded his studies in Nancy in 2018. Since 2018, he has been a Ph.D.
candidate at the Computer Architecture departments of Barcelona Supercomputing
Center (BSC) and Universitat Politècnica de Catalunya (UPC), Spain.
---|---


# WizardMerge - Save Us From Merging Without Any Clues

Qingyu Zhang  The University of Hong KongHong KongChina<EMAIL_ADDRESS>,  Junzhe Li  The University of Hong KongHong KongChina<EMAIL_ADDRESS>,  Jiayi Lin  The University of Hong KongHong KongChina<EMAIL_ADDRESS>,  Jie Ding  The University of Hong KongHong KongChina
<EMAIL_ADDRESS>,  Lanteng Lin  Beijing University of Posts and
TelecommunicationsBeijingChina<EMAIL_ADDRESS>and  Chenxiong Qian  The
University of Hong KongHong KongChina<EMAIL_ADDRESS>
###### Abstract.

Modern software development necessitates efficient version-oriented
collaboration among developers. While Git is the most popular version control
system, it generates unsatisfactory version merging results due to textual-
based workflow, leading to potentially unexpected results in the merged
version of the project. Although numerous merging tools have been proposed for
improving merge results, developers remain struggling to resolve the conflicts
and fix incorrectly modified code without clues. We present WizardMerge, an
auxiliary tool that leverages merging results from Git to retrieve code block
dependency on text and LLVM-IR level and provide suggestions for developers to
resolve errors introduced by textual merging. Through the evaluation, we
subjected WizardMerge to testing on 227 conflicts within five large-scale
projects. The outcomes demonstrate that WizardMerge diminishes conflict
merging time costs, achieving a 23.85% reduction. Beyond addressing conflicts,
WizardMerge provides merging suggestions for over 70% of the code blocks
potentially affected by the conflicts. Notably, WizardMerge exhibits the
capability to identify conflict-unrelated code blocks that require manual
intervention yet are harmfully applied by Git during the merging.

Version control, Code merging, Static analysis

††ccs: Software and its engineering Software configuration management and
version control systems††ccs: Theory of computation Program analysis††ccs:
Software and its engineering Automated static analysis

##  1\. Introduction

As the most globally renowned version control system, Git (Git, 2023a) has
been helping with the development and maintenance of millions of projects. To
automatically merge the codes from two different versions, Git utilizes a
Three-way Merge Algorithm (Vinkler, 2023) as the default strategy on the text
level. The textual-based merging is general and suitable for various types of
text files and the merging tempo is proved to be the fastest. However, it
simply considers lines of code, neglecting all syntax and semantic
information, which leads to potential bugs in the merged version of the
project (Khurana, 2014; Spealman, 2018).

To mitigate the shortcomings of traditional textual-based merging, multiple
merging approaches (Zhu and He, 2018; Zhu et al., 2022; Apel et al., 2011;
Larsén et al., 2022; Shen et al., 2019; Sousa et al., 2018; Apel et al., 2012)
are proposed for enhancing the correctness of merging results. These tools can
be classified as Structured Merging and Semi-structured Merging. Structured
merging tools (Larsén et al., 2022; Zhu et al., 2022; Sousa et al., 2018; Zhu
and He, 2018) transform the code intended for merging into an Abstract Syntax
Tree (AST), thereby converting the code merging into the merging of edges and
nodes on the AST (Accioly et al., 2018). Semi-structured merging (Apel et al.,
2012, 2011; Shen et al., 2019), akin to structured merging, designates certain
semantically insensitive AST nodes (e.g., strings) as text, allowing them to
be directly processed by the text-based merging strategy during the merging
process (Cavalcanti et al., 2017).

Despite structured and semi-structured merging tools facilitating code
merging, challenges arise when it is unclear which version of the code should
take precedence. This uncertainty leads to merging conflicts. In the context
of large-scale software projects, conflicts can become a source of frustration
for developers, as they must dedicate significant effort to resolve the issues
that arise from merging before they can release the final merged version
(Ahmed et al., 2017; Nishimura and Maruyama, 2016). Addressing these conflict
resolutions has given rise to merging assistance systems. These systems are
designed with objectives such as selecting the most suitable developers to
resolve conflicts (Costa et al., 2016), prioritizing the resolution order for
conflicts (Shen et al., 2021), and even automatically generating alternative
conflict resolutions (Zhu and He, 2018). With the rapid advancements in
machine learning technologies in recent years, researchers have turned to
machine learning approaches (Zhang et al., 2022; Svyatkovskiy et al., 2022;
Elias et al., 2023; Dong et al., [n. d.]; Aldndni et al., 2023; Dinella et
al., 2022; Dong et al., 2023). These systems are trained using extensive
datasets containing merge conflict scenarios and can provide predictions on
the most suitable resolution strategy for each conflicting portion of code.

While these researches have made noteworthy contributions to code merging,
they still exhibit the following limitations. Firstly, structured (Apel et
al., 2012; Larsén et al., 2022; Zhu et al., 2022; Sousa et al., 2018; Zhu and
He, 2018) and semi-structured (Apel et al., 2011; Shen et al., 2019) still
generate conflicts when the direct merging between two AST noes failed, and
cannot assist developers in resolving them. Secondly, conflict resolution
assistance systems (Shen et al., 2021; Zhu and He, 2018; Costa et al., 2016)
focus solely on resolving conflicts, overlooking potential errors introduced
by incorrectly applied but conflict-free code. Though machine learning
approaches (Zhang et al., 2022; Svyatkovskiy et al., 2022; Elias et al., 2023;
Dong et al., [n. d.]; Aldndni et al., 2023; Dinella et al., 2022) can automate
conflict merging, the functionality of the resulting code may not ensure
alignment with developers’ expectations. Additionally, machine learning
methods necessitate specific code datasets for pre-training, which raises
universality issues when applied to more diverse code projects. Moreover, the
developers often have unpredictable operations on resolving conflicts, where
the auto-generated conflict resolution may fail to meet the expectations of
them.

To address these limitations, we introduce a novel approach aiming to aid
developers in handling complex code-merging scenarios. Recognizing that
developers have unpredictable ultimate needs, our approach focuses on grouping
conflicts by relevance and providing prioritized suggestions for resolving
conflicts rather than resolving them directly. Our approach also detects the
incorrectly applied codes as they can be easily neglected but cumbersome to
handle for developers. To realize these design goals, our approach requires a
thorough understanding of the dependency relations in the two merging
candidate versions. Firstly, we perform definition dependency graph
construction on LLVM Intermediate Representation (IR) (LLVM, 2024) and utilize
definition indicators extracted from Clang (Lattner, 2008) to indicate the
definition name and ranges in the source file. Following graph construction,
our approach analyzes the Git merge outcomes that present all the conflicts
and modified code blocks. Then, we align the definitions in the source file
with code snippets in Git’s outcomes to map from LLVM-IR to the Git merge
results. Given the dependency graph analysis and aligned Git merge results, we
further conduct an edge-sensitive algorithm to detect incorrectly applied
codes, which we deem as conflicts since they require developers’ attention as
well. Finally, we assign priorities to these conflicted nodes and produce
merging suggestions.

We implement a prototype WizardMerge for C/C++ projects as most large-scale
projects are written in C/C++ (Handy, 2023). We evaluate WizardMerge on 227
conflicts from five popular large projects. The outcomes demonstrate that
WizardMerge diminishes conflict merging time costs. Beyond addressing
conflicts, WizardMerge provides merging suggestions for most of the code
blocks affected by the conflicts. Moreover, WizardMerge exhibits the
capability to identify conflict-unrelated code blocks which should require
manual intervention yet automatically applied by Git.

In summary, we make the following contributions:

  * $\bullet$

We proposed a novel approach to infer the dependency between text-level code
blocks with modification.

  * $\bullet$

We proposed a remarkable methodology, which aims to pinpoint code blocks that
have been automatically applied by Git but introduce unexpected results.

  * $\bullet$

We implemented a code merging auxiliary prototype named WizardMerge based on
the approaches and evaluated the system on projects with large-scale code
bases. We will open source WizardMerge and evaluation datasets at
https://github.com/aa/bb.

##  2\. Background

###  2.1. Git Merging

Figure 1. Three-way merging workflow of Git.

Git is a free and open-source distributed version control system designed for
efficient handling of projects of all sizes (Git, 2023a). Git merge, as a key
operation, facilitates the integration of changes between versions and is
often used to consolidate code changes, bug fixes, or new features (Git,
2023b). Git supports multiple textual-based merging algorithms (Atlassian,
2022). Take the default and most commonly employed algorithm, Three-way
Merging Algorithm (Vinkler, 2023) as an example, the workflow is shown in
Figure 1. When the developer tries to merge two commits (i.e., $C_{3}$ Variant
A (VA) and $C_{5}$ Vairant B (VB) in Figure 1), Git first traverses the
commit-graph back until it reaches the nearest common ancestor commit (i.e.,
$C_{2}$, named Base). Then, all source code blocks of each newer version are
mapped to the corresponding code blocks in base versions, and the modified
code blocks of either VA or VB are regarded as Diff Code Blocks (DCBs). A DCB
in a variant may contain zero or multiple lines of code, indicating the
removal of an existing line or modification/addition of multiple continuous
lines. After the code matching stage, Git will iterate each code block tuple,
and determine which commit should be applied according to the following rules:

  * $\bullet$

If code blocks of VA and VB remain the same as the code block of Base, or both
of them are changed in the same way, inherit the code block from VA. In Figure
1, both VA and VB remove the definition of v4 (i.e., deleting line 4 of Base).
Due to identical modifications at the same locations, Git applies these
changes. It is noteworthy that even for code removal, VA and VB maintain a
pair of empty DCBs, symbolizing the deletion of lines.

  * $\bullet$

If only one code block of either VA or VB is changed, Git applies this code
block, and marks this code block and the corresponding code block in the other
variant as DCBs. In Figure 1, VA alters lines 1-2 and introduces a new line at
3. Git’s code-matching algorithm identifies these modifications, designating
lines 1-3 of VA as DCB 1 and lines 1-2 of VB as DCB 2. Since only DCB 1
changes, Git applies it to generate the code for the Merged Commit at lines
1-3.

  * $\bullet$

If both code blocks from VA and VB are changed, and the modifications are
different, Git marks both code blocks as DCBs. As Git cannot decide which one
should be applied, it emits a conflict containing the two DCBs. In Figure 1,
VA and VB independently modify the definition of v7. Git detects these
alterations, marking line 7 of VA as DCB 3 and line 6 of VB as DCB 4. Since
these two modifications differ, Git cannot determine which one to apply.
Consequently, Git signals the inconsistency between DCB 3 and DCB 4, prompting
developers to resolve this conflict.

Figure 2. An example of a clean but incorrect Git merge with the three-way
merging algorithm

###  2.2. Limitations of Existing Approaches

Despite being the most widely used code merging tool currently, Git merge
faces the following two challenges: (Challenge 1) It cannot ascertain
developers’ expectations for code functionality. Consequently, when both
versions modify the same code, Git treats this discrepancy as a conflict,
necessitating manual intervention for resolution. We discussed how the
conflicts are generated in §2.1. (Challenge 2) It cannot ensure the
correctness of successfully applied and conflict-free code blocks. Even when
Git successfully merges two versions without conflicts, the merged code may be
generated with new bugs. Figure 2 shows an incorrect merging scenario. Only
the first line of VA and the third line of VB are changed. Using Git merge,
the two versions of code can be easily merged without any conflict (i.e., the
first line applied from VA and the second line applied from VB).
Unfortunately, in the merged version, the definition of variable a has been
removed, which causes a compilation error at the third line. These DCBs
enforced by Git without conflict, yet resulting in unexpected results, are
termed Violated DCBs. Given that these violated DCBs are not flagged as
conflicts and are automatically incorporated by Git merge, they tend to
introduce concealed programming errors into the merged code. In the most
severe scenarios, these error-prone code segments might seemingly execute
successfully but could potentially give rise to security issues post-
deployment (Khurana, 2014; Spealman, 2018).

Over the years, researchers have concentrated on enhancing the quality of
merged code and conflict resolution. However, these two basic limitations have
not yet been fully resolved. On the one hand, structured (Zhu et al., 2022;
Larsén et al., 2022; Sousa et al., 2018; Zhu and He, 2018) and semi-structured
(Apel et al., 2012, 2011; Shen et al., 2019) merging still report conflicts
when the same AST node is modified simultaneously by two merging candidate
branches. On the other hand, the conflict resolution assistance system (Shen
et al., 2021; Zhu and He, 2018) and machine learning approaches (Zhang et al.,
2022; Svyatkovskiy et al., 2022; Elias et al., 2023; Dong et al., [n. d.];
Aldndni et al., 2023; Dinella et al., 2022; Dong et al., 2023) only consider
conflicts reported by the merge tool, ignoring all code snippets that have
been applied. Additionally, automatic software merging tools (Zhu et al.,
2022; Larsén et al., 2022; Sousa et al., 2018; Zhu and He, 2018; Apel et al.,
2012, 2011; Shen et al., 2019; Zhang et al., 2022; Svyatkovskiy et al., 2022;
Elias et al., 2023; Dong et al., [n. d.]; Aldndni et al., 2023; Dinella et
al., 2022; Dong et al., 2023) neglect an essential observation: developers
have unpredictable ultimate needs, therefore cannot fully overcome Challenge
1. To better illustrate this, we provide an example of implementing the
Fibonacci sequence in Figure 3. Two versions, A and B, calculate the Fibonacci
sequence using recursion and iteration, respectively. When attempting to merge
these versions, a conflict arises, and two developers resolve it. Although
both developers decide to use the iterative approach from version B to avoid
stack overflow for large values of $n$, they implement different strategies
for handling negative values of $n$. Developer A, inspired by version A, uses
an unsigned definition for $n$ to eliminate negative values (line 1 in
resolution A). In contrast, Developer B opts to return zero when $n$ is less
than zero (line 3 in resolution B). Since developers’ decisions on conflict
resolution are unpredictable, automatic software merging tools often fail to
produce an acceptable resolution in such cases.

Figure 3. An example of different resolutions to the same conflict

Furthermore, machine learning systems (Zhang et al., 2022; Svyatkovskiy et
al., 2022; Elias et al., 2023; Dong et al., [n. d.]; Aldndni et al., 2023;
Dinella et al., 2022; Dong et al., 2023) are limited in their ability to
resolve conflicts in large codebases due to input and output sequence
constraints. However, these conflicts typically do not significantly impact
developers’ time. For example, even MergeGen (Dong et al., 2023), the most
advanced system available, failed to achieve satisfactory results when applied
to the large-scale targets evaluated in §4. Upon completing MergeGen’s pre-
training, we discovered that it produced no correct outputs, achieving an
accuracy of 0%. This failure can be attributed to MergeGen’s default input and
output sequence length limitations of 500 and 200 BPE, respectively (Dong et
al., 2023). These limitations are excessively stringent for large-scale
project source code, leading to truncation of code beyond the prescribed
lengths. However, the end of the truncated code is usually far away from where
conflict occurs and MergeGen cannot master the ability to resolve the
conflicts given the trimmed training and testing sets. Attempts to relax these
length limitations are impractical due to increased GPU memory consumption
during training. Moreover, while machine learning techniques excel in
generating merge results, they may not always align perfectly with developers’
expectations. Although MergeGen’s evaluation results demonstrate superior
conflict code matching precision and accuracy on a line of code basis compared
to previous works (Dong et al., 2023), it still falls short of expectations in
some cases, with average precision and accuracy rates of 71.83% and 69.93%,
respectively.

##  3\. Design

Given the challenges outlined in the preceding section, we have identified two
key insights. Addressing Challenge 1, we recognize that the expected outcomes
of merges are subjective and open-ended. Consequently, our approach emphasizes
guiding developers in resolving conflicts rather than prescribing resolutions.
To tackle Challenge 2, it is imperative to analyze all modified code. To this
end, we present WizardMerge, a novel conflict resolution assistance system,
which provides developers with clues and aids in conflict resolution.
Moreover, WizardMerge emphasizes all modified code snippets, not just
conflicts, enabling it to uncover hidden discrepancies and preempt potential
errors. A detailed design of WizardMerge will be presented in the subsequent
subsections.

###  3.1. Overview

Figure 4. System overview of WizardMerge.

Figure 4 depicts the system overview of WizardMerge. WizardMerge first
consumes compilation metadata from the two merge candidates through LLVM(LLVM,
2024). WizardMerge employs LLVM based on two insights: i) For large projects,
code is compiled before a new version release to ensure compilation success,
allowing WizardMerge to collect metadata without introducing additional
merging steps; ii) LLVM Intermediate Representation (IR) provides a robust
static analysis framework and comprehensive debug information, facilitating
WizardMerge in performing definition dependency reasoning. To bridge LLVM IR
analysis with merge results from Git, the compilation metadata also
encompasses definition indicators. A definition indicator serves as the
representation of a named definition section at the source code level,
indicating the range and name of a definition. For example, a definition
indicator of a function records its function name, along with its start and
end line numbers in the source code file. Subsequently, To identify
relationships between all modified codes, WizardMerge advances to the
Dependency Graph Generation stage. Instead of focusing only on conflicts,
dependencies for all definitions are analyzed. WizardMerge creates vertices
for the definitions and establishes edges between vertices according to the
dependency relationships of definitions analyzed from LLVM IRs. Following
this, the Overall Dependency Graph (ODG) is generated to represent the
dependencies among all the definitions in both candidate versions of the
target project. To attach Git’s textual results with IR-level dependency
information, WizardMerge aligns Git merge’s results and ODG to match DCBs with
vertices in ODG through Graph-Text Alignment. This stage is capable of mapping
DCBs to the corresponding definition nodes in each ODG, refining definition
nodes into DCB nodes, and transforming definition dependencies into DCB
dependencies. To rectify errors introduced by Git merge, WizardMerge employs
an edge-sensitive algorithm in the Violated DCB Detection stage, detecting
both conflict-related and conflict-unrelated violated DCBs. These violated
DCBs and conflicts are categorized, prioritized based on the dependency graph,
and presented as suggestions to developers to assist in resolution.

###  3.2. Dependency Graph Generation

WizardMerge first constructs ODG based on the LLVM IR and definition
indicator. WizardMerge currently supports the following types of nodes and
edges:

Graph node. Subsequently, WizardMerge generates nodes for each named
definition with the corresponding indicator. Considering the types of
definitions, WizardMerge creates three types of nodes based on the indicator
information: Type Node (TN) represents composite types, e.g. structure, class,
type alias, and enumeration; Global Variable Node (GN) represents global
variable; Function Node (FN) represents function.

Graph edge. Each named definition may depend on other definitions within the
project. For instance, a function might utilize a global variable or return a
pointer with a specific structure type. In the ODG, these usage dependencies
among definitions are deduced from LLVM IRs and represented by the edges
linking one node to another. The types of edges are defined by the types of
their two connected nodes. An edge of type A-B represents a dependency from
node A to node B. In WizardMerge, five classifications of edges are supported:
TN-TN, GN-TN, FN-TN, FN-GN and FN-FN.

Note that WizardMerge will never generate an edge from TN to FN, even though
member functions may be defined within a composite type. Instead, WizardMerge
creates TN for all functions, irrespective of whether the function is
standalone or nested within another scope. If an FN represents a nested
function defined inside a composite type, an FN-TN edge is built to represent
the dependency from the function to the specific type.

###  3.3. Resolving Suggestion Generation

In this stage, WizardMerge extracts DCB information from Git merge to aid in
the analysis. Then, merging suggestions can be generated based on the analysis
results.

####  3.3.1. Graph-Text Alignment

The merge results cannot be directly linked to the corresponding node in ODG.
This is primarily because these results are raw texts that provide no
additional clues for program analysis. In the raw results, a single large DCB
may cover multiple nodes and a single node may encompass several DCBs. This
N-to-N relationship complicates the analysis of the graph.

Figure 5. Example alignment between node and DCB text.

WizardMerge initially associates each DCB with its corresponding definition
indicators. To identify all nodes contained in the file where the DCB is
situated, WizardMerge extracts the nodes whose range intersects with the DCB
range. If no matched node is found, it indicates that the DCB is not in a
definition (e.g., newlines or comments) and will not be further analyzed by
WizardMerge. Treating each DCB as a ”line segment”, its start and end line
numbers represent the coordinates of the line segment’s two endpoints on the
coordinate axis. Similarly, each definition indicator of a node is considered
as a unique ”color”. The range of each node signifies a specific coordinate
interval that is colored with the definition represented by the node. Thus,
retrieving the node during each DCB traversal can be seen as a color query for
the interval $[start\\_line,end\\_line]$, and interval modification and
information maintenance can be efficiently managed using line segment trees.
For a target project containing $N$ lines of code, each ”coloring” and ”color
query” operation can be achieved with a time complexity of $O(log_{2}N)$ (Cp-
Algorithms, 2023). WizardMerge subsequently logs all DCBs corresponding to
each node, organizing them in ascending order of line numbers. The node is
then subdivided into finer-grained nodes. The ranges of these finer-grained
nodes are updated concurrently based on the original node and their
corresponding unique DCBs. Fine-grained nodes belonging to the same definition
will be connected sequentially in range order, which implicitly expresses the
dependency between code blocks. This mechanism ensures that each node in ODG
aligns with at most one DCB, effectively preventing any matching confusion
within the ODG.

Taking Figure 5 as an instance, there are two definitions: Named Def 1, Named
Def 2. Before alignment, the nodes are created with their range information.
Let’s consider two DCBs associated with these definitions ($[L2,L5]$ and
$[L6,L7]$). To establish a one-to-one mapping between DCBs and nodes, each
node can be divided into multiple ones, while unaffected lines are excluded as
they do not influence the merging. For DCB $[L2,L5]$, WizardMerge detects that
$[L2,L3]$ belongs to Named Def 1 and $[L5,L5]$ belongs to Named Def 2.
Consequently, a new node starting from $L2$ to $L3$ will replace the original
node for Named Def 1. As $[L1,L1]$ remains unchanged, it will be discarded.
Furthermore, a new node from $L5$ to $L5$ is also formed since $[L6,L7]$,
representing another portion of Named Def 2, corresponds to the DCB $[L6,L7]$.
To indicate the code dependency from lines to previous lines within the same
definition, an additional edge from node $[L6,L7]$ to node $[L5,L5]$ is
established.

As WizardMerge is tasked with managing two code versions (VA and VB), some
nodes in the ODG of VA must possess a corresponding mirror node in the ODG of
VB. WizardMerge also constructs a mapping of each node to its matched node in
the other version’s ODG by matching the name of the definition and the DCB
metadata linked to the node. Note that if one node is aligned with a DCB, it
must have one unique mirror node with the other DCB in the same DCB pair. If
the node has a matched node, the matched node must be the mirror node and the
definition name is consistent with the current node. The matched node results
contribute to the violated DCB detection via dependency missing determination.
Besides, the ODG’s size can also be shrunk if there are nodes not attached to
any DCBs, which means they are not changed during merging. After the node
deletion, the newly generated graph is called Shrunk Dependency Graph (SDG).

####  3.3.2. Violated DCB Detection

Violated DCBs are the underlying cause of seemingly successful but erroneous
merging. To offer developers a comprehensive understanding of the merging
process, WizardMerge detects violated DCBs based on an edge-sensitive
algorithm and deems them as conflicts requiring resolution suggestions. Given
the SDGs and node matching relationship, WizardMerge traverses each edge in
the two versions of the SDG separately. Each edge, starting from $v$ and
ending at $u$, signifies that $v$ relies on $u$. WizardMerge determines which
version of the DCB associated with $u$ and $v$ is ultimately applied in the
merge results (i.e., from VA, VB, or conflict). WizardMerge then ascertains
whether these nodes represent violated DCBs by the applied versions and
matching nodes of $u$ and $v$. We introduce all the safe (i.e. not violated
DCBs detected) and violated scenarios as follows.

##### Symbols Definition

Let the SDGs from VA and VB be represented as $G_{A}=\ <V(G_{A}),E(G_{A})>$
and $G_{B}=\ <V(G_{B}),E(G_{B})>$, where $V$ indicates the vertices set and
$E$ indicates the edges set. For each vertex $v\in V$, we represent its mirror
node as $Mi(v)$ and use $match(Mi(v))$ to indicate whether the mirror node of
$v$ is a matching node ($True$ or $False$). $v$ belongs to only one of the
$V_{N}$, $V_{A}$, and $V_{C}$ vertex sets, representing not applied, applied,
and conflict node sets respectively. For each edge $e(v,u)\in E$, it
represents an edge from $v$ to $u$, indicating $v$’s dependency on $u$.
According to the construction principles of SDG, there are two basic facts:

  * $\bullet$

If $v\in V_{A}$, then $Mi(v)\in V_{N}$, and vice versa.

  * $\bullet$

If $v\in V_{C}$, then $Mi(v)\in V_{C}$.

As each $v\in V_{A}$ must indicate another vertex (i.e., $Mi(v)$) belongs to
$V_{N}$, WizardMerge only analyzes the cases where $v\in V_{A}$ or $v\in
V_{C}$ to avoid duplicate traversal.

##### Safe Scenarios

For each $v$ and an edge $e=(v,u)$, we define the scenarios satisfying any of
the following four formulas as safe:

(1) $v\in V_{A},u\in V_{A}$ (2) $v\in V_{A},u\notin V_{A},match(Mi(u))=True$
(3) $v\in V_{C},u\in V_{A}$ (4) $v\in V_{C},u\notin V_{A},match(Mi(u))=True$

In SDGs, the above formulas can be regarded as an edge-sensitive detection
algorithm, which is visiualized as depicted in Figure 6. For Equation 1, if
both $u$ and $v$ are applied, it means the dependency relation between nodes
within the same SDG (as shown in Scenario 1 of Figure 6). By the same token,
Scenario 3 also illustrates such a direct dependency represented by Equation
3. For Equation 2 (Scenario 2 in Figure 6), $v$ is applied but $u$ is either
not applied ($u\in V_{N}$) or in conflict status ($u\in V_{C}$). Nevertheless,
if the mirror of $u$ matches $u$ ($match(Mi(u))=True$), it means that at least
in the other SDG, $v$ can find its corresponding dependency applied (i.e.,
$Mi(u)$) although $u$ is not applied, or both versions of conflicted $u$ hold
the same dependency for $v$. To this end, WizardMerge uses a virtual
dependency edge from $v$ to $Mi(u)$ to indicate a cross dependency between
nodes from different SDGs. Similarly, Equation 4 (Scenario 4) is also regarded
as safe with the same reason.

Figure 6. Edge traversal scenarios visualization

##### Violated Scenarios

For each $v$ and an edge $e=(v,u)$, all the scenarios not detected as safe are
regarded as violated scenarios. These scenarios are:

(5) $v\in V_{A},u\notin V_{A},match(Mi(u))=False$ (6) $v\in V_{C},u\notin
V_{A},match(Mi(u))=False$

The Scenario 5 and Scenario 6 in Figure 6 visualize Equation 5 and Equation 6
respectively. Once $u$ is not applied or in conflict, and the mirror node of
$u$ does not match it ($match(Mi(u))=False$), it means that $v$ misses
dependency from $u$ in both SDGs (when $u\in V_{N}$), or $Mi(u)$ holds a
different dependency from $u$, which does not match $v$’s requirement (when
$u\in V_{C}$).

WizardMerge identifies these cases are incorrectly handled by Git merge and
marks the corresponding $v$, $u$, $Mi(v)$ and $Mi(u)$ as violated. Note that
vertices with conflicts are always treated as violated, regardless of whether
they are encountered in safe or violated scenarios. Finally, the DCBs attached
to these vertices are also marked as violated.

Figure 7. MDG example. Each node in MDG contains exactly a pair of mirror
nodes in SDG. Each edge is built if there is at least one SDG edge from one
SDG node to another.

####  3.3.3. Priority-Oriented Classification

WizardMerge further minimizes the number of nodes that require processing and
constructs a Minimum Dependency Graph (MDG) to emulate the dependencies of the
merged version of code. In the MDG, each node will consist of either an
applied node or a conflict node and its matching node, and the edges between
nodes will be created based on various SDGs according to the applying status.
Specifically, while establishing the MDG, WizardMerge will traverse each
conflict node or node associated with violated DCBs, and based on the applying
status of the node, it will switch to the corresponding version of SDG and
continue traversing the nodes in that particular SDG. Particularly, if the
node is in conflict status, then the outcoming edges of both the mirror of the
node and itself would be iterated. Concurrently, WizardMerge sets up a
directed edge between corresponding nodes for the MDG, relying on the
encountered edges during traversal. Ultimately, the MDG encapsulates the
essential dependencies of the two versions of code to be merged.

Figure 7 shows an instance illustrating how MDG is built from SDG. Each MDG
node is created from a pair of nodes related to conflict or violated DCBs. SDG
node A-E are from VA and all Mirror nodes are from VB. Starting from A and its
mirror, WizardMerge iterates the outcoming edges and finds B is linked to a
violated DCB. Then, WizardMerge creates a new node MDG_Node_B containing B and
its mirror. As B is not applied while its mirror node is applied, WizardMerge
iterates the outcoming edges of the mirror of B and finds a pair of conflict
nodes (i.e., E and Mirror), which forms MDG_Node_E. WizardMerge then iterates
the outcoming edges of both B and Mirror because of the conflict. By the same
token, MDG_Node_D and MDG_Node_C are created.

WizardMerge then employs the Tarjan algorithm (Tarjan, 1972) to condense the
MDG nodes and eliminate cycles. During this process, nodes in the same
strongly connected component are regarded as having identical priority, as
these nodes may reference each other within the code. In the case of the
directed acyclic MDG, WizardMerge divides the MDG into multiple subgraphs
based on connectivity. All nodes within each subgraph are grouped, and each
node is assigned a priority through the topological sorting of the subgraph.
Nodes that appear later in the topological order signify that other nodes have
greater dependencies on them, while the nodes themselves have fewer
dependencies. Consequently, these nodes are assigned higher priority, enabling
developers to address them earlier. In Figure 7, MDG_Node_C, MDG_Node_D and
MDG_Node_E are in the same cyclic of MDG and are thus assigned the same
resolution priority as they depend on each other. After calculating the
topological order, WizardMerge suggests that the DCB resolution priority
should be {MDG_Node_C, MDG_Node_D, MDG_Node_E}, {MDG_Node_B} and {MDG_Node_A}.

##  4\. Evaluation

In this section, we evaluate the effectiveness of WizardMerge, aiming to
answer the following research questions:

  * $\bullet$

RQ1:  Can WizardMerge help reduce the time consumption of merging conflicts?

  * $\bullet$

RQ2:  Can WizardMerge detect violated DCBs related to conflicts applied by
Git?

  * $\bullet$

RQ3:  Can WizardMerge detect violated DCBs unrelated to conflicts applied by
Git?

Dataset Collection. We choose Firefox (Mozilla, 2023), Linux Kernel (Torvalds,
2023), MySQL (MySQL, 2024), PHP (MySQL, 2024), and LLVM (LLVM, 2024) as the
target projects because of their widespread usage as open-source software.
Additionally, they boast extensive code bases and are maintained by multiple
developers, resulting in repositories that feature intricate commits and
merging scenarios. We collect 22 conflict pairs from Firefox, 43 from Linux
Kernel, 17 from LLVM, 46 from PHP, and 99 from MySQL with a committing
timeframe from 2021 to 2024. For each pair of conflicts, we only focus on the
files in C/C++ format and guarantee they either have at least five conflict
regions or violated DCBs detected. On average, a conflict contains 824.33
lines of codes and is related to 6.8 files.

Evaluate with State-of-the-art (SOTA) Systems. We initially intended to assess
WizardMerge alongside other cutting-edge systems. However, JDIME (Apel et al.,
2012), Mastery (Zhu et al., 2022), Spork (Larsén et al., 2022), SafeMerge
(Sousa et al., 2018), AutoMerge (Zhu and He, 2018), IntelliMerge (Shen et al.,
2019) and SoManyConflicts (Shen et al., 2021) encountered language
incompatibility issues within our datasets. Besides, migrating WizardMerge to
the languages these systems support is impractical because as an LLVM-based
project, WizardMerge requires the full support from the LLVM framework, while
the compiler front ends of Java (Stepanov, 2020), Typescript (ApsarasX, 2021),
and Javascript (ApsarasX, 2021) are still under development. Furthermore,
FSTMerge(Apel et al., 2011) purports scalability contingent upon users
implementing the merging engine for specific languages. Unfortunately, its
C/C++ parsers are either underdeveloped (i.e., accommodating only basic
syntax) or unimplemented, rendering it unsuitable for real-world projects. In
addition, as mentioned in § 2.2, the machine learning approaches (Zhang et
al., 2022; Svyatkovskiy et al., 2022; Elias et al., 2023; Dong et al., [n.
d.]; Aldndni et al., 2023; Dinella et al., 2022; Dong et al., 2023) meet the
sequence length limitation challenge when facing the large-scale targets we
chose.

Evaluation Environment. We evaluated WizardMerge on an AMD EPYC 7713P server
with 64/128 cores/threads, NVIDIA GeForce RTX 4090 (24GB GPU memory), and
256GB memory, running Ubuntu 20.04 with kernel 5.4.0.

###  4.1. Effectiveness on Conflict Resolution

To address RQ1, we conducted a comparative analysis of the time consumption
associated with two distinct approaches (Git merge w/ and w/o WizardMerge) for
merging conflict pairs. As WizardMerge only provides suggestions instead of
resolutions of conflicts, We have to assign two types of technical staff to
the manual merging phase: skilled staffs, researchers with deep understanding
of the project, and ordinary staffs, researchers having general understanding
of the project. Initially, the ordinary staff employed WizardMerge to analyze
the two versions and performed the merge utilizing the suggestions provided by
WizardMerge. Subsequently, the skilled staff manually merged the two candidate
versions using Git merge without any additional assistance. We meticulously
recorded the number of conflicts that can be analyzed by WizardMerge and the
time taken (with precision to the minute) from the commencement of conflict
analysis to their complete resolution.

Table 1. Conflict coverage of WizardMerge. Total Num indicates the total number of conflicts in each dataset. Analyzed Num indicates the number of conflicts successfully analyzed by WizardMerge. Cover Rate indicates the ratio of the above two columns. Dataset | Analyzed Num |  Total Num | Cover Rate
---|---|---|---
Firefox | 159 |  160 | 99.38%
Linux Kernel | 75 |  88 | 85.23%
LLVM | 71 |  72 | 96.61%
PHP | 236 |  255 | 92.55%
MySQL | 797 |  964 | 82.68%

Before comparing the effectiveness of merging w/ and w/o WizardMerge, we first
evaluate its ability to assess conflicts. As shown in Table 1, we calculated
the total number of conflicts for each dataset and recorded how many conflicts
can be successfully analyzed by WizardMerge. WizardMerge can give suggestions
of more than 80% conflicts from the five targets. Notice that some conflicts
cannot be handled by WizardMerge, we manually dig the reasons behind the
failure. In the design section, we mentioned that WizardMerge’s analysis is
based on LLVM IR. However, in textual merging results, some conflicts are
caused by the content of comments or preprocessing instructions (e.g.,
#include and macro definition). Since comments do not belong to the code
scope, and the preprocessing instructions will be expanded in the Clang front
end, LLVM IR will lose the text information of these conflicts, and finally
WizardMerge will not give suggestions related to them.

Figure 8. Manual merging time w/ and w/o WizardMerge.

The effectiveness of merging w/ and w/o WizardMerge is quantified by time
consumption and is shown in Figure 8. When the time consumption of merging a
pair of commits exceeds 70 minutes, we will mark it as ”$>70$” and stop
resolving it. In 135 out of 277 conflict scenarios, WizardMerge contributes to
reducing version conflict resolution time, and as the time consumption w/o
WizardMerge increases, the assistance ability of WizardMerge also becomes more
obvious. Remarkably, for the 205th conflict pair, manual merging w/o
WizardMerge costs more than 70 minutes, while with the help of WizardMerge,
the merging process can be finished in 35 minutes. This exceptional
performance is attributed to the Priority-Oriented Classification module in
WizardMerge, which provides categorization and fixes priority recommendations
for manually resolved code blocks. Simultaneously, the Violated DCB Detection
module in WizardMerge automatically identifies code blocks related to
conflicts. This feature simplifies developers’ efforts in analyzing
dependencies and avoids the substantial time spent on the manual in-depth
exploration of extensive code space required by Git merge. However,
WizardMerge may not optimize the time consumption for all data points. In 18
out of 277 conflict cases, using WizardMerge could even increase the burden of
conflict resolution. This occurs when only a small number of conflicts are
present and few code blocks are affected, rendering WizardMerge’s assistance
not substantial. Additionally, as mentioned above, WizardMerge fails to
generate suggestions on comments or preprocessing instructions.

Listing 1: Case study for conflict & violated DCB classification and
WizardMerge-produced resolving order assignment.

⬇

1diff \--git a/gfx/layers/ScrollbarData.h b/gfx/layers/ScrollbarData.h

2\--- b/gfx/layers/ScrollbarData.h

3+++ a/gfx/layers/ScrollbarData.h

4@@ +38,10 -38,9 @@ struct ScrollbarData

5 * This constructor is for Thumb layer type.

6 */

7 ScrollbarData(ScrollDirection aDirection, float aThumbRatio,

8<<<<<<< HEAD

9+ OuterCSSCoord aThumbStart, OuterCSSCoord aThumbLength,

10+ OuterCSSCoord aThumbMinLength, bool aThumbIsAsyncDraggable,

11+ OuterCSSCoord aScrollTrackStart,

12+ OuterCSSCoord aScrollTrackLength, uint64_t aTargetViewId)

13=======

14- CSSCoord aThumbStart, CSSCoord aThumbLength,

15- bool aThumbIsAsyncDraggable, CSSCoord aScrollTrackStart,

16- CSSCoord aScrollTrackLength, uint64_t aTargetViewId)

17>>>>>>> 281943a7a7564da09bd6076cac0c47a7a62144dc

18 : mDirection(Some(aDirection)),

19 mScrollbarLayerType(ScrollbarLayerType::Thumb),

20 mThumbRatio(aThumbRatio),

21@@ +65,16 -63,16 @@

22 public:

23 ScrollbarData() = default;

24

25<<<<<<< HEAD

26+ static ScrollbarData CreateForThumb(

27+ ScrollDirection aDirection, float aThumbRatio,

28+ OuterCSSCoord aThumbStart,

29+ OuterCSSCoord aThumbLength, OuterCSSCoord aThumbMinLength,

30+ bool aThumbIsAsyncDraggable,

31+ OuterCSSCoord aScrollTrackStart,

32+ OuterCSSCoord aScrollTrackLength, uint64_t aTargetViewId) {

33=======

34- static ScrollbarData CreateForThumb(ScrollDirection aDirection,

35- float aThumbRatio, CSSCoord aThumbStart,

36- CSSCoord aThumbLength,

37- bool aThumbIsAsyncDraggable,

38- CSSCoord aScrollTrackStart,

39- CSSCoord aScrollTrackLength,

40- uint64_t aTargetViewId) {

41>>>>>>> 281943a7a7564da09bd6076cac0c47a7a62144dc

42 return ScrollbarData(aDirection, aThumbRatio, aThumbStart, aThumbLength,

43+ aThumbMinLength, aThumbIsAsyncDraggable,

44+ aScrollTrackStart, aScrollTrackLength, aTargetViewId);

45- aThumbIsAsyncDraggable, aScrollTrackStart,

46- aScrollTrackLength, aTargetViewId);

47 }

48

49@@ MergeGuardian Result

50@@ Group 0:

51@@ |

52@@ C-- ScrollbarData xxx/ScrollbarData.h 41-44, 41-43

53@@ |

54@@ C-- CreateForThumb xxx/ScrollbarData.h 68-74, 66-72

55@@ |

56@@ A-- CreateForThumb xxx/ScrollbarData.h 76-77

57@@ |

58@@ B-- (applied) CreateForThumb xxx/ScrollbarData.h 74-75

1 presents a case study illustrating how WizardMerge classifies the conflicts
and violated DCBs and assigns resolving privileges between VA 145d3f6 and VB
281943a. Initially, both versions introduce distinct modifications to the
ScrollbarData constructor, resulting in a merge conflict (lines 8-17).
Subsequently, both versions make different alterations to the parameter types
of the CreateForThumb method in the ScrollbarData class, leading to another
merge conflict (lines 25-41). However, Git’s strategy reports these conflicts
directly to the developer without providing additional clues. In contrast,
WizardMerge utilizes dependency analysis between definitions to discern that
the constructor of ScrollbarData will be called by CreateForThumb (line 42).
Consequently, WizardMerge classifies the two conflicts into one group,
assigning higher fix priority to lines 8-17 than to lines 25-41.

Additionally, VA and VB present diverse implementations of the function body
of the CreateForThumb method. According to the three-way merging algorithm,
Git applied the code snippets from VB (lines 45-46) after detecting these two
conflicts. Moreover, within the pair of DCBs represented by lines 43-46,
although lines 45-46 are applied without conflicts, it cannot ensure the
constructor of ScrollbarData receives the correct parameter types when both
conflicts are present. This is because, if the developer chooses to apply all
VA modifications when resolving these conflicts, the applied lines 45-46 from
VB will lack essential parameters, aThumbMinLength and aThumbIsAsyncDraggabl,
used by ScrollbarData constructor and the types of aThumbStart, aThumbLength,
aScrollTrackStart, and aScrollTrackLength will not match the ScrollbarData
constructor prototype. Nevertheless, WizardMerge detects lines 45-46 and its
mirror DCB (i.e., lines 43-44) through its innovative dependency analysis
approach, treating them as violated DCBs. It reports them to developers along
with other conflicts. Since lines 43-46 depend not only on lines 8-17
(function call) but also on lines 25-41 (definition of prototype), these two
violated DCBs are grouped with the previous two conflicts, with fixed priority
coming after the two conflicts. The resolution suggestions provided by
WizardMerge are shown in lines 49-58 of 1, where items prefixed with C
indicate pairs of DCBs with conflicts, and items prefixed with A or B indicate
DCBs from VA or VB considered as violated DCBs.

Conclusion: Our evaluation confirms WizardMerge can give suggestions for
72.45% of the conflicts. We analyze the time expenditures associated with
conflict resolution and their corresponding DCBs w/ and w/o the utilization of
WizardMerge to answering RQ1. On average, WizardMerge demonstrates a 23.85%
reduction in resolution time. This underscores the efficiency and practicality
of WizardMerge in facilitating conflict resolution, even in the context of
large-scale real-world software.

Table 2. Violated DCB detection records. CR VA represents the LoC of CR violated DCB in VA, and CR VB represents the LoC of CR violated DCB in VB. The format $n/m$ indicates that there are $m$ LoCs in total, of which WizardMerge detects $n$. Similarly, CU VA represents the LoC of CU violated DCB in VA, and CU VB represents the LoC of CU violated DCB in VB. The format $n/m$ indicates that WizardMerge detect $m$ LoCs as CU violated DCB, of which $n$ are confirmed. Recall and Precision with $\dagger$ and $\ddagger$ stand for VA and VB respectively. Dataset | CR-VA |  CR-VB | CU-VA | CU-VB | Recall$\dagger$ | Recall$\ddagger$ | Precision$\dagger$ | Precision$\ddagger$
---|---|---|---|---|---|---|---|---
Firefox | 151/174 |  112/123 | 75/652 | 98/717 | 88.30% | 91.06% | 11.50% | 13.67%
Linux Kernel | 107/131 |  156/192 | 171/1245 | 105/905 | 81.68% | 81.25% | 13.73% | 11.60%
LLVM | 212/316 |  16/23 | N/A | N/A | 67.09% | 69.57% | N/A | N/A
PHP | 92/132 |  49/139 | 226/324 | 213/358 | 69.70% | 35.25% | 69.75% | 59.50%
MySQL | 12274/13100 |  3171/3469 | 1750/4597 | 1307/2427 | 93.69% | 91.41% | 38.07% | 53.85%

###  4.2. Violated DCB Detection

To address both RQ2 and RQ3, our initial step involves establishing the ground
truth regarding the number of violated DCBs by manually merging two code
versions using Git merge. Subsequently, we employ WizardMerge to conduct an
analysis and document the identified violated DCBs. As not all code segments
within a DCB pertain to violated DCBs, we utilize Line of Code (LoC) for
careful quantification of the violated DCBs. These violated DCBs are further
categorized into Conflict-Related (CR) and Conflict-Unrelated (CU) violated
DCBs.

####  4.2.1. Conflict-Related Violated DCBs

In addition to addressing conflict DCBs, developers should reassess the DCBs
automatically applied by Git merge. Resolving one conflict might potentially
impact other sets of DCBs. Throughout our evaluation, we recorded the LoC for
DCBs linked to conflicts in both versions. This data reflects WizardMerge’s
capability in elucidating the correlation between conflicts and violated DCBs.

Table 2 illustrates the CR-violated DCB detection results of WizardMerge. As
VA and VB’s codes are different, the LoC of CR-violated DCBs in the same diff
pair may vary as well. Thus, we documented the LoC from both VA and VB.
According to the evaluation, 167 out of 227 conflict scenarios are confirmed
to contain CR-violated DCBs. For most of the targets, WizardMerge successfully
detected more than 60% CR-violated DCBs, providing a promising assistive cue
for developers in executing manual fixes and facilitating them in exploring
the CR-violated DCBs. Noticeably, although MySQL datasets have the most LoC of
CR-violated DCBs, WizardMerge’s detection recall even reaches 93.69%. For LLVM
and PHP, WizardMerge showed moderate recalls.

We also delved into the reasons behind WizardMerge’s inability to detect CR-
violated DCBs in certain datasets. Firstly, the Linux Kernel encountered
compilation failure with the ”O0” option, a crucial setting for preserving
debug information and preventing code optimization. Although ”Og” can be used
for better debug ability, it is akin to ”O1,” resulting in the elimination of
significant debug information (Du, 2018). For instance, inlined functions are
inserted at the invocation location and subsequently removed from the original
code. As WizardMerge depends on the collaboration of debug information and
LLVM IR, the absence of debug information leads to the failure of node
generation and DCB matching. Secondly, some datasets include violated
dependencies among local variables within a specific function or macro
definition, which WizardMerge’s analysis currently does not support.

Listing 2: Case study for conflict-related violated DCBs

⬇

1diff \--git a/drivers/net/virtio_net.c b/drivers/net/virtio_net.c

2\--- b/drivers/net/virtio_net.c

3+++ a/drivers/net/virtio_net.c

4@@ -126,12 +127,9 @@ struct virtnet_stat_desc virtnet_rq_stats_desc[] = {

5 #define VIRTNET_SQ_STATS_LEN ARRAY_SIZE(virtnet_sq_stats_desc)

6 #define VIRTNET_RQ_STATS_LEN ARRAY_SIZE(virtnet_rq_stats_desc)

7

8<<<<<<< 5c5e0e81202667f9c052edb99699818363b19129

9- struct virtnet_rq_dma {

10- dma_addr_t addr;

11- u32 ref;

12- u16 len;

13- u16 need_sync;

14=======

15+ struct virtnet_interrupt_coalesce {

16+ u32 max_packets;

17+ u32 max_usecs;

18>>>>>>> 1acfe2c1225899eab5ab724c91b7e1eb2881b9ab

19 };

20@@ -147,6 +145,8 @@ struct send_queue {

21

22 struct virtnet_sq_stats stats;

23

24+ struct virtnet_interrupt_coalesce intr_coal;

25

26 struct napi_struct napi;

27@@ -164,6 +164,8 @@ struct receive_queue {

28

29 struct virtnet_rq_stats stats;

30

31+ struct virtnet_interrupt_coalesce intr_coal;

32

33 /* Chain pages by the private ptr. */

34@@ -185,12 +187,6 @@ struct receive_queue {

35 struct xdp_rxq_info xdp_rxq;

36

37- /* Record the last dma info to free ... */

38- struct virtnet_rq_dma *last_dma;

39- /* Do dma by self */

40- bool do_dma;

41 };

42@@ -295,10 +292,8 @@ struct virtnet_info {

43 u32 speed;

44

45 /* Interrupt coalescing settings */

46- u32 tx_usecs;

47- u32 rx_usecs;

48- u32 tx_max_packets;

49- u32 rx_max_packets;

50+ struct virtnet_interrupt_coalesce intr_coal_tx;

51+ struct virtnet_interrupt_coalesce intr_coal_rx;

2 presents an intriguing case study revealing conflict-related violated DCBs
detected by WizardMerge between VA 5c5e0e8 and VB 1acfe2c. In VA, the
definition for virtnet_rq_dma is present, whereas at the same position in VB,
virtnet_interrupt_coalesce is defined. Git identifies these versions’
different modifications as a conflict and prompts manual resolution for
developers. Subsequently, Git designates other DCBs as not in conflict and
applies them based on their consistency with the base version’s DCBs.
Eventually, the code snippets from lines 24, 31, and 50-51 (from VA) along
with 37-40 (from VB) are applied. Despite the differences between VA and VB in
lines 46-51, lines 46-49 from VB are consistent with the base version’s
snippets. According to the three-way merging strategy, Git prefers to apply
lines 50-51 from VA. In contrast, WizardMerge analyzes all modified code and
discovers that even though the conflict is highlighted, some related DCBs have
been applied without alerting the developers. For instance, applying lines
37-40 from VB assumes the presence of struct virtnet_rq_dma. Yet, if the
developer opts for lines 15-17 as the conflict resolution, the structure
becomes undefined within that context. Similarly, applying lines 24, 31, and
50-51 from VA assumes the definition of struct virtnet_interrupt_coalesce,
while they will cause compilation errors if the developer chooses lines 9-13
as the conflict resolution. Consequently, WizardMerge identifies these code
snippets as violated DCBs in conjunction with the conflict. Furthermore,
WizardMerge assigns higher priority to the conflict, signifying the dependency
of other DCBs on the conflict and suggesting developers resolve the conflict
before reconsidering these violated DCBs.

####  4.2.2. Conflict-Unrelated Violated DCBs

Throughout this evaluation, we document the LoC for DCBs unrelated to
conflicts in both variant versions reported by WizardMerge. Following this, we
manually inspected the identified DCBs and calculated the number of LoC
genuinely violated among them.

The results of WizardMerge’s detection of CU-violated DCBs are also presented
in Table 2. As CU-violated DCBs are isolated from conflicts, WizardMerge
demonstrates the capability to detect them, even in scenarios where it fails
to handle any conflicts. In total, WizardMerge detected CU-violated DCBs in
137 out of 227 conflict scenarios, while no CU-violated DCBs were found in
LLVM. These DCBs, lacking necessary dependent definitions and automatically
applied by Git merge without developer notification, do not lead to conflicts
but can result in compile errors or even latent bugs affecting users at
runtime. While WizardMerge showcases its potential in uncovering violated
dependency issues, the evaluation also highlights instances of false positive
CU-violated DCBs. This arises from the lack of function body analysis in
WizardMerge. According to WizardMerge’s DCB detection algorithm §3.3.2, the
relationship between two DCBs from the same function relies on line numbers,
with the latter one forcibly dependent on the former one. If the two DCBs are
applied from different versions, WizardMerge marks them as CU-violated DCBs,
even if they are unrelated. This conservative algorithm may result in more
false positives, but WizardMerge prioritizes its application to prevent
overlooking the detection of CU-violated DCBs.

Listing 3: The definitions of function EnsureNSSInitializedChromeOrContent are
the same in both versions

⬇

1// security/manager/ssl/nsNSSComponent.cpp

2bool EnsureNSSInitializedChromeOrContent() {

3 ...

4 if (XRE_IsParentProcess()) {

5 // Create nsISupports * via template class nsCOMPtr.

6 nsCOMPtr<nsISupports> nss =

7 do_GetService(PSM_COMPONENT_CONTRACTID);

8 if (!nss) {

9 return false;

10 }

11 initialized = true;

12 return true;

13 }

14 ...

15}

Listing 4: Difference between commits d2956560d539 and a20620423a53 in file
xpcom/base/nsCOMPtr.h

⬇

1diff \--git a/xpcom/base/nsCOMPtr.h b/xpcom/base/nsCOMPtr.h

2\--- a/xpcom/base/nsCOMPtr.h

3+++ b/xpcom/base/nsCOMPtr.h

4template <class T>

5class MOZ_IS_REFPTR nsCOMPtr final {

6 ...

7};

8

9...

10

11+ template <>

12+ class MOZ_IS_REFPTR nsCOMPtr<nsISupports>

13+ : private nsCOMPtr_base {

14+ ...

15+ }

3 and 4 present another case study where WizardMerge explores conflict-
unrelated violated DCBs within Firefox (between versions VA d295656 and VB
a206204), which were overlooked by Git merge. Specifically, in the file
nsNSSComponent.cpp, both versions define the function
EnsureNSSInitializedChromeOrContent with the same contents. In 3 lines 6-7, a
pointer to nsISupports is created via the template class nsCOMPtr. The
definition of nsCOMPtr is found in nsCOMPtr.h. However, in addition to the
generic template, a template specialization (Vandevoorde and Josuttis, 2002)
is also defined for nsISupports in VB, as shown in lines 11-15 in 4. This
specialization of nsCOMPtr for nsISupports allows users to employ
nsCOMPtr¡nsISupports¿ similarly to how they use nsISupports* and void*,
essentially as a ’catch-all’ pointer pointing to any valid [XP]COM interface
(Mozilla, 2024). When attempting to merge nsCOMPtr.h from the two versions,
Git applies the file from VA because the file from VB is identical to the file
from the base version. Consequently, in the function
EnsureNSSInitializedChromeOrContent, the usage of nsCOMPtr¡nsISupports¿ will
follow lines 4-7 in 4, causing nss to only be able to point to the single
[XP]COM-correct nsISupports instance within an object. This inconsistency can
lead to a potential type confusion bug (Haller et al., 2016; Jeon et al.,
2017). Since no compilation error occurs after successfully being applied by
Git merge, it would be extremely challenging for developers to notice such a
bug, not to mention identify the root cause. With the assistance of
WizardMerge, the loss of template specialization can be detected in the merged
version, thereby notifying developers to address it manually.

Conclusion: We assess the efficacy of WizardMerge in identifying CR-violated
and CU-violated DCBs by quantifying these DCBs in terms of Lines of Code
(LoC), addressing both RQ2 and RQ3. The results reveal that WizardMerge
achieves a detection recall of 80.09% and 73.71% for CR-violated DCBs from
both merging candidates in the five target projects on average. Furthermore,
despite attaining precision rates of 33.26% and 34.66% for CU-violated DCBs in
the four target projects on average, WizardMerge effectively reveals deeply
concealed CU-violated DCBs that are overlooked by developers. To underscore
the impacts of CR-violated and CU-violated DCBs, we present case studies that
further elucidate the rationale behind WizardMerge’s noteworthy findings.

##  5\. Discussion

In this section, we discuss the present limitations in WizardMerge’s design
and explore potential avenues for enhancing WizardMerge.

Improve Graph Generation. As discussed in §3.3, WizardMerge incorporates three
node types and five edge types to construct the ODG. While it adeptly manages
numerous merging scenarios, the evaluation outcomes highlighted in §4 suggest
that this incompleteness could result in an inability to address certain
conflicts or violated DCB instances. For example, WizardMerge cannot infer the
dependency from a global variable to a function if the global variable is
initialized by the function. This is because, during the compilation process,
the initial values of global variables are established before the execution.
In contrast, a function’s return value is accessible only after being
executed. When initializing global variables with a function’s return value,
the compiler transforms the function invocation into initialization code. To
ensure the execution of this initialization code before the main program
commences, the compiler positions this code within a specific section of the
executable file, commonly denoted as the ”.init” segment. This separation
facilitates the execution of these initialization routines prior to the
initiation of the main program logic. We leave updating the features as our
future work to adapt to such scenarios.

Assess Code Optimization. WizardMerge conducts dependency analysis based on
the compilation metadata. Nevertheless, it overlooks a substantial amount of
code information due to compilation optimizations like unused function
elimination and vectorization (LLVM, 2023). As an interim measure, WizardMerge
presently enforces the ”O0” option. However, some projects require compilation
optimization for successful building. For instance, the Linux kernel relies on
optimization to eliminate redundant code segments and disallows the ”O0”
option. In the future, we aim to explore how to adapt our approach to
arbitrary optimization options.

##  6\. Related Work

###  6.1. Merging Strategies

##### Structured Merging

Mastery (Zhu et al., 2022) introduces an innovative structured merging
algorithm that employs a dual approach: top-down and bottom-up traversal. It
can minimize redundant computations and enable the elegant and efficient
handling of the code that has been relocated from its original position to
another location. Spork (Larsén et al., 2022) extends the merging algorithm
from the 3DM (Lindholm, 2004) to maintain the well-structured code format and
language-specific constructs. To fully retain the original functionality of
the merged code, SafeMerge (Sousa et al., 2018) leverages a verification
algorithm for analyzing distinct edits independently and combining them to
achieve a comprehensive demonstration of conflict freedom.

##### Semi-structured Merging

JDime (Apel et al., 2012) introduces a structured merge approach with auto-
tuning that dynamically adjusts the merge process by switching between
unstructured and structured merging based on the presence of conflicts.
FSTMerge (Apel et al., 2011) stands as an early example of semi-structured
merging, offering a framework for the development of semi-structured merging.
Intellimerge (Shen et al., 2019) transforms source code into a program element
graph via semantic analysis, matches vertices with similar semantics, merges
matched vertices’ textual content, and ultimately translates the resulting
graph back into source code files.

The above works, however, cannot help the developers with resolving conflicts.
On the contrary, WizardMerge is constructed atop Git merge, furnishing
developers with clues to aid manual resolution instead of dictating final
merging decisions.

###  6.2. Conflict Resolution

##### Conflict Resolution Assistance

TIPMerge (Costa et al., 2016) evaluates the developers’ experience with the
key files based on the project and branch history (Costa et al., 2016) to
determine the most suitable developers for merging tasks. Automerge (Zhu and
He, 2018) relies on version space algebra (Lau et al., 2003) to represent the
program space and implement a ranking mechanism to identify a resolution
within the program space that is highly likely to align with the developer’s
expectations. SoManyConflicts (Shen et al., 2021) is implemented by modeling
conflicts and their interrelations as a graph and employing classical graph
algorithms to offer recommendations for resolving multiple conflicts more
efficiently.

##### Machine Learning Approaches

MergeBERT (Svyatkovskiy et al., 2022) reframes conflict resolution as a
classification problem and leverages token-level three-way differencing and a
transformer encoder model to build a neural program merge framework. Gmerge
(Zhang et al., 2022) investigates the viability of automated merge conflict
resolution through k-shot learning utilizing pre-trained large language models
(LLMs), such as GPT-3 (Floridi and Chiriatti, 2020). MergeGen (Dong et al.,
2023) treats conflict resolution as a generation task, which can produce new
codes that do not exist in input, and produce more flexible combinations.

The essential difference compared with existing assistance systems and machine
learning approaches is that WizardMerge considers all modified code snippets,
which further helps developers resolve the violated DCBs in merging scenarios.

##  7\. Conclusion

We introduce WizardMerge, a novel code-merging assistance system leveraging
the merging results of Git and dependency analysis based on LLVM IR, named
definition range, and debug information. Via the dependency analysis,
WizardMerge is able to detect the loss of dependency of the named definitions,
therefore providing more accurate merging order suggestions including
conflicts and applied code blocks for the developers. Our evaluation
demonstrates that WizardMerge significantly diminishes conflict merging time
costs. Beyond addressing conflicts, WizardMerge provides merging suggestions
for most of the code blocks potentially affected by the conflicts. Moreover,
WizardMerge exhibits the capability to identify conflict-unrelated code blocks
which should require manual intervention yet automatically applied by Git.

## References

  * (1)
  * Accioly et al. (2018) Paola Accioly, Paulo Borba, and Guilherme Cavalcanti. 2018.  Understanding semi-structured merge conflict characteristics in open-source java projects.  _Empirical Software Engineering_ 23 (2018), 2051–2085.
  * Ahmed et al. (2017) Iftekhar Ahmed, Caius Brindescu, Umme Ayda Mannan, Carlos Jensen, and Anita Sarma. 2017.  An empirical examination of the relationship between code smells and merge conflicts. In _2017 ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM)_. IEEE, 58–67.
  * Aldndni et al. (2023) Waad Aldndni, Na Meng, and Francisco Servant. 2023.  Automatic prediction of developers’ resolutions for software merge conflicts.  _Journal of Systems and Software_ 206 (2023), 111836.
  * Apel et al. (2012) Sven Apel, Olaf Leßenich, and Christian Lengauer. 2012.  Structured merge with auto-tuning: balancing precision and performance. In _Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering_. 120–129.
  * Apel et al. (2011) Sven Apel, Jörg Liebig, Benjamin Brandl, Christian Lengauer, and Christian Kästner. 2011.  Semistructured merge: rethinking merge in revision control systems. In _Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering_. 190–200.
  * ApsarasX (2021) ApsarasX. 2021.  Use LLVM by JavaScript/TypeScript.  https://dev.to/apsarasx/use-llvm-by-javascripttypescript-27c3.  Accessed: 2024-Feb.
  * Atlassian (2022) Atlassian. 2022.  Git Merge.  https://www.atlassian.com/git/tutorials/using-branches/git-merge.  Accessed: 2023-Oct.
  * Cavalcanti et al. (2017) Guilherme Cavalcanti, Paulo Borba, and Paola Accioly. 2017.  Evaluating and improving semistructured merge.  _Proceedings of the ACM on Programming Languages_ 1, OOPSLA (2017), 1–27.
  * Costa et al. (2016) Catarina Costa, Jair Figueiredo, Leonardo Murta, and Anita Sarma. 2016.  TIPMerge: recommending experts for integrating changes across branches. In _Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering_. 523–534.
  * Cp-Algorithms (2023) Cp-Algorithms. 2023.  Segment Tree.  https://cp-algorithms.com/data_structures/segment_tree.html.  Accessed: 2023-Oct.
  * Dinella et al. (2022) Elizabeth Dinella, Todd Mytkowicz, Alexey Svyatkovskiy, Christian Bird, Mayur Naik, and Shuvendu Lahiri. 2022.  Deepmerge: Learning to merge programs.  _IEEE Transactions on Software Engineering_ 49, 4 (2022), 1599–1614.
  * Dong et al. ([n. d.]) Jinhao Dong, Qihao Zhu, Zeyu Sun, Yiling Lou, and Dan Hao. [n. d.].  Merge Conflict Resolution: Classification or Generation?  ([n. d.]).
  * Dong et al. (2023) Jinhao Dong, Qihao Zhu, Zeyu Sun, Yiling Lou, and Dan Hao. 2023.  Merge Conflict Resolution: Classification or Generation?. In _2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 1652–1663.
  * Du (2018) Changbin Du. 2018.  kernel hacking: GCC optimization for better debug experience (-Og).  https://lwn.net/Articles/753639/.  Accessed: 2024-Jan.
  * Elias et al. (2023) Paulo Elias, Heleno de S Campos Junior, Eduardo Ogasawara, and Leonardo Gresta Paulino Murta. 2023.  Towards accurate recommendations of merge conflicts resolution strategies.  _Information and Software Technology_ (2023), 107332.
  * Floridi and Chiriatti (2020) Luciano Floridi and Massimo Chiriatti. 2020.  GPT-3: Its nature, scope, limits, and consequences.  _Minds and Machines_ 30 (2020), 681–694.
  * Git (2023a) Git. 2023a.  Git.  https://git-scm.com/.  Accessed: 2023-Oct.
  * Git (2023b) Git. 2023b.  Git Merge.  https://git-scm.com/docs/git-merge.  Accessed: 2023-Oct.
  * Haller et al. (2016) Istvan Haller, Yuseok Jeon, Hui Peng, Mathias Payer, Cristiano Giuffrida, Herbert Bos, and Erik van der Kouwe. 2016.  TypeSan: Practical Type Confusion Detection. In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ (Vienna, Austria) _(CCS ’16)_. Association for Computing Machinery, New York, NY, USA, 517–528.  https://doi.org/10.1145/2976749.2978405
  * Handy (2023) Kumaran Handy. 2023.  The Biggest Codebases in History, as Measured by Lines of Code.  https://www.artstation.com/blogs/dioeye/Rn8z/the-biggest-codebases-in-history-as-measured-by-lines-of-code.  Accessed: 2024-Jan.
  * Jeon et al. (2017) Yuseok Jeon, Priyam Biswas, Scott Carr, Byoungyoung Lee, and Mathias Payer. 2017.  HexType: Efficient Detection of Type Confusion Errors for C++. In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ (Dallas, Texas, USA) _(CCS ’17)_. Association for Computing Machinery, New York, NY, USA, 2373–2387.  https://doi.org/10.1145/3133956.3134062
  * Khurana (2014) Jatin Khurana. 2014.  GIT merge successfully but introduce a compilation error.  https://stackoverflow.com/questions/25270430/git-merge-successfully-but-introduce-a-compilation-error.  Accessed: 2024-Jan.
  * Larsén et al. (2022) Simon Larsén, Jean-Rémy Falleri, Benoit Baudry, and Martin Monperrus. 2022.  Spork: Structured Merge for Java with Formatting Preservation.  _IEEE Transactions on Software Engineering_ 49, 1 (2022), 64–83.
  * Lattner (2008) Chris Lattner. 2008.  LLVM and Clang: Next generation compiler technology. In _The BSD conference_ , Vol. 5. 1–20.
  * Lau et al. (2003) Tessa Lau, Steven A Wolfman, Pedro Domingos, and Daniel S Weld. 2003.  Programming by demonstration using version space algebra.  _Machine Learning_ 53 (2003), 111–156.
  * Lindholm (2004) Tancred Lindholm. 2004.  A three-way merge for XML documents. In _Proceedings of the 2004 ACM symposium on Document engineering_. 1–10.
  * LLVM (2023) LLVM. 2023.  LLVM’s Analysis and Transform Passes.  https://llvm.org/docs/Passes.html.  Accessed: 2023-Dec.
  * LLVM (2024) LLVM. 2024.  The LLVM Compiler Infrastructure.  https://llvm.org/.  Accessed: 2024-Apr.
  * Mozilla (2023) Mozilla. 2023.  Mercurial Gecko Repositories.  https://hg.mozilla.org/.  Accessed: 2023-Dec.
  * Mozilla (2024) Mozilla. 2024.  Gecko-dev: nsCOMPtr.h.  https://github.com/mozilla/gecko-dev/blob/a20620423a5363cf7afdac81e062bc687c29366a/xpcom/base/nsCOMPtr.h Accessed: 2024-01-29.
  * MySQL (2024) MySQL. 2024.  MySQL.  https://dev.mysql.com/.  Accessed: 2024-Apr.
  * Nishimura and Maruyama (2016) Yuichi Nishimura and Katsuhisa Maruyama. 2016.  Supporting merge conflict resolution by using fine-grained code change history. In _2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER)_ , Vol. 1. IEEE, 661–664.
  * Shen et al. (2021) Bo Shen, Wei Zhang, Ailun Yu, Yifan Shi, Haiyan Zhao, and Zhi Jin. 2021.  SoManyConflicts: Resolve many merge conflicts interactively and systematically. In _2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 1291–1295.
  * Shen et al. (2019) Bo Shen, Wei Zhang, Haiyan Zhao, Guangtai Liang, Zhi Jin, and Qianxiang Wang. 2019.  IntelliMerge: a refactoring-aware software merging technique.  _Proceedings of the ACM on Programming Languages_ 3, OOPSLA (2019), 1–28.
  * Sousa et al. (2018) Marcelo Sousa, Isil Dillig, and Shuvendu K Lahiri. 2018.  Verified three-way program merge.  _Proceedings of the ACM on Programming Languages_ 2, OOPSLA (2018), 1–29.
  * Spealman (2018) Calvin Spealman. 2018.  When a Clean Merge is Wrong.  https://www.caktusgroup.com/blog/2018/03/19/when-clean-merge-wrong/.  Accessed: 2024-Jan.
  * Stepanov (2020) Alexey Stepanov. 2020.  What’s the difference between Kotlin/Native and Java bytecode with compile through LLVM frontend?  https://stackoverflow.com/questions/60580188/whats-the-difference-between-kotlin-native-and-java-bytecode-with-compile-throu.  Accessed: 2024-Feb.
  * Svyatkovskiy et al. (2022) Alexey Svyatkovskiy, Sarah Fakhoury, Negar Ghorbani, Todd Mytkowicz, Elizabeth Dinella, Christian Bird, Jinu Jang, Neel Sundaresan, and Shuvendu K Lahiri. 2022.  Program merge conflict resolution via neural transformers. In _Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 822–833.
  * Tarjan (1972) Robert Tarjan. 1972.  Depth-first search and linear graph algorithms.  _SIAM journal on computing_ 1, 2 (1972), 146–160.
  * Torvalds (2023) Linus Torvalds. 2023.  Linux Kernel Official Repository.  https://github.com/torvalds/linux.  Accessed: 2023-Oct.
  * Vandevoorde and Josuttis (2002) David Vandevoorde and Nicolai M Josuttis. 2002.  _C++ templates: The complete guide, portable documents_.  Addison-Wesley Professional.
  * Vinkler (2023) Alexis Määttä Vinkler. 2023.  The Magic of 3-Way Merge.  https://blog.git-init.com/the-magic-of-3-way-merge/.  Accessed: 2023-Oct.
  * Zhang et al. (2022) Jialu Zhang, Todd Mytkowicz, Mike Kaufman, Ruzica Piskac, and Shuvendu K Lahiri. 2022.  Using pre-trained language models to resolve textual and semantic merge conflicts (experience paper). In _Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis_. 77–88.
  * Zhu and He (2018) Fengmin Zhu and Fei He. 2018.  Conflict resolution for structured merge via version space algebra.  _Proceedings of the ACM on Programming Languages_ 2, OOPSLA (2018), 1–25.
  * Zhu et al. (2022) Fengmin Zhu, Xingyu Xie, Dongyu Feng, Na Meng, and Fei He. 2022.  Mastery: Shifted-Code-Aware Structured Merging. In _International Symposium on Dependable Software Engineering: Theories, Tools, and Applications_. Springer, 70–87.