FAQ
Hello there,

I was wondering if there is some documentation on the implementation of the
SSA backend, which could help stepping into the code.

Furthermore it would be nice to have something at hand to better understand
the rewrite rules.
For example, how do I match a non-constant bool, or is there no special
representation for a boolean value?
How would I express the following rule?
(And8 (Not Bool[a]) Bool[b]) -> (Less8U a b)
Which should optimize
a, b :=randomBool(), randomBool()
c := !a && b
to
c := uint8(a) < uint8(b)
assuming bools are implemented using uint8.

Best,
  Marvin

--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

  • Keith Randall at Mar 28, 2016 at 3:25 pm

    On Mon, Mar 28, 2016 at 7:05 AM, Marvin Stenger wrote:

    Hello there,

    I was wondering if there is some documentation on the implementation of
    the SSA backend, which could help stepping into the code.
    Not a whole lot. The original proposal doc is at
    https://docs.google.com/document/d/1szwabPJJc4J-igUZU4ZKprOrNRNJug2JPD8OYi3i1K0/edit?usp=sharing

    Furthermore it would be nice to have something at hand to better
    understand the rewrite rules.
    For example, how do I match a non-constant bool, or is there no special
    representation for a boolean value?
    How would I express the following rule?
    (And8 (Not Bool[a]) Bool[b]) -> (Less8U a b)
    Which should optimize
    a, b :=randomBool(), randomBool()
    c := !a && b
    to
    c := uint8(a) < uint8(b)
    assuming bools are implemented using uint8.
    There is no special representation for a bool, it is a Value like any
    other. You can use the type to distinguish it if you need to, but (in
    generic ops at least) the opcodes will distinguish it.
    There is no "and" for booleans. && is a shortcutting operation, so it
    compiles to multiple basic blocks. c := !a && b compiles to something like

    b1:
         x = (Not a)
         if x goto b2 else b4
    b2:
         if b goto b3 else b4
    b3:
         c1 = (ConstBool [1])
         goto b5
    b4:
        c1 = (ConstBool [0])
        goto b5
    b5:
        c = (Phi c1 c2)

    This pattern would be hard to match with rewrite rules. Some passes do it
    with code, see shortcircuit for an example.
    Generating boolean variables from other booleans is fairly uncommon. Much
    more common is "if !a && b { ... }", so if you're going to rewrite &&
    constructs make sure you don't pessimize that pattern.

    Best,
    Marvin

    --
    You received this message because you are subscribed to the Google Groups
    "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Marvin Stenger at Mar 28, 2016 at 3:42 pm
    Thanks for the info.

    Marvin

    Am Montag, 28. März 2016 17:25:42 UTC+2 schrieb Keith Randall:


    On Mon, Mar 28, 2016 at 7:05 AM, Marvin Stenger <marvin.s...@gmail.com
    <javascript:>> wrote:
    Hello there,

    I was wondering if there is some documentation on the implementation of
    the SSA backend, which could help stepping into the code.
    Not a whole lot. The original proposal doc is at
    https://docs.google.com/document/d/1szwabPJJc4J-igUZU4ZKprOrNRNJug2JPD8OYi3i1K0/edit?usp=sharing

    Furthermore it would be nice to have something at hand to better
    understand the rewrite rules.
    For example, how do I match a non-constant bool, or is there no special
    representation for a boolean value?
    How would I express the following rule?
    (And8 (Not Bool[a]) Bool[b]) -> (Less8U a b)
    Which should optimize
    a, b :=randomBool(), randomBool()
    c := !a && b
    to
    c := uint8(a) < uint8(b)
    assuming bools are implemented using uint8.
    There is no special representation for a bool, it is a Value like any
    other. You can use the type to distinguish it if you need to, but (in
    generic ops at least) the opcodes will distinguish it.
    There is no "and" for booleans. && is a shortcutting operation, so it
    compiles to multiple basic blocks. c := !a && b compiles to something like

    b1:
    x = (Not a)
    if x goto b2 else b4
    b2:
    if b goto b3 else b4
    b3:
    c1 = (ConstBool [1])
    goto b5
    b4:
    c1 = (ConstBool [0])
    goto b5
    b5:
    c = (Phi c1 c2)

    This pattern would be hard to match with rewrite rules. Some passes do it
    with code, see shortcircuit for an example.
    Generating boolean variables from other booleans is fairly uncommon. Much
    more common is "if !a && b { ... }", so if you're going to rewrite &&
    constructs make sure you don't pessimize that pattern.

    Best,
    Marvin

    --
    You received this message because you are subscribed to the Google Groups
    "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-dev+...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Alexandru Moșoi at Mar 29, 2016 at 3:10 pm
    I wanted to do this in the phiopt pass at some point but I was not sure
    what values can a boolean take. Is it 0 and not-0, or 0 and 1? If the
    later, it's relatively easy to do.

    So, is v17 = Arg <bool> {b} [0] guaranteed to be 0 or 1 always?

    luni, 28 martie 2016, 17:25:42 UTC+2, Keith Randall a scris:


    On Mon, Mar 28, 2016 at 7:05 AM, Marvin Stenger <marvin.s...@gmail.com
    <javascript:>> wrote:
    Hello there,

    I was wondering if there is some documentation on the implementation of
    the SSA backend, which could help stepping into the code.
    Not a whole lot. The original proposal doc is at
    https://docs.google.com/document/d/1szwabPJJc4J-igUZU4ZKprOrNRNJug2JPD8OYi3i1K0/edit?usp=sharing

    Furthermore it would be nice to have something at hand to better
    understand the rewrite rules.
    For example, how do I match a non-constant bool, or is there no special
    representation for a boolean value?
    How would I express the following rule?
    (And8 (Not Bool[a]) Bool[b]) -> (Less8U a b)
    Which should optimize
    a, b :=randomBool(), randomBool()
    c := !a && b
    to
    c := uint8(a) < uint8(b)
    assuming bools are implemented using uint8.
    There is no special representation for a bool, it is a Value like any
    other. You can use the type to distinguish it if you need to, but (in
    generic ops at least) the opcodes will distinguish it.
    There is no "and" for booleans. && is a shortcutting operation, so it
    compiles to multiple basic blocks. c := !a && b compiles to something like

    b1:
    x = (Not a)
    if x goto b2 else b4
    b2:
    if b goto b3 else b4
    b3:
    c1 = (ConstBool [1])
    goto b5
    b4:
    c1 = (ConstBool [0])
    goto b5
    b5:
    c = (Phi c1 c2)

    This pattern would be hard to match with rewrite rules. Some passes do it
    with code, see shortcircuit for an example.
    Generating boolean variables from other booleans is fairly uncommon. Much
    more common is "if !a && b { ... }", so if you're going to rewrite &&
    constructs make sure you don't pessimize that pattern.

    Best,
    Marvin

    --
    You received this message because you are subscribed to the Google Groups
    "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-dev+...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Keith Randall at Mar 29, 2016 at 3:23 pm
    ConstBool should have 0 or 1 in AuxInt.
    Generic bool-typed values are "true" or "false", there's no notion of how
    they are represented.
    AMD64 represents bools with a byte, either 0 or 1.
    In a register, the higher bits (8-63) of the register holding a bool are
    undefined.

    See cmd/compile/internal/ssa/gen/{generic,AMD64}Ops.go for the description
    of the ops in question. If we don't have adequate comments there, we
    should fix that.
    On Tue, Mar 29, 2016 at 8:10 AM, Alexandru Moșoi wrote:

    I wanted to do this in the phiopt pass at some point but I was not sure
    what values can a boolean take. Is it 0 and not-0, or 0 and 1? If the
    later, it's relatively easy to do.

    So, is v17 = Arg <bool> {b} [0] guaranteed to be 0 or 1 always?

    luni, 28 martie 2016, 17:25:42 UTC+2, Keith Randall a scris:


    On Mon, Mar 28, 2016 at 7:05 AM, Marvin Stenger <marvin.s...@gmail.com>
    wrote:
    Hello there,

    I was wondering if there is some documentation on the implementation of
    the SSA backend, which could help stepping into the code.
    Not a whole lot. The original proposal doc is at
    https://docs.google.com/document/d/1szwabPJJc4J-igUZU4ZKprOrNRNJug2JPD8OYi3i1K0/edit?usp=sharing

    Furthermore it would be nice to have something at hand to better
    understand the rewrite rules.
    For example, how do I match a non-constant bool, or is there no special
    representation for a boolean value?
    How would I express the following rule?
    (And8 (Not Bool[a]) Bool[b]) -> (Less8U a b)
    Which should optimize
    a, b :=randomBool(), randomBool()
    c := !a && b
    to
    c := uint8(a) < uint8(b)
    assuming bools are implemented using uint8.
    There is no special representation for a bool, it is a Value like any
    other. You can use the type to distinguish it if you need to, but (in
    generic ops at least) the opcodes will distinguish it.
    There is no "and" for booleans. && is a shortcutting operation, so it
    compiles to multiple basic blocks. c := !a && b compiles to something like

    b1:
    x = (Not a)
    if x goto b2 else b4
    b2:
    if b goto b3 else b4
    b3:
    c1 = (ConstBool [1])
    goto b5
    b4:
    c1 = (ConstBool [0])
    goto b5
    b5:
    c = (Phi c1 c2)

    This pattern would be hard to match with rewrite rules. Some passes do
    it with code, see shortcircuit for an example.
    Generating boolean variables from other booleans is fairly uncommon.
    Much more common is "if !a && b { ... }", so if you're going to rewrite &&
    constructs make sure you don't pessimize that pattern.

    Best,
    Marvin

    --
    You received this message because you are subscribed to the Google
    Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send
    an email to golang-dev+...@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Marvin Stenger at Mar 29, 2016 at 3:30 pm
    I guess the problem is, that there are no CPU instructions for booleans.
    These are just a concept of go as a higher level language, and therefore
    depend on the implementation of the compiler.
    The translation of abstractions, as booleans, to something the CPU can work
    with should be documented, especially if we can make use of certain
    invariants for further optimization.

    Am Dienstag, 29. März 2016 17:23:07 UTC+2 schrieb Keith Randall:
    ConstBool should have 0 or 1 in AuxInt.
    Generic bool-typed values are "true" or "false", there's no notion of how
    they are represented.
    AMD64 represents bools with a byte, either 0 or 1.
    In a register, the higher bits (8-63) of the register holding a bool are
    undefined.

    See cmd/compile/internal/ssa/gen/{generic,AMD64}Ops.go for the description
    of the ops in question. If we don't have adequate comments there, we
    should fix that.

    On Tue, Mar 29, 2016 at 8:10 AM, Alexandru Moșoi <alex...@mosoi.ro
    <javascript:>> wrote:
    I wanted to do this in the phiopt pass at some point but I was not sure
    what values can a boolean take. Is it 0 and not-0, or 0 and 1? If the
    later, it's relatively easy to do.

    So, is v17 = Arg <bool> {b} [0] guaranteed to be 0 or 1 always?

    luni, 28 martie 2016, 17:25:42 UTC+2, Keith Randall a scris:


    On Mon, Mar 28, 2016 at 7:05 AM, Marvin Stenger <marvin.s...@gmail.com>
    wrote:
    Hello there,

    I was wondering if there is some documentation on the implementation of
    the SSA backend, which could help stepping into the code.
    Not a whole lot. The original proposal doc is at
    https://docs.google.com/document/d/1szwabPJJc4J-igUZU4ZKprOrNRNJug2JPD8OYi3i1K0/edit?usp=sharing

    Furthermore it would be nice to have something at hand to better
    understand the rewrite rules.
    For example, how do I match a non-constant bool, or is there no special
    representation for a boolean value?
    How would I express the following rule?
    (And8 (Not Bool[a]) Bool[b]) -> (Less8U a b)
    Which should optimize
    a, b :=randomBool(), randomBool()
    c := !a && b
    to
    c := uint8(a) < uint8(b)
    assuming bools are implemented using uint8.
    There is no special representation for a bool, it is a Value like any
    other. You can use the type to distinguish it if you need to, but (in
    generic ops at least) the opcodes will distinguish it.
    There is no "and" for booleans. && is a shortcutting operation, so it
    compiles to multiple basic blocks. c := !a && b compiles to something like

    b1:
    x = (Not a)
    if x goto b2 else b4
    b2:
    if b goto b3 else b4
    b3:
    c1 = (ConstBool [1])
    goto b5
    b4:
    c1 = (ConstBool [0])
    goto b5
    b5:
    c = (Phi c1 c2)

    This pattern would be hard to match with rewrite rules. Some passes do
    it with code, see shortcircuit for an example.
    Generating boolean variables from other booleans is fairly uncommon.
    Much more common is "if !a && b { ... }", so if you're going to rewrite &&
    constructs make sure you don't pessimize that pattern.

    Best,
    Marvin

    --
    You received this message because you are subscribed to the Google
    Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send
    an email to golang-dev+...@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-dev+...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-dev @
categoriesgo
postedMar 28, '16 at 2:05p
activeMar 29, '16 at 3:30p
posts6
users3
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase