[Bug c++/81929] New: exponential slowdown in undefined behavior sanitizer for streaming

["patrick.a.moran at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>]

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

            Bug ID: 81929
           Summary: exponential slowdown in undefined behavior sanitizer
                    for streaming
           Product: gcc
           Version: 7.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: patrick.a.moran at gmail dot com
  Target Milestone: ---

Created attachment 42028
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=42028&action=edit
A reproduction of the issue described

I've attached a reproduction. The trigger for the behavior we identified is:

 * To stream a number of ints (or other numeric types) into a
std::ostringstream
 * To call .str() on that std::ostringstream
 * To do all of the above in a single expression
 * Build with -fsanitize=undefined

It seems that all the above conditions are necessary - the problem vanishes if
you:
 * Split the same logic into multiple logical lines of code
 * Call some member function other than .str() (like .rdbuf())
 * Stream string literals instead of numeric types
 * Compile without -fsanitize=undefined

The behavior we see is a compile-time that seems to grow as roughly 4^n, where
n is the number of ints being streamed in. On my box

10 numbers =   0.671s
11 numbers =   1.608s
12 numbers =   5.356s
13 numbers =  20.250s
14 numbers =  80.163s
15 numbers = 318.994s

Salient output from perf record / perf report:

# Overhead  Command       Shared Object                      Symbol
# ........  ............  ................................. 
........................................................................................................................................
#
    59.95%  cc1plus       cc1plus                            [.]
walk_tree_1(tree_node**, tree_node* (*)(tree_node**, int*, void*), void*,
hash_set<tree_node*, default_hash_traits<tree_node*> >*, tree_node*
(*)(tree_node**, int*, tree_node* (*)(tree_node**, int*, void*), void*,
hash_set<tree_node*, default_hash_traits<tree_node*> >*))
    23.54%  cc1plus       cc1plus                            [.]
replace_placeholders_r(tree_node**, int*, void*)
    14.87%  cc1plus       cc1plus                            [.]
cp_walk_subtrees(tree_node**, int*, tree_node* (*)(tree_node**, int*, void*),
void*, hash_set<tree_node*, default_hash_traits<tree_node*> >*)
     0.07%  cc1plus       cc1plus                            [.]
push_to_top_level()
     0.06%  cc1plus       [kernel.kallsyms]                  [k] clear_page_c_e
     0.04%  cc1plus       cc1plus                            [.]
lookup_name_real(tree_node*, int, int, bool, int, int)