<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p><font size="-1">This looks like a very worthwhile project. Often
we are looking for faster execution with code size being a
secondary issue though some uses will have the reverse priority.
Hopefully, the project will provide execution times along with
code-size reductions.</font></p>
<p><font size="-1">Neil Nelson</font><br>
</p>
<div class="moz-cite-prefix">On 9/1/20 3:29 PM, Andrew Litteken via
llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:25BE20B9-92BF-4ED2-B399-9B11142B0D46@gmail.com">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Hello,</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">I’m Andrew Litteken, and I am working on a
framework for defining, detecting, and deduplicating similar
code sections at the IR level.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Programmers can introduce sections of code
that perform nearly the same operation. By copying and pasting
code throughout a code base, or using a piece of code as a
reference to create a new piece of code that has nearly the same
structure redundancies are inadvertently introduced throughout
programs. Furthermore, compilers can introduce similarity
through sets of instructions that require the same code
generation strategies, or optimizing to the same patterns.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">For example these two pieces of code:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">int fn(const
std::vector<int> &myVec) {</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;"> for (auto
it = myVec.begin(),</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;"> et =
myVec.end(); it != et; ++it) {</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;"> if
(*it & 1)</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">
return 0;</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;"> }</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;"> return 1;</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">}</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier; min-height:
13px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal;">And</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; min-height: 13px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">int fn(const
std::vector<int> &myVec) {</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;"> for (const
int &x : myVec) {</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;"> if (x
% 2)</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">
return 1;</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;"> }</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;"> return 0;</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">}</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier; min-height:
13px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal;">have a conditional that is finding
whether the variable (it and x respectively) is equal to 1.
And, they generate the same piece of IR code for the
conditional:</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; min-height: 13px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">%11 = load
i32, i32* %10, align 4</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">%12 = and i32
%11, 1</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">%13 = icmp eq
i32 %12, 0</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">%14 =
getelementptr inbounds i32, i32* %10, i64 1</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
11px; line-height: normal; font-family: Courier;">br i1 %13,
label %7, label %15</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Such sections of code can be called
similar. Two sections of code are considered similar when they
perform the same operations on a given set of inputs. However,
this does not require identity. This particular definition
allows for the same sequences of instructions to have different
operand names. For example:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%1 = add i32 %a, 10</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%2 = add i32 %a, %1</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%3 = icmp slt icmp
%1, %2</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">and</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%1 = add i32 11, %a</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%2 = sub i32 %a, %1</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%3 = icmp sgt icmp
%2, %1</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier; min-height: 14px;"><br
class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">are clearly not identical. There are
different constants, the comparison operator is different and
there are flipped operands. But if the constant 10, the
constant 11, and register <span class="" style="font-stretch:
normal; line-height: normal; font-family: Courier;">%a</span> are
considered inputs inputs into these sections, then the two
regions could reduce to be:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%1 = add i32
%input1, %input2</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%2 = sub %input2 %a,
%1</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%3 = icmp slt icmp
%1, %2</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Ultimately, these sets of operations that
are performing the same action, even though the operands are
different. This patch focuses on this sort of “structural”
similarity.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">However, this concept can be easily
generalized. For example, two sections of code could be
considered similar when they contain the same instructions, but
are not necessarily used in the same order. Yet, because of the
way the operands are used in this different ordering, the
instructions still compute the same results for the given
inputs.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">If these similarities are recognized, it
could offer improvements towards reducing code size, analyzing
redundancies in a large project, or creating tools to help
refactor code for a programmer.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">This new framework offers an interface to
detect similarity at the IR level. It has an internal
representation that can be accessed via an analysis, allowing
for easy access by other transformation and analysis passes that
want to leverage detected similarity within a program. It can
also be easily serialized into a file format like JSON, or as
OptRemarks. In the future, a more advanced notion of similarity
could be used, and would it be relatively simple to swap a new
detection algorithm into the similarity framework.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">At present, there have been two different
applications developed on top of this framework. The first is a
similarity visualizer tool called LLVM-Sim that can ingest a
module, and uses the framework to find the similarity in that
module, and output a report for a programmer in a serialized
form, like mentioned above. The second is an IR Outliner using
the analysis pass as the basis for the outlining candidates. I
will first talk briefly about the framework before moving into
the two applications.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
14px; line-height: normal;"><b class="">Finding Similarity:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">The framework for finding similarity is
centered around adding an analysis pass that finds similar
regions of code that do not cross basic blocks, and groups them
into different groups of similarity based on their structure.
These are then made available to other passes, such as an
outliner, or a tool, such as LLVM-Sim.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">In more detail, finding similarity works
by hashing instructions to integers, and placing them in a long
list. The list can be thought of as a string, with each
unsigned integer acting as a character. This string can then be
processed by a Suffix Tree to find repeated substrings in the
program. Following this, the instances of each repeated
substring are analyzed for structural similarity. In this case,
if a one-to-one mapping for the operands of two different
instances of a repeated substring can be found, so that each set
of operands is operated on in the same way, then those two
regions of instructions are considered to be structurally
similar to one another. These tasks are handled by three new
classes: The IRInstructionMapper, the IRSimilarityCandidate, and
the IRSimilarityIdentifier.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
14px; line-height: normal;"><b class="">Finding Similarity
Implementation:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class="">IRInstructionMapper:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Since matching instructions that are
identical does not provide that much information when looking
for structural similarity, the value of the instruction, and the
value of the operands for most instructions are not considered.
Instead only the opcode, types and parameters are considered.
Ultimately, if the opcode and types match, then the instructions
are considered to be performing the same operation. However,
for some instructions like shufflevector, or getelementptr
instructions, it is ensured that the parameters match, in
keeping with the “isSameOperationAs” instruction method. Each
unique instruction via this scheme is mapped to an unsigned
integer. Creating the mapping of the entire program to integers
treats the program like a string with each integer as a
character, and allows the use of data structures such as the
Suffix Tree (recently refactored into LibSupport in review <a
href="https://reviews.llvm.org/D80586" class=""
moz-do-not-send="true"><span class="" style="color: rgb(9, 79,
209);">D80586</span></a>) to process the string for repeated
sequences of instruction in program.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">This maps instructions such as </div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%1 = add i32 %a, 1</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%2 = add i32 %b, %c</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">To the same values as they have the same
opcode and same type, and instructions such as</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%1 = add i32 %a, 1</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%2 = add i64 %b, %c</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%3 = mul i64 %b, %c</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Are mapped to different values, since they
have different opcodes and types.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class="">IRSimilarityIdentifier:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">The list of integers representing the
program is then passed to the Suffix Tree, which can quickly
find repeated substrings, and creates an IRSimilarityCandidate
for each instance of these repeated substring. The
IRSimilarityCandidate provides an interface for comparing the
operand use and instructions of one IRSimilarityCandidate to
another to determine structural similarity.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Structural similarity is determined by
attempting to find a one-to-one mapping from each register in
one candidate to each register in another. If this mapping is
found, then the two candidates are performing the same
operations on a given set of inputs and are structurally
similar. For example:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%1 = add %2, %3</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%4 = add %1, %2</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Is equivalent to</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%a = add %b, %c</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%d = add %b, %a</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">And the IRSimilarityCandidates containing
these sections of code would be considered structurally similar.
But</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%1 = add %2, %3</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%4 = add %1, %2</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Is not equivalent to</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%a = add %b, %c</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%d = add %a, %e.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Since the use of <span class=""
style="font-stretch: normal; line-height: normal; font-family:
Courier;">%2</span> in the first section does not match the
use of <span class="" style="font-stretch: normal; line-height:
normal; font-family: Courier;">%b</span> in the second. So the
IRSimilarityCandidates containing these sections would not be
considered structurally similar.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">The IRSimilarityIdentifier takes the
IRSimilarityCandidates created from the instances of the
repeated substrings and uses the IRSimilarityCandidate’s
interface, described above, to determine which instances of a
given repeated substring are structurally similar to one
another.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Once it has been determined which
instances of a repeated substring that are structurally similar,
sets of IRSimilarityCandidates that have been found to be
compatible are grouped together (a Similarity Group). The
IRSimilarityCandidates contained in each group are structurally
similar to one another. In terms of the example above, the
first two sections of code would be in the same Similarity
Group, but the third is not structurally similar to either.
Therefore, it would be in its own group, and does not have a
matching structure with another IRSimilarityCandidate in the
program.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
14px; line-height: normal;"><b class="">Application: Visualizing
Similarity</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">One potential application is simply
exporting any similarities found for viewing by a user.
LLVM-Sim is a tool that accepts a module, and passes them to the
IRSimilarityIdentifier and retrieves the Similarity Groups for
the module. These are then exported to a JSON file that has an
entry for each Similarity Group, and a list of ranges for each
region of similarity contained in that group. This tool also
could be implemented with remarks rather than JSON for faster,
more streamlined processing of program information.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">If a module had a Similarity Group with
two sections, instructions 5 to 10 and instructions 15 to 20,
and a different Similarity Group contained two sections between
instructions 1 to 4 and 21 to 24, the output JSON would be:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">{</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> “1": [{"s": 5,
"e": 10, {“s": 15, "e": 20}],</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> “2": [{"s": 1,
"e": 4}, {"s": 21, "e": 24}]</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">}</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">This information could be used to create
interfaces to look at, and compare the similarity present in the
program, such as in the example interface here: <a
href="https://reviews.llvm.org/D86974" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86974</a>, which
has two instances of the program alongside its IR with two
different similar sections highlighted.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
14px; line-height: normal;"><b class="">Application:
Deduplicating Similarity with Outlining:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Alternatively, following identifying the
similar sections of the program, the similar regions of code can
be deduplicated. The IR Outliner makes use of the Code
Extractor and the new Similarity Analysis Pass to remove each of
the similar ranges individually, and the new IR Outliner
deduplicates the individually extracted functions for each
region ensuring that the information needed for each extraction
is not lost.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Outlining at the IR level can benefit any
target architecture and reduce the overall size of a program
before any target specific decisions. On the other hand, the
Machine Outliner in LLVM runs after the register allocator and
needs to be implemented for each target separately. The concept
of code structural similarity is easier to implement in a
general way at the IR level.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">The IR Outliner is off by default. There
is a flag -<span class="" style="font-stretch: normal;
line-height: normal; font-family: Courier;">mllvm</span> -<span
class="" style="font-stretch: normal; line-height: normal;
font-family: Courier;">ir-outliner</span> that will use the
defined cost model to attempt to outline sections of code that
will lead to an overall decrease in the size of the program.
There is also a debugging option -<span class=""
style="font-stretch: normal; line-height: normal; font-family:
Courier;">mllvm</span> -<span class="" style="font-stretch:
normal; line-height: normal; font-family: Courier;">ir-outliner-no-cost </span>that
will outline the Similarity Groups greedily based on how many
instructions will be removed, but does not consider the number
of instructions added.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">There are more details about the
implementation of the IR Outliner at the end of the RFC.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class="">Results:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">The LLVM Test Suite, compiled with the IR
Outliner on top of -Oz, has seen code size reductions of up to
60% and an average of 1% code size reduction for both X86 and
AArch64. In these tests, the IR Outliner is placed as the last
stage before code generation for the given target. There are
some regressions. These are due to the fact that our cost model
is not as accurate at the assembly code generation phase. It
can be difficult to estimate how many instructions will be added
during code generation at the IR level. For instance, if many
arguments need to be created to handle constants, the decisions
when creating a call at the assembly level are not directly
obvious. So, our cost model may estimate that fewer
instructions are added than actually need to be. Using target
hooks may be a way to address this issue to get a better sense
of what will happen during code generation than a general
framework for calling conventions.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">CTMark Code Size (x86_64):</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">Test
|Original| With | Reduction</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">
| -Oz |Outlining|</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">-----------------------------------------------------</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">consumer-typeset.test
| 484566 | 458642 | -5.3%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">SPASS.test
| 490445 | 470669 | -4.0%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">sqlite3.test
| 525902 | 512813 | -2.5%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">clamscan.test
| 569405 | 567437 | -0.3%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">lencod.test
| 762084 | 759454 | -0.3%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">bullet.test
| 779072 | 779072 | 0.0%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">kc.test
| 482848 | 482848 | 0.0%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">tramp3d-v4.test
| 708712 | 708712 | 0.0%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">pairlocalalign.test
| 485246 | 485462 | +0.0%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">7zip-benchmark.test
| 982651 | 983563 | +0.1%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">Geomean difference:
-1.3%</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Notable Decreases:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">GCC-C-execute-20041011-1.test:
6600 before, 2343 after, -64.5%.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">This test uses a lot of macros, and the
outliner picks up on the similarity of the same set of inserted
instructions.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">frame_layout: 113631
before, 98110 after, -13.7%.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">This test has a lot of repetitive and
repeated instructions performed on different sets of arguments,
making it a good candidate for outlining.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
14px; line-height: normal;"><b class="">Related Work:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">The previous RFC (<a
href="http://lists.llvm.org/pipermail/llvm-dev/2017-September/117153.html"
class="" moz-do-not-send="true"><span class="" style="color:
rgb(9, 79, 209);">RFC: PT.2 Add IR level interprocedural
outliner for code size.</span></a>) and review (<a
href="https://reviews.llvm.org/D53942" class=""
moz-do-not-send="true"><span class="" style="color: rgb(9, 79,
209);">D53942: IR Outliner Pass</span></a>) discuss similar
techniques for outlining identical instructions at the machine
code level. This patch uses a more general concept of similarity
and works at the IR Level instead. Both share the Suffix Tree
data structure (see <a
href="http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html"
class="" moz-do-not-send="true"><span class="" style="color:
rgb(15, 76, 155);">Interprocedural MIR-level outlining pass</span></a>)
to identify “outlinable” code sequences within a module.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">The framework could also be extended to
encompass the Machine Outliner, so a
MachineCodeSimilarityIdentifier that feeds the MachineOutliner
could be used rather than having all of the functionality inside
the one MachineOutliner pass.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
14px; line-height: normal;"><b class="">Similarity
Identification Implementation:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
14px; line-height: normal;"><b class="">IR Outliner
Implementation:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class="">- Cost Model:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Using information such as region size,
inputs, and outputs, across all the candidates, the arguments
that need to be passed to the outlined function are found. From
this, estimates are made for:</div>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>How
many instructions will need to be added to make a call to the
function.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>How
many instructions will be removed by inserting the call.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>How
many instructions will be added by creating the new function
due to argument handling.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>How
many instructions will be added from stack instructions at
call site.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>How
many instructions will be added from stack instructions
inside call.</li>
</ul>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Then the outlined function is only created
if the number of instructions added is less than the number of
instructions removed. </div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Right now, this cost model was developed
through a general sense of what happens in most calling
conventions, and is conservative. Target hooks would allow for
a target specific sense of how large each instruction is, so
better sense how many machine instructions are being outlined
could be developed. It would also give insight into the
particular calling convention in use. This would allow for a
more accurate cost model, and find more opportunities for
outlining.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class="">- Extraction and
Consolidation:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">If it is determined that outlining all of
the IRSimilarityCandidates in a Similarity Group will add fewer
instructions than it removes, each candidate's block is
extracted using the the Code Extractor. The contents of one of
the functions is placed in a new overall function, that has
input and outputs depending on the arguments needed for each
region, as determined by the Code Extractor. When the
consolidation is performed, anything that is not the same across
each section, like constants, are extracted into arguments as
well. If the arguments are large, they are current extracted
directly into the function arguments as well and are not passed
by reference.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">As an example of extraction and
consolidation, if the following two blocks are extracted, which
each have a different constant in the second operand of the
first add,</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%1 = add i32 %a, 10</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%2 = add i32 %1, %a</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier; min-height: 14px;"><br
class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%1 = add i32 %a, 11</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%2 = add i32 %1, %a</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">The extracted function would be:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">define internal
@outlined_ir_func(i32 %a, i32 %b) {</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">entry:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> %1 = add i32 %a,
%b</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> %2 = add i32 %1,
%a</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> ret void</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">}</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">And calls of:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">call void
@outlined_ir_func(i32 %a, 10)</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">call void
@outlined_ir_func(i32 %a, 11)</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">For values that are used outside of the
region, but are created inside the region, a register that has a
pointer to a location is passed as an argument and the data is
stored into that register. However, between different similar
sections, the values used for outputs are not necessarily the
same. If this is the case, a block for each set of possible
outputs needed is added, with a switch statement to different
sections, controlled by an extra argument.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">For example, if the following two blocks
were extracted, which each have a different item used outside of
the similar section</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%1 = add i32 %a, %b</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%2 = add i32 %1, %a</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%3 = mul i32 %1, %1</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier; min-height: 14px;"><br
class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%4 = add i32 %a, %b</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%5 = add i32 %5, %a</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%6 = div i32 %5, %5</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">The extracted function would be:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">define internal
@outlined_ir_func(i32 %a, i32 %b, i32* %c, i32 %d) {</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">entry:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> %1 = add i32 %a,
%b</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> %2 = add i32 %1,
%a</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> switch %d, label
%final [</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> i32 0, label
%block1</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> i32 1, label
%block2</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> ]</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">block1:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> store i32 %1, %c</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">block2:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;"> store i32 %2, %c</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">}</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier; min-height: 14px;"><br
class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">And calls of</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier; min-height: 14px;"><br
class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">call void
@outlined_ir_func(i32 %a, i32 %b, i32* %c, 0)</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%val = load i32,
i32* %c </div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%3 = mul i32 %val,
%val</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier; min-height: 14px;"><br
class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">call void
@outlined_ir_func(i32 %a, i32 %b, i32* %c, 1)</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%val1 = load i32,
i32* %c </div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier; min-height: 14px;"><br
class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">%6 = div i32 %val1,
%val1</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Once there is complete function, the call
sites are replaced with the new function. If a function does
not require a certain argument it is simply replaced with a null
value. For instance, in the example above, if there was a third
region did not need any sort of output value the call would be:</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier;">call void
@outlined_ir_func(i32 %a, i32 %b, i32* nullptr, -1)</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; font-family: Courier; min-height: 14px;"><br
class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Using a negative one for the switch
statement, the program simply falls through to the ending block.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal; font-size:
14px; line-height: normal;"><b class="">Implementation in Many
Patches:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Each of these patches includes tests. But
the minimum number of patches needed to see outlining are the
Instruction Mapper, Candidate, Identifier, and Wrapper pass
paired with the initial setup and extraction with the input
consolidation. These are current on Phabricator and the links
are included.</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class="">Similarity Identification
Analysis Pass:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class=""><i class="">Instruction
Mapper:</i></b></div>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IRInstructionMapper:
Adding initial mapping of instructions to unsigned integers</li>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link: <a
href="https://reviews.llvm.org/D86968" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86968</a></li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link ilist Parent: <a
href="https://reviews.llvm.org/D86969" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86969</a></li>
</ul>
</ul>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class=""><i class="">IRInstructionCandidate:</i></b></div>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IRInstructionCandidate:
Adding initial candidate structural code, with no special
cases for commutativity.</li>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link Basic: <a
href="https://reviews.llvm.org/D86970" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86970</a></li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link Structural Comparison: <a
href="https://reviews.llvm.org/D86971" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86971</a></li>
</ul>
</ul>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class=""><i class="">IRSimilarityIdentifier:</i></b></div>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IRSimilarityIdentifier:
Add Suffix Tree processing and grouping candidates by
structural similarity.</li>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link: <a
href="https://reviews.llvm.org/D86972" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86972</a></li>
</ul>
</ul>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class=""><i class="">WrapperPass:</i></b></div>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>Wrapper
Pass: Adding a wrapper and printer pass for the
IRSimilarityIdentifier.</li>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link: <a
href="https://reviews.llvm.org/D86973" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86973</a></li>
</ul>
</ul>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class=""><i class="">Extra Features:</i></b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">- Commutativity IRSimilarityCandidate:
Adding flexibility for commutative instructions in structural
comparison.</div>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>Predicate
Isomorphism IRInstructionMapper/IRSimilarityCandidate: Adding
flexibility for isomorphic predicate instructions in
structural comparison.</li>
</ul>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class="">LLVM-Sim:</b></div>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>LLVM-Sim
Basic: Process multiple files using LLVM-Sim and give results
of the identifier to a JSON File.</li>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link: <a
href="https://reviews.llvm.org/D86974" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86974</a></li>
</ul>
</ul>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class="">IROutliner:</b></div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class=""><i class="">Extraction:</i></b></div>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>Initial
Setup and Extraction: Extract the different regions
individually</li>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link: <a
href="https://reviews.llvm.org/D86975" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86975</a></li>
</ul>
</ul>
<b class=""><i class="">Consolidation:</i></b><br class="">
<span class=""></span><span class="">
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IR
Outliner: Adding checks to exclude certain functions that
either cannot be outlined, or require extra work to outline.</li>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link: <a
href="https://reviews.llvm.org/D86976" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86976</a></li>
</ul>
<li class="">IROutliner Only Inputs: Extract only regions that
require inputs, and consolidate each group into one outlined
function.</li>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link Extract: <a
href="https://reviews.llvm.org/D86977" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86977</a></li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Link Consolidate: <a
href="https://reviews.llvm.org/D86978" class=""
moz-do-not-send="true">https://reviews.llvm.org/D86978</a></li>
</ul>
<li class="">IROutliner Constants: Elevate constants to
arguments when they are not the same in each region.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
Assumes: Handles the special case of llvm.assumes which are
removed from extracted regions.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
Sunken Allocas: Handles the case of objects with their
lifetimes entirely included in the region, and elevates them
to arguments.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
Outputs: Handles the case of multiple different output
schemes in different regions.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
Reduce Output Blocks: remove duplicate output scheme plots
for output registers in outlined functions.</li>
</ul>
</span>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><b class=""><i class="">Miscellaneous
Features:</i></b></div>
<ul class="">
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
Attribute Merging: Makes sure that function attributes are
merged consistently.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
Attribute Compatibility: Adds an option to turn on function
attribute incompatibilities for items like sanitizing memory
for outlined function.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
DebugInfo: Makes sure that debug info is consistent for
outlined functions.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
Cost Model: Adds a cost model, so that reductions are
prioritized rather than what comes first in terms of sheer
code size outlined.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
with OptRemarks: Adding OptRemarks to the outliner.</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
with SwiftError: Adding support for swifterror outlined
parameters</li>
<li class="" style="margin: 0px; font-stretch: normal;
line-height: normal;"><span class="" style="font-stretch:
normal; font-size: 14.4px; line-height: normal;"></span>IROutliner
with LinkOnceODR: Adding flag to outline from LinkOnceODR
functions.</li>
</ul>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Any feedback, comments, and discussion are
welcome and appreciated!</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal; min-height: 14px;"><br class="">
</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Thank You,</div>
<div class="" style="margin: 0px; font-stretch: normal;
line-height: normal;">Andrew</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
</body>
</html>