Ternary operator and memory access

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • Ancient_Hacker

    #16
    Re: Ternary operator and memory access


    Eric Sosman wrote:

    Unfortunately, there's a huge loophole: The implementation
    gets to define what an "access" is, and the definition may or
    may not match the programmer's intent. Most effective uses of
    `volatile' thus require some intimacy with the implementation' s
    documentation suite.

    Yes, there can be very very touchy variables, where something that
    seems innocuous, like just evaluating their address can cause
    side-effects. For example on machines with many segment registers,
    just loading up an address into an address register can cause "seg
    fault"-like traps. Best example, the x86 in 16-bit protected mode.
    Peeking at any segment value that hasnt been explicitly allocated to
    your program will trap out. You're typically handed just 4 out of 8192
    possible segments, so the odds arent good if the goods are odd.

    So compilers, when in that code-generating mode, have to be very
    conservative. No loading up of arbitrary addresses, no stuffing extra
    info into the top bits of pointers.

    Comment

    • Skarmander

      #17
      Re: Ternary operator and memory access

      Udo A. Steinberg wrote:
      On Mon, 07 Aug 2006 14:43:47 +0100 Chris Dollin (CD) wrote:
      >
      CDUdo A. Steinberg wrote:
      CD>
      CD Or, in other words, is a compiler allowed to speculatively fetch a and b
      CD from memory and then assign one of them to x based on the condition?
      CD>
      CDYes, if you can't tell the difference [with conforming C code]; this is the
      CD"as if" rule. The standard specifies the semantics, and the implementation
      CDcan do anything that provides the same result so long as its sneakiness
      CDis invisible.
      >
      How well defined is "invisible sneakiness"?
      Almost exactly, since it's fully defined by the language specification. Any
      two pieces of behavior that have equal semantics according to the standard
      are interchangeable , even if they are observably different. The key is that
      "observatio n" happens on the concrete machine, while the standard only
      defines semantics in terms of an abstract machine.
      In my case "a" is only mapped in virtual memory if the condition is true.
      Otherwise access to "a" causes a page fault. Here the compiler sneakiness
      becomes visible to the user. However, if the compiler can always assume
      that all memory is mapped, then the sneakiness is indeed invisible.
      >
      The compiler is allowed to do this, according to the standard, even if the
      page fault involved releasing a carrier pigeon that flies to Mount
      Kilimanjaro to retrieve the information you requested -- the standard does
      not say how memory retrieval is implemented, in particular not what its
      performance characteristics are. Of course, implementations are expected to
      be "reasonable " to give the poor programmer a fighting chance.

      The sort of guarantees you're looking for require intimate knowledge of the
      platform(s) you're compiling on (which includes the compiler). Aside from
      "volatile", you have little to no way to reliably influence the compiler's
      behavior with regards to memory access, and even "volatile" has its fuzzy areas.

      You can try to make prefetching the values as difficult or unattractive as
      possible, you can try disabling optimization for this particular piece of
      code, you can try compiler-specific extensions, or you could write the parts
      you don't want the compiler to ever optimize in assembler. All of these
      approaches require an amount of nonportable code, but since you're
      specifically dealing with virtual memory that you have some sort of
      interface to, this shouldn't be a big problem. Just make sure you document
      clearly what you're trying to achieve in each instance, so your code won't
      mysteriously break when the platform changes and human beings won't undo
      your carefully crafted compiler conning.

      S.

      Comment

      • Richard

        #18
        Re: Ternary operator and memory access

        Skarmander <invalid@dontma ilme.comwrites:
        >
        You can try to make prefetching the values as difficult or
        unattractive as possible, you can try disabling optimization for this
        particular piece of code, you can try compiler-specific extensions, or
        you could write the parts you don't want the compiler to ever optimize
        in assembler. All of these approaches require an amount of nonportable
        code, but since you're specifically dealing with virtual memory that
        you have some sort of interface to, this shouldn't be a big
        problem. Just make sure you document clearly what you're trying to
        achieve in each instance, so your code won't mysteriously break when
        the platform changes and human beings won't undo your carefully
        crafted compiler conning.
        >
        S.
        Surely its as simple as just replacing variables with function calls to
        retrieve them? get() calls if you will.

        There is no way the compiler will generate a call to the function
        outside of the condition being matched.

        Or? ...

        Comment

        • Skarmander

          #19
          Re: Ternary operator and memory access

          Richard wrote:
          Skarmander <invalid@dontma ilme.comwrites:
          >
          >You can try to make prefetching the values as difficult or
          >unattractive as possible, you can try disabling optimization for this
          >particular piece of code, you can try compiler-specific extensions, or
          >you could write the parts you don't want the compiler to ever optimize
          >in assembler. All of these approaches require an amount of nonportable
          >code, but since you're specifically dealing with virtual memory that
          >you have some sort of interface to, this shouldn't be a big
          >problem. Just make sure you document clearly what you're trying to
          >achieve in each instance, so your code won't mysteriously break when
          >the platform changes and human beings won't undo your carefully
          >crafted compiler conning.
          >>
          >
          Surely its as simple as just replacing variables with function calls to
          retrieve them? get() calls if you will.
          >
          There is no way the compiler will generate a call to the function
          outside of the condition being matched.
          >
          Provided that the compiler does not (partially) inline the functions and the
          functions produce an observable side effect, and assuming of course that
          we're not running on a DS9K.

          Tricking a compiler can be arbitrarily complicated, depending on how smart
          the compiler is. There is no language construct that will guarantee that no
          virtual memory access will be generated to an object; a compiler would in
          principle be free to do this "whenever it felt like it", provided it could
          guarantee this would not cause the program to abort or invoke other
          nonconforming behavior. If the only penalty is speed, though, there are no
          standards-imposed limits to what the compiler can or can't do, just
          considerations of reasonability and (conservative) practicality.

          S.

          Comment

          • Chris Torek

            #20
            Re: Ternary operator and memory access

            >Richard wrote On 08/07/06 11:05,:
            >Possibly I overs implified it : there is no issue with HW if the
            >"result" of b=g() is used from a register. But clearly if expressions
            >(1) and (2) are of the form "*a" or "*b" then it would be madness for
            >the compiler to access *b if the condition is true. Or?
            Or, more specifically, suppose we have:

            int f(int x, int *ap, int *bp) {
            return x ? *ap : *bp;
            }

            (which is of course just the conditional operator itself, written in
            function form, with type restricted to "int" and pointers for the
            values involved).

            In article <1154965455.873 251@news1nwk>
            Eric Sosman <Eric.Sosman@su n.comwrote:
            The compiler might not know whether *a,*b are or aren't
            >safe, but it might be able to tell that it makes no difference.
            >
            int *a = ...;
            int *b = ...;
            *a = 42; /* die here if *a unsafe */
            *b = 56; /* die here if *b unsafe */
            x = cond ? *a : *b;
            >
            >The compiler might conclude that if *a,*b are unsafe the final
            >line won't be executed anyhow, hence a speculative fetch adds
            >no new failure mode to the program.
            Or, the machine may have a "load from memory, but if there is a
            fault during loading, ignore it" instruction -- often actually
            spelled "prefetch" and having no target register -- in which case,
            it can generate:

            f_: .global f_
            # inputs: r1 = x, r2 = ap, r3 = bp
            pref (r2) # prefetch from *ap
            pref (r3) # prefetch from *bp
            tst r1 # which one should we use?
            bz L1
            ld r0,(r2) # x != 0, so fetch from *ap
            ret
            L1:
            ld r0,(r3) # fetch from *bp
            ret

            The two "extra" instructions start RAM -cache transfers, which
            typically take dozens of CPU cycles, if needed. Meanwhile the CPU
            can still execute instructions. This means that the during the
            delay caused by testing r1 (i.e., x), something useful is still
            going on.

            (These "prefetch" instructions would be more useful if they were
            placed further back in the instruction stream, which is of course
            only possible if the routine f() is expanded in line.)
            --
            In-Real-Life: Chris Torek, Wind River Systems
            Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
            email: forget about it http://web.torek.net/torek/index.html
            Reading email is like searching for food in the garbage, thanks to spammers.

            Comment

            • Keith Thompson

              #21
              Re: Ternary operator and memory access

              "Ancient_Hacker " <grg2@comcast.n etwrites:
              Eric Sosman wrote:
              > Unfortunately, there's a huge loophole: The implementation
              >gets to define what an "access" is, and the definition may or
              >may not match the programmer's intent. Most effective uses of
              >`volatile' thus require some intimacy with the implementation' s
              >documentatio n suite.
              >
              Yes, there can be very very touchy variables, where something that
              seems innocuous, like just evaluating their address can cause
              side-effects. For example on machines with many segment registers,
              just loading up an address into an address register can cause "seg
              fault"-like traps. Best example, the x86 in 16-bit protected mode.
              Peeking at any segment value that hasnt been explicitly allocated to
              your program will trap out. You're typically handed just 4 out of 8192
              possible segments, so the odds arent good if the goods are odd.
              >
              So compilers, when in that code-generating mode, have to be very
              conservative. No loading up of arbitrary addresses, no stuffing extra
              info into the top bits of pointers.
              On the other hand, the compiler is in control of the generated code,
              and can do whatever it likes as long as no strictly conforming program
              can tell the difference. It's free to load an arbitrary address if it
              knows that doing so won't have any visible side effects -- and, since
              it's the compiler, it's in a position to know that (unlike the user,
              who should assume that it can invoke undefined behavior). Similarly,
              if it knows that stuffing information into the top bits of pointers
              won't cause any change in behavior (e.g., it happens to know that the
              top N bits are ignored by the hardware and/or operating system), it's
              free to do that as well.

              --
              Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
              San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
              We must do something. This is something. Therefore, we must do this.

              Comment

              Working...