What's the difference between REDUCE(operation) and REDUCE_INPUT_GRAPH(operation) in turboshaft?

[Jianxiao Lu]

Hi everyone,

I am working on adding a new phase in turboshaft, but I can't understand the difference between REDUCE(operation) and  REDUCE_INPUT_GRAPH(operation) and can't make sure which one to use.  Do you have any suggestions?

Thanks!

[dmerc...@google.com]

Hi,

First: a Turboshaft phase that uses OptimizationPhase creates a copy of the graph. The old graph is referred to as input_graph and the newly created graph is the output_graph. This works by reducing each operation one by one (where each reduction creates a new operation in the output_graph), always reducing the inputs before their uses.

REDUCE_INPUT_GRAPH takes as argument the Operation and OpIndex from the input_graph. This is usually used for reducers that analyse the graph beforehand, since a common way to store the result of an analysis is a map OpIndex->Data (we usually use an OpIndexSideTable for this (https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/sidetable.h;l=183;drc=3509554952d382190091b85b2331da874e026a21)). An example is StoreStoreElimination (https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/store-store-elimination-reducer.h), which analyses the input_graph to figure out which stores can be removed, and has a ZoneSet<OpIndex> containing the stores that can be removed (see https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/store-store-elimination-reducer.h;l=381-386;drc=fa7521ef3eb6c69fa398809e7ce4a869c94661fa).

REDUCE takes as argument the already lowered arguments of the operation (the same arguments as the constructor). This means that the OpIndex arguments of REDUCE belong to the output_graph rather than the input_graph. This is typically useful when a lowering/reduction is only based on what the inputs of the operation are, but not on information further away down the graph. For instance, MachineLoweringReducer (https://crsrc.org/c/v8/src/compiler/turboshaft/machine-lowering-reducer-inl.h) lowers Simplified operations to Machine operations, which doesn't require any knowledge beyond the inputs of each operation, and thus uses REDUCE methods.

REDUCE methods can't easily look down the graph, because their inputs belong to the output_graph, but next operations of the input_graph haven't been lowered yet, so they don't appear in the output_graph yet.

There are some exceptions, and in particular BranchEliminationReducer uses REDUCE method, but still looks ahead in the input_graph (see its REDUCE(Goto) method for instance https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/branch-elimination-reducer.h;l=290-363;drc=b8997b5668474283e3ecbcf6dcc6538565ef2cc5), but this is a special case: BranchElimination needs to know both what an operation was reduced to, and what comes next in the graph. 

FYI, the link between REDUCE_INPUT_GRAPH and REDUCE is done in ReducerBaseForwarder  (https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/assembler.h;l=654;drc=1753b83910819bce453d453b054e9f5b4924bbf8), which calls AssembleOutputGraphXXX from optimization-phase.h (for instance, see AssembleOutputGraphWordBinop: https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/optimization-phase.h;l=948-949;drc=2054c8f629321b0789f72e751c3813aec6539008), which maps the OpIndex inputs to the new graph and calls ReduceXXX. 

I hope that helps, let us know if you have other questions or need more details. Also, feel free to let us know what optimization/reducer/lowering you're trying to implement, so that we can give a more focused reply :)

Cheers,

Darius

[Jianxiao Lu]

Thanks Darius for the such a detailed explanation!