Architecture¶

2024年4月22日
分类于 Architecture
需要 2 分钟阅读时间

Memory Consistency and Cache Coherence

导言

许多现代计算机系统，包括同构和异构体系结构，都支持硬件中的共享内存。在共享内存系统中，每个处理器内核可以对单个共享地址空间进行读写。

要拓展Victima模拟器的cache部分，首先要明白一些缓存一致性的基础知识。

2024年1月4日
分类于 Architecture
需要 5 分钟阅读时间

CPU / GPU Performance Model based on Interval Analysis

导言

在与袁福焱交流他的GPU Design Space Exploration的工作内容时，发现和我PIM模拟器Zsim, Sniper的原理是异曲同工，师出本源的方法。

2024年1月3日
分类于 Architecture
需要 2 分钟阅读时间

New Generation Shenwei System

导言

研究生期间，虽然我是HPC方向的。但是我并没有参与过新一代神威系统的软件优化。在毕业前，特地了解相关设计。¹²

2023年11月14日
分类于 Architecture
需要 2 分钟阅读时间

Host-Core With PIM-Core In 3D-stacked Mem

导言

more clear about the connection and 3D-stacked Mem.

2023年8月1日
分类于 Architecture
需要 2 分钟阅读时间

Double 2 int8

将范围double映射到Int8

解释PPT：除开int8的映射，还考虑了误差的计算，和重新计算M+空间的double并排序。

注释：

采用的是欧式距离（两点直线距离），不是切比雪夫距离（max(delta x, delta y)）
C_2^n ，由于目标函数是所有边的距离和，所以要乘以边的数量。C_2^n 是从n个点中取两个点的组合数，也就是边的数量。
C_k^n , k是支撑点个数，n 是总个数。
修正M个，因为题目要求求TopM，由于第M个可能是 +delta来的，M+1个可能是-delta导致的，所以要修正M个后面2*delta的范围。

上面不知道具体怎么实现的（需要看代码）。下面同时要注意溢出的处理。int8溢出加法，可以转化为int16, 再相加。

_mm256_cvtepi8_epi16

AVX的操作Int寄存器也是分有无符号

_epi8 signed char, or _epu8 unsigned char

👏我要😘开吹了👏

本来IPCC2022 拿了第二名，我还心有不甘。直到我的风神大人教育了我。

拿到风神大人的PPT的时候，我醍醐灌顶。

这么体贴人，不愧是我温迪大人.

Disassembly file: objdump

objdump file

Disassembly of section .plt:

0000000000402020 <.plt>:
  402020: ff 35 e2 bf 02 00     pushq  0x2bfe2(%rip)        # 42e008 <_GLOBAL_OFFSET_TABLE_+0x8>
  402026: ff 25 e4 bf 02 00     jmpq   *0x2bfe4(%rip)        # 42e010 <_GLOBAL_OFFSET_TABLE_+0x10>
  40202c: 0f 1f 40 00           nopl   0x0(%rax)

0000000000402030 <_Znam@plt>:
  402030: ff 25 e2 bf 02 00     jmpq   *0x2bfe2(%rip)        # 42e018 <_Znam@GLIBCXX_3.4>
  402036: 68 00 00 00 00        pushq  $0x0
  40203b: e9 e0 ff ff ff        jmpq   402020 <.plt>

0000000000402040 <_ZNSo3putEc@plt>:
  402040: ff 25 da bf 02 00     jmpq   *0x2bfda(%rip)        # 42e020 <_ZNSo3putEc@GLIBCXX_3.4>
  402046: 68 01 00 00 00        pushq  $0x1
  40204b: e9 d0 ff ff ff        jmpq   402020 <.plt>

.plt节主要实现了使用过程链接表(Procedure Linkage Table)实现延迟绑定的功能。

openmp相关的执行

omp_outlined函数

问题：objdump 程序有许多类似 <.omp_outlined..16>: 的函数，但是main函数里并没有调用。实际openmp是怎么执行这些代码的呢？

在使用了OpenMP指令的C/C++程序编译后,编译器会自动生成一些名为.omp_outlined.的函数。这些函数是OpenMP所需要的运行时支持函数,不是直接在main函数中调用的,其执行方式主要有以下几种:

一些关键的运行时函数,如线程创建、同步等,是在程序启动时由OpenMP运行时库初始化和直接调用的。
对于并行region,编译器会在主线程发起并行时调用对应的.omp_outlined.函数创建线程并发布工作。
一些工作分配,同步等调用也是隐式通过运行时库的支持函数实现的。
对于并行循环,编译器会将循环体移动到.omp_outlined.函数,在循环分配工作时调用。
减少指令,作用域变化等也会引发这些函数的调用。

所以.omp_outlined.函数的执行是隐式通过运行时库触发和调度的,不需要用户代码直接调用。它们是OpenMP实现所必须的,由编译器和运行时库协调完成。用户只需要编写OpenMP指令,不必关心具体的调用细节。

总体来说,这是一种让并行执行透明化的实现机制,减少了用户的工作量。

OpenMP的汇编代码

不同平台不同，有GOMP_parallel_start开头的。也有如下x86平台的

  405854:   48 c7 84 24 a0 00 00    movq   $0x4293b9,0xa0(%rsp)
  40585b:   00 b9 93 42 00 
  405860:   48 8d bc 24 90 00 00    lea    0x90(%rsp),%rdi
  405867:   00 
  405868:   ba 10 5f 40 00          mov    $0x405f10,%edx
  40586d:   be 02 00 00 00          mov    $0x2,%esi
  405872:   4c 89 f9                mov    %r15,%rcx
  405875:   4c 8b 44 24 20          mov    0x20(%rsp),%r8
  40587a:   31 c0                   xor    %eax,%eax
  40587c:   e8 ff cb ff ff          callq  402480 <__kmpc_fork_call@plt>
  405881:   48 8b 7c 24 60          mov    0x60(%rsp),%rdi

这段汇编代码实现了OpenMP中的并行构造,主要执行了以下几个步骤:

在栈上写入一个常量0x4293b9,可能是team的参数 (48 c7 84 24)
准备参数,获取rsp+0x90地址到rdi作为第1参数 (%rdi)
设置edx为0x405f10,可能是kmp_routine函数地址
esi设置为2,可能表示有2个参数
r15设置到rcx,传入线程号参数
r8传入栈上第0x20个参数,可能是void* shareds参数
清空eax,一些调用约定使用
调用 __kmpc_fork_call函数,这是OpenMP的runtime库函数,用来并行执行一个函数
kmpc fork multiple parallel call？
最后将返回值保存在rdi指定的栈空间上

所以这段代码实现了调用OpenMP runtime并行执行一个函数的操作,准备参数,调用runtime API,获取返回值的一个流程。

利用runtime库的支持函数可以实现汇编级别的OpenMP并行性。

readelf

各section位置以及含义，参考文档

$ readelf -S bfs.inj
There are 37 section headers, starting at offset 0xbe8e8: 
在文件内 0xbe8e8字节开始

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  序号 节名称               节类型          节的虚拟地址偏移量      节在文件中的偏移量
节大小         每个条目的大小（如果大小固定）  节的标志  节的链接信息    节的额外信息    节的信息对齐方式
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .interp           PROGBITS         00000000004002a8  000002a8
       000000000000001c  0000000000000000   A       0     0     1
  [ 2] .note.gnu.build-i NOTE             00000000004002c4  000002c4
       0000000000000024  0000000000000000   A       0     0     4
  [ 3] .note.ABI-tag     NOTE             00000000004002e8  000002e8
       0000000000000020  0000000000000000   A       0     0     4
  [ 4] .gnu.hash         GNU_HASH         0000000000400308  00000308
       000000000000005c  0000000000000000   A       5     0     8
  [ 5] .dynsym           DYNSYM           0000000000400368  00000368
       00000000000007e0  0000000000000018   A       6     1     8
  [ 6] .dynstr           STRTAB           0000000000400b48  00000b48
       0000000000000b1d  0000000000000000   A       0     0     1
  [ 7] .gnu.version      VERSYM           0000000000401666  00001666
       00000000000000a8  0000000000000002   A       5     0     2
  [ 8] .gnu.version_r    VERNEED          0000000000401710  00001710
       0000000000000110  0000000000000000   A       6     5     8
  [ 9] .rela.dyn         RELA             0000000000401820  00001820
       00000000000000f0  0000000000000018   A       5     0     8
  [10] .rela.plt         RELA             0000000000401910  00001910
       00000000000006c0  0000000000000018  AI       5    24     8
  [11] .init             PROGBITS         0000000000402000  00002000
       000000000000001b  0000000000000000  AX       0     0     4
  [12] .plt              PROGBITS         0000000000402020  00002020
       0000000000000490  0000000000000010  AX       0     0     16
  [13] .text             PROGBITS         00000000004024b0  000024b0
       0000000000026475  0000000000000000  AX       0     0     16
  [14] .fini             PROGBITS         0000000000428928  00028928
       000000000000000d  0000000000000000  AX       0     0     4
  [15] .rodata           PROGBITS         0000000000429000  00029000
       0000000000001180  0000000000000000   A       0     0     16
  [16] .eh_frame_hdr     PROGBITS         000000000042a180  0002a180
       00000000000002ac  0000000000000000   A       0     0     4
  [17] .eh_frame         PROGBITS         000000000042a430  0002a430
       0000000000001780  0000000000000000   A       0     0     8
  [18] .gcc_except_table PROGBITS         000000000042bbb0  0002bbb0
       00000000000005d0  0000000000000000   A       0     0     4
  [19] .init_array       INIT_ARRAY       000000000042dbc8  0002cbc8
       0000000000000010  0000000000000008  WA       0     0     8
  [20] .fini_array       FINI_ARRAY       000000000042dbd8  0002cbd8
       0000000000000008  0000000000000008  WA       0     0     8
  [21] .data.rel.ro      PROGBITS         000000000042dbe0  0002cbe0
       00000000000001f0  0000000000000000  WA       0     0     8
  [22] .dynamic          DYNAMIC          000000000042ddd0  0002cdd0
       0000000000000220  0000000000000010  WA       6     0     8
  [23] .got              PROGBITS         000000000042dff0  0002cff0
       0000000000000010  0000000000000008  WA       0     0     8
  [24] .got.plt          PROGBITS         000000000042e000  0002d000
       0000000000000258  0000000000000008  WA       0     0     8
  [25] .data             PROGBITS         000000000042e258  0002d258
       0000000000000010  0000000000000000  WA       0     0     8
  [26] .bss              NOBITS           000000000042e280  0002d268
       0000000000000180  0000000000000000  WA       0     0     64
  [27] .comment          PROGBITS         0000000000000000  0002d268
       000000000000004a  0000000000000001  MS       0     0     1
  [28] .debug_info       PROGBITS         0000000000000000  0002d2b2
       000000000002a06e  0000000000000000           0     0     1
  [29] .debug_abbrev     PROGBITS         0000000000000000  00057320
       0000000000000a57  0000000000000000           0     0     1
  [30] .debug_line       PROGBITS         0000000000000000  00057d77
       000000000000af9a  0000000000000000           0     0     1
  [31] .debug_str        PROGBITS         0000000000000000  00062d11
       0000000000010328  0000000000000001  MS       0     0     1
  [32] .debug_loc        PROGBITS         0000000000000000  00073039
       0000000000042846  0000000000000000           0     0     1
  [33] .debug_ranges     PROGBITS         0000000000000000  000b587f
       00000000000054c0  0000000000000000           0     0     1
  [34] .symtab           SYMTAB           0000000000000000  000bad40
       00000000000018c0  0000000000000018          35   106     8
  [35] .strtab           STRTAB           0000000000000000  000bc600
       0000000000002177  0000000000000000           0     0     1
  [36] .shstrtab         STRTAB           0000000000000000  000be777
       000000000000016c  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

字段含义

Type 字段，具体含义参考文档1-10
Link 字段中的值是节头表中节头条目的索引，索引从0开始，表示第一个节头表条目，依此类推。比如5 代表与[ 5] .dynsym 有关

值得注意

One section type, SHT_NOBITS described below, occupies no space in the file, and its sh_offset member locates the conceptual placement in the file.

so the number "2d258" remains unchanged.

  [25] .data             PROGBITS         000000000042e258  0002d258
       0000000000000010  0000000000000000  WA       0     0     8
  [26] .bss              NOBITS           000000000042e280  0002d268
       0000000000000180  0000000000000000  WA       0     0     64

.plt

This section holds the procedure linkage table. See ‘‘Special Sections’’ in Part 1 and ‘‘Procedure Linkage Table’’ in Part 2 for more information.

Function symbols (those with type STT_FUNC) in shared object files have special significance. When another object file references a function from a shared object, the link editor automatically creates a procedure linkage table entry for the referenced symbol.

参考文档2-17 page48

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

无

2023年7月27日
分类于 Architecture
需要 9 分钟阅读时间

Cache

导言

Cache is to reduce latency

2023年7月26日
分类于 Architecture
需要 3 分钟阅读时间

llvm

LLVM项目开始于一种比Java字节码更低层级的IR，因此，初始的首字母缩略词是Low Level Virtual Machine。它的想法是发掘低层优化的机会，采用链接时优化。

插一嘴：链接时优化

GCC也支持链接时优化，称为LTO（Link Time Optimization），通过把多个编译单元中分别生成的目标文件在链接时进行全局的优化，可以提高程序的执行效率。
具体内容：大幅度减少可执行文件的体积
冗余代码和变量/函数的消除：对于在多个模块中出现的相同代码/变量/函数，链接时优化可以将它们合并，从而减少可执行文件的体积，提高程序的执行效率。
内联函数：将函数调用直接替换为函数本身的代码，从而减少函数调用的开销，提高程序的执行效率。
循环展开和向量化：内联函数后，或许能进一步将循环展开和向量化，从而减少循环体内的分支判断，优化程序的执行效率。

IR：gcc与llvm的区别

学过编译原理的人都知道，编译过程主要可以划分为前端与后端：

前端把源代码翻译成中间表示 (IR)。
后端把IR编译成目标平台的机器码。当然，IR也可以给解释器解释执行。

经典的编译器如gcc：在设计上前端到后端编写是强耦合的，你不需要知道，无法知道，也没有API来操作它的IR。

好处是：因为不需要暴露中间过程的接口，编译器可以在内部做任何想做的平台相关的优化。
坏处是，每当一个新的平台出现，这些编译器都要各自为政实现一个从自己的IR到新平台的后端。
甚至如果当一种新语言出现，且需要实现一个新的编译器，那么可能需要设计一个新的IR，以及针对大部分平台实现这个IR的后端。
如果有M种语言、N种目标平台，那么最坏情况下要实现 M*N 个前后端。这是很低效的。
LLVM的核心设计了一个叫 LLVM IR 的通用中间表示，并以库(Library) 的方式提供一系列接口，为你提供诸如操作IR、生成目标平台代码等等后端的功能。
在使用通用IR的情况下，如果有M种语言、N种目标平台，那么最优情况下我们只要实现 M+N 个前后端。

llvm IR

LLVM IR 中间表示是适用于多种编程语言的通用中间表示，支持C、C++、Objective-C、Swift、Java、Python等多种编程语言。
它是一种低级别的语言，类似于汇编语言，但比汇编语言更高级，包含了类型、变量、函数、控制流等高级语言的特性。
LLVM编译器可以将多种编程语言编译成LLVM IR，从而可以在LLVM IR层面进行各种优化处理，再将LLVM IR转换为目标平台的机器码。
比如要将Python脚本编译成LLVM IR中间表示，可以使用Python LLVM编译器llvmlite和numba。

LLVM IR表示与转换

LVM IR实际上有三种表示：

.ll 格式：人类可以阅读的文本。
.bc 格式：适合机器存储的二进制文件。
内存表示

各种格式是如何生成并相互转换：

格式	转换命令
.c -> .ll	clang -emit-llvm -S a.c -o a.ll
.c -> .bc	clang -emit-llvm -c a.c -o a.bc
.ll -> .bc	llvm-as a.ll -o a.bc
.bc -> .ll	llvm-dis a.bc -o a.ll
.bc -> .s	llc a.bc -o a.s

对于LLVM IR来说，.ll文件就相当于汇编，.bc文件就相当于机器码。这也是llvm-as和llvm-dis指令为什么叫as和dis的缘故。

llvm 前端

clang实现的前端包括

词法分析(识别标记)
处理源代码的文本输入，将语言结构分解为一组单词和标记，去除注释、空白、制表符等。每个单词或者标记必须属于语言子集，语言的保留字被变换为编译器内部表示。
词法分析报错的例子包括：拼写错误、注释没有正确结束、字符串没有正确结束等。
语法分析(标记结构完整)
语法分析器会根据语法规则验证程序的正确性，如缺少右括号、是否缺少关键字、变量未定义、函数应该有返回值等。
语义分析(有无语义矛盾)
借助符号表检验代码没有违背语言类型系统。这个表存储标识符（符号）和它们各自的类型之间的映射，以及其它内容。
类型检查的一种直觉的方法是，在解析之后，遍历AST的同时从符号表收集关于类型的信息。
例子：定义了两个变量 a 冲突。

llvm 后端

见 llvm Backend 一文

clang

clang 与 llvm的关系

Clang 是 LLVM 项目中的一个 C/C++/Objective-C 编译器，它使用 LLVM 的前端和后端进行代码生成和优化。它可以将 C/C++/Objective-C 代码编译为 LLVM 的中间表示（LLVM IR），然后进一步将其转换为目标平台的机器码。Clang 拥有很好的错误信息展示和提示，支持多平台使用，是许多开发者的首选编译器之一。同时，Clang 也作为 LLVM 项目的一个前端，为 LLVM 的生态系统提供了广泛的支持和应用。

clang 的开发与苹果公司的关系

Clang 的开发起源于苹果公司的一个项目，即 LLVM/Clang 项目。在 2005 年，苹果公司希望能够使用一种更加灵活、可扩展、优化的编译器来替代 GCC 作为其操作系统 macOS (Mac OS X) 开发环境的默认编译器。由于当时的 GCC 开发被其维护者们认为变得缓慢和难以维护，苹果公司决定开发一款新的编译器，这就是 Clang 诞生的原因。Clang 的开发团队由该项目的创立者 Chris Lattner 领导，他带领团队将 Clang 发展为一款可扩展、模块化、高效的编译器，并成功地将其嵌入到苹果公司的开发工具链 Xcode 中，成为了 macOS 开发环境中默认的编译器之一。

Clang 是一个开源项目，在苹果公司的支持下，Clang 的开发得到了全球各地的开发者们的广泛参与和贡献。现在，Clang 成为了 LLVM 生态中的一个重要组成部分，被广泛地应用于多平台的编译器开发中。

clang-cannot-find-iostream

Clang and Clang++ "borrow" the header files from GCC & G++. It looks for the directories these usually live in and picks the latest one. If you've installed a later GCC without the corresponding G++, Clang++ gets confused and can't find header files. In your instance, for example, if you've installed gcc 11 or 12.

You can use clang-10 -v -E or clang++-10 -v -E to get details on what versions of header files it's trying to use.

安装g++-12解决

常用工具

github/tools目录下有许多实用工具

llvm-as：把LLVM IR从人类能看懂的文本格式汇编成二进制格式。注意：此处得到的不是目标平台的机器码。
llvm-dis：llvm-as的逆过程，即反汇编。不过这里的反汇编的对象是LLVM IR的二进制格式，而不是机器码。
opt：优化LLVM IR。输出新的LLVM IR。
llc：把LLVM IR编译成汇编码。需要用as进一步得到机器码。
lli：解释执行LLVM IR。

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

文章部分内容来自ChatGPT-3.5，暂时没有校验其可靠性(看上去貌似说得通)。

https://zhuanlan.zhihu.com/p/122522485

2023年6月27日
分类于 Architecture
需要 8 分钟阅读时间

Assembly X86

关于X86 与 arm的寄存器的区别写在了arm那篇下

IDA analysis

word/ dword/ qword

In x86 terminology/documentation, a "word" is 16 bits

x86 word = 2 bytes

x86 dword = 4 bytes (double word)

x86 qword = 8 bytes (quad word)

x86 double-quad or xmmword = 16 bytes, e.g. movdqa xmm0, [rdi].

常见X86汇编

https://en.wikipedia.org/wiki/X86_instruction_listings

https://www.felixcloutier.com/x86/

https://officedaytime.com/simd512e/

官方手册第一个4800页

SHR     # Shift right (unsigned shift right)
SAL       # Shift Arithmetically left (signed shift left)
lea       # Load Effective Address, like mov but not change Flags, can store in any register, three opts
imul      # Signed multiply
movslq    # Move doubleword to quadword with sign-extension.
movl $0x46dd0bfe, 0x804a1dc #将数值0x46dd0bfe放入0x804a1dc的地址中
movl 0x46dd0bfe, 0x804a1dc #将0x46dd0bfe地址里的内容放入0x804a1dc地址中

lea & leaq

lea    -0xc(%ebp),%eax
mov    %eax,0x8(%esp) #常见于scanf第三个参数，lea传结果写入地址

// x is %rdi, result is %rax 就是计算地址，没有寻址操作
lea    0x0(,%rdi,8),%rax //result = x * 8;
lea    0x4b(,%rdi),%rax //result = x + 0x4b;

call & ret

Call 地址：返回地址入栈（等价于“Push %eip，mov 地址，%eip”；注意eip指向下一条尚未执行的指令）
ret：从栈中弹出地址，并跳到那个地址（pop %eip）

leave

leave：使栈做好返回准备，等价于

mov %ebp，%esp
pop %ebp

compare order

cmpl   $0x5,$0x1
jle    8048bc5 # Jump if Less or Equal 会触发，前面的 1<=5

X86 load store

X86 不像 ARM有专门的ldr， str指令。是通过mov实现的

movswl (%rdi), %eax sign-extending load from word (w) to dword (l). Intel movsx eax, word [rdi]

AVX

https://docs.oracle.com/cd/E36784_01/html/E36859/gntbd.html

vxorpd   XORPD
Bitwise Logical XOR for Double-Precision Floating-Point Values

vxorps   XORPS
Bitwise Logical XOR for Single-Precision Floating-Point Values

vmovaps  MOVAPS
Move Aligned Packed Single-Precision Floating-Point Values

test & jump

test    al, al
jne     0x1000bffcc

The test instruction performs a logical and of the two operands and sets the CPU flags register according to the result (which is not stored anywhere). If al is zero, the anded result is zero and that sets the Z flag. If al is nonzero, it clears the Z flag. (Other flags, such as Carry, oVerflow, Sign, Parity, etc. are affected too, but this code has no instruction testing them.)

The jne instruction alters EIP if the Z flag is not set. There is another mnemonic for the same operation called jnz.

test   %eax,%eax
jg     <phase_4+0x35> # eax & eax > 0 jump

注意 cmp不等于 test

The TEST operation sets the flags CF and OF to zero.

The SF is set to the MSB(most significant bit) of the result of the AND.

If the result of the AND is 0, the ZF is set to 1, otherwise set to 0.

kinds of jump

AT&T syntax jmpq *0x402390(,%rax,8) into INTEL-syntax: jmp [RAX*8 + 0x402390].

ja VS jg

JUMP IF ABOVE AND JUMP IF GREATER

ja jumps if CF = 0 and ZF = 0 (unsigned Above: no carry and not equal)

jg jumps if SF = OF and ZF = 0 (signed Greater, excluding equal)

FLAGS

cmp performs a sub (but does not keep the result).

cmp eax, ebx

Let's do the same by hand:

 reg     hex value   binary value  

 eax = 0xdeadc0de    ‭11011110101011011100000011011110‬
 ebx = 0x1337ca5e    ‭00010011001101111100101001011110‬
  -    ----------
 res   0xCB75F680    11001011011101011111011010000000

The flags are set as follows:

OF (overflow) : did bit 31 change      -> no
SF (sign)     : is bit 31 set          -> yes
CF (carry)    : is abs(ebx) < abs(eax) -> no  
ZF (zero)     : is result zero         -> no
PF (parity)   : is parity of LSB even  -> no (archaic)
AF (Adjust)   : overflow in bits 0123  -> archaic, for BCD only.

Carry Flag

Carry Flag is a flag set when:

a) two unsigned numbers were added and the result is larger than "capacity" of register where it is saved.

Ex: we wanna add two 8 bit numbers and save result in 8 bit register. In your example: 255 + 9 = 264 which is more that 8 bit register can store. So the value "8" will be saved there (264 & 255 = 8) and CF flag will be set.

b) two unsigned numbers were subtracted and we subtracted the bigger one from the smaller one.

Ex: 1-2 will give you 255 in result and CF flag will be set.

Auxiliary Flag is used as CF but when working with BCD. So AF will be set when we have overflow or underflow on in BCD calculations. For example: considering 8 bit ALU unit, Auxiliary flag is set when there is carry from 3rd bit to 4th bit i.e. carry from lower nibble to higher nibble. (Wiki link)

Overflow Flag is used as CF but when we work on signed numbers.

Ex we wanna add two 8 bit signed numbers: 127 + 2. the result is 129 but it is too much for 8bit signed number, so OF will be set.

Similar when the result is too small like -128 - 1 = -129 which is out of scope for 8 bit signed numbers.

register signed & unsigned

Positive or negative The CPU does not know (or care) whether a number is positive or negative. The only person who knows is you. If you test SF and OF, then you treat the number as signed. If you only test CF then you treat the number as unsigned. In order to help you the processor keeps track of all flags at once. You decide which flags to test and by doing so, you decide how to interpret the numbers.

register multiply

The computer makes use of binary multiplication(AND), followed by bit shift (in the direction in which the multiplication proceeds), followed by binary addition(OR).

1100100
0110111
=======
0000000
-1100100
--1100100
---0000000
----1100100
-----1100100
------1100100
==============
1010101111100

100 = 1.1001 * 2^6
55  = 1.10111* 2^5
100 * 55 -> 1.1001 * 1.10111 * 2^(6+5)

for more:

How computer multiplies 2 numbers? And: Binary multiplier - Wikipedia

Memory and Addressing Modes

声明静态代码区域

DB, DW, and DD can be used to declare one, two, and four byte data locations,

# 基本例子
.DATA       
var DB 64   ; Declare a byte, referred to as location var, containing the value 64.
var2    DB ?    ; Declare an uninitialized byte, referred to as location var2.
DB 10   ; Declare a byte with no label, containing the value 10. Its location is var2 + 1.
X   DW ?    ; Declare a 2-byte uninitialized value, referred to as location X.
Y   DD 30000        ; Declare a 4-byte value, referred to as location Y, initialized to 30000.

数组的声明，The DUP directive tells the assembler to duplicate an expression a given number of times. For example, 4 DUP(2) is equivalent to 2, 2, 2, 2.

Z   DD 1, 2, 3  ; Declare three 4-byte values, initialized to 1, 2, and 3. The value of location Z + 8 will be 3.
bytes   DB 10 DUP(?)    ; Declare 10 uninitialized bytes starting at location bytes.
arr DD 100 DUP(0)       ; Declare 100 4-byte words starting at location arr, all initialized to 0
str DB 'hello',0    ; Declare 6 bytes starting at the address str, initialized to the ASCII character values for hello and the null (0) byte.

寻址

32位X86机器寻址支持

最多支持32位寄存器和32位有符号常数相加
其中一个寄存器可以再乘上 2，4，8

# right
mov eax, [ebx]  ; Move the 4 bytes in memory at the address contained in EBX into EAX
mov [var], ebx  ; Move the contents of EBX into the 4 bytes at memory address var. (Note, var is a 32-bit constant).
mov eax, [esi-4]    ; Move 4 bytes at memory address ESI + (-4) into EAX
mov [esi+eax], cl   ; Move the contents of CL into the byte at address ESI+EAX
mov edx, [esi+4*ebx]        ; Move the 4 bytes of data at address ESI+4*EBX into EDX

# wrong and reason
mov eax, [ebx-ecx]  ; Can only add register values
mov [eax+esi+edi], ebx      ; At most 2 registers in address computation

指定存储在地址的数据大小

mov BYTE PTR [ebx], 2   ; Move 2 into the single byte at the address stored in EBX.
mov WORD PTR [ebx], 2   ; Move the 16-bit integer representation of 2 into the 2 bytes starting at the address in EBX.
mov DWORD PTR [ebx], 2      ; Move the 32-bit integer representation of 2 into the 4 bytes starting at the address in EBX.

汇编寄存器顺序，作用方向

这和汇编器语法有关：

X86 instructions

For instructions with two operands, the first (lefthand) operand is the source operand, and the second (righthand) operand is the destination operand (that is, source->destination).

mov eax, ebx — copy the value in ebx into eax
add eax, 10 — EAX ← EAX + 10

AT&T syntax

AT&T Syntax is an assembly syntax used in UNIX environments, that originates from AT&T Bell Labs. It is descended from the MIPS assembly syntax. (AT&T, American Telephone & Telegraph)

AT&T Syntax is an assembly syntax used mostly in UNIX environments or by tools like gcc that originated in that environment.

语法特点：https://stackoverflow.com/tags/att/info

需要注意的：

Operands are in destination-last order
Register names are prefixed with %, and immediates are prefixed with $
sub $24, %rsp reserves 24 bytes on the stack.
Operand-size is indicated with a b/w/l/q suffix on the mnemonic
addb $1, byte_table(%rdi) increment a byte in a static table.
The mov suffix (b, w, l, or q) indicates how many bytes are being copied (1, 2, 4, or 8 respectively)
imul $13, 16(%rdi, %rcx, 4), %eax 32-bit load from rdi + rcx<<2 + 16, multiply that by 13, put the result in %eax. Intel imul eax, [16 + rdi + rcx*4], 13.
movswl (%rdi), %eax sign-extending load from word (w) to dword (l). Intel movsx eax, word [rdi].

Intel syntax (used in Intel/AMD manuals).

The Intel assembler(icc,icpc我猜) uses the opposite order (destination<-source) for operands.

语法特点： https://stackoverflow.com/tags/intel-syntax/info

RISC-V

beq rs1, rs2, Label #RISC-V
SW rs2, imm(rs1)  # Mem[rs1+imm]=rs2 ,汇编将访存放在最后
add rd, rs1, rs2  # rd = rs1 + rs2

反汇编器

但是这个语法不是很重要，因为decompiler有选项控制语法

objdump has -Mintel flag, gdb has set disassembly-flavor intel option.

gcc -masm=intel -S or objdump -drwC -Mintel.

2023年5月31日
分类于 Architecture
需要 2 分钟阅读时间

llvm Backend

llvm 后端概述

后端（backend）由一套分析和转换Pass组成，它们的任务是代码生成，即将LLVM中间表示（IR）变换为目标代码（或者汇编）。
LLVM支持广泛的目标：ARM，AArch64，Hexagon，MSP430，MIPS，Nvidia PTX，PowerPC，R600，SPARC，SystemZ，X86，和XCore。
所有这些后端共享一套共用的接口，它是目标无关代码生成器的一部分，以通用API的方法抽象化后端任务。每个目标必须特殊化代码生成通用类，以实现目标特定的行为。

后端的基本流程

下图给出了将LLVM IR转换为目标汇编代码必需的步骤

Backend

浅灰色的中间框，也叫super pass，是必需的，它们是后端的核心部分。
白色框所指示的，可以执行非必需的优化Pass以进一步改进翻译的质量。对于提高所生成的代码的效率更重要。
比如-O3的优化，而且其顺序对结果也有影响。

详细解释各阶段：

指令选择（Instruction Selection）：将三地址结构的LLVM IR变换为DAG（Directed Acyclic Graph）
每个DAG能够表示单一基本块的计算。DAG内节点表示机器指令，边表示数据依赖关系。
第1次指令调度（Instruction Scheduling），也称为前寄存器分配（RA）调度，对指令排序，同时尝试发现尽可能多的指令层次的并行。然后这些指令被变换为MachineInstr三地址表示。
寄存器分配（Register Allocation），它将无限的虚拟寄存器的引用转换为有限的目标特定的寄存器集，寄存器不够时挤出（spill）到内存。
第2次指令调度，也称为后寄存器分配（RA）调度。因为此时在这个点可获得真实的寄存器信息，某些类型寄存器存在额外的风险和延迟，它们可被用以改进指令顺序。
代码输出（Code Emission）阶段将指令从MachineInstr表示变换为MCInst实例。这种新的表示更适合汇编器和链接器，它有两种选择：输出汇编代码或者输出二进制块（blob）到一种特定的目标代码格式。

后端代码结构

后端的实现分散在LLVM源代码树的不同目录中。代码生成背后的主要程序库位于lib目录和它的子文件夹CodeGen、MC、TableGen、和Target中，具体参考文档

Tablegen位置在类似 llvm/lib/Target/X86/X86.td的地方

llvm 编译优化

通过llvm的分析和转换Pass相结合实现的。
首先，通过分析Pass获取程序的一些特性和数据流等信息，例如控制流分析、数据流分析、依赖分析等。
然后，根据所得到的分析信息，llvm会执行转换Pass，对程序进行一系列的重构、优化和变换，例如常量传播、死代码消除、内联函数、循环展开等。

举例：O3优化实现

程序优化选项 -O3 是通过启用 LLVM Pass Manager 并按照顺序执行包含多个具体优化 Pass 的过程实现的。包括：

函数内部优化 Pass，如内联、函数内联、无用函数清理、控制流扁平化；
函数间优化 Pass，如基于静态单走边分析的间接调用目标推导、函数每次调用的参数的重复计算消除、通过符号解析执行的函数简介化等。
模块优化 Pass，如死代码消除、全局优化、常量传播、数值宽化和窄化、整除优化等；
特定于架构的优化 Pass，包括指令调度和寄存器分配等。

这些 Pass 的执行范围涵盖 LLVM IR 与 LLVM 后端。

TableGen

LLVM的TableGen是一种表格驱动代码生成工具，主要用于生成汇编器、反汇编器、指令选择器、调度器等代码。
它使用基于LLVM IR的DSL(Domain-Specific Language)来描述目标指令集的特性和规则，然后将这些信息转换为C++代码。
使用TableGen可以将目标指令集的实现与源代码分离，从而提高代码的可读性和可维护性。

TableGen的输入文件使用扩展名“.td”（TableGen的缩写），它们可以描述如下内容：

Instruction Set Architecture (ISA) - 描述目标机的指令集特性，例如指令集架构、寄存器、寄存器类、操作数类型、地址模型、端对齐性等。
Selection DAG - 描述了如何将LLVM IR节点映射到目标机指令集的指令，例如指令的操作码、操作数、调用约定、指令延迟等。
Pattern Matching - 对匹配到的指令模板做出生成想要的IR节点的选择。
Instruction Scheduling - 描述调度器行为、指令之间的时间关系，以及如何将指令插入到调度图中的规则等。
TableGen自动化了目标机指令集的大部分工作，同时也使得自定义目标机变得相对容易。
该工具支持针对多种平台和编译器的后端代码生成。
对于嵌入式系统和非标准指令集架构等领域，TableGen有着广泛的应用。