A life of detested source code: from Clang to LLVM to MachO

Type of programming language

1.1 Interpreted language

Python and JS are common interpreted languages. They execute without generating an executable.

Their execution process is as follows:

1.2 Compiled languages

Common C\C++, Objective-C, Swift are compiled languages that need to go through the following process to generate executable files before they can be executed.

Second, the LLVM

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

The LLVM project was initiated in 2000 by Dr. ChrisLattner of UIUC university in the us. In 2006, ChrisLattner joined Apple inc and devoted himself 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.

ChrisLattner is also the father of Swift. To the big guy 🧎♂️

2.1 Traditional compiler design

Compiler front end

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

The optimizer

The optimizer is responsible for various optimizations that improve the runtime of your code, such as eliminating redundant calculations.

Back end/code generator

Map code to the target instruction set, generate machine language, and perform machine-specific code optimizations.

2.2 iOS compiler architecture

The ObjectiveC/C/C++ compiler uses Clang on the front end, Swift on the back end and LLVM on the back end.

2.3 Design of LLVM

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

Other compilers, such as GCC, have been very successful, but because it was designed as a whole application, its use has been very limited.

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. So LLVM can write a separate front end for any programming language and a separate back end for any hardware architecture.

Third, Clang

For our developers, our Clang is the one we touch the most.

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 C, C++, objecte-C, and it belongs to the whole LLVM architecture, the compiler front-end. For developers, there are many benefits to studying Clang.

Explore the compilation process of Objective-C

Let’s explore the following code as an example

#import <Foundation/Foundation.h>

int addResult(int a, int b) {
    return a + b;
}

#define ADD_FUNCTION(x, y) addResult(x, y)

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int numA = 1;
        int b1 = 1;
        int b2 = 2;
        int numB = b1 + b2;
        int result = ADD_FUNCTION(numA, numB);
        NSLog(@"Result: %d", result);
    }
    return 0;
}
Copy the code

4.1 Compilation Phase Overview

We can list the complete compile phases with the following command:

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

0: input file
- Find the source file
1: pretreatment
- This process includes macro replacement and import of header files
2: compile
- For lexical analysis, grammar analysis, check whether the grammar is correct, and finally generate IR
3: the back end
- Here LLVM is optimized one Pass at a time, each Pass doing something to generate assembly code
4: assembly
- Generate object file
5: link
- Link the required dynamic and static libraries to generate the corresponding image executable
6: Binding structure
- Generate corresponding executable files according to different system architectures

4.2 pretreatment

Clang-e main.m >> preprocessing. MCopy the code

By comparison, it is obvious that the macro definition has been replaced.

4.3 Compilation Phase

Lexical analysis

The code is sliced up into tokens, such as brackets, equals signs, and strings.

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

Syntax analysis

The task of parsing is to verify that the syntax is correct. On the basis of lexical analysis, word sequences are combined into various grammatical phrases, such as “program”, “statement”, “expression”, etc., and then all nodes are formed into AbstractSyntaxTree (AbstractSyntaxTree, AST). The purpose of grammar analysis is to analyze and judge whether the source program is structurally correct.

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

Produce intermediate code IR

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

Here will generate.ll file, extract a section of addResult related code for simple analysis:

; Function Attrs: noinline nounwind optnone ssp uwtable
define i32 @addResult(i32 %0, i32 %1) #1{%3 = alloca i32, align 4 // Open 32 bit space, 4 bytes, %3
  %4 = alloca i32, align 4
  store i32 %0, i32* %3, align 4 // Save the %0 argument to %3
  store i32 %1, i32* %4, align 4
  %5 = load i32, i32* %3, align 4 // Read %5 from %3
  %6 = load i32, i32* %4, align 4
  %7 = add nsw i32 %5%,6 // the value of %5 + %6 is saved to %7
  ret i32 %7 // Returns %7 32bit
}
Copy the code

The main function:

; Function Attrs: noinline optnone ssp uwtable
define i32 @main(i32 %0, i8** %1) #2 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  %5 = alloca i8**, align 8
  %6 = alloca i32, align 4
  %7 = alloca i32, align 4
  %8 = alloca i32, align 4
  %9 = alloca i32, align 4
  %10 = alloca i32, align 4
  store i32 0, i32* %3, align 4
  store i32 %0, i32* %4, align 4
  store i8** %1, i8*** %5, align 8
  %11 = call i8* @llvm.objc.autoreleasePoolPush() #3
  store i32 1, i32* %6, align 4
  store i32 1, i32* %7, align 4
  store i32 2, i32* %8, align 4
  %12 = load i32, i32* %7, align 4
  %13 = load i32, i32* %8, align 4
  %14 = add nsw i32 %12, %13
  store i32 %14, i32* %9, align 4
  %15 = load i32, i32* %6, align 4
  %16 = load i32, i32* %9, align 4
  %17 = call i32 @addResult(i32 %15, i32 %16)
  store i32 %17, i32* %10, align 4
  %18 = load i32, i32* %10, align 4
  notail call void (i8*, ...) @NSLog(i8* bitcast (%struct.__NSConstantString_tag* @_unnamed_cfstring_ to i8*), i32 %18)
  call void @llvm.objc.autoreleasePoolPop(i8* %11)
  ret i32 0
}
Copy the code

Compiler optimization

The debug mode is not optimized by default.

Let’s pass in the corresponding optimization level and reproduce it as.ll (using the same Os as release) :

Clang-os-s-fobjc-arc-emit - LLVM main.m -o main optimized. LlCopy the code

addResult

; Function Attrs: norecurse nounwind optsize readnone ssp uwtable willreturn
define i32 @addResult(i32 %0, i32 %1) local_unnamed_addr #1 {
  %3 = add nsw i32 %1, %0
  ret i32 %3
}
Copy the code

main

; Function Attrs: optsize ssp uwtable define i32 @main(i32 %0, i8** nocapture readnone %1) local_unnamed_addr #2 { %3 = tail call i8* @llvm.objc.autoreleasePoolPush() #3 notail call void (i8*, ...) @NSLog(i8* bitcast (%struct.__NSConstantString_tag* @_unnamed_cfstring_ to i8*), i32 4) #5, ! clang.arc.no_objc_arc_exceptions ! 9 tail call void @llvm.objc.autoreleasePoolPop(i8* %3) #3 ret i32 0 }Copy the code

Here we find that the optimized intermediate code is introduced quite a bit, and the redundant computational logic in the code directly generates the results

bitCode

This is xcode7 after the start of bitcode apple will do further optimization, generated BC intermediate code. We can try to generate BC code with optimized IR code.

Clang-emit - LLVM -c main optimized ll-o main optimized.bcCopy the code

The BC file here cannot be viewed in text mode

Generating assembly code

Assembly code can be generated from.bc or.ll code

Clang-s-fobjc-arc main Optimized bc-o main optimized S or Clang-s-fobjc-arc main not optimized ll-o main not optimizedCopy the code

Comparing the assembly code before and after optimization, it is found that the optimized instruction is much less:

Generate object file

Clang-fmodules-c main is not optimized. S-o main is not optimizedCopy the code

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. This stage is the work of the compiler back end.

See the sign

Xcrun nm-nm main is not optimizedCopy the code

Output:

                 (undefined) external _NSLog
                 (undefined) external ___CFConstantStringClassReference
                 (undefined) external _objc_autoreleasePoolPop
                 (undefined) external _objc_autoreleasePoolPush
0000000000000000 (__TEXT,__text) external _addResult
0000000000000020 (__TEXT,__text) external _main
000000000000008e (__TEXT,__ustring) non-external l_.str
Copy the code

_NSLogIs one isundefined external 的
- undefined
  - Symbol temporarily not found in current file_NSLog
- external
  - Indicates that the symbol is externally accessible

If you’re interested, you can go through the symbol table and find the symbol and there’s a procedure for finding _NSLog

Generate an executable file

The linker compiles the resulting.o and (dylib.a) files to create a Mach-o file (executable).

clang main.o -o main
Copy the code

Error:

Undefined symbols for architecture x86_64:
  "_NSLog", referenced from:
      _main in main.o
  "___CFConstantStringClassReference", referenced from:
      CFString in main.o
  "_objc_autoreleasePoolPop", referenced from:
      _main in main.o
  "_objc_autoreleasePoolPush", referenced from:
      _main in main.o
ld: symbol(s) not found for architecture x86_64
Copy the code

Because we’re using symbols in the Foundation framework that NSLog can’t be generated directly, we’re going to add parameters

clang -framework Foundation main.o -o main
Copy the code

Generated successfully: