【12】CS61C Midterm 1 Cheatsheet

  1. 5 Great Ideas in Computer Architecture

    1. Abstraction (Layers of Representation/Interpretation)
    2. Moore’s Law (Designing through trends)
    3. Principle of Locality (Memory Hierarchy)
    4. Parallelism & Amdahl’s law (which limits it)
    5. Dependability via Redundancy
  2. ENIAC (U.Penn., 1946)

    First Electronic General-Purpose Computer

    EDSAC (Cambridge, 1949)

    First General Stored-Program Computer

  3. Two’s Complement 补码

    One’s Complement 反码

  4. CPP (C Pre-Processor)

    CPP replaces comments with a single space

    CPP commands begin with “#”

  5. Constants can be found at: Code, static, or stack

  6. String Literals can be found at: Static or stack

  7. Undefined Behavior: “heisenbugs”

    In contrast to “Bohrbugs” which are deterministic

  8. C pass basic parameters “by value”

  9. C Program’s address space:

    Stack Heap StaticData Code

  10. Realloc Can Move Data

  11. Anything you put explicitly in quotes becomes a constant string. For efficiency, these strings are stored as read only global variables. It is undefined behavior to write to a constant string, But fortunately it is usually an immediate crash.

  12. Why Do Memory Leaks Slow Things Down?

    Memory leaks lead to fragmentation. As a consequence you use more memory, and its more scattered around. Computers are designed to access contiguous memory.

  13. Instruction set architecture (ISA) specifies the set of commands (instructions) a computer can execute.

  14. RISC-V: 32bit Instruction, 32 registers.

  15. RISC-V does not require that integers be word aligned.

  16. Instructions must be word aligned, or half-word aligned if the 16b optional © instruction set is also enabled.

  17. NOP add x0 x0 x0

  18. 12bits imm, immediates are “sign extended”

  19. Shift right arithmetic is sign extended,

    Shift Right Logical is not, insert 0s.

  20. Six Fundamental Steps in Calling a Function (The Calling Convention)

    1. Put parameters in a place where function can access them

    2. Transfer control to function

    3. Acquire (local) storage resources needed for function

    4. Perform desired task of the function

    5. Put result value in a place where calling code can access it and maybe restore any registers you used

    6. Return control to point of origin.

    (Note: a function can be called from several points in a program, including from itself.)

  21. Prologue ○ Before function begins ○ Stores saved registers that the function will use ○ Decrement the stack pointer to allocate space on the stack ○ If the function calls another function during its routine, also needs to store ra

  22. Epilogue ○ After function completes ○ Restores saved registers that the function used ○ Increment the stack pointer to free space on the stack ○ If the function called another function during its routine, also needs to restore ra

  23. Caller Saved:

    a0-a7, ra, t0-t6

  24. Callee Saved:

    sp, s0-s11, (ra), (fp(s0), gp, tp)

  25. Functions called with jal, return with jr ra.

  26. 6 Types:

    1. R-format for register-register arithmetic/logical operations

    2. I-format for register-immediate ALU operations and loads, JALR

    3. S-format for stores

    4. B-format for branches

    5. U-format for 20-bit upper immediate instructions

    6. J-format for jumps

  27. Immediate is always sign-extended to 32-bits before use in an arithmetic operation. (Unless unsigned)

  28. PC-Relative Addressing: Use the immediate field as a two’s-complement offset relative to PC.

  29. RISC-V conditional branches can only reach ± 2^10 × 32-bit instructions either side of PC

  30. Syntax of Multiplication (signed):

    mul rd, rs1, rs2

    mulh rd, rs1, rs2

    If you do mulh/mul back to back, the architecture can fuse them.

  31. Syntax of Division (signed):

    div rd, rs1, rs2

    rem rd, rs1, rs2

    can fuse

  32. Compiler converts a single HLL file into a single assembly language file.

  33. Assembler removes pseudoinstructions, converts what it can to machine language, and creates a checklist for the linker (relocation table). A .s file becomes a .o file.

    • Does 2 passes to resolve addresses, handling internal forward references
  34. Assembler Directives .text: Subsequent items in user text

    .data: Subsequent items in user data

    .globl sym: declares sym global, can reference in other files

    .string str: store str in memory and null-terminate it

    .word w1…wn: store n 32-bit ints in successive memory words

  35. Linker combines several .o files and resolves absolute addresses.

    • Enables separate compilation, libraries that need not be compiled, and resolves remaining addresses
  36. Loader loads executable into memory and begins execution.

  37. In reality, loader is the operating system (OS). And these days, the loader actually does a lot of the linking.

  38. Symbol table contains labels that can be used across other files.

    And relocation table contains labels within this file of which addresses are not yet resolved.

  39. The loader reads the header of the executable file to determine the size of text and data segments, not the object files.

  40. j label == jal x0 label

    jr reg == jalr x0 reg


807 Words

2019-02-20 11:15 +0800