Compiling the example code below with GCC 11.4.0 (I actually encountered this bug in all versions >= 11 which I tried but not in older ones) and -O2 (other optimization levels seem to work) results in an endless loop and finally a segmentation fault due to an out-of-bounds access. We can clearly argue about issues in the implementation of the bitfield class (it is based on a real implementation of such a class I encountered in existing codebase) but the main problem here is that the simple for loop in bug() is generated into an endless loop. I think regardless of how the test method is implemented, this loop should always terminate correctly. #include <cstdint> #include <cstddef> #include <array> #include <climits> template<size_t S> class bitfield { private: using Element = uint8_t; static constexpr uint32_t C = (S - 1u) / 8u; private: std::array<Element, C + 1> m_Array; public: bool test(size_t i) const { if (i >= S){ return false; } const size_t index = static_cast<uint32_t>(i) / 8u; const Element bitmask = 1u << (i % 8u); return (m_Array[index] & bitmask) != 0u; } }; void bug2(const bitfield<0x120u> &b) { if (!b.test(1u)) { volatile int test = 1; } } void bug(const bitfield<0x250u> &b) { for (uint16_t i = 0u; i < 0x250u; i++) { // this loop seems to not properly terminate if (!b.test(i)) { volatile int test = i; } } } int main() { bitfield<0x250u> b; bug(b); return 0; } Looking at the generated assembler code (in this example ARM64 generated in godbolt.org, the same issue is also present on my x86-64 machine) we can see, that the check for i < 0x250 is completely lost. Actually, at .L9 we do the increment of the loop variable and then unconditionally jump back to .L10 for the next iteration. bug(bitfield<592ul> const&): sub sp, sp, #16 mov w2, 0 mov w4, 1 .L10: lsr w3, w2, 3 and w1, w2, 7 lsl w1, w4, w1 ldrb w3, [x0, w3, uxtw] and w1, w1, w3 tst w1, 255 bne .L9 str w2, [sp, 12] .L9: add w2, w2, 1 b .L10 During testing of different variants of the code I encountered that there seem to be different (but totally unexpected) ways to solve the issue: - adding -fno-tree-vrp or -fno-guess-branch-probability - deleting method bug2 - changing the type of i to size_t
Note, that the volatile variables are just there to provide a minimal example and not have the entire loop optimized away. In the origian implementation I deduced this minimal example from, there was actually a useful implementation. But putting e.g. a std::cout at this place also solved the issue.
Confirmed. The issue is IPA ICF figures out that bitfield<288>::test and bitfield<592>::test are the same but really they are not due to the size being different. /app/example.cpp:18:10: optimized: Semantic equality hit:bool bitfield<S>::test(size_t) const [with long unsigned int S = 288]/60->bool bitfield<S>::test(size_t) const [with long unsigned int S = 592]/61 /app/example.cpp:18:10: optimized: Assembler symbol names:_ZNK8bitfieldILm288EE4testEm.part.0/60->_ZNK8bitfieldILm592EE4testEm.part.0/61
I will try bisect.
(In reply to Sam James from comment #3) > I will try bisect. Most likely r11-5094-gafa6adbd6c83ee or r11-4987-g602c6cfc79ce4a or r11-4986-ga1fdc16da34118 .
Well, ICF figures out the other part of the partial inlined test() are equal and I think they are. The if (i >= S){ return false; } tests are inlined and eliminated (I think correctly so). -fno-partial-inlining also avoids the issue. The issue is that ICF doesn't wipe (or compare) range info so we get after inlining: <bb 2> [local count: 10737416]: goto <bb 6>; [100.00%] <bb 3> [local count: 1063004409]: # RANGE [irange] long unsigned int [0, 591] NONZERO 0x3ff _5 = (long unsigned int) i_2; # RANGE [irange] unsigned int [0, 287] NONZERO 0x1ff _11 = (unsigned int) _5;
Honza - ICF seems to fixup points-to sets when merging variables, so there should be a way to kill off flow-sensitive info inside prevailing bodies as well. But would that happen before inlining the body? Can you work on that? I think comparing ranges would weaken ICF unnecessarily?
(In reply to Andrew Pinski from comment #4) > (In reply to Sam James from comment #3) > > I will try bisect. > > Most likely r11-5094-gafa6adbd6c83ee or r11-4987-g602c6cfc79ce4a or > r11-4986-ga1fdc16da34118 . r11-4987-g602c6cfc79ce4a is the first bad commit commit r11-4987-g602c6cfc79ce4a Author: Jan Hubicka <jh@suse.cz> Date: Fri Nov 13 15:58:41 2020 +0100 Improve handling of memory operands in ipa-icf 2/4
> Honza - ICF seems to fixup points-to sets when merging variables, so there > should be a way to kill off flow-sensitive info inside prevailing bodies > as well. But would that happen before inlining the body? Can you work > on that? I think comparing ranges would weaken ICF unnecessarily? AFAIK ICF does no changes to winning function body. It basically relies on the fact that early optimizations are local and thus arrive to same solutions for most of metadata. So only really easy fix is to make it match value ranges, too. I will check how much that fire in practice - I can only think of split funtions to diverge, which is probably not that bad in practice. IPA-prop and IPA-PTA is only done after ICF. We indeed discussed clearing possibility of merging alias sets which is relatively important in practice (increasing TBAA precision on LTO slowly degraded ICF effectivity significantly), but got into glory details of inventing representation which would make inliner to pick right body (without alias sets cleared). This was never made to fly (Martin got scared by the details and I got it on my ever overflowing TODO list). Honza
(In reply to Jan Hubicka from comment #8) > > Honza - ICF seems to fixup points-to sets when merging variables, so there > > should be a way to kill off flow-sensitive info inside prevailing bodies > > as well. But would that happen before inlining the body? Can you work > > on that? I think comparing ranges would weaken ICF unnecessarily? > > AFAIK ICF does no changes to winning function body. It basically relies > on the fact that early optimizations are local and thus arrive to same > solutions for most of metadata. So only really easy fix is to make it > match value ranges, too. I will check how much that fire in practice - > I can only think of split funtions to diverge, which is probably not > that bad in practice. But is it possible to add a local transform stage and would that also affect which body we inline? But yes, inlining the original body would be so much better ...
Tracking in 113907 as that one has more detail about the ICF vs Ranges issue, possible short and longer term solutions, etc. *** This bug has been marked as a duplicate of bug 113907 ***