CBMC
Loading...
Searching...
No Matches
ensure_one_backedge_per_target.cpp
Go to the documentation of this file.
1/*******************************************************************\
2
3Module: Ensure one backedge per target
4
5Author: Diffblue Ltd.
6
7\*******************************************************************/
8
11
13
15
16#include "goto_model.h"
17
18#include <algorithm>
19
23{
24 return a->location_number < b->location_number;
25}
26
29 goto_programt &goto_program)
30{
31 auto &instruction = *it;
32 std::vector<goto_programt::targett> backedges;
33
34 // Check if this instruction has multiple incoming edges from (lexically)
35 // lower down the program. These aren't necessarily loop backedges (in fact
36 // the program might be acyclic), but that's the most common case.
37 for(auto predecessor : instruction.incoming_edges)
38 {
39 if(predecessor->location_number > instruction.location_number)
40 backedges.push_back(predecessor);
41 }
42
43 if(backedges.size() < 2)
44 return false;
45
46 std::sort(backedges.begin(), backedges.end(), location_number_less_than);
47
48 auto last_backedge = backedges.back();
49 backedges.pop_back();
50
51 // Can't transform if the bottom of the (probably) loop is of unexpected
52 // form:
53 if(!last_backedge->is_goto() || last_backedge->targets.size() > 1)
54 {
55 return false;
56 }
57
58 // If the last backedge is a conditional jump, add an extra unconditional
59 // backedge after it:
60 if(!last_backedge->condition().is_true())
61 {
62 auto new_goto =
64 // Turn the existing `if(x) goto head; succ: ...`
65 // into `if(!x) goto succ; goto head; succ: ...`
66 last_backedge->condition_nonconst() = not_exprt(last_backedge->condition());
67 last_backedge->set_target(std::next(new_goto));
68 // Use the new backedge as the one true way to the header:
70 }
71
72 // Redirect all but one of the backedges to the last one.
73 // For example, transform
74 // "a: if(x) goto a; if(y) goto a;" into
75 // "a: if(x) goto b; if(y) b: goto a;"
76 // In the common case where this is a natural loop this corresponds to
77 // branching to the bottom of the loop on a `continue` statement.
78 for(auto backedge : backedges)
79 {
80 if(backedge->is_goto() && backedge->targets.size() == 1)
81 {
82 backedge->set_target(last_backedge);
83 }
84 }
85
86 return true;
87}
88
90{
91 inline bool operator()(
93 const goto_programt::targett &i2) const
94 {
96 }
97};
98
100{
105 natural_loops{goto_program};
106 std::set<goto_programt::targett, location_number_less_thant> modified_loops;
107
108 for(auto it1 = natural_loops.loop_map.begin();
109 it1 != natural_loops.loop_map.end();
110 ++it1)
111 {
112 DATA_INVARIANT(!it1->second.empty(), "loops cannot have no instructions");
113 // skip over lexical loops
114 if(
115 (*std::prev(it1->second.end()))->is_goto() &&
116 (*std::prev(it1->second.end()))->get_target() == it1->first)
117 continue;
118 if(modified_loops.find(it1->first) != modified_loops.end())
119 continue;
120 // it1 refers to a loop that isn't a lexical loop, now see whether any other
121 // loop is nested within it1
122 for(auto it2 = natural_loops.loop_map.begin();
123 it2 != natural_loops.loop_map.end();
124 ++it2)
125 {
126 if(it1 == it2)
127 continue;
128
129 if(std::includes(
130 it1->second.begin(),
131 it1->second.end(),
132 it2->second.begin(),
133 it2->second.end(),
135 {
136 // make sure that loops with overlapping body are properly nested by a
137 // back edge; this will be a disconnected edge, which
138 // ensure_one_backedge_per_target connects
139 if(
140 modified_loops.find(it2->first) == modified_loops.end() &&
141 (!(*std::prev(it2->second.end()))->is_goto() ||
142 (*std::prev(it2->second.end()))->get_target() != it2->first))
143 {
144 auto new_goto = goto_program.insert_after(
145 *std::prev(it2->second.end()),
147 it2->first, (*std::prev(it2->second.end()))->source_location()));
148 it2->second.insert_instruction(new_goto);
149 it1->second.insert_instruction(new_goto);
150 modified_loops.insert(it2->first);
151 }
152
153 goto_program.insert_after(
154 *std::prev(it1->second.end()),
156 it1->first, (*std::prev(it1->second.end()))->source_location()));
157 modified_loops.insert(it1->first);
158 break;
159 }
160 }
161 }
162
163 if(!modified_loops.empty())
164 goto_program.update();
165
166 bool any_change = !modified_loops.empty();
167
168 for(auto it = goto_program.instructions.begin();
169 it != goto_program.instructions.end();
170 ++it)
171 {
172 any_change |= ensure_one_backedge_per_target(it, goto_program);
173 }
174
175 return any_change;
176}
177
179{
180 auto &goto_function = goto_model_function.get_goto_function();
181
182 if(ensure_one_backedge_per_target(goto_function.body))
183 {
184 goto_function.body.update();
185 goto_model_function.compute_location_numbers();
186 return true;
187 }
188
189 return false;
190}
191
193{
194 bool any_change = false;
195
196 for(auto &id_and_function : goto_model.goto_functions.function_map)
198
199 if(any_change)
200 goto_model.goto_functions.update();
201
202 return any_change;
203}
ait supplies three of the four components needed: an abstract interpreter (in this case handling func...
Definition ai.h:562
function_mapt function_map
Interface providing access to a single function in a GOTO model, plus its associated symbol table.
Definition goto_model.h:190
goto_functionst goto_functions
GOTO functions.
Definition goto_model.h:34
A generic container class for the GOTO intermediate representation of one function.
instructionst instructions
The list of instructions in the goto program.
void update()
Update all indices.
instructionst::iterator targett
targett insert_after(const_targett target)
Insertion after the instruction pointed-to by the given instruction iterator target.
static instructiont make_goto(targett _target, const source_locationt &l=source_locationt::nil())
Main driver for working out if a class (normally goto_programt) has any natural loops.
Boolean negation.
Definition std_expr.h:2459
static bool location_number_less_than(const goto_programt::targett &a, const goto_programt::targett &b)
bool ensure_one_backedge_per_target(goto_programt::targett &it, goto_programt &goto_program)
Ensure one backedge per target.
Symbol Table + CFG.
Compute natural loops in a goto_function.
#define DATA_INVARIANT(CONDITION, REASON)
This condition should be used to document that assumptions that are made on goto_functions,...
Definition invariant.h:534
bool operator()(const goto_programt::targett &i1, const goto_programt::targett &i2) const