If I'm reading the IR correctly, the branch has already been rewritten to directly use #26, so I'm not expecting there to be two comparisons. The branch targets are the same, but the condition is being inverted (again) during ISel. I think the IR should be translated to this: v7(R) = Arm64Cmp32 && branch if equal v0(R) #50 [rpo_immediate:7] [rpo_immediate:6]
And many thanks for the pipeline overview! I will continue playing. On Thursday, July 27, 2023 at 9:52:27 AM UTC+1 Nico Hartmann wrote: > 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.p...@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-...@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/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 | 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/6a480cb5-3e5f-4b02-aaae-af67ea02f53dn%40googlegroups.com.