CBMC
skip_loops.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Skip over selected loops by adding gotos
4 
5 Author: Michael Tautschnig
6 
7 Date: January 2016
8 
9 \*******************************************************************/
10 
13 
14 #include "skip_loops.h"
15 
16 #include <util/message.h>
17 #include <util/string2int.h>
18 
20 
21 typedef std::set<unsigned> loop_idst;
22 typedef std::map<irep_idt, loop_idst> loop_mapt;
23 
24 static bool skip_loops(
25  goto_programt &goto_program,
26  const loop_idst &loop_ids,
27  messaget &message)
28 {
29  loop_idst::const_iterator l_it=loop_ids.begin();
30  Forall_goto_program_instructions(it, goto_program)
31  {
32  if(l_it==loop_ids.end())
33  break;
34  if(!it->is_backwards_goto())
35  continue;
36 
37  const unsigned loop_id=it->loop_number;
38  if(*l_it<loop_id)
39  break; // error handled below
40  if(*l_it>loop_id)
41  continue;
42 
43  goto_programt::targett loop_head=it->get_target();
44  goto_programt::targett next=it;
45  ++next;
46  CHECK_RETURN(next != goto_program.instructions.end());
47 
48  goto_program.insert_before(
49  loop_head,
51  next, true_exprt(), loop_head->source_location()));
52 
53  ++l_it;
54  }
55  if(l_it!=loop_ids.end())
56  {
57  message.error() << "Loop " << *l_it << " not found"
58  << messaget::eom;
59  return true;
60  }
61 
62  return false;
63 }
64 
65 static bool parse_loop_ids(
66  const std::string &loop_ids,
67  loop_mapt &loop_map)
68 {
69  std::string::size_type length=loop_ids.length();
70 
71  for(std::string::size_type idx=0; idx<length; idx++)
72  {
73  std::string::size_type next=loop_ids.find(",", idx);
74  std::string val=loop_ids.substr(idx, next-idx);
75  std::string::size_type delim=val.rfind(".");
76 
77  if(delim==std::string::npos)
78  return true;
79 
80  std::string fn=val.substr(0, delim);
81  unsigned nr=safe_string2unsigned(val.substr(delim+1));
82 
83  loop_map[fn].insert(nr);
84 
85  if(next==std::string::npos)
86  break;
87  idx=next;
88  }
89 
90  return false;
91 }
92 
94  goto_modelt &goto_model,
95  const std::string &loop_ids,
96  message_handlert &message_handler)
97 {
98  messaget message(message_handler);
99 
100  loop_mapt loop_map;
101  if(parse_loop_ids(loop_ids, loop_map))
102  {
103  message.error() << "Failed to parse loop ids" << messaget::eom;
104  return true;
105  }
106 
107  loop_mapt::const_iterator it=loop_map.begin();
108  for(auto &gf_entry : goto_model.goto_functions.function_map)
109  {
110  if(it == loop_map.end() || it->first < gf_entry.first)
111  break; // possible error handled below
112  else if(it->first == gf_entry.first)
113  {
114  if(skip_loops(gf_entry.second.body, it->second, message))
115  return true;
116  ++it;
117  }
118  }
119  if(it!=loop_map.end())
120  {
121  message.error() << "No function " << it->first << " in goto program"
122  << messaget::eom;
123  return true;
124  }
125 
126  // update counters etc.
127  goto_model.goto_functions.update();
128 
129  return false;
130 }
const source_locationt & source_location() const
Definition: expr.h:231
function_mapt function_map
goto_functionst goto_functions
GOTO functions.
Definition: goto_model.h:34
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:73
instructionst instructions
The list of instructions in the goto program.
Definition: goto_program.h:622
instructionst::iterator targett
Definition: goto_program.h:614
static instructiont make_goto(targett _target, const source_locationt &l=source_locationt::nil())
targett insert_before(const_targett target)
Insertion before the instruction pointed-to by the given instruction iterator target.
Definition: goto_program.h:692
Class that provides messages with a built-in verbosity 'level'.
Definition: message.h:154
mstreamt & error() const
Definition: message.h:391
static eomt eom
Definition: message.h:289
The Boolean constant true.
Definition: std_expr.h:3063
Symbol Table + CFG.
#define Forall_goto_program_instructions(it, program)
static bool parse_loop_ids(const std::string &loop_ids, loop_mapt &loop_map)
Definition: skip_loops.cpp:65
std::map< irep_idt, loop_idst > loop_mapt
Definition: skip_loops.cpp:22
static bool skip_loops(goto_programt &goto_program, const loop_idst &loop_ids, messaget &message)
Definition: skip_loops.cpp:24
std::set< unsigned > loop_idst
Definition: skip_loops.cpp:21
Skip over selected loops by adding gotos.
#define CHECK_RETURN(CONDITION)
Definition: invariant.h:495
unsigned safe_string2unsigned(const std::string &str, int base)
Definition: string2int.cpp:16
#define size_type
Definition: unistd.c:347