x86-64学习2-Control

Made by Mike_Zhang

Computer System 相关文章:
有符号二进制数表示方法 Signed binary number representation
浮点数二进制数表示方法 Floating point numbers representation
UltraFish Plus - 有符号二进制数转换器 Signed binary number convertor
UltraFish Plus - 浮点数表示方法转换器 Floating Point Numbers Representation Convertor
UltraFish Plus - 多进制整数转换器 Multiple Bases Unsigned Integer Convertor
Y86-64学习1-State & Instruction & Basic Encoding
Y86-64学习2-Y86-64 SEQ Stages
x86-64学习1-Introduction & Data Formats & Information Accessing & Arithmetic Logical Operation
x86-64学习2-Control

1 Condition Codes

Condition Codes(CC): Describe attributes of the most recent arithmetic or logic operation.

  • CF: Carry Flag, the carry out of the MSB, to detect overflow for unsigned operations;
  • ZF: Zero Flag, Yielding zero;
  • SF: Sign Flag, Yielding a negative value;
  • OF: Overflow Flag, overflow due to two’s complement, negative or positive.

Integer arithmetic operations (CS: APP)

In above Integer arithmetic operations:

  • For leaq: do not update to CC, only compute the address;
  • For others: causes the CC to be set,
    • For logical operations (e.g. XOR), CF and OF set to 0;
    • For shift operations,CF set to the last bit shifted out; OF set to 0;
    • For INC and DEC: OF and ZF will be set, NO change to CF.

Comparison and test instructions (CS: APP)

CMP and TEST set CC without changing any other registers:

CMP:

  • Set CC based on the difference;
  • Same as SUB, without changing the destination;
  • CMP S1, S2: S2-S1, in reverse order;
  • ZF: 0 means two operands are equal;
  • Other flags: the ordering relation between them;

TEST:

  • Same as AND, without changing the destination;
  • Two same operands: to detect whether it is negative, zero or positive;
  • Marked operand: to detect some specific bits.

2 Accessing Condition Codes


The SET instructions (CS: APP)

Using the CC:

  • Set single bit to 0 or 1 based on the combinations of the CC;
  • Conditionally jump;
  • Conditionally transfer data.

For the first case, the SET instructions:

  • Destination: low-order single-byte register, or single-byte memory location;
    • Will not alter the remaining bytes, need to clear upper bits to 0, using e.g. movzbl.

[Example]
For a < b expression in C:


Example of the SET instructions (CS: APP)

3 Jump Instructions


The jump instructions (CS: APP)

Jump instruction make the execution to a completely new position in the program.

  • The assembler encode the jump target which is the destination address into the jump instruction.
  • jmp: unconditionally jump, direct and indirect jump:
    • direct jump: jump target encoded in the instruction, giving the target label, e.g.
      • jmp .L1;
    • indirect jump: jump target read from register or memory address, using * following by an operand specifier, e.g.,
      • jmp *%rax: register jump target;
      • jmp *(%rax): memory location target;
  • others ara conditionally jump, based on some combination of the CC.

4 Conditional Branches with Conditional Control


Compilation of conditional statements (CS: APP)

General form of if-else statement in C:

1
2
3
4
if (test-expr)
    then-statement
else
    else-statement

goto code:

1
2
3
4
5
6
7
8
    t = test-statement
    if (!t)
        goto false
    then-statement
    got done
false:
    else-statement
done:
  • Only one of the two branch statement will be executed;
  • The complier generates separated blocks of code for then-statement and else-statement;
  • Drawbacks: this mechanism is simple and general, but very inefficient on modern processors.

5 Conditional Branches with Conditional Moves


Compilation of conditional statements using conditional assignment (CS: APP)
  • Via conditional transfer of data;
  • Computes both outcomes of a conditional operation and selected based on the condition holding;
  • Achieving high performance through pipelining in modern processor;
    • Overlapping steps of success instructions;
    • Determining the sequence of instruction well ahead of time to keep the pipeline full;

The conditional move instructions (CS: APP)
  • S, D: 16, 32, 64-bit long, NO Single-bit;
  • The assembler encodes the operand length based on the name of destination register;
  • No prediction: Just 1. read the source value; 2. check the CC; 3. update the destination register or keep no change;

General form of conditional expression and assignment:

1
v = test-expr ? then-expr : else-expr;

Goto code:

1
2
3
4
5
6
7
    if (!test-expr)
        goto false;
    v = then-expr;
    goto done;
false:
    v = else-expr;
done:
  • Both then-expr and else-expr will be executed, finally based on the test-expr.

Assembly code example:

1
2
3
4
v = then-expr;
ve = else-expr;
t = test-expr;
if (!t) v = ve;

Bad Cases for Conditional Move:

  • Expensive Computations

    • val = Test(x) ? Hard1(x) : Hard2(x);
    • Both function need to be executed;
    • Only use it when computations are very simple;

  • Risky Computation

    • val = p ? *p : 0;
    • Both value get computed;
    • May be *0, null pointer, error!
    • May have undesirable effect.

  • With side effects

    • val = x > 0 ? x*=7 : x+= 3;
    • Both value get computed;
    • Same variable got change;
    • MUST be side-effect free!

6 Loop Implementations

6.1 Do-While Loops

General form of a do-while statement:

1
2
3
do
    body-statement
    while(test-expr);

Goto code:

1
2
3
4
5
loop:
    body-statement
    t = test-expr;
    if (t)
        goto loop;
  • body-statement executed at least once;

Code for do–while version of factorial program (CS: APP)
    1. Initialization of result;
    1. Execute the body of the loop;
    1. Test the condition, then do the jump or not.

6.2 While Loops

General form of a while statement:

1
2
while(test-expr)
    body-statement
  • The test-expr evaluated before the loop body, the loop may be terminated before first execution of the body.

6.2.1 Jump-to-middle Translation

Performs the initial test via jumping to the test at then end of the loop, then go to the loop body if holds.

Goto code:

1
2
3
4
5
6
7
    goto test;
loop:
    body-statement
test:
    t = test-expr;
    if (t)
        goto loop;

C and assembly code for while version of factorial using jump-to-middle translation (CS: APP)
  • Test n before modifying the value of n or result.

6.2.2 Guarded-do Translation

It transfer the while loop into a do-while loop, test the condition at first, jump to skip the loop body if test fails.

while to do-while code:

1
2
3
4
5
6
7
t = test-expr;
if (!t)
    goto done;
do
    body-statement
    while (test-expr);
done:

Goto code:

1
2
3
4
5
6
7
8
9
t = test-expr;
if (!t)
    goto done;
loop:
    body-statement
    t = test-expr;
    if (t)
        goto loop;
done:

C and assembly code for while version of factorial using guarded-do translation (CS: APP)

6.3 For Loops

General form of a for loop:

1
2
for (init-expr; test-expr; update-expr)
    body-statement

Transfer to while loop:

1
2
3
4
5
init-expr;
while (test-expr) {
    body-statement
    update-expr;
}

Jump-to-middle goto code:

1
2
3
4
5
6
7
8
9
    init-expr;
    goto test;
loop:
    body-statement
    update-expr;
test:
    t = test-expr;
    if (t)
        goto loop;

Guarded-do goto code:

1
2
3
4
5
6
7
8
9
10
11
    init-expr;
    t = test-expr;
    if (!t)
        goto done;
loop:
    body-statement
    update-expr;
    t = test-expr;
    if (t)
        goto loop;
done:

[Example]

1
2
3
4
5
6
7
8
long fact_for(long n)
{
    long i;
    long result = 1;
    for (i = 2; i <= n; i++)
        result *= i;
    return result;
}

Transfer to while loop:

1
2
3
4
5
6
7
8
9
10
long fact_for_while(long n)
{
    long i = 2;
    long result = 1;
    while (i <= n) {
        result *= i;
        i++;
    }
    return result;
}

Jump-to-middle goto code:

1
2
3
4
5
6
7
8
9
10
11
12
13
long fact_for_jm_goto(long n)
{
    long i = 2;
    long result = 1;
    goto test;
loop:
    result *= i;
    i++;
test:
    if (i <= n)
        goto loop;
    return result;
}

Assembly code:

7 Switch Implementations


Example switch statement and its translation into extended C (CS: APP)

Assembly code for switch statement (CS: APP)

Jump Table (CS: APP)
  • Jump Table: jt[i] is the address of a code segment will be accessed when the switch index is i;
  • Key step is to access the code location through the jump table (see in RED BOX );
  • Three cases:
      1. Test whether the switch index is out of the range, for the missing cases, just jump to the default case (loc_def) for case 101 and 105;
      1. Duplicate case, assign the same code label(loc_D) for the same entries (e.g. 104 and 106);
      1. Fall-through case, for 102 to 103, omitting the jmp instruction at the end of case 102.

参考

B. Randal, D. R. O’Hallaron, Computer systems : a programmer’s perspective, Third edition. Boston: Pearson, 2016.

写在最后

x86-64相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

原创文章，转载请标明出处
Made by Mike_Zhang




感谢你的支持
Computer System > x86-64
#学习 #Computer System #x86-64
x86-64学习2-Control
https://ultrafish.io/post/x86-64-learning-2/
Author
Mike_Zhang
Posted on
February 24, 2022
Licensed under