Оптимальное упорядочение деревьев

Оптимальное упорядочение деревьев (Optimal ordering for trees) — Существует простой алгоритм определения оптимального порядка, в котором следует осуществлять вычисления, образующие линейный участок программы для случая, когда они представлены в виде дерева. Оптимальность здесь понимается в том смысле, что порядок задает самую короткую последовательность команд машины из всех возможных для данного дерева.

Алгоритм состоит из двух частей. Первая помечает каждую вершину дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для вычисления поддерева с данным корнем при условии, что не делается запоминаний промежуточных результатов. Вторая часть — это обход дерева, порядок которого управляется вычисленными метками вершин. Выходной код генерируется во время указанного обхода дерева. Содержательно алгоритм, обрабатывая два операнда бинарной операции, сначала работает над вычислением того из них, который требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым.

В общем случае, когда луч может содержать общие подвыражения и представляется дэгом, задача генерации кода существенно усложняется: задачи оптимальной генерации кода по дэгу для одноадресной машины, а также для машины с неограниченным числом регистров являются [math]\displaystyle{ \mathcal NP }[/math]-Полными.

Литература

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.