[Bug tree-optimization/104038] New: ranger infinite loop on a PHI statement

[Bug tree-optimization/104038] New: ranger infinite loop on a PHI statement

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

            Bug ID: 104038
           Summary: ranger infinite loop on a PHI statement
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: msebor at gcc dot gnu.org
  Target Milestone: ---

I'm debugging what looks like an infinite loop deep in Ranger.  Interrupting
with SIGABRT the cc1plus process while under GDB produces the backtrace below. 
Returning eventually re-enters the infinite loop in
gimple_ranger::prefill_stmt_dependencies().

The statement being processed at the highest level is:

_11 = PHI <_2493(5), _27180(6)>

Program received signal SIGABRT, Aborted.
0x0000000000ac2f81 in tree_check (__t=0x7fffc6437990, __f=0x31ca5b8
"/src/gcc/master/gcc/value-relation.cc", __l=1117, __g=0x31ca7f4
"find_relation_block", __c=SSA_NAME) at /src/gcc/master/gcc/tree.h:3440
3440      if (TREE_CODE (__t) != __c)
(gdb) bt
#0  0x0000000000ac2f81 in tree_check (__t=0x7fffc6437990, 
    __f=0x31ca5b8 "/src/gcc/master/gcc/value-relation.cc", __l=1117, 
    __g=0x31ca7f4 "find_relation_block", __c=SSA_NAME)
    at /src/gcc/master/gcc/tree.h:3440
#1  0x0000000001bb3831 in dom_oracle::find_relation_block (this=0x55615c0, 
    bb=2, v1=324, v2=47, obj=0x0) at /src/gcc/master/gcc/value-relation.cc:1117
#2  0x0000000001bb3976 in dom_oracle::find_relation_dom (this=0x55615c0, 
    bb=0x7fffe7e08af8, v1=324, v2=47)
    at /src/gcc/master/gcc/value-relation.cc:1149
#3  0x0000000001bb2f52 in dom_oracle::set_one_relation (this=0x55615c0, 
    bb=0x7fffe7e08af8, k=GT_EXPR, op1=0x7fffc643c798, op2=0x7fffc6436870)
    at /src/gcc/master/gcc/value-relation.cc:946
#4  0x0000000001bb3511 in dom_oracle::register_transitives (this=0x55615c0, 
    root_bb=0x7fffe7e08af8, relation=...)
    at /src/gcc/master/gcc/value-relation.cc:1043
#5  0x0000000001bb2c76 in dom_oracle::register_relation (this=0x55615c0, 
    bb=0x7fffe7e08af8, k=GT_EXPR, op1=0x7fffc643c798, op2=0x7fffc643c750)
    at /src/gcc/master/gcc/value-relation.cc:892
#6  0x0000000001bb2a79 in relation_oracle::register_stmt (this=0x55615c0, 
    stmt=0x7fffe7e12948, k=GT_EXPR, op1=0x7fffc643c798, op2=0x7fffc643c750)
    at /src/gcc/master/gcc/value-relation.cc:846
#7  0x0000000002c01084 in fur_depend::register_relation (this=0x7fffffff89e0, 
    s=0x7fffe7e12948, k=GT_EXPR, op1=0x7fffc643c798, op2=0x7fffc643c750)
    at /src/gcc/master/gcc/gimple-range-fold.cc:198
#8  0x0000000002c028d9 in fold_using_range::range_of_range_op (
    this=0x7fffffff8a0f, r=..., s=0x7fffe7e12948, src=...)
    at /src/gcc/master/gcc/gimple-range-fold.cc:642
#9  0x0000000002c021f5 in fold_using_range::fold_stmt (this=0x7fffffff8a0f, 
    r=..., s=0x7fffe7e12948, src=..., name=0x7fffc643c798)
    at /src/gcc/master/gcc/gimple-range-fold.cc:552
#10 0x0000000002bf70be in gimple_ranger::fold_range_internal (this=0x5509e30, 
    r=..., s=0x7fffe7e12948, name=0x7fffc643c798)
    at /src/gcc/master/gcc/gimple-range.cc:250
#11 0x0000000002bf7636 in gimple_ranger::prefill_stmt_dependencies (
    this=0x5509e30, ssa=0x7fffc64631b0)
    at /src/gcc/master/gcc/gimple-range.cc:385
#12 0x0000000002bf7373 in gimple_ranger::range_of_stmt (this=0x5509e30, r=..., 
    s=0x7fffe7e41898, name=0x7fffc64631b0)
    at /src/gcc/master/gcc/gimple-range.cc:307
#13 0x0000000002bf68d4 in gimple_ranger::range_of_expr (this=0x5509e30, r=..., 
    expr=0x7fffc64631b0, stmt=0x7fffd76f4900)
    at /src/gcc/master/gcc/gimple-range.cc:120
#14 0x000000000160c78a in get_size_range (query=0x5509e30, exp=0x7fffc64631b0, 
    stmt=0x7fffd76f4900, range=0x7fffffffc190, flags=3)
    at /src/gcc/master/gcc/pointer-query.cc:320
#15 0x000000000160d8de in gimple_call_alloc_size (stmt=0x7fffd76f4900, 
    rng1=0x7fffffffc470, qry=0x5509e30)
    at /src/gcc/master/gcc/pointer-query.cc:506
#16 0x0000000001614a30 in handle_ssa_name (ptr=0x7fffc6463240, addr=false, 
    ostype=0, pref=0x7fffffffd650, snlim=..., qry=0x7fffffffd730)
    at /src/gcc/master/gcc/pointer-query.cc:2053
#17 0x00000000016160a8 in compute_objsize_r (ptr=0x7fffc6463240, 
    stmt=0x7fffe7f45f50, addr=false, ostype=0, pref=0x7fffffffd650, snlim=..., 
    qry=0x7fffffffd730) at /src/gcc/master/gcc/pointer-query.cc:2346
#18 0x00000000016156d6 in handle_ssa_name (ptr=0x7fffc6463288, addr=false, 
    ostype=0, pref=0x7fffffffd650, snlim=..., qry=0x7fffffffd730)
    at /src/gcc/master/gcc/pointer-query.cc:2196
#19 0x00000000016160a8 in compute_objsize_r (ptr=0x7fffc6463288, 
    stmt=0x7fffe7e0a3c0, addr=false, ostype=0, pref=0x7fffffffd650, snlim=..., 
--Type <RET> for more, q to quit, c to continue without paging--
    qry=0x7fffffffd730) at /src/gcc/master/gcc/pointer-query.cc:2346
#20 0x00000000016156d6 in handle_ssa_name (ptr=0x7fffc6463318, addr=false, 
    ostype=0, pref=0x7fffffffd650, snlim=..., qry=0x7fffffffd730)
    at /src/gcc/master/gcc/pointer-query.cc:2196
#21 0x00000000016160a8 in compute_objsize_r (ptr=0x7fffc6463318, 
    stmt=0x7fffe7e0a410, addr=false, ostype=0, pref=0x7fffffffd650, snlim=..., 
    qry=0x7fffffffd730) at /src/gcc/master/gcc/pointer-query.cc:2346
#22 0x00000000016156d6 in handle_ssa_name (ptr=0x7fffc6463360, addr=false, 
    ostype=0, pref=0x7fffffffd650, snlim=..., qry=0x7fffffffd730)
    at /src/gcc/master/gcc/pointer-query.cc:2196
#23 0x00000000016160a8 in compute_objsize_r (ptr=0x7fffc6463360, 
    stmt=0x7fffc642fa00, addr=false, ostype=0, pref=0x7fffffffd650, snlim=..., 
    qry=0x7fffffffd730) at /src/gcc/master/gcc/pointer-query.cc:2346
#24 0x0000000001616253 in compute_objsize (ptr=0x7fffc6463360, 
    stmt=0x7fffc642fa00, ostype=0, pref=0x7fffffffd650, ptr_qry=0x7fffffffd730)
    at /src/gcc/master/gcc/pointer-query.cc:2380
#25 0x0000000001611d1d in pointer_query::get_ref (this=0x7fffffffd730, 
    ptr=0x7fffc6463360, stmt=0x7fffc642fa00, pref=0x7fffffffd650, ostype=0)
    at /src/gcc/master/gcc/pointer-query.cc:1498
#26 0x0000000002c52305 in (anonymous namespace)::walk_ssa_vars (
    func=0x7fffce791f00) at /src/gcc/master/gcc/gimple-warn-recursion.c:184
#27 0x0000000002c52395 in (anonymous namespace)::pass_warn_recursion::execute (
    this=0x3f1b6b0, func=0x7fffce791f00)
    at /src/gcc/master/gcc/gimple-warn-recursion.c:200
#28 0x0000000001605b8c in execute_one_pass (pass=0x3f1b6b0)
    at /src/gcc/master/gcc/passes.c:2637
#29 0x0000000001605f08 in execute_pass_list_1 (pass=0x3f1b6b0)
    at /src/gcc/master/gcc/passes.c:2737
#30 0x0000000001605f92 in execute_pass_list (fn=0x7fffce791f00, pass=0x3f1b530)
    at /src/gcc/master/gcc/passes.c:2748
#31 0x0000000001603a29 in do_per_function_toporder (
    callback=0x1605f55 <execute_pass_list(function*, opt_pass*)>, 
    data=0x3f1b530) at /src/gcc/master/gcc/passes.c:1773
#32 0x0000000001606bc2 in execute_ipa_pass_list (pass=0x3f1b4d0)
    at /src/gcc/master/gcc/passes.c:3082
#33 0x00000000010a68c1 in ipa_passes ()
    at /src/gcc/master/gcc/cgraphunit.c:2160
#34 0x00000000010a6c43 in symbol_table::compile (this=0x7fffea1cf000)
    at /src/gcc/master/gcc/cgraphunit.c:2281
#35 0x00000000010a71ae in symbol_table::finalize_compilation_unit (
    this=0x7fffea1cf000) at /src/gcc/master/gcc/cgraphunit.c:2529
#36 0x000000000175eec2 in compile_file () at /src/gcc/master/gcc/toplev.c:479
#37 0x0000000001761e5c in do_compile (no_backend=false)
    at /src/gcc/master/gcc/toplev.c:2158
#38 0x0000000001762233 in toplev::main (this=0x7fffffffdb0a, argc=14, 
    argv=0x7fffffffdc58) at /src/gcc/master/gcc/toplev.c:2310
#39 0x0000000002e86a74 in main (argc=14, argv=0x7fffffffdc58)
    at /src/gcc/master/gcc/main.c:39
(gdb) 


The rest of the GDB session:

(gdb) n
crash_signal (signo=0) at /src/gcc/master/gcc/toplev.c:311
311     {
(gdb) return
warning: Function does not return normally to caller.
Make crash_signal(int) return now? (y or n) y
#0  <signal handler called>
(gdb) fin
Run till exit from #0  <signal handler called>
0x0000000000ac2f81 in tree_check (__t=0x7fffc6437990, __f=0x31ca5b8
"/src/gcc/master/gcc/value-relation.cc", __l=1117, __g=0x31ca7f4
"find_relation_block", __c=SSA_NAME) at /src/gcc/master/gcc/tree.h:3440
3440      if (TREE_CODE (__t) != __c)
(gdb) 
Run till exit from #0  0x0000000000ac2f81 in tree_check (__t=0x7fffc6437990, 
    __f=0x31ca5b8 "/src/gcc/master/gcc/value-relation.cc", __l=1117, 
    __g=0x31ca7f4 "find_relation_block", __c=SSA_NAME)
    at /src/gcc/master/gcc/tree.h:3440
0x0000000001bb3831 in dom_oracle::find_relation_block (this=0x55615c0, bb=2,
v1=324, v2=47, obj=0x0) at /src/gcc/master/gcc/value-relation.cc:1117
1117          unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
Value returned is $1 = (tree_node *) 0x7fffc6437990
(gdb) 
Run till exit from #0  0x0000000001bb3831 in dom_oracle::find_relation_block (
    this=0x55615c0, bb=2, v1=324, v2=47, obj=0x0)
    at /src/gcc/master/gcc/value-relation.cc:1117
0x0000000001bb3976 in dom_oracle::find_relation_dom (this=0x55615c0,
bb=0x7fffe7e08af8, v1=324, v2=47) at /src/gcc/master/gcc/value-relation.cc:1149
1149          r = find_relation_block (bb->index, v1, v2);
Value returned is $2 = TRUTH_NOT_EXPR
(gdb) 
Run till exit from #0  0x0000000001bb3976 in dom_oracle::find_relation_dom (
    this=0x55615c0, bb=0x7fffe7e08af8, v1=324, v2=47)
    at /src/gcc/master/gcc/value-relation.cc:1149
0x0000000001bb2f52 in dom_oracle::set_one_relation (this=0x55615c0,
bb=0x7fffe7e08af8, k=GT_EXPR, op1=0x7fffc643c798, op2=0x7fffc6436870) at
/src/gcc/master/gcc/value-relation.cc:946
946           curr = find_relation_dom (bb, v1, v2);
Value returned is $3 = TRUTH_NOT_EXPR
(gdb) 
Run till exit from #0  0x0000000001bb2f52 in dom_oracle::set_one_relation (
    this=0x55615c0, bb=0x7fffe7e08af8, k=GT_EXPR, op1=0x7fffc643c798, 
    op2=0x7fffc6436870) at /src/gcc/master/gcc/value-relation.cc:946
dom_oracle::register_transitives (this=0x55615c0, root_bb=0x7fffe7e08af8,
relation=...) at /src/gcc/master/gcc/value-relation.cc:1044
1044                  if (dump_file && (dump_flags & TDF_DETAILS))
Value returned is $4 = (relation_chain *) 0x6b39460
(gdb) 
Run till exit from #0  dom_oracle::register_transitives (this=0x55615c0, 
    root_bb=0x7fffe7e08af8, relation=...)
    at /src/gcc/master/gcc/value-relation.cc:1044
0x0000000001bb2c76 in dom_oracle::register_relation (this=0x55615c0,
bb=0x7fffe7e08af8, k=GT_EXPR, op1=0x7fffc643c798, op2=0x7fffc643c750) at
/src/gcc/master/gcc/value-relation.cc:892
892           register_transitives (bb, *ptr);
(gdb) 
Run till exit from #0  0x0000000001bb2c76 in dom_oracle::register_relation (
    this=0x55615c0, bb=0x7fffe7e08af8, k=GT_EXPR, op1=0x7fffc643c798, 
    op2=0x7fffc643c750) at /src/gcc/master/gcc/value-relation.cc:892
0x0000000001bb2a79 in relation_oracle::register_stmt (this=0x55615c0,
stmt=0x7fffe7e12948, k=GT_EXPR, op1=0x7fffc643c798, op2=0x7fffc643c750) at
/src/gcc/master/gcc/value-relation.cc:846
846       register_relation (gimple_bb (stmt), k, op1, op2);
(gdb) 
Run till exit from #0  0x0000000001bb2a79 in relation_oracle::register_stmt (
    this=0x55615c0, stmt=0x7fffe7e12948, k=GT_EXPR, op1=0x7fffc643c798, 
    op2=0x7fffc643c750) at /src/gcc/master/gcc/value-relation.cc:846
fur_depend::register_relation (this=0x7fffffff89e0, s=0x7fffe7e12948,
k=GT_EXPR, op1=0x7fffc643c798, op2=0x7fffc643c750) at
/src/gcc/master/gcc/gimple-range-fold.cc:199
199     }
(gdb) 
Run till exit from #0  fur_depend::register_relation (this=0x7fffffff89e0, 
    s=0x7fffe7e12948, k=GT_EXPR, op1=0x7fffc643c798, op2=0x7fffc643c750)
    at /src/gcc/master/gcc/gimple-range-fold.cc:199
fold_using_range::range_of_range_op (this=0x7fffffff8a0f, r=...,
s=0x7fffe7e12948, src=...) at /src/gcc/master/gcc/gimple-range-fold.cc:644
644                   if (gimple_range_ssa_p (op2))
(gdb) 
Run till exit from #0  fold_using_range::range_of_range_op (
    this=0x7fffffff8a0f, r=..., s=0x7fffe7e12948, src=...)
    at /src/gcc/master/gcc/gimple-range-fold.cc:644
0x0000000002c021f5 in fold_using_range::fold_stmt (this=0x7fffffff8a0f, r=...,
s=0x7fffe7e12948, src=..., name=0x7fffc643c798) at
/src/gcc/master/gcc/gimple-range-fold.cc:552
552         res = range_of_range_op (r, s, src);
Value returned is $5 = true
(gdb) 
Run till exit from #0  0x0000000002c021f5 in fold_using_range::fold_stmt (
    this=0x7fffffff8a0f, r=..., s=0x7fffe7e12948, src=..., name=0x7fffc643c798)
    at /src/gcc/master/gcc/gimple-range-fold.cc:552
gimple_ranger::fold_range_internal (this=0x5509e30, r=..., s=0x7fffe7e12948,
name=0x7fffc643c798) at /src/gcc/master/gcc/gimple-range.cc:251
251     }
Value returned is $6 = true
(gdb) 
Run till exit from #0  gimple_ranger::fold_range_internal (this=0x5509e30, 
    r=..., s=0x7fffe7e12948, name=0x7fffc643c798)
    at /src/gcc/master/gcc/gimple-range.cc:251
gimple_ranger::prefill_stmt_dependencies (this=0x5509e30, ssa=0x7fffc64631b0)
at /src/gcc/master/gcc/gimple-range.cc:386
386                   m_cache.set_global_range (name, r);
Value returned is $7 = true
(gdb) 
Run till exit from #0  gimple_ranger::prefill_stmt_dependencies (
    this=0x5509e30, ssa=0x7fffc64631b0)
    at /src/gcc/master/gcc/gimple-range.cc:386

Program received signal SIGABRT, Aborted.
0x0000000001bb4c90 in value_relation::op2 (this=0x7fffc643dee8) at
/src/gcc/master/gcc/value-relation.cc:574
574       inline tree op2 () const { return name2; }
(gdb) n
crash_signal (signo=0) at /src/gcc/master/gcc/toplev.c:311
311     {
(gdb) return
warning: Function does not return normally to caller.
Make crash_signal(int) return now? (y or n) y
#0  <signal handler called>
(gdb) fin
Run till exit from #0  <signal handler called>
0x0000000001bb4c90 in value_relation::op2 (this=0x7fffc643dee8) at
/src/gcc/master/gcc/value-relation.cc:574
574       inline tree op2 () const { return name2; }
(gdb) 
Run till exit from #0  0x0000000001bb4c90 in value_relation::op2 (
    this=0x7fffc643dee8) at /src/gcc/master/gcc/value-relation.cc:574
0x0000000001bb3843 in dom_oracle::find_relation_block (this=0x55615c0, bb=2,
v1=603, v2=414, obj=0x0) at /src/gcc/master/gcc/value-relation.cc:1118
1118          unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
Value returned is $8 = (tree_node *) 0x7fffc64367e0
(gdb) 
Run till exit from #0  0x0000000001bb3843 in dom_oracle::find_relation_block (
    this=0x55615c0, bb=2, v1=603, v2=414, obj=0x0)
    at /src/gcc/master/gcc/value-relation.cc:1118
0x0000000001bb3976 in dom_oracle::find_relation_dom (this=0x55615c0,
bb=0x7fffe7e08af8, v1=603, v2=414) at
/src/gcc/master/gcc/value-relation.cc:1149
1149          r = find_relation_block (bb->index, v1, v2);
Value returned is $9 = TRUTH_NOT_EXPR
(gdb) 
Run till exit from #0  0x0000000001bb3976 in dom_oracle::find_relation_dom (
    this=0x55615c0, bb=0x7fffe7e08af8, v1=603, v2=414)
    at /src/gcc/master/gcc/value-relation.cc:1149
0x0000000001bb2f52 in dom_oracle::set_one_relation (this=0x55615c0,
bb=0x7fffe7e08af8, k=GT_EXPR, op1=0x7fffc6441750, op2=0x7fffc643e168) at
/src/gcc/master/gcc/value-relation.cc:946
946           curr = find_relation_dom (bb, v1, v2);
Value returned is $10 = TRUTH_NOT_EXPR
(gdb) 
Run till exit from #0  0x0000000001bb2f52 in dom_oracle::set_one_relation (
    this=0x55615c0, bb=0x7fffe7e08af8, k=GT_EXPR, op1=0x7fffc6441750, 
    op2=0x7fffc643e168) at /src/gcc/master/gcc/value-relation.cc:946
dom_oracle::register_transitives (this=0x55615c0, root_bb=0x7fffe7e08af8,
relation=...) at /src/gcc/master/gcc/value-relation.cc:1044
1044                  if (dump_file && (dump_flags & TDF_DETAILS))
Value returned is $11 = (relation_chain *) 0x6f07d00
(gdb) 
Run till exit from #0  dom_oracle::register_transitives (this=0x55615c0, 
    root_bb=0x7fffe7e08af8, relation=...)
    at /src/gcc/master/gcc/value-relation.cc:1044
0x0000000001bb2c76 in dom_oracle::register_relation (this=0x55615c0,
bb=0x7fffe7e08af8, k=GT_EXPR, op1=0x7fffc6441750, op2=0x7fffc6441708) at
/src/gcc/master/gcc/value-relation.cc:892
892           register_transitives (bb, *ptr);
(gdb) 
Run till exit from #0  0x0000000001bb2c76 in dom_oracle::register_relation (
    this=0x55615c0, bb=0x7fffe7e08af8, k=GT_EXPR, op1=0x7fffc6441750, 
    op2=0x7fffc6441708) at /src/gcc/master/gcc/value-relation.cc:892
0x0000000001bb2a79 in relation_oracle::register_stmt (this=0x55615c0,
stmt=0x7fffe7e18a50, k=GT_EXPR, op1=0x7fffc6441750, op2=0x7fffc6441708) at
/src/gcc/master/gcc/value-relation.cc:846
846       register_relation (gimple_bb (stmt), k, op1, op2);
(gdb) 
Run till exit from #0  0x0000000001bb2a79 in relation_oracle::register_stmt (
    this=0x55615c0, stmt=0x7fffe7e18a50, k=GT_EXPR, op1=0x7fffc6441750, 
    op2=0x7fffc6441708) at /src/gcc/master/gcc/value-relation.cc:846
fur_depend::register_relation (this=0x7fffffff89e0, s=0x7fffe7e18a50,
k=GT_EXPR, op1=0x7fffc6441750, op2=0x7fffc6441708) at
/src/gcc/master/gcc/gimple-range-fold.cc:199
199     }
(gdb) 
Run till exit from #0  fur_depend::register_relation (this=0x7fffffff89e0, 
    s=0x7fffe7e18a50, k=GT_EXPR, op1=0x7fffc6441750, op2=0x7fffc6441708)
    at /src/gcc/master/gcc/gimple-range-fold.cc:199
fold_using_range::range_of_range_op (this=0x7fffffff8a0f, r=...,
s=0x7fffe7e18a50, src=...) at /src/gcc/master/gcc/gimple-range-fold.cc:644
644                   if (gimple_range_ssa_p (op2))
(gdb) 
Run till exit from #0  fold_using_range::range_of_range_op (
    this=0x7fffffff8a0f, r=..., s=0x7fffe7e18a50, src=...)
    at /src/gcc/master/gcc/gimple-range-fold.cc:644
0x0000000002c021f5 in fold_using_range::fold_stmt (this=0x7fffffff8a0f, r=...,
s=0x7fffe7e18a50, src=..., name=0x7fffc6441750) at
/src/gcc/master/gcc/gimple-range-fold.cc:552
552         res = range_of_range_op (r, s, src);
Value returned is $12 = true
(gdb) 
Run till exit from #0  0x0000000002c021f5 in fold_using_range::fold_stmt (
    this=0x7fffffff8a0f, r=..., s=0x7fffe7e18a50, src=..., name=0x7fffc6441750)
    at /src/gcc/master/gcc/gimple-range-fold.cc:552
gimple_ranger::fold_range_internal (this=0x5509e30, r=..., s=0x7fffe7e18a50,
name=0x7fffc6441750) at /src/gcc/master/gcc/gimple-range.cc:251
251     }
Value returned is $13 = true
(gdb) 
Run till exit from #0  gimple_ranger::fold_range_internal (this=0x5509e30, 
    r=..., s=0x7fffe7e18a50, name=0x7fffc6441750)
    at /src/gcc/master/gcc/gimple-range.cc:251
gimple_ranger::prefill_stmt_dependencies (this=0x5509e30, ssa=0x7fffc64631b0)
at /src/gcc/master/gcc/gimple-range.cc:386
386                   m_cache.set_global_range (name, r);
Value returned is $14 = true
(gdb) 
Run till exit from #0  gimple_ranger::prefill_stmt_dependencies (
    this=0x5509e30, ssa=0x7fffc64631b0)
    at /src/gcc/master/gcc/gimple-range.cc:386

[Bug tree-optimization/104038] ranger infinite loop on a PHI statement

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

--- Comment #1 from Martin Sebor <msebor at gcc dot gnu.org> ---
Created attachment 52197
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52197&action=edit
Patch needed to trigger the infinite loop.

When the attached patch is applied the infinite loop can be triggered by
compiling the test case (to be attached) with -O2.

[Bug tree-optimization/104038] ranger infinite loop on a PHI statement

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

--- Comment #2 from Martin Sebor <msebor at gcc dot gnu.org> ---
Created attachment 52198
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52198&action=edit
Unreduced test case.

The attached translation unit reproduces the infinite loop.

[Bug tree-optimization/104038] ranger infinite loop on a PHI statement

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

--- Comment #3 from Martin Sebor <msebor at gcc dot gnu.org> ---
The basic block being analyzed is bb 2 in clang::clangd::stdlib::initialize(). 
What's unusual about it is that it's a sequence of 2464 assignments like so:

<bb 2> :
SymCount_21 = 0;
SymCount_22 = SymCount_21 + 1;
SymCount_23 = SymCount_22 + 1;
SymCount_24 = SymCount_23 + 1;
...
SymCount_2481 = SymCount_2480 + 1;
SymCount_2482 = SymCount_2481 + 1;
SymCount_2483 = SymCount_2482 + 1;
_2484 = (sizetype) SymCount_2483;
if (_2484 <= 288230376151711743)
  goto <bb 3>; [INV]
else
  goto <bb 4>; [INV]

[Bug tree-optimization/104038] ranger infinite loop on a PHI statement

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

--- Comment #4 from Martin Sebor <msebor at gcc dot gnu.org> ---
The problem is reproducible with -O1 and above.  To confirm it's not infinite
recursion I let the process run for about an hour before killing it.  Memory
consumption seems to slowly but steadily increase as GCC spins.

[Bug tree-optimization/104038] ranger infinite loop on a PHI statement

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=103603

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Similar to PR 103603.

[Bug tree-optimization/104038] ranger infinite loop on a PHI statement

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=103464

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
And PR 103464.

[Bug tree-optimization/104038] ranger infinite loop on a PHI statement while building Clang

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|ranger infinite loop on a   |ranger infinite loop on a
                   |PHI statement               |PHI statement while
                   |                            |building Clang
                 CC|                            |amacleod at redhat dot com

--- Comment #7 from Martin Sebor <msebor at gcc dot gnu.org> ---
With r12-6606 the infinite loop should be reproducible with an unmodified GCC
trunk.

[Bug tree-optimization/104038] ranger infinite loop on a PHI statement while building Clang

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

--- Comment #8 from Andrew Macleod <amacleod at redhat dot com> ---
The issue is transitive relations are being registered in an unbounded way.
SymCount_369 = SymCount_368 + 1;
SymCount_370 = SymCount_369 + 1;
SymCount_371 = SymCount_370 + 1;


_370 > _369, and _369 is > _368, so it registers a transitive relation between
_370 > _368
Then we register _371 > 370 and transitive relations_371 > 369 as well as _371
> 368

This cascades as the chain gets longer and would be quadratic in nature.
This is then compounded by the currently linear nature of looking up a relation
within the current basic block.

On monday, I will introduce a capping heuristic to transitivity and/or limiting
the number of relations we can add to a block, preventing either situation from
being an issue going forward.

[Bug tree-optimization/104038] ranger infinite loop on a PHI statement while building Clang

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:254ada46ae0f21bd6f40314214f969f368328e22

commit r12-6678-g254ada46ae0f21bd6f40314214f969f368328e22
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Jan 17 12:03:18 2022 -0500

    Limit the number of relations registered per basic block.

    In pathological cases, the number of transitive relations being added is
    potentially quadratic.  Lookups for relations in a block is linear in
    nature, so simply limit the number of relations to some reasonable number.

            PR tree-optimization/104038
            * doc/invoke.texi (relation-block-limit): New.
            * params.opt (relation-block-limit): New.
            * value-relation.cc (dom_oracle::register_relation): Check for NULL
            record before invoking transitive registery.
            (dom_oracle::set_one_relation): Check limit before creating record.
            (dom_oracle::register_transitives): Stop when no record created.
            * value-relation.h (relation_chain_head::m_num_relations): New.

[Bug tree-optimization/104038] ranger infinite loop on a PHI statement while building Clang

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104038

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |FIXED

--- Comment #10 from Andrew Macleod <amacleod at redhat dot com> ---
fixed.