cprover
count_eloc.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Count effective lines of code
4 
5 Author: Michael Tautschnig
6 
7 Date: December 2012
8 
9 \*******************************************************************/
10 
13 
14 #include "count_eloc.h"
15 
16 #include <iostream>
17 #include <unordered_set>
18 
19 #include <util/file_util.h>
20 #include <util/pointer_expr.h>
22 #include <util/prefix.h>
23 
24 #include <goto-programs/cfg.h>
26 
28 
29 typedef std::unordered_set<irep_idt> linest;
30 typedef std::unordered_map<irep_idt, linest> filest;
31 typedef std::unordered_map<irep_idt, filest> working_dirst;
32 
33 static void collect_eloc(
34  const goto_modelt &goto_model,
35  working_dirst &dest)
36 {
37  for(const auto &gf_entry : goto_model.goto_functions.function_map)
38  {
39  for(const auto &instruction : gf_entry.second.body.instructions)
40  {
41  const auto &source_location = instruction.source_location;
42 
43  filest &files = dest[source_location.get_working_directory()];
44  const irep_idt &file = source_location.get_file();
45 
46  if(!file.empty() && !source_location.is_built_in())
47  {
48  files[file].insert(source_location.get_line());
49  }
50  }
51  }
52 }
53 
54 void count_eloc(const goto_modelt &goto_model)
55 {
56  std::size_t eloc=0;
57 
58  working_dirst eloc_map;
59  collect_eloc(goto_model, eloc_map);
60 
61  for(auto const &files : eloc_map)
62  for(auto const &lines : files.second)
63  eloc+=lines.second.size();
64 
65  std::cout << "Effective lines of code: " << eloc << '\n';
66 }
67 
68 void list_eloc(const goto_modelt &goto_model)
69 {
70  working_dirst eloc_map;
71  collect_eloc(goto_model, eloc_map);
72 
73  for(auto const &files : eloc_map)
74  for(auto const &lines : files.second)
75  {
76  std::string file=id2string(lines.first);
77  if(!files.first.empty())
78  file=concat_dir_file(id2string(files.first), file);
79 
80  for(const irep_idt &line : lines.second)
81  std::cout << file << ':' << line << '\n';
82  }
83 }
84 
85 void print_path_lengths(const goto_modelt &goto_model)
86 {
87  const irep_idt &entry_point=goto_model.goto_functions.entry_point();
88  goto_functionst::function_mapt::const_iterator start=
89  goto_model.goto_functions.function_map.find(entry_point);
90 
91  if(start==goto_model.goto_functions.function_map.end() ||
92  !start->second.body_available())
93  {
94  std::cout << "No entry point found, path length undefined\n";
95  return;
96  }
97 
98  struct visited_cfg_nodet
99  {
100  bool visited;
101 
102  visited_cfg_nodet():visited(false)
103  {
104  }
105  };
106 
107  typedef cfg_baset<visited_cfg_nodet> cfgt;
108  cfgt cfg;
109  cfg(goto_model.goto_functions);
110 
111  const goto_programt &start_program=start->second.body;
112 
113  const cfgt::entryt &start_node =
114  cfg.get_node_index(start_program.instructions.begin());
115  const cfgt::entryt &last_node =
116  cfg.get_node_index(--start_program.instructions.end());
117 
118  cfgt::patht shortest_path;
119  cfg.shortest_path(start_node, last_node, shortest_path);
120  std::cout << "Shortest control-flow path: " << shortest_path.size()
121  << " instructions\n";
122 
123  std::size_t n_loops=0, loop_ins=0;
124  for(const auto &gf_entry : goto_model.goto_functions.function_map)
125  {
126  forall_goto_program_instructions(i_it, gf_entry.second.body)
127  {
128  // loops or recursion
129  if(
130  i_it->is_backwards_goto() ||
131  i_it == gf_entry.second.body.instructions.begin())
132  {
133  const cfgt::entryt &node = cfg.get_node_index(i_it);
134  cfgt::patht loop;
135  cfg.shortest_loop(node, loop);
136 
137  if(!loop.empty())
138  {
139  ++n_loops;
140  loop_ins+=loop.size()-1;
141  }
142  }
143  }
144  }
145 
146  if(n_loops>0)
147  std::cout << "Loop information: " << n_loops << " loops, "
148  << loop_ins << " instructions in shortest paths of loop bodies\n";
149 
150  std::size_t n_reachable=0;
151  cfg.visit_reachable(start_node);
152  for(std::size_t i=0; i<cfg.size(); ++i)
153  if(cfg[i].visited)
154  ++n_reachable;
155  std::cout << "Reachable instructions: " << n_reachable << "\n";
156 }
157 
158 void print_global_state_size(const goto_modelt &goto_model)
159 {
160  const namespacet ns(goto_model.symbol_table);
161 
162  // if we have a linked object, only account for those that are used
163  // (slice-global-inits may have been used to avoid unnecessary initialization)
164  goto_functionst::function_mapt::const_iterator f_it =
166  const bool has_initialize =
167  f_it != goto_model.goto_functions.function_map.end();
168  std::unordered_set<irep_idt> initialized;
169 
170  if(has_initialize)
171  {
172  for(const auto &ins : f_it->second.body.instructions)
173  {
174  if(ins.is_assign())
175  {
176  const code_assignt &code_assign = ins.get_assign();
178  ode.build(code_assign.lhs(), ns);
179 
180  if(ode.root_object().id() == ID_symbol)
181  {
182  const symbol_exprt &symbol_expr = to_symbol_expr(ode.root_object());
183  initialized.insert(symbol_expr.get_identifier());
184  }
185  }
186  }
187  }
188 
189  mp_integer total_size = 0;
190 
191  for(const auto &symbol_entry : goto_model.symbol_table.symbols)
192  {
193  const symbolt &symbol = symbol_entry.second;
194  if(
195  symbol.is_type || symbol.is_macro || symbol.type.id() == ID_code ||
196  symbol.type.get_bool(ID_C_constant) ||
198  (has_initialize && initialized.find(symbol.name) == initialized.end()))
199  {
200  continue;
201  }
202 
203  const auto bits = pointer_offset_bits(symbol.type, ns);
204  if(bits.has_value() && bits.value() > 0)
205  total_size += bits.value();
206  }
207 
208  std::cout << "Total size of global objects: " << total_size << " bits\n";
209 }
Control Flow Graph.
A multi-procedural control flow graph (CFG) whose nodes store references to instructions in a GOTO pr...
Definition: cfg.h:87
A codet representing an assignment in the program.
Definition: std_code.h:295
exprt & lhs()
Definition: std_code.h:312
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
function_mapt function_map
static irep_idt entry_point()
Get the identifier of the entry point to a goto model.
symbol_tablet symbol_table
Symbol table.
Definition: goto_model.h:30
goto_functionst goto_functions
GOTO functions.
Definition: goto_model.h:33
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:74
instructionst instructions
The list of instructions in the goto program.
Definition: goto_program.h:556
bool get_bool(const irep_namet &name) const
Definition: irep.cpp:64
const irep_idt & id() const
Definition: irep.h:407
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:92
Split an expression into a base object and a (byte) offset.
Definition: pointer_expr.h:21
const exprt & root_object() const
void build(const exprt &expr, const namespacet &ns)
Given an expression expr, attempt to find the underlying object it represents by skipping over type c...
Expression to hold a symbol (variable)
Definition: std_expr.h:81
const irep_idt & get_identifier() const
Definition: std_expr.h:110
const symbolst & symbols
Read-only field, used to look up symbols given their names.
Symbol table entry.
Definition: symbol.h:28
bool is_macro
Definition: symbol.h:61
bool is_type
Definition: symbol.h:61
typet type
Type of symbol.
Definition: symbol.h:31
irep_idt name
The unique identifier.
Definition: symbol.h:40
bool has_prefix(const std::string &s, const std::string &prefix)
Definition: converter.cpp:13
std::unordered_set< irep_idt > linest
Definition: count_eloc.cpp:29
void count_eloc(const goto_modelt &goto_model)
Definition: count_eloc.cpp:54
void print_global_state_size(const goto_modelt &goto_model)
Definition: count_eloc.cpp:158
std::unordered_map< irep_idt, filest > working_dirst
Definition: count_eloc.cpp:31
static void collect_eloc(const goto_modelt &goto_model, working_dirst &dest)
Definition: count_eloc.cpp:33
void print_path_lengths(const goto_modelt &goto_model)
Definition: count_eloc.cpp:85
std::unordered_map< irep_idt, linest > filest
Definition: count_eloc.cpp:30
void list_eloc(const goto_modelt &goto_model)
Definition: count_eloc.cpp:68
Count effective lines of code.
#define CPROVER_PREFIX
std::string concat_dir_file(const std::string &directory, const std::string &file_name)
Definition: file_util.cpp:159
Symbol Table + CFG.
#define forall_goto_program_instructions(it, program)
const std::string & id2string(const irep_idt &d)
Definition: irep.h:49
BigInt mp_integer
Definition: mp_arith.h:19
std::list< path_nodet > patht
Definition: path.h:45
API to expression classes for Pointers.
optionalt< mp_integer > pointer_offset_bits(const typet &type, const namespacet &ns)
Pointer Logic.
#define INITIALIZE_FUNCTION
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition: std_expr.h:190
Definition: kdev_t.h:19