Оптимизация трехадресного кода

У меня есть следующий трехадресный код, где n — некоторая внешняя константа:

   x = 0
   i = 0
L: t1 = i * 4
   t2 = a[t1]
   t3 = i * 4
   t4 = b[t3]
   t5 = t2 * t4
   x = x + t5
   i = i + 1
   if i < n goto L

Я хотел бы оптимизировать его настолько, насколько это возможно. Вот что я придумал до сих пор:

    x = 0
    i = 0
    t1 = -4
L:  t1 = t1+4
    t5 = a[t1] * b[t1]
    x = x + t5
    i = i + 1
    if i < n goto L

Кто-нибудь может предложить исправления/дополнительные оптимизации?


optimization assembly compiler-construction compiler-optimization machine-code
person John Roberts    schedule 16.04.2013    source источник
comment
Поддерживает ли целевая архитектура сложную адресацию памяти и способен ли codegen распознавать простые шаблоны для сопоставления с ней?   -  person harold    schedule 16.04.2013
comment
Здесь нет целевой архитектуры. Это больше педагогический пример, над которым я работаю, чтобы узнать об оптимизации кода компилятора.   -  person John Roberts    schedule 16.04.2013
comment
Ok. Очень жаль. В противном случае я бы предложил вычислять смещения до конца массивов, используя отрицательный индекс (тогда тест i < n становится i == 0, что скатывается в сложение) и адресуя массивы вида end[4 * i]. Это интересная оптимизация IMO, но она не зависит от цели.   -  person harold    schedule 16.04.2013

Ответы (1)


arrow_upward
1
arrow_downward

Я бы, наверное, сделал что-то вроде этого:

    x = 0
    t1 = (n-1)*4
L:  t5 = a[t1] * b[t1]
    x = x + t5
    t1 = t1 - 4
    if t1 >= 0 goto L

Я не знаю, что такое целевая машина, но последние две инструкции обычно можно выполнить с чем-то вроде SUB / JNS (что сохраняет сравнение).

person Michael    schedule 16.04.2013
comment
t1 = (n-1)*4 недопустимый трехадресный код. Кроме того, я не уверен, как это эквивалентно. Согласно оригиналу, T1 изначально должен быть равен 0 — нет гарантии, что n-1 будет равен 0. - person John Roberts; 16.04.2013
comment
Почему это не будет действительным 3AC, если n является константой (что вы указали в вопросе)? Значение выражения может быть оценено во время компиляции. Что касается того, как это эквивалентно; код (насколько я понимаю) вычисляет сумму произведений между a и b. Порядок, в котором выполняется суммирование, не должен иметь значения (он не влияет на результат), поэтому мой ответ повторяется в обратном порядке от n-1 до 0, поскольку обычно это более эффективно. - person Michael; 16.04.2013
comment
+1 для вас. Согласно статье в Википедии о TAC: выражения, содержащие более одной основной операции, не могут быть представлены в трехадресном коде как одна инструкция. Поэтому я думаю, что его нужно разбить на t1 = n-1 и t1 = t1 * 4. Кроме этого, я думаю, что ваше представление на самом деле эквивалентно, поэтому я отказываюсь от своих сомнений по этому поводу. Однако я все еще не уверен, что это оптимальнее - хотя у вас на одну инструкцию меньше, вы ввели дополнительную MUL-операцию. Хотя, возможно, ты и прав, я просто не уверен. - person John Roberts; 16.04.2013
comment
Тем не менее, дополнительный mul не в цикле, и как вообще определяется оптимальность, если у вас нет целевой архитектуры? Меньше всего инструкций? Наименьшее количество выполненных инструкций? Являются ли некоторые инструкции более тяжелыми, чем другие? - person harold; 16.04.2013
comment
Возможно, я был немного неясен в своем предыдущем комментарии: поскольку n является константой, вы можете оценить (n-1)*4 во время компиляции, например. если n равно 5, инструкция 3AC может быть t1 = 16. - person Michael; 16.04.2013