# SUPPORTING CUSTOM INSTRUCTIONS WITH THE LLVM COMPILER

Mehmet EymenÜNAY 040190218 BoraİNAN 040190205 EmrecanYİĞİT 040190203
Elektronik ve Haberleşme MühendisliğiElectronics and Communication Engineering
Elektrik Mühendisliği ProgramıElectrical Engineering Programme Haziran
2023June 2023 Haziran 2023June 2023 Dr. Tankut AKGÜLIstanbul Technical
University LLVM DERLEYİCİSİYLE RISC-V İŞLEMCİ İÇİN EK BUYRUKLARIN
DESTEKLENMESİ FOR RISC-V PROCESSOR Haziran 2023June 2023 Haziran 2023June 2023
Prof. Dr. Name SURNAMEMiddle East Technical University Prof. Dr. Name
SURNAMEBoğaziçi University Prof. Dr. Name SURNAMEBilkent University Prof. Dr.
Name SURNAMESabancı University Prof. Dr. Name SURNAMEKoç University  ABI :
Application Binary Interface ALU : Arithmetic Logic Unit ASIP : Application
Specific Integrated Processor AST : Abstract Syntax Tree CPU : Central
Processing Unit DAG : Directed Acyclic Graph DCE : Dead Code Elimination DSE :
Dead Store Elimination FPGA : Field Programmable Gate Arrays GCC : GNU
Compiler Collection IC : Integrated Circuit IR : Intermediate Representation
ISA : Instruction Set Architecture IoT : Internet of Things LLVM : Low Level
Virtual Machine LSB : Least Significant Bit MC : Machine Code MSB : Most
Significant Bit RISC : Reduced Instruction Set Computer SDnode : SelectionDAG
node SDvalue : SelectionDAG value SSA : Static Single Assignment $\bm{\oplus}$
: XOR $\bm{\land}$ : AND $\bm{\lor}$ : OR $\bm{\lnot}$ : NOT At the outset we
would like to express our sincere thanks and gratitude to our project advisor
Dr. Tankut Akgül who kindly provided us academic support and guidance
throughout our efforts. Without his support and encouragement we would not be
able to overcome the difficulties encountered over the course of our studies.
We would like to express our gratitude to him for helping us make progress
with the project. We would also like to take this opportunity to express our
sincere gratitude and appreciation to Prof. Sıddıka Berna Örs Yalçın for
shaping our targets and supporting us. LLVM community was greatly helpful and
thus, we are thankful to them as well. Finally, we would like to thank our
families and friends who did not spare their moral support during our
university education. Özel buyruklara sahip donanım hızlandırıcılarının
yükselişi, bu hızlandırıcıları destekleyen özel derleyici arka uçlarını
gerektirmektedir. Bu çalışma, LLVM ve LLVM RISC-V arka ucunun ayrıntılı
analizlerini sunmakta ve söz konusu dönüşümlere uçtan uca genel bakış sağlayan
vaka çalışmalarıyla desteklenmektedir. Buyruk tasarımının hem donanım hem de
yazılım tasarım alanında dikkate alınması gerektiğini düşünüyoruz. Gerekli
derleyici değişiklikleri, buyruğun iyi tasarlanmadığı ve yeniden gözden
geçirilmesi gerektiği anlamına gelebilir. RISC-V standart uzantılarının buyruk
tasarımcılarına rehberlik edebilecek örnek buyruklar sağladığını tartışıyoruz.
Bu çalışmada, derleyiciye özel bir buyruk ekleme süreci çevirici desteği ve
örüntü eşleştirme desteği olarak iki kısma ayrılmıştır. Örüntü eşleştirme
desteği olmadan, geleneksel yazılımlar hızlandırıcı için elle satır arası
çevirme dili girişleri gerektirir ve bu da ölçeklenebilir değildir. Buyruk
semantiğinden bağımsız olarak çevirici desteği eklemek basit olsa da, örüntü
eşleştirme desteğinde durum tam tersidir. Örüntü eşleştirme desteği ve
değişiklik için doğru derleyici aşamasını seçmek, derleyicideki iç
dönüşümlerin bilinmesini gerektirir. Bu çalışma, örüntü eşleştirme konusunu
derinlemesine incelemekte ve örüntü eşleştirme desteği sorununa çeşitli
yaklaşımlar sunmaktadır. Örüntünün karmaşıklığına bağlı olarak, daha yüksek
seviyeli dönüşümlerin, örneğin Ara Form seviyesinin, Buyruk Seçimi aşamasına
kıyasla daha sürdürülebilir olabileceği tartışılmaktadır. The rise of hardware
accelerators with custom instructions necessitates custom compiler backends
supporting these accelerators. This study provides detailed analyses of LLVM
and its RISC-V backend, supplemented with case studies providing end-to-end
overview of the mentioned transformations. We discuss that instruction design
should consider both hardware and software design space. The necessary
compiler modifications may mean that the instruction is not well designed and
need to be reconsidered. We discuss that RISC-V standard extensions provide
exemplary instructions that can guide instruction designers. In this study,
the process of adding a custom instruction to compiler is split into two parts
as Assembler support and pattern matching support. Without pattern matching
support, conventional software requires manual entries of inline Assembly for
the accelerator which is not scalable. While it is trivial to add Assembler
support regardless of the instruction semantics, pattern matching support is
on the contrary. Pattern matching support and choosing the right stage for the
modification, requires the knowledge of the internal transformations in the
compiler. This study delves deep into pattern matching and presents multiple
ways to approach the problem of pattern matching support. It is discussed that
depending on the pattern’s complexity, higher level transformations, e.g. IR
level, can be more maintainable compared to Instruction Selection phase.

##  Chapter 1 INTRODUCTION

Recent advances and studies on Integrated Circuits (IC) caused technology to
produce application-specific circuits for various areas of usage. Extensions
for the open source processor architectures became a part of the industrial
development. More custom accelerators are developed, especially with RISC-V
open and modular instruction set architecture (ISA). Hardware accelerators
have the promise of being fast and efficient.

However, loading new abilities to an extended processor comes with a problem.
Programming languages and their compilers are developed for common
architectures. A compiler targeting standard ISA will not produce the custom
instructions for the accelerator. A compiler modification is needed to be able
to introduce the accelerator to the high-level languages. In this thesis, we
show various ways to approach the problem and present the best practices for
it.

For the research, several accelerators with specific custom instructions are
targeted [8, 9]. Instructions which are targeted to hardware are SHLXOR, RORI
and S-box. The encodings and instruction operations were mostly designed by
the hardware developers. The process of required compiler modifications for
SHLXOR and RORI are demonstrated in Sections 8.1 and 8.2. S-box instruction,
due to its non-linearity, was a complicated instruction to characterize. It is
a good example that not every instruction can be added in a similar process
and instruction-specific design can be required. Also similar to the design of
ISAs, instructions should be designed by considering both hardware and
software.

S-box instruction is analyzed from several aspects. Firstly, the Intermediate
Representation (IR) optimizations it gets through are demonstrated in depth in
Section 3.2.3. Secondly, the limitations of TableGen which was a sufficient
system for the previous instructions, are discussed and C++ pattern matching
is explained in Section 7.4. Thirdly, pattern matching in IR and MCInst level
are discussed in Section 7.5. Finally, we proposed two new instructions that
can be implemented in hardware that can accelerate S-box operation as LXR and
NAXOR. A simplified version of LXR which has independent Load addresses is
demonstrated in Section 8.4. The S-box case where the load addresses are
dependent is presented in C++ pattern matching in Section 7.4. The second
proposed instruction, NAXOR, is shown in Section 8.3.

In conjunction with LXR and NAXOR which do not have target hardware, MLA
instruction is also presented without target hardware. MLA is discussed in
detail in Chapter 6 where it is traced from the C code to Assembly in steps of
compilation and Section 7.3 where its support was added with TableGen.

###  1.1 Purpose of Project

Application-Specific Instruction Set Processors (ASIP) are becoming more
popular with the development of embedded systems. The specialization of the
core causes a tradeoff between flexibility and performance. For special
purposes, using ASIPs increases efficiency, however, we can program a custom
ASIP only by using assembly instructions that we defined. Programming custom
processors with assembly language is not a preferred way of coding. We are
also not able to use high-level languages because compiling tools are designed
for common architectures with certain instructions. The ability to add custom
instructions to compilers will enable us to make more use of custom hardware
designs.

ASIPs are feasible for all application-specific embedded systems like
consumer, industrial, automotive, home appliances, cryptology, medical,
telecommunication, commercial, aerospace, and military applications. The
custom back-end that we will design under the supervision of Dr. Tankut Akgül,
is going to serve the processor designed by Prof. Dr. Sıddıka Berna Örs
Yalçın’s research team. When the project is completed, Prof. Yalçın is going
to be able to produce the assembly codes that are compatible with the
processor’s extended instruction set in addition to RISC-V.

Prof. Yalçın and her team are designing application-specific instruction set
processors. The purpose of this project is to create a compiler back-end for a
processor that supports custom instructions on top of RISC-V instructions.
This compiler is going to help to program the custom processor by using high-
level languages. Existing RISC-V compilers are not able to produce efficient
assembly codes for ASIPs. Therefore a need arose for a compiler back-end. The
main reason for choosing this project is that we wanted to meet an actual need
for a critical existing problem. The project has the potential to be the
bridge between hardware and software of custom hardware projects in research,
enabling them to be candidates for production use cases.

##  Chapter 2 BASICS OF A COMPILER

A compiler is a software that converts source code written in a high-level
programming language into machine code (MC) appropriate for a particular
computer architecture. There are different stages of a compiler but they can
be grouped into two main parts such as “Front-End” and “Back-End”. These parts
of the compiler are also called the analysis and synthesis parts of the
compiler. The analysis stage separates the source program into its individual
components and applies a grammatical structure to them. The source code is
then represented in an intermediate stage using this structure. The synthesis
phase creates the final target program by using the IR. We can think of the
compilation process as a series of phases, each of which takes the source
program and transforms it into another representation [10]. These phases can
be seen in Figure 2.1.

Figure 2.1: Compiler Stages

###  2.1 Front-End

####  2.1.1 Lexical Analysis

The compiler breaks down the source code into smaller units called lexemes,
which are pieces of code that correspond to specific patterns in the code.
These lexemes are then converted into tokens that can be used for syntax and
semantic analyses.

####  2.1.2 Syntax Analysis

The compiler checks that the code follows the proper syntax for the
programming language it is written in. This process is also called parsing. As
part of this step, the compiler often creates abstract syntax trees (AST) in
order to represent the logical structure of different parts of the code.

####  2.1.3 Semantic Analysis

The compiler checks that the code makes logical sense, going beyond syntax
analysis by ensuring that the code is correct. For example, the compiler might
check that variables have been declared correctly and given the appropriate
data types. This process is known as semantic analysis.

####  2.1.4 IR Code Generation

After the source code has been analyzed for lexemes, syntax, and semantics,
the compiler creates an IR of the code. This intermediate code is going to be
converted to machine code in the last two phases. These two phases are
platform-dependent, meaning they are specific to a particular hardware
architecture but the previous phases were not. Therefore, to create a new
compiler, it is not necessary to start from scratch. Instead, it is possible
to use the intermediate code from an existing compiler and build the final
stages of the process for a specific platform. Because of that, we are
interested in the back-end part for our project.

###  2.2 Middle-End

####  2.2.1 Optimization

The intermediate code is prepared for the final code generation step. This
process does not change the meaning or functionality of the code, but it can
make the program run faster and more efficiently. A Directed Acyclic Graph
(DAG) used in the compiler design process might represent the dependencies
between different instructions in the IR code, such as the order in which
those instructions need to be executed or the data dependencies between them.
The DAG can be used by the compiler to identify opportunities for
optimization, such as removing unnecessary instructions, combining some of
them, or rearranging the order of execution to reduce the number of resources
required by the code. Static single assignment (SSA) is also an important part
of optimization. It is a technique that is used to organize the IR in a way
that ensures each variable is assigned a value only once and that each
variable is defined before it is used.

###  2.3 Back-End

####  2.3.1 Target Code Generation

The target code generator is the final stage of the compilation process, and
its main function is to convert the optimized code into a form that the
machine can understand. The optimized code is turned into a relocatable
machine code. The relocatable machine code is the input to the linker and
loader, which are responsible for combining the code with other necessary
resources and preparing it for execution Target code generation can be divided
into different parts:

####  2.3.2 Instruction Selection

IR is the input of the code generation step, and it maps the IR into the
target machine’s instruction set. There may be multiple ways for converting
one representation, so the code generator tries to select the most suitable
instructions.

####  2.3.3 Register Allocation

There may be many different variables/values in a program. The code generator
decides which registers to use to keep these values.

####  2.3.4 Instruction Scheduling

The code generator determines the sequence in which instructions will be
executed and creates schedules for the execution of those instructions.

##  Chapter 3 THE LLVM COMPILER

LLVM is a collection of modular and flexible libraries and a toolchain
software that can be used to build a wide variety of compilers and other
tools. LLVM compilers consist of a set of libraries that implement the parts
of a compiler. There are different front-end libraries a for every language
and different back-end libraries for every architecture. There is only one
common IR optimizer that connects specific front end and back end.

Figure 3.1: Front-end and Back-end libraries connected by LLVM

LLVM IR is the common target of programming languages and is the source for
every target hardware. Various LLVM front-ends translate related languages
into IR. Related back-end compiles IR into assembly according to the target
hardware. This structure helps to increase flexibility between front-ends and
back-ends. With this structure, we are able to have compilers for every
combination of $M$ source codes and $N$ targets with $M$ front-end and $N$
back-end instead of $MxN$ compilers. In our case, we do not have to deal with
the front end as our customised back end will be lowering any input
programming language thanks to LLVM IR. The front-end we use in the
development process will be Clang which is the LLVM C/C++ front-end [11].

In LLVM, intrinsic functions are internal functions and they have their
semantics directly defined by LLVM itself. LLVM provides both target-
independent and target-specific intrinsics [12]. These intrinsics have well-
known semantics and names and they must adhere to certain restrictions. In
general, these intrinsics serve as an expansion mechanism for the LLVM
language that does not necessitate modifying all of the transformations in
LLVM when introducing changes to the language. Intrinsic function names start
with “llvm.” [13].

Clang supports the notion of builtin functions used in GNU Compiler Collection
(GCC). Some of these have the same syntax as in GCC to not disrupt
portability. In addition to these, Clang supports other builtin functions that
GCC doesn’t. Some of these are __builtin_shufflevector, __builtin_unreachable
etc. As we can see, these builtin functions start with double underscores.

Intrinsic functions and builtin functions are two separate things and should
not be confused. Builtins are at C level (source code) while intrinsics are
LLVM IR level and are not exposed to the user. A builtin function may or may
not be expanded into intrinsic calls. It is possible to connect a new builtin
function in the front-end to an intrinsic in the middle-end.

###  3.1 Parts of the Clang Front-end

####  3.1.1 Clang Lex Library

Clang Lex Library is a typical lexer implemented as finite state machines that
read source code one character at a time and transition between different
states based on the characters read. The Clang lexer, which is a front-end
compiler for the C, C++, and Objective-C programming languages, uses this
approach to filter out comments and white space, recognize and tokenize
language elements such as keywords, identifiers, and operators, and handle
escape sequences and string literals. The implementation files of the Clang
lexer can be found in the llvm-project/clang/lib/lex directory within the LLVM
infrastructure.

####  3.1.2 Clang Parse Library

Clang Parse Library is the parser that takes the tokens produced by the lexer
and constructs an AST to represent the structure and meaning of the source
code. The Clang parser checks the source code for proper syntax and resolves
symbols and identifiers. It also performs type-checking to ensure the source
code follows the rules of the programming language. It creates the AST, a
tree-like structure, that represents the source code in a way that is easily
processed by the compiler. The implementation files of the Clang lexer can be
found in the llvm-project/clang/lib/parse directory within the LLVM
infrastructure.

####  3.1.3 Clang Sema Library

Clang Sema Library is a semantic analyzer that involves examining the meaning
and context of the source code in a program. In Clang, semantic analysis is a
phase in the compilation process that analyzes the AST generated by the parser
to verify that the source code conforms to the rules of the programming
language and is properly constructed. Semantic analysis performs various
checks and transformations on the AST to ensure the source code is correct.
The implementation files of the Clang semantic analyzer can be found in the
llvm-project/clang/lib/sema directory within the LLVM infrastructure.

####  3.1.4 Clang CodeGen Library

Clang CodeGen is the code generation library that takes the AST as input which
is generated by the parser and corrected by the semantic analyzer. It
generates the IR code and produces a .ll file which will be used in the back
end. The implementation files of the Clang lexer can be found in the llvm-
project/clang/lib/CodeGen directory within the LLVM infrastructure.

###  3.2 LLVM IR Optimizer

LLVM IR is a representation which serves as a common ground for front-ends and
back-ends. LLVM IR is not as high level as programming languages but it
provides more information than assembly by having types or more expressive
functions. LLVM IR instructions are stored in Basic Block structures which
contain sequential IR instructions with an entry and exit.

LLVM Optimizer is a common optimization medium used for every possible source-
target combination of a compiler. It takes the output file of CodeGen as input
and runs three types of passes:

  1. 1.

Analysis passes: These passes analyze the IR and collect information about the
IR without modifying the IR.

  2. 2.

Transformation passes: These passes modify the IR by using the information
gathered from Analysis passes. The optimizations are the product of these
transformations.

  3. 3.

Utility passes: These passes are used to perform tasks such as printing the IR
or verifying the IR.

The output of the optimizer becomes the input for the target back-end which
lowers the LLVM IR to the target Assembly. As the generated LLVM IR at the end
of the optimizations is the object of pattern matching and assembly support
for any custom instruction, it is a critical part of the design process.

####  3.2.1 Analysis Passes

There are almost 40 analysis passes. The significant documented analysis
passes are listed below:

  * $\bullet$

Exhaustive Alias Analysis Precision Evaluator

  * $\bullet$

Basic Alias Analysis (stateless AA impl)

  * $\bullet$

Basic CallGraph Construction

  * $\bullet$

Count Alias Analysis Query Responses

  * $\bullet$

Dependence Analysis

  * $\bullet$

AA use debugger

  * $\bullet$

Dominance Frontier Construction

  * $\bullet$

Dominator Tree Construction

  * $\bullet$

Simple mod/ref analysis for globals

  * $\bullet$

Counts the various types of Instructions

  * $\bullet$

Interval Partition Construction

  * $\bullet$

Induction Variable Users

  * $\bullet$

Lazy Value Information Analysis

  * $\bullet$

LibCall Alias Analysis

  * $\bullet$

Statically lint-checks LLVM IR

  * $\bullet$

Natural Loop Information

  * $\bullet$

Memory Dependence Analysis

  * $\bullet$

Decodes module-level debug info

  * $\bullet$

Post-Dominance Frontier Construction

  * $\bullet$

Post-Dominator Tree Construction

  * $\bullet$

Alias Set Printer

  * $\bullet$

Find Used Types

  * $\bullet$

Detect single entry single exit regions

  * $\bullet$

Scalar Evolution Analysis

  * $\bullet$

ScalarEvolution-based Alias Analysis

  * $\bullet$

Stack Safety Analysis

  * $\bullet$

Target Data Layout

####  3.2.2 Transformation Passes

There are almost 60 transformation passes. The documented transformation
passes are listed below:

  * $\bullet$

Aggressive Dead Code Elimination

  * $\bullet$

Inliner for always_inline functions

  * $\bullet$

Promote ‘by reference’ arguments to scalars

  * $\bullet$

Basic-Block Vectorization

  * $\bullet$

Profile Guided Basic Block Placement

  * $\bullet$

Break critical edges in CFG

  * $\bullet$

Optimize for code generation

  * $\bullet$

Merge Duplicate Global Constants

  * $\bullet$

Dead Code Elimination

  * $\bullet$

Dead Argument Elimination

  * $\bullet$

Dead Type Elimination

  * $\bullet$

Dead Instruction Elimination

  * $\bullet$

Dead Store Elimination

  * $\bullet$

Deduce function attributes

  * $\bullet$

Dead Global Elimination

  * $\bullet$

Global Variable Optimizer

  * $\bullet$

Global Value Numbering

  * $\bullet$

Canonicalize Induction Variables

  * $\bullet$

Function Integration/Inlining

  * $\bullet$

Combine redundant instructions

  * $\bullet$

Combine expression patterns

  * $\bullet$

Internalize Global Symbols

  * $\bullet$

Interprocedural Sparse Conditional Constant Propagation

  * $\bullet$

Jump Threading

  * $\bullet$

Loop-Closed SSA Form Pass

  * $\bullet$

Loop Invariant Code Motion

  * $\bullet$

Delete dead loops

  * $\bullet$

Extract loops into new functions

  * $\bullet$

Extract at most one loop into a new function

  * $\bullet$

Loop Strength Reduction

  * $\bullet$

Rotate Loops

  * $\bullet$

Canonicalize natural loops

  * $\bullet$

Unroll loops

  * $\bullet$

Unroll and Jam loops

  * $\bullet$

Unswitch loops

  * $\bullet$

Lower global destructors

  * $\bullet$

Lower atomic intrinsics to non-atomic form

  * $\bullet$

Lower invokes to calls, for unwindless code generators

  * $\bullet$

Lower SwitchInsts to branches

  * $\bullet$

Promote Memory to Register

  * $\bullet$

MemCpy Optimization

  * $\bullet$

Merge Functions

  * $\bullet$

Unify function exit nodes

  * $\bullet$

Partial Inliner

  * $\bullet$

Remove unused exception handling info

  * $\bullet$

Reassociate expressions

  * $\bullet$

Relative lookup table converter

  * $\bullet$

Demote all values to stack slots

  * $\bullet$

Scalar Replacement of Aggregates

  * $\bullet$

Sparse Conditional Constant Propagation

  * $\bullet$

Simplify the CFG

  * $\bullet$

Code sinking

  * $\bullet$

Strip all symbols from a module

  * $\bullet$

Strip debug info for unused symbols

  * $\bullet$

Strip Unused Function Prototypes

  * $\bullet$

Strip all llvm.dbg.declare intrinsics

  * $\bullet$

Strip all symbols, except dbg symbols, from a module

  * $\bullet$

Tail Call Elimination

[14]

####  3.2.3 Case Study: Optimizations on S-box

One of the research topics of this study was to observe the changes to a
function shown in Code 1 performing S-box with bitwise operations. As the
pattern is large hundreds of lines of LLVM IR and RISC-V Assembly are
generated without enabling optimizations. The unoptimized LLVM IR is given in
Appendices in Code shown in Code 11.2. However, when the optimizations are
enabled the final LLVM IR file shown in Code 2 and the RISC-V Assembly is
significantly smaller.

⬇

1typedef struct {

2 int x[5];

3} ascon_state_t;

4

5void sbox(ascon_state_t state) {

6 int t0, t1, t2, t3, t4;

7 state.x[0] ^= state.x[4];

8 state.x[4] ^= state.x[3];

9 state.x[2] ^= state.x[1];

10 t0 = state.x[0];

11 t1 = state.x[1];

12 t2 = state.x[2];

13 t3 = state.x[3];

14 t4 = state.x[4];

15 t0 =~ t0;

16 t1 =~ t1;

17 t2 =~ t2;

18 t3 =~ t3;

19 t4 =~ t4;

20 t0 &= state.x[1];

21 t1 &= state.x[2];

22 t2 &= state.x[3];

23 t3 &= state.x[4];

24 t4 &= state.x[0];

25 state.x[0] ^= t1;

26 state.x[1] ^= t2;

27 state.x[2] ^= t3;

28 state.x[3] ^= t4;

29 state.x[4] ^= t0;

30 state.x[1] ^= state.x[0];

31 state.x[0] ^= state.x[4];

32 state.x[3] ^= state.x[2];

33 state.x[2] =~ state.x[2];

34

35 return;

36}

Code 1: S-box C code

At the end of optimization passes the following IR will be generated:  ⬇ 1;
Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn
memory(argmem: readwrite) uwtable 2define dso_local void @sbox(ptr nocapture
noundef %state) local_unnamed_addr #0 { 3entry: 4 %arrayidx = getelementptr
inbounds [5 x i32], ptr %state, i32 0, i32 4 5 %0 = load i32, ptr %arrayidx,
align 4, !tbaa !7 6 %1 = load i32, ptr %state, align 4, !tbaa !7 7 %xor = xor
i32 %1, %0 8 %arrayidx4 = getelementptr inbounds [5 x i32], ptr %state, i32 0,
i32 3 9 %2 = load i32, ptr %arrayidx4, align 4, !tbaa !7 10 %xor7 = xor i32
%2, %0 11 %arrayidx9 = getelementptr inbounds [5 x i32], ptr %state, i32 0,
i32 1 12 %3 = load i32, ptr %arrayidx9, align 4, !tbaa !7 13 %arrayidx11 =
getelementptr inbounds [5 x i32], ptr %state, i32 0, i32 2 14 %4 = load i32,
ptr %arrayidx11, align 4, !tbaa !7 15 %xor12 = xor i32 %4, %3 16 %not = xor
i32 %xor, -1 17 %not23 = xor i32 %3, -1 18 %not24 = xor i32 %xor12, -1 19
%not25 = xor i32 %2, -1 20 %not26 = xor i32 %xor7, -1 21 %and = and i32 %3,
%not 22 %and31 = and i32 %4, %not23 23 %and34 = and i32 %2, %not24 24 %and37 =
and i32 %0, %not25 25 %and40 = and i32 %xor, %not26 26 %xor43 = xor i32
%and31, %xor 27 %xor46 = xor i32 %and34, %3 28 %xor49 = xor i32 %xor12, %and37
29 %xor52 = xor i32 %and40, %2 30 %xor55 = xor i32 %and, %xor7 31 store i32
%xor55, ptr %arrayidx, align 4, !tbaa !7 32 %xor60 = xor i32 %xor46, %xor43 33
store i32 %xor60, ptr %arrayidx9, align 4, !tbaa !7 34 %xor65 = xor i32
%xor43, %xor55 35 store i32 %xor65, ptr %state, align 4, !tbaa !7 36 %xor70 =
xor i32 %xor49, %xor52 37 store i32 %xor70, ptr %arrayidx4, align 4, !tbaa !7
38 %not73 = xor i32 %xor49, -1 39 store i32 %not73, ptr %arrayidx11, align 4,
!tbaa !7 40 ret void 41} Code 2: Optimized S-box LLVM IR LLVM optimization
passes are responsible for the simplification of IR. In this case, the
following passes were the passes changing the IR and were run sequentially.

  1. 1.

InferFunctionAttrsPass

  2. 2.

SROAPass

  3. 3.

EarlyCSEPass

  4. 4.

GlobalOptPass

  5. 5.

InstCombinePass

  6. 6.

EarlyCSEPass

  7. 7.

InstCombinePass

  8. 8.

ReassociatePass

  9. 9.

InstCombinePass

  10. 10.

DSEPass

  11. 11.

PostOrderFunctionAttrsPass

As it can be observed some passes can run several times. For example,
InstCombinePass runs to canonicalize and prepare the expressions for the
following pass which is the reason why it is running prior to three distinct
passes.

##### Infer Function Attributes - InferFunctionAttrsPass

This pass adds metadata to LLVM IR, by analyzing it. Function attributes are
used to pass information about functions between LLVM passes.

⬇

181; Function Attrs: nocallback nofree nosync nounwind willreturn
memory(argmem: readwrite)

182declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #1

183

184; Function Attrs: nocallback nofree nosync nounwind willreturn
memory(argmem: readwrite)

185declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #1

Code 3: LLVM IR Before InferFunctionAttrsPass

⬇

181; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn
memory(argmem: readwrite)

182declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #1

183

184; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn
memory(argmem: readwrite)

185declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #1

Code 4: LLVM IR After InferFunctionAttrsPass

Function attribute is inferred as "mustprogress" as the lifetime starting
function is interacting with its environment in an observable way making
memory access [15].

The lifetime function decides the accessibility of the pointer to the memory.
When memory is allocated the lifetime of the pointer to the memory starts and
ends when deallocated [16].

##### Scalar Replacement of Aggregates - SROAPass

Aggregate IR instructions such as "alloca" are promoted to registers. The
promotion to registers also means the lifetime is under control and the
explicit lifetime intrinsic calls can be removed.

⬇

11 %state.indirect_addr = alloca ptr, align 4

12 %t0 = alloca i32, align 4

13 %t1 = alloca i32, align 4

14 %t2 = alloca i32, align 4

15 %t3 = alloca i32, align 4

16 %t4 = alloca i32, align 4

17 store ptr %state, ptr %state.indirect_addr, align 4, !tbaa !7

18 call void @llvm.lifetime.start.p0(i64 4, ptr %t0) #2

19 call void @llvm.lifetime.start.p0(i64 4, ptr %t1) #2

20 call void @llvm.lifetime.start.p0(i64 4, ptr %t2) #2

21 call void @llvm.lifetime.start.p0(i64 4, ptr %t3) #2

22 call void @llvm.lifetime.start.p0(i64 4, ptr %t4) #2

Code 5: Alloca and Lifetime Start Lines Removed From LLVM IR Before SROAPass

⬇

172 store i32 %not73, ptr %arrayidx75, align 4, !tbaa !11

173 call void @llvm.lifetime.end.p0(i64 4, ptr %t4) #2

174 call void @llvm.lifetime.end.p0(i64 4, ptr %t3) #2

175 call void @llvm.lifetime.end.p0(i64 4, ptr %t2) #2

176 call void @llvm.lifetime.end.p0(i64 4, ptr %t1) #2

177 call void @llvm.lifetime.end.p0(i64 4, ptr %t0) #2

Code 6: Lifetime End Lines Removed From LLVM IR Before SROAPass

An important transformation SROA does is promoting the use of registers
instead of using the stack for local variables and using "Load/Store"
operations to use them in the unoptimized IR [17]. "Store/Load" operations are
reduced significantly in this stage, especially for intermediate variables
where the C code is not referring to the array directly.

SROA pass relies on the analysis passes of Alias Analysis through the
collection of analysis passes for Loads.

⬇

15 t0 =~ t0;

16 t1 =~ t1;

17 t2 =~ t2;

18 t3 =~ t3;

19 t4 =~ t4;

Code 7: NOT operations between Intermediate Variables

⬇

66 store i32 %10, ptr %t4, align 4, !tbaa !11

67 %11 = load i32, ptr %t0, align 4, !tbaa !11

68 %not = xor i32 %11, -1

69 store i32 %not, ptr %t0, align 4, !tbaa !11

70 %12 = load i32, ptr %t1, align 4, !tbaa !11

71 %not23 = xor i32 %12, -1

72 store i32 %not23, ptr %t1, align 4, !tbaa !11

73 %13 = load i32, ptr %t2, align 4, !tbaa !11

74 %not24 = xor i32 %13, -1

75 store i32 %not24, ptr %t2, align 4, !tbaa !11

76 %14 = load i32, ptr %t3, align 4, !tbaa !11

77 %not25 = xor i32 %14, -1

78 store i32 %not25, ptr %t3, align 4, !tbaa !11

79 %15 = load i32, ptr %t4, align 4, !tbaa !11

80 %not26 = xor i32 %15, -1

81 store i32 %not26, ptr %t4, align 4, !tbaa !11

Code 8: Intermediate Load and Stores in LLVM IR Before SROAPass

⬇

45 %not = xor i32 %6, -1

46 %not23 = xor i32 %7, -1

47 %not24 = xor i32 %8, -1

48 %not25 = xor i32 %9, -1

49 %not26 = xor i32 %10, -1

Code 9: Load and Stores Promoted to Registers in LLVM IR After SROAPass

Similar to the dramatic change in the previous example, operations between the
array elements and the intermediate variables are optimized so that the
registers are used instead of the stack.

According to the statistics obtained from the "opt" tool of LLVM:

> 5 mem2reg - Number of alloca’s promoted within one block
> 1 mem2reg - Number of alloca’s promoted with a single store
> 1 sroa - Maximum number of partitions per alloca
> 8 sroa - Maximum number of uses of a partition
> 41 sroa - Number of alloca partition uses rewritten
> 6 sroa - Number of alloca partitions formed
> 6 sroa - Number of allocas analyzed for replacement
> 41 sroa - Number of instructions deleted
> 6 sroa - Number of allocas promoted to SSA values
>

##### Early Common Subexpression Elimination - EarlyCSEPass

Performs a simple dominator tree walk, eliminating trivially redundant
instructions. A dominator tree is a type of tree where every parent node
dominates the child node. The definition of dominance from graph theory is
that every path to the dominated node passes through the dominator node [18].

Early CSE pass relies on MemorySSA analysis which analyses by representing
memory operations in SSA form [19, 20].

⬇

4define dso_local void @sbox(ptr noundef %state) #0 {

5entry:

6 %x = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32 0

7 %arrayidx = getelementptr inbounds [5 x i32], ptr %x, i32 0, i32 4

8 %0 = load i32, ptr %arrayidx, align 4, !tbaa !7

9 %x1 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32 0

10 %arrayidx2 = getelementptr inbounds [5 x i32], ptr %x1, i32 0, i32 0

11 %1 = load i32, ptr %arrayidx2, align 4, !tbaa !7

Code 10: Redundant Load Instructions in LLVM IR Before EarlyCSEPass

In Code 10 you can see that "%x1" and "%arrayidx2" are equal to the function
argument "%state". EarlyCSE pass detects this redundant condition and uses the
already present "%state" pointer in the output.

⬇

2define dso_local void @sbox(ptr noundef %state) #0 {

3entry:

4 %arrayidx = getelementptr inbounds [5 x i32], ptr %state, i32 0, i32 4

5 %0 = load i32, ptr %arrayidx, align 4, !tbaa !7

6 %1 = load i32, ptr %state, align 4, !tbaa !7

Code 11: Optimized Load Instructions in LLVM IR After EarlyCSEPass

Another remark from this example is that the pointer calculation is done in
two instructions by "getelementptr" LLVM instruction which accesses the
struct’s address and then the element’s address in it. EarlyCSE combines these
two instructions outputting the offset calculated pointers.

A natural result of these simple optimizations is that the section which makes
use of registers has increased. It can be seen in Code 12 that the
recalculation of pointers by getelementptr is removed as they are used at the
beginning of the function, as shown partly in Code 11.

⬇

30 %x13 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32
0

31 %arrayidx14 = getelementptr inbounds [5 x i32], ptr %x13, i32 0, i32 0

32 %6 = load i32, ptr %arrayidx14, align 4, !tbaa !7

33 %x15 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32
0

34 %arrayidx16 = getelementptr inbounds [5 x i32], ptr %x15, i32 0, i32 1

35 %7 = load i32, ptr %arrayidx16, align 4, !tbaa !7

36 %x17 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32
0

37 %arrayidx18 = getelementptr inbounds [5 x i32], ptr %x17, i32 0, i32 2

38 %8 = load i32, ptr %arrayidx18, align 4, !tbaa !7

39 %x19 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32
0

40 %arrayidx20 = getelementptr inbounds [5 x i32], ptr %x19, i32 0, i32 3

41 %9 = load i32, ptr %arrayidx20, align 4, !tbaa !7

42 %x21 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32
0

43 %arrayidx22 = getelementptr inbounds [5 x i32], ptr %x21, i32 0, i32 4

44 %10 = load i32, ptr %arrayidx22, align 4, !tbaa !7

45 %not = xor i32 %6, -1

46 %not23 = xor i32 %7, -1

47 %not24 = xor i32 %8, -1

48 %not25 = xor i32 %9, -1

49 %not26 = xor i32 %10, -1

50 %x27 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32
0

51 %arrayidx28 = getelementptr inbounds [5 x i32], ptr %x27, i32 0, i32 1

52 %11 = load i32, ptr %arrayidx28, align 4, !tbaa !7

53 %and = and i32 %not, %11

54 %x29 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32
0

55 %arrayidx30 = getelementptr inbounds [5 x i32], ptr %x29, i32 0, i32 2

56 %12 = load i32, ptr %arrayidx30, align 4, !tbaa !7

57 %and31 = and i32 %not23, %12

58 %x32 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32
0

59 %arrayidx33 = getelementptr inbounds [5 x i32], ptr %x32, i32 0, i32 3

60 %13 = load i32, ptr %arrayidx33, align 4, !tbaa !7

61 %and34 = and i32 %not24, %13

62 %x35 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32
0

63 %arrayidx36 = getelementptr inbounds [5 x i32], ptr %x35, i32 0, i32 4

64 %14 = load i32, ptr %arrayidx36, align 4, !tbaa !7

65 %and37 = and i32 %not25, %14

66 %x38 = getelementptr inbounds %struct.ascon_state_t, ptr %state, i32 0, i32
0

67 %arrayidx39 = getelementptr inbounds [5 x i32], ptr %x38, i32 0, i32 0

68 %15 = load i32, ptr %arrayidx39, align 4, !tbaa !7

69 %and40 = and i32 %not26, %15

Code 12: Redundant Instructions in LLVM IR Before EarlyCSEPass

⬇

20 %6 = load i32, ptr %state, align 4, !tbaa !7

21 %7 = load i32, ptr %arrayidx9, align 4, !tbaa !7

22 %8 = load i32, ptr %arrayidx4, align 4, !tbaa !7

23 %9 = load i32, ptr %arrayidx, align 4, !tbaa !7

24 %not = xor i32 %6, -1

25 %not23 = xor i32 %7, -1

26 %not24 = xor i32 %xor12, -1

27 %not25 = xor i32 %8, -1

28 %not26 = xor i32 %9, -1

29 %and = and i32 %not, %7

30 %and31 = and i32 %not23, %xor12

31 %and34 = and i32 %not24, %8

32 %and37 = and i32 %not25, %9

33 %and40 = and i32 %not26, %6

Code 13: Optimized LLVM IR After EarlyCSEPass

Register-based operations increased because redundant load operations from the
same pointers are removed. For example, in Code 12 to obtain "%and", register
operation result "%not" and loaded value "%11" are used. In the output of
EarlyCSE, Code 13, we can see that instead of reloading to register the loaded
register is used, "%7" in this case.

According to the statistics obtained from the "opt" tool of LLVM:

> 19 early-cse - Number of instructions Common Subexpression Eliminated
> 7 early-cse - Number of load instructions Common Subexpression Eliminated
> 35 early-cse - Number of instructions simplified or Dead Code Eliminated
>

##### Optimize Global Variables - GlobalOpt

This pass aims to optimize global variables and transforms them into constants
if necessary. This pass did not significantly change the IR. It only added an
attribute to the function, "local_unnamed_addr" meaning that the address of
the function is not significant in the module.

⬇

7define dso_local void @sbox(ptr noundef %state) local_unnamed_addr #0 {

Code 14: "local_unnamed_addr" Attribute Added to LLVM IR After GlobalOpt

##### Combine Redundant Instructions - InstCombinePass

Combines redundant instructions and canonicalizes them. Canonicalization is
the form in which a single way of commutability is preferred. For example, if
a binary operator has a constant operand it is moved to the right. Canonic
instructions can then be used by other passes which can assume the
instructions to be in the canonic form [21].

⬇

10 %0 = load i32, ptr %arrayidx, align 4, !tbaa !7

11 %1 = load i32, ptr %state, align 4, !tbaa !7

12 %xor = xor i32 %1, %0

13 store i32 %xor, ptr %state, align 4, !tbaa !7

14 %arrayidx4 = getelementptr inbounds [5 x i32], ptr %state, i32 0, i32 3

15 %2 = load i32, ptr %arrayidx4, align 4, !tbaa !7

16 %3 = load i32, ptr %arrayidx, align 4, !tbaa !7

17 %xor7 = xor i32 %3, %2

Code 15: Redundant Load Instruction in LLVM IR Before InstCombine

⬇

4 %arrayidx = getelementptr inbounds [5 x i32], ptr %state, i32 0, i32 4

5 %0 = load i32, ptr %arrayidx, align 4, !tbaa !7

6 %1 = load i32, ptr %state, align 4, !tbaa !7

7 %xor = xor i32 %1, %0

8 store i32 %xor, ptr %state, align 4, !tbaa !7

9 %arrayidx4 = getelementptr inbounds [5 x i32], ptr %state, i32 0, i32 3

10 %2 = load i32, ptr %arrayidx4, align 4, !tbaa !7

11 %xor7 = xor i32 %0, %2

Code 16: Removed Load Instruction in LLVM IR After InstCombine

According to the statistics obtained from the "opt" tool of LLVM:

> 5 aa - Number of NoAlias results
> 109 assume-queries - Number of Queries into an assume assume bundles
> 10 basicaa - Number of times a GEP is decomposed
> 11 instcombine - Number of insts combined
> 1 instcombine - Number of expansions
> 2 instcombine - Number of instruction combining iterations performed
>

##### Early Common Subexpression Elimination - 2nd Run of EarlyCSEPass

Similar to the previous EarlyCSE run in Section 3.2.3, load instructions to
registers are reused in the subsequent instructions.

⬇

34 %8 = load i32, ptr %arrayidx9, align 4, !tbaa !7

35 %xor46 = xor i32 %8, %and34

36 store i32 %xor46, ptr %arrayidx9, align 4, !tbaa !7

37 %9 = load i32, ptr %arrayidx11, align 4, !tbaa !7

38 %xor49 = xor i32 %9, %and37

39 store i32 %xor49, ptr %arrayidx11, align 4, !tbaa !7

40 %10 = load i32, ptr %arrayidx4, align 4, !tbaa !7

41 %xor52 = xor i32 %10, %and40

42 store i32 %xor52, ptr %arrayidx4, align 4, !tbaa !7

43 %11 = load i32, ptr %arrayidx, align 4, !tbaa !7

44 %xor55 = xor i32 %11, %and

45 store i32 %xor55, ptr %arrayidx, align 4, !tbaa !7

46 %12 = load i32, ptr %state, align 4, !tbaa !7

47 %13 = load i32, ptr %arrayidx9, align 4, !tbaa !7

48 %xor60 = xor i32 %13, %12

Code 17: Redundant Load Instructions in LLVM IR Before 2nd EarlyCSEPass

⬇

31 %xor46 = xor i32 %3, %and34

32 store i32 %xor46, ptr %arrayidx9, align 4, !tbaa !7

33 %xor49 = xor i32 %xor12, %and37

34 store i32 %xor49, ptr %arrayidx11, align 4, !tbaa !7

35 %xor52 = xor i32 %2, %and40

36 store i32 %xor52, ptr %arrayidx4, align 4, !tbaa !7

37 %xor55 = xor i32 %xor7, %and

38 store i32 %xor55, ptr %arrayidx, align 4, !tbaa !7

39 %xor60 = xor i32 %xor46, %xor43

Code 18: Removed Load Instructions in LLVM IR After 2nd EarlyCSEPass

##### Combine Redundant Instructions - 2nd Run of InstCombinePass

⬇

4 %arrayidx = getelementptr inbounds [5 x i32], ptr %state, i32 0, i32 4

5 %0 = load i32, ptr %arrayidx, align 4, !tbaa !7

9 %arrayidx4 = getelementptr inbounds [5 x i32], ptr %state, i32 0, i32 3

10 %2 = load i32, ptr %arrayidx4, align 4, !tbaa !7

11 %xor7 = xor i32 %0, %2

22 %not25 = xor i32 %2, -1

27 %and37 = and i32 %xor7, %not25

Code 19: XOR Instruction in LLVM IR Before InstCombine

⬇

4 %arrayidx = getelementptr inbounds [5 x i32], ptr %state, i32 0, i32 4

5 %0 = load i32, ptr %arrayidx, align 4, !tbaa !7

9 %arrayidx4 = getelementptr inbounds [5 x i32], ptr %state, i32 0, i32 3

10 %2 = load i32, ptr %arrayidx4, align 4, !tbaa !7

22 %not25 = xor i32 %2, -1

27 %and37 = and i32 %0, %not25

Code 20: XOR Instruction in LLVM IR After InstCombine

The first algebraic optimization in the process can be observed in this
example. In Code 19, to obtain "%and37" the boolean operations of the
following must be performed:

$(\%0\oplus\%2)\land(\%2\oplus-1)$

It can be shown that a simpler boolean form can be obtained by transitioning
equivalent boolean equations:

$(\%0\oplus\%2)\land\lnot\%2$
$((\%0\land\lnot\%2)\lor(\lnot\%0\land\%2))\land\lnot\%2$
$(\%0\land\lnot\%2\land\lnot\%2)\lor(\lnot\%0\land\%2\land\lnot\%2)$
$(\%0\land\lnot\%2)\lor(0)$ $\%0\land(\%2\oplus-1)$

In Code 20, the redundant operation $\%0\oplus\%2$ is removed and the result
is:

$\%0\land(\%2\oplus-1)$

According to the statistics obtained from the "opt" tool of LLVM:

> 60 assume-queries - Number of Queries into an assume assume bundles
> 5 instcombine - Number of insts combined
> 1 instcombine - Number of expansions
> 2 instcombine - Number of instruction combining iterations performed
> 12 instsimplify - Number of reassociations
>

##### Reassociate Expressions - ReassociatePass

Reassociates associative expressions, to promote better constant propagation
and simplify expression graph to reduce instruction count. It implements an
algorithm where the constants have the least rank and the rank increases with
the expression reverse post-order traversal [22].

⬇

26 %and34 = and i32 %2, %not24

27 %and37 = and i32 %0, %not25

28 %and40 = and i32 %xor, %not26

29 %xor43 = xor i32 %xor, %and31

Code 21: Instructions in LLVM IR Before ReassociatePass

⬇

26 %and34 = and i32 %not24, %2

27 %and37 = and i32 %not25, %0

28 %and40 = and i32 %not26, %xor

29 %xor43 = xor i32 %and31, %xor

Code 22: Instructions with Reassociated Arguments in LLVM IR After
ReassociatePass

A basic glance at the debug output of the pass gives more idea about how the
reassociation works.

⬇

1Calculated Rank[state] = 3

2Combine negations for: %

3LINEARIZE: %

4OPERAND: %

5ADD USES LEAF: %

6OPERAND: %

7ADD LEAF: %

8RAIn: xor i32 [ %

9RAOut: xor i32 [ %

10RA: %

11TO: %

12Combine negations for: %

13LINEARIZE: %

14OPERAND: %

15ADD USES LEAF: %

16OPERAND: %

17ADD USES LEAF: %

18RAIn: xor i32 [ %

19RAOut: xor i32 [ %

20RA: %

21TO: %

Code 23: Debug Output of Reassociate Pass from LLVM opt tool

The debug output deals with the beginning of the function which is given
below.

⬇

5 %0 = load i32, ptr %arrayidx, align 4, !tbaa !7

6 %1 = load i32, ptr %state, align 4, !tbaa !7

7 %xor = xor i32 %1, %0

8 store i32 %xor, ptr %state, align 4, !tbaa !7

9 %arrayidx4 = getelementptr inbounds [5 x i32], ptr %state, i32 0, i32 3

10 %2 = load i32, ptr %arrayidx4, align 4, !tbaa !7

11 %xor7 = xor i32 %0, %2

Code 24: Instructions in LLVM IR Before ReassociatePass

The pass computed that the reassociation would result in the instruction "%xor
= xor i32 %1, %0" which is already how the IR is so it is not changed.
However, as it can be seen in Code 22, "%xor7 = xor i32 %2, %0" replaced its
alternative representation as the rank of "%0" is less than "%2".

According to the statistics obtained from the "opt" tool of LLVM:

> 16 reassociate - Number of insts reassociated

##### Combine Redundant Instructions - 2nd Run of InstCombinePass

In this last run of InstCombinePass instruction count is not changed. Some
reassociations by the previous pass are reversed.

⬇

26 %and34 = and i32 %not24, %2

27 %and37 = and i32 %not25, %0

28 %and40 = and i32 %not26, %xor

29 %xor43 = xor i32 %and31, %xor

Code 25: Instructions in LLVM IR Before the 3rd InstCombinePass

⬇

26 %and34 = and i32 %2, %not24

27 %and37 = and i32 %0, %not25

28 %and40 = and i32 %xor, %not26

29 %xor43 = xor i32 %and31, %xor

Code 26: Instructions with Reassociated Arguments in LLVM IR After
InstCombinePass

Though it may seem wasteful, it is a common theme in LLVM that some
transformations may be done and be completely reversed by another pass.

According to the statistics obtained from the "opt" tool of LLVM:

> 60 assume-queries - Number of Queries into an assume assume bundles
> 7 instcombine - Number of insts combined
> 2 instcombine - Number of instruction combining iterations performed
> 12 instsimplify - Number of reassociations
>

##### Dead Store Elimination - DSEPass

Dead code in the Dead Code Elimination (DCE) pass refers to the variables in
any point of the program which are not used in the future. DCE does not
eliminate control flow and store instructions, for this reason, Dead Store
Elimination (DSE) pass is used to simplify the store instructions of the given
program.

Trivial dead stores are eliminated. As the load operations are optimized, most
of the store instructions become dead meaning that they do not affect the flow
in any way.

Similar to Early CSE pass in Section 3.2.3, DSE pass relies on Memory SSA
analysis.

⬇

30 store i32 %xor43, ptr %state, align 4, !tbaa !7

31 %xor46 = xor i32 %and34, %3

32 store i32 %xor46, ptr %arrayidx9, align 4, !tbaa !7

33 %xor49 = xor i32 %xor12, %and37

34 store i32 %xor49, ptr %arrayidx11, align 4, !tbaa !7

35 %xor52 = xor i32 %and40, %2

36 store i32 %xor52, ptr %arrayidx4, align 4, !tbaa !7

Code 27: Redundant Store Instructions in LLVM IR Before DSEPass

⬇

27 %xor46 = xor i32 %and34, %3

28 %xor49 = xor i32 %xor12, %and37

29 %xor52 = xor i32 %and40, %2

Code 28: Removed Store Instructions in LLVM IR After DSEPass

To see how the DSE works we can observe two dead Store’s and a killer Store,
unnecessary code is stripped away.

⬇

2define dso_local void @sbox(ptr noundef %state) local_unnamed_addr #0 {

8 store i32 %xor, ptr %state, align 4, !tbaa !7

30 store i32 %xor43, ptr %state, align 4, !tbaa !7

42 store i32 %xor65, ptr %state, align 4, !tbaa !7

Code 29: Store Instructions to the Same Address in LLVM IR Before DSEPass

Here is the debug output of the DSE pass.

⬇

1Trying to eliminate MemoryDefs killed by 4 = MemoryDef(3) (

2store i32 %

3 trying to get dominating access

4 visiting 3 = MemoryDef(2)->liveOnEntry (store i32 %

5 visiting 2 = MemoryDef(1)->liveOnEntry (store i32 %

6 visiting 1 = MemoryDef(liveOnEntry) (store i32 %

7 Checking for reads of 1 = MemoryDef(liveOnEntry) (store i32 %

8 4 = MemoryDef(3)->1 ( store i32 %

9 ... skipping killing def/dom access

10 2 = MemoryDef(1)->liveOnEntry (store i32 %

11 3 = MemoryDef(2)->liveOnEntry (store i32 %

12 Checking if we can kill 1 = MemoryDef(liveOnEntry) (store i32 %

13DSE: Remove Dead Store:

14 DEAD: store i32 %

15 KILLER: store i32 %

16 trying to get dominating access

17 visiting 0 = MemoryDef(liveOnEntry)

18 ... found LiveOnEntryDef

19 finished walk

20 .

21 .

22 .

23 Trying to eliminate MemoryDefs killed by 10 = MemoryDef(9) (

24 store i32 %

25 trying to get dominating access

26 visiting 9 = MemoryDef(8) (store i32 %

27 visiting 8 = MemoryDef(7) (store i32 %

28 visiting 7 = MemoryDef(6)->liveOnEntry (store i32 %

29 visiting 6 = MemoryDef(4) (store i32 %

30 visiting 4 = MemoryDef(liveOnEntry) (store i32 %

31 Checking for reads of 4 = MemoryDef(liveOnEntry) (store i32 %

32 10 = MemoryDef(9)->4 (store i32 %

33 ... skipping killing def/dom access

34 6 = MemoryDef(4) (store i32 %

35 9 = MemoryDef(8) (store i32 %

36 7 = MemoryDef(6)->liveOnEntry (store i32 %

37 8 = MemoryDef(7) (store i32 %

38 Checking if we can kill 4 = MemoryDef(liveOnEntry) (

39 store i32 %

40DSE: Remove Dead Store:

41 DEAD: store i32 %

42 KILLER: store i32 %

43 trying to get dominating access

44 visiting 0 = MemoryDef(liveOnEntry)

45 ... found LiveOnEntryDef

46 finished walk

Code 30: Debug Output of DSE Pass from LLVM opt tool

It can be observed that whenever the DSE encounters a Store instruction with
the same address as a previous Store instruction, kills the previous
instruction. The last Store instruction survives DSE.

According to the statistics obtained from the "opt" tool of LLVM:

> 14 aa - Number of MustAlias results
> 62 aa - Number of NoAlias results
> 30 basicaa - Number of times a GEP is decomposed
> 29 dse - Number iterations check for reads in getDomMemoryDef
> 0 dse - Number of other instrs removed
> 7 dse - Number of stores deleted
> 7 dse - Number of times a valid candidate is returned from getDomMemoryDef
> 5 dse - Number of stores remaining after DSE
> 1 ir - Number of renumberings across all blocks
> 71 memory-builtins - Number of arguments with unsolved size and offset
>

##### Post-Order Function Attributes Pass - PostOrderFunctionAttrsPass

This pass is similar to the InferFunctionAttrsPass in Section 3.2.3. It does
not change the IR, adds metadata to it for the other passes.

⬇

1; Function Attrs: nounwind uwtable

2define dso_local void @sbox(ptr noundef %state) local_unnamed_addr #0 {

Code 31: Function Attributes After PostOrderFunctionAttrsPass

⬇

1; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn
memory(argmem: readwrite) uwtable

2define dso_local void @sbox(ptr nocapture noundef %state) local_unnamed_addr
#0 {

Code 32: Function Attributes Before PostOrderFunctionAttrsPass

The added attributes signal that the function does not deallocate memory, does
not recurse by calling itself, never raises an exception, will continue
execution at the end according to the call stack, and may read or write any
memory.

In the end of optimization passes, the IR at Code 2 will be generated.

####  3.2.4 Clang Optimization Levels

It should be noted that in order to observe an optimised Assembly, the LLVM IR
should be generated by enabling optimizations. Clang can be invoked with
optimization levels deciding which optimization passes are going to be run.
The optimizations can target speed or code size. Speed optimizing options
range from "-O1" to "-O3". "-O2" enables most of the optimizations. "-O3"
enables optimizations that can increase the compile time and generate larger
code. The main code optimizing options are "-Os" and "-Oz". "-Os" is similar
to "-O2" but runs extra optimizations to reduce code size. "-Oz" runs more
code-reducing optimizations compared to "-Os" and is similar to "-O2" again
[23]. Caution must be taken as when no arguments are given to Clang, at the
time of writing, Clang uses the "-O0" optimization level. Implementing pattern
matching on unoptimized LLVM IR is not feasible for several reasons. Firstly,
the IR is more sensitive to changes in the front end. Changing the code style
in the front end can cause CodeGen to produce a slightly different IR which
makes it less predictable. Secondly, the code size can be too large with
redundant code which makes pattern matching large instructions cumbersome. We
recommend using "-O2" or "-Os" optimization levels while developing
instruction selection patterns.

LLVM optimizations can be performed with an LLVM IR input by using the "opt"
tool [24]. It is possible to experiment with different optimizations and
observe their results on the output.

###  3.3 Stages of the LLVM RISC-V Back-end

LLVM RISC-V back-end is responsible for compiling optimized IR down to RISC-V
assembly or object code. LLVM back-end consists of libraries for the code
generation steps[25].

####  3.3.1 Instruction Selection

SelectionDAG is the default instruction selector of LLVM RISC-V back-end which
is responsible for selecting the appropriate RISC-V instructions for a given
IR instruction. It takes the target-independent LLVM code as input and
generates the target-dependent DAG of instructions. SelectionDAG is at the
core of this study since we will be dealing with adding new instructions to
the RISC-V back end.

##### SelectionDAG construction

After IR generation is done, SelectionDAG gets the optimized IR and converts
it into a target-independent SelectionDAG representation. SelectionDAG
consists of SelectionDAG nodes (SDnode) which are created by
SelectionDAGBuilder class. SelectionDAGIsel visits all the IR instructions and
uses the SelectionDAGBuilder class. The relevant instruction method requests
an SDNode to the DAG and assigns its opcode. Every SDNode has an opcode for
the operation it represents. SDNodes have multiple values to return as the
result. SDValues (SelectionDAG value) hold the information to determine which
number to return. SelectionDAGBuilder class reshapes the linear IR input to a
SelectionDAG tree form. At the end of the construction, SelectionDAG is a
target-independent and illegal DAG.

##### SelectionDAG legalization

SelectionDAG is a target-dependent representation after the construction stage
of the instruction selection. Before creating a target-specific code,
SelectionDAG checks if the DAG is legal because the constructed DAG may
include incompatible instructions and data types to the target architecture
[26]. SelectionDAG legalization refers to the process of transforming the
SelectionDAG according to the constraints and requirements of the target
architecture. Legalization may involve adding, removing, splitting or merging
the nodes, targeting to match the register file and instruction set of the
target architecture [27]. SelectionDAG legalization also ensures that the data
type of the target architecture is compatible with the target architecture by
truncating or promoting the data types. For example, if SelectionDAG includes
32-bit integer (i32) data type nodes targeted to an i64 architecture,
SDlegalizer promotes the i32 nodes to 64-bit integer (i64) data type. For
every target architecture type, IselLowering.cpp files are responsible for
legalizing the SelectionDAG. SDlegalizer legalizes the illegal DAG into a
supported form and ensures that the generated code is efficient and compatible
with the target architecture.
An example of legalizing the SelectionDAG by truncating the i64 data type DAG
into i32 data type target architecture is shown in Code 33. IR code includes
i64 data type variables however, target architecture supports only i32 data
type. Before the legalization (Figure 3.2) DAG is not converted to the target
data type yet and it needed to become i64 compatible. It can be seen that
after legalization (Figure 3.3), i32 nodes are truncated and there are no i64
nodes in the DAG.

⬇

1 define i64 @test(i64 %

2 ret i64 %

3 }

Code 33: IR code input for legalization example Figure 3.2: DAG diagram before
the legalization stage Figure 3.3: DAG diagram after the legalization stage

##### SelectionDAG optimization

The DAG should be optimized after legalization because the legalization phase
may create unnecessary DAG nodes and the reducible nodes are not combined yet.
SelectionDAG optimizer minimizes the DAG nodes before creating the target-
specific instructions.

##### SelectionDAG target-dependent instruction selection

At the last phase of the instruction selection, SelectionDAG selects the
suitable instructions for the target architecture. SelectionDAG uses the
relevant TableGen target description (.td) files or C++ logic to match the
patterns and replaces the patterns with the target-specific instructions.

####  3.3.2 Scheduling and Formation

Scheduling is the phase of assigning an order to the DAG form of RISC-V
instructions. The formation phase is responsible for converting the DAG into a
list of machine instructions.

####  3.3.3 SSA-based Machine Code Optimizations

LLVM uses SSA-based optimizations before register allocation. SSA
optimizations ensure that each variable is assigned and defined only once
before it is used.

####  3.3.4 Register Allocation

The register allocation is responsible for assigning physical registers to
virtual registers in the IR. Each target has a specific register count and
order. The register allocator maps the registers by taking the RISC-V
architecture registers into account. It uses the relevant TargetRegisterInfo,
and MachineOperand classes.

####  3.3.5 Prologue/Epilogue Code Insertion

Prologue and epilogue code insertion is another optimization phase that is
responsible for frame-pointer elimination and stack packing.

####  3.3.6 Code Emission

The code emission stage is responsible for lowering the code generator
abstractions down to the Machine Code layer abstractions. It takes the
assembly as input and creates the final RISC-V machine codes.

####  3.3.7 Linking

LLD is the LLVM linker library that is responsible for combining multiple
object files into a single executable file. LLD is invoked after the code
emission and generates a file by resolving symbol references, adjusting
addresses, and performing other tasks as necessary.

##  Chapter 4 RISC-V

In this project, our target is a 32-bit RISC-V core. RISC stands for reduced
instruction set computer and RISC-V is an open standard ISA. [28] It is
structured as a small base ISA and it has different additional extensions. The
base ISA is straightforward, rendering RISC-V appropriate for academic and
learning purposes, yet extensive enough to function as a cost-effective and
energy-efficient ISA for embedded systems [29]. Being open-source and royalty-
free is another significant advantage and is an important reason why RISC-V is
being commonly used. RISC-V was developed by Prof. Krste Asanović and his
students Andrew Waterman and Yunsup Lee. They started working on this project
in 2010 as a part of as part of the Parallel Computing Laboratory which was in
UC Berkeley. Par Lab was sponsored by several companies and worked on
advancing parallel computing.

###  4.1 RISC-V ISA

The ISA constitutes a part of a computer’s abstract design that defines how
the Central Processing Unit (CPU) is managed by the software. It serves as a
bridge between the software and hardware, defining the processor’s abilities
and the methods by which it performs tasks. Its level in the system can be
seen in Figure 4.1.

Figure 4.1: Level of abstraction diagram [1]

There are different base integer variants of RISC-V such as RV32I, RV64I, and
RV128I. These have address spaces of 32, 64, and 128 bits respectively [30].
In our project, we are interested in 32 bits. RISC-V has 32 general-purpose
registers. Their Application Binary Interface (ABI) names and purposes can be
seen in Figure 4.2. Also in the Figure, we can see a different set of
registers. These registers are used for floating point operations. Their ABI
and purposes are also given.

Figure 4.2: RISC-V registers [2]

###  4.2 RISC-V Base Instructions

There are four basic instruction formats in the base RV32I ISA. These are
named R, I, S, U and all of these are 32-bits in length. There are two more
additional variants named B and J as well [3]. These formats are given in
Figure 4.3.

Figure 4.3: RISC-V base instruction formats [3]

$R_{S1}$ and $R_{S2}$ are the source registers and $R_{d}$ is the destination
register. An immediate value can also be used in some of the formats. The base
instructions of the RV32I are given in Figure 4.4. By inspecting their
formats, we can see which type the instructions belong to. For example, the
ADDI instruction is an I-type instruction and XOR is an R-type instruction.

Figure 4.4: RV32I base instruction set [3]

###  4.3 RISC-V Extensions

We had mentioned the extensions previously. Abbreviations for these extensions
and what they are for are given in Figure 4.5.

Figure 4.5: List of standard extension sets [4]

Thanks to these instruction extensions, more specific tasks can be implemented
since we are not limited by the base instructions. Among these, the bit
manipulation (B) standard extension contains numerous instructions that can be
useful in a wide range of applications. This extension’s instructions mainly
operate on bits. These extensions are also divided into several groups
according to common properties. These subgroups and their purposes can be seen
in Figure 4.6.

Figure 4.6: Bit manipulation extension groupings [5]

Grouping these instructions according to how commonly they are used and the
similarity of the operations that they perform makes them more organized and
easier to work on with hardware and software. Some of these extensions are
compatible with RV64 only. The compatibilities and the groups the instructions
belong to are given in Figure 4.7.

Figure 4.7: Bit RV32/RV64 compatibilities and groups [6]

To give a clearer image of what bit manipulation (B) instructions do, a few of
them will be explained. For example, “CLZ” is an instruction for counting the
leading zeros. Its purpose is to find out how many zeros are there before
encountering a 1, starting from the most significant bit. Another example is
“ORN” instruction. It negates the second operand and performs bitwise or with
the first one.

Zba is also a subgroup of the bit manipulation extensions. Shift and add
instructions are included in this group and they perform a left shift by 1, 2,
or 3 bits since they are commonly used in codes and also because they require
only a minimal amount of extra hardware beyond that of a basic adder. This
way, lengthening the critical path in implementations can be avoided. For
example, SH1ADD is a part of this group and it shifts the operand by 1 and
adds 1 [31].

There is also a scalar cryptography instruction set extension for RISC-V. The
RISC-V Scalar Cryptography extensions allow cryptographic tasks to be
completed more quickly. Furthermore, these extensions significantly reduce the
difficulty of implementing fast and secure cryptography in embedded devices
and IoT [32]. This instruction set extension is also divided into subgroups
according to the purpose and similarity of the instructions. The groups are
given in Figure 4.8. These groups and their purposes can be explained briefly.

  * $\bullet$

Zbkb contains bit manipulation instructions for cryptography. These are a
selection of the bit manipulation extension Zbb that have specific
applications in cryptography.

  * $\bullet$

Zbkc contains carry-less multiply instructions.

  * $\bullet$

Zbkx instructions can be useful for implementing s-boxes in constant time.

  * $\bullet$

Zknd contains instructions that help speed up the decryption and key schedule
functions of the AES block cipher and Zkne does the same for encryption.

  * $\bullet$

Zknh has some instructions that can help speed up the SHA2 family of
cryptographic hash functions.

  * $\bullet$

Zksed contains instructions that speed up the SM4 block cipher.

  * $\bullet$

Zksh instructions help accelerate the SM3 hash function.

  * $\bullet$

Zkr can be useful to seed cryptographic random bit generators [33].

These extensions are supported by the compiler but pattern matching support
for Zbkb and Zbkx is incomplete in the LLVM RISC-V backend. Also for Zknd,
Zkne, Zknh, Zksed and Zksh, no pattern matching exists. Therefore, these
instructions can be only used via builtin functions or from the assembler
[34].

Figure 4.8: Cryptography extension subgroups [7]

The modular structure of these extensions is useful for hardware and software
developers. For example, the B extension is built in Clang so only an extra
argument will provide the necessary instructions from the input extension.

It is important for hardware developers to consider that developing
accelerators targeting instructions in standard extensions will reduce the
software workload significantly. The reason for this is LLVM supports RISC-V
standard extensions and follows updates closely. Corner cases are thought out
and optimization opportunities are utilized. RISC-V standard extensions are
comprehensive and may already contain the extensions that we want to
implement. After making sure that the extension we want is not present, we may
try to implement non-standard extensions.

##  Chapter 5 ASCON CRYPTOGRAPHIC ALGORITHM

ASCON (Authenticated Encryption with Associated Data) is a lightweight
encryption algorithm that is a family of lightweight authenticated ciphers.
ASCON is designed to have both authenticity and confidentiality for
transmitted data and it is efficient in terms of both speed and code size. It
has a clean and simple design, making it suitable for resource-constrained
environments. ASCON was designed by Christoph Dobraunig, Maria Eichlseder,
Florian Mendel, and Martin Schläffer in 2014. It was proposed as a candidate
for the lightweight authenticated encryption competition (CAESAR) in 2014 and
was selected as one of the finalists.

###  5.1 ASCON Structure

Ascon is based on the Sponge structure that is shown in Figure 5.1. ASCON gets
an initial input to start and encrypt the algorithm. The length of the initial
input is 320 bits which consists of five 64-bit words. Initial input includes
a secret key, initial vector and nonce. A secret key is used to encrypt and
decrypt the transmitted information. Information can be read if the key is
known thus it must be kept secret. The initial vector is a random value to
start an iterated process. Nonce increases the protection of the cipher
against cryptanalysis techniques.

Figure 5.1: Associated data and plaintext are absorbed into the sponge-based
structure

Concatenated input consists of two parts. The first r bits of the input are
the rate bits. The last c = 320 – r bits of the input are called capacity
bits. In the initialization stage, “a” rounds of permutation functions are
implemented to concatenated input. After permutation, the last 128 bits of the
capacity bits are XORed with the 128-bit secret key.

At the beginning of the associated data stage, rate bits are XORed with the
first block of the associated data then “b” rounds of permutation are
implemented to the output. This step is repeated with the previous output and
the next block of the associated data until all the blocks are covered.
Associated data is absorbed into the sponge structure. At the end of the
associated stage, capacity bits are XORed with 1’s.

In the Plaintext stage, the plaintext blocks are absorbed into the sponge-like
the associated stage and the ciphertext blocks are obtained. At the beginning
of the finalization stage, the secret key is XOR’ed with the first 128 bits of
the capacity bits. “a” rounds of permutations are implemented and the last 128
bits of the capacity bits are XORed with the secret key. The output of the
finalization stage is called the 128-bit tag.

###  5.2 Permutation Function of the ASCON Algorithm

ASCON’s permutation function consists of a nonlinear substitution layer and a
linear diffusion layer. The substitution layer performs a 5-bit S-box. S-box
takes five 64-bit concatenated words as input. 64 S-boxes are performed for
every bit of the words in a single permutation function. S-box operations are
shown in Figure 5.2. The linear diffusion layer performs the rotations and
XORs shown in Equation 5.1.

Figure 5.2: S-box operations

$\displaystyle
x_{0}\leftarrow\Sigma_{0}\left(x_{0}\right)=x_{0}\oplus\left(x_{0}\ggg
19\right)\oplus\left(x_{0}\ggg 28\right)$ (5.1) $\displaystyle
x_{1}\leftarrow\Sigma_{1}\left(x_{1}\right)=x_{1}\oplus\left(x_{1}\ggg
61\right)\oplus\left(x_{1}\ggg 39\right)$ $\displaystyle
x_{2}\leftarrow\Sigma_{2}\left(x_{2}\right)=x_{2}\oplus\left(x_{2}\ggg
1\right)\oplus\left(x_{2}\ggg 6\right)$ $\displaystyle
x_{3}\leftarrow\Sigma_{3}\left(x_{3}\right)=x_{3}\oplus\left(x_{3}\ggg
10\right)\oplus\left(x_{3}\ggg 17\right)$ $\displaystyle
x_{4}\leftarrow\Sigma_{4}\left(x_{4}\right)=x_{4}\oplus\left(x_{4}\ggg
7\right)\oplus\left(x_{4}\ggg 41\right)$

##  Chapter 6 PATH OF AN INSTRUCTION

In this chapter, the path of an instruction will be demonstrated and the
corresponding DAG input of the most critical phases of SelectionDAG will be
shown. We selected the input program as a function that performs
multiplication and addition. This was our litmus test code used while adding
MLA (Multiply and Add) instruction to the LLVM back-end with TableGen. We
explained how to modify the compiler so that it recognises MLA instruction
thoroughly in Section 7.3.

⬇

1int a,b,c;

2void maddFunc() {

3 a = 3;

4 b = 103;

5

6 c = 127;

7 a = a * b + c;

8}

Code 34: madd.c program =+*abca Figure 6.1: AST of MLA operation

###  6.1 Clang AST

The simplified AST of the expression is shown in Figure 6.1. The AST consists
of an expression tree with three levels. At the highest level, there is an
expression tree of multiplication between variables ’a’ and ’b’. This
expression tree’s result becomes an argument for another expression tree with
the addition operator. The second argument at this addition subtree is the
variable ’c’. The expression tree at the root has assignment as an operator.
The first argument to this tree is ’a’ and the second argument is the result
of multiplication and addition. Figure 6.2 shows the AST output of Clang for
Code 34.

Figure 6.2: AST generated by Clang

###  6.2 LLVM IR

Clang CodeGen produces LLVM IR with the AST as the input. Figure 35 shows the
produced LLVM IR. The optimized LLVM IR is the input to SelectionDAG to
generate target-specific instructions.

⬇

1define void @maddFunc() {

2 store i32 3, i32* @a

3 store i32 103, i32* @b

4 store i32 127, i32* @c

5 %1 = load i32, i32* @a

6 %2 = load i32, i32* @b

7 %5 = mul nsw i32 %1, %2

8 %4 = load i32, i32* @c

9 %5 = add nsw i32 %3, %4

10 store i32 %5, i32* @a

11 ret void

12}

Code 35: LLVM IR file generated at the output of Clang

###  6.3 SelectionDAG

Input DAGs to SelectionDAG’s passes will be demonstrated so on. The following
phases will be demonstrated:

  1. 1.

First Optimization

  2. 2.

Legalization

  3. 3.

Second Optimization

  4. 4.

Instruction Selection

  5. 5.

Instruction Scheduling

  6. 6.

Register Allocation

####  6.3.1 First Optimization Pass

Figure 6.3 shows the DAG before the first optimization pass. It is the direct
translation of LLVM IR to DAG form. After optimization, redundant nodes will
be removed such as "Constant<0>" node.

Figure 6.3: DAG before first optimization pass

Figure 6.4 shows the DAG before legalization. The first optimization took
place by removing nodes that do not contribute to the DAG. However, the
instructions are not, in LLVM terms, "legal" as these general SDNodes do not
map directly to every target’s instructions.

####  6.3.2 Instruction Legalization

Figure 6.4: DAG before Legalization

Figure 6.5 shows the DAG before the second optimization pass. The DAG is
legalized by introducing RISCVISD::ADD_LO and RISCVISD::HI nodes. These
SDnodes act as flags to give target-specific information to target-independent
algorithms. These definitions are introduced at
lib/Target/RISCV/RISCVISelLowering.h file [35]. It is the RISCV DAG lowering
interface.

According to the interface file, RISCVISD::ADD_LO is meant to add Lo 12 bits
from an address and to be replaced by ADDI (Add Immediate) at Instruction
Selection. Similarly, RISCVISD::HI is meant to get Hi 20 bits from an address
and to be replaced by LUI (Load Upper Immediate). With a legalized DAG the
second optimization pass begins.

####  6.3.3 Second Optimization Pass

Figure 6.5: DAG before the second optimization

Figure 6.6 shows the DAG before the Instruction Selection phase. A comparison
of Figure 6.5 and 6.6 indicates that the second optimization did not change
the DAG. This may be due to the reason that the subgraphs including the
legalized nodes are not complex enough as the input C code is minimal.

The DAG nodes up until Instruction Selection are instances of SDNode class
which are target-independent nodes.

Figure 6.6: DAG before Instruction Selection

####  6.3.4 Instruction Selection

Figure 6.7 shows the DAG before the Instruction Scheduling phase. You can see
that the instructions are selected according to the RISC-V target. SDNode
class nodes are replaced by MachineSDNode class nodes which are target-
specific.

RISCVISD nodes are replaced by their counterparts. The general Load and Store
instructions are replaced by their type-aware corresponding LW (Load Word) and
SW (Store Word) instructions. Most importantly the MLA instruction is selected
replacing the subgraph of ’mul’ and ’add’ LLVM instructions.

Our pattern definition of MLA instruction declares operand relations as in the
subgraph. The instruction selection phase took it as a reference, detected the
pattern inside the global DAG, and used it to place the MLA node. The pattern
definition process is explained thoroughly in Section 7.3.

Figure 6.7: DAG before Instruction Scheduling

####  6.3.5 Instruction Scheduling

The DAG is transformed into a target-specific DAG with the result of
legalization and selection phases. However, to generate a linear byte
sequence, the DAG must be flattened. The instruction scheduling phase gets the
DAG and linearises it according to the dependency graph of nodes. The
scheduling dependency can be seen in Figure 6.8. Chain edges are used to show
dependencies between instructions where one instruction cannot be placed
before the other.

Figure 6.8: Scheduling Dependency Graph

####  6.3.6 Machine Instruction in SSA Form

The generated Machine Instruction as a result of scheduling is shown in Figure
6.9. Because register allocation is not yet performed, the instructions are in
SSA form. In SSA form, virtual registers are considered to be infinite unless
some specific registers have to be used. In this case, ’$x0’ is mentioned with
ADDI instructions as they are hardwired zero in RISC-V.

Figure 6.9: Machine Instruction before Register Allocation

###  6.4 Machine Code Instruction

After register allocation, a Machine Code Instruction (MCInst) representation
of the code is created. MCInst can be thought of as an IR of the lower-level
code. It can be used to produce both an object file and an Assembly file. The
generated Assembly is presented below:

⬇

1 maddFunc:

2# %

3 addi sp, sp, -16

4.Ltmp0:

5 sw ra, 12(sp)

6 sw s0, 8(sp)

7 addi s0, sp, 16

8 lui a0, %

9 li a1, 3

10 sw a1, %

11 lui a1, %

12 li a2, 103

13 sw a2, %

14 lui a2, %

15 li a3, 127

16 sw a3, %

17 lw a3, %

18 lw a1, %

19 lw a2, %

20 mla a1, a3, a1 ,a2

21 sw a1, %

22 lw ra, 12(sp)

23 lw s0, 8(sp)

24 addi sp, sp, 16

25 ret

Code 36: madd.s Assembly Output

##  Chapter 7 ADDING CUSTOM INSTRUCTIONS

The instruction selection system we focused on at the back end of the LLVM
compiler is SelectionDAG among FastISel and GlobalIsel. SelectionDAG is the
most mature Instruction Selection framework with more target support. However,
shortly it is worth considering GlobalISel as it is developed recently as an
alternative to SelectionDAG. The reasons to replace it are to make it faster,
smaller, more testable and open to low-level optimizations.

###  7.1 TableGen Reference

TableGen is a domain-specific language used in the LLVM back end side to
generate CPP header files. The purpose it serves is that it removes the
redundancy of instruction declaration code which can be common to numerous
architectures with minor differences. To maintain and scale the framework the
minor differences are implemented level by level at a series of inheritance
operations between TableGen classes.

LLVM Static Compiler, LLC, is responsible for converting LLVM IR to Assembly
codes. To add new instructions, changes are made in TableGen files and LLC is
recompiled. During the compilation operation of the LLC program, TableGen
records are created which declare every instruction’s encoding and describe
its features. Referring to the records, DAGs are used in the process of
instruction selection. DAG is a graph structure that has no cycles and has
directions on the edges.

Operations or functions are represented as nodes in the DAG. They are critical
parts of declaring the logic or pattern of the new instruction.

The operations represented on the DAG can be LLVM intrinsics as well as
instructions. LLVM instructions resemble conventional assembly instructions,
in contrast, LLVM intrinsics have higher level abstraction depending on their
functionality. Their instruction generation may vary depending on the target
hardware. It is possible to define a new complicated instruction either by
combining simple LLVM instructions and higher-level intrinsics in the DAG
level or by creating a new LLVM intrinsic which gets created at the
Intermediate Level of the compilation process.

###  7.2 RISC-V TableGen Classes

The most general instruction class used for every target architecture is the
“InstructionEncoding” TableGen class defined in
llvm/include/llvm/Target/Target.td. This class holds the decoder method and
size of instruction in addition to minor variables. It gets inherited by the
generic “Instruction” class which is defined in the same class. This class
holds input and output DAGs and information which is useful to the compiler
and is generalizable to all architectures.

The general class gets inherited by every target-specific class. In RISC-V’s
case, the next stop of the instruction is the “RVInst” class which inherits
from the general “Instruction” class and it resides in
llvm/lib/Target/RISCV/RISCVInstrFormats.td TableGen file. It defines the
general bit patterns of RISC-V instructions. For example, the opcode being the
first 7 bits. It defines additional information like the assembly string
pattern. This general class is inherited by every type of instruction of R, I,
S, B, U, and J types. As a simple example, XOR instruction can be traced. As
XOR is an R type, a register-register instruction, it continues its
inheritance journey from “RVInstR”. It is common to R type instructions to
have funct7, rs2, rs1, funct3, and rd format ordered from most significant bit
(MSB) to least significant bit (LSB). These variables are assigned
corresponding bit fields in the class.

The RISC-V formats mentioned are included in the
llvm/lib/Target/RISCV/RISCVInstrInfo.td file which is in the same directory as
the RISCVInstrFormats.td file. After inclusion, the “RVInstR” class gets
inherited by the “ALU_rr” class. The “ALU_rr” class adds the commutability
feature which means swapping source 1 and source 2 does not create a different
result like in addition but not in subtraction. In the end, XOR’s record is
defined by putting funct7, funct3 and assembly string manually in a single
line with scheduling information added.

###  7.3 Adding a New Instruction Using TableGen

This section will guide the reader in introducing new instructions via
TableGen. Create a new TableGen file for custom additions and include it at
the end of the RISCVInstrInfo.td file. We named it RISCVInstrInfoCrypt.td as
it is going to be cryptography related.

⬇

1include "RISCVInstrInfoCrypt.td"

Code 37: Include file

The specifications of the instruction will be added to the
RISCVInstrInfoCrypt.td file.

####  7.3.1 Introducing the ALU_rrr TableGen Class

Here we created a new class of instruction named ALU_rrr. MLA instruction
requires three source registers and is defined to be ALU type so the
specifications are:

⬇

1let hasSideEffects = 0, mayLoad = 0, mayStore = 0 in

2class ALU_rrr<bits<2> funct2, bits<3> funct3, string opcodestr,

3 bit Commutable = 0>

4 : RVInstR4<funct2, funct3, OPC_OP,

5 (outs GPR:$rd), (ins GPR:$rs1, GPR:$rs2, GPR:$rs3),

6 opcodestr, "$rd, $rs1, $rs2 ,$rs3"> {

7 let isCommutable = Commutable;

8}

Code 38: ALU_rrr class definition

The class is wrapped with three flags:

⬇

1let hasSideEffects = 0, mayLoad = 0, mayStore = 0 in

  * $\bullet$

If the instruction has no side effect, hasSideEffects will be 0.

  * $\bullet$

If there is no need or possibility to load data from memory, mayLoad will be
0.

  * $\bullet$

If there is no need or possibility to store data from memory, mayStore will be
0.

Here you can see class arguments:

⬇

1class ALU_rrr<bits<2> funct2, bits<3> funct3, string opcodestr,

2 bit Commutable = 0>

Class is defined with ALU_rrr name. Variables are defined. funct2 is a two-bit
binary number as RVInstR4 is used which reserves 5 bits of funct7 for another
register. funct3 is a three-bit binary number. opcodestr is the string that
will be shown in the assembly file. Commutable is a zero bit which determines
the importance of the order of the inputs.

⬇

1: RVInstR4<funct2, funct3, OPC_OP,

2(outs GPR:$rd), (ins GPR:$rs1, GPR:$rs2, GPR:$rs3),

RVInstR4 instruction type is called from RISCVInstrFormats.td file. funct2,
funct3, opcode, output and inputs are given as arguments to the higher class
in order.

⬇

1opcodestr, "$rd, $rs1, $rs2 ,$rs3"> {

2 let isCommutable = Commutable;

3}

Opcode string used for Assembly and activating commutability option.

####  7.3.2 Introducing the MLA Instruction for Assembler Support

The definition of the instruction can now be added using the ALU_rrr class
defined above and by choosing the correct scheduling variables. For the MLA
instruction, it is:

⬇

1def MLA : ALU_rrr<0b10, 0b100, "mla">,

2Sched<[WriteIMul, ReadIMul, ReadIMul]>;

MLA instruction is defined and ALU_rrr instruction type is used.
funct2,funct3, opcode string and schedules are sufficient to have the full
definition of the instruction thanks to the custom ALU_rrr class.

####  7.3.3 Introducing the MLA Instruction for Pattern Matching Support

Add the instruction’s pattern defining source to the target custom instruction
transformation. For the MLA instruction, it is:

⬇

1def : Pat< (add (mul GPR:$src1, GPR:$src2), GPR:$src3),

2(MLA GPR:$src1, GPR:$src2, GPR:$src3)>;

Note that it is possible to define more patterns to introduce optimizations.
There can be multiple source patterns for the same target pattern. The target
pattern can also be a tree of SDNodes containing the custom instruction.

###  7.4 Adding Pattern Matching Support for New Instruction Using C++ in
SelectionDAG

TableGen aims to provide a declarative way to introduce new patterns for new
instruction developers. However, not all instructions can be described in this
scheme. Although it is called "dag" as a keyword in TableGen, it expects a
tree of instructions. For certain use cases, custom C++ can be the only way to
match until the TableGen based system improves. It is also possible to use C++
in complex patterns together with TableGen, which can make the most of the
pattern declarative and only the necessary part in imperative style.

A domain that TableGen fails is matching a graph of instructions with
dependant operands. As an example, we can think of an instruction having two
operands of Load Instructions. If the Load instructions are from an array,
they must be related to each other by an offset and it might need to be
detected for certain patterns.

⬇

1define void @sbox(ptr %0) {

2 %2 = getelementptr inbounds [5 x i32], ptr %0, i32 0, i32 4

3 %3 = load i32, ptr %2

4 %4 = load i32, ptr %0

5 %5 = xor i32 %4, %3

Code 39: Minimal Subtree of Optimized S-box LLVM IR

In Code 39, it can be seen that the XOR instruction is between the first
element of the input struct and the fifth element of it. As the locations of
elements matter, they must be matched by not only looking at Load instructions
but also their operands. What we are looking for is to have the base of Load
instruction to be equal and the offset operand of it to evaluate to 4,
designating the fifth element of the struct. TableGen is not suitable for this
operation and the source code of SelectionDAG’s RISC-V backend should be
analyzed to place the logic to pattern match this set of instructions.

The process for adding an instruction via C++ is as follows:

  1. 1.

Create a record declaration in TableGen to provide the Assembler support,
ignoring the Pattern declaration.

  2. 2.

Observe the DAG in the debug output or dot file and locate the root of it.

  3. 3.

Add a function in RISCVISelDAGToDAG.cpp file in the root instruction case.

  4. 4.

Implement pattern matching and replacement with SDnode.

SelectionDAG consists of numerous files but the most relevant ones to the
developer can be few if the complexity of the pattern is small. The order of
files will be from IR to Assembly. RISCVCodeGenPrepare.cpp file provides
mechanisms for matching in IR form. This file exists mainly due to the
limitation of SelectionDAG which is running per basic block.
RISCVISelLowering.cpp contains the lowering of IR to SDnodes. It can decide on
whether a type or expression should be legalized or expanded.
RISCVISelDAGToDAG.cpp is the instruction selector in C++. Its implementation
traverses the DAG from the root and runs the selection functions depending on
the SDnode type which is parallel to instructions.

⬇

3 t0: ch,glue = EntryToken

4 t2: i32,ch = CopyFromReg t0, Register:i32 %0

8 t8: i32,ch = load<(load (s32) from %ir.0, !tbaa !7)> t0, t2, undef:i32

9 t4: i32 = add nuw t2, Constant:i32<16>

13 t7: i32,ch = load<(load (s32) from %ir.2, !tbaa !7)> t0, t4, undef:i32

16 t9: i32 = xor t8, t7

Code 40: The corresponding Optimized and Legalized DAG of Code 39

In an attempt to match the three instructions in Code 39, the DAG in Code 40
is analyzed. The first remark is that "getelementptr" is converted to an add
instruction which calculates the offset. Another remark is that the load
instructions have the same base address in the first operand as expected
pointing to the same node. If the pattern is large, we can introduce a new
function which will contain the logic. The function’s prototype should be
added to the corresponding header file.

⬇

1void RISCVDAGToDAGISel::Select(SDNode *Node) {

2 .

3}

4 .

5switch (Opcode) {

6 .

7 .

8 case ISD::XOR:{

9 if (tryShrinkShlLogicImm(Node))

10 return;

11 if (selectSbox(Node))

12 return;

13 break;

14 }

15}

Code 41: Introduction of New Function for Pattern Matching in C++

The C++ logic for matching this pattern is provided below.

⬇

1bool RISCVDAGToDAGISel::selectSBox(SDNode *Node) {

2 SDValue LOAD0 = Node->getOperand(0);

3 SDValue LOAD1 = Node->getOperand(1);

4 //Check if there is a load pair

5 if(LOAD0.getOpcode() != ISD::LOAD

6 || LOAD1.getOpcode() != ISD::LOAD)

7 return false;

8 SDValue LOAD0_op0 = LOAD0.getOperand(0);

9 SDValue LOAD0_op1_offset = LOAD0.getOperand(1); // t0

10

11 SDValue LOAD1_op0 = LOAD1.getOperand(0);

12 SDValue LOAD1_op1_offset = LOAD1.getOperand(1);

13

14 if(LOAD1_op1_offset.getOpcode() != ISD::ADD)

15 return false;

16

17 if(LOAD1_op0 != LOAD0_op0)

18 return false;

19

20 //Check if the addendum0 is the same as the second

21 SDValue LOAD1_op1_off_Addend0 = LOAD1_op1_offset.getOperand(0);

22 if(LOAD1_op1_off_Addend0 != LOAD0_op1_offset)

23 return false;

24

25 SDValue LOAD1_op1_off_Addend1 = LOAD1_op1_offset.getOperand(1);

26

27 auto *LOAD1_op1_offset_Addendum1C =

28 dyn_cast<ConstantSDNode>(LOAD1_op1_offset_Addendum1);

29 if(!LOAD1_op1_offset_Addendum1C)

30 return false;

31 //Check if addendum1 is 16 more than first load offset

32 if(LOAD1_op1_offset_Addendum1C->getZExtValue() != 16)

33 return false;

34

35 //Pattern is matched replace here

36

37 return true;

38}

Code 42: C++ logic for Pattern Matching the DAG in Code 40

The logic starts from the root of the DAG which in this case is XOR
instruction or the ISD::XOR SDnode. Then we iterate through its leaves and
check the distinctive features of the pattern. In this pattern, we are
interested in the distance of offset addresses of Load instructions so we
progressively approach them by assuming the pattern holds and quitting if not.
Progressive checking is a common theme in LLVM and as Instruction Selection is
one of the stages affecting the compilation times significantly, patterns
should not be checked in a single if statement by logical combinations.

The checks, if statements are doing can be summarised in steps. As the
function only runs when the instruction selection finds an XOR SDNode, the
root can be assumed as XOR safely.

  1. 1.

Check if both the operands are Load instructions.

  2. 2.

Check if the second Load instruction has an Add instruction in its second
operand

  3. 3.

Check if the base offset of the first load and the first addendum of the
second load are the same, as they should point to the beginning of the struct.

  4. 4.

Check if the second addendum is a constant.

  5. 5.

Check if the unsigned value of constant second addendum is equal to 16.

At this point, it can be safely assumed that the only XOR that conforms to the
pattern can be in this line of program. SelectionDAG provides more API to
simply replace the nodes in that pattern with the custom instruction.

To interact with the DAG, SelectionDAG’s API is used. We encourage the
developers to read the source code and learn to use the public functions
exposed by SelectionDAG in order to interact with the DAG most effectively.
RISCVISelDAGToDAG.cpp file already has many instruction selection mechanisms
in place which can be read through.

###  7.5 Discussion of Pattern Matching in Other Stages of the Compiler

Pattern Matching can be assumed to mainly be an Instruction Selection problem
where the pattern will be simply identified and replaced. However, when we
take a look at the baseline problem any Compiler technology solves, it is to
convert more familiar patterns in some language to a more unfamiliar pattern
in machine language. Also, this conversion occurs in a large number of steps
through optimization in IR form as discussed in Section 3.2, to DAG formation
in SelectionDAG to MCInstr form down the pipeline. Their data structures can
differ in representing the instructions which can make some pattern matching
schemes to be more fragile than others. Also, as the lowering gets performed
high-level information about the program is lost but the formation gets closer
to the final output of Assembly.

For simple cases where for example a combination of R-type instructions will
be matched and replaced, Instruction Selection might be the most convenient
stage to extend. However if the pattern requires the instruction selection to
be performed already, pattern match can be done in the MC layer. On the
contrary, if higher level information of the pattern is required, a pattern
can be matched to an intrinsic function at the IR level.

Another reason to consider different stages is that there can be multiple
patterns mapped to the same instruction. Further optimization opportunities
can rise in further stages.

####  7.5.1 Case Study: SH1ADD in SelectionDAG and MC Layer

It was discussed that dealing with the lowered DAG to MC layer can provide
more optimization opportunities. In this section, the case of "SH1ADD"
instruction which is ratified in the RISC-V Zba extension will be analyzed.
The instruction shifts rs1 left by one, adds rs2 and writes to rd. Its
encoding and pattern in the standard implementation of LLVM in TableGen are as
follows:

⬇

1let Predicates = [HasStdExtZba] in {

2def SH1ADD : ALU_rr<0b0010000, 0b010, "sh1add">,

3 Sched<[WriteSHXADD, ReadSHXADD, ReadSHXADD]>;

4def SH2ADD : ALU_rr<0b0010000, 0b100, "sh2add">,

5 Sched<[WriteSHXADD, ReadSHXADD, ReadSHXADD]>;

6def SH3ADD : ALU_rr<0b0010000, 0b110, "sh3add">,

7 Sched<[WriteSHXADD, ReadSHXADD, ReadSHXADD]>;

8} // Predicates = [HasStdExtZba]

Code 43: Instruction Encoding of the Instructions

As the SH2ADD and SH3ADD have similar implementations to SH1ADD their patterns
will be stripped.

⬇

1let Predicates = [HasStdExtZba] in {

2def : Pat<(add (shl GPR:$rs1, (XLenVT 1)), non_imm12:$rs2),

3 (SH1ADD GPR:$rs1, GPR:$rs2

4

5// More complex cases use a ComplexPattern.

6def : Pat<(add sh1add_op:$rs1, non_imm12:$rs2),

7 (SH1ADD sh1add_op:$rs1, GPR:$rs2)>;)>;

8

9def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 6)), GPR:$rs2),

10 (SH1ADD (SH1ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;

11def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 10)), GPR:$rs2),

12 (SH1ADD (SH2ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;

13def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 18)), GPR:$rs2),

14 (SH1ADD (SH3ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;

Code 44: Instruction Pattern of the Instructions

We can observe that ComplexPattern’s are used to enable using C++ together
with TableGen. The Complex Pattern’s TableGen declarations are provided below:

⬇

1

2def sh1add_op : ComplexPattern<XLenVT, 1,

3 "selectSHXADDOp<1>", [], [], 6>;

4

5class binop_oneuse<SDPatternOperator operator>

6 : PatFrag<(ops node:$A, node:$B),

7 (operator node:$A, node:$B), [{

8 return N->hasOneUse();

9}]>;

10

11def mul_oneuse : binop_oneuse<mul>;

Code 45: TableGen Declaration of ComplexPatterns

"selectSHXADDOp" is a template function which provides the shift amount
argument.

⬇

1

2bool selectSHXADDOp(SDValue N, unsigned ShAmt, SDValue &Val);

3template <unsigned ShAmt> bool

4 selectSHXADDOp(SDValue N, SDValue &Val) {

5return selectSHXADDOp(N, ShAmt, Val);

6}

Code 46: Template Function of the ComplexPattern for "sh1add_op"

The C++ logic can be found in RISCVISelDAGToDAG.cpp file, the implementation
will be reduced to the patterns described in the comments:

⬇

1/// Look for various patterns that can be done with a SHL that can be

2/// folded into a SHXADD. \p ShAmt contains 1, 2, or 3 and is set based

3/// on which SHXADD we are trying to match.

4bool RISCVDAGToDAGISel::selectSHXADDOp(SDValue N, unsigned ShAmt,

5 SDValue &Val) {

6 if (N.getOpcode() == ISD::AND

7 && isa<ConstantSDNode>(N.getOperand(1))) {

8 SDValue N0 = N.getOperand(0);

9

10 bool LeftShift = N0.getOpcode() == ISD::SHL;

11 if ((LeftShift || N0.getOpcode() == ISD::SRL) &&

12 isa<ConstantSDNode>(N0.getOperand(1))) {

13 uint64_t Mask = N.getConstantOperandVal(1);

14 unsigned C2 = N0.getConstantOperandVal(1);

15

16 unsigned XLen = Subtarget->getXLen();

17 if (LeftShift)

18 Mask &= maskTrailingZeros<uint64_t>(C2);

19 else

20 Mask &= maskTrailingOnes<uint64_t>(XLen - C2);

21

22 // Look for (and (shl y, c2), c1) where c1 is a shifted mask

23 // with no leading zeros and c3 trailing zeros. We can use an

24 // SRLI by c2+c3 followed by a SHXADD with c3 for the X amount.

25 ...

26 // Look for (and (shr y, c2), c1) where c1 is a shifted mask

27 // with c2 leading zeros and c3 trailing zeros. We can use an

28 // SRLI by C3 followed by a SHXADD using c3 for the X amount.

29 ...

30 }

31 }

32 }

33

34 bool LeftShift = N.getOpcode() == ISD::SHL;

35 if ((LeftShift || N.getOpcode() == ISD::SRL) &&

36 isa<ConstantSDNode>(N.getOperand(1))) {

37 SDValue N0 = N.getOperand(0);

38 if (N0.getOpcode() == ISD::AND && N0.hasOneUse() &&

39 isa<ConstantSDNode>(N0.getOperand(1))) {

40 uint64_t Mask = N0.getConstantOperandVal(1);

41 if (isShiftedMask_64(Mask)) {

42 unsigned C1 = N.getConstantOperandVal(1);

43 unsigned XLen = Subtarget->getXLen();

44 unsigned Leading = XLen - llvm::bit_width(Mask);

45 unsigned Trailing = llvm::countr_zero(Mask);

46 // Look for (shl (and X, Mask), C1) where Mask has 32 leading

47 // zeros and C3 trailing zeros.

48 // If C1+C3==ShAmt we can use SRLIW+SHXADD.

49 ...

50 // Look for (srl (and X, Mask), C1) where Mask has 32 leading

51 // zeros and C3 trailing zeros.

52 // If C3-C1==ShAmt we can use SRLIW+SHXADD.

53 ...

54 }

55 }

56 }

57 return false;

58}

Code 47: Implementation of the ComplexPattern for "sh1add_op"

Despite using TableGen and SelectionDAG, there is an optimization opportunity
for "SH1ADD" in MCInst form. It is done in immediate materialization where a
constant node in the DAG representation is not converted to instructions until
needed. In the MCTargetDesc/RISCVMatInt.cpp file, an optimization for
representing immediates is provided as follows:

⬇

1namespace llvm::RISCVMatInt {

2InstSeq generateInstSeq(int64_t Val,

3 const FeatureBitset &ActiveFeatures) {

4 RISCVMatInt::InstSeq Res;

5 generateInstSeqImpl(Val, ActiveFeatures, Res);

6 ...

7

8// Perform optimization with SH*ADD in the Zba extension.

9 if (Res.size() > 2 && ActiveFeatures[RISCV::FeatureStdExtZba]) {

10 int64_t Div = 0;

11 unsigned Opc = 0;

12 RISCVMatInt::InstSeq TmpSeq;

13 // Select the opcode and divisor.

14 if ((Val %

15 Div = 3;

16 Opc = RISCV::SH1ADD;

17 } else if ((Val %

18 Div = 5;

19 Opc = RISCV::SH2ADD;

20 } else if ((Val %

21 Div = 9;

22 Opc = RISCV::SH3ADD;

23 }

24 // Build the new instruction sequence.

25 if (Div > 0) {

26 generateInstSeqImpl(Val / Div, ActiveFeatures, TmpSeq);

27 TmpSeq.emplace_back(Opc, 0);

28 if (TmpSeq.size() < Res.size())

29 Res = TmpSeq;

30 } else {

31 // Try to use LUI+SH*ADD+ADDI.

32 int64_t Hi52 = ((uint64_t)Val + 0x800ull) & ~0xfffull;

33 int64_t Lo12 = SignExtend64<12>(Val);

34 Div = 0;

35 if (isInt<32>(Hi52 / 3) && (Hi52 %

36 Div = 3;

37 Opc = RISCV::SH1ADD;

38 } else if (isInt<32>(Hi52 / 5) && (Hi52 %

39 Div = 5;

40 Opc = RISCV::SH2ADD;

41 } else if (isInt<32>(Hi52 / 9) && (Hi52 %

42 Div = 9;

43 Opc = RISCV::SH3ADD;

44 }

45 // Build the new instruction sequence.

46 if (Div > 0) {

47 // For Val that has zero Lo12 (implies Val equals to Hi52)

48 // should has already been processed to LUI+SH*ADD

49 // by previous optimization.

50 generateInstSeqImpl(Hi52 / Div, ActiveFeatures, TmpSeq);

51 TmpSeq.emplace_back(Opc, 0);

52 TmpSeq.emplace_back(RISCV::ADDI, Lo12);

53 if (TmpSeq.size() < Res.size())

54 Res = TmpSeq;

55 }

56 }

57 }

Code 48: Immediate Materialization for "SH1ADD"

By using "SH1ADD" in immediate materialization, a single instruction can be
used instead of two. It can be checked that in the standard testing suite,
there is the following function which returns a 64-bit integer:  ⬇ 1define i64
@PR54812() { 2; RV64I-LABEL: PR54812: 3; RV64I: # % 4; RV64I-NEXT: lui a0,
1048447 5; RV64I-NEXT: addiw a0, a0, 1407 6; RV64I-NEXT: slli a0, a0, 12 7;
RV64I-NEXT: ret 8; 9; RV64IZBA-LABEL: PR54812: 10; RV64IZBA: # % 11; RV64IZBA-
NEXT: lui a0, 872917 12; RV64IZBA-NEXT: sh1add a0, a0, a0 13; RV64IZBA-NEXT:
ret 14; 15 ret i64 -2158497792; 16} Code 49: Function for Immediate
Materialization In the FileCheck lines which are explained in Section 9.2, we
can see the Assembly lines that should be emitted. It can be observed that the
desired immediate can be obtained with "sh1add" in fewer instructions.

####  7.5.2 Case Study: ROR in SelectionDAG and IR Level

In LLVM, rotation instruction which is shifting and feeding the carry back to
the shift point is captured at the IR level. To match in IR level, a new
intrinsic function is defined in TableGen. TableGen is not only used in
instruction selection, it is used wherever a declarative form is better suited
such as in IR or MLIR levels.

⬇

1//===-------------------- Bit Manipulation Intrinsics \---------===//

2//

3

4// None of these intrinsics accesses memory at all.

5let IntrProperties = [IntrNoMem, IntrSpeculatable, IntrWillReturn]

6 in {

7 def int_bswap: DefaultAttrsIntrinsic<[llvm_anyint_ty],

8 [LLVMMatchType<0>]>;

9 def int_ctpop: DefaultAttrsIntrinsic<[llvm_anyint_ty],

10 [LLVMMatchType<0>]>;

11 def int_bitreverse: DefaultAttrsIntrinsic<[llvm_anyint_ty],

12 [LLVMMatchType<0>]>;

13 def int_fshl : DefaultAttrsIntrinsic<[llvm_anyint_ty],

14 [LLVMMatchType<0>, LLVMMatchType<0>, LLVMMatchType<0>]>;

15 def int_fshr : DefaultAttrsIntrinsic<[llvm_anyint_ty],

16 [LLVMMatchType<0>, LLVMMatchType<0>, LLVMMatchType<0>]>;

17}

Code 50: Funnel Shift Intrinsic Definition

’fshr’ is defined as funnel shift right intrinsic function [36]. It is matched
in IR optimizations by InstCombine pass.

⬇

1/// Match UB-safe variants of the funnel shift intrinsic.

2static Instruction *matchFunnelShift(Instruction &Or,

3 InstCombinerImpl &IC){

4 unsigned Width = Or.getType()->getScalarSizeInBits();

5

6 // First, find an or’d pair of opposite shifts:

7 // or (lshr ShVal0, ShAmt0), (shl ShVal1, ShAmt1)

8 BinaryOperator *Or0, *Or1;

9 if (!match(Or.getOperand(0), m_BinOp(Or0)) ||

10 !match(Or.getOperand(1), m_BinOp(Or1)))

11 return nullptr;

12

13 Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;

14 if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal0),

15 m_Value(ShAmt0)))) ||

16 !match(Or1, m_OneUse(m_LogicalShift(m_Value(ShVal1),

17 m_Value(ShAmt1)))) ||

18 Or0->getOpcode() == Or1->getOpcode())

19 return nullptr;

20

21 // Canonicalize to or(shl(ShVal0, ShAmt0), lshr(ShVal1, ShAmt1)).

22 if (Or0->getOpcode() == BinaryOperator::LShr) {

23 std::swap(Or0, Or1);

24 std::swap(ShVal0, ShVal1);

25 std::swap(ShAmt0, ShAmt1);

26 }

27

28 // Match the shift amount operands for a funnel shift pattern.

29 // This always matches a subtraction on the R operand.

30 auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width)

31 -> Value * {

32 // Check for constant shift amounts that sum to the bitwidth.

33 ...

34

35 return nullptr;

36 };

37

38 Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, Width);

39 bool IsFshl = true; // Sub on LSHR.

40 if (!ShAmt) {

41 ShAmt = matchShiftAmount(ShAmt1, ShAmt0, Width);

42 IsFshl = false; // Sub on SHL.

43 }

44 if (!ShAmt)

45 return nullptr;

46

47 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;

48 Function *F = Intrinsic::getDeclaration(Or.getModule(), IID,

49 Or.getType());

50 return CallInst::Create(F, {ShVal0, ShVal1, ShAmt});

51}

Code 51: Funnel Shift Right Pattern Matching

The pattern matching API is provided by IR/PatternMatch.h file. After the
pattern for rotation and the shift amount are matched the corresponding
intrinsic function is called.

The function is called in OR visiting function, so the root of the pattern is
OR:

⬇

1Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {

2 ...

3 if (Instruction *Funnel = matchFunnelShift(I, *this))

4 return Funnel;

5 ...

6 return nullptr;

7}

Code 52: Funnel Shift Right Pattern Function Called

The intrinsic function is converted to ROTR SDnode in the general
SelectionDAGBuilder.cpp file.

⬇

1/// Lower the call to the specified intrinsic function.

2void SelectionDAGBuilder::visitIntrinsicCall(const CallInst &I,

3 unsigned Intrinsic) {

4 const TargetLowering &TLI = DAG.getTargetLoweringInfo();

5 SDLoc sdl = getCurSDLoc();

6 DebugLoc dl = getCurDebugLoc();

7 SDValue Res;

8

9 SDNodeFlags Flags;

10 if (auto *FPOp = dyn_cast<FPMathOperator>(&I))

11 Flags.copyFMF(*FPOp);

12

13 switch (Intrinsic) {

14 default:

15 // By default, turn this into a target intrinsic node.

16 visitTargetIntrinsic(I, Intrinsic);

17 return;

18 ...

19

20 case Intrinsic::fshl:

21 case Intrinsic::fshr: {

22 bool IsFSHL = Intrinsic == Intrinsic::fshl;

23 SDValue X = getValue(I.getArgOperand(0));

24 SDValue Y = getValue(I.getArgOperand(1));

25 SDValue Z = getValue(I.getArgOperand(2));

26 EVT VT = X.getValueType();

27

28 if (X == Y) {

29 auto RotateOpcode = IsFSHL ? ISD::ROTL : ISD::ROTR;

30 setValue(&I, DAG.getNode(RotateOpcode, sdl, VT, X, Z));

31 } else {

32 auto FunnelOpcode = IsFSHL ? ISD::FSHL : ISD::FSHR;

33 setValue(&I, DAG.getNode(FunnelOpcode, sdl, VT, X, Y, Z));

34 }

35 return;

36 }

37 ...

38}

Code 53: Funnel Shift Intrinsic converted to ROTL

The intrinsic functions can be defined as target-specific or target
independent. "fshl" is a general intrinsic function and targets can either
expand it by replacing it with its equivalent instructions or lower it
directly to an instruction by legalizing it. RISC-V Zbb extension supports
bitwise rotation so LLVM has the extension’s implementation in the source. In
RISCVISelLowering.cpp file the legalization of "ROTR" is managed regarding
whether the extension is enabled or disabled.

⬇

1RISCVTargetLowering::RISCVTargetLowering(const TargetMachine &TM,

2 const RISCVSubtarget &STI)

3 : TargetLowering(TM), Subtarget(STI) {

4 ...

5 if (Subtarget.hasStdExtZbb() || Subtarget.hasStdExtZbkb() ||

6 Subtarget.hasVendorXTHeadBb()) {

7 if (Subtarget.is64Bit())

8 setOperationAction({ISD::ROTL, ISD::ROTR}, MVT::i32, Custom);

9 } else {

10 setOperationAction({ISD::ROTL, ISD::ROTR}, XLenVT, Expand);

11 }

12 ...

13}

Code 54: ROTR Legalization Conditional

The "Custom" action is defined in TableGen in RISCVInstrInfoZb.td file as well
as instruction encodings.

⬇

1def riscv_rolw : SDNode<"RISCVISD::ROLW", SDT_RISCVIntBinOpW>;

2def riscv_rorw : SDNode<"RISCVISD::RORW", SDT_RISCVIntBinOpW>;

3...

4let Predicates = [HasStdExtZbbOrZbkb] in {

5def ROL : ALU_rr<0b0110000, 0b001, "rol">,

6 Sched<[WriteRotateReg, ReadRotateReg, ReadRotateReg]>;

7def ROR : ALU_rr<0b0110000, 0b101, "ror">,

8 Sched<[WriteRotateReg, ReadRotateReg, ReadRotateReg]>;

9

10def RORI : RVBShift_ri<0b01100, 0b101, OPC_OP_IMM, "rori">,

11 Sched<[WriteRotateImm, ReadRotateImm]>;

12} // Predicates = [HasStdExtZbbOrZbkb]

13...

14let Predicates = [HasStdExtZbbOrZbkb] in {

15def : PatGprGpr<shiftop<rotl>, ROL>;

16def : PatGprGpr<shiftop<rotr>, ROR>;

17

18def : PatGprImm<rotr, RORI, uimmlog2xlen>;

19// There’s no encoding for roli in the the ’B’ extension as it can be

20// implemented with rori by negating the immediate.

21def : Pat<(rotl GPR:$rs1, uimmlog2xlen:$shamt),

22 (RORI GPR:$rs1, (ImmSubFromXLen uimmlog2xlen:$shamt))>;

23} // Predicates = [HasStdExtZbbOrZbkb]

Code 55: ROR Encodings and Pattern

As you can see when the pattern match logic is lifted up to the IR level the
modifications in Instruction Selection are straightforward to implement.

##  Chapter 8 NEW INSTRUCTIONS

This chapter contains more examples and demonstrations of new instructions.

###  8.1 SHLXOR Instruction

The purpose of SHLXOR instruction is to shift the first source operand one bit
to the left and then XOR it with the second source operand. Then, the obtained
result is stored in the destination register. By adding this instruction, we
can perform this operation with a single instruction instead of using shift
left and XOR instructions separately, making it more efficient. Let’s give an
example to make it clearer what this instruction does. RS1 and RS2 are source
operands and RD is the output.

RS1: 0x0101 RS2: 0xFFFF RD: 0xFDFD

0x0101 is shifted left by one and then XOR’ed with 0xFFFF, giving the result
0xFDFD. As we mentioned, this new instruction requires two source registers
and one destination register. Therefore, unlike the MLA instruction, we don’t
need to create a new class to support it. There is already a class named
ALU_rr in the RISCVInstrinfo.td file that has two source and one destination
register. Therefore, the new SHLXOR instruction is going to belong to the
ALU_rr class. The ALU_rr class definition is given below.

⬇

1let hasSideEffects = 0, mayLoad = 0, mayStore = 0 in

2class ALU_rr<bits<7> funct7, bits<3> funct3, string opcodestr,

3bit Commutable = 0>

4: RVInstR<funct7, funct3, OPC_OP, (outs GPR:$rd),

5 (ins GPR:$rs1, GPR:$rs2),

6opcodestr, "$rd, $rs1, $rs2"> {

7let isCommutable = Commutable;

8}

As we can see, encoding of this type of instruction consists of funct7,
funct3, opcode, source registers, and the destination register. The encoding
format and the other properties are described in the class. The source
registers are described as inputs and the destination register is described as
the output. In the RISCVInstrInfoCrypt.td file, we add the definition of the
SHLXOR instruction by using the ALU_rr class. In this part, we define funct7,
funct3, and the mnemonic of the new instruction as well as the scheduling.

⬇

1def SHLXOR : ALU_rr<0b0011000, 0b111, "shlxor">,

2 Sched<[WriteIALU, ReadIALU, ReadIALU]>;

Also in the same file, we define the instruction’s pattern. When we examine
this definition, we can clearly see what the instruction performs and its
pattern. In the inner parentheses, we can see the shifting of the first source
operand by one bit. Then, the result of this shifting operation is used as an
input for the XOR operation alongside the second source operand.

⬇

1def : Pat< (xor (shl GPR:$src1, (i32 1)), GPR:$src2),

2 (SHLXOR GPR:$src1, GPR:$src2)>;

After doing these, we can try it with a simple C code given below.

⬇

1int a,b;

2

3void shlxor() {

4 a = 3;

5 b = 5;

6

7 a = b^(a<<1);

8}

Let’s get an assembly output from this C code by running the following
commands:

⬇

1clang -S -target riscv32-linux-gnu -emit-llvm shlxor.c

2<llvm-build-path>/build/bin/llc -mtriple=riscv32 shlxor.ll

This C code basically shifts the variable "a" by one bit and XOR’s it with the
"b" variable. Then the result is stored in "a". We can see that, the register
that stores the value "a" is both the first source register and the
destination register. The assembly output is given below.

⬇

1.Lfunc_begin0:

2 .loc 0 4 0 # shlx.c:4:0

3 .cfi_sections .debug_frame

4 .cfi_startproc

5# %

6 addi sp, sp, -16

7 .cfi_def_cfa_offset 16

8.Ltmp0:

9 .loc 0 5 4 prologue_end # shlx.c:5:4

10 sw ra, 12(sp) # 4-byte Folded Spill

11 sw s0, 8(sp) # 4-byte Folded Spill

12 .cfi_offset ra, -4

13 .cfi_offset s0, -8

14 addi s0, sp, 16

15 .cfi_def_cfa s0, 0

16 lui a0, %

17 li a1, 3

18 sw a1, %

19 .loc 0 6 4 # shlx.c:6:4

20 lui a1, %

21 li a2, 5

22 sw a2, %

23 .loc 0 9 6 # shlx.c:9:6

24 lw a1, %

25 .loc 0 9 9 is_stmt 0 # shlx.c:9:9

26 lw a2, %

27 .loc 0 9 7 # shlx.c:9:7

28 shlxor a1, a2, a1

29 .loc 0 9 4 # shlx.c:9:4

30 sw a1, %

31 .loc 0 10 1 is_stmt 1 # shlx.c:10:1

32 lw ra, 12(sp) # 4-byte Folded Reload

33 lw s0, 8(sp) # 4-byte Folded Reload

34 addi sp, sp, 16

35 ret

In the assembly output, we can see the SHLXOR instruction in line 28. a1 and
a2 are the sources and a1 is also the destination as we can see.

In addition to that, we can check the DAG in order to see the effect of our
newly added instruction. We can compare the DAGs before and after the new
instruction is added. We can observe the DAG before SHLXOR is added in Figure
8.1. In this DAG, shift left (shl) and xor instructions can be seen separately

Figure 8.1: DAG before SHLXOR is added

The DAG after we add the SHLXOR instruction can be seen in Figure 8.2. In this
DAG, instead of two separate instructions, a single SHLXOR instruction can be
seen.

Figure 8.2: DAG after SHLXOR is added

###  8.2 RORI Instruction

One of the Instructions that we worked on is RORI instruction. The purpose of
this instruction is to take the operand and rotate it to the right by the
amount of the immediate value. This is different from shifting right using an
immediate. When shifting a number to the right, the LSBs are deleted and the
MSBs are either zero or sign extended. On the other hand, when a number is
rotated right, the LSBs that are pushed out are not deleted but written into
the most significant bits. We want to add an instruction that performs this
operation.

First of all, we tried pattern matching and added the definition and pattern
of our new instruction to the InstrInfoCrypt.td file. However, the RORI
instruction was not observed when we checked the assembly output created by
using a simple C code that implements the rotation operation. This is because
the pattern can have different combinations and may not match what we expect.
Therefore, the instruction cannot be recognized and we can’t see it in the
assembly output.

Realizing that, we looked for other options and tried to make use of
intrinsics and builtin functions. We added the definitions to the
InstrInfoCrypt.td file.

⬇

1def ROTI : ALU_ri<0b101, "roti">;

It is ALU_ri type because one of the operands is an immediate value and we
only need one register for this instruction.

⬇

1def : Pat<(rotr GPR:$rs1, simm12:$imm12),

2(ROTI GPR:$rs1, simm12:$imm12)>;

We used rotr here because we wanted to make use of the builtin function
__builtin_rotateright32. "rotr" is defined in the RISVIselLowering.cpp file.

⬇

1if (Subtarget.hasStdExtZbb() || Subtarget.hasStdExtZbkb()) {

2if (Subtarget.is64Bit())

3setOperationAction({ISD::ROTL, ISD::ROTR}, MVT::i32, Custom);

4} else {

5setOperationAction({ISD::ROTL, ISD::ROTR}, XLenVT, Expand);

6}

However, we need to change the “Expand” to “Legal” here otherwise we will not
see the ROTI instruction in the assembly output. This way, we are legalizing
the action. If we don’t do this, we will see the fshr (funnel shift right)
intrinsic in the .ll file but ROTI won’t make it into the assembly output.
After doing these, we can try it with a simple C code. As mentioned before, we
used a builtin rotate function in the C code given below to guarantee the
generation of "fshl" llvm intrinsic function.

⬇

1int a;

2

3void ROT() {

4 a = 15;

5

6 a = __builtin_rotateright32(a,2);

7}

This code rotates 15 to the right by 2 bits. We can obtain the .ll file by
running the following command.

⬇

1clang -S -target riscv32-linux-gnu -emit-llvm roti.c

The simplified contents of the .ll file is given below.

⬇

1@a = dso_local global i32 0

2

3define void @ROT() {

4 store i32 15, i32* @a

5 store i32 %

6 ret void

7}

The fshr intrinsic is visible in the sixth line. After that, the assembly
output can be obtained by running the following command.

⬇

1<llvm-build-path>/build/bin/llc -mtriple=riscv32 roti.ll$

The obtained assembly output is given below.

⬇

1ROT: # @ROT

2.Lfunc_begin0:

3 .loc 0 3 0 # roti.c:3:0

4 .cfi_sections .debug_frame

5 .cfi_startproc

6# \%bb.0:

7 addi sp, sp, -16

8 .cfi_def_cfa_offset 16

9.Ltmp0:

10 .loc 0 4 4 prologue_end # roti.c:4:4

11 sw ra, 12(sp) # 4-byte Folded Spill

12 sw s0, 8(sp) # 4-byte Folded Spill

13 .cfi_offset ra, -4

14 .cfi_offset s0, -8

15 addi s0, sp, 16

16 .cfi_def_cfa s0, 0

17 lui a0, \%hi(a)

18 li a1, 15

19 sw a1, \%lo(a)(a0)

20 .loc 0 11 30 # roti.c:11:30

21 lw a1, \%lo(a)(a0)

22 .loc 0 11 6 is_stmt 0 # roti.c:11:6

23 roti a1, a1, 2

24 .loc 0 11 4 # roti.c:11:4

25 sw a1, \%lo(a)(a0)

26 .loc 0 14 1 is_stmt 1 # roti.c:14:1

27 lw ra, 12(sp) # 4-byte Folded Reload

28 lw s0, 8(sp) # 4-byte Folded Reload

29 addi sp, sp, 16

30 ret

The ROTI instruction can be seen in the assembly output in line 23. As
expected, it uses one register as both the destination and the source
alongside an immediate value.

After further investigation, we realized that rotation instruction was already
implemented in bit manipulation extension for RISC-V and in the
RISCVInstrInfoZb.td file. This file contains the instruction extensions for
bit manipulations. These instructions operate on the bits of the data and RORI
is one of those instructions. However, in order to utilize this extension, we
need to add some flags to the command while running Clang in order to get an
assembly output from the C code we write. The simple C code for RORI is given
below .

⬇

1#define XLEN 32

2#include <stdint.h>

3#define uint_xlen_t uint32_t

4

5uint_xlen_t rotimm(uint_xlen_t rs1){

6 uint_xlen_t a = 0;

7 a = ((rs1>>2) | (rs1<<(XLEN-2)));

8 return a;

9}

Here, we use 32 as the length because our target is 32-bit. The rotation is
implemented in the seventh line. After that, we run the following command with
additional flags as mentioned before.

⬇

1clang \--target=riscv32 -O -S rori.c -march=rv32imaczbb

Here, -O defines the level of optimization. -S is used for getting an assembly
file as an output. rori.c is the name of our simple C code. -march=rv32imaczbb
designates that we want to utilize the Zbb subgroup of the bit manipulation
extension. The assembly output is given below.

⬇

1rotimm:

2 rori a0, a0, 2

3 ret

This way, we managed to successfully obtain RORI instruction in the assembly
output.

###  8.3 NAXOR Instruction

The S-box algorithm includes a certain pattern that is used repeatedly. NOT-
AND-XOR pattern is used five times in an s-box cycle. This pattern is lowered
into one instruction using TableGen. The definition and specifications of the
pattern are added to RISCVInstrInfoCrypt.td file. After matching this pattern
15 rows of the assembly file are reduced to one single instruction.

⬇

1def NAXOR : ALU_rrr<0b11, 0b100, "naxor">,

2Sched<[WriteIMul, ReadIMul, ReadIMul]>;

Since there are three variables in this instruction, custom ALU_rrr class is
used which is explained in Section 7.3.1. "11" and "100" base 2 numbers are
used for funct2 and funct3.

⬇

1def : Pat< (xor (and (not GPR:$src1), GPR:$src2), GPR:$src3),

2 (NAXOR GPR:$src1, GPR:$src2, GPR:$src3)>;

This pattern is repeated 5 times as emphasized in Figure 8.3. NAXOR
instruction reduces 15 instructions into 5 instructions.

Figure 8.3: NAXOR patterns in s-box algorithm Figure 8.4: DAG diagram output
for the s-box algorithm before scheduling Figure 8.5: DAG diagram output for
the s-box algorithm

⬇

1typedef struct {

2 int x[5];

3} ascon_state_t;

4

5void sbox(ascon_state_t state) {

6 int t0, t1, t2, t3, t4;

7 state.x[0] ^= state.x[4];

8 state.x[4] ^= state.x[3];

9 state.x[2] ^= state.x[1];

10 t0 = state.x[0];

11 t1 = state.x[1];

12 t2 = state.x[2];

13 t3 = state.x[3];

14 t4 = state.x[4];

15 t0 =~ t0;

16 t1 =~ t1;

17 t2 =~ t2;

18 t3 =~ t3;

19 t4 =~ t4;

20 t0 &= state.x[1];

21 t1 &= state.x[2];

22 t2 &= state.x[3];

23 t3 &= state.x[4];

24 t4 &= state.x[0];

25 state.x[0] ^= t1;

26 state.x[1] ^= t2;

27 state.x[2] ^= t3;

28 state.x[3] ^= t4;

29 state.x[4] ^= t0;

30 state.x[1] ^= state.x[0];

31 state.x[0] ^= state.x[4];

32 state.x[3] ^= state.x[2];

33 state.x[2] =~ state.x[2];

34

35 return;

36}

Code 56: C code input for the S-box algorithm

⬇

1define void @sbox(ptr %0) {

2 %2 = getelementptr inbounds [5 x i32], ptr %0, i32 0, i32 4

3 %3 = load i32, ptr %2

4 %4 = load i32, ptr %0

5 %5 = xor i32 %4, %3

6 %6 = getelementptr inbounds [5 x i32], ptr %0, i32 0, i32 3

7 %7 = load i32, ptr %6

8 %8 = xor i32 %7, %3

9 %9 = getelementptr inbounds [5 x i32], ptr %0, i32 0, i32 1

10 %10 = load i32, ptr %9

11 %11 = getelementptr inbounds [5 x i32], ptr %0, i32 0, i32 2

12 %12 = load i32, ptr %11

13 %13 = xor i32 %12, %10

14 %14 = xor i32 %5, -1

15 %15 = xor i32 %10, -1

16 %16 = xor i32 %13, -1

17 %17 = xor i32 %7, -1

18 %18 = xor i32 %8, -1

19 %19 = and i32 %10, %14

20 %20 = and i32 %12, %15

21 %21 = and i32 %7, %16

22 %22 = and i32 %3, %17

23 %23 = and i32 %5, %18

24 %24 = xor i32 %20, %5

25 %25 = xor i32 %21, %10

26 %26 = xor i32 %13, %22

27 %27 = xor i32 %23, %7

28 %28 = xor i32 %19, %8

29 store i32 %28, ptr %2

30 %29 = xor i32 %25, %24

31 store i32 %29, ptr %9

32 %30 = xor i32 %24, %28

33 store i32 %30, ptr %0

34 %31 = xor i32 %26, %27

35 store i32 %31, ptr %6

36 %32 = xor i32 %26, -1

37 store i32 %32, ptr %11

38 ret void

39}

Code 57: Optimized S-box LLVM IR Figure 8.6: DAG diagram output for the s-box
algorithm after NAXOR instruction is matched

⬇

1sbox:

2 lw a1, 16(a0)

3 lw a2, 0(a0)

4 lw a3, 12(a0)

5 lw a4, 4(a0)

6 lw a5, 8(a0)

7 xor a2, a2, a1

8 xor a6, a3, a1

9 xor a7, a5, a4

10 not t0, a2

11 not t1, a4

12 not t2, a7

13 not t3, a3

14 not t4, a6

15 and t0, a4, t0

16 and a5, a5, t1

17 and t1, a3, t2

18 and a1, a1, t3

19 and t2, a2, t4

20 xor a2, a2, a5

21 xor a4, t1, a4

22 xor a1, a7, a1

23 xor a3, t2, a3

24 xor a5, t0, a6

25 sw a5, 16(a0)

26 xor a4, a4, a2

27 sw a4, 4(a0)

28 xor a2, a2, a5

29 sw a2, 0(a0)

30 xor a3, a3, a1

31 sw a3, 12(a0)

32 not a1, a1

33 sw a1, 8(a0)

34 ret

Code 58: Assembly output without NAXOR instruction

⬇

1sbox:

2 lw a1, 16(a0)

3 lw a2, 0(a0)

4 lw a3, 12(a0)

5 lw a4, 4(a0)

6 lw a5, 8(a0)

7 xor a2, a2, a1

8 xor a6, a3, a1

9 xor a7, a5, a4

10 naxor a5, a4, a5 ,a2

11 naxor t0, a7, a3 ,a4

12 naxor a1, a3, a1 ,a7

13 naxor a3, a6, a2 ,a3

14 naxor a2, a2, a4 ,a6

15 sw a2, 16(a0)

16 xor a4, t0, a5

17 sw a4, 4(a0)

18 xor a2, a2, a5

19 sw a2, 0(a0)

20 xor a3, a3, a1

21 sw a3, 12(a0)

22 not a1, a1

23 sw a1, 8(a0)

24 ret

Code 59: Assembly output with NAXOR instruction

15 lines of not, and, xor operations are reduced to 5 NAXOR instructions.

###  8.4 LXR Instruction

LXR instruction covers an XOR operation of two loads from independent
addresses. ALU_rr class is used. Note that in order to match loads with
dependant addresses, C++ logic must be implemented as discussed in Section
7.4.

⬇

1let mayLoad = 1 in{

2def LXR : ALU_rr<0b0011011, 0b101, "lxr">,

3Sched<[WriteIALU, ReadIALU, ReadIALU]>;

4}

ALU_rr class is used and 0011011, 101 base 2 numbers are used for funct7 and
funct3. mayLoad flag is 1 to enable the load instruction in the pattern.

⬇

1def : Pat< (xor (load GPR:$rs1),(load GPR:$rs2)),

2(LXR GPR:$rs1,GPR:$rs2)>;

LXR instruction covers the xor operation of two loaded numbers.

Figure 8.7: DAG diagram for the example LXR algorithm before scheduling Figure
8.8: DAG diagram output for the example LXR algorithm

⬇

1 define i32 @foo(ptr %

2 ret i32 %

3 }

Code 60: IR code input for LXR algorithm

⬇

1 foo:

2 lw a0, 0(a0)

3 lw a1, 0(a1)

4 xor a0, a0, a1

5 ret

Code 61: Assembly output without LXR instruction Figure 8.9: DAG diagram
output for the example LXR algorithm after LXR instruction is matched

⬇

1foo:

2 lxr a0, a0, a1

3 ret

Code 62: Assembly output with LXR instruction

Two loads and one xor instructions are reduced to LXR instruction.

##  Chapter 9 TESTING

Regression testing is a core part of LLVM because of its size and active
development. To make sure newly added features don’t break the already present
functionality it is a must to both build functionality and its corresponding
tests.

LLVM-lit coordinates the testing procedure. The comment lines that start with
“RUN” call other programs via LLVM-lit. LLVM-lit also gives the output of a
program to another program as an input.

FileCheck, as the name implies, controls the checking process. It basically
compares the file and the corresponding lines of the output. It is used with
CHECK-* command.

In this chapter SHLXOR instruction which was introduced in Section 8.1 will be
tested. Its instruction encoding and Assembler support are tested with MC
tests. Its pattern matching support is tested with LLC tests.

###  9.1 MC Test

LLVM-MC is an abstracted assembler and object file emitter integrated with the
compiler [37].

Before adding a new instruction, its encoding should be designed. LLVM-MC is
going to be used to get the encoding results. A wrong input to TableGen class
may result in a different encoding than expected. With an MC test, the
expectation and result will be compared.

⬇

1# RUN: llvm-mc %

2# RUN: | FileCheck -check-prefixes=CHECK-ASM,CHECK-ASM-AND-OBJ %

3# RUN: llvm-mc -filetype=obj -triple=riscv32 < %

4# RUN: | llvm-objdump -M no-aliases -d -r - \

5# RUN: | FileCheck -check-prefixes=CHECK-ASM-AND-OBJ %

6

7# CHECK-ASM-AND-OBJ: shlxor s2, s2, s8

8# CHECK-ASM: encoding: [0x33,0x59,0x89,0x81]

9shlxor s2, s2, s8

Code 63: MC Test File

The first RUN command sequence results in the output given in Code 64.

⬇

1$ <llvm-build-path>/build/bin/llvm-mc \\\

2<llvm-build-path>/llvm/test/MC/RISCV/crypt.s \\\

3-triple=riscv32 -riscv-no-aliases -show-encoding

4

5 . text

6

7 shlxor s2, s2, s8 # encoding: [0x33,0x59, 0x89, 0x81]

Code 64: Result of first "RUN" command

In Code 63, FileCheck is checking both the Assembly encoding and the string as
it was provided with the prefixes: CHECK-ASM, CHECK-ASM-AND-OBJ.

The second RUN sequence with only the llvm-mc part gives out an ELF object
which itself isn’t useful. The console output can be seen in Code 65.

⬇

1$ <llvm-build-path>/build/bin/llvm-mc \\\

2<llvm-build-path>/llvm/test/MC/RISCV/crypt.s \\\

3-filetype=obj -triple=riscv32

4

5ELF‘4(3Y.text.strtab.symtab48%

Code 65: Result of second "RUN" command

By using the pipe ‘|’ operator similar to Shell usage, we can tell LLVM-lit to
feed another program with the output of a program. The test commands with
shell pipe are demonstrated in Code 66.

⬇

1$ <llvm-build-path>/build/bin/llvm-mc -filetype=obj -triple=riscv32 <

2<llvm-build-path>/llvm/test/MC/RISCV/crypt.s | \\\

3<llvm-build-path>/build/bin/llvm-objdump -M no-aliases -d -r -

4

5

6<stdin>: file format elf32-littleriscv

7

8Disassembly of section .text:

9

1000000000 <.text>:

11 0: 33 59 89 81 = shlxor s2, s2, s8

Code 66: Use of pipe operator in Shell

Observing the outputs directly through the shell indicates what FileCheck is
looking for in the standard output. Here in the second RUN sequence, FileCheck
is provided only with CHECK-ASM-AND-OBJ and therefore it does not check the
CHECK-ASM line. It seems that the object dump resulted in the correct string.

In Code 67 we can observe that the test is passed:

⬇

1$ <llvm-build-path>/build/bin/llvm-lit \\\