cprover
local_may_alias.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Field-insensitive, location-sensitive may-alias analysis
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
11 
12 #ifndef CPROVER_ANALYSES_LOCAL_MAY_ALIAS_H
13 #define CPROVER_ANALYSES_LOCAL_MAY_ALIAS_H
14 
15 #include <stack>
16 #include <memory>
17 
18 #include <util/union_find.h>
19 
20 #include "locals.h"
21 #include "dirty.h"
22 #include "local_cfg.h"
23 
25 {
26 public:
28 
29  explicit local_may_aliast(
30  const goto_functiont &_goto_function):
31  dirty(_goto_function),
32  locals(_goto_function),
33  cfg(_goto_function.body)
34  {
35  build(_goto_function);
36  }
37 
38  void output(
39  std::ostream &out,
40  const goto_functiont &goto_function,
41  const namespacet &ns) const;
42 
46 
47  // given a pointer, returns possible aliases
48  std::set<exprt> get(
50  const exprt &src) const;
51 
52  // returns 'true' when pointers src1 and src2 may be aliases
53  bool aliases(
55  const exprt &src1, const exprt &src2) const;
56 
57 protected:
58  void build(const goto_functiont &goto_function);
59 
60  typedef std::stack<local_cfgt::node_nrt> work_queuet;
61 
63 
65 
66  // the information tracked per program location
67  class loc_infot
68  {
69  public:
71 
72  bool merge(const loc_infot &src);
73  };
74 
75  typedef std::vector<loc_infot> loc_infost;
77 
78  void assign_lhs(
79  const exprt &lhs,
80  const exprt &rhs,
81  const loc_infot &loc_info_src,
82  loc_infot &loc_info_dest);
83 
84  typedef std::set<unsigned> object_sett;
85 
86  void get_rec(
87  object_sett &dest,
88  const exprt &rhs,
89  const loc_infot &loc_info_src) const;
90 
91  unsigned unknown_object;
92 };
93 
95 {
96 public:
98  {
99  }
100 
101  void operator()(const goto_functionst &_goto_functions)
102  {
103  goto_functions=&_goto_functions;
104 
105  forall_goto_functions(f_it, _goto_functions)
106  forall_goto_program_instructions(i_it, f_it->second.body)
107  target_map[i_it]=f_it->first;
108  }
109 
111  {
112  PRECONDITION(goto_functions!=nullptr);
113  fkt_mapt::iterator f_it=fkt_map.find(fkt);
114  if(f_it!=fkt_map.end())
115  return *f_it->second;
116 
117  goto_functionst::function_mapt::const_iterator f_it2=
118  goto_functions->function_map.find(fkt);
119  assert(f_it2!=goto_functions->function_map.end());
120  return *(fkt_map[fkt]=std::unique_ptr<local_may_aliast>(
121  new local_may_aliast(f_it2->second)));
122  }
123 
125  {
126  target_mapt::const_iterator t_it=
127  target_map.find(t);
128  assert(t_it!=target_map.end());
129  return operator()(t_it->second);
130  }
131 
132  std::set<exprt> get(
134  const exprt &src) const;
135 
136 protected:
138  typedef std::map<irep_idt, std::unique_ptr<local_may_aliast> > fkt_mapt;
140 
141  typedef std::map<goto_programt::const_targett, irep_idt > target_mapt;
143 };
144 
145 #endif // CPROVER_ANALYSES_LOCAL_MAY_ALIAS_H
std::map< irep_idt, std::unique_ptr< local_may_aliast > > fkt_mapt
Variables whose address is taken.
const goto_functionst * goto_functions
std::set< unsigned > object_sett
goto_functionst::goto_functiont goto_functiont
Definition: locals.h:19
std::stack< local_cfgt::node_nrt > work_queuet
bool merge(const loc_infot &src)
std::map< goto_programt::const_targett, irep_idt > target_mapt
CFG for One Function.
void build(const goto_functiont &goto_function)
instructionst::const_iterator const_targett
unsigned_union_find alias_sett
loc_infost loc_infos
TO_BE_DOCUMENTED.
Definition: namespace.h:62
#define PRECONDITION(CONDITION)
Definition: invariant.h:225
goto_function_templatet< goto_programt > goto_functiont
unsigned unknown_object
Base class for all expressions.
Definition: expr.h:46
void operator()(const goto_functionst &_goto_functions)
local_may_aliast(const goto_functiont &_goto_function)
Definition: dirty.h:22
void assign_lhs(const exprt &lhs, const exprt &rhs, const loc_infot &loc_info_src, loc_infot &loc_info_dest)
local_may_aliast & operator()(goto_programt::const_targett t)
numbering< exprt > objects
bool aliases(const goto_programt::const_targett t, const exprt &src1, const exprt &src2) const
std::vector< loc_infot > loc_infost
local_may_aliast & operator()(const irep_idt &fkt)
Local variables whose address is taken.
void output(std::ostream &out, const goto_functiont &goto_function, const namespacet &ns) const
#define forall_goto_functions(it, functions)
#define forall_goto_program_instructions(it, program)
Definition: goto_program.h:68
void get_rec(object_sett &dest, const exprt &rhs, const loc_infot &loc_info_src) const