Optimizing Compilation of Array Accesses in Solidity Smart Contracts

OPTIMIZING COMPILATION OF ARRAY ACCESSES IN SOLIDITY SMART CONTRACTS COMPILACIÓN OPTIMIZANTE DE ACCESOS A ARRAYS EN CONTRATOS INTELIGENTES EN SOLIDITY Trabajo de Fin de Grado Curso 2022–2023 Autor Javier Sande Ríos Director Jesús Correas Fernández Grado en Ingeniería Informática Facultad de Informática Universidad Complutense de Madrid OPTIMIZING COMPILATION OF ARRAY ACCESSES IN SOLIDITY SMART CONTRACTS COMPILACIÓN OPTIMIZANTE DE ACCESOS A ARRAYS EN CONTRATOS INTELIGENTES EN SOLIDITY Trabajo de Fin de Grado en Ingeniería Informática Autor Javier Sande Ríos Director Jesús Correas Fernández Convocatoria: Junio 2023 Grado en Ingeniería Informática Facultad de Informática Universidad Complutense de Madrid May 28, 2023 Agradecimientos A mis padres por brindarme la oportunidad de estudiar. Junto a ellos, a mi hermana y a toda mi familia por el constante cariño y apoyo incondicional que siempre me han brindado. A mis compañeros y amigos por todos los momentos inolvidables que hemos compartido a lo largo de este camino. A la Universidad y a todos sus profesores por su dedicación e incansable esfuerzo, especialmente durante los difíciles años de la pandemia, por en enseñarnos y proporcionarnos los recursos necesarios para convertirnos en excelentes profesionales. Por último, pero no menos importante, quiero expresar mi más profundo agradecimiento a mi director en este trabajo, Jesús Correas Fernández, por su guía durante todo el proceso y por su esfuerzo para adaptarse a las dificultades que implicó la diferencia horaria v Abstract On Ethereum, smart contracts must have two key characteristics: efficiency, an essential feature in smart contracts with a direct economic impact on the user, and security. The compiler of Solidity, the most widely used language for programming Ethereum smart contracts, automatically incorporates various security checks to avoid programming errors. This is the case of bounds checks on array accesses. Nevertheless, these checks introduce some computational overhead, which might be unnecessary in some scenarios. In this project, two approaches are proposed to reduce the costs associated with these controls and, consequently, array accesses. First, we introduce a new Solidity code construct that allows you to disable bounds checks in those sections of code that programmers deem unnecessary. Secondly, we propose a new compiler optimization phase that takes advantage of the high-level language structures of the program in order to optimize low-level accesses to arrays and relax the applicability conditions of current optimizations. Finally, we confirm through experimental results the effectiveness of both solutions in reducing the computational cost of array accesses. Keywords Ethereum, blockchain, smart contract, Solidity, optimizing compiler, runtime check. vii Resumen En Ethereum, los contratos inteligentes deben tener dos características clave: eficiencia, característica esencial con un impacto económico directo en el usuario, y la seguridad. El compilador de Solidity, el lenguaje más utilizado para programar contratos inteligentes en Ethereum, incorpora automáticamente varios controles de seguridad para evitar errores de programación. Este es el caso de los controles de límites en los accesos a arrays. No obstante, estas comprobaciones introducen cierta sobrecarga computacional, que puede ser innecesaria en algunos escenarios. En este proyecto, se proponen dos enfoques para reducir los costos asociados con estos controles y, en consecuencia, con el acceso a arrays. Primero, presentamos una nueva construcción de código de Solidity que permite deshabilitar las comprobaciones de límites en aquellas secciones de código en las que los programadores las consideran innecesarias. En segundo lugar, proponemos una nueva fase de optimización en el compilador, que aprovecha las estructuras del lenguaje de alto nivel del programa para optimizar los accesos de bajo nivel a los arrays y relajar las condiciones de aplicabilidad de las optimizaciones actuales. Finalmente, confirmamos a través de resultados experimentales la efectividad de ambas soluciones para reducir el costo computacional de los accesos mediante índice a arrays. Palabras clave Ethereum, blockchain, contratos inteligentes, Solidity, compilador optimizador, comprobaciones en tiempo de ejecución. ix Introduction Ethereum is one of the most important blockchain networks in the current landscape. Its launch altered the blockchain world due to its smart contracts, programs whose code and state can be stored in the blockchain network to be executed by all users. Smart contracts, commonly developed using the Solidity language, are used by network users through transactions and executed in the nodes. These nodes, known as miners, are economically rewarded proportionally to the computational cost of the executed transaction. This compensation, paid by the user, makes the efficiency of the contracts essential, encouraging responsible use of the blockchain and avoiding attacks that block network resources. Another essential feature of smart contracts is security. These programs often manage and store digital assets of great value, exposed to all network users. Therefore, contracts must be as secure as possible. However, sometimes security and efficiency clash, as in the case of array accesses on Solidity smart contracts. The use of arrays is a widespread practice in programming. Arrays are a flexible data type, extremely useful for storing and structuring data in programs, and smart contracts are no exception. However, the cost of accessing arrays is considerably high in Solidity smart contracts. In order to avoid programming errors, the Solidity compiler automatically generates bounds checks on each index access. Therefore, each access to an index involves two memory loads to access the length and the value, significantly increasing the cost. This high cost implies a limitation in their use, especially when storing non-volatile data, one of the most common uses of arrays. Therefore, the optimization of array accesses is of great interest. In this project, we propose two possible solutions for this problem. On the one hand, we will propose a Solidity language construct that allows programmers to eliminate bounds checks they consider unnecessary. On the other hand, we will propose a new compiler optimization to reduce the array length loads when possible and, consequently, reduce the cost of accessing arrays. 1 2 Goals The main goal of this project is to design, implement and test two optimization proposals to reduce the gas consumption associated with array accesses in Solidity smart contracts. In order to achieve it, we initially set the following goals: Understand how the current production compiler works, its internal and intermediate representations of the code, and its compilation phases. Understand current approaches of the Solidity language and its compiler to generate optimized code, their applicability, and limitations. Implement an optimization at the language level that allows developers to disable bounds checks on array index accesses. Implement a new optimization able to reduce array access gas cost in situations the current optimization modules cannot. Planning This project was divided into two main phases developed between September 2022 and May 2023. Each project phase focused on one of the two array optimization proposals. Language optimization block. During the first phase, between September and December, we focused on implementing a new language construct in Solidity, called uncheckedArray block, to provide developers with a tool to disable bounds checks in array accesses to reduce gas consumption. In order to implement this language extension, we first performed a deep study of the Solidity language, its compiler, and a similar solution that the language provides to reduce gas consumption on arithmetic operations. Then, we decided how to name and structure this new block, its possible use, and its limitations. Finally, we implemented the block to test and analyze the real performance of this new optimization tool on smart contracts. Compiler optimization. In the second phase of the project, we implemented a new optimization at compile time to reduce the cost of array accesses inside loops. During this phase, we used all the knowledge about the compiler acquired in the first phase. Nevertheless, we needed to perform some research and experiments in order to understand the optimizations currently performed by the compiler, its performance, and its limitations. Once we had a clear idea of how we could improve 3 the optimizations, we focused on establishing the constraints needed to guarantee the soundness of our new optimization. Finally, we implemented an experimental version of the proposed optimization and integrated it into a production version of the official compiler. We measured the potential impact on the gas consumption of real smart contracts by performing several tests with non-trivial benchmark programs. During both phases, we maintained weekly meetings to discuss the difficulties found, decisions taken, implementation details, and experimental evaluation, as well as the results obtained with benchmark programs and conclusions outlining some lines of future work. Code repositories The developed optimizations are available in the following GitHub repository: https://github.com/javierSande/solidity This repository is a fork from the original Solidity repository1, and it is publicly available. The repository is composed of four different branches: develop branch: contains the version of the official develop branch we used as a base for our development, corresponding to version v0.8.192of the compiler as of February 23, 2023. uncheckedArray branch: contains the basic implementation of the uncheckedArray block as presented in Section 2 of Chapter 3. targetedUncheckedArray branch: contains the final implementation of the uncheckedArray block as presented in Section 3 of Chapter 3. arrayLoopOptimization branch: contains the implementation of the compiler optimization as presented in Chapter 4. Additionally, the benchmarks developed for the evaluation of the optimization presented in Chapter 4 are available in the following GitHub repository: https://github.com/javierSande/solidity-benchmarks The README page of the repository contains the setup instructions to perform gas cost evaluations of code generated by an official or experimental version of the Solidity compiler. 1The official Solidity repository can be found at https://github.com/ethereum/solidity. 2Commit 983407762c3423e9c301d5ae56ac7b6d951655df 4 Structure of the document This memory contains the background, implementation details, and conclusion of the proposed optimizations. The document is structured as follows: Chapter 1: introduces Ethereum, the Ethereum Virtual Machine, and Solidity language. This chapter provides the theoretical and technical background to understand the necessity and possibilities for creating optimizations. Chapter 2: introduces the Solidity compiler, its compilation process, and state of the art on Solidity code optimizations. Chapter 3: presents the uncheckedArray block, a new Solidity structure to allow developers to disable safety checks in favor of efficiency. Chapter 4: presents a new compiler optimization phase that takes advantage of a higher level of code representation to optimize array accesses inside loops. Conclusions and Future Work: presents the conclusions of the optimizations developed in our project and proposes lines of work for future development of the proposed optimizations. Chapter 1 Ethereum Ethereum is an open-source, decentralized blockchain network conceived by Vitalik Buterin in 2013 and officially launched in 2015 [25]. It is founded on the basis of the blockchain protocol, first proposed by David Chaum in 1982, and first implemented by Satoshi Nakamoto1in 2008 with the creation of Bitcoin [19]. As a blockchain, Ethereum is a distributed ledger where transactions are recorded into blocks linked using cryptographic hashes. Like many other blockchain networks, it has its own digital currency, ether, used to store value, perform exchanges, pay fees, and reward participants of the network, such as the mining nodes. What makes Ethereum special is that it was the first programmable blockchain. This means that the network can be used to execute programs. Those programs are known as smart contracts, a concept first coined in the 1990s by Nick Szabo, who defined them as: A set of promises, specified in digital form, including protocols within which the parties perform on these promises. [22] Smart contracts are programs whose code and state are stored on the network at a specific address, allowing anyone to interact with them through function calls executed in the Ethereum Virtual Machine(EVM). When a blockchain user wants to communicate with the smart contract, it sends a transaction to its address specifying the function of the contract it wants to execute. Then, this transaction is validated by the network nodes, which execute the corresponding function using the EVM on its local machine. The possibility of storing and executing programs in a decentralized environment in a secure manner has opened the door to a large number of new technologies, such 1Pseudonymous person or group of persons who developed Bitcoin. 5 6Chapter 1. Ethereum as decentralized apps, known as dApps,Non-fungible tokens (NFTs) and the Web3. All of them are based on the smart contract technology introduced by Ethereum. Ethereum is, at the time of this writing, a system with a market capitalization of $200B, which performs more than 1 million transactions and has half a million active addresses daily2. It is a network in continuous growth, laying the foundations for the future of decentralized systems. 1.1. Ethereum Virtual Machine The Ethereum Virtual Machine (EVM) is a virtual machine capable of Turingcomplete computation. It is a runtime environment executed by the blockchain nodes to process the blockchain transactions, including the function calls to smart contracts. The EVM can be seen as the state function of the Ethereum network [25]. It takes an input (state of the blockchain, its contracts, and code to be executed), performs some computations, and outputs a new state. Figure 1.1: Representation of the EVM from EVM Illustrated [23] The EVM is a simple stack-based architecture with a 1024-element stack. The word size is 256 bits in the stack, and in all its memory regions3, in order to facilitate cryptographic operations such as hashing and elliptic curves. As illustrated in Figure 1.1, the EVM is composed of the following elements: 2These and more statistics about Ethereum can be consulted at https://etherscan.io. 3Volatile memory is both word and byte-addressable. We consider the same word size for all regions for simplicity. 1.2. Gas 7 The program counter (PC). A ROM memory containing the code to execute. The gas available to perform the operations, a parameter that limits the computation done in a transaction. The stack that contains the local values used on the operations. A volatile memory region to store data during the execution. A persistent memory region called storage, where the contract state is stored. The EVM executes the bytecode of the compiled contract interpreted as a sequence of opcodes4, instructions that perform stack-bases operations (e.g., PUSH, ADD,PUSH) and other blockchain and cryptographic related operations such as BLOCKHASH, BALANCE and KECCAK256. 1.2. Gas The EVM can execute Turing-complete programs. However, it is a quasi-Turingcomplete machine since its computation is bounded through a parameter called gas, which limits the amount of computation performed in a single transaction. This computation limit has a security reason. It limits the execution on the EVM and, consequently, in the blockchain, preventing buggy or malicious contracts from executing indefinitely, hanging the network (Denial of Service). Moreover, this cost model has another essential duty: rewarding the miners. Each unit of gas has an associated price set in ether5determined by the users that issue the transaction. With this amount of ether, miners are rewarded for the computational effort of executing the operation and are incentivized to prioritize certain transactions. Users can set higher gas prices to prioritize transactions or lower prices if they do not mind the transaction taking longer to process. The average gas price of each mined block can be consulted in real-time on platforms such as Etherscan. Along with specifying the gas price, the user that initializes the transaction or contract call specifies the amount of gas that can be destinated to its execution on the EVM. Each EVM instruction has a predefined gas cost6withdrawn from the 4Read more about EVM opcode at https://ethereum.org/en/developers/docs/evm/ opcodes/ 5Usally, gas price is specified in gwei that corresponds to 10−9ether. 6The cas cost of each EVM instruction can be consulted at https://ethereum.org/en/ developers/docs/evm/opcodes/. 8Chapter 1. Ethereum total amount of gas when it is executed. The non-consumed gas is returned to the caller after the function call. However, if the EVM runs out of gas while executing the function call or the execution fails, the contract state reverts, but the gas is not refunded to the caller. The gas cost mechanism is a fundamental feature of the Ethereum blockchain. It ensures that the network remains secure and economically incentivized for miners. Nevertheless, this mechanism urges the contracts in the network to be as efficient as possible since they have a direct monetary cost on their users. 1.3. Programming Languages Developers can use several programming languages to develop smart contracts for the Ethereum blockchain. Different languages can target the EVM, such as LLL (Lisp Like Language) [18], one of the first languages developed for Ethereum, or Vyper [24], an experimental language. However, the vast majority of smart contracts in the Ethereum blockchain are coded in one particular language, Solidity. According to Etherscan, the reference analytics platform for Ethereum, this language is used by more than 99% of the contracts used in the blockchain7. In this project, we aim our optimizations to reach the largest number of smart contracts possible. Therefore, we focused on the Solidity language, its compilation into EVM bytecode, and its intermediate representation, Yul. 1.3.1. Solidity Solidity is an object-oriented language that targets the Ethereum Virtual Machine (EVM). It was proposed in 2014 by Gavin James Wood and developed by members of the Ethereum Foundation led by Christian Reitwiessner. It is mainly influenced by C++, but it also has borrowed concepts from other languages such as Python and JavaScript. This similarity with other popular languages has made Solidity an easy language to adopt for developers who want to develop smart contracts. Solidity is the most popular programming language in the Ethereum blockchain. It is used for developing smart contracts that can be compiled into EVM bytecode to be deployed in the network. In Solidity, four types of programs can be developed8: 7These and more statistics about smart contracts can be consulted at https://etherscan.io/ dashboards/contract-statistics. 8Read more about contracts, interfaces, and libraries in Solidity at https://docs. soliditylang.org/en/v0.8.19/contracts.html. 1.3. Programming Languages 9 Contracts. They can be seen as Java or C++ classes. They represent the smart contract deployed at the network with its state variables, functions, and constructor. They are defined using the contract keyword, and, as shown in Figure 1.2, they usually have the following structure: •Declaration of its state variables that may include a default value (Lines 2 and 3). •Constructor, a function declared with the constructor keyword only executed when the contract is created (Lines 5 to 7). If not declared, the contract has an implicit constructor with no parameters. •Functions of the contract (Lines 9 to 11). 1contract C { 2uint size; 3uint[] a; 4 5constructor(uint _size) { 6size = _size; 7} 8 9function getFirst() public view returns (uint) { 10 return a[0]; 11 } 12 } Figure 1.2: Example of Solidity smart contract Abstract contracts. Contracts that are used as the base to implement other contracts. They contain at least one function that is not implemented, and they cannot be deployed. They are declared using the abstract keyword before the contract keyword. Interfaces. Similar to abstract contracts, but cannot provide the implementation of the functions defined. They are declared using the interface keyword. Libraries. Libraries are a special kind of contract that contains reusable code. They are usually deployed only once on the blockchain, and their code is used by other contracts using function calls. They are declared using the library keyword. On Solidity, the following value types can be used: Booleans with two possible values: true or false. 16 Chapter 1. Ethereum The array is a reference type containing elements of a specific type. In Solidity, programmers can define arrays of any value, reference, mapping, or function type. They can be located in memory, calldata, or storage and can have a static or dynamic size. 1contract C { 2uint[4] arrayA; // Fixed-size array 3uint[] arrayB = [1,2]; // Fixed-size array 4uint[] arrayC; // Dynamic array 5 6function f(uint size, uint[] calldata callArray, uint[5] calldata callArrayB) public { 7uint[5] memory memArrayA; 8int[] memory memArrayB = new int[](size); 9bool[] memory memArrayC; 10 memArrayC = new bool[](size); 11 12 for (uint i = 0; i < size; i++) 13 { 14 arrayC.push(i); 15 arrayC.pop(); 16 } 17 18 uint length = arrayC.length; 19 value = arrayC[0]; 20 uint[] memory slice = callArray[1:4]; 21 } 22 } Figure 1.8: Example of arrays in Solidity Memory. Arrays in memory are created inside the body of a function using a local variable pointer. They are declared in two different ways, depending on how their size is set. In function f(Lines 6 to 21 of Figure 1.8), we can observe the different ways of declaring a memory array. Arrays allocated in memory always have a fixed size that can be set statically (Line 7) or dynamically (Line 8 or Lines 9 and 10). Like any memory value, they are allocated on creation, starting at the first free memory position, where the length is stored, and consecutively storing all the array values. In the case of dynamic size arrays, their local variable (Line 9) initially points to the zero memory slot (0x60) while they are not initialized (Line 10). Calldata. Arrays in calldata are only readable and are used as arguments or return values of contract functions. Calldata arrays can have a static or dynamic immutable 1.5. Arrays access in Ethereum 17 size. If they have a dynamic size, their lengths are calculated based on the range of addresses it comprises in the calldata region. Line 6 of Figure 1.8 shows the declaration of a dynamic and a static calldata arrays as function arguments f. Storage. Arrays allocated in storage are created as contract state variables with a fixed or dynamic size. In the contract of Figure 1.8, we can observe the two ways of declaring a fixed-size array in storage: without initializing its values (Line 2) or initializing its values (Line 3). Additionally, at Line 4, we can see the declaration of a dynamic array. Dynamic arrays can only be declared in storage and can perform the push and pop operations in order to append or remove a value at the last position of the array. In Solidity, arrays can be accessed in three different ways: Length access. The number of elements of the array can be consulted using the length member of the array pointer. At Line 18 of Figure 1.8, we can observe an example of length access to an array. Index access. The elements of the array can be accessed using their index (<array base>[index]), as shown at Line 19 of Figure 1.8. Index Range access. A subset of continuous elements of the array can be obtained using their index range (<array base>[from: to]), as shown at Line 20 of Figure 1.8. Index range accesses are only available for dynamic calldata arrays. In Solidity smart contracts, an out-of-bounds check is always performed when accessing an array by index. This check compares the index being accessed with the array length, raising an exception if the index is not lower. Out-of-bounds checking helps to provide safer code, avoiding overflows on array accesses. However, they also have a negative impact on gas consumption. When accessing memory or storage arrays with a dynamically set length (dynamic arrays or fixed-size arrays with size set at runtime), their length must be loaded in order to perform the bounds check. Therefore, on each access, two loads have to be done: the length of the array and the value being accessed. This makes index accesses very expensive, especially in the case of storage arrays. The length load is not required for fixed-size arrays with statically set sizes since their length is known at compile time. There is also a gas consumption increase for all array indexes accessed due to all the other instructions performed during the check. In this project, we will propose two different optimizations for the array index access to reduce its gas consumption by avoiding the length load needed for the out-of-bounds checks. Chapter 2 The Solidity Compiler In order to define a compiler, we will quote the definition given by the classic reference book on compiler technology, Compilers: principles, techniques, and tools [1] popularly known as the Dragon Book: A compiler is a program that can read a program in one language, the source language, and translate it into an equivalent program in another language, the target language. [1, p. 1] The compilation of a program is a complex process composed of different phases. The traditional phases of the compilation process, as presented in the Dragon Book and shown in Figure 2.1, are: Lexical Analysis. It is the first phase of the compilation process. During this phase, the compiler processes the source program as a stream of characters, grouping them into lexemes stored as tokens. Syntax Analysis or Parsing. The compiler generates a tree structure representing the structure of the obtained tokens following the source language grammar. This structure is called the syntax tree. Semantic Analysis. The compiler checks that the code complies with the semantic rules of the source language. Intermediate Code Generation. This optional phase is where the compiler may generate an intermediate representation (IR) from the syntax tree. Code Optimization. During this phase, the compiler transforms the intermediate code in order to be able to generate a more efficient target code. The optimizations in this phase are machine-independent since they transform the intermediate representations without involving specific details of the targeted 19 20 Chapter 2. The Solidity Compiler machine as registers or memory allocation. Code Generation. The compiler maps the intermediate representation (or the syntax tree in case the IR was not generated) into the target code. During this phase, the compiler is in charge of the register allocation of the generated variables or their position on the stack in the case of stack-based machines (as the EVM). Figure 2.1: Phases of the compilation process from the Dragon Book [1] Finally, the target code generated may be subject to machine-dependent optimizations that transform the code to achieve a better performance based on features specific to the targeted machine. In this chapter, we will introduce the compilation of Solidity smart contracts into the final bytecode executed by the Ethereum Virtual Machine. As we will see, the compiler process resembles the traditional phase division previously presented, with minimal variations. This explanation of the Solidity compiler will mainly focus on the compiler features and phases that are modified or extended in the implementation of our proposed optimizations and which will be mentioned in later chapters. 2.1. Phases of the Solidity Compiler 21 2.1. Phases of the Solidity Compiler The Solidity compiler is the software that reads a program in Solidity and translates it into an equivalent program in EVM bytecode. The compiler was released in 2014 with the publication of the Solidity language by the Ethereum Foundation. It is an open-source compiler that can be consulted in its GitHub repository [15], where community contributors help to develop and improve it, led by the Ethereum Foundation official developers. The Solidity compiler is constantly evolving to adapt itself to the changes in the EVM and the Solidity language. At the moment of this project, the Solidity compiler is in version 0.8.19. The compiler, written in C++, is a complex program consisting of several modules that handle different phases of the compilation process. Figure 2.2 illustrates the main phases of a Solidity smart contract compilation. Parse Analyze Source code in Solidity Bytecode IR code ASM code AST Checked AST Generate and Optimize Figure 2.2: Phases of the Solidity compiler In this section, we will review the most relevant compiler phases and modules, the understanding of which is critical to the optimizations we will perform in both the Solidity language and the compiler. 2.1.1. Parsing Parsing is the first phase of the compilation process of a Solidity smart contract. During this phase, the compiler generates an internal representation of the code containing all the information included in the source files. This internal representation, called Abstract Syntax Tree (AST), will be used in the following phases to interpret, analyze and generate the EVM bytecode. 22 Chapter 2. The Solidity Compiler 2.1.1.1. Abstract Syntax Tree The Abstract Syntax Tree (AST) is a hierarchical representation of the code containing the information needed to analyze the source code and generate the machine-readable code. During this phase, the compiler generates an AST for each source file. 1pragma solidity >=0.8.4; 2 3contract C { 4uint[] a; 5 6function f() public view returns (uint) { 7return a[0] + 2; 8} 9} Figure 2.3: Example of Solidity smart contract We will use the minimal code shown in Figure 2.3 as a running example for this section. The AST generated by the compiler when compiling the code in Figure 2.3 is represented in Figure 2.5. Every AST node of the Solidity compiler has the following attributes: An identifier of the AST node that is unique. The location in the source file. An Annotation object that contains information about the object type and other annotations. Apart from those attributes, all AST nodes have the following methods: The == and != operator functions that check if two nodes have the same id. An accept function to be traversed by a visitor (checkers or code generators). The AST of a given source file can be exported as a JSON using the –ast-compactjson command line option of the current compiler. In Figure 2.4, we can see part of the generated JSON representing AST of the add expression in the function defined in Figure 2.3. 2.1. Phases of the Solidity Compiler 23 1"expression":{ 2"commonType":{"typeIdentifier":"t_uint256","typeString":"uint256"}, 3"id":15, 4"isConstant":false,"isLValue":false,"isPure":false," lValueRequested":false, 5"leftExpression":{ 6"baseExpression":{ 7"id":11, "name":"a", 8"nodeType":"Identifier", 9"src":"154:1:0", 10 "typeDescriptions":{"typeIdentifier":" t_array$_t_uint256_$dyn_storage","typeString":"uint256[] storage ref"} 11 }, 12 "id":13, 13 "indexExpression":{ 14 "id":12, "name":"i", 15 "nodeType":"Identifier", 16 "src":"156:1:0", 17 "typeDescriptions":{"typeIdentifier":"t_uint256","typeString":" uint256"} 18 }, 19 "isConstant":false,"isLValue":true,"isPure":false, 20 "lValueRequested":false, 21 "nodeType":"IndexAccess", 22 "src":"154:4:0", 23 "typeDescriptions":{"typeIdentifier":"t_uint256","typeString":" uint256"} 24 }, 25 "nodeType":"BinaryOperation", 26 "operator":"+", 27 "rightExpression":{ 28 "id":14, 29 "isConstant":false,"isLValue":false,"isPure":true, 30 "kind":"number","lValueRequested":false, 31 "nodeType":"Literal", 32 "src":"161:1:0", 33 "typeDescriptions":{"typeIdentifier":"t_rational_2_by_1","typeString ":"int_const 2"}, 34 "value":"2" 35 }, 36 "src":"154:8:0", 37 "typeDescriptions":{"typeIdentifier":"t_uint256","typeString":" uint256"} 38 } Figure 2.4: Example of AST Expression node represented as JSON 24 Chapter 2. The Solidity Compiler Root PragmaDirective nodesnodes ContractDefinition typeName VariableDeclaration parameter returnParameters body FunctionDefinition statements Block parameters ParameterList parameters ParameterList typeName VariableDeclaration ElementaryTypeName expression Return leftExpression rightExpression BinaryOperation baseExpression indexExpression IndexAccess Literal baseType ArrayTypeName ElementaryTypeName typeName VariableDeclaration ElementaryTypeName Identifier Identifier Figure 2.5: Example of the AST of a contract Visitor pattern. The compiler implements the Visitor Pattern [17] in order to allow the different analyzers and code generators to traverse the AST. In order to implement this pattern, classes ASTVisitor and ASTConstVisitor1are defined, providing a default implementation of the methods to visit each kind of AST Node, as shown in Figure 2.6. The compiler analyzers and code generators, which will be discussed in later sections, inherit from either the ASTVisitor or ASTConstVisitor classes. Each of them overwrites the visit methods to perform its corresponding actions over the source code elements represented by each AST node. The use of this pattern makes the AST fully modular and simplifies the extension and modification of the AST nodes, as well as the extension of every module that works over the AST (i.e., type checking or IR generation). 1Source code available at https://github.com/javierSande/solidity/blob/develop/ libsolidity/ast/ASTVisitor.h 2.1. Phases of the Solidity Compiler 25 1virtual bool visit(Block& _node) { return visitNode(_node); } 2virtual void endVisit(Block& _node) { endVisitNode(_node); } 3 4/// Generic function called by default for each node, to be overridden by derived classes 5/// if behavior unspecific to a node type is desired. 6virtual bool visitNode(ASTNode&) { return true; } 7/// Generic function called by default for each node, to be overridden by derived classes 8/// if behavior unspecific to a node type is desired. 9virtual void endVisitNode(ASTNode&) { } Figure 2.6: Example of default methods used by the AST visitors Relevant AST nodes. While over 60 diverse types of AST nodes are used to represent different syntactic elements of source code, it is beyond the scope of this document to describe all of them in detail. Instead, we will focus on the most pertinent types for our compiler modifications. Statement node. The AST Statement node is one of the most basic types of nodes in the Solidity AST. It serves as a base to represent a wide range of different code statements, such as variable declarations, function calls, or control flow statements (if-else or loop constructions). Each possible code statement is represented by a corresponding AST node that inherits from the Statement node. Figure 2.7 shows an example of a statement that represents a return statement (Return class). 1contract C { 2uint[] a; 3 4function f() public view returns (uint) { 5return a[0] + 2; 6} 7} Figure 2.7: Example of statement Block. The AST Block node is one of the most relevant AST nodes of the compiler in the context of this project. A block is a type of statement containing a group of zero or more code statements enclosed within curly braces. It represents diverse structures such as the body of contracts, functions, if-else statements, or loops. Additionally, blocks can also contain other nested blocks. 32 Chapter 2. The Solidity Compiler All the generated code is streamed into a single string variable that is later parsed into a Yul AST3to be analyzed. Finally, if the –optimize flag is set, the IR code is optimized using the Yul optimization module explained in Section 2.2.1.2. 2.1.3.2. EVM Assembly generation The generation of EVM assembly code, or ASM code, is the previous step to the final binaries generation. The assembly code is a human-readable low-level representation of the instructions that the EVM will execute. ASM code can be generated directly from the Solidity source code or from the generated IR code (–via-ir). Generate from source code. By default, the assembly code of the smart contracts is generated directly from the Solidity source code, using the AST generated at the parsing phase and completed during the analysis phase. In order to transform the code structures into assembly code, the compiler uses two different methods depending on the complexity and usage frequency of the structure: Transform statements directly to assembly code, as shown in Figure 2.15. 1m_context << dupInstruction(1 + _stackDepth); 2switch (_arrayType.location()) 3{ 4case DataLocation::CallData: 5// length is stored on the stack 6break; 7case DataLocation::Memory: 8m_context << Instruction::MLOAD; 9break; 10 case DataLocation::Storage: 11 m_context << Instruction::SLOAD; 12 if (_arrayType.isByteArrayOrString()) 13 m_context.callYulFunction(m_context.utilFunctions(). extractByteArrayLengthFunction(), 1, 1); 14 break; 15 } Figure 2.15: Compiler code excerpt that illustrates the direct transformation to assembly 3The Yul Abstract Syntax Tree is a syntax representation of the Yul code similar to the one used for Solidity code, but much simpler with only 18 types of nodes. See https://github.com/ ethereum/solidity/blob/28593839d9913a740e9c8514d2ba607241d54398/libyul/AST.h for more information 2.1. Phases of the Solidity Compiler 33 Use predefined function templates written in Yul, as in the IR generation, and generate the corresponding assembly code. This method is used to transform complex internal operations such as copying an array from storage to memory, as in the example shown in Figure 2.16. The predefined Yul templates are also used for functions in charge of ABI4encoding, decoding, and type conversions. 1m_context.callYulFunction(m_context.utilFunctions(). copyByteArrayToStorageFunction(_sourceType, _targetType), 3, 0); Figure 2.16: Compiler code excerpt that illustrates the usage of predefined Yul function Generate from IR. The EVM assembly generation from the IR code (Yul) is relatively straightforward. Since both representations operate at a similarly low level, each Yul statement can be translated into only a few assembly instructions. However, when generating the assembly code, the compiler has to track the evolution of the stack size and the position of each variable on it, making this process highly complex. In order to perform the code transformation, the compiler uses the previously generated AST of the IR, visiting each node and appending the transformations into an Assembly object containing the final assembly code. Figure 2.17 shows an example of a function used to transform an if structure in Yul to assembly code. 1void CodeTransform::operator()(If const& _if) 2{ 3visitExpression(*_if.condition); 4m_assembly.setSourceLocation(originLocationOf(_if)); 5m_assembly.appendInstruction(evmasm::Instruction::ISZERO); 6AbstractAssembly::LabelID end = m_assembly.newLabelId(); 7m_assembly.appendJumpToIf(end); 8(*this)(_if.body); 9m_assembly.setSourceLocation(originLocationOf(_if)); 10 m_assembly.appendLabel(end); 11 } Figure 2.17: Compiler code excerpt that illustrates the transformation from IR to assembly 4See more about the ABI specification at https://docs.soliditylang.org/en/v0.8.19/ abi-spec.html 34 Chapter 2. The Solidity Compiler 2.1.3.3. Bytecode generation The bytecode generation is the last phase of code generation in the compiler. In this phase, the assembly code is linked and assembled into the creation and runtime bytecode. The generated bytecode is the lowest-level language produced by the compiler, the hexadecimal representation of the EVM instructions, as the example shown in Figure 2.18. 6080604052348015600f57600080fd5b506004361060285760003560e01c806326121ff014 602d575b600080fd5b60336047565b604051603e91906072565b60405180910390f35b60 0060026000546056919060ba565b905090565b6000819050919050565b606c81605b565b 82525050565b6000602082019050608560008301846065565b92915050565b7f4e487b71 000000000000000000000000000000000000000000000000000000006000526011600452 60246000fd5b600060c382605b565b915060cc83605b565b925082820190508082111560 e15760e0608b565b5b9291505056fea2646970667358221220148429967791ea8a3f39c34 3c7247dc5662860f0c6e71d1c1440a899503ee0ac64736f6c637827302e382e32302d63692 e323032322e31302e382b636f6d6d69742e65376430363665342e6d6f640058 Figure 2.18: Runtime bytecode of the contract of Figure 2.3 In addition to generating EVM bytecode as a sequence of hexadecimal opcodes, the Solidity compiler can also output a human-readable representation of the EVM instructions. This output can be generated using the command-line option –opcodes. Figure 2.19 shows an example of the opcode representation of the bytecode. 1PUSH 80 2PUSH 40 3MSTORE 4CALLVALUE 5DUP1 6ISZERO 7PUSH 0x0f 8JUMPI 9PUSH 0 Figure 2.19: Opcodes representation of the first instructions on Figure 2.18 2.2. Code optimizations 35 2.2. Code optimizations During the code generation, compilers try to generate a target code as efficient as possible. In order to do that, the compiler transforms the code into a new, more efficient code. However code optimization is not a trivial task, as explained on the following paragraph extracted from the Dragon Book [1]: The challenge is that, mathematically, the problem of generating an optimal target program for a given source program is undecidable; many of the subproblems encountered in code generation such as register allocation are computationally intractable. In practice, we must be content with heuristic techniques that generate good, but not necessarily optimal, code. Fortunately, heuristics have matured enough that a carefully designed code generator can produce code that is several times faster than code produced by a naive one. [1, p. 505] There is a great variety of different code optimizations that compilers can perform, targeting different levels of abstraction and targeting different objectives, such as time efficiency, memory efficiency, or target code size. We can distinguish two main types of code optimizations on compilers: Machine-independent code. These optimizations are performed at an optimization phase prior to the target code generation, where the compiler transforms the IR into a new IR code from which a more efficient code can be generated. At this level, the optimizations are not tied to specific features of the targeted architecture, such as register or memory allocation. Machine-dependent code. These optimizations are performed over the target code at the end of the code generation process. At this level, optimizations are tied to the specific features of the targeted architecture, such as the stack allocation on the EVM. In the Ethereum blockchain, the efficiency of smart contracts is critical. The execution of each contract call has an associated gas cost which translates directly into an economic cost for the user. In a network where hundreds of thousands of contract calls are performed daily, reducing the execution cost of contract calls is crucial for developers, contract owners, and clients, especially when dealing with large-scale smart contracts. Accordingly, there is a high interest in generating the most efficient code possible regarding gas consumption, and the code optimization process for any code targeting the EVM is subject to intense research. In this section, we will discuss the state of the art on code optimizations in Ethereum. On the one hand, we will introduce the two optimization modules in the Solidity compiler, which respectively perform transformations on the IR and generated code in order to output the most efficient code possible. On the other 36 Chapter 2. The Solidity Compiler hand, we will cover some proposed work on pre and post-generation optimizations for code targeting the EVM. 2.2.1. Solidity compiler optimizations The Solidity compiler has two different optimizer modules that optimize the generated code in order to make it more efficient in terms of execution cost and code size. The optimizer modules of the compiler operate at two different levels. The ‘old’ module operates at the opcode level and focuses on performing small transformations on the generated code in order to improve its efficiency. In contrast, the ‘new’ optimizer operates at the IR code level and plays the role of the machine-independent code optimization module transforming the IR during the code generation process. On the current compiler version, both optimization modules are disabled by default and can be activated using the command line parameter –optimize. Additionally, we can use the parameter –optimize-runs to indicate an approximate number of times the contract is expected to be executed across its lifetime. This expected number of executions allows developers to establish on the optimizer a tradeoff between the code size, which affects the deployment cost, and the execution gas cost once deployed. In a contract that will be used only a few times, the compiler will prioritize producing a shorter code over the execution cost reduction. In contrast, for contracts that will be executed many times, the optimizer will generate more efficient code without caring about the length of the final optimized code. However, an optimized contract will probably consume less gas for deployment as well as for function calls. 2.2.1.1. Opcode optimizer The opcode optimizer was the first code optimizer implemented in the Solidity compiler. It operates at the opcode (bytecode) level applying simplification rules and removing unused and duplicated code. The opcode optimization takes place at the end of the code generation process, transforming the generated bytecode into a more efficient bytecode. Therefore, this module fits into the definition of a machinedependent code optimizer since it works directly on the target code instead of the IR. The optimizer divides the sequence of instructions on blocks delimited by JUMP instructions. Then it analyzes the instructions inside those blocks, keeping track of the stack, memory, or storage modifications. Finally, it applies several optimization phases in a loop until no optimization is possible. The optimizations applied are: FullInliner: replaces jumps to blocks containing simple instructions with a copy of the instructions in the block. 2.2. Code optimizations 37 JumpdestRemover: removes unused JUMPDEST instructions and their referenced tags. PeepholeOptimiser: optimizes small windows of instructions, replacing them with a more efficient sequence of instructions that produces the same result.5 BlockDeduplicator: unifies duplicated blocks. CommonSubexpressionEliminator: finds and combines equal expressions. ConstantOptimiser: replaces constant expressions by their computed values at compile time. The opcode optimizer module can be very effective at applying simple optimizations to the bytecode, reducing the gas consumption of a contract. However, it has some limitations. Because it operates on a very low level, it has limited information and understanding of the code. It can optimize small sets of bytecode instructions but cannot perform optimizations for high-level structures. Furthermore, because the low-level code is exceptionally complex to interpret, implementing new optimizations and proving its correctness is very challenging. For our purpose, it would be almost impossible to develop an optimization step for array accesses, as it would be very difficult to specifically target the bytecode sections corresponding to optimizable array accesses, and every change on the bytecode to optimize the accesses would have side-effects on the stack of the EVM. 2.2.1.2. Yul optimizer The Yul optimizer [14] was introduced in version 0.4.20 of the compiler [7]. It is an optimization module that operates on Yul code (the IR) and serves the role of the machine-independent code optimizer transforming the IR code during the code generation process in a way it leads to a more efficient generated bytecode. This module is much more powerful than the opcode optimizer. Since it operates at a higher level of abstraction, it can perform more sophisticated optimizations taking advantage of the semantics of the contract code. Furthermore, because there is no possibility of performing arbitrary jumps in Yul, the optimizer can compute the side effects of each function call. This allows the optimizer to perform sophisticated optimizations, such as code reordering or even function call removal. Finally, because it operates at a higher level of abstraction, it is easier for developers to understand, maintain and extend the optimizer. Now, developers do not have to figure out how to target optimizable patterns on the EVM assembly code nor deal with the side effects of the optimizations on the stack. This module generates an optimized IR code that the compiler will transform into ASM code. Consequently, if the optimized 5Read more about the peephole optimization in the Dragon Book [1, p. 549] 38 Chapter 2. The Solidity Compiler IR code is equivalent to the original IR code, the generated ASM code is guaranteed to be equivalent to the ASM code that would be generated from the original code. The Yul optimizer performs a predefined sequence of optimization steps to the AST of the generated IR, transforming it to optimize the code or to allow further optimizations. This set of steps can be personalized by the developer using the –yul-optimizations command-line parameter. These are some of the most relevant optimization steps detailed in the Yul optimizer documentation [14]: LoadResolver: replaces loads from memory or storage for its value if known. DeadCodeEliminator: removes unreachable code. EqualStoreEliminator: removes store instructions to memory or storage if there is an identical call without any changes on the parameter values in between. LoopInvariantCodeMotion: moves variable declarations outside the loop if such variables remain constant during the loop and have only read side effects or no side effects. ForLoopConditionIntoBody: moves the condition expression of the loop into the body. ExpressionInliner and FullInliner: replace function calls with a copy of the corresponding function body. When the optimization option on the compiler is activated, the Yul optimization can take place in two different phases of the compilation process. Default ASM generation. In the case the –via-ir flag is not set, the EVM assembly code is directly generated from the original Solidity code, as seen in section 2.1.3.2. However, as explained in the previously mentioned section, this code generation process uses, in some cases, predefined function templates coded in Yul. When the optimizations are activated, the generated Yul functions from those templates and the Yul code inside the inline assembly blocks will be optimized by the Yul module before being transformed into EVM assembly code. In this scenario, the Yul optimization has a limited effect on the final ASM code and, consequently, the bytecode. This is because it only optimizes small independent sections of the contract but does not optimize the contract as a whole. ASM generation via IR. If the –via-ir flag is set, the IR code is used to generate the EVM assembly code. Therefore, when the optimizations are enabled, the Yul optimizer module will optimize the IR code, and this optimized IR code will be used to generate the EVM assembly code. Consequently, in 2.2. Code optimizations 39 this scenario, the Yul optimizer has a much more significant impact on the code because all the code will be optimized as a whole, being able to capture relations between all the elements of the code. 2.2.2. Related work on code optimizations In addition to the compiler optimization modules, developers can find a great variety of external optimization tools focused on improving efficiency in Ethereum smart contracts. A relevant example of external optimizations for EVM code is GASPER, an optimization tool proposed in the article Under-Optimized Smart Contracts Devour Your Money [6]. In this article, a group of researchers from different Chinese universities described seven costly code patterns not being optimized by the Solidity compiler. Those patterns were separated into two categories. The useless code-related patterns category includes situations where a nested conditional evaluates to true or to false under all circumstances due to its relation with the condition they are enclosed into. Besides, the loop-related patterns collect simple loop patterns where expensive operations can be moved outside the loop or duplicated operations can be combined or removed. Finally, they implemented GASPER, a tool that automatically identifies the code-related patterns and expensive operations on loops, giving the developer valuable information to optimize the code. Another relevant work on the same area was presented in Characterizing Efficiency Optimizations in Solidity Smart Contracts [5], where a group of researchers from the Vienna University of Technology analyze the applicability of 25 optimization strategies for Solidity smart contracts. Those strategies are divided into: Time-for-Space Rules where memory and storage usage is reduced by not storing any value that can be computed when needed, which on the other hand, increases the execution time. Space-for-Time Rules where execution time is reduced by storing precomputed or frequently used data, which on the other hand, increases the use of memory and storage. Loop Rules that describe strategies to move code out of the loop, to reduce the number of conditional expressions inside the loop body, and to fusion loops. Logic Rules related to logic evaluations. These rules exploit identity properties, reorder evaluations, precompute conditions, and replace boolean variables with condition expressions. Procedure Rules that reduce the number of functions by performing inlining, 40 Chapter 2. The Solidity Compiler transforming iterative functions into recursive functions or Expression Rules that exploit identities remove common subexpressions and combine expressions. They concluded that while not all of the strategies discussed could be applied to programs targeting EVM or providing gas cost reduction, most of them, 21 out of 25, have direct applicability to smart contracts and have the potential to reduce gas consumption. Among these examples of research on smart contracts optimization, it is mandatory to mention the research carried out by the Costa Group6, a research group of the Complutense University of Madrid, in which this work has been developed. This group, dedicated to the research of optimization, verification, and understanding of programs, has carried out relevant publications related to smart contracts optimization in recent years. An example of their research work is GASOL (Gas AnalysiS and Optimization tooL) [2], a gas analyzer and optimizer for smart contracts. GASOL is a tool able to analyze Solidity functions according to different cost models that the programmer can select. It infers the gas cost associated with the targeted program as well as the number of EVM instructions that will require. Moreover, this tool detects optimizable patterns related to storage usage and optionally generates an optimized version of the Solidity code. Optimizations consist of substituting multiple accesses to the same storage value, which are expensive, by accesses to a copy of the value stored in memory, which is considerably cheaper. However, this transformation is only viable when the cost of creating the variable copy and updating the original variable with the final value is paid off by the saved gas on the memory accesses. Thus, it uses the cost analysis performed over the code to detect code sections where this transformation reduces gas costs. The analysis and optimization capabilities offered by GASOL make it an extremely powerful tool for developers seeking to create efficient Solidity smart contracts. The article Inferring Needless Write Memory Accesses on Ethereum Bytecode [3] is another example of external optimization developed by this group. This article describes a static analyzer that detects unnecessary memory write instructions on the EVM bytecode. The described analyzer identifies memory slot allocation, reads and writes, and detects memory write instructions to access a memory slot that is not being read afterward. This post-compilation optimization has proved to be useful in detecting optimization opportunities on real smart contracts, according to the results provided in the mentioned article. 6See more about Costa Group at their website: https://costa.fdi.ucm.es/web/. 2.2. Code optimizations 41 It is worth noting that the mentioned proposals from the Costa Group focus on reducing the execution cost by optimizing the usage of the memory layout (storage or memory) since the cost of loading or storing values from storage or memory often causes a significant portion of the total gas expense. In line with this shared motivation, the following chapters will introduce two new optimization proposals to reduce gas consumption on array accesses. 48 Chapter 3. Optional Checking Finally, we adapted the block parsing function of the compiler to the new grammar. To do so, we added a new step, shown in Figure 3.5, to check if the uncheckedArray token precedes the brackets that open the block being processed. 1bool const uncheckedArrayBlock = m_scanner->currentToken() == Token:: UncheckedArray; Figure 3.5: Modification on the parse of the uncheckedArray block It is important to note that we have added a new parser error in this phase, which is issued when an uncheckedArray block is found outside a regular block. Figure 3.6 shows the introduced parsing error. 1if (!_allowUncheckedArrayBlock) 2parserError(5297_error, "\" uncheckedArray\" blocks can only be used inside regular blocks."); 3advance(); Figure 3.6: New parse error 3.2.2.3. Syntax checking In order to ensure the correct syntax of uncheckedArray blocks, the compiler must check that they do not appear nested in the code. To do so, we have extended the SyntaxChecker with a variable to track when it is inside an uncheckedArray block. This variable is updated when an uncheckedArray block is accessed and exited during the syntax checking (performed using the visitor pattern) and used when an uncheckedArray block is accessed to check if the accessed block is inside another uncheckedArray block. Additionally, we have added a check in the block visit function to guarantee that the visited uncheckedArray block is not inside another one. 3.2.2.4. Type checking The uncheckedArray block does not impact how types must be checked within the block. Therefore, no modification is required. 3.2. Unchecked Array 49 3.2.2.5. Code generation Finally, the compiler has been modified to generate the correct code for index accesses performed inside an uncheckedArray block. Bounds checks on the array index array accesses are generated at an IR or ASM level, depending on whether the IR code is used to generate the ASM code. Consequently, we have only modified how the array index accesses are generated in the IR and ASM code. As seen in Chapter 2, the Solidity compiler has two modules in charge of generating these representations: the IR generator and the ASM generator. IR Code generation. The IR code generation for array index accesses uses predefined Yul util functions. Therefore, new util functions have been defined to generate the array accesses to each type of memory location, as the one being shown in Figure 3.7. 1function <functionName>(array, index) -> slot, offset { 2<?multipleItemsPerSlot> 3<?isBytesArray> 4switch lt(arrayLength, 0x20) 5case 0 { 6slot, offset := <indexAccessNoChecks>(array, index) 7} 8default { 9offset := sub(31, mod(index, 0x20)) 10 slot := array 11 } 12 <!isBytesArray> 13 let dataArea := <dataAreaFunc>(array) 14 slot := add(dataArea, div(index, <itemsPerSlot>)) 15 offset := mul(mod(index, <itemsPerSlot>), <storageBytes>) 16 </isBytesArray> 17 <!multipleItemsPerSlot> 18 let dataArea := <dataAreaFunc>(array) 19 slot := add(dataArea, mul(index, <storageSize>)) 20 offset := 0 21 </multipleItemsPerSlot> 22 } Figure 3.7: Predefined Yul util function for a storage index access inside an uncheckedArray block Since those new functions are inserted in the resulting code by the IRCodeGenerator, using the information from the AST node and the IRGenerationContext, we have 50 Chapter 3. Optional Checking extended the context so the generator can determine whether array access must include bounds checks. The solution is to include a new variable with two possible enum values: Checked or Unchecked. This variable stores the value Unchecked while the generator traverses the nodes inside an uncheckedArray block, and the value Checked otherwise. Then, the generator uses that information from its context to decide which predefined array access function to insert, as shown in Figure 3.8. 1m_context.uncheckedArrays() ? 2m_utils.storageUncheckedArrayIndexAccessFunction(arrayType) : 3m_utils.storageArrayIndexAccessFunction(arrayType)) Figure 3.8: Call to generate a storage array access in IR code EVM assembly code generation. The EVM assembly code generation is highly complex because of how local variables are treated on the limited stack of the EVM (Section 1.4 Chapter 1). Fortunately, the generated code of most of the basic operations is predefined, as it is on the IR code generation explained in the previous paragraph. This is the case of array operations such as push,pop, or length accesses, whose generated assembly code is defined in the ArrayUtils class. The modifications needed here are minimal as the function in charge of generating the array index access code already contemplated the possibility of not doing bounds checks over the array length. The official compiler version uses this option when the access is part of other larger operations, such as a push or an assignment of an array from memory to storage (copy of the array), where the soundness of the array accesses is guaranteed by construction. Therefore, we have extended the corresponding compiler context, as we did with the IR generation context, so the ExpressionCompiler can determine whether to add the bounds checks to the EVM assembly code. Figure 3.9 shows the modification made on the generator code in order to enable or disable the checks on array accesses based on the information of the compiler context. 1checkAccess = !m_context.uncheckedArrays(); 2ArrayUtils(m_context).accessIndex(arrayType, checkAccess); Figure 3.9: Call to generate the EVM assembly code of a storage array access 3.3. Targeted Unchecked Array To increase the power of this new gas-saving mechanism, we want it to support targeting specific arrays inside the block. With this slight improvement, developers 3.3. Targeted Unchecked Array 51 can include at the opening of the uncheckedArray block a list of the array bases that should not be checked on index access. The list is optional, and if it is not provided, none of the arrays accessed inside the block will perform bounds checks. In Figure 3.10, we can see how this new feature of the uncheckedArray block is used. 1// SPDX-License-Identifier: BSD-4-Clause 2pragma solidity >=0.8.4; 3 4contract C { 5uint256[] arrA; 6uint256[] arrB; 7 8function f(uint idx) pure public returns (uint) { 9// arrA access will not check out-of-bounds. 10 uncheckedArray(arrA) { 11 return arrA[idx] + arrB[idx]; 12 } 13 } 14 } Figure 3.10: Example of usage of targeted uncheckedArray block 3.3.1. Constraints In addition to the uncheckedArray block constraints (Section 3.2.1), there is a significant limitation when targeting array accesses. Since expressions cannot be evaluated at compilation time, array bases have to be literally compared. Therefore, array base expressions need to be transformed into strings to be compared. To avoid possible misunderstandings, we have extended the compiler with a new warning, shown in Figure 3.11. This warning rises when an expression different from an identifier is listed as a targeted array base. 1Warning: The array accesses performed over a base listed here will not perform index out-of-bounds checks. Comparison between array bases is literal. Only in those accesses with the same literal base the uncehckedArray will take effect. 2--> c.sol:11:22: 3| 411 | uncheckedArray(matrix[i]) { 5| ^^^^^^^^^ Figure 3.11: Warning about literal comparisons of the targeted array bases 52 Chapter 3. Optional Checking 3.3.2. Implementation The implementation of the optional target list on the uncheckedArray block required to extend most of the compilation phases originally modified3. We had to modify the AST block node and the parsing in order to retrieve and store the targets list, the different analyzers to check that each element in the list is valid and an array base, and finally, the code generator to only disable the bounds checks on the accesses to targeted arrays when specified. 3.3.2.1. AST Representation In addition to the original changes to the block node, we needed to extend the block node to store the list of the targeted array bases when provided. In order to do that, a vector of expressions has been added to the block attributes. Those provided expressions became then children of the block node in the AST. Therefore, the accept function (visitor pattern) of the block has also been modified to allow the visitors to access the array base list. This extension is fundamental to ensure that all the compiler checks are performed over the elements of the targets list. Finally, a method nodeToString has been defined for all the expression type nodes, so they can be literally compared between them (see 3.3.1). Figure 3.12 shows an example of the nodeToString() methods to represent member accesses. 1ASTString const MemberAccess::nodeToString() const { 2return expression().nodeToString() + TokenTraits::toString(Token:: Period) + memberName(); 3} Figure 3.12: Member access nodeToString method 3.3.2.2. Parsing The only difference when parsing this new version of the block is that the uncheckedArray block can now receive a list of parameters between the identifier and the opening braces of the block. Therefore, we have extended the grammar with this new feature, as shown in Figure 3.13, and modified the parser phase. Now, when the parser finds the uncheckedArray keyword, it looks for an opening parenthesis to parse the target list. If it founds an opening brace instead, it will treat 3All changes performed to the original compiler in order to implement this version of the uncheckedArray block the can be found at https://github.com/ethereum/solidity/compare/ develop...javierSande:solidity:targetedUncheckedArray. 3.3. Targeted Unchecked Array 53 the block as an uncheckedArray block where the bounds checks are disabled on all array index accesses. 1/** 2* A curly-braced block of statements. Opens its own scope. 3*/ 4block: 5LBrace ( statement | uncheckedBlock | uncheckedArrayBlock )* RBrace; 6 7uncheckedBlock: Unchecked block; 8 9uncheckedArrayBlock: 10 UncheckedArray block | UncheckedArray LParen (expression? ( Comma expression?)* ) RParen block; Figure 3.13: Grammar to parse blocks 3.3.2.3. Syntax checking This new feature of the uncheckedArray block has no other effect on the syntax checking than extending the checking over the expressions on the targets list. However, this was already solved when we adapted the accept function of the block node. 3.3.2.4. Type checking When a list of targets is specified in an uncheckedArray block, the compiler must perform type-checking on the expressions on that list. As with syntax checking, this was solved when we adapted the accept function of the block node. However, we also needed to implement a new type check over the parameter list to guarantee that all the parameters conform to valid array bases. In order to do that, we have modified the type checker so it traverses the list of bases, checking that its type belongs to the Array category and is not a string or byte array. Finally, we have modified the checker so it raises the warning described in Section 3.3.1 (Figure 3.11) whenever it finds on the targets list an array base expression that is not an identifier. 3.3.2.5. Code generation The only change in the code generation is how the IR and EVM assembly code generators decide whether array access must include the bounds checks. Now, we 54 Chapter 3. Optional Checking have three possibilities: The uncheckedArray block has no targets, so the bounds of all the arrays are unchecked. The uncheckedArray block has a list of targets, so only the bounds of targeted arrays are unchecked. We are outside any uncheckedArray block, so the bounds of all the array accesses are checked. Consequently, we have modified the generation contexts to be able to store the required information to identify these three scenarios. We keep the previously added variable, indicating if we are inside an uncheckedArray block that affects all the arrays (Unchecked) or not (Checked), and a new vector has been created in order to store the targeted bases, if any. Now, the code generator will query its context whether the array access must bypass bounds checks, as shown in Figure 3.14. With our modifications, the context will now answer affirmatively if the code is into an uncheckedArray block without targets (where all accesses are unchecked) or if the array base is literally equal to one of the targets stored in the context. 1checkAccess = !m_context.isArrayUnchecked(baseExpression); 2ArrayUtils(m_context).accessIndex(arrayType, checkAccess); Figure 3.14: Call to generate a storage array access in EVM assembly code 3.4. Results and experiments As explained at the beginning of this chapter, skipping the out-of-bounds checking on array index accesses reduces the consumed gas. By doing this, we save the cost of the length retrieval, the comparison, and other instructions that take part in the bounds check. Once we implemented the uncheckedArray block to bypass such bounds checks, we wanted to quantify the gas savings on array accesses. In order to do that, for each kind of access (in storage, memory, and calldata), we have performed a study on the bounds check bytecode, its instructions, and cost, quantifying the theoretical gas saving of removing the check. Finally, we have executed different smart contracts to measure the real impact of the uncheckedArray block. 3.4. Results and experiments 55 3.4.1. Storage gas saving Since accessing storage has the highest gas cost among all the possible memory accesses, we expect the uncheckedArray block to have the most important gas reduction when applied to storage array accesses. In Figure 3.15, we can observe the main part of the bounds check in the EVM assembly code: 1DUP2 2SLOAD // Load length 3DUP2 4LT // Compare 5PUSH2 60x75 7JUMPI // Jump to panic function Figure 3.15: Example of EVM assembly code for bounds checks on storage arrays From the observed code and according to the current gas costs published by the Ethereum foundation at EIP-2929 [8], by bypassing that check, we will save gas by not executing the following instructions: Two DUP2 instructions, with a cost of 3 gas units each. A load from storage (SLOAD), with a cost of 2100 units on the first access to the address and of 100 in later accesses. A comparison (LT), with a cost of 3 gas units. APUSH2 instruction, with a cost of 3 gas units. AJUMPI instruction, with a cost of 10 gas units. This results in an estimated gas save of 122 units. It is a theoretical result, and this gas-saving can be slightly different in practice since other instructions may be avoided or introduced to keep track of variables in the stack of the EVM, and the structure of EVM bytecode may be different, resulting in a different division of the code into blocks and, consequently, a different number of jump operations. Additionally, if the array length has not been previously accessed, we will save 2100 gas units on the first array access. Experimental results. To measure the gas savings using the uncheckedArray block, we have developed a simple benchmark. It comprises a smart contract with an array in storage and a function that iterates that array and computes the sum 56 Chapter 3. Optional Checking of its elements. This function has two versions: one that wraps the loop in an uncheckedArray block (Figure 3.16) and another without the uncheckedArray block. 1function accessStorage() public returns (uint) { 2uint sum = 0; 3uncheckedArray(array) { 4for(uint256 i = 0; i < array.length; i++) 5sum += array[i]; 6} 7return sum; 8} Figure 3.16: Tested function The benchmark has been executed several times with different array lengths, showing the following results: Iterations Original Gas Unchecked Gas Diff Diff per Iteration 1 26380 26279 101 101.00 10 51220 50012 1208 120.80 100 299620 287342 12278 122.78 1000 2783620 2660642 122978 122.98 Table 3.1: Gas savings on storage accesses In Table 3.1, we can see the results of executing the code shown in Figure 3.16 with and without the uncheckedArray block over arrays of 1, 10, 100, and 1000 elements. Results show that as we increase the array size and, consequently, the iterations to access the array, the saved gas per iteration tends to be 123 gas units. This saving is one unit higher than expected, and most probably, it is because bypassing the bounds check means we are avoiding an extra JUMP instruction (cost of 1 unit of gas) to exit from the block containing such a check. However, when executed on an array with only one array, the improvement is smaller than expected. If we only perform one iteration, we save 21 units less than expected (22 if we take 123 units as the new reference). This difference is because, as explained, removing the bounds checks, and therefore, some blocks of the code, may generate a redistribution of the bytecode. This redistribution can have side effects on the execution cost of the rest of the contract, increasing or decreasing the gas consumed. Looking at these results, we can interpret that in this specific case, we reduce the gas consumption by 123 units per iteration, but the rest of the function increases its consumption by 21 units. Therefore, if the function only performs one iteration, the gas saving will be 101 units, but as we increase the number of 3.4. Results and experiments 57 iterations, this extra cost is distributed between all the iterations, getting close to the 123 units of gas saved per iteration. Again, this is valid for this particular case. On other functions, the effect on the cost execution unrelated to the array index accesses can be different, even causing a reduction. Nonetheless, this side effect on the contract gas cost is minimal compared to the potential savings of the uncheckedArray block, especially when performing multiple accesses. 3.4.2. Memory gas saving In the case of arrays in memory, we expect the uncheckedArray block to have a lower impact on the gas cost. In Figure 3.17, we can observe the main part of the bounds check in the EVM assembly code: 1DUP2 2MLOAD // Load length 3DUP2 4LT // Compare 5PUSH2 60x75 7JUMPI // Jump to panic function Figure 3.17: Example of EVM assembly code for bounds checks on memory arrays From the observed code, according to EIP-2929 [8], we can conclude that by bypassing that check, we will save gas by not executing the following instructions: Two DUP2 instructions, with a cost of 3 gas units each. A load from memory (MLOAD), with a cost of 3 units. A comparison (LT), with a cost of 3 gas units. APUSH2 instruction, with a cost of 3 gas units. AJUMPI instruction, with a cost of 10 gas units. This results in a theoretical gas save of 25 units. However, as in the case of storage accesses, this number may vary slightly depending on the compiled contract. 64 Chapter 4. Compiler Optimizations of gas per iteration. Since accessing values from storage has a high cost, when the array size remains constant inside the loop, it is highly convenient to store the length of the array in a local variable (stack) outside the loop. This variable can then be used inside the loop condition, saving a storage load per iteration. As shown in Figure 4.2, it is a simple change on the code that can make us save around 100 gas units per iteration (cost of load from storage). Nonetheless, developers sometimes do not perform this optimization due to oversight or ignorance. 1function search(uint x) view public returns (uint,bool) { 2uint len = arr.length; 3for (uint i = 0; i < len; i++) { 4if (arr[i] == x) 5return (i,true); 6} 7return (0, false); 8} Figure 4.2: Example of optimized sequential search in Solidity There is another possible optimization for this loop, similar to the previous one, but which is only possible to perform in the source code using an inline assembly block. As we know from previous chapters, when accessing the elements in storage or memory arrays, the array length must be loaded to perform the bounds checking. This optimization aims to store such length on a local variable outside the loop and use it to check bounds on each array index access performed inside the loop. 4.1. Current Loop Optimizations Once the two optimization goals to implement in this phase of the project are set, we must study how the current optimizer modules of the compiler treat array length and index accesses inside loops. In the case of the opcode optimizer (see Section 2.2.1.1), since it works at a very low level, it can only optimize array accesses in very specific cases. Using the ConstantOptimizer, the module can replace the array length loads of static-sized arrays with the computed length at compile time. This has a gas-saving effect on index and length accesses over arrays with a predefined fixed size. However, this module performs no optimization on dynamic-sized arrays. On its side, the Yul optimization module (see Section 2.2.1.2), in very specific situations, is able to perform the optimizations mentioned in the introduction of this chapter on dynamic-sized arrays. By using the LoopInvariantCodeMotion step 4.1. Current Loop Optimizations 65 together with function inlining, the Yul module is able to identify some situations where the array length load can be performed outside the loop, as we see in the next section. 4.1.1. Loop Invariant Code Motion The Loop Invariant Code Motion is an optimization step of the Yul optimizer module, introduced in Section 2.2.1.2 of Chapter 2. This step analyzes the body of the loop and moves variable declarations outside the loop if such variables remain constant during the loop and have only read side effects (e.g., a load from storage or memory) or no side effects. This optimization is very powerful because it can prevent the program from computing expressions with constant results on each iteration. However, since this module works at a relatively low level, it presents two significant limitations that restrict the situations where the optimization can be applied. Foremost, it works only at the top level in the loop body and post block, i.e., variable declarations inside conditional branches will not be considered for moving. And second, it cannot reason about fine-grained storage or memory locations. Consequently, if the code writes to any location in the same memory region (storage or memory) inside the loop body, the compiler is not able to determine whether the location written corresponds to the length of the array being cached or to any other location in the storage or memory, and, consequently, the optimization is not applied. 4.1.2. Real case analysis In order to completely analyze how this optimization works on both index and length array accesses inside the loop, we let us take the function shown in Figure 4.3 as an example. This function is one of the particular situations where the Yul optimizer is able to optimize the array length access and the array index access by extracting the array length loads from the loop. In the following explanation of how this loop is optimized, we will only focus on the steps that directly affect the array length and index access. Since the IR code has high complexity and the complete optimization process makes the result very difficult to interpret, the code shown to support the explanation is just a representation of how the real IR code would be modified if we only apply the mentioned optimization steps. Therefore, many optimization steps have been left aside, some expressions have been simplified, and certain variables have been conveniently renamed or deleted. 66 Chapter 4. Compiler Optimizations 1function sum() view public returns (uint) { 2uint s = 0; 3for (uint i = 0; i < arr.length; i++) 4s += arr[i]; 5return s; 6} Figure 4.3: Function to add the elements of an array The Yul code shown in Figure 4.4 corresponds to the IR generated by the compiler for the function of Figure 4.3. Observe that the loop condition has been moved to the loop body (Lines 10-13). This code reordering is performed by the optimization step ForLoopConditionIntoBody, which moves the condition expression of the loop into the body. This optimization step is applied by default when generating the IR code of loops, even if the optimizations are disabled. It is important to note that the generated code uses Yul functions for performing basic operations on the array at Lines 12, 17, and 18. We will focus on the calls highlighted at Lines 12 and 17, which code is shown in Figure 4.5. Once the compiler has generated the IR code, it will start with the optimization process. The first relevant steps of the loop optimization performed by the compiler are related to function inlining. During this process, the optimizer module will try to replace function calls in the code with the body of the called function. This process is performed in two different steps, the ExpressionInliner and the FullInliner, which target different kinds of function calls: Expression Inliner. The expression inliner step inlines functions to replace calls inside functional expressions. This optimization step is applied when the following conditions hold: •The expression returns a single value. •It is on the left side of a variable assignment. •The expression has only movable1arguments. •The expression has arguments that are small constants or that are referenced less than twice in the function body. Therefore, in the case of array access optimizations, the expression inliner will exclusively affect the call to the auxiliary length loading function at Line 12 as it complies with all the conditions. In contrast, the auxiliary function in 1According to the compiler documentation, an expression is considered movable "if it is sideeffect free and its evaluation only depends on the values of variables and the call-constant state of the environment". 4.1. Current Loop Optimizations 67 1function fun_sum_34() -> var__7 { 2var__7 := zero_value_for_split_t_uint256() 3let var_s_10 := convert_t_rational_0_by_1_to_t_uint256(0x00) 4 5for { 6let var_i := convert_t_rational_0_by_1_to_t_uint256(0x00) 7} 1 { 8var_i := increment_t_uint256(var_i) 9} { 10 // Loop condition: i < arr.length 11 let _slot := 0x00 12 let expr_19 := array_length_t_array$_t_uint256_$dyn_storage( _slot) 13 if iszero( lt(var_i, expr_19) ) { break } 14 15 // Load arr[i] 16 let _1_slot := 0x00 17 let _8, _9 := storage_array_index_access_t_array$_t_uint256_$dyn_storage( _1_slot, var_i) 18 let _10 := read_from_storage_split_dynamic_t_uint256(_8, _9) 19 20 // sum += arr[i] 21 var_s_10 := checked_add_t_uint256(var_s_10, _10) 22 } 23 24 var__7 := var_s_10 25 leave 26 } Figure 4.4: IR code from Figure 4.3 charge of the array access at Line 17 does not comply with the first condition, as it returns two variables. Full Inliner. The full inliner step performs function inlining if the transformation does not lead to a larger code. Therefore, it inlines functions only if the called function is very small or if it is called only a few times in the entire code. Consequently, the array length getter would also be inlined by this optimization step because its body comprises a single instruction. Nevertheless, since the auxiliary function to perform the array index access is considered a large function, it will only be inlined into large functions if used only a few times in the code. Our experiments detected that the optimizer does not inline the 68 Chapter 4. Compiler Optimizations function call with more than three index accesses expressions on the code. Additionally, if several functions contain array accesses, the inlining does not occur. We cannot establish an exact heuristic since this behavior varies depending on the code size, how many accesses are produced, and where they are produced. However, we can establish that this is a major limitation because in most of the cases tried, with experimental and real contracts, this inlining is not produced, and, without this inlining, the following optimization steps over the array access are not possible. 1function storage_array_index_access_t_array$_t_uint256_$dyn_storage( array, index) -> slot, offset { 2//Bounds check 3let arrayLength := array_length_t_array$_t_uint256_$dyn_storage( array) 4if iszero(lt(index, arrayLength)) { 5panic_error_0x32() 6} 7// Compute the storage slot of the element in the array 8let dataArea := array_dataslot_t_array$_t_uint256_$dyn_storage( array) 9slot := add(dataArea, mul(index, 1)) 10 offset := 0 11 } 12 13 function array_length_t_array$_t_uint256_$dyn_storage(value) -> length { 14 length := sload(value) 15 } Figure 4.5: IR auxiliar functions used in Figure 4.4 Since our code contains a single array access, the inlining process will successfully replace the function calls to the array length getter and the array index access auxiliary functions, shown in Figure 4.5. In Figure 4.6, we can observe the code resulting from this optimization process. Finally, the loop invariant code motion step will try to move outside the loop the declaration of variables that remain constant inside the loop. Since there is no side-effect on loading the array length and the length remains constant (there is no writing to storage), the optimizer will be able to move both array length loads, the one for the loop condition and the one for the loop access. Here is where having the array index access inlined is critical. Because it is inlined, the array length access for the bounds checks (Line 11 in Figure 4.6) can be identified as a constant expression by the loop invariant code motion. If it were not inlined, the length load would be performed inside the array index access auxiliary function that is called inside 4.1. Current Loop Optimizations 69 the loop with variable arguments (the index being accessed) and, consequently, a non-constant expression. 1function fun_sum_34() -> var__7 { 2var__7 := zero_value_for_split_t_uint256() 3let var_s_10 := convert_t_rational_0_by_1_to_t_uint256(0x00) 4 5for { 6let var_i := convert_t_rational_0_by_1_to_t_uint256(0x00) 7} 1 { 8var_i := increment_t_uint256(var_i) 9} { 10 // Loop condition: i < arr.length 11 let expr_19 := sload(0x00) 12 if iszero( lt(var_i, expr_19) ) { break } 13 14 // Load arr[i] 15 let _1_slot := 0x00 16 17 //Load array length 18 let arrayLength := sload(_1_slot) 19 20 //Bounds check 21 if iszero(lt(var_i, arrayLength)) { panic_error_0x32() } 22 23 // Compute the storage slot of the element in the array 24 let dataArea := array_dataslot_t_array$_t_uint256_$dyn_storage( _1_slot) 25 slot := add(dataArea, mul(var_i, 1)) 26 offset := 0 27 28 // Load value from storage 29 let _10 := extract_from_storage_value_dynamict_uint256(sload( _1_slot), offset) 30 31 // sum += arr[i] 32 var_s_10 := checked_add_t_uint256(var_s_10, _10) 33 } 34 35 var__7 := var_s_10 36 leave 37 } Figure 4.6: Optimized IR code after applying ExpressionInliner and FullInliner steps to the code in Figure 4.4 70 Chapter 4. Compiler Optimizations In this particular case, the optimizer will even detect that the loop condition expression (Line 12 in Figure 4.6) and the condition expression of the bounds check on the array access (Line 21 in Figure 4.6) are the same. Since the first condition leads to an exit of the loop when reached, the second condition always evaluates to true, so the optimizer will remove the bounds check on the array access. Figure 4.7 shows the IR code after optimizing the array length and access loads. In this Figure, we can see that the code reading the length of the array has been moved out of the loop to Line 4. If the conditions were not equal, the bounds check would have remained on the code, but since both load expressions (Line 11 and 18 in Figure 4.6) are equivalent, the optimizer will remove one of them and use the same variable for both conditional expressions. 1function fun_sum_34() -> var__7 { 2var__7 := zero_value_for_split_t_uint256() 3let var_s_10 := convert_t_rational_0_by_1_to_t_uint256(0x00) 4let arrayLength := sload(0x00) 5 6for { 7let var_i := convert_t_rational_0_by_1_to_t_uint256(0x00) 8} 1 { 9var_i := increment_t_uint256(var_i) 10 } { 11 // Loop condition: i < arr.length 12 if iszero( lt(var_i, arrayLength) ) { break } 13 14 // Load arr[i] 15 // Compute the storage slot of the element in the array 16 mstore(0, ptr) 17 let dataArea := keccak256(0, 0x20) 18 19 slot := add(dataArea, mul(var_i, 1)) 20 let _10 := extract_from_storage_value_dynamict_uint256(sload( slot), 0) 21 22 // sum += arr[i] 23 var_s_10 := checked_add_t_uint256(var_s_10, _10) 24 } 25 26 var__7 := var_s_10 27 leave 28 } Figure 4.7: Optimized IR code after applying LoopInvariantCodeMotion step to the code in Figure 4.6 4.2. A new optimization phase 71 To summarize, after all these optimization steps are applied, some unnecessary variables are removed, and the generated code will produce two fewer loads from storage per iteration than the original one, resulting in a great improvement in contract efficiency. If the array were stored in memory, the optimization process would be the same, but the amount of gas saved would be much lower because the cost of loading values from memory is only three gas units in most cases. In the case of an array in calldata, the optimization would not have any effect since the length of the array would already be stored in the stack. However, this is an ideal case. As we have seen during the process, the optimization module has several important limitations: Regarding array length accesses inside the loop, the following conditions must hold: •There is no write to storage inside the loop. •The array length access must be at the loop body top level and not inside any other structure, such as if-then expressions or nested loops. Regarding array index accesses, an additional very strong limitation is required: •The code can only have a few array index accesses in the entire contract, usually less than four2. This last constraint makes it almost impossible to take advantage of this optimization module on array accesses on smart contracts. In this analysis of the current optimizations on arrays inside loops, we have seen that even though they exist and they are quite powerful, they can be used in very limited situations, especially in the case of array index accesses. Consequently, it would be interesting to create a new array access optimization, based on the same principles, that overcomes most of the current limitations and, therefore, covers a much wider range of situations. 4.2. A new optimization phase Knowing the limitations of the current optimizer modules when dealing with loops and array accesses, we decided to implement a new optimization phase at a higher level of abstraction. This new optimization phase overcomes most of the 2This number may vary slightly depending on the size of the contract and function where the accesses are performed. 72 Chapter 4. Compiler Optimizations limitations faced by the Yul optimizer. We propose to directly generate optimized array access in IR code, using all the information we can extract from the AST of the Solidity code. This extra information gives the optimizer a significant advantage compared to the current modules, allowing us to optimize array accesses, both to their length and by index, in a broader range of situations. Additionally, this new optimization phase opens a new window to further complex optimizations that could not be implemented on the existing modules. For example, this optimization allows storage modifications that do not affect the array length inside the loop. At the Yul level, the optimizer can only see a SSTORE instruction to a dynamically computed storage slot, and it can not know if that slot is the one containing the length of the array. But now, at the Solidity level, the optimizer can distinguish between a storage modification that affects the array length, such as a push or pop operation, and a modification of the value of an array index that does not have any side effect on its length. 4.2.1. Applicability constraints The first constraint of this new optimization is that it is only performed over storage arrays. The reason is that while the gas cost of loading a value from storage is high (100 gas units according to EIP-2929 [8]), the load from memory is cheap (3 gas units). Therefore, when optimizing memory arrays, the margin is so low that only the new instructions needed at EVM bytecode level to keep the array lengths on the stack during the whole loop may be more expensive than loading it when required. We leave as a future work the study of an optimization that can also obtain gains with memory arrays. In the case of calldata arrays, this optimization has no sense as they do not need their length to be loaded when being accessed. A fundamental part of this optimization is to set the conditions that guarantee that the generated code is equivalent to the original. Since we are moving the array length load outside the loop, we need to guarantee that the length remains constant during the execution of the loop. In order to do that, we have first to identify all the ways the array length of a storage array can be modified in Solidity code and then to establish the constraints that guarantee a safe application of the optimization: Doing a push operation on the array. Doing a pop operation on the array. Assigning a new array to the array storage variable. Using an inline assembly block. Calling a function that performs any previously mentioned operation. 4.2. A new optimization phase 73 Push and Pop. Push and pop operations increase or decrease by one unit the length of the array they are applied to. This operation can be performed over the dynamic storage arrays using the contract state variable as well as a memory pointer that points to the array, which makes it very difficult to keep track of which storage array is being modified. Therefore, we have established as a constraint that the optimization only is performed if there is no push nor pop operation over any array inside the loop. Array copy. In Solidity, assignments between storage and memory and between state variables create an independent copy. Therefore, any assignment of an array (in storage, memory, or calldata) to a state variable results in the array being copied to the state variable and, consequently, changing its length. In order to solve this situation, the optimizer does not optimize array accesses where its array base is assigned with another value inside the loop. Inline Assembly. Inline assembly blocks perform low-level operations using the Yul language, such as direct accesses to storage using SLOAD or SSTORE bytecode instructions. Therefore, when analyzing inline assembly blocks, we face the same limitations as the Yul optimizer: we cannot identify if a SSTORE instruction is modifying the length of an array being used inside the loop. Consequently, the optimization is not performed if there is an inline assembly block inside the loop. Function calls. Finally, the length of an array can be modified by calling a function that performs any of the previous operations. Therefore, we must guarantee that no modification to an array length is done in the called function or any function called from it. This would require elaborating and analyzing the function call graph, as well as complex reasoning and soundness proof. However, this is out of the scope of this project phase. In order to simplify the check of this condition, we have established a more restrictive constraint that guarantees the previous one: the called function does not modify the state of the contract in any way (there are no writes to storage). We can easily identify if a function modifies the contract state using the state modifiers (see mutability checking in Section 2.1.2 of Chapter 2). These modifiers guarantee that all functions transitively reachable must have declared the same or a more restrictive modifier, and thus we do not need to perform any traversal of the function call graph. Using them, we can establish that the optimization will not take place if there is a call to a function that is not view or pure. Another important constraint for this new optimizer is that it only operates on accesses where the base expression is a variable identifier. Therefore, we can only optimize accesses to one-dimensional arrays or to the first dimension of multidimensional arrays. If we wanted to optimize accesses to the second and following dimensions of the array, we would need to store outside the loop the length of each array accessed in each dimension. That solution would not be practical for two main 80 Chapter 4. Compiler Optimizations the new –optimize-arrays flag. 1Optimizer Options: 2--optimize Enable bytecode optimizer. 3--optimize-runs n (=200) 4The number of runs specifies roughly how often each 5opcode of the deployed code will be executed across the 6lifetime of the contract. Lower values will optimize 7more for initial deployment cost, higher values will 8optimize more for high-frequency usage. 9--optimize-yul Legacy option, ignored. Use the general --optimize to 10 enable Yul optimizer. 11 --no-optimize-yul Disable Yul optimizer in Solidity. 12 --optimize-arrays Enable array access optimizer in Solidity. Same effect as --optimize and --via-ir. 13 --yul-optimizations steps 14 Forces yul optimizer to use the specified sequence of 15 optimization steps instead of the built-in one. Figure 4.14: Optimization options of the compiler 4.3. Results and experiments As explained at the beginning of this chapter, this new optimization stores the length of storage arrays being accessed (both to access its length or index) inside a loop on a local variable (stored in the stack). Then this variable is used to replace length loads on length accesses (e.g., condition of the loop) and bounds checks on index accesses. With this slight change in the code, we save the cost of loading a value from storage on each array access on each iteration of the loop. We only maintain the cost of the first length load, which is now performed previous to the start of the loop. Therefore, we are saving 100 gas units per access on each iteration 4in each iteration except the first one. However, since we are adding the array lengths to the stack, the generated bytecode may introduce new instructions to keep these values on the top of the stack during the loop execution. Consequently, the final saved amount may be slightly lower. Nevertheless, the difference between the cost of operations on the stack (e.g., PUSH,POP,DUP), which usually varies between 1 and 3 gas units, is much lower than a load from storage (100 gas units) so only on remote cases the optimization may not reduce the gas consumption because of those extra instructions. 4According to EIP-2929 [8], the cost of the first access to a storage slot is 2100 gas units. However, since we maintain this access, this does not affect the saving computation. 4.3. Results and experiments 81 Additionally, there is a specific case where the optimization increases the gas consumption: if the loop is not accessed. Since with the optimization, the array lengths are loaded before entering the loop, if the loop is not accessed, we will produce extra loads from storage. This issue can be easily solved in future work by wrapping the array loads on a conditional statement with the same condition as the array loop. 4.3.1. Simple experiment In order to prove the theoretical gas saving per access, we used a simple function similar to the one used in the previous chapter to test the uncheckedArray block. Figure 4.15 shows the tested function, which saves the sum of two arrays in one array, all in storage. 1function sumArrays() public { 2for(uint256 i = 0; i < size; i++) 3a[i] = b[i] + c[i]; 4} Figure 4.15: Tested function The execution of this simple benchmark on arrays of different lengths (1, 10, and 100 elements) produced the results shown in Table 4.1. Iterations Original New Optimization Diff Diff per Iteration 1 36305 36376 -71 -71.00 10 278387 275965 2422 242.20 100 2699207 2671855 27352 273.52 Table 4.1: Gas cost difference between using the original optimization and the new optimization We observe that our new optimization increases gas consumption when executing the code over an array with a single element. This consumption increase is because, as explained, the optimization takes the length loads out of the loop, but they are still performed once. Consequently, since the optimization cannot reduce the number of loads but still introduces an extra cost by creating new local variables, the final gas cost is slightly increased (less than an 0.2%). However, as we increase the length of the array and consequently the number of iterations, the optimization becomes more effective, increasing the gas saves per 82 Chapter 4. Compiler Optimizations iteration to an amount close to the expected 300 gas units (3 length loads from storage) for this case. 4.3.2. Real life experiments The main goal during this phase is to improve the current array access optimizations providing a new optimization that covers a much more comprehensive range of scenarios and that can be used on real code without any needed modification, as required with the uncheckedArray block. Therefore, we want to measure the efficiency of this new optimization on the code of contracts currently being used in the Ethereum blockchain. In order to do that, we have selected public smart contracts and libraries that developers frequently use to manage arrays and matrices. Using such libraries and contracts, we have developed a benchmark 5to measure the gas saving when applying our new optimization. This benchmark is composed of three different test suites that use three real libraries to perform different operations over storage arrays and matrixes. We have slightly modified the code of some of the original libraries to adapt them to the current compiler version and only use storage arrays. In order to evaluate the gas savings produced with this new optimization, we have used the same optimization setup for both the current compiler and the compiler with our new optimization. We have set up the –optimize and –via-ir flags, which generate the most optimized code the current optimizations can generate. Array Library. The Array test suite uses an array management library from the Solidity Standard Library [4]. This library repository provides two libraries, UintArray and IntArray, to manage arrays of unsigned and signed integers. Both libraries are implemented as contracts that store the integer array in a state variable (in storage), allowing the calling contract to perform different operations over the array. In order to develop our test suite, we have selected three methods of the UintArray library (maximum value getter, the minimum value getter, and the sum of the elements of the array), and we have created three different tests where we create an array, call the corresponding method and verify the correctness of the returned value. Moreover, since the library was developed with a target to the 0.4.0 version of the compiler, we had to modify some function declarations in order to adapt themselves to the current compiler version restrictions, such as the constructor definition or the memory space declaration on function reference parameters. 5The used benchmarks can be consulted at https://github.com/javierSande/ solidity-benchmarks.git. 4.3. Results and experiments 83 We have computed the gas savings by executing each test three times over arrays of 100 elements sorted in ascending order, descending order, and randomly generated. Table 4.2 and Figure 4.16 show the average gas consumption of each test with and without our optimization. Method Original Gas Optimized Gas Diff Percentage Max 299687 280597 19090 6.37% Min 296619 278543 18076 6.09% Sum 300269 282369 17900 5.96% Table 4.2: Gas savings on Array Library tests 0 50000 100000 150000 200000 250000 300000 350000 testMax testMin testSum Gas units consumed Gas Consumption Comparison Original Array Access Optimized Figure 4.16: Comparison of the gas cost between original code and optimized code The results show a gas reduction of around 6% on each test. We can observe that the sum test has a slightly lower saving than the other two tests because, on this test, the array is accessed only once per iteration, while on the other tests, it is accessed twice whenever local minimums or maximums are found. Additionally, we can observe s a slight difference in gas consumption and saving between the maximum and minimum getter tests, which are technically identical in terms of performance, which is explained because of the randomness of the array. Probably, the array sorted randomly produces more accesses when looking for the maximum (more local maximums), which explains the higher average gas cost and the higher gas saving on the max test over the min test. From these results, we conclude that the optimization produces a significant gas saving even in functions where arrays are accessed only a few times per iteration, where the potential gas reduction is lower. 84 Chapter 4. Compiler Optimizations Matrix Library. The Matrix test suite has been developed using the SolMATe libraries [20] for floating-point computation, array manipulation, and linear algebra. From it, we took the VectorUtils and MatrixUtils libraries to develop several tests on array manipulation. With these test suites, we want to measure the efficiency of our optimization when manipulating matrices, even when it can only optimize accesses to the first dimension of a matrix. We have developed six tests to add, multiply, and transpose matrices, add or multiply a matrix by a number, and compute the diagonal of a matrix. Since both libraries only supported memory arrays, they have been modified to be able to operate over storage arrays. Additionally, some unused functions were removed. Each test calls a library function that receives storage matrices as parameters and returns a new matrix or vector (diagonal) stored in memory. Therefore, our new optimization will only reduce gas from the array read accesses, limiting its potential even more. Method Original Gas Optimized Gas Diff Percentage Add Matrix 833995 751526 82469 9.89% Add Number 511443 441897 69546 13.60% Diagonal 100008 97978 2030 2.03% Dot 1868660 1751896 116764 6.25% Multiply Number 515487 445941 69546 13.49% Transpose 462439 417172 45267 9.79% Table 4.3: Gas savings on Matrix Library tests 0 200,000 400,000 600,000 800,000 1,000,000 1,200,000 1,400,000 1,600,000 1,800,000 2,000,000 testAddMatrix testAddNum testDiagonal testDot testMulNum testTranspose Gas units consumed Gas Consumption Comparison Original Array Access Optimized Figure 4.17: Comparison of the gas cost between original code and optimized code 4.3. Results and experiments 85 Tests have been executed over a storage 10 x 10 matrix with random integer values, using both the current compiler and the modified compiler containing our new optimization. Despite the limitations, with our optimization, we reduce the gas consumption between 9% and 14% in most tests. Table 4.3 and Figure 4.17 show a great reduction in tests with many array accesses per iteration, such as additions and multiplications, where all the array elements are accessed. Nonetheless, we also observe a very low gas reduction on the diagonal test, which performs much fewer array accesses than other tests. As shown in Figure 4.18 in a 10 x 10 matrix, the function only performs ten iterations with two array index accesses (1 to the rows and 1 to the columns) per iteration, where we only optimize the row access (first dimension). The test performs an identical operation to check that the diagonal values are correct, so we have to double the number of iterations. From those 20 iterations, we are getting a saving of 2030 gas units, which means we are saving around 100 units per iteration. Knowing that the loop complies with the current compiler constraints to optimize the array length access on the condition, we can conclude that our optimizer is saving this extra gas from each array index access in the loop. Therefore, our optimization is using its maximum potential, and the only reason the saving percentage is low is that most of the gas consumption on the function is produced by other operations, such as creating the memory vector6. 1function diag(int256[][] storage a) internal view returns (int256[] memory) { 2int256[] memory diagonal_vector = new int256[](a.length); 3for (uint i=0; i<a.length; i++) { 4diagonal_vector[i] = a[i][i]; 5} 6return diagonal_vector; 7} Figure 4.18: Diagonal function of the MatrixUtils library The case of the dot test is similar. Although the dot operation requires accessing every value in the array since it is a complex function with three nested loops, it has a high gas cost derived from other operations, and consequently, the percentage of the saved gas may be lower but still significant (more than 100,000 gas units). Those results prove that our new optimization, despite its limitations on multidimensional arrays, performs well when optimizing matrix accesses. It is also probable that as we increase the number of dimensions of an array, this performance decreases, 6The creation of vector in memory has relatively high cost due to memory expansion (EIP2929 [8]). 86 Chapter 4. Compiler Optimizations but the use of storage arrays of 3 or more dimensions is not frequent in Solidity smart contracts since the cost of manipulating them is extremely high. Sorting Library. The Sorting tests suite is a collection of the most common sorting methods in programming adapted to Solidity, contained in the SortLib library. Sorting methods are one of the most access intense manipulations of arrays, performing several array index accesses per iteration in order to read, compare and reorder values. Consequently, they are a great benchmark to measure the real potential of our optimization on a complex array manipulation. On the SortLib library, we have included several integer sorting methods with different complexities: the selection, insertion, and bubble (standard and optimized) sort methods, which have a n2time complexity, and the heap sort method with a nlogn time complexity. Using the mentioned library, we have developed several tests to call the corresponding sorting method and check the result. Each test has been executed three times with an array with 100 integers sorted in ascending (best-case scenario), descending (worst-case scenario), and random order to guarantee reliable average gas consumption results. 0 1000000 2000000 3000000 4000000 5000000 6000000 7000000 8000000 9000000 10000000 testBubbleSort testBubbleSortOptimized testHeapSort testInsertionSort testSelectionSort Gas units consumed Gas Consumption Comparison Original Array Access Optimized Figure 4.19: Comparison of the gas cost between original code and optimized code Table 4.4 and Figure 4.19 show the average gas consumption on each test for the code compiled with and without our new optimization. These results indicate that our optimization produces a remarkable reduction of gas consumption, between 10% and 17% of the total gas cost, independently of the order of complexity of the sorting method. 4.4. Conclusions 87 Method Original Gas Optimized Gas Diff Percentage Bubble Sort 7928770 6828488 1100282 13.88% Bubble Sort Optim. 8948553 7441954 1506599 16.84% Heap Sort 2184631 1876938 307693 14.08% Insertion Sort 6314264 5356155 958109 15.17% Selection Sort 4069664 3623238 446426 10.97% Table 4.4: Gas savings on Sort Library tests 4.4. Conclusions In this chapter, we have presented a new optimization for array accesses performed inside loops. As explained, this is an optimization already being performed by the Yul optimizer module of the official compiler. However, since this optimization is being performed at Yul level, the compiler lacks much important information about the code behavior. Consequently, the amount of optimized Yul code is limited and can only target particular cases. As a solution to the significant limitations of the Yul optimizer, we have proposed a new optimization phase at a higher level. This new phase works with information from the source code and its AST, having much more information on the effects of the code on the program state and, therefore, overcoming most of the limitations the Yul optimizer faces. Then, we implemented a new array optimization in this new phase using the same idea as the original optimization. This optimization identifies accesses to storage arrays inside loops, analyzes if their length remains constant on each iteration, and moves the load of their lengths outside the loop when possible, avoiding loading the length on each iteration. In order to prove the effectiveness of this new optimization, we have compared the gas consumption of different smart contracts when only applying the current optimizations and when adding our optimization. Firstly, we have compared the consumption of a simple contract to identify the origin of the gas savings easily. Results show us that the gas savings are as expected and that, even in simple contracts, the proposed optimization goes further than the current optimizer. Finally, we have compared the gas consumption over real libraries used by developers to manage arrays in their smart contracts. The results have shown a more than considerable reduction in gas consumption, exceeding the 10% in most cases. This new compiler optimization has proved to be almost as efficient as the uncheckedArray block when reducing the gas cost of accessing storage arrays. Additionally, it has two advantages over the mentioned block: it preserves safety, and we do not need to modify code to get optimized accesses. On the downside, it only optimizes array accesses inside loops and in specific situations where the compiler can guarantee that the array length remains constant. Conclusions and Future Work We started this project with the aim of optimizing array accesses in Solidity smart contracts. In order to do so, we focused on reducing the overhead produced by bounds checks. The initial study of the Solidity language, its compiler, and the optimization strategies used to reduce gas consumption on smart contracts allowed us to present and implement two optimization proposals to accomplish our initial goal. The first proposed solution was to allow programmers to disable bounds checks on index accesses. In order to do so, we based ourselves on a solution currently used in the Solidity language that disables underflow and overflow checks on arithmetic operations, the unchecked block. From this idea, we came up with a new language construct, the uncheckerArray block, that disables bounds checks on any array access enclosed in the block, and which has proven its effectiveness on experimental results, reducing gas consumption in memory, calldata, and, most significantly, storage arrays. However, this solution is not perfect. It puts safety in the hands of programmers, requires to modify the code, and is not able to reduce gas consumption of accesses where the bounds checks are needed. All these drawbacks of the first solution motivated a completely different one: an optimization at compile time. In this second solution, we wanted to create a new compiler optimization on array accesses. From the study of the current compiler, we discover that the optimizations being performed are limited by the low-level information about the code they have. Accordingly, we implemented a new optimization phase that takes place during the IR generation, using the information from the Solidity source code and its AST. Using this new phase, we implemented a new optimization that targets storage array accesses inside loops, reducing its gas cost derived from the length load on bounds checks. This new optimization has proven a remarkable efficacy, showing substantial gas 89