Ah, I think I was miss-reading the Arm64 instructions: Arm64CompareAndBranch is cbz (?) so the control-flow would work out... Too many levels of conditionals for me! On Thursday, July 27, 2023 at 11:34:02 AM UTC+1 Sam Parker-Haynes wrote:
> 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/0311de9a-2b21-4def-b8d7-d18c75915624n%40googlegroups.com.