Hi Sam, Briefly summarized, the Turboshaft pipeline is organized into phases where each phase is defined by a stack of reducers (e.g. `OptimizationPhase<SomeReducer, SomeOtherReducer, AnotherReducer>::Run()`). A Turboshaft graph is passed to each phase (the "input graph") and the phase then iterates over the graph and passes each operation through the stack. At the bottom of the stack, a new operation (or a sequence of operations) is generated into the phase's output (the "output graph"). The output graph is then the next phase's input. However, some phases run analyses. Those always process the phase's input graph regardless of where they are in the stack. The `DeadCodeEliminationReducer` is one of these that runs an analysis on the input graph and then skips emitting dead operations during reduction. As a result, operations that became dead during a previous reduction in the same phase (reducer stack), will not be removed.
There are two ways to get rid of unused operations: - When a phase iterates over the input graph, all operations that don't have uses are just skipped. So once an operation that doesn't have any uses is emitted into the output graph, it will be removed (or rather ignored when generating the next graph) at the beginning of the next phase. - Using the `DeadCodeEliminationReducer`, which is a more powerful liveness analysis that can do much more. It will run a full fixpoint analysis on the input graph to find all live operations to remove all dead operations in one step. It will also eliminate unnecessary control flow by rewriting BranchOp and GotoOp targets and it will rewrite PhiOps and such. If you want to make use of this, it has to be in the following phase, because - as described above - it always runs on the phase's input graph. However, this is a more expensive analysis+reducer, so I would not recommend using it for the example you provided above but just rely on the next OptimizationPhase run to remove the unused operations. Regarding the ISel, I think the generated code looks okay. `v7(R) = ...` is the comparison of `v0` with `50` (so that's basically `26: Word32Equal(4, 25)`) and then we branch based on this result. Please clarify what you think is wrong here. Nico On Wed, Jul 26, 2023 at 12:35 PM Sam Parker-Haynes <sam.par...@arm.com> wrote: > Hi Nico, > > I've been having a poke around using a toy wasm example. I'm trying to > understand how the wasm optimization pipeline works. I have this basic > block: > > BLOCK B7 <- B4 > > 26: Constant()[word32: 50] > > 27: Equal(#3, #26)[Word32] > > 28: Constant()[word32: 0] > > 29: Equal(#27, #28)[Word32] > > 30: Branch(#29)[B10, B8, None] > > And I can see that MachineOptimizationReducer changes the branch (29) > condition, but it doesn't remove (28) and (27): > > BLOCK B6 <- B4 > 25: Constant()[word32: 50] > 26: Equal(#3, #25)[Word32] > 27: Constant()[word32: 0] > 28: Equal(#26, #27)[Word32] > 29: Branch(#26)[B7, B8, None] > > I've tried adding DeadCodeElimination, but it always seems to run *before* > MachineOptimizationReducer, > how can I get it to run afterwards? > > What I find somewhat worrying is that this IR is lowered to equivalent > looking Turbofan IR but then ISel appears to be using Word32Equal (28) as > the branch condition again: > > --- BLOCK B5 id7 <- B4 --- > 24: IfFalse(22) > 25: Int32Constant[50] > 26: Word32Equal(4, 25) > 27: Int32Constant[0] > 28: Word32Equal(26, 27) > 29: Branch[Unspecified, None](26) -> B7, B6 > > B5: AO#4 (no frame) instructions: [11, 13) > predecessors: B4 > 11: gap () () > v7(R) = Arm64Cmp32 && set if equal v0(R) #50 > 12: gap () () > Arm64CompareAndBranch32 && branch if not equal v7(R) > [rpo_immediate:7] [rpo_immediate:6] > > Any idea of what's going here? > > cheers! > On Tuesday, July 25, 2023 at 10:53:01 AM UTC+1 Sam Parker-Haynes wrote: > >> Great, thanks for the info, I'll take a look around. >> >> On Tuesday, July 25, 2023 at 10:47:07 AM UTC+1 Nico Hartmann wrote: >> >>> There is not a lot of (up to date) documentation. A very brief summary: >>> >>> The new IR's operations (which replace Turbofan's nodes) are defined in >>> turboshaft/operations.h >>> <https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/operations.h> >>> . >>> The current state of the pipeline is as follows: We run >>> Turbofan's frontend and then translate to the Turboshaft IR (in >>> turboshaft/graph-builder.cc >>> <https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/graph-builder.cc>). >>> Next, the Turboshaft optimization and lowering phases run on the CFG (see >>> primarily pipeline.cc >>> <https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/pipeline.cc> >>> and >>> the turboshaft/*-phase.h included from there). Eventually, we translate the >>> CFG back into Turbofan's sea-of-nodes IR (in >>> turboshaft/recreate-schedule.cc >>> <https://source.chromium.org/chromium/chromium/src/+/main:v8/src/compiler/turboshaft/recreate-schedule.cc>) >>> to run the backend. >>> >>> We are currently working on reimplementing the rest of Turbofan's phases >>> to have a full Turboshaft CFG pipeline eventually, but we plan to ship a >>> first version of Turboshaft soonish, which still only covers part of the >>> pipeline and relies on the translation back and forth. >>> >>> On Tue, Jul 25, 2023 at 11:05 AM Sam Parker-Haynes <sam.p...@arm.com> >>> wrote: >>> >>>> Hi Nico, >>>> >>>> A CFG IR sounds good to me :) I've been hesitate to look as I didn't >>>> know the status, is there any documentation? Is it currently piggybacking >>>> off turbofan for some functionality? I can't immediately see where/how >>>> graph nodes are defined. >>>> >>>> cheers, >>>> >>>> On Tuesday, July 25, 2023 at 9:37:26 AM UTC+1 Nico Hartmann wrote: >>>> >>>>> Hi Sam, >>>>> >>>>> We are currently migrating Turbofan to a new CFG-based IR >>>>> (Turboshaft). This could help. >>>>> >>>>> Cheers, >>>>> Nico >>>>> >>>>> On Tue, Jul 25, 2023 at 10:23 AM Sam Parker-Haynes <sam.p...@arm.com> >>>>> wrote: >>>>> >>>>>> Hi, >>>>>> >>>>>> I've been wondering how to go about adding general support for >>>>>> conditional operations in Turbofan, specifically conditional compares for >>>>>> AArch64. But I now see that Intel APX extensions also support more >>>>>> conditional instructions, beyond cmov. >>>>>> >>>>>> I'm not a huge fan of flag continuations, as it's been too easy for >>>>>> me to introduce bugs while using them, so is there a safer way to >>>>>> approach >>>>>> this? >>>>>> >>>>>> Machine-level predication would seem to require a CFG in a form that >>>>>> isn't really available until during/after jump-threading. So a few >>>>>> questions about jump threading: >>>>>> - Could predication happen there? >>>>>> - Why does jump threading run so late, why not before regalloc? >>>>>> >>>>>> And, in general, what is the policy on having optimisation passes >>>>>> that run on machine code? >>>>>> >>>>>> Thanks, >>>>>> Sam >>>>>> >>>>>> -- >>>>>> -- >>>>>> v8-dev mailing list >>>>>> v8-...@googlegroups.com >>>>>> http://groups.google.com/group/v8-dev >>>>>> --- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "v8-dev" group. >>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>> send an email to v8-dev+un...@googlegroups.com. >>>>>> To view this discussion on the web visit >>>>>> https://groups.google.com/d/msgid/v8-dev/80169017-f248-4424-89ad-97260f28643dn%40googlegroups.com >>>>>> <https://groups.google.com/d/msgid/v8-dev/80169017-f248-4424-89ad-97260f28643dn%40googlegroups.com?utm_medium=email&utm_source=footer> >>>>>> . >>>>>> >>>>> >>>>> >>>>> -- >>>>> Nico Hartmann | Software Engineer | nicoha...@google.com | Chrome - V8 >>>>> >>>> -- >>>> -- >>>> v8-dev mailing list >>>> v8-...@googlegroups.com >>>> http://groups.google.com/group/v8-dev >>>> --- >>>> You received this message because you are subscribed to the Google >>>> Groups "v8-dev" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to v8-dev+un...@googlegroups.com. >>>> >>> To view this discussion on the web visit >>>> https://groups.google.com/d/msgid/v8-dev/f4cb3d5e-d703-4e0a-b65d-1fbacf1573a0n%40googlegroups.com >>>> <https://groups.google.com/d/msgid/v8-dev/f4cb3d5e-d703-4e0a-b65d-1fbacf1573a0n%40googlegroups.com?utm_medium=email&utm_source=footer> >>>> . >>>> >>> >>> >>> -- >>> Nico Hartmann | Software Engineer | nicoha...@google.com | Chrome - V8 >>> >> -- > -- > v8-dev mailing list > v8-dev@googlegroups.com > http://groups.google.com/group/v8-dev > --- > You received this message because you are subscribed to the Google Groups > "v8-dev" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to v8-dev+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/v8-dev/87824ff9-a7a0-4a22-b69b-44e686d07f1an%40googlegroups.com > <https://groups.google.com/d/msgid/v8-dev/87824ff9-a7a0-4a22-b69b-44e686d07f1an%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- Nico Hartmann | Software Engineer | nicohartm...@google.com | Chrome - V8 -- -- v8-dev mailing list v8-dev@googlegroups.com http://groups.google.com/group/v8-dev --- You received this message because you are subscribed to the Google Groups "v8-dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to v8-dev+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/CAHNjccKpcX0WGC6pTA2Op2Tpaq7UMuAWaPR1bNw1XfQ5HEbNAQ%40mail.gmail.com.
