Automatic date update in version.in
[external/binutils.git] / gdb / dwarf2-frame-tailcall.c
1 /* Virtual tail call frames unwinder for GDB.
2
3    Copyright (C) 2010-2018 Free Software Foundation, Inc.
4
5    This file is part of GDB.
6
7    This program is free software; you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 3 of the License, or
10    (at your option) any later version.
11
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
19
20 #include "defs.h"
21 #include "frame.h"
22 #include "dwarf2-frame-tailcall.h"
23 #include "dwarf2loc.h"
24 #include "frame-unwind.h"
25 #include "block.h"
26 #include "hashtab.h"
27 #include "gdbtypes.h"
28 #include "regcache.h"
29 #include "value.h"
30 #include "dwarf2-frame.h"
31
32 /* Contains struct tailcall_cache indexed by next_bottom_frame.  */
33 static htab_t cache_htab;
34
35 /* Associate structure of the unwinder to call_site_chain.  Lifetime of this
36    structure is maintained by REFC decremented by dealloc_cache, all of them
37    get deleted during reinit_frame_cache.  */
38 struct tailcall_cache
39 {
40   /* It must be the first one of this struct.  It is the furthest callee.  */
41   struct frame_info *next_bottom_frame;
42
43   /* Reference count.  The whole chain of virtual tail call frames shares one
44      tailcall_cache.  */
45   int refc;
46
47   /* Associated found virtual taill call frames chain, it is never NULL.  */
48   struct call_site_chain *chain;
49
50   /* Cached pretended_chain_levels result.  */
51   int chain_levels;
52
53   /* Unwound PC from the top (caller) frame, as it is not contained
54      in CHAIN.  */
55   CORE_ADDR prev_pc;
56
57   /* Compensate SP in caller frames appropriately.  prev_sp and
58      entry_cfa_sp_offset are valid only if PREV_SP_P.  PREV_SP is SP at the top
59      (caller) frame.  ENTRY_CFA_SP_OFFSET is shift of SP in tail call frames
60      against next_bottom_frame SP.  */
61   unsigned prev_sp_p : 1;
62   CORE_ADDR prev_sp;
63   LONGEST entry_cfa_sp_offset;
64 };
65
66 /* hash_f for htab_create_alloc of cache_htab.  */
67
68 static hashval_t
69 cache_hash (const void *arg)
70 {
71   const struct tailcall_cache *cache = (const struct tailcall_cache *) arg;
72
73   return htab_hash_pointer (cache->next_bottom_frame);
74 }
75
76 /* eq_f for htab_create_alloc of cache_htab.  */
77
78 static int
79 cache_eq (const void *arg1, const void *arg2)
80 {
81   const struct tailcall_cache *cache1 = (const struct tailcall_cache *) arg1;
82   const struct tailcall_cache *cache2 = (const struct tailcall_cache *) arg2;
83
84   return cache1->next_bottom_frame == cache2->next_bottom_frame;
85 }
86
87 /* Create new tailcall_cache for NEXT_BOTTOM_FRAME, NEXT_BOTTOM_FRAME must not
88    yet have been indexed by cache_htab.  Caller holds one reference of the new
89    tailcall_cache.  */
90
91 static struct tailcall_cache *
92 cache_new_ref1 (struct frame_info *next_bottom_frame)
93 {
94   struct tailcall_cache *cache = XCNEW (struct tailcall_cache);
95   void **slot;
96
97   cache->next_bottom_frame = next_bottom_frame;
98   cache->refc = 1;
99
100   slot = htab_find_slot (cache_htab, cache, INSERT);
101   gdb_assert (*slot == NULL);
102   *slot = cache;
103
104   return cache;
105 }
106
107 /* Create new reference to CACHE.  */
108
109 static void
110 cache_ref (struct tailcall_cache *cache)
111 {
112   gdb_assert (cache->refc > 0);
113
114   cache->refc++;
115 }
116
117 /* Drop reference to CACHE, possibly fully freeing it and unregistering it from
118    cache_htab.  */
119
120 static void
121 cache_unref (struct tailcall_cache *cache)
122 {
123   gdb_assert (cache->refc > 0);
124
125   if (!--cache->refc)
126     {
127       gdb_assert (htab_find_slot (cache_htab, cache, NO_INSERT) != NULL);
128       htab_remove_elt (cache_htab, cache);
129
130       xfree (cache->chain);
131       xfree (cache);
132     }
133 }
134
135 /* Return 1 if FI is a non-bottom (not the callee) tail call frame.  Otherwise
136    return 0.  */
137
138 static int
139 frame_is_tailcall (struct frame_info *fi)
140 {
141   return frame_unwinder_is (fi, &dwarf2_tailcall_frame_unwind);
142 }
143
144 /* Try to find tailcall_cache in cache_htab if FI is a part of its virtual tail
145    call chain.  Otherwise return NULL.  No new reference is created.  */
146
147 static struct tailcall_cache *
148 cache_find (struct frame_info *fi)
149 {
150   struct tailcall_cache *cache;
151   void **slot;
152
153   while (frame_is_tailcall (fi))
154     {
155       fi = get_next_frame (fi);
156       gdb_assert (fi != NULL);
157     }
158
159   slot = htab_find_slot (cache_htab, &fi, NO_INSERT);
160   if (slot == NULL)
161     return NULL;
162
163   cache = (struct tailcall_cache *) *slot;
164   gdb_assert (cache != NULL);
165   return cache;
166 }
167
168 /* Number of virtual frames between THIS_FRAME and CACHE->NEXT_BOTTOM_FRAME.
169    If THIS_FRAME is CACHE-> NEXT_BOTTOM_FRAME return -1.  */
170
171 static int
172 existing_next_levels (struct frame_info *this_frame,
173                       struct tailcall_cache *cache)
174 {
175   int retval = (frame_relative_level (this_frame)
176                 - frame_relative_level (cache->next_bottom_frame) - 1);
177
178   gdb_assert (retval >= -1);
179
180   return retval;
181 }
182
183 /* The number of virtual tail call frames in CHAIN.  With no virtual tail call
184    frames the function would return 0 (but CHAIN does not exist in such
185    case).  */
186
187 static int
188 pretended_chain_levels (struct call_site_chain *chain)
189 {
190   int chain_levels;
191
192   gdb_assert (chain != NULL);
193
194   if (chain->callers == chain->length && chain->callees == chain->length)
195     return chain->length;
196
197   chain_levels = chain->callers + chain->callees;
198   gdb_assert (chain_levels <= chain->length);
199
200   return chain_levels;
201 }
202
203 /* Implementation of frame_this_id_ftype.  THIS_CACHE must be already
204    initialized with tailcall_cache, THIS_FRAME must be a part of THIS_CACHE.
205
206    Specific virtual tail call frames are tracked by INLINE_DEPTH.  */
207
208 static void
209 tailcall_frame_this_id (struct frame_info *this_frame, void **this_cache,
210                         struct frame_id *this_id)
211 {
212   struct tailcall_cache *cache = (struct tailcall_cache *) *this_cache;
213   struct frame_info *next_frame;
214
215   /* Tail call does not make sense for a sentinel frame.  */
216   next_frame = get_next_frame (this_frame);
217   gdb_assert (next_frame != NULL);
218
219   *this_id = get_frame_id (next_frame);
220   (*this_id).code_addr = get_frame_pc (this_frame);
221   (*this_id).code_addr_p = 1;
222   (*this_id).artificial_depth = (cache->chain_levels
223                                  - existing_next_levels (this_frame, cache));
224   gdb_assert ((*this_id).artificial_depth > 0);
225 }
226
227 /* Find PC to be unwound from THIS_FRAME.  THIS_FRAME must be a part of
228    CACHE.  */
229
230 static CORE_ADDR
231 pretend_pc (struct frame_info *this_frame, struct tailcall_cache *cache)
232 {
233   int next_levels = existing_next_levels (this_frame, cache);
234   struct call_site_chain *chain = cache->chain;
235
236   gdb_assert (chain != NULL);
237
238   next_levels++;
239   gdb_assert (next_levels >= 0);
240
241   if (next_levels < chain->callees)
242     return chain->call_site[chain->length - next_levels - 1]->pc;
243   next_levels -= chain->callees;
244
245   /* Otherwise CHAIN->CALLEES are already covered by CHAIN->CALLERS.  */
246   if (chain->callees != chain->length)
247     {
248       if (next_levels < chain->callers)
249         return chain->call_site[chain->callers - next_levels - 1]->pc;
250       next_levels -= chain->callers;
251     }
252
253   gdb_assert (next_levels == 0);
254   return cache->prev_pc;
255 }
256
257 /* Implementation of frame_prev_register_ftype.  If no specific register
258    override is supplied NULL is returned (this is incompatible with
259    frame_prev_register_ftype semantics).  next_bottom_frame and tail call
260    frames unwind the NULL case differently.  */
261
262 struct value *
263 dwarf2_tailcall_prev_register_first (struct frame_info *this_frame,
264                                      void **tailcall_cachep, int regnum)
265 {
266   struct gdbarch *this_gdbarch = get_frame_arch (this_frame);
267   struct tailcall_cache *cache = (struct tailcall_cache *) *tailcall_cachep;
268   CORE_ADDR addr;
269
270   if (regnum == gdbarch_pc_regnum (this_gdbarch))
271     addr = pretend_pc (this_frame, cache);
272   else if (cache->prev_sp_p && regnum == gdbarch_sp_regnum (this_gdbarch))
273     {
274       int next_levels = existing_next_levels (this_frame, cache);
275
276       if (next_levels == cache->chain_levels - 1)
277         addr = cache->prev_sp;
278       else
279         addr = dwarf2_frame_cfa (this_frame) - cache->entry_cfa_sp_offset;
280     }
281   else
282     return NULL;
283
284   return frame_unwind_got_address (this_frame, regnum, addr);
285 }
286
287 /* Implementation of frame_prev_register_ftype for tail call frames.  Register
288    set of virtual tail call frames is assumed to be the one of the top (caller)
289    frame - assume unchanged register value for NULL from
290    dwarf2_tailcall_prev_register_first.  */
291
292 static struct value *
293 tailcall_frame_prev_register (struct frame_info *this_frame,
294                                void **this_cache, int regnum)
295 {
296   struct tailcall_cache *cache = (struct tailcall_cache *) *this_cache;
297   struct value *val;
298
299   gdb_assert (this_frame != cache->next_bottom_frame);
300
301   val = dwarf2_tailcall_prev_register_first (this_frame, this_cache, regnum);
302   if (val)
303     return val;
304
305   return frame_unwind_got_register (this_frame, regnum, regnum);
306 }
307
308 /* Implementation of frame_sniffer_ftype.  It will never find a new chain, use
309    dwarf2_tailcall_sniffer_first for the bottom (callee) frame.  It will find
310    all the predecessing virtual tail call frames, it will return false when
311    there exist no more tail call frames in this chain.  */
312
313 static int
314 tailcall_frame_sniffer (const struct frame_unwind *self,
315                          struct frame_info *this_frame, void **this_cache)
316 {
317   struct frame_info *next_frame;
318   int next_levels;
319   struct tailcall_cache *cache;
320
321   if (!dwarf2_frame_unwinders_enabled_p)
322     return 0;
323
324   /* Inner tail call element does not make sense for a sentinel frame.  */
325   next_frame = get_next_frame (this_frame);
326   if (next_frame == NULL)
327     return 0;
328
329   cache = cache_find (next_frame);
330   if (cache == NULL)
331     return 0;
332
333   cache_ref (cache);
334
335   next_levels = existing_next_levels (this_frame, cache);
336
337   /* NEXT_LEVELS is -1 only in dwarf2_tailcall_sniffer_first.  */
338   gdb_assert (next_levels >= 0);
339   gdb_assert (next_levels <= cache->chain_levels);
340
341   if (next_levels == cache->chain_levels)
342     {
343       cache_unref (cache);
344       return 0;
345     }
346
347   *this_cache = cache;
348   return 1;
349 }
350
351 /* The initial "sniffer" whether THIS_FRAME is a bottom (callee) frame of a new
352    chain to create.  Keep TAILCALL_CACHEP NULL if it did not find any chain,
353    initialize it otherwise.  No tail call chain is created if there are no
354    unambiguous virtual tail call frames to report.
355    
356    ENTRY_CFA_SP_OFFSETP is NULL if no special SP handling is possible,
357    otherwise *ENTRY_CFA_SP_OFFSETP is the number of bytes to subtract from tail
358    call frames frame base to get the SP value there - to simulate return
359    address pushed on the stack.  */
360
361 void
362 dwarf2_tailcall_sniffer_first (struct frame_info *this_frame,
363                                void **tailcall_cachep,
364                                const LONGEST *entry_cfa_sp_offsetp)
365 {
366   CORE_ADDR prev_pc = 0, prev_sp = 0;   /* GCC warning.  */
367   int prev_sp_p = 0;
368   CORE_ADDR this_pc;
369   struct gdbarch *prev_gdbarch;
370   struct call_site_chain *chain = NULL;
371   struct tailcall_cache *cache;
372
373   gdb_assert (*tailcall_cachep == NULL);
374
375   /* PC may be after the function if THIS_FRAME calls noreturn function,
376      get_frame_address_in_block will decrease it by 1 in such case.  */
377   this_pc = get_frame_address_in_block (this_frame);
378
379   /* Catch any unwinding errors.  */
380   TRY
381     {
382       int sp_regnum;
383
384       prev_gdbarch = frame_unwind_arch (this_frame);
385
386       /* Simulate frame_unwind_pc without setting this_frame->prev_pc.p.  */
387       prev_pc = gdbarch_unwind_pc (prev_gdbarch, this_frame);
388
389       /* call_site_find_chain can throw an exception.  */
390       chain = call_site_find_chain (prev_gdbarch, prev_pc, this_pc);
391
392       if (entry_cfa_sp_offsetp != NULL)
393         {
394           sp_regnum = gdbarch_sp_regnum (prev_gdbarch);
395           if (sp_regnum != -1)
396             {
397               prev_sp = frame_unwind_register_unsigned (this_frame, sp_regnum);
398               prev_sp_p = 1;
399             }
400         }
401     }
402   CATCH (except, RETURN_MASK_ERROR)
403     {
404       if (entry_values_debug)
405         exception_print (gdb_stdout, except);
406       return;
407     }
408   END_CATCH
409
410   /* Ambiguous unwind or unambiguous unwind verified as matching.  */
411   if (chain == NULL || chain->length == 0)
412     {
413       xfree (chain);
414       return;
415     }
416
417   cache = cache_new_ref1 (this_frame);
418   *tailcall_cachep = cache;
419   cache->chain = chain;
420   cache->prev_pc = prev_pc;
421   cache->chain_levels = pretended_chain_levels (chain);
422   cache->prev_sp_p = prev_sp_p;
423   if (cache->prev_sp_p)
424     {
425       cache->prev_sp = prev_sp;
426       cache->entry_cfa_sp_offset = *entry_cfa_sp_offsetp;
427     }
428   gdb_assert (cache->chain_levels > 0);
429 }
430
431 /* Implementation of frame_dealloc_cache_ftype.  It can be called even for the
432    bottom chain frame from dwarf2_frame_dealloc_cache which is not a real
433    TAILCALL_FRAME.  */
434
435 static void
436 tailcall_frame_dealloc_cache (struct frame_info *self, void *this_cache)
437 {
438   struct tailcall_cache *cache = (struct tailcall_cache *) this_cache;
439
440   cache_unref (cache);
441 }
442
443 /* Implementation of frame_prev_arch_ftype.  We assume all the virtual tail
444    call frames have gdbarch of the bottom (callee) frame.  */
445
446 static struct gdbarch *
447 tailcall_frame_prev_arch (struct frame_info *this_frame,
448                           void **this_prologue_cache)
449 {
450   struct tailcall_cache *cache = (struct tailcall_cache *) *this_prologue_cache;
451
452   return get_frame_arch (cache->next_bottom_frame);
453 }
454
455 /* Virtual tail call frame unwinder if dwarf2_tailcall_sniffer_first finds
456    a chain to create.  */
457
458 const struct frame_unwind dwarf2_tailcall_frame_unwind =
459 {
460   TAILCALL_FRAME,
461   default_frame_unwind_stop_reason,
462   tailcall_frame_this_id,
463   tailcall_frame_prev_register,
464   NULL,
465   tailcall_frame_sniffer,
466   tailcall_frame_dealloc_cache,
467   tailcall_frame_prev_arch
468 };
469
470 void
471 _initialize_tailcall_frame (void)
472 {
473   cache_htab = htab_create_alloc (50, cache_hash, cache_eq, NULL, xcalloc,
474                                   xfree);
475 }