[Tree][Static Analyzer] Tree representing types and svalues type
Hi David, hi all, I was playing along with APIs from the Static Analyzer and encountered a segfault in gcc/tree.cc:5068 (i.e. in function build2 and failure is due to a gcc_assert call), after a call to ana::region_model::get_representative_tree. >From my debugging of the problem, I realized that the svalue which I built with the SA API as the following from an element_region (C sample): const ana::region *base = elm_reg->get_base_region(); // base_ptr is the svalue passed to get_representative_tree const ana::svalue *base_ptr = base->get_ptr_svalue( TYPE_POINTER_TO(base->get_type), base); I realized that the SA resulting in the call to get_ptr_svalue has NULL_TREE as type (return by get_type on base_ptr). And this is because TYPE_POINTER_TO (base->get_type) is returning a NULL_TREE. I found my way around by calling build_pointer_type(base->get_type()) which is currently building the expecting type. But from this, two questions raised in my mind: 1. Is it coherent for the ana::region_model_manager::get_ptr_svalue to return a sval with a null type? 2. Can a tree view as a tree_type_common member have an uninitialized pointer_to member? I think, but definitely not sure) that the member is not initialized here by some part of the compiler, because I think that the inner type of regions and svalues are build by the SA by using the TREE_TYPE macro directly from the GIMPLE. I ask this question to know if this is a bug and I should try to do a minimal example out of it, or if it is a intended behavior for any reason from the compiler. Thank you for reading me, Pierrick
[PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin
Hi.
When I implemented a hash table with reference to the C++ STL, I found that
when the hash table in the C++ STL deletes elements, if the first element
deleted is the begin element, the before begin node is repeatedly assigned.
This creates unnecessary performance overhead.
First, let’s see the code implementation:
In _M_remove_bucket_begin, _M_before_begin._M_nxt is assigned when
&_M_before_begin == _M_buckets[__bkt]. That also means
_M_buckets[__bkt]->_M_nxt is assigned under some conditions.
_M_remove_bucket_begin is called by _M_erase and _M_extract_node:
1. Case _M_erase a range: _M_remove_bucket_begin is called in a for loop
when __is_bucket_begin is true. And if __is_bucket_begin is true and
&_M_before_begin == _M_buckets[__bkt], __prev_n must be &_M_before_begin.
__prev_n->_M_nxt is always assigned in _M_erase. That means
_M_before_begin._M_nxt is always assigned, if _M_remove_bucket_begin is
called and &_M_before_begin == _M_buckets[__bkt]. So there’s no need to
assign _M_before_begin._M_nxt in _M_remove_bucket_begin.
2. Other cases: _M_remove_bucket_begin is called when __prev_n ==
_M_buckets[__bkt]. And __prev_n->_M_nxt is always assigned in _M_erase and
_M_before_begin. That means _M_buckets[__bkt]->_M_nxt is always assigned.
So there's no need to assign _M_buckets[__bkt]->_M_nxt in
_M_remove_bucket_begin.
In summary, there’s no need to check &_M_before_begin == _M_buckets[__bkt]
and assign _M_before_begin._M_nxt in _M_remove_bucket_begin.
Then let’s see the responsibility of each method:
The hash table in the C++ STL is composed of hash buckets and a node list.
The update of the node list is responsible for _M_erase and _M_extract_node
method. _M_remove_bucket_begin method only needs to update the hash
buckets. The update of _M_before_begin belongs to the update of the node
list. So _M_remove_bucket_begin doesn’t need to update _M_before_begin.
Existing tests listed below cover this change:
23_containers/unordered_set/allocator/copy.cc
23_containers/unordered_set/allocator/copy_assign.cc
23_containers/unordered_set/allocator/move.cc
23_containers/unordered_set/allocator/move_assign.cc
23_containers/unordered_set/allocator/swap.cc
23_containers/unordered_set/erase/1.cc
23_containers/unordered_set/erase/24061-set.cc
23_containers/unordered_set/modifiers/extract.cc
23_containers/unordered_set/operations/count.cc
23_containers/unordered_set/requirements/exception/basic.cc
23_containers/unordered_map/allocator/copy.cc
23_containers/unordered_map/allocator/copy_assign.cc
23_containers/unordered_map/allocator/move.cc
23_containers/unordered_map/allocator/move_assign.cc
23_containers/unordered_map/allocator/swap.cc
23_containers/unordered_map/erase/1.cc
23_containers/unordered_map/erase/24061-map.cc
23_containers/unordered_map/modifiers/extract.cc
23_containers/unordered_map/modifiers/move_assign.cc
23_containers/unordered_map/operations/count.cc
23_containers/unordered_map/requirements/exception/basic.cc
Regression tested on x86_64-pc-linux-gnu. Is it OK to commit?
---
diff --git a/libstdc++-v3/include/bits/hashtable.h
b/libstdc++-v3/include/bits/hashtable.h
index b48610036fa..6056639e663 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -872,13 +872,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__next_n || __next_bkt != __bkt)
{
// Bucket is now empty
- // First update next bucket if any
+ // Update next bucket if any
if (__next_n)
_M_buckets[__next_bkt] = _M_buckets[__bkt];
- // Second update before begin node if necessary
- if (&_M_before_begin == _M_buckets[__bkt])
- _M_before_begin._M_nxt = __next_n;
_M_buckets[__bkt] = nullptr;
}
}
no-need-to-update-before-begin-node.diff
Description: Binary data
Re: [PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin
Huanghui Nie writes: > Hi. Please CC the libstdc++ LM for libstdc++ patches, per https://gcc.gnu.org/onlinedocs/libstdc++/manual/appendix_contributing.html#list.patches. > [...]
