update

UsanoCoCr · Sep 27, 2023 · 7ce897f · 7ce897f
1 parent c0afaf6
commit 7ce897f
Show file tree

Hide file tree

Showing 37 changed files with 3,583 additions and 1 deletion.
diff --git a/2023小班/2-information encoding.pdf b/2023小班/2-information encoding.pdf
diff --git a/2023小班/21班练习题/第二章补充题.docx b/2023小班/21班练习题/第二章补充题.docx
diff --git a/2023小班/21班练习题/第二章补充题答案.docx b/2023小班/21班练习题/第二章补充题答案.docx
diff --git a/2023小班/Seminar2.md b/2023小班/Seminar2.md
@@ -0,0 +1,10 @@
+# Seminar 2
+
+## 回课
+- 字长决定了虚拟地址空间的最大大小
+- 向偶数舍入：最低有效位为0表示偶数，向这个方向舍入
+
+## 补充
+- 为什么不把Tmin写成-21474..648? => -x = -(x)
+- 对立即数的判定顺序：int, unsigned, long, unsigned long, long long, unsigned long long
+- 逻辑运算符结果转换为有符号数
diff --git a/2023小班/回课/Bits, Bytes, Integers, and Floating Point.pptx b/2023小班/回课/Bits, Bytes, Integers, and Floating Point.pptx
diff --git a/LectureNote/1695791680227.png b/LectureNote/1695791680227.png
diff --git a/LectureNote/1695793935027.png b/LectureNote/1695793935027.png
diff --git a/LectureNote/Lecture1.md b/LectureNote/Lecture1.md
@@ -203,6 +203,7 @@ sizeof操作返回的类型是size_t，是一个无符号类型，i-DELTA在运
     - e.g. 0x01234567
         - 0x67 at lowest address
         - 0x01 at highest address
+- 小端法先读高地址，大端法读低地址
 ![Alt text](1694594369037.png)
 
 Internet Protocol (IP) uses big endian, while Intel uses little endian.

diff --git a/LectureNote/Lecture3.md b/LectureNote/Lecture3.md
@@ -138,7 +138,7 @@ objdump -d hello.o
     - dest = &source
 
 - Uses:
-    - **computing addresses without a memory reference**
+    - **computing addresses without a memory reference**, 即计算地址时不会访问内存
         -e.g. p = &a[i]
 
     - computing arithmetic expressions of the form x + k * y (k = 1, 2, 4, 8)

diff --git a/LectureNote/Lecture4.md b/LectureNote/Lecture4.md
@@ -0,0 +1,179 @@
+# Machine-Level Programming II: Control
+
+### Why use lea?
+- CPU designers intended to use: calculate a pointer to an object
+- Compiler author like to use it for arithmetic
+
+### Control Flow
+```c++
+extern void op1(void);
+extern void op2(void);
+
+void decision(int x){
+    if (x){
+        op1();
+    }
+    else{
+        op2();
+    }
+}
+```
+```assembly
+decision:
+    tsubl $8, %esp
+    je .L2 // jump if x == 0
+    call op1
+    jmp .L1
+.L2:
+    call op2
+.L1:
+    addl $8, %esp
+    ret
+```
+
+### Processor State
+- information about currently executing program
+    - Temporary data: %rax, %rcx, %rdx, %rsi, %rdi, %r8, %r9, %r10, %r11
+    - Location of runtime stack: %rsp
+    - Location of current code control point: %rip
+    - Status of current test: CF, ZF, SF, OF
+
+### Condition Codes
+- CF: carry flag
+- ZF: zero flag
+- SF: sign flag
+- OF: overflow flag
+
+- e.g. : addq src, dest $\equalscolon$ t = a + b
+    - CF set if carry/borrow out of most significant bit (unsigned overflow)
+    - ZF set if result is zero (t == 0)
+    - SF set if result is negative (t < 0)  
+    - OF set if two's complement overflow (signed overflow)
+        - (a>0 && b>0 && t<0) || (a<0 && b<0 && t>0)
+
+**Not set by leaq instruction**
+lea不会改变条件码
+
+CF: 如果是无符号数，那么借位、补位就意味着溢出，CF和二者等价
+
+### Condition Codes: Compare
+- cmpq src1, src2 $\equalscolon$ t = src2 - src1
+    - CF set if unsigned src2 < src1
+    - ZF set if src2 == src1
+    - SF set if src2 < src1 (signed)
+    - OF set if two's complement overflow (signed)
+
+### Condition Codes: Test
+- testq src1, src2 $\equalscolon$ t = src1 & src2
+    - ZF set if t == 0
+    - SF set if t < 0
+**very often: testq %rax, %rax**
+
+### Reading Condition Codes
+- setX instructions
+    - set low-order byte of destination to 0 or 1 based on combinations of condition codes
+
+    | setX | Condition | Description |
+    | --- | --- | --- |
+    | sete | ZF | Equal |
+    | setne | ~ZF | Not equal |
+    | sets | SF | Negative |
+    | setns | ~SF | Nonnegative |
+    | setg | \~(SF^OF)&~ZF | Greater than (signed) |
+    | setge | ~(SF^OF) | Greater than or equal (signed) |
+    | setl | (SF^OF) | Less than (signed) |
+    | setle | (SF^OF)| Less than or equal (signed) |
+    | seta | \~CF&~ZF | Above (unsigned) |
+    | setb | CF | Below (unsigned) |
+
+- e.g. setl(signed <)
+
+    | SF | OF | SF^OF | Implication |
+    | --- | --- | --- | --- |
+    | 0 | 0 | 0 | a-b >= 0 & no overflow |
+    | 0 | 1 | 1 | (a-b >= 0 & overflow) == a-b<0| 
+    | 1 | 0 | 1 | a-b < 0 & no overflow|
+    | 1 | 1 | 0 | (a-b < 0 & overflow) == a-b>=0|
+
+### Jumping
+- jump to different part of code based on condition codes
+
+    | jX | Condition | Description |
+    | --- | --- | --- |
+    | jmp | 1 | Unconditional |
+    | je | ZF | Equal |
+    | jne | ~ZF | Not equal |
+    | js | SF | Negative |
+    | jns | ~SF | Nonnegative |
+    | jg | \~(SF^OF)&~ZF | Greater than (signed) |
+    | jge | ~(SF^OF) | Greater than or equal (signed) |
+    | jl | (SF^OF) | Less than (signed) |
+    | jle | (SF^OF)| Less than or equal (signed) |
+    | ja | \~CF&~ZF | Above (unsigned) |
+    | jb | CF | Below (unsigned) |
+
+
+### General Conditional Expression Translation
+C Code:
+```c++
+    val = Test ? Then_Expr : Else_Expr;
+```
+Goto Version:
+```c++
+    ntest = !Test;
+    if (ntest) goto Else;
+    val = Then_Expr;
+    goto Done;
+Else:
+    val = Else_Expr;
+Done:
+```
+### Using Conditional Moves
+- Conditional Move Instructions
+    - Instruction supports: if (Test) Dest = Src;
+    - GCC tried to use them when known to be safe
+
+- Why
+    - Branches are very disruptive to instruction flow through pipeline
+    - Conditional moves do not require control transfer
+
+- Bad Cases
+    - Expensive Computation
+        - Both then and else value get computed
+        - only make sense when computations are cheap
+    - Risky Computation
+        - May have undesirable effects
+    - Computation with side effects
+        - Must be side-effect free
+
+### Loops
+- General Do-While Translation
+    ```c++
+    do
+        Body
+    while (Test);
+    ```
+    ```c++
+    //goto version
+    loop:
+        Body
+        if (test) goto loop;
+    ```
+
+    - Do-While Loop Compilation
+        ```assembly
+            movl $1, %eax // set result to 0
+        .L2:
+            imulq %rdi, %rax // result *= x
+            subq $1, %rdi // n--
+            cmpq $1, %rdi // n == 1?
+            jg .L2 // if n > 1, goto .L2
+            rep; ret // return result
+        ```
+
+- While Loop Example
+- For Loop Form
+
+### Switch Statements
+
+
diff --git a/LectureNote/Lecture5.md b/LectureNote/Lecture5.md
@@ -0,0 +1,153 @@
+# Machine-Level Programming III: Procedures
+
+## Mechanisms in Procedures
+- Passing control
+- Passing data
+- Memory management
+
+*Mechanisms all inplemented with machine instructions*
+
+*x86-64 inplementation of a procedure uses only those mechanisms required*
+
+e.g.
+```c++
+long mult2(long, long);
+void multstore(long x, long y, long *dest){
+    long t = mult2(x, y);
+    *dest = t;
+}
+```
+```assembly
+multstore:
+    pushq %rbx
+    call mult2
+    movq %rdx, (%rbx)
+    popq %rbx
+    ret
+```
+  - Passing control: call, ret
+  - Passing data: movq, movabsq
+  - Memory management: pushq, popq
+  - **Note**: %rbx is callee-saved register
+  - **Note**: %rdx is used to return value from mult2
+  - **Note**: %rax is used to return value from multstore
+  - **Note**: %rdi, %rsi, %rdx are used to pass arguments to mult2
+  - **Note**: %rdi is used to pass arguments to multstore
+  - **Note**: %rsp is used to allocate space for mult2
+  - **Note**: %rsp is used to allocate space for multstore
+
+### x86-64 Stack
+- Region of memory managed with stack discipline
+    - memory viewed as array of bytes
+    - different regions have different purpose
+    - grows toward lower addresses
+    - %rsp points to top of stack (**lowest address**)
+        ![Alt text](1695791680227.png)
+
+### x86-64 Stack: Push & Pop
+- pushq src $\equalscolon$ *%rsp $\leftarrow$ src, %rsp $\leftarrow$ %rsp - 8
+    - fetch operand
+    - **firstly decrement %rsp by 8**: allocate 8 bytes on stack
+    - write operand at address (%rsp)
+
+- popq dest $\equalscolon$ dest $\leftarrow$ *%rsp, %rsp $\leftarrow$ %rsp + 8
+    - read 8 bytes from address (%rsp)
+    - **firstly increment %rsp by 8**: deallocate 8 bytes on stack
+    - write bytes to dest(usually a register)
+
+**the memory does not change until, only the value of %rsp changes**
+
+## Passing Control
+### Procedure Control Flow
+- Use stack to support procedure call and return
+- procedure call: **call label**
+    - push **return address** on stack: address of the next instruction right after call
+    - jump to label
+- return address:
+    - **address of the next instruction right after call**
+- procedure return: **ret**
+    - pop return address from stack
+    - jump to return address
+
+### Procedure Data Flow
+- register first 6 arguments: %rdi, %rsi, %rdx, %rcx, %r8, %r9
+- return value: %rax
+- stack: other arguments, local variables, return address, saved registers
+
+**only allocate stack space when needed**
+
+## Manage Local Data
+### Stack-Based Language
+- Languages that support recursion
+    - C, C++, Java, Python, Scheme, ML, Haskell, ...
+    - Code must be "Reentrant"(可载入：可以被多次同时调用，自身是不会改变的)
+        - multiple simultaneous instantiations of single procedure
+        - e.g. 随机数发生器就不是reentrant的
+    - Need some place to store state of each instantiation
+        - local variables
+        - return pointer
+        - arguments
+- Stack discipline
+    - state for given procedure needed for limited time(栈上的数据只在有限的时间内有效)
+        - from when called to when return
+    - callee returns before caller does: 被调用者先返回，调用者后返回
+        - callee can overwrite state of caller
+        - callee can use same memory for all instantiations
+- Stack allocated in **Frames**(栈帧)
+    - state for single procedure instantiation: 栈帧是一次实例化时超出寄存器大小时在栈上分配的空间
+
+### Stack Frames
+- Contents
+    - return information
+    - local storage (if needed)
+    - temporaries (if needed)
+- Management
+    - space allocated when enter procedure
+        - "set-up" code
+        - includes push by call instruction
+    - deallocated when return
+        - "finish" code
+        - includes pop by ret instruction
+    ![Alt text](1695793935027.png)
+
+### x86-64/Linux Stack Frame
+- Current Stack Frame(从栈顶到栈底/低地址到高地址)
+    - argument build: parameters for function about to call
+    - local variables: if can't keep in registers
+    - saved register context
+    - old frame pointer: %rbp
+
+- Caller Stack Frame
+    - return address
+        - pushed by call instruction
+    - arguments for this call
+
+### x86-64/Linux Register Usage
+- %rbp: base pointer
+    - points to base of current stack frame
+    - **%rbp is callee-saved**
+- %rsp: stack pointer
+    - points to top of current stack frame
+    - **%rsp is callee-saved**
+- %rbx, %r12, %r13, %r14, %r15: callee-saved
+- %rax: return value
+    - **caller-saved**
+- %rdi, %rsi, %rdx, %rcx, %r8, %r9: first 6 arguments
+    - **caller-saved**
+- %r10, %r11: **caller-saved**
+
+### Illustration of Recursion
+- Handled without special consideration
+    - stack frames mean that each function call has private storage
+        - save registers & local variables
+        - save return address
+    - register saving conventions prevent one function call from corrupting another's data
+        - unless the C code explicitly does so
+    - stack discipline folloews call/return pattern
+        - if P calls Q, then Q returns before P does
+        - Last-In-First-Out(LIFO) property of stack
+
+- Also works for mutual recursion: P calls Q, Q calls P
+    - each call has its own stack frame
+    - each call returns to its caller
+    - each call has its own set of registers
diff --git a/datalab/datalab-handout.tar b/datalab/datalab-handout.tar
diff --git a/datalab/datalab-handout/Driverhdrs.pm b/datalab/datalab-handout/Driverhdrs.pm
@@ -0,0 +1,14 @@
+#
+# This file contains course and lab specific parameters for drivers.
+#
+package Driverhdrs;
+
+# This is no longer needed
+$COURSE_NAME = "15213-s16";
+
+# No need to ever update these
+$LAB = "datalab";
+$SERVER_NAME = "unofficial.fish.ics.cs.cmu.edu";
+$SERVER_PORT = "80";
+$AUTOGRADE_TIMEOUT = "300";
+1;