I am solving one of the lab exercises from the CS:APP course as a self-study.

In the CS:APP course the maximum positive number, that can be represented with 4 bytes in two's complement, is marked as Tmax (which is equal to the 0x7fffffff).

Likewise, the most negative number is marked as Tmin (which is equal to the 0x80000000).

The goal of the exercise was to implement a isTmax() function which should return 1, when given an Tmax, otherwise it should return 0. This should be done only with a restricted set of operators which are: ! ~ & ^ | , the maximum number of operators is 10.

Below you can see my implementation of isTmax() function, with comments explaining how it should work.

#include <stdio.h>

int isTmax(int x) 
{
    /* Ok, lets assume that x really is tMax.
     * This means that if we add 1 to it we get tMin, lets call it
     * possible_tmin. We can produce an actual tMin with left shift.
     * We can now xor both tmins, lets call the result check.
     * If inputs to xor are identical then the check will be equal to
     * 0x00000000, if they are not identical then the result will be some
     * value different from 0x00000000.
     * As a final step we logicaly negate check to get the requested behaviour.
     * */
    int possible_tmin = x   1;
    int tmin = 1 << 31;
    int check = possible_tmin ^ tmin;
    int negated_check = !check;

    printf("input =\t\t 0xx\n", x);
    printf("possible_tmin =\t 0xx\n", possible_tmin);
    printf("tmin =\t\t 0xx\n", tmin);
    printf("check =\t\t 0xx\n", check);
    printf("negated_check =\t 0xx\n", negated_check);

    return negated_check;
}

int main() 
{
    printf("output: %i", isTmax(0x7fffffff));

    return 0;
}

The problem that I am facing is that I get different output whether I set an optimization flag when compiling the program. I am using gcc 11.1.0.

With no optimizations I get this output, which is correct for the given input:

$ gcc main.c -lm -m32 -Wall && ./a.out
input =          0x7fffffff
possible_tmin =  0x80000000
tmin =           0x80000000
check =          0x00000000
negated_check =  0x00000001
output: 1

With optimization enabled I get this output, which is incorrect.

gcc main.c -lm -m32 -Wall -O1 && ./a.out
input =          0x7fffffff
possible_tmin =  0x80000000
tmin =           0x80000000
check =          0x00000000
negated_check =  0x00000000
output: 0

For some reason the logical negation is not applied to the check variable when optimization is enabled.

The problem persists with any other level of optimization (-O2, -O3, -Os). Even if I write the expressions as a one-liner return !((x 1) ^ (1 << 31)); nothing changes.

I can "force" a correct behavior If I declare check as a volatile.

I am using the same level of optimization as is used by the automated checker that came with the exercise, If I turn it off my code passes all checks.

Can anyone shed on some light why is this happening? Why doesn't the logical negation happen?

EDIT: I have added a section with the extra guidelines and restrictions connected to the exercise that I forgot to include with the original post. Specifically, I am not allowed to use any other data type instead of int. I am not sure if that also includes literal suffix U.

  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code
  must conform to the following style:

  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ |   << >>

  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.

  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
  7. Use any data type other than int.  This implies that you
     cannot use arrays, structs, or unions.


  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting an integer by more
     than the word size.

CodePudding user response：

The specific cause is most likely in 1 << 31. Nominally, this would produce 2³¹, but 2³¹ is not representable in a 32-bit int. In C 2018 6.5.7 4, where the C standard specifies the behavior of <<, it says the behavior in this case is not defined.

When optimization is disabled, the compiler may generate a processor instruction that gives 1 left 31 bits. This produces the bit pattern 0x80000000, and subsequent instructions interpret that as −2³¹.

In contrast, with optimization enabled, the optimization software recognizes that 1 << 31 is not defined and does not generate a shift instruction for it. It may replace it with a compile-time value. Since the behavior is not defined by the C standard, the compiler is allowed to use any value for that. It might use zero, for example. (Since the entire behavior is not defined, not just the result, the compiler is actually allowed toreplace this part of your program with anything. It could use entirely different instructions or just abort.)

You can start to fix that by using 1u << 31. That is defined because 2³¹ fits in the unsigned int type. However, there is a problem when assigning that to tmin, because tmin is an int, and the value still does not fit in an int. However, for this conversion, the behavior is implementation-defined, not undefined. Common C implementations define the conversion to wrap modulo 2³², which means that the assignment will store −2³¹ in tmin. However, an alternative is to change tmin from int to unsigned int (which may also be written just as unsigned) and then work with unsigned integers. That will give fully defined behavior, rather than undefined or implementation-defined, except for assuming the int width is 32 bits.

Another problem is x 1. When x is INT_MAX, that overflows. That is likely not the cause of the behavior you observe, as common compilers simply wrap the result. Nonetheless, it can be corrected similarly, by using x 1u and changing the type of possible_tmin to unsigned.

That said, the desired result can be computed with return ! (x ^ ~0u >> 1);. This takes zero as an unsigned int, complements it to produce all 1 bits, and shifts it right one bit, which gives a single 0 bit followed by all 1 bits. That is the INT_MAX value, and it works regardless of the width of int. Then this is XORed with x. The result of that has all zero bits if and only if x is also INT_MAX. Then ! either changes that zero into 1 or changes a non-zero value into 0.

CodePudding user response：

Change the type of the variables from int to unsigned int (or just unsigned) because bitwise operations with signed values cause undefined behavior.

CodePudding user response：

@Voo made a correct observation, x 1 created an undefined behavior, which was not apparent at first as the printf calls did not show anything weird happening.