backend: incorrect code optimization on while loops

[liushuyu]

I tried this code with -O3:

// adapted from https://github.com/rust-lang/rust/blob/master/src/test/ui/consts/const-eval/infinite_loop.rs
pub const fn test() -> u64 {
    let mut n = 113383; // #20 in https://oeis.org/A006884
    while n != 1 {
        n = if n % 2 == 0 { n/2 } else { 3*n + 1 };
    }
    n
}

pub const fn test_1() -> u64 {
    test()
}

I expected to see this happen: The function test_1 returns 1.

Instead, this happened: The function test_1 returns 113383.

(tree dump from phase ccp1-raw):

;; Function const_eval_oeis_a006884::test (_ZN23const_eval_oeis_a0068844test17h64d1733dc533ef5cE, funcdef_no=0, decl_uid=74, cgraph_uid=1, symbol_order=0)

Folding predicate 1 != 0 to 1
Removing basic block 4
Removing basic block 5
Removing basic block 6
Removing basic block 7
Merging blocks 2 and 3
Merging blocks 2 and 8
__attribute__((cdecl))
u64 const_eval_oeis_a006884::test ()
{
  u64 n;

  <bb 2> :
  gimple_return <113383>

}



;; Function const_eval_oeis_a006884::test_1 (_ZN23const_eval_oeis_a0068846test_117h64d1733dc533ef5cE, funcdef_no=1, decl_uid=97, cgraph_uid=2, symbol_order=1)

__attribute__((cdecl))
u64 const_eval_oeis_a006884::test_1 ()
{
  u64 _1;

  <bb 2> :
  gimple_call <const_eval_oeis_a006884::test, _1>
  gimple_return <_1>

}

As you can see, the constant evaluator, for some reason, believes the function should return 113383, which is impossible in this case (it should return 1, which is dictated by the end condition for that while loop).

To verify if this is caused by GCC's middle-end or backend, I made an equivalent code in C++:

constexpr int test() {
  int n = 113383;
  while (n != 1) {
    if (n % 2 == 0) {
      n /= 2;
    } else {
      n = n * 3 + 1;
    }
  }
  return n;
}

int test_1() {
  return test();
}

When dumping the tree from the same pass:

;; Function test (_Z4testv, funcdef_no=0, decl_uid=2368, cgraph_uid=1, symbol_order=0)

int test ()
{
  int n;
  unsigned int n.0_1;
  unsigned int _2;
  int _3;
  int _6;

  <bb 2> :
  # DEBUG BEGIN_STMT
  # DEBUG n => 113383
  # DEBUG BEGIN_STMT
  goto <bb 6>; [INV]

  <bb 3> :
  # DEBUG BEGIN_STMT
  n.0_1 = (unsigned int) n_4;
  _2 = n.0_1 & 1;
  if (_2 == 0)
    goto <bb 4>; [INV]
  else
    goto <bb 5>; [INV]

  <bb 4> :
  # DEBUG BEGIN_STMT
  n_9 = n_4 / 2;
  # DEBUG n => n_9
  goto <bb 6>; [INV]

  <bb 5> :
  # DEBUG BEGIN_STMT
  _3 = n_4 * 3;
  n_8 = _3 + 1;
  # DEBUG n => n_8

  <bb 6> :
  # n_4 = PHI <113383(2), n_9(4), n_8(5)>
  # DEBUG n => n_4
  # DEBUG BEGIN_STMT
  if (n_4 != 1)
    goto <bb 3>; [INV]
  else
    goto <bb 7>; [INV]

  <bb 7> :
  # DEBUG BEGIN_STMT
  _6 = n_4;
  return _6;

}



;; Function test_1 (_Z6test_1v, funcdef_no=1, decl_uid=2376, cgraph_uid=2, symbol_order=1)

int test_1 ()
{
  int D.2391;

  <bb 2> :
  # DEBUG BEGIN_STMT
  # DEBUG n => 113383
  # DEBUG n => NULL
  return 1;

}

As you can see, the result is correct. (so it's not a GCC internals' issue)

Meta

• 4f0a272

[CohenArthur]

This is also the case when compiling the code in a non-const fn and with -O0. So there's something weird going on.

pub fn test() -> u64 {
    let mut n = 113383; // #20 in https://oeis.org/A006884
    while n != 1 {
        n = if n % 2 == 0 { n / 2 } else { 3 * n + 1 };
    }
    n
}

pub fn test_1() -> u64 {
    test()
}

extern "C" {
    fn printf(fmt: *const i8, ...);
}

fn main() {
    unsafe { printf("%lu\n" as *const str as *const i8, test_1()) }
}

with gccrs: 113383
with rustc: 1

[dkm]

__attribute__((cdecl))
u64 example::test ()
{
  u64 n = 113383;

    u64 RUSTTMP.0;
    u64 n = 113383;
  while (1)
    {
      {
        <D.82>:;
        if (n != 1) break;

https://rust.godbolt.org/z/4PTv1KbjY

Looks like something is wrong early in the frontend