Оптимизация «статических» циклов

Question

Я пишу скомпилированный язык для удовольствия, и я недавно получил возможность сделать мой оптимизационный компилятор очень надежным. Я вычислил несколько способов оптимизации некоторых вещей, например, 2 + 2 всегда 4, поэтому мы можем выполнить эту математику во время компиляции, если (false) {...} можно полностью удалить и т. Д., Но теперь Я получил петли. После некоторых исследований я считаю, что то, что я пытаюсь сделать, - это не совсем разворачивание цикла, но это все еще метод оптимизации. Позволь мне объяснить.

Выполните следующий код.

String s = ""; 
for(int i = 0; i < 5; i++){ 
    s += "x"; 
} 
output(s); 

Как человек, я могу сидеть здесь и сказать, что это 100% времени будет эквивалентно

output("xxxxx"); 

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

Я придумал три типа петель, которые мне нужно выяснить, как классифицировать. Петли, которые всегда будут иметь одно и то же состояние машины после каждого прогона, независимо от входов, циклов, которые НИКОГДА не завершатся, и циклов, которые я не могу понять так или иначе. В случае, если я не могу понять это (он условно меняет, сколько раз он будет работать на основе динамических ресурсов), я не беспокоюсь об оптимизации. Циклы, которые являются бесконечными, будут компилировать ошибку/предупреждение, если только это не будет подавлено программистом, и петли, которые являются одинаковыми, каждый раз должны просто пропустить непосредственно, чтобы поставить машину в правильное состояние, без цикла.

Главный случай, конечно, для оптимизации - это итерации статического цикла, когда все вызовы внутри внутри также являются статическими. Определение того, является ли цикл динамическими компонентами достаточно простым, и если он не является динамическим, я предполагаю, что он должен быть статичным. Я не могу понять, как определить, будет ли оно бесконечным или нет. У кого-нибудь есть мысли по этому поводу? Я знаю, что это подмножество проблемы с остановкой, но я считаю, что она разрешима; проблема с остановкой является проблемой из-за того, что для некоторых подмножеств программ вы просто не можете сказать, что она может работать вечно, это может быть не так, но я не хочу рассматривать эти случаи, я просто хочу рассмотреть случаи где он остановится, или он НЕ остановится, но сначала я должен провести различие между тремя состояниями.

Answer 1

Это похоже на своего рода символический решатель, который может быть определен для нескольких классов, но не в целом.

Давайте немного ограничим требования: переполнение номера не должно просто для циклов (хотя иногда оно может быть преобразовано в полный цикл, за исключением случаев, когда используется продолжение и т. Д.), Никаких разрывов, никаких изменений управляющей переменной внутри цикла for ,

for (var i = S; E(i); i = U(i)) ...

где Е (я) и U (я) является выражением, которые могут быть символический манипулируют.Есть несколько классов, которые относительно легко:

U(i) = i + CONSTANT: n -ого цикла значение i является S + n * CONSTANT

U(i) = i * CONSTANT: n -ого цикла значение i является S * CONSTANT^n

U(i) = i/CONSTANT: n -м цикл i is S * CONSTANT^-n

U(i) = (i + CONSTANT) % M: n -ого цикла значение i является (S + n * CONSTANT) % M

и некоторые другие довольно простые комбинации (и некоторые очень трудные)

Определение, заканчивается ли цикл ищет n где E(i(n)) ложно. Это может быть сделано с помощью некоторых символических манипуляций для многих случаев, но в создании решателя много работы.

E.g.

• for(int i = 0; i < 5; i++),
• i(n) = 0 + n * 1 = n, E(i(n)) =>not(n < 5) =>
• n >= 5 => остановки для n = 5

---

• for(int i = 0; i < 5; i--),
• i(n) = 0 + n * -1 = -n, E(i(n)) =>not(-n < 5) =>-n >= 5 =>
• n < -5 - с n является неотрицательное целое число, это никогда не верно - никогда не останавливается

---

• for(int i = 0; i < 5; i = (i + 1) % 3),
• E(i(n)) = >not(n % 3 < 5) =>n % 3 >= 5 => это никогда не бывает => никогда не останавливается

---

• for(int i = 10; i + 10 < 500; i = i + 2 * i) =>
• for(int i = 10; i < 480; i = 3 * i),
• i(n) = 10 * 3^n,
• E(i(n)) =>not(10 * 3^n < 480) =>10 * 3^n >= 480 =>3^n >= 48 =>n >= log3(48) =>n >= 3.5... =>
• так как п цел => он остановится на n = 4

для других случаев, было бы хорошо, если они могут трансформироваться в те, которые вы уже можете решить ...

Многие приемы для символической манипуляции происходят из Лиспа эпохи, и не так уж сложно. Хотя описанные (или варианты) являются наиболее распространенными видами практики, существует много более сложных и/или невозможных для решения сценариев.