레지스터 할당을위한 알고리즘

Question

나는 모든 것을 스택에 둔 내 오래된 것을 선호하여 Trees를위한 코드 생성/레지스터 할당 알고리즘을 구현하려고합니다. 이제 Sethi-Ullman algorithm을 구현하려고하지만 위키 피 디아와 일부 웹 페이지에서 발견 한 내용만으로 알고리즘의 일부분이 분명하지 않습니다.

일부 의사 코드/C/C++ 작업 코드가 없으므로 부분에 대한 설명을 찾고 있습니다.

1) 무료 등록을 선택하려면 어떤 방법을 사용해야합니까? 즉, 사용 된 레지스터 스택. 나는 아주 가난하다고 생각하는 것을 사용하고 있습니다 : 대체적으로 레지스터를 반환하십시오 : 이전에 레지스터가 R0이면 R1을 반환하십시오. R1이면 R0을 반환합니다. 작은 표현에는 효과가 없습니다.

2) label(left) >= K and label(right) >= K 일 때 어떻게해야합니까?

2+b*3 

그것은 생성 않습니다 :

LOAD R0,[b] 
LOAD R1,3 
MUL R0,R1 
LOAD R1,2 
ADD R1,R0 

그리고 이런 하나를

다음은이 같은 특급에서 나무를 들어 label 및 sethi-ullman 기능

REG reg() 
{ 
    static REG r = REG_NONE; 

    switch(r) { 
     case REG_NONE: 
      r = REG_r0; 
      break; 
     case REG_r0: 
      r = REG_r1; 
      break; 
     case REG_r1: 
      r = REG_r0; 
      break; 
     default: 
      assert(0); 
      break; 
    } 
    return r; 
} 

void SethiUllman(AST *node) 
{ 
    static const int K = 2; 

    if(node->left != NULL && node->right != NULL) { 
      int l = node->left->n; 
      int r = node->right->n; 

      if(l >= K && r >= K) { 
       SethiUllman(node->right); 
       node->n = node->n - 1; 
       //emit(node->right, REG_r0); 
       SethiUllman(node->left); 
       //emit(node->left, REG_r1); 
      } 
      else if(l >= r) { 
       SethiUllman(node->left); 
       SethiUllman(node->right); 
       node->n = node->n - 1; 
      } 
      else if(l < r) { 
       SethiUllman(node->right); 
       SethiUllman(node->left); 
       node->n = node->n - 1; 
      } 

      node->reg = reg(); 

      printf("%s %s,%s\n", 
         op_string(node->type), 
         reg_string(node->left->reg), 
         reg_string(node->right->reg)); 

     } 
    else if(node->type == TYPE::id) { 
     node->n = node->n + 1; 
     node->reg = reg(); 
     emit(node); 
    } 
    else { 
     node->reg = reg(); 
     emit(node); 
    } 
} 

void label(AST *node) 
{ 
    if(node == NULL) 
     return; 

    label(node->left); 
    label(node->right); 

    if(node->left != NULL && node->right != NULL) { 
     int l = node->left->n; 
     int r = node->right->n; 
     if(l == r) 
      node->n = 1 + l; 
     else 
      node->n = max(1, l, r); 
    } 
    else if(node->type == TYPE::id) { 
     node->n = 1; 
    } else if(node->type == TYPE::number) { 
     node->n = 0; 
    } 
} 

입니다 :

난 단지 주요 알고리즘을 제공보다도

LOAD R0,[b] 
LOAD R1,3 
MUL R0,R1 
LOAD R1,2 
ADD R1,R0 
LOAD R1,8 < R1 is not preserved. I don't know how it should be done. 
ADD R0,R1 

하지만 필요한 경우 나, 컴퓨터에 테스트 케이스에 전체 코드를 제공 할 수 있습니다

8+(2+b*3) 

그것은 생성 않습니다.

Answer 1

표현식이 계산에 2 개 이상의 레지스터를 필요로하지 않아서 8+(2+b*3) 표현이 단지 "작동하지"않는 이유를 이해하지 못합니다. 그러나 두 개의 레지스터에서 전체 계산을 수행 할 수없는 경우 임시 (스택) 위치에 레지스터를 저장 한 다음 다시 필요할 때 임시 위치에서 값을 복원하는 "흘러 내림"을 수행해야합니다.

LOAD R0,[b] 
LOAD R1,3 
MUL R0,R1  ; R0 = b*3 
LOAD R1,2  
ADD R1,R0  ; R1 = 2+(b*3) 
LOAD R1,8 < R1 is not preserved. I don't know how it should be done. 
ADD R0,R1 

우리는 유출하여, 그것을 다시 작성할 수 있습니다 :

이것은 당신이 게시 코드입니다 그러나

LOAD R0,[b] 
LOAD R1,3 
MUL R0,R1  ; R0 = b*3 
LOAD R1,2  
ADD R1,R0  ; R1 = 2+(b*3) 
STORE R1, [tmp] 
LOAD R1,8 < R1 is not preserved. I don't know how it should be done. 
LOAD R0, [tmp] 
ADD R0,R1 

는,이 제안하는 흘리고없이 할 수 있다는 것을 실제 알고리즘 당신 똑같이,

LOAD R0,[b] 
LOAD R1,3 
MUL R0,R1  ; R0 = b*3 
LOAD R1,2  
ADD R0,R1  ; R0 = 2+(b*3) 
LOAD R1,8  ; Use R0 above -> R1 is now free. 
ADD R0,R1 

또는 : 사용하는 것은 잘못된 것입니다

LOAD R0,[b] 
LOAD R1,3 
MUL R0,R1  ; R0 = b*3 
LOAD R1,2  
ADD R1,R0  ; R1 = 2+(b*3) 
LOAD R0,8  ; Store in R1 above -> R0 is now free. 
ADD R0,R1 

잘 모르겠습니다 만, 처음에는 ADD 명령어의 왼쪽/오른쪽 피연산자를 선택하는 것이 좋을 것이라고 생각합니다.

일부 인쇄물을 추가하여 코드를 따르고 다양한 상황에서 어떤 결과가 나오는지 봅니다.