Чтение кода сборки IA32, касающегося использования двойных массивов

Question

Это точный вопрос:

Следующий код транспонирует элементы массива M x M, где M константа, определенная #define:

void transpose(Marray_t A) {
    int i, j;
    for (i = 0; i < M; i++)
        for (j = 0; j < i; j++) {
           int t = A[i][j];
           A[i][j] = A[j][i];
           A[j][i] = t;
       } 
}

При компиляции с уровнем оптимизации -02 GCC генерирует следующее код для внутреннего цикла функции:

1. .L3 
2. movl (%ebx),%eax 
3. movl (%esi,%ecx,4),%edx 
4. movl %eax, (%esi,%ecx,4) 
5. addl $1, %ecx 
6. movl %edx, (%ebx) 
7. addl $52,%ebx 
8. cmpl %edi,%ecx 
9. jl .L3

A. Какова стоимость М?

B. Какие регистры содержат значения программы i и J?

C. Напишите версию транспонирования C-кода, которая использует оптимизации, которые происходят в этом цикле. Используйте параметр M в вашем код, а не числовая константа.

Итак, в моих попытках понять это, я заметил, что он умножается на 4, что означает, что он хранит типы 4 байта (может быть, int или указатель). Затем он увеличивает i на 52 долл. (Я полагаю, i), поскольку это большее значение, и, следовательно, переход к следующему массиву), а 52/4 равняется 13. Поэтому я бы предположил, что M = 13. Неверно?

Для B я бы предположил, что% ebx содержит i, а% ecx содержит i.

Для C я не совсем уверен, потому что я не совсем понимаю представленный цикл. Позвольте мне попытаться понять по номеру строки и сказать мне, где я не прав. 1. очевидно, это начало метки цикла. 2. перемещает предположительно значение i в% eax. Тогда 3. сохраняет A [i] [j] в t. Но ... я действительно не понимаю этого. :/ Помогите??

Answer 1

Я исправил некоторые ошибки в коде ассемблера (%ecs -> %ecx и (ebx) -> (%ebx)). Надеюсь, я случайно не ввел новые ошибки.

На вопросы, где вы почти там с пониманием. Давайте возьмем код построчно и попытаемся перевести его на C.

   L3:
2. movl (%ebx),%eax
   // We load a 32-bit value from the address stored in ebx. We can't yet deduce the type, but let's assume int for now
   int *ebx = ??;         
   int eax = *ebx; 
3. movl (%esi,%ecx,4),%edx
   // As you noted we're dealing with 32-bit values, so when converting to C we divide the index by 4
   int *esi = ??;
   int ecx = ??; 
   int edx = esi[ecx]; 
4. movl %eax, (%esi,%ecx,4)
   esi[ecx] = eax; 
5. addl $1, %ecx 
   ecx++;
6. movl %edx, (%ebx)
   *ebx = edx; 
7. addl $52,%ebx
   // Again we have to remember to divide by the size of the type used (4)
   ebx += 13; 
8. cmpl %edi,%ecx 
9. jl .L3
   int edi = ??; 
   if (ecx < edi) goto L3;

Из этого мы видим, что у нас есть некоторые неизвестные значения, которые инициализируются вне внутреннего цикла, но мы также можем дать хорошие предположения относительно того, что они из себя представляют.

• ecx увеличивается при каждой итерации цикла, а затем используется для определения того, следует ли продолжать цикл: очевидно, это j из кода C.
• edi - это значение, с которым мы сравниваем j при принятии решения о цикле, но оно не изменяется во внутреннем цикле: оно i.
• esi индексируется построчно с ecx (j), поэтому оно соответствует &a[i][j].
• ebx увеличивается на 52 (13 позиций индекса) на каждой итерации цикла - как вы уже догадались, 13 - это M - это соответствует &m[j][i] и перемещается в точку на j -ом элементе строки следующий столбец каждой итерации.

Теперь мы можем ответить на вопросы:

A. Какое значение М?

13

B. Какие регистры содержат программные значения i и j?

edi и ecx соответственно.

C. Напишите версию кода транспонирования C, которая использует оптимизации, которые происходят в этом цикле. Используйте параметр M в своем коде, а не числовую константу.

Это должно быть прямо сейчас.