Re: [jira] Created: (STDCXX-1022) [MSVC x86 / optimized] ICE in std::__make_heap()

[Martin Sebor-2]

Hi Farid,

Did you happen to reduce this to a small test case and send
it to Microsoft?

Thanks
Martin

Farid Zaripov (JIRA) wrote:

> [MSVC x86 / optimized] ICE in std::__make_heap()
> ------------------------------------------------
>
>                  Key: STDCXX-1022
>                  URL: https://issues.apache.org/jira/browse/STDCXX-1022
>              Project: C++ Standard Library
>           Issue Type: Bug
>           Components: External
>          Environment: 32-bit MSVC 7.1, 8.0, 9.0 in optimized builds
>             Reporter: Farid Zaripov
>
>
> The 25.heap, 25.partial_sort, 25.sort tests are failed to compile on every 32-bit MSVC in optimized builds due to ICE:
>
> {noformat}
> f:\stdcxx\4.2.x\include\rw\_heap.cc(93) : fatal error C1001: An internal error has occurred in the compiler.
> (compiler file 'f:\dd\vctools\compiler\utc\src\p2\main.c[0x51144F50:0x0000002C]', line 182)
>  To work around this problem, try simplifying or changing the program near the locations listed above.
> Please choose the Technical Support command on the Visual C++
>  Help menu, or open the Technical Support help file for more information
> {noformat}
>
>
>

[Martin Sebor]

0....:....1....:....2....:....3....:....4....:....5....:....6....:....7....:....8
Btw., the reason I ask is so we can come up with a better/cleaner workaround,
hopefully one that will be as efficient as the original code and won't need
an #ifdef.

Do you see the ICE in a specific test (or example), maybe only for a specific
instantiation of the template, or does it happen regardless of the actual
types of the template arguments?

Martin Sebor-2 wrote:

Hi Farid,

Did you happen to reduce this to a small test case and send
it to Microsoft?

Thanks
Martin

Farid Zaripov (JIRA) wrote:
> [MSVC x86 / optimized] ICE in std::__make_heap()
> ------------------------------------------------
>
>                  Key: STDCXX-1022
>                  URL: https://issues.apache.org/jira/browse/STDCXX-1022
>              Project: C++ Standard Library
>           Issue Type: Bug
>           Components: External
>          Environment: 32-bit MSVC 7.1, 8.0, 9.0 in optimized builds
>             Reporter: Farid Zaripov
>
>
> The 25.heap, 25.partial_sort, 25.sort tests are failed to compile on every 32-bit MSVC in optimized builds due to ICE:
>
> {noformat}
> f:\stdcxx\4.2.x\include\rw\_heap.cc(93) : fatal error C1001: An internal error has occurred in the compiler.
> (compiler file 'f:\dd\vctools\compiler\utc\src\p2\main.c[0x51144F50:0x0000002C]', line 182)
>  To work around this problem, try simplifying or changing the program near the locations listed above.
> Please choose the Technical Support command on the Visual C++
>  Help menu, or open the Technical Support help file for more information
> {noformat}
>
>
>

[Farid Zaripov-2]

> Did you happen to reduce this to a small test case and send
> it to Microsoft?

  Not yet. It's difficult to create the small test.

> Do you see the ICE in a specific test (or example), maybe only for a
> specific instantiation of the template, or does it happen regardless
> of the actual types of the template arguments?

  Today I've made some investigations:

1. the 25.heap, 25.partial.sort and 25.sort tests from trunk and 4.3.x branch
are compiled withoud ICE;

2. the only difference between preprocessed 25.heap tests from 4.2.x branch and trunk is

-----------------
Comparing files 42x.i and trunk.i
***** 42x.i
void  __declspec (noreturn)
__rw_assert_fail (const char*, const char*, int, const char*)
***** trunk.i
void
__rw_assert_fail (const char*, const char*, int, const char*)
*****
-----------------

3. removing _RWSTD_NORETURN from declaration of the __rw_assert_fail() eliminates
the ICE in tests from 4.2.x branch;

4. The __rw_assert_fail() is used in RandomAccessIter methods thus RW_ASSERT macro;

  So I guess, that MSVC issues ICE when processing "infinite" for-loop (loop without condition)
with __declspec (noreturn) function inside the loop.


> Btw., the reason I ask is so we can come up with a better/cleaner
> workaround, hopefully one that will be as efficient as the original
> code and won't need an #ifdef.

  I've just added condition in for-loop, to make the loop finite.
We can rewrite the loop the same way, as it's implemented in Dinkumware STL
(it's also fixes the ICE):

-----------
template<class _RanIt,
        class _Diff,
        class _Ty,
        class _Pr> inline
        void _Make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *, _Ty *)
        {       // make nontrivial [_First, _Last) into a heap, using _Pred
        _Diff _Bottom = _Last - _First;
        for (_Diff _Hole = _Bottom / 2; 0 < _Hole; )
                {       // reheap top half, bottom to top
                --_Hole;
                std::_Adjust_heap(_First, _Hole, _Bottom,
                        _Ty(*(_First + _Hole)), _Pred);
                }
        }
-----------


-------------
_EXPORT
template <class _RandomAccessIter, class _Compare, class _Dist>
void __make_heap (_RandomAccessIter __first, _RandomAccessIter __last,
                  _Compare __comp, _Dist*)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    const _Dist __dist = __last - __first;

    for (_Dist __parent = __dist / 2; 0 < __parent; ) {
        --__parent;
        __adjust_heap (__first, __parent, __dist, *(__first + __parent),
                       __comp);
    }
}
-------------

Farid.

[Martin Sebor]

Farid Zaripov-2 wrote:

> Did you happen to reduce this to a small test case and send
> it to Microsoft?

  Not yet. It's difficult to create the small test.

> Do you see the ICE in a specific test (or example), maybe only for a
> specific instantiation of the template, or does it happen regardless
> of the actual types of the template arguments?

  Today I've made some investigations:

1. the 25.heap, 25.partial.sort and 25.sort tests from trunk and 4.3.x branch
are compiled withoud ICE;

2. the only difference between preprocessed 25.heap tests from 4.2.x branch and trunk is

-----------------
Comparing files 42x.i and trunk.i
***** 42x.i
void  __declspec (noreturn)
__rw_assert_fail (const char*, const char*, int, const char*)
***** trunk.i
void
__rw_assert_fail (const char*, const char*, int, const char*)
*****
-----------------

3. removing _RWSTD_NORETURN from declaration of the __rw_assert_fail() eliminates
the ICE in tests from 4.2.x branch;

Thanks for looking into it! That's too bad about noreturn. It can help
the compiler generate better code so it would be a shame to have to
remove it. A test case might help us come up with a workaround and get
Microsoft to fix their compiler :)

4. The __rw_assert_fail() is used in RandomAccessIter methods thus RW_ASSERT macro;

  So I guess, that MSVC issues ICE when processing "infinite" for-loop (loop without condition)
with __declspec (noreturn) function inside the loop.


> Btw., the reason I ask is so we can come up with a better/cleaner
> workaround, hopefully one that will be as efficient as the original
> code and won't need an #ifdef.

  I've just added condition in for-loop, to make the loop finite.
We can rewrite the loop the same way, as it's implemented in Dinkumware STL
(it's also fixes the ICE):

...

_EXPORT
template <class _RandomAccessIter, class _Compare, class _Dist>
void __make_heap (_RandomAccessIter __first, _RandomAccessIter __last,
                  _Compare __comp, _Dist*)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    const _Dist __dist = __last - __first;

    for (_Dist __parent = __dist / 2; 0 < __parent; ) {
        --__parent;
        __adjust_heap (__first, __parent, __dist, *(__first + __parent),
                       __comp);
    }
}

This is close to what I had in mind when I saw the #ifdef but is it
the same thing? IIUC, in the original version, the loop will execute
at least once. In this version, it may not execute at all (i.e., if
__parent is zero). Or does it not matter? If not, this would seem
like an improvement over the original code irrespective of the ICE,
which is exactly what I was hoping for! :)

Martin

[Farid Zaripov-2]

> This is close to what I had in mind when I saw the #ifdef but is it
> the same thing? IIUC, in the original version, the loop will execute
> at least once. In this version, it may not execute at all (i.e., if
> __parent is zero).

  In the original version __parent is 0 only for __dist in [ 1; 2; 3 ].

  In this version __parent is 1 (will become 0 before calling __adjust_heap() due to
predecrement) for __dist in [ 2; 3 ].

  But when __dist == 1 (the heap contain's the exactly one element) there's no
sence to call __adjust_heap().

Farid.