Loop in machine-level

Loop

Do-While loop
Do-while 역시 goto문으로 표현할 수 있다.

• 일반화

// just do-while in C
do
	Body
    while (Test);

// goto version in C
loop:
	Body
    if (Test) goto loop;

Example

// just do-while in C
long pcount_do(unsigned long x)
{
	long result = 0;
    do {
    	result += x & 0x1;
        x >>= 1;
    } while (x) ;
    return result;
}

$\darr$

// do-while with goto in C
long pcount_do_j(unsigned long x)
{
	long result = 0;
loop:
	result += x & 0x1;
    x >>= 1;
    if (x) goto loop;
    return result;	
}

$\darr$

Register	Use(s)
%rdi	Argument x
%rax	result

// do-while with goto in Assembly
pcount_do_j :
	movl $0, %eax // %eax에 0을 저장, %rax 전체 0으로 초기화
.L2 : // loop 진입
	movq %rdi, %rdx // %rdx에 %rdi 값 복사, t = x;
    andl $1, %edx // %rdx의 하위 비트 하나만 비교, t = x & 0x1
    addq %rdx, %rax // result += t
    shrq %rdi // %rdi 오른쪽으로 시프트 1회
    jne .L2 // %rdi != 0이면 .L2로 점프
    rep; ret // %rax 리턴, return result;

While loop

• Jump to Middle

// just while in C
while (Test)
	Body

// jump to middle in C
	goto test;
loop:
	Body
test:
    if (Test) goto loop;
done:

• goto version

// just while in C
while (Test)
	Body

// do-while in C
	if (!Test) goto done;
	do
		Body
    	while (Test);
done:

// goto in C
	if (!Test) goto done;
loop:
	Body
    if (Test) goto loop;
done:

Example1: Jump to Middle

// just while in C
long pcount_while(unsigned long x)
{
	long result = 0;
    while (x)
    {
    	result += x & 0x1;
        x >>= 1;
    }
    return result;
}

$\darr$

// jump to middle in C
long pcount_while_jtm(unsigned long x)
{
	long result = 0;
    goto test;
loop:
	result += x & 0x1;
    x >>= 1;
test:
	if (x) goto loop;
    return result;
}

Example2: goto

// just while in C
long pcount_while(unsigned long x)
{
	long result = 0;
    while (x)
    {
    	result += x & 0x1;
        x >>= 1;
    }
    return result;
}

$\darr$

// do-while in C
long pcount_while_dw(unsigned long x)
{
	long result = 0;
    if (!x) goto done;
    do
    {
    	result += x & 0x1;
        x >>= 1;
    } while (x);
done:
    return result;
}

$\darr$

//goto in C
long pcount_while_dwgt(unsigned long x)
{
	long result = 0;
    if (!x) goto done;
loop:
	result += x & 0x1;
    x >>= 1;
    if (x) goto loop;
done:
	return result;
}

For loop

• While conversion

// for in C
for (Init; Test; Update)
	Body

// for to while in C
Init;
while (Test)
	Body
    Update;

• Do-While conversion

// for in C
for (Init; Test; Update)
	Body

// for to do-while in C
Init;
if (!Test) goto done; // 생략 가능
loop:
	Body
	Update;
	if (Test) goto loop;
done:

<참고자료>
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition