Недавно мы переделали наши внутренние инструменты, визуализирующие компиляцию JavaScript и WebAssembly. При работе оптимизирующего компилятора Ion мы теперь можем генерировать интерактивные графы, демонстрирующие, как конкретно обрабатываются и оптимизируются функции.

Вы можете сами поэкспериментировать с этими графами в оригинале статьи. Просто введите какой-нибудь код на JavaScript в функцию test, и наблюдайте за созданием графа. Также там можно щёлкать и перетаскивать граф, менять масштаб при помощи колеса мыши с зажатым Ctrl и перетаскивать ползунок вниз, чтобы изучить процесс оптимизации.

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

Разумеется, мы не первые, кто начал визуализировать внутренние графы компиляторов, и не первые, кто сделал их интерактивными. Но меня не устраивали результаты работы популярных инструментов наподобие Graphviz и Mermaid, поэтому я решил создать алгоритм специально под наши потребности. Получившийся алгоритм прост, быстр, создаёт на удивление высококачественный вывод и его можно реализовать в менее чем тысяче строк кода. В этой статье я объясню алгоритм и конструкторские решения, лежащие в его основе.

Предыстория

Как уже знают читатели нашего блога, у SpiderMonkey есть множество уровней исполнения кода JavaScript и WebAssembly. Самый высокий уровень называется Ion, это оптимизирующий SSA-компилятор, тратящий на компиляцию больше всего времени, но создающий высококачественные результаты.

При работе над Ion нам часто требуется визуализировать и отлаживать граф SSA. Для этой цели мы с 2011 года использовали инструмент под названием iongraph, созданный Шоном Стэнглом. Это простой скрипт на Python, получающий JSON-дамп графов нашего компилятора и использующий Graphviz для создания PDF. Он совершенно адекватен задаче и стал статус-кво для большинства авторов компилятора, но, к сожалению, вывод Graphviz обладает множеством недостатков, из-за которых наша работа становится монотонной и утомительной.

Первый недостаток заключается в том, что вывод Graphviz редко напоминает тот исходный код, на основе которого он сгенерирован. Graphviz размещает узлы там, где, как ему кажется, они минимизируют погрешность, из-за чего граф как будто случайным образом виляет влево и вправо. Он не даёт интуитивного представления, насколько глубоко вложен блок кода, и не упрощает определение того, находятся ли блоки внутри или снаружи циклов. Возьмём для примера следующую функцию и её граф Graphviz:

function foo(n) {
  let result = 0;
  for (let i = 0; i < n; i++) {
    if (!!(i % 2)) {
      result = 0x600DBEEF;
    } else {
      result = 0xBADBEEF;
    }
  }

  return result;
}

Контринтуитивно здесь то, что return идёт до первых двух присвоений в теле цикла. Так как этот граф отражает поток управления JavaScript, мы ожидаем увидеть return в конце. С увеличением размером и сложности графов эта проблема только усугубляется.

Второй связанный с этим недостаток заключается в том, что вывод Graphviz нестабилен. Небольшие изменения во вводе может привести к большим изменениям в выводе. При пролистывании графов каждого прохода Ion узлы скачут влево или вправо, ветви true и false меняются местами, циклы идут справа, а не слева, и так далее. Из-за этого очень сложно понять влияние каждого отдельного этапа. Посмотрите на показанные ниже примеры «до» и «после» и обратите внимание, что второй граф почти, но не полностью, отзеркаливает первый, нес��отря на крайне минимальные изменения в структуре графа:

Все эти недостатки меня не устраивали. Графы потоков управления должны иметь возможность соответствовать структуре программы, на основе которой он сгенерирован. В конечном итоге, граф потока управления обладает множеством ограничений, о которых не могут знать инструменты общего назначения: в них очень мало циклов, и эти циклы чётко определены, потому что создаются на основе циклов программы; кроме того, и JavaScript, и WebAssembly обладают редуцируемым потоком управления, то есть все циклы программы имеют только одну точку входа, и перейти напрямую в середину цикла невозможно. Эту информацию можно использовать в нашу пользу.

К тому же, статический PDF — далеко не идеальное решение при исследовании сложных графов. Нахождение входных данных или точек использования функции становится монотонным и утомительным упражнением, потому что приходится следовать по стрелкам от блока к блоку. Даже приближать и отдалять граф сложно. В итоге я пришёл к выводу, что для преодоления этих ограничений нам просто нужно создать интерактивный инструмент.

Насколько сложной может быть структура?

При попытке создания структуры графов у меня произошёл фальстарт: алгоритм пытался сортировать блоки в вертикальные «дорожки». Это быстро ломало структуру для множества программ, поэтому мне пришлось вернутся на исходные позиции; то есть, на самом деле, к исходникам того самого инструмента, замену которому я хотел создать.

dot (типичный иерархический режим структуры Graphviz) использует алгоритм, называющийся послойным алгоритмом Сугиямы; он взят из статьи 1981 года Сугиямы и коллег. В качестве знакомства с алгоритмом я посмотрел короткую серию лекций, в которой алгоритм Сугиямы разбивался на пять этапов:

1. Разбиение циклов, при котором направление некоторых рёбер изменяется, что приводит к созданию ориентированного ациклического графа.

2. Выравнивание, при котором вершины распределяются по горизонтальным слоям в зависимости от их глубины в графе, а к рёбрам, пересекающим несколько слоёв, добавляются вспомогательные вершины.

3. Минимизация пересечений, при которой порядок вершин в слое изменяется так, чтобы минимизировать пересечение рёбер.

4. Позиционирование вершин, при котором вершины горизонтально позиционируются так, чтобы рёбра были максимально прямыми.

5. Рисование, при котором получившийся граф рендерится на экране.

Эти этапы показались мне на удивление простыми и позволили внедрить в задачу наши собственные знания:

• В нашем случае разбиение циклов будет тривиальной задачей, потому что единственные циклы в наших данных — это программные циклы, а обратные рёбра этих циклов явным образом помечены. При создании структуры графа мы можем просто игнорировать обратные рёбра.

• Процесс выравнивания будет простым и его легко изменить, чтобы граф больше напоминал исходный код. В частности, любые блоки, идущие после цикла в исходном коде, можно искусственно опускать вниз в структуре, устранив сбивающую с толку проблему раннего выхода.

• Перемещение вершин для снижения количества пересечений рёбер — это, на самом деле, плохая идея, потому что наша цель заключается в стабильности между графами. Например, ветви true и false условных конструкций должны всегда находиться в одном порядке, и небольшая доля пересекающихся рёбер — это незначительная цена в обмен на такую стабильность.

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

Все эти упрощения привели к созданию очень простого алгоритма, первоначальная реализация которого заняла всего тысячу строк кода на JavaScript. (В демо можно посмотреть, как она тогда выглядела.) Кроме того, она оказалась очень эффективной, потому что не задействовала самые вычислительно сложные части алгоритма Сугиямы.

iongraph от начала до конца

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

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

Этап 1: создание слоёв

Сначала мы сортируем базовые блоки в горизонтальные дорожки, называемые «слоями». Сделать это очень просто; мы начинаем со слоя 0 и рекурсивно обходим граф, в процессе увеличивая номер уровня. При обходе мы отслеживаем «высоту» каждого цикла, но не в пикселях, а в слоях.

Также мы пользуемся этим для вертикального позиционирования узлов «внутри» и «снаружи» циклов. Если мы видим исходящее из цикла ребро, то откладываем присвоение слоя блоку, в которой оно идёт, пока не завершим присвоение слоёв содержимого цикла, после чего будем знать высоту цикла.

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

Ниже показана анимация работы алгоритма разбиения на слои. Обратите внимание, что последний блок графа посещается дважды, по разу для каждого ответвляющегося в него цикла, и в каждом из случаев присвоение слоя блоку откладывается до присвоения слоёв всему циклу. Окончательная позиция блока находится под обоими циклами, а не под одним из его предшественников, как это было бы в Graphviz. (Помните, что позиции по горизонтали и вертикали ещё не вычислены; для наглядности позиции блоков в этой диаграмме указаны специально.)

function layerBlock(block, layer = 0) {
  // Особая обработка "блоков обратных рёбер"

  // Ранний выход, если блок не будет обновляться
  if (layer <= block.layer) {
    return;
  }

  // Обновляем слой текущего блока
  block.layer = Math.max(block.layer, layer);

  // Обновляем высоты всех циклов, содержащихся в текущем блоке
  let header = block.loopHeader;
  while (header) {
    header.loopHeight = Math.max(header.loopHeight, block.layer - header.layer + 1);
    header = header.parentLoopHeader;
  }

  // Рекурсивно распределяем по слоям последующие элементы
  for (const succ of block.successors) {
    if (succ.loopDepth < block.loopDepth) {
      // Исходящие из текущего цикла рёбра будут распределены по слоям позже
      block.loopHeader.outgoingEdges.push(succ);
    } else {
      layerBlock(succ, layer + 1);
    }
  }

  // Назначаем слои всем исходящим рёбрам только после того,
  // как будет обработано содержимое цикла
  if (block.isLoopHeader()) {
    for (const succ of block.outgoingEdges) {
      layerBlock(succ, layer + block.loopHeight);
    }
  }
}

Этап 2: создание вспомогательных узлов

При каждом пересечении ребра и слоя мы создаём вспомогательный узел. Это позволяет прокладывать рёбра через слои без пересечения с блоками. В отличие от традиционного алгоритма Сугиямы, мы всегда накладываем идущие вниз узлы слева и идущие вверх узлы справа, создавая постоянный поток против часовой стрелки. Кроме того, это упрощает чтение длинных вертикальных рёбер, направление которых в противном случае было бы не совсем понятно. (Посмотрите, как обратное ребро цикла перешло справа налево в показанном выше примере с «нестабильной структурой» Graphviz.)

Кроме того, мы объединяем все рёбра, идущие в одну точку, объединяя их вспомогательные узлы. Это существенно снижает визуальный шум.

Этап 3: спрямление рёбер

Это самый нечёткий и ситуативный этап процесса. По сути, мы выполняем множество небольших проходов, движущихся вверх и вниз по графу и выравнивающих узлы структуры друг с другом. Проходы спрямления рёбер состоят из следующих частей:

• Перемещение узлов вправо от их цикла, чтобы создать «отступ».

• Обход слоя слева направо с перемещением дочерних элементов вправо, чтобы выровнять их с их родителями. Если в результате какие-то узлы накладываются друг на друга, то они перемещаются ещё дальше вправо.

• Обход слоя справа налево, перемещение родителей вправо, чтобы выровнять с их дочерними элементами. Эта версия более консервативна, она не перемещает узел, если он наложится на другой. Благодаря этому устраняется большинство проблем из первого этапа.

• Спрямление последовательностей вспомогательных узлов, чтобы получались чёткие вертикальные линии.

• «Притягивание» последовательностей вспомогательных узлов в левую сторону графа, если места для их перемещения вправо нет.

• Спрямление всех «почти прямых» рёбер согласно выбранному пороговому значению. Благодаря этому граф выглядит менее волнистым. Этот этап выполняется многократным «расчёсыванием» графа вверх и вниз, выравниванием родителей с дочерними элементами, затем дочерних элементов с родителями и так далее.

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

Мы не достигаем этой стратегией какой-то конечной точки и не стремимся к этому. Я выяснил, что если продолжать многократно применять эти проходы, то узлы бесконечно будут смещаться вправо. Поэтому проходы создания структуры настроены вручную, обеспечивая вполне приемлемые результаты для графов, с которыми мы обычно работаем. Тем не менее, систему определённо можно улучшить, особенно в случае больших графов, которым идёт на пользу увеличение количества итераций.

В конце этого этапа все узлы имеют фиксированную координату X и в дальнейшем не изменяются.

Этап 4: прокладывание горизонтальных рёбер

При горизонтальном прохождении между слоями рёбра могут пересекаться. Для устранения этой проблемы мы сортируем рёбра на параллельные «дорожки», давая каждой ��з них смещение по вертикали. После прокладывания всех рёбер мы записываем общую высоту дорожек и храним их в предыдущем слое, как его «высоту дорожки». Это позволяет нам оставить место под рёбра на последнем этапе создания структуры.

Сначала мы сортируем рёбра по их начальной позиции, слева направо. Так создаётся постоянная структура рёбер, на практике имеющая небольшое количество вертикальных пересечений. Затем рёбра распределяются по дорожкам по принципу «снаружи внутрь», с расположением идущих вправо рёбер наверху, а идущих влево — снизу и с созданием новой дорожки, если ребро наложится или пересечётся с каким-то другим ребром.

Показанная ниже диаграмма в оригинале статьи интерактивна, можете нажимать на блоки и перетаскивать их, чтобы посмотреть, как горизонтальные рёбра распределяются по дорожкам.

function trackHorizontalEdges(layer) {
  const TRACK_SPACING = 20;

  // Собираем все рёбра в слое и сортируем слева направо по координате начала
  const layerEdges = [];
  for (const node of layer.nodes) {
    for (const edge of node.edges) {
      layerEdges.push(edge);
    }
  }
  layerEdges.sort((a, b) => a.startX - b.startX);

  // Распределяем рёбра по "дорожкам" на основании того, накладываются ли они друг на друга горизонтально
  // Обходим дорожки снаружи внутрь и останавливаемся,
  // если произойдёт наложение на какое-то другое ребро.
  const rightwardTracks = []; // [][]Edge
  const leftwardTracks = [];  // [][]Edge
  nextEdge:
  for (const edge of layerEdges) {
    const trackSet = edge.endX - edge.startX >= 0 ? rightwardTracks : leftwardTracks;
    let lastValidTrack = null; // []Edge | null

    // Итеративно обходим дорожки в обратном порядке (снаружи внутрь)
    for (let i = trackSet.length - 1; i >= 0; i--) {
      const track = trackSet[i];
      let overlapsWithAnyInThisTrack = false;
      for (const otherEdge of track) {
        if (edge.dst === otherEdge.dst) {
          // Присваиваем ребро этой дорожке, чтобы объединить стрелки
          track.push(edge);
          continue nextEdge;
        }

        const al = Math.min(edge.startX, edge.endX);
        const ar = Math.max(edge.startX, edge.endX);
        const bl = Math.min(otherEdge.startX, otherEdge.endX);
        const br = Math.max(otherEdge.startX, otherEdge.endX);
        const overlaps = ar >= bl && al <= br;
        if (overlaps) {
          overlapsWithAnyInThisTrack = true;
          break;
        }
      }

      if (overlapsWithAnyInThisTrack) {
        break;
      } else {
        lastValidTrack = track;
      }
    }

    if (lastValidTrack) {
      lastValidTrack.push(edge);
    } else {
      trackSet.push([edge]);
    }
  }

  // На основании информации дорожки применяем к каждому ребру смещения для рендеринга.
  const tracksHeight = TRACK_SPACING * Math.max(
    0,
    rightwardTracks.length + leftwardTracks.length - 1,
  );
  let trackOffset = -tracksHeight / 2;
  for (const track of [...rightwardTracks.toReversed(), ...leftwardTracks]) {
    for (const edge of track) {
      edge.offset = trackOffset;
    }
    trackOffset += TRACK_SPACING;
  }
}

Этап 5: вертикальное размещение

Наконец, мы назначаем каждому узлу координату Y. Начиная с нулевой координаты Y, мы итеративно обходим слои, многократно прибавляя высоту слоя и высоту его дорожки; высота слоя — это максимальная высота узла в слое. Все узлы в пределах слоя получают одинаковую координату Y; это более простое и удобочитаемое решение, чем используемое по умолчанию в Graphviz вертикальное центрирование узлов внутри слоя.

Теперь, когда у каждого узла есть координаты X и Y, процесс создания структуры завершён.

function verticalize(layers) {
  let layerY = 0;
  for (const layer of layers) {
    let layerHeight = 0;
    for (const node of layer.nodes) {
      node.y = layerY;
      layerHeight = Math.max(layerHeight, node.height);
    }
    layerY += layerHeight;
    layerY += layer.trackHeight;
  }
}

Этап 6: рендеринг

В этой статье мы не будем рассматривать подробности рендеринга, однако мне хотелось бы рассказать о стилистическом решении, повышающем читаемость наших графов.

При рендеринге рёбер мы используем стиль, позаимствованный у синтаксических диаграмм. У них есть множество преимуществ по сравнению с кривыми Безье, используемыми в Graphviz. Во-первых, прямые линии кажутся более упорядоченными и удобными для отслеживания при скроллинге вверх и вниз. Во-вторых, их легко прокладывать (они вертикальные при пересечении слоёв, горизонтальные между слоями). В-третьих, их легко объединять, когда они имеют одну общую конечную точку, а точки соединений чётко показывают направление ребра. В-четвёртых, они всегда пересекаются под прямыми углами, что повышает понятность и изначально снижает потребность в устранении пересечений рёбер.

Рассмотрим следующий пример. Здесь есть множество пересечений рёбер, которые обычно считаются нежелательными, однако рёбра и их направления остаются понятными. В частности, стоит отметить отмеченное красным вертикальное соединение слева: оно не просто даёт сразу понять, что у рёбер одна конечная точка, но и само соединение показывает, что рёбра направлены вниз. Мне кажется, это намного красивее и удобнее, чем «мешанина проводов», которую обычно генерирует Graphviz.

Почему это всё же работает?

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

Большинство алгоритмов генерации графов — это задачи оптимизации, в которых по каким-то выбранным метрикам минимизируются погрешности. Однако, на практике, эти метрики, похоже, плохо коррелируют с читаемостью. Например, в теории, кажется правильным изменять порядок узлов для минимизации пересечения рёбер. Однако предсказуемый порядок узлов приводит к более разумному результату, а простых правил прокладки рёбер оказывается достаточно для создания аккуратной структуры. (Плюс они обеспечивают стабильность структуры между проходами.) Аналогично, правила типа «выравнивание родителей с дочерними элементами» приводят к созданию более читаемых результатов, чем «минимизация длин рёбер».

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

Наконец, получившийся алгоритм просто более эффективен. Все проходы генерации структуры в iongraph легко запрограммировать и удобно масштабировать до больших графов, потому что они выполняются примерно за линейное время. На мой взгляд, лучше выполнить фиксированное количество итераций структуры согласно сложности графа и бюджету времени, чем ждать, пока сложный солвер ограничений решит задачу «полностью».

Благодаря этой философии можно ориентироваться даже в самых плохих графах. Ниже показан скриншот скомпилированной в WebAssembly и отрендеренной при помощи старого инструмента функции zlib.

Чтобы сгенерировать это кошмарное спагетти, Graphviz понадобилось примерно десять минут. Для сравнения: iongraph может справиться со структурой этой функции за 20 миллисекунд. Получившийся результат не особо красив, зато рендерится в тысячи раз быстрее и в нём гораздо проще ориентироваться.

Наверно, программистам следует меньше доверять волшебным оптимизирующим системам, особенно если результат должен быть человекочитаемым. При благоразумном использовании простые (и глупые алгоритмы) могут быть очень эффективными.

Работа на будущее

Мы уже интегрировали iongraph в профилировщик Firefox, благодаря чему можно легко просматривать графы самых затратных и важных функций, влияющих на производительность. К с��жалению, он доступен только в отдельных сборках оболочки SpiderMonkey и отсутствует в полных сборках браузерах. Это вызвано архитектурными различиями захвата данных профилирования и флагов, с которыми собираются браузер и оболочка. Мне бы хотелось, чтобы однажды пользователи Firefox смогли сами просматривать эти графы, но пока у нас нет планов по внедрению их в браузер. Вы можете отслеживать работы по багтрекингу.

Мы собираемся продолжать время от времени дополнять iongraph фичами, которые помогут нам в работе. У нас накопилось много идей будущих фич, в том числе расширение возможностей навигации, поиск и визуализация информации распределения регистров, однако нет конкретной дорожной карты по выпуску этих фич.

Чтобы поэкспериментировать с iongraph локально, вы можете запустить отладочную сборку оболочки SpiderMonkey с флагом IONFLAGS=logs; при этом будет выполнен дамп в /tmp/ion.json. Этот файл затем можно будет загрузить в автономный iongraph. Учтите, что в текущем состоянии инструмент довольно неудобен для пользователя.

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