preface

Today, we will have a simple understanding and analysis of the compiler architecture system LLVM. After understanding the compilation process of LLVM, we will simply implement a Clang plug-in for fun. So let’s get started.

Before you dive into compilers, understand the difference between interpreted and compiled languages.

  • Interpreted languages: programs do not need to be compiled; they are translated into machine language at runtime, every time they are executed. Low efficiency, interpreter dependence, good cross-platform.

  • Compiled languages: programs need a special compilation process before they can be executed. The program is compiled into a machine-language file, which can be used directly without retranslation at runtime. Program execution efficiency, compiler – dependent, less cross-platform.

So is there a way to make your application more efficient while still being cross-platform?

Heh heh, of course. LLVM, which we’ll explore today, offers a solution.

A:LLVM

1.1 LLVMAn overview of the

LLVM is a framework system of architecture compilers, written in C++, used to optimize compile-time, link-time, run-time, and idle-time of programs written in any programming language. Keep it open to developers and compatible with existing scripts.

The LLVM program was initiated in 2000 by Dr. Chris Lattner of UIUC University in the United States. Chris Lattner joined Apple Inc. in 2006. And committed to the application of LLVM in Apple development system. Apple is also a major funder of the LLVM program.

Currently LLVM has been adopted by Apple iOS development tools, Xilinx Vivado, Facebook, Google and other major companies.

1.2: Traditional compiler design

1.2.1: Compiler front end (Frontend)

The task of the compiler front end is to parse the source code. It will perform: lexical analysis, Syntax analysis, semantic analysis, check the source code for errors, then build an Abstract Syntax Tree (AST), LLVM’s front end will also generate intermediate representation (IR) code.

1.2.2: Optimizer (Optimizer)

The optimizer is responsible for various optimizations. Reduce package size (strip symbols), improve code runtime (eliminate redundant calculations, reduce pointer jumps, etc.).

1.2.3: the back-end (Backend)/Code generator (CodeGenerator)

The back end maps code to the target instruction set. Generate machine language and perform machine-specific code optimizations.

Because traditional compilers (such as GCC) are designed as monolithic applications and do not support multiple languages or multiple hardware architectures, their usefulness is limited.

1.3: LLVMThe design of the

The most important part of LLVM comes when the compiler decides to support multiple source languages or multiple hardware architectures.

The most important aspect of LLVM design is the use of common code representation (IR), which is the form used to represent code in the compiler. LLVM can write a separate front end for any programming language and a separate back end for any hardware architecture. When you need to support a new language, you just need to write a separate front end that can generate IR. When you need to support a new hardware architecture, you just need to write a separate back end that can receive IR.

1.3.1: iOSCompiler architecture

Objective-c /C/C++ uses a compiler with Clang front end, Swift Swift and LLVM back end.

2:Clang

Clang is a subproject of the LLVM project. It is a lightweight compiler based on the LLVM architecture that was created as an alternative to GCC to provide faster compilation times. It is the compiler responsible for compiling objective-C /C/C++, and it belongs to the compiler front end of the entire LLVM architecture. For developers, there are many benefits to studying Clang.

2.1: Compilation process

To print the compile phase of the source code, run the following command:

clang -ccc-print-phases main.m
Copy the code

The print result is as follows:

  1. Input file: Find the source file.
  2. Preprocessing stage: This process includes macro replacement and import of header files.
  3. Compilation stage: lexical analysis, grammar analysis, check whether the grammar is correct, the final generationIR(orbitcode).
  4. Back end: hereLLVMIt’s gonna go through one by onePass(segment, segment) to optimize, eachPassDo something that eventually generates assembly code.
  5. Generate the object file.
  6. Link: Link required dynamic and static libraries to generate executable files.
  7. Depending on the hardware architecture (hereM1versioniMAC.arm64), generate the corresponding executable file.

The optimizer is not specified because the optimizer is distributed in the front and back ends.

0: enter the source file

Find the source file.

1: pretreatment stage

Perform preprocessing instructions, including macro replacement, import of header files, conditional compilation, and generate new source code to the compiler.

With the following command, you can see the code after executing the preprocessor instruction:

// View it directly from the terminal
clang -E main.m

// Generate mian1.m file to view
clang -E main.m >> main1.m
Copy the code

2: Compilation phase

Perform lexical analysis, syntax analysis, semantic analysis, check whether syntax is correct, generate AST, generate IR (.ll) or bitcode (.bc) files.

2.1: Lexical analysis

After preprocessing, lexical analysis is performed to divide the code into tokens and indicate the number of lines and columns in which they are located, including keywords, class names, method names, variable names, parentheses, operators, etc.

You can use the following command to see the results of the lexical analysis:

clang -fmodules -fsyntax-only -Xclang -dump-tokens main.m
Copy the code

These graphs:

2.2: Grammatical analysis

Lexical analysis is followed by grammatical analysis, whose task is to verify the correctness of the grammatical structure of the source code. On the basis of lexical analysis, word sequences are combined into various grammatical phrases, such as “statement”, “expression”, etc., and then all nodes are formed into Abstract Syntax Tree (AST).

You can run the following command to view the result of syntax analysis:

clang -fmodules -fsyntax-only -Xclang -ast-dump main.m

// If the import header file is not found, specify the SDKClang-isysroot SDK path -fmodules-fsyntax-only - xclang-ast -dump main.mCopy the code

Syntax tree analysis:

// The addresses here are all virtual addresses (the offset address of the current file)
// Mach-o decompile to get the virtual address
// typedef 0x1298AD470 Virtual address
-TypedefDecl 0x1298ad470 <line:12:1, col:13> col:13 referenced XJ_INT_64 'int'
| `-BuiltinType 0x12a023500 'int'
// main returns int, the first argument int, the second argument const char **
`-FunctionDecl 0x1298ad778 <line:15:1, line:22:1> line:15:5 main 'int (int, const char **)'
  // The first argument
  |-ParmVarDecl 0x1298ad4e0 <col:10, col:14> col:14 argc 'int'
  // The second argument
  |-ParmVarDecl 0x1298ad628 <col:20, col:38> col:33 argv 'const char **':'const char **'
  // compound statement, current row 41 to 22 column 1
  // the main function {} range
  /* { XJ_INT_64 a = 10; XJ_INT_64 b = 20; printf("%d", a + b + C); return 0; } * /
  `-CompoundStmt 0x12a1aa560 <col:41, line:22:1>
    // declare xj_inT_64A = 10 in row 17, column 5 through column 21
    |-DeclStmt 0x1298ad990 <line:17:5, col:21>
      // Variable A, 0x1298AD908 Virtual address
    | `-VarDecl 0x1298ad908 <col:5, col:19> col:15 used a 'XJ_INT_64':'int' cinit
        / / value is 10
    |   `-IntegerLiteral 0x1298ad970 <col:19> 'int' 10
    Xj_int_64b = 20 xj_int_64b = 20
    |-DeclStmt 0x1298adeb8 <line:18:5, col:21>
      // Variable B, 0x1298AD9B8 Virtual address
    | `-VarDecl 0x1298ad9b8 <col:5, col:19> col:15 used b 'XJ_INT_64':'int' cinit
        / / value is 20
    |   `-IntegerLiteral 0x1298ada20 <col:19> 'int' 20
    // Call printf
    |-CallExpr 0x12a1aa4d0 <line:19:5, col:27> 'int'
      // Int printf(const char * __restrict,...)
    | |-ImplicitCastExpr 0x12a1aa4b8 <col:5> 'int (*)(const char *, ...) ' <FunctionToPointerDecay>
        // printf function 0x1298ada48 Virtual address
    | | `-DeclRefExpr 0x1298aded0 <col:5> 'int (const char *, ...) ' Function 0x1298ada48 'printf' 'int (const char *, ...) '
      // The first argument, "" contents
    | |-ImplicitCastExpr 0x12a1aa518 <col:12> 'const char *' <NoOp>
        // Type description
    | | `-ImplicitCastExpr 0x12a1aa500 <col:12> 'char *' <ArrayToPointerDecay>
          // %d
    | |   `-StringLiteral 0x1298adf30 <col:12> 'char [3]' lvalue "%d"
      // Add the value of a + b as the first value + the second value 30
    | `-BinaryOperator 0x12a1aa440 <col:18, line:10:11> 'int' '+'
        // 加法运算,a + b
    |   |-BinaryOperator 0x12a1aa400 <line:19:18, col:22> 'int' '+'
          // Type description
    |   | |-ImplicitCastExpr 0x1298adfc0 <col:18> 'XJ_INT_64':'int' <LValueToRValue>
            // a
    |   | | `-DeclRefExpr 0x1298adf50 <col:18> 'XJ_INT_64':'int' lvalue Var 0x1298ad908 'a' 'XJ_INT_64':'int'
          // Type description
    |   | `-ImplicitCastExpr 0x1298adfd8 <col:22> 'XJ_INT_64':'int' <LValueToRValue>
            // b
    |   |   `-DeclRefExpr 0x1298adf88 <col:22> 'XJ_INT_64':'int' lvalue Var 0x1298ad9b8 'b' 'XJ_INT_64':'int'
        // the macro replaces 30
    |   `-IntegerLiteral 0x12a1aa420 <line:10:11> 'int' 30
    // return 0
    `-ReturnStmt 0x12a1aa550 <line:21:5, col:12>
      `-IntegerLiteral 0x12a1aa530 <col:12> 'int' 0
\
Copy the code

Syntax error, the corresponding error is indicated:

2.3: Generate intermediate codeIR(intermediate representation)

After the above steps are completed, the intermediate Code IR is generated. The Code Generation will iterate the syntax tree from the top down and gradually translate it into LLVM IR. In this step, the OC code Bridges the Runtime, such as property synthesis, ARC processing, etc.

2.3.1: IRBasic syntax of

@global id % local ID ALloca open space align memory align I32 32 bits, 4 bytes Store write memory Load read data call call function RET return

You can run the following command to generate a. Ll text file and view the IR code.

clang -S -fobjc-arc -emit-llvm main.m
Copy the code

2.4: IRThe optimization of the

In the IR code above, you can see that by translating the syntax tree bit by bit, the GENERATED IR code, which looks a bit silly, can actually be optimized.

The optimization levels of LLVM are -O0, -O1, -O2, -O3, -OS, -ofAST, and -oz (the first one is uppercase O).

This can be optimized using the command:

clang -Os -S -fobjc-arc -emit-llvm main.m -o main.ll
Copy the code

The optimized IR code is concise and clear (the higher the optimization level is, the better it is, -OS in release mode, which is also the most recommended).

You can also set it in Xcode: target -> Build Setting -> Optimization Level

2.5: bitCode

After Xcode 7, if bitcode is enabled, Apple will further optimize the IR file of.ll to generate the intermediate code of the.bc file.

The optimized IR code is generated using the following command:

clang -emit-llvm -c main.ll -o main.bc
Copy the code

3: back-end stage (assembly generation.s)

The backend converts the received IR structure into different processing objects, and implements its processing as one Pass type after another. Through processing Pass, IR conversion, analysis and optimization are completed. Assembly code (.s) is then generated.

Generate assembly code using.bc or.ll code with the following command:

// bitcode -> .s
clang -S -fobjc-arc main.bc -o main.s
// IR -> .s
clang -S -fobjc-arc main.ll -o main.s
// Assembly code can also be optimized
clang -Os -S -fobjc-arc main.ll -o main.s
Copy the code

4: Assembly stage (generate the target file.o)

The generation of the object file is that the assembler takes the assembly code as input, converts the assembly code into machine code, and finally outputs the object file (.o).

The command is as follows:

clang -fmodules -c main.s -o main.o
Copy the code

Use the nm command to view the symbols in main.o:

xcrun nm -nm main.o
Copy the code

The following output is displayed:

You can see that after executing the command, an error was reported: the external _printf symbol could not be found. Because this function is imported from the outside, you need to link in the corresponding libraries you use.

5: Link stage (generate executable fileMach-O)

The linker links together the compiled.o files, the required dynamic library.dylib, and the static library.a to produce an executable (a Mach-o file).

The command is as follows:

clang main.o -o main
Copy the code

See the symbol after the link:

The external _printf symbol is still not found in the output, but it has been added (from libSystem) to indicate that the library _printf resides in is libSystem. This is because the libSystem dynamic library needs to be dynamically bound at run time. The test and main functions have also generated the offset position of the file. This file is now a correct executable.

It also has a dyLD_STUB_binder symbol, which is used for dynamic binding when mach-O is in memory. Dyld immediately bound the dyLD_STUB_binder function address in libSystem to the symbol in Mach-O. The dyLD_STUB_binder symbol is a non-lazy binding. Other lazy binding symbols, such as _printf here, are first used with dyLD_stub_binder to bind the real function address to the symbol, so that the call can be made using the symbol to find the corresponding function address in the library.

External function dynamic binding diagram:

The difference between links and bindings:

  • Link, compile time, mark symbol in which library, just make a mark.

  • Binding, at run time, binds the external function address to a symbol in Mach-O.

Execute the Mach -o file with the following command:

./main
Copy the code

Execution Result:

6: Bind the hardware architecture

According to different hardware architecture (here is M1 version iMAC, ARM64), generate the corresponding executable file.

2.2: Summarize the compilation process

2.2.1: Commands used in each phase

\
//// ====== Front-end start =====
// 1. Tokens main.m clang-fmodules-fsyntax-only - xclang-dump -tokens main.m
// 2
clang -fmodules -fsyntax-only -Xclang -ast-dump main.m // 3. Generate IR file clang-s-fobjc-arc-emit - LLVM main.m
// 3.1 Specify optimization level to generate IR file
clang -Os -S -fobjc-arc -emit-llvm main.m -o main.ll 
// 3.2 (according to compiler Settings) generate bitcode files
clang -emit-llvm -c main.ll -o main.bc 

//// ====== Back-end start =====

// 1. Generate assembler files
// bitcode -> .s 
clang -S -fobjc-arc main.bc -o main.s 
// IR -> .s 
clang -S -fobjc-arc main.ll -o main.s 
// Specify the optimization level to generate assembler files
clang -Os -S -fobjc-arc main.ll -o main.s 

// 2. Generate the target Mach-o file
clang -fmodules -c main.s -o main.o 
// 2.1 Check the mach-o file
xcrun nm -nm main.o 

// 3. Generate an executable mach-o file
clang main.o -o main 

//// ====== Start =====
// 4. Execute executable mach-o file
./main
Copy the code

Generating assembler files is already the job of the back end of the compiler, so why use clang? This is because we use the interface provided by Clang to call up the corresponding back-end functionality. As for whether the backend has its own unique command, I do not know 😂. Welcome to 😂.

2.2.2: File types generated at each stage

2.2.3: Compiling flow chart

Summary and notice

  • Interpreted language & compiled language

  • LLVM compiler (emphasis) :

    • Front end: read code, lexical analysis, syntax analysis, generationAST.LLVMUnique:IR, apple only:bc
    • Optimizer: According to one after anotherPassTo optimize
    • Back end: generate assembly code, generate object files, link dynamic and static libraries, and generate corresponding executable files according to different architectures
  • What are the benefits of LLVM?

    • Front and rear end separation, scalability is very strong.
  • LLVM compilation process (key points) :

    1. Input file: Find the source file.
    2. Preprocessing stage: This process includes macro replacement and import of header files.
    3. Compilation stage: lexical analysis, grammar analysis, check whether the grammar is correct, the final generationIR(orbitcode).
    4. Back end: hereLLVMIt’s gonna go through one by onePass(segment, segment) to optimize, eachPassDo something that eventually generates assembly code.
    5. Generate the object file.
    6. Link: Link required dynamic and static libraries to generate executable files.
    7. Depending on the hardware architecture (hereM1versioniMAC.arm64), generate the corresponding executable file.

This article introduces LLVM and Clang related concepts, design ideas, and compilation processes. The next article will use LLVM and Clang to implement a simple plug-in. Stay tuned for 😉!