Forklift: An Extensible Neural Lifter

Authors: jordi  armengol-estapé
rodrigo c o rocha
jackson  woodruff
pasquale  minervini
michael f p o'boyle
Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-23 02:42:20

Abstract: The escalating demand to migrate legacy software across different Instruction Set Architectures (ISAs) has driven the development of assembly-to-assembly translators to map between their respective assembly languages. However, the development of these tools requires substantial engineering effort. State-of-the-art approaches use lifting, a technique where source assembly code is translated to an architecture-independent intermediate representation (IR) — for example, the LLVM IR — and use a pre-existing compiler to recompile the IR to the target ISA. However, the hand-written rules these lifters employ are sensitive to the particular compiler and optimization level used to generate the code and require significant engineering effort to support each new ISA. We propose Forklift, the first neural lifter that learns how to translate assembly to LLVM IR using a token-level encoder-decoder Transformer. We show how to incrementally add support to new ISAs by fine tuning the assembly encoder and freezing the IR decoder, improving the overall accuracy and efficiency. We collect millions of parallel LLVM IR, x86, ARM, and RISC-V programs across compilers and optimization levels to train Forklift and set up an input/output-based accuracy harness. We evaluate Forklift on two challenging benchmark suites and translate 2.5x more x86 programs than a state-of-the-art hand-written lifter and 4.4x more x86 programs than GPT-4 as well as enabling translation from new ISAs.

Main paper: 
 introduction: 
 We are witnessing a rapid diversification of computer hardware to overcome the limits of technology scaling. This diversification has been accompanied by an increase in the number and variety of Instruction Set Architectures (ISAs) (Hennessy & Patterson, 2019) . However, for the successful adoption of any new hardware, pre-existing legacy applications must be ported to their new ISAs (Pegoraro, 2023) . Unfortunately, legacy software frequently exists only in binary form with no access to the original source code, preventing easy recompilation to new ISAs (Di Cosmo & Zacchiroli, 2017) .Binary translation solves this problem: taking binaries and translating them to new architectures (Rocha et al., 2022; D'Antras et al., 2017) . However, developing binary translation tools is a difficult task that requires substantial engineering effort for each new ISA. For each new ISA, the same challenges must repeatedly be overcome, reconstructing information typically destroyed during compilation such as function signatures and pointers, and undoing architecture-specific steps such as register allocation and vectorization (Cifuentes et al., 2002) . These tasks are non-trivial to overcome as compilers are not designed to be bidirectional -and must be redone for each new architecture. We leverage the LLVM's ability to compile to a wide range of target ISAs. As the target of Forklift is always LLVM IR, we freeze the decoder and fine-tune existing encoders to incrementally add support for new sources, maintaining accuracy on prior sources.Lifting is the standard approach to this problem, where a manually engineered tool lifts the source binary language into a shared compiler intermediate representation (IR) (Cifuentes et al., 2002) . In computational linguistics terms, compiler IR can be thought of as a sort of interlingua (Alansary, 2014) . The existing compiler infrastructure for this IR can then be used to re-optimize and lower the code to a new binary format. While this removes a significant barrier in binary translator design by reusing existing infrastructure, it still leaves the most challenging part of the problem unsolved. Critically, existing lifters require significant engineering efforts. They must overcome the information loss that compiling entails, and they are typically designed not just for a single ISA but also for a compiler and optimization level.In this paper, we tackle the heart of this engineering problem: how can we automatically learn lifting? We present Forklift, the first neural lifter, implemented as a token-level encoder-decoder Transformer. We pose lifting as a sequence-to-sequence task in which the model is directly fed with assembly instructions and is expected to generate the equivalent IR of the LLVM compiler. Unlike previous work in learnable binary translation (Lee et al., 2024) , which translates directly to the target assembly rather than lifting, we sidestep the need to learn to generate code for every translation direction. Once Forklift lifts code to LLVM IR, we can leverage the existing power of LLVM to re-optimize and recompile to the desired target, directly benefiting from the LLVM ecosystem.We collect a million-scale parallel dataset of LLVM IR, x86, ARM, and RISC-V for several compilers and optimization levels to train Forklift and set up an I/O-based accuracy harness.We evaluate Forklift1 on two challenging benchmark suites against a strong hand-written lifter, Lasagne (Rocha et al., 2022) , and a state-of-the-art Large Language Model (LLM), OpenAI's GPT-4 (OpenAI et al., 2024) . Forklift outperforms existing approaches without requiring manual engineering effort, automatically learning the intricacies of each ISA, compiler, and optimization level. On optimized x86 code, Forklift is 2.5x more accurate than Lasagne and 4.4x more accurate than GPT-4. Forklift is able to perform on new ISAs in a way traditional tools are not. Furthermore, as we lift all assembly targets to LLVM IR, we freeze the decoder and incrementally fine-tune the encoder for each new architecture. This incremental learning enables parameter sharing in the decoder and transfer learning in the encoder, yielding improved accuracy and efficiency. 
background: 
 LLVM IR The LLVM project (Lattner & Adve, 2004 ) is an industry-standard compiler infrastructure. It is designed around an intermediate representations language, LLVM IR, which is a generic static single-assignment (SSA) low-level language akin to assembly. Language developers need only translate their programs into LLVM IR to make use of the pre-existing code-generation backends. LLVM supports all ISAs and has a extensive set of optimizations available. LLVM first applies the desired optimization passes to the IR, and then lowers it to the assembly language of choice.Neural code translation Neural code translation (Chen et al., 2018; Roziere et al., 2020) is the task of learning a neural network model T that takes as input a unit of code (e.g., a function) in a given language A and outputs an equivalent program in the desired target language, B:T : A → B (1) Each instance of A, B is represented as a sequence of tokens. a = [a 1 , . . . a n ] ∈ A, B = [b 1 , . . . b m ] ∈ B.For the translation between some source a ∈ A and some target code b ∈ B to be correct, we require a and b to be semantically equivalent:EQUATIONwith M, M ′ being functions denoting the meaning of programs in A and B, respectively. While undecidable in general (Winskel, 1993) , in practice, there are looser bounds of equivalence such as observational equivalence on finite subsets of input/output pairs.Standard machine learning approaches train models on a given dataset and then remain frozen. However, the model's information can quickly become outdated, or need to be adapted to a new task. A solution is fine tuning the original model with new data. However, this leads to catastrophic forgetting (McCloskey & Cohen, 1989) , a phenomenon in which we see a drop in the model's performance on the original task or data it was originally trained on. Thus, one is required to either create a copy of the model for each new task, or fine tune with a mix of data including the original dataset. Both options are impractical. In incremental learning (van de Ven et al., 2022; Wang et al., 2024) settings, the machine learning system is explicitly designed to incrementally support new tasks, classification tasks, or domains as the system requirements are updated. For example, adding support for new languages to a multilingual machine translation system (Escolano et al., 2019) . 
extensible neural lifting: 
 Our goal is to port legacy assembly to new ISAs in a scalable manner. We assume that we have access to a C compiler for all the source ISAs of interest and to an LLVM-based compiler (Clang) for the target ISA, which is the case in practice. We take functions as the basic unit of translation, following previous work on code translation (Lachaux et al., 2020) .We present our method, Forklift, in four key steps. First, we describe how to generate machine learning-scale data to train our model (Section 3.1). Second, we discuss the critical design choice of which specific IR to lift to (Section 3.2). Third, we describe the architecture of Forklift (Section 3.3). Finally, we propose a method for continually adding new ISAs to Forklift (Section 3.4).scratch, without any pretraining. We do not fine tune from an existing LLM due to the additional computational cost not being justified given the poor performance of code LLMs on low-level code observed in Lee et al. (2024) . If an LLM pretrained on LLVM IR was available,2 one could opt for starting the training from the LLM as the decoder, and a randomly initialized encoder attached to the decoder via randomly initialized crossattention modules added to the decoder. Our method is orthogonal to LLM improvements.Tokenization For the vocabulary, we train a Unigram tokenizer (Kudo, 2018) of 16k tokens. We split individual digits and apply domain-specific normalization (such as space and endof-line normalization, unnecessary assembly boilerplate removal). 3 We note that, unlike assembly languages, LLVM IR has a native struct type for user-defined types, like C. This means that the model will learn to generate structs from code that does not have structs, which can lead to complications for the model. In Armengol-Estape et al. ( 2024), a similar problem was solved with type inference. However, since lifting, unlike decompilation, does not require realistic type names, we instead opt for simplifying the task to the model by normalizing struct names.Verifier We need a method to verify that a given low-level translation is correct. We opt for observational equivalence, i.e., unit tests. While unit tests don't formally guarantee semantic equivalence, in practice passing unit tests with good coverage strongly correlates with correctness. Due to the imperative, low-level nature of the code we tackle, we implement a code evaluator that aside from return values, also checks for side effects on arrays, struct pointers, and global variables. We do not check for side effects involving system calls. We assume that the desired functions have reference unit tests, which is an increasingly realistic assumption given the proliferation of automatic unit test generation methods (Kind et al., 2022; Siddiq et al., 2024) .We tackle incrementally multi-source neural lifting, that is, we need to incrementally support multiple assembly languages. In this work, we start training an x86 lifter, as x86 is a mainstream ISA. We, then, freeze the decoder, copy the x86 encoder and fine-tune it for ARM. Afterwards, for a new architecture, e.g., RISC-V, we proceed similarly starting from the previous ARM encoder, motivated by the similarities between ARM and RISC-V. 
experimental framework: 
 To evaluate the effectiveness of our approach, we train neural lifters both from scratch and with the extensibility approach outlined in Section 3.4. We evaluate the models against a state-of-the-art LLM, ChatGPT4 (OpenAI et al., 2024) , and a strong handwritten baseline, the lifter used in Lasagne (Rocha et al., 2022) using input/output accuracy.Baselines As our first baseline, we use the lifter in Lasagne (Rocha et al., 2022) , which is a state-of-the-art hand-written binary translator built by extending the LLVM-Mctoll lifter (Yadavalli & Smith, 2019) . Since this lifter is coupled with a disassembler (similar to Unix's objdump), we provide it with an object file. As an LLM baseline, we use the most recent version4 of GPT-4 (OpenAI et al., 2024) . We provide GPT-4 with the textual assembly of the function, and experiment with different prompts.We provide each translation system with the source assembly function. We then take the output LLVM IR, compile it back, and call the function from a C interface with the original context of the function. We then check for input/output accuracy using the unit tests from the corresponding evaluation benchmarks, following the verifier implementation described in Section 3. For our models, we sample with beam search and evaluate the top 5 hypotheses.Benchmarks We evaluate our approach on two benchmarks suites: the program synthesis benchmark in Collie et al. (2020) , Synth, with a curated set of features in C (e.g., numeric arrays and strings) and a subset of 512 functions in ExeBench (Armengol-Estapé et al., 2022) ,5 scrapped from public repositories, to allow wider-scale evaluation and interaction with user-defined types and external function calls. Synth has the interesting characteristic of being rich in automatically vectorizable functions, i.e., loops that the compiler automatically vectorizes when using e.g. the O3 optimization code. While faster, this further complicates recovering the original LLVM IR. For a realistic, yet challenging evaluation, for all ISAs, we evaluate on assembly generated with the O3 optimization level, considerably more complex than unoptimized, O0. To avoid train-evaluation overlaps, the benchmarks in Synth were already filtered out from the train set in Armengol-Estapé et al. ( 2022) in the original dataset; the same work performed exact C token-level decontamination to minimize train-test overlaps. In this work, we apply additional deduplications using assembly tokens rather than C tokens (unlike Armengol-Estapé et al. ( 2022)) to search for duplicates, given the fact that different C functions could be lowered to identical assembly.We implement our models in PyTorch (Paszke et al., 2017) using Huggingface Transformers (Wolf et al., 2020) . We build an encoder-decoder Transformer (Vaswani et al., 2017a) with the architectural modifications in Lewis et al. (2019) , for a total of 153M trainable parameters. We use a context window of 2048 tokens for both source and target sequences. For further details please see Appendix A. 
results, discussion, and analysis: 
 Table 1 shows the overall performance of the lifters across source ISAs and benchmark suite when translating between optimized assembly (O3), generated by the Clang compiler, into LLVM IR. Forklift consistently performs well across the ISAs with a stable accuracy on Exebench of 71 to 75%. Lasagne has at best half this accuracy, achieving this only on x86. The Lasagne ARM port is considerably weaker, demonstrating the difficulty of manual lifters. GPT-4 is not competitive in this task, highlighting the intrinsic difficulty of lifting and hinting at a scarcity of low-level code in mainstream LLMs pretraining data. However, it obtains non-trivial performance on Exebench, ranging between 16% and 22%.The Synth dataset is especially challenging to lift from optimized assembly, as a considerable amount of the loops are vectorized. Vectorized assembly is typically longer and difficult to get right (custom vector instructions, padding, etc). GPT-4 especially struggles in this benchmark. Instead, Forklift achieves accuracies between 51% and 67.42%. The performance is the lowest on x86, as x86's vectorizations typically require more instructions than their ARM counterparts.In the remainder of this section, we analyze the impact of the a) learned LLVM IR target, b) incremental learning, c) the original compiler, and d) prompting strategies for GPT-4. Finally, we perform error analysis and discuss the limitations of our approach. Appendix D provides additional results. Table 4 shows the performance of Forklift (with the extensibility methodology described in Section 3.4 and decoder sharing) across ISAs. As a baseline we compare to models trained from scratch. The incremental approach has the advantage of a smaller parameter count due to the shared decoder. However, we observe additional advantages. Firstly, there is a a faster convergence (see appendix for details), which would help in scenarios with restricted data or compute. Secondly, accuracy slightly improves on x86 ARM and significantly improves on RISC-V, which we attribute to the regularization effect of the fixed decoder and the transfer learning of the encoder. Table 5 shows a comparison between a full fine-tuning approach vs the frozen decoder approach (Forklift). There is no clear winner in terms of accuracy, with one model being slightly better on Synth and the other being slightly better on ExeBench. We prefer the frozen decoder one due to the decoder parameter sharing, leading to lesser overall parameter count.MODEL EXE SYNTH Neural full-FT 72.37% 69.90% Forklift 75.31% 67.96%Table 5 : Full fine-tuning vs frozen decoder on ARM.Hand-written lifters can be sensitive to the original compiler that generated the assembly.Lasagne was originally evaluated with Clang and its performance significantly drops when using GCC-generated code (see Appendix, Table 11 ). Following a similar approach for extending Forklift to ARM and RISC-V with Clang, we fine tune the original x86 encoder with GCC-generated assembly, and outperform Lasagne ( Table 7 shows the performance of GPT-4 with different prompting strategies. First, we simply ask GPT-4 to translate the assembly function into the corresponding LLVM IR. We observe that GPT-4 especially struggles when literally translating architectural intrinsics.Thus, we explicitly ask the model not to use intrinsics and come up with the original LLVM IR code. We also experiment with one-shot learning, which slightly degrades performance. Including prior experiments implies feeding costly long sequences to the model. We use the best-performing prompt, Prompted no intrinsics strategy, for the rest of the experiments.Exe Synth Simple prompt 12.87% 0.95% Prompted no intrinsics 17.07% 0.95% Prompted no intrinsics + One-shot 12.28% 0.95% Table 7 : GPT-4 performance on Synth lifting from x86, breakdown.Table 8 shows the correlations between different features (e.g., compilability of the predicted translation) and the input/output accuracy of each system on x86. We refer to Appendix F for similar tables on other architectures.We observe that the main feature driving Lasagne failure is vectorization (vectorized) on Synth, and global variables (has_globals) on ExeBench. The correlation with compilability (compiles) of generated code is strong on Synth but weaker on ExeBench. This suggests that on Synth, when Lasagne's LLVM IR compiles, it is likely to be correct. However, on ExeBench, we encounter runtime crashes in many cases, leading to a lack of input/output accuracy even when it compiles. In Appendix E, we provide additional results and analysis for Lasagne.Forklift's input/output accuracy generally correlates with compilability, which is an interesting feature because it minimizes the unreliability of having compilable yet subtly incorrect translations. We note the following limitations of our system. Firstly, we tackle functions with a maximum length of 2048 tokens as opposed to full programs with unbounded lengths. Secondly, Forklift is fed with textual assembly, for which we assume the presence of a correct disassembler, which is a typical assumption in the literature (Hosseini & Dolan-Gavitt, 2022) . Thirdly, Forklift does not formally guarantee the semantic equivalence of its translations. Fourth, for the incremental learning strategy we start from the intuition that the encoder is essentially in charge of understanding the source assembly, while the decoder is mainly concerned with IR generation; however, since the system is trained end-to-end, both roles might be more intertwined. Finally, this work was performed under a limited compute budget, and we were not able to pretrain an LLVM IR LLM to work as the decoder. 
related work: 
 Binary translators and lifters A large number of binary translators exist for a wide range of tasks, from optimizing code (Bruening, 2004; Bansal & Aiken, 2008) to instrumenting code (Nethercote & Seward, 2007; Luk et al., 2005) . Common approaches are to do this statically (Engelke & Schulz, 2020; Reidel et al., 2021) , where binaries are translated ahead of time, and dynamically (Bellard, 2005; Altman & Ebcioglu, 2000) , where binaries are translated on the fly. However, these approaches are challenging to port to new architectures (Hazelwood & Klauser, 2006; Chen et al., 2013; Bansal & Aiken, 2008) . LLVM IR has been used as a target-independent language for many lifters (Shen et al., 2012) . Lasagne (Rocha et al., 2022) introduces a state-of-the-art x86 → LLVM IR lifter by extending the industry-grade LLVM-McToll lifter, and leverages this lifter to build an effective static binary translator x86 → ARM.Neural approaches Transformer-based (Vaswani et al., 2017b) approaches are state-of-theart in code translation (Lachaux et al., 2020), and LLMs (Brown et al., 2020) have further improved (Chen et al., 2021a) . However, even code-specific LLMs still struggle with lowlevel languages (Lee et al., 2024) , as developers don't typically upload assembly to the Internet. Rather, low-level representations of code are implicitly present on codebases. Domain-specific Transformers have been trained in decompilation settings (Chen et al., 2021b; Armengol-Estape et al., 2024; Tan et al., 2024) . Unlike decompilation, lifting is more concerned with obtaining accurate and fast portable code rather than readability in a user-level language.More recently, Cummins et al. (2023) trained an LLM to predict LLVM IR for code size optimization. However, the model cannot handle assembly language and is not publicly available. Guess&Sketch (Lee et al., 2024) tackled RISC-V ↔ ARM with an encoder-decoder Transformer augmented with a symbolic engine to fix partially correct translations. However, they evaluate on unoptimized assembly and are limited by the quadratic complexity of all translation directions. Our work is orthogonal to theirs and Forklift could benefit from the symbolic augmentation, which in our case would involve less engineering work to implement due to only having to support one target language (LLVM IR). Starcoder2 (Lozhkov et al., 2024) 2024)). Escolano et al. (2020) propose jointly training a multilingual translation system with a per-language encoder and decoder, resulting in a system with shared latent space but no sharing of parameters, inspired by interlingual machine translation (Alansary, 2014) . Then, they can incrementally add languages by freezing an existing encoder-decoder pair and training the new ones. Unlike natural languages, assembly languages do have an explicit, complete interlingua available, LLVM's intermediate representations. Thus, we can have a single frozen decoder and incrementally add new encoders which in our case we, unlike Escolano et al. (2020) , fine tune from existing encoders rather than from scratch. Interestingly, Szafraniec et al. (2023) also exploit the interlingual nature of LLVM IR, but as a pivot language for improving the training of code translation models between source languages. 
conclusions: 
 This paper introduces Forklift, the first neural lifter. It effectively translates from optimized assembly into generic compiler intermediate representations. This enables porting legacy applications between ISAs, and reoptimizing them to the new architecture, exploiting existing compiler infrastructure. Forklift outperforms Lasagne, a state-of-the-art handwritten lifter, and a GPT-4, a strong general-purpose LLM, and it is capable of efficiently supporting new ISAs. As future work, we suggest replacing Forklift's decoder by an LLM pretrained on LLVM IR, and integrating symbolic approaches. 
 
 Appendix: We use a learning rate of 1 × 10 -4 , with an inverse square root scheduler and 10k warmup updates. We train each model with a global batch size of 16 function pairs for a total of 900k updates on 4 NVIDIA A100 for a total of 72 hours, using a weight decay of 5 × 10 -3 as regularization. For the adaptations, we use a learning rate of 5 × 10 -5 and 5k warmup updates, freezing all decoder parameters.8 Regarding the training data, we augmented the compilable C dataset in Armengol-Estapé et al. ( 2022) with the required assembly and LLVM IR targets. Aside from the token-based C deduplication performed in the original dataset, we additionally perform an assemblybased deduplication, which leads to finding further duplicates (different C code can lead to the same assembly), and use a similar strategy to prevent data leakage to the evaluation sets. We also filter for length, but only for the training set. For a realistic evaluation, we do not filter for length on evaluation sets for any of the systems. After filtering, we are left with about 2.7-3.3M parallel functions depending on the translation pair. We use the validation set to monitor training and select the best checkpoint.As for the tokenizer, we train a Unigram tokenizer with vocabulary of 16k tokens. using the tokenizers library.9 For incrementally adding new languages to the vocabulary, we would train new tokenizers and merge them back into the shared vocabulary, training only the embeddings of the new tokens (the ones without overlap with previous vocabulary). To simplify the implementation, we do a one-off shared vocabulary for LLVM IR, x86, ARM, and RISCV).There are several variants of ARM. For evaluation, we use the target triple aarch64-linux-gnu. However, Lasagne does not have 64 bit support for ARM. Thus, for a fair evaluation, for Lasagne we use the target used in their tests, arm-linux-gnueabi.Before evaluating the translation systems, we check that the original function compiles in our host machine, and discard those which don't for all systems. Depending on the ISA and benchmark, the number of discarded functions ranges between 3% and 23%.These are the compiler (Clang, GCC) optimization levels used in this work:• O0: Unoptimized code.• O3: Aggressive execution in terms of execution time.• Oz: Aggressive optimization in terms of code size.The length of IR target varies across formats and benchmark suite. O0 is expected to be more verbose as it is deliberately unoptimized to aid programmer debugging. O3 targets performance and optimizes unnecessary computation away and is hence normally smaller in size. However, for Synth it is considerably larger due to the presence of extensive vectorization which requires much setup code. Oz aims at code size reduction and hence is the smallest of the IRs.Figures 2 (ExeBench) and 3 (Synth) show the faster convergence of the ARM lifter when fine-tuning from x86 as opposed to starting from scratch. Table 9 shows the % of compilable translations generated by each system from O3 assembly. Given the relatively poor performance of Lasagne, it is worth investigating. Table 11 shows the performance of Lasagne across the experimental parameters. Lasagne performs well in restricted settings, but struggles when moved out of its "comfort zone". On numerical benchmarks where the x86 binary has been generated by Clang with no optimizations, it is able to perform extremely well, outperforming all techniques.However, its performance drops by two-thirds when changing benchmark suite with more complex data types or compiler optimization level which introduce vector instructions.The immaturity of the ARM lifter is emphasised across each category. Although it performs best on Clang O0 Synth, the performance is less than half that achieved on x86. Changing compilers again has an overall negative effect, surprisingly though, using GCC with O0 on Exebench is better than using Clang. In this section, we include additional input/output accuracy correlation tables. We have excluded the systems for which the accuracies were close to 0 on the corresponding dataset. This section provides detailed examples to illustrate where existing lifters fail to accurately lift code and features that Forklift struggles to lift. Existing lifters struggle to lift features they were not designed for. For example Lasagne Rocha et al. (2022) fails to lift code that is vectorized, which frequently happens on higher optimization levels. Similarly, we show examples where Forklift is able to remove architecture-specific features such as vectorization when it lifts the code, allowing LLVM to re-introduce vectorization for the new targets. Finally, we show an examples where Forklift produces incorrect code, and highlight the future work that should be done to improve this.This benchmark (Listing 1) increments each element of an integer array by one. When compiled with clang on O3 (Listing 2) and Oz (Listing 3), it is vectorized, as seen by the use of the psubd instructions in the .LBB0_6 block.Forklift lifts this correctly (Listing 4), recreating code in a similar style to Oz (Listing 3). GPT-4 fails to recreate the correct code (Listing 6), producing syntactically correct LLVM IR that does not perform the correct function. Rule-based Lasagne lifter does not support all the vector instructions in the assembly code (Listing 8).Interestingly, we also provide the O3 recompilations to x86 (Listing 5) and ARM (Listing 6) of the LLVM IR Oz predicted by Forklift. Critically, both are vectorized, showcasing that we can recover generic code from an optimized assembly and use LLVM to recompile it with new optimizations.Listing 1: Original C void a r r a y _ i n c ( i n t * a r r , i nt n ) { f o r ( i n t i = 0 ; i < n ; ++ i ) { a r r [ i ] += 1 ; } }Listing 2: Clang x86 O3. g l o b l a r r a y _ i n c # --Begin f u n c t i o n a r r a y _ i n c . p 2 a l i g n 4 , 0 x90 . type a r r a y _ i n c , @function a r r a y _ i n c : # @array_inc . c f i _ s t a r t p r o c # %bb . 0 : t e s t l %e s i , %e s i j l e . LBB0_11 # %bb . 1 : movl %e s i , %eax cmpl $7 , %e s i j a. LBB0_3 # %bb . 2 :x o r l %ecx , %ecx jmp . LBB0_10 . LBB0_3 : movl %eax , %ecx andl $ -8 , %ecx l e a q -8(% r c x ) , %r s i movq %r s i , %rdx shrq $3 , %rdx addq $1 , %rdx movl %edx , %r8d andl $1 , %r8d t e s t q %r s i , %r s i j e. LBB0_4 # %bb . 5 : movq %r8 , %r s i subq %rdx , %r s i x o r l %edx , %edx pcmpeqd %xmm0, %xmm0 . p 2 a l i g n 4 , 0 x90 . LBB0_6 : # =>This I n n e r Loop Header : Depth=1 movdqu (% rd i ,%rdx , 4 ) , %xmm1 movdqu 16(% rd i ,%rdx , 4 ) , %xmm2 movdqu 32(% rd i ,%rdx , 4 ) , %xmm3 movdqu 48(% rd i ,%rdx , 4 ) , %xmm4 psubd %xmm0, %xmm1 psubd %xmm0, %xmm2 movdqu %xmm1, (% rd i ,%rdx , 4 ) movdqu %xmm2, 16(% rd i ,%rdx , 4 ) psubd %xmm0, %xmm3 psubd %xmm0, %xmm4 movdqu %xmm3, 32(% rd i ,%rdx , 4 ) movdqu %xmm4, 48(% rd i ,%rdx , 4 ) addq $16 , %rdx addq $2 , %r s i j n e . LBB0_6 # %bb . 7 : t e s t q %r8 , %r 8 j e . LBB0_9 . LBB0_8 : movdqu (% rd i ,%rdx , 4 ) , %xmm0 movdqu 16(% rd i ,%rdx , 4 ) , %xmm1 pcmpeqd %xmm2, %xmm2 psubd %xmm2, %xmm0 psubd %xmm2, %xmm1 movdqu %xmm0, (% rd i ,%rdx , 4 ) movdqu %xmm1, 16(% rd i ,%rdx , 4 ) . LBB0_9 : cmpq %rax , %r c x j e . LBB0_11 . p 2 a l i g n 4 , 0 x90 . LBB0_10 :# =>This I n n e r Loop Header : Depth=1 addl $1 , (% r d i ,% rcx , 4 ) addq $1 , %r c x cmpq %rcx , %rax j n e . LBB0_10 . LBB0_11 : r e t q . LBB0_4 :x o r l %edx , %edx t e s t q %r8 , %r 8 j n e . LBB0_8 jmp . LBB0_9 . Lfunc_end0 :. s i z e a r r a y _ i n c , . Lfunc_end0 -a r r a y _ i n c . ; preds = %4 r e t void 8 :; preds = %4 %9 = g e t e l e m e n t p t r inbounds i 3 2 , i 3 2 * %0, i 6 4 %5 %10 = load i 3 2 , i 3 2 * %9, a l i g n 4 , ! t b a a ! 2 %11 = add nsw i 3 2 %10 , 1 s t o r e i 3 2 %11 , i 3 2 * %9, a l i g n 4 , ! t b a a ! 2 %12 = add nuw nsw i 6 4 %5, 1 br l a b e l %4 } Listing 4: LLVM IR predicted by Forklift (IO correct) %s t r u c t . s t r u c t 0 = type { i 3 2 } d e f i n e d s o _ l o c a l void @array_inc (% s t r u c t . s t r u c t 0 * nocapture %0, i 3 2 %1) local_unnamed_addr { %3 = s e x t i 3 2 %1 t o i 6 4 br l a b e l %4 4 : ; preds = %8, %2 %5 = phi i 6 4 [ %12 , %8 ] , [ 0 , %2 ] %6 = icmp s l t i 6 4 %5, %3 br i 1 %6, l a b e l %8, l a b e l %7 7 : ; preds = %4 r e t void 8 : ; preds = %4 %9 = g e t e l e m e n t p t r inbounds %s t r u c t . s t r u c t 0 , %s t r u c t . s t r u c t 0 * %0, i 6 4 %5, i 3 2 0 %10 = load i 3 2 , i 3 2 * %9, a l i g n 4 %11 = add nsw i 3 2 %10 , 1 s t o r e i 3 2 %11 , i 3 2 * %9, a l i g n 4 %12 = add nuw nsw i 6 4 %5, 1 br l a b e l %4 } Listing 5: Vectorized x86 recompilation of the previous LLVM IR Oz . g l o b l a r r a y _ i n c # --Begin f u n c t i o n a r r a y _ i n c . p 2 a l i g n 4 , 0 x90 . type a r r a y _ i n c , @function a r r a y _ i n c : # @array_inc # %bb . # %. _ c r i t _ e d g e r e t q . LBB0_4 :x o r l %edx , %edx t e s t q %r8 , %r 8 j n e . LBB0_8 jmp . LBB0_9 . Lfunc_end0 :. s i z e a r r a y _ i n c , . Lfunc_end0 -a r r a y _ i n cListing 6: Vectorized ARM recompilation of the previous LLVM IR Oz. g l o b l a r r a y _ i n c // --Begin f u n c t i o n a r r a y _ i n c . p 2 a l i g n 2 . type a r r a y _ i n c , @function a r r a y _ i n c : // @array_inc // %bb . 0 : // k i l l : def $w1 k i l l e d $w1 . s i z e a r r a y _ i n , . Lfunc_end0 -a r r a y _ i n cListing 7: LLVM IR predicted by GPT-4 in the x86 case (compiles but not correct) @LC0 = i n t e r n a l c o n s t a n t <4 x i 3 2 > < i 3 2 1 , i 3 2 1 , i 3 2 1 , i 3 2 1> d e c l a r e void @llvm . memcpy . p 0 i 8 . p 0 i 8 . i 6 4 ( i 8 * nocapture writeonly , i 8 * nocapture readonly , i 6 4 , i 1 immarg ) d e f i n e void @array_inc ( i 3 2 * %0, i 3 2 %1) { e n t r y : %2 = icmp s l e i 3 2 %1, 0 br i 1 %2, l a b e l %L1 , l a b e l %3 3 : ; preds = %e n t r y %4 = add i 3 2 %1, -1 %5 = icmp u l e i 3 2 %4, 2 br i 1 %5, l a b e l %L6 , l a b e l %6 6 :; preds = %3 %7 = and i 3 2 %1, -4 %8 = icmp eq i 3 2 %7, 0 br i 1 %8, l a b e l %L9 , l a b e l %9 9 :; preds = %6 %10 = z e x t i 3 2 %7 t o i 6 4 %11 = g e t e l e m e n t p t r i 3 2 , i 3 2 * %0, i 6 4 %10 %12 = add i 3 2 %7, 1 %13 = icmp s l e i 3 2 %12 , %1 br i 1 %13 , l a b e l %14 , l a b e l %L1 1 4 :; preds = %9 %15 = g e t e l e m e n t p t r i 3 2 , i 3 2 * %0, i 3 2 %12 s t o r e i 3 2 1 , i 3 2 * %15 , a l i g n 4 %16 = add i 3 2 %7, 2 %17 = icmp s l e i 3 2 %16 , %1 br i 1 %17 , l a b e l %18 , l a b e l %L1 1 8 :; preds = %14 %19 = g e t e l e m e n t p t r i 3 2 , i 3 2 * %0, i 3 2 %16 s t o r e i 3 2 1 , i 3 2 * %19 , a l i g n 4 %20 = add i 3 2 %7, 3 %21 = icmp s l e i 3 2 %20 , %1 br i 1 %21 , l a b e l %22 , l a b e l %L1 2 2 :; preds = %18 %23 = g e t e l e m e n t p t r i 3 2 , i 3 2 * %0, i 3 2 %20 s t o r e i 3 2 1 , i 3 2 * %23 , a l i g n 4 br l a b e l %L1 L6 :; preds = %3 br l a b e l %9 L9 :; preds = %6 br l a b e l %L1 L1 :; preds = %22 , %18 , %14 , %9, %entry , %L9 In this benchmark (Listing 9), the string a is searched for characters that exist in the string s.In this case, we can see that the compiled code is not vectorized, it relies only on simple x86 instructions (Listing 10). As a result, Lasagne is able to work. However, the generated code is verbose: much longer than the original code (Listing 15). This unnatural code means that during future lowering passes, LLVM has a much more challenging task to generate performant code. We can see that GPT-4 fails to create a compilable sequence of LLVM IR (Listing 16), calling a strlen function that is not defined.Finally, we can see that Forklift is able to generate correct lifted code (Listing 12) with one key difference from the original (Listing 11): the injection of a struct type around the string. Forklift tends to proactively inject these types due to the GitHub code it was trained on, which is very struct-heavy. x o r l %eax , %eax # k i l l : def $eax k i l l e d $eax k i l l e d $rax r e t q . LBB0_5 :x o r l %eax , %eax . p 2 a l i g n 4 , 0 x90 . LBB0_6 :# =>This I n n e r Loop Header : Depth=1 cmpb $0 , 1(% rd i ,% rax ) l e a q 1(% rax ) , %rax j n e . LBB0_6 . LBB0_10 :# k i l l : def $eax k i l l e d $eax k i l l e d $rax r e t q . Lfunc_end0 :. ; preds = %e n t r y br l a b e l %r e t u r n r e t u r n :; preds = %r e t u r n _ i , %r e t u r n _ z e r o %r e t _ v a l . 0 = phi i 3 2 [ %i . 0 , %r e t u r n _ i ] , [ 0 , %r e t u r n _ z e r o ] r e t i 3 2 %r e t _ v a l . 0 }In this benchmark, the function: (arr[i] -arr2[i]) * arr2[i] is computed for cases where (arr[i] -arr2[i]) is even (Listing 15). This code is not vectorized by LLVM on O3 (Listing 16) due to the branch that guards the access to the out array . As a result, Lasagne is able to generate correct results for this benchmark -all the instructions are within its realm of capability (Listing 19). However, in this case, Forklift generates incorrect code (Listing 18). The type signatures are equivalent, but the behavior of the function is incorrect. Again, we can see that Forklift produces code that relies on simple structs.GPT-4 produces code that does not compile: it is syntactically invalid: it declares the function twice, and then produces an error when compiling one of the instructions (Listing 20).Listing 15: Original C void m u l t i p l y _ e e n s ( i n t * a r r , i n t * a r r 2 , i n t n , i n t * out ) { i n t f i l t e r e d = 0 ; f o r ( i n t i = 0 ; i < n ; ++ i ) { i n t x = a r r multiply_evens , @function m u l t i p l y _ e v e n s : # @multiply_evens . c f i _ s t a r t p r o c # %bb . 0 : t e s t l %edx , %edx j l e . LBB0_6 # %bb . 1 : movl %edx , %r9d movl %r9d , %r8d andl $1 , %r8d cmpl $1 , %edx j n e . LBB0_7 # %bb . 2 :x o r l %edx , %edx . LBB0_3 : t e s t q %r8 , %r 8 j e . LBB0_6 # %bb . 4 :Code will be made available at https://github.com/jordiae/forklift.After the submission of this article, an LLM pretrained on LLVM IR was released(Cummins et al., 2024). In Section 6, we discuss their results and how they compare to Forklift's.Unigram was shown to outperform BPE inBostrom & Durrett (2020), but it is out of scope of this work to perform an ablation study on tokenization strategies.Most recent version of ChatGPT4 as of March 2024.The first 512 functions in the test set, to minimize the overhead incurred in the executing the functions and running the different systems.See examples in the Appendix G. Appendix B explains the optimization levels.As shown inTable 9 in the Appendix D.Together with the encoder embedding layer, tied with the decoder embeddings.https://github.com/huggingface/tokenizers 


Decision: This paper presents Forklift for translating assembly to LLVM IR. They discussed their approach for data generation, model architecture, and other design choices. The incremental learning method is interesting: when adding new assembly languages, they can freeze the decoder and finetune for new languages. The neural architecture is an encoder-decoder Transformer based on BART. They demonstrate strong empirical results, where their model outperforms Lasagne and GPT-4.

The data and method from this work can be great contributions to the field of LM for software engineering, and thus I recommend acceptance. I recommend the authors to revise their work according to suggestions from reviewers. In particular, I think it is more convincing to add finetuning experiments with more recent coding language models, and it is helpful to show the empirical results on how the base model and pretraining affect the performance.

Reviews: review: paper_summary: paper_summary: This paper proposes a neural lifter to translate the source binary language into a shared compiler intermediate representation. The approach is to generate LLVM IR and source binaries from a large set of C functions, and reverse the translation from binaries to the LLVM IR.
strength_weakness: strength_weakness: 1. The details on 3.1 Data Generation, however are quite lacking. Can you quantify the amount of the publicly available repositories crawled and describe the type of sources? Were there any challenges in applying the method of Armengol-Estape et al., 2022? 

2. I am not fully convinced by "We do not fine tune from an existing LLM due to the
additional computational cost not being justified given the poor performance of code
LLMs on low-level code observed" - I think an experiment is required is to confirm that fine tune from an existing LLM (even if poor) is worse than train from scratch.

3. The results in Table 1 look v good - was there any check for train-test overlap since you crawled from public repos?
questions: questions: Please see and respond to reasons to reject as well as 

3. Why do you think the model is experiencing negative correlation on length of original C code (c_length), and number of arguments of the function?

4. "We assume that the desired functions have reference unit tests" - I don't see any particular method here. This seems like standard approach to function execution accuracy? Also, where do you construct the unit tests? Later you write that "We then take the output LLVM IR, compile it back, and call the function from a C interface with the original context of the function. We then check for input/output accuracy" (presumably against unit tests).
paper_summary: paper_summary: The paper proposes Forklift, a neural lifter using a Transformer model to translate assembly code of different ISAs to the architecture-independent LLVM IR. Forklift achieves better accuracy and efficiency than both a state-of-the-art hand-written lifter and GPT-4 when translating x86 programs and enables translation from additional ISAs.
strength_weakness: strength_weakness: - The main novelty in this paper is the application along with its setup (training and evaluation data, etc.) while there is little to no innovation over standard LM training.
questions: questions: - How do you ensure that there is no leakage between the training data and the evaluation data?
- It’s great that Forklift performs significantly better than Lasagne out-of-the-box. Do you have a sense of whether the failures of Lasagne that you identified in this could be fixed? Do you know what it would take and how much better the performance would be?
paper_summary: paper_summary: The paper introduces Forklift, which converts assembly into an intermediate representation for generic compiler optimization across different hardware platforms. Forklift outperforms Lasagne and GPT-4, gradually adding support for new ISAs by fine-tuning the assembly encoder and freezing the IR decoder to improve overall accuracy and efficiency. Overall, it leans towards an application-oriented approach.
strength_weakness: strength_weakness: 1. There are certain limitations in the methodological contribution. Could some structured learning modules be introduced based on the representation of the intermediate language? Will the increase in data volume continue to improve effectiveness, i.e., is there a scaling law in the size of intermediate representation data?
2. Experiments were not conducted on popular code LLMs. For instance, StarCoder2 was pre-trained on LLVM. Would this be beneficial for the task?
paper_summary: paper_summary: This paper presents Forklift, a model designed to translate machine architecture-dependent assembly code into an intermediate representation that is architecture-independent, facilitating the migration of (legacy) programs to other machine architectures. Forklift is based on an encoder-decoder Transformer architecture and is trained using a parallel dataset created by the authors. The authors also incorporate the idea of incremental learning, initially training the model with x86 architecture and then fine-tuning it with another architecture. Experimental results demonstrate that Forklift outperforms other baselines, including a state-of-the-art hand-written model and GPT4, particularly in terms of passing unit tests. Furthermore, the authors present results from additional experiments to address interesting questions, such as the impact of incremental learning and error analysis.
strength_weakness: strength_weakness: - Lack of detailed description of the parallel datasets and evaluation datasets, particularly unit tests. The number of data items and the difficulty level of unit tests are not specified, and it's unclear whether the authors have made the datasets open for reproducibility.

- Some questions I have for the authors:
questions: questions: - The incremental learning idea is intriguing. Would training the model at the optimization level be feasible? For instance, the paper suggests the order: x86 => ARM => RISC-V. How about this alternative order: x86 O0 => x86 O3 => ARM O0 => ARM O3? Since the optimization level varies even with the same architecture, I'm curious about the potential results.

- In my experience, tokenization poses a significant challenge in improving the performance of understanding assembly code. How does the model's performance differ when using Byte Pair Encoding (BPE) compared to a unigram tokenizer?

- What are the features listed in Table 8? Could you provide more information about "edit_sim" and "has_float"?

Comments: comment: Thank you for addressing my questions. I will improve my score as the authors have clarified my concerns. I hope they will incorporate the comments from the other reviewers.

Yours,
Thank you for the response! I think this helps clarify some of my questions.