11674460316

Committed 04 Nov 2024 11:25PM UTC coverage: 90.541% (+0.05%) from 90.488%

Build # 11674460316

Build Type

push

github

Committed by

elazarg

Commit Message

revert to memcpy, add requires(trivially_copyable)

Signed-off-by: Elazar Gershuni <elazarg@gmail.com>

Run Details

2 of 2 new or added lines in 1 file covered. (100.0%)

76 existing lines in 3 files now uncovered.

8567 of 9462 relevant lines covered (90.54%)

8696209.32 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

71.9

/src/asm_cfg.cpp

// Copyright (c) Prevail Verifier contributors.
// SPDX-License-Identifier: MIT
#include <cassert>

#include <algorithm>
#include <map>
#include <optional>
#include <string>
#include <vector>

#include "asm_syntax.hpp"
#include "crab/cfg.hpp"

using std::optional;
using std::set;
using std::string;
using std::to_string;
using std::vector;

static optional<label_t> get_jump(Instruction ins) {
    if (const auto pins = std::get_if<Jmp>(&ins)) {
        return pins->target;
    }
    return {};
}

static bool has_fall(const Instruction& ins) {
    if (std::holds_alternative<Exit>(ins)) {
        return false;
    }

    if (const auto pins = std::get_if<Jmp>(&ins)) {
        if (!pins->cond) {
            return false;
        }
    }

    return true;
}

/// Update a control-flow graph to inline function macros.
static void add_cfg_nodes(cfg_t& cfg, const label_t& caller_label, const label_t& entry_label) {
    bool first = true;

    // Get the label of the node to go to on returning from the macro.
    basic_block_t& exit_to_node = cfg.get_node(cfg.next_nodes(caller_label).front());

    // Construct the variable prefix to use for the new stack frame,
    // and store a copy in the CallLocal instruction since the instruction-specific
    // labels may only exist until the CFG is simplified.
    basic_block_t& caller_node = cfg.get_node(caller_label);
    std::string stack_frame_prefix = to_string(caller_label);
    for (auto& inst : caller_node) {
        if (const auto pcall = std::get_if<CallLocal>(&inst)) {
            pcall->stack_frame_prefix = stack_frame_prefix;
        }
    }

    // Walk the transitive closure of CFG nodes starting at entry_label and ending at
    // any exit instruction.
    std::set macro_labels{entry_label};
    std::set seen_labels{entry_label};
    while (!macro_labels.empty()) {
        label_t macro_label = *macro_labels.begin();
        macro_labels.erase(macro_label);

        if (stack_frame_prefix == macro_label.stack_frame_prefix) {
            throw std::runtime_error{stack_frame_prefix + ": illegal recursion"};
        }

        // Clone the macro block into a new block with the new stack frame prefix.
        const label_t label(macro_label.from, macro_label.to, stack_frame_prefix);
        auto& bb = cfg.insert(label);
        for (auto inst : cfg.get_node(macro_label)) {
            if (const auto pexit = std::get_if<Exit>(&inst)) {
                pexit->stack_frame_prefix = label.stack_frame_prefix;
            } else if (const auto pcall = std::get_if<Call>(&inst)) {
                pcall->stack_frame_prefix = label.stack_frame_prefix;
            }
            bb.insert(inst);
        }

        if (first) {
            // Add an edge from the caller to the new block.
            first = false;
            caller_node >> bb;
        }

        // Add an edge from any other predecessors.
        for (const auto& prev_macro_nodes = cfg.prev_nodes(macro_label);
             const auto& prev_macro_label : prev_macro_nodes) {
            const label_t prev_label(prev_macro_label.from, prev_macro_label.to, to_string(caller_label));
            if (const auto& labels = cfg.labels(); std::ranges::find(labels, prev_label) != labels.end()) {
                cfg.get_node(prev_label) >> bb;
            }
        }

        // Walk all successor nodes.
        for (const auto& next_macro_nodes = cfg.next_nodes(macro_label);
             const auto& next_macro_label : next_macro_nodes) {
            if (next_macro_label == cfg.exit_label()) {
                // This is an exit transition, so add edge to the block to execute
                // upon returning from the macro.
                bb >> exit_to_node;
            } else if (!seen_labels.contains(next_macro_label)) {
                // Push any other unprocessed successor label onto the list to be processed.
                if (!macro_labels.contains(next_macro_label)) {
                    macro_labels.insert(next_macro_label);
                }
                seen_labels.insert(macro_label);
            }
        }
    }

    // Remove the original edge from the caller node to its successor,
    // since processing now goes through the function macro instead.
    caller_node -= exit_to_node;

    // Finally, recurse to replace any nested function macros.
    string caller_label_str = to_string(caller_label);
    long stack_frame_depth = std::ranges::count(caller_label_str, STACK_FRAME_DELIMITER) + 2;
    for (auto& macro_label : seen_labels) {
        for (const label_t label(macro_label.from, macro_label.to, caller_label_str);
             const auto& inst : cfg.get_node(label)) {
            if (const auto pins = std::get_if<CallLocal>(&inst)) {
                if (stack_frame_depth >= MAX_CALL_STACK_FRAMES) {
                    throw std::runtime_error{"too many call stack frames"};
                }
                add_cfg_nodes(cfg, label, pins->target);
            }
        }
    }
}

/// Convert an instruction sequence to a control-flow graph (CFG).
static cfg_t instruction_seq_to_cfg(const InstructionSeq& insts, const bool must_have_exit) {
    cfg_t cfg;
    std::optional<label_t> falling_from = {};
    bool first = true;

    // Do a first pass ignoring all function macro calls.
    for (const auto& [label, inst, _] : insts) {

        if (std::holds_alternative<Undefined>(inst)) {
            continue;
        }

        auto& bb = cfg.insert(label);

        if (first) {
            first = false;
            cfg.get_node(cfg.entry_label()) >> bb;
        }

        bb.insert(inst);
        if (falling_from) {
            cfg.get_node(*falling_from) >> bb;
            falling_from = {};
        }
        if (has_fall(inst)) {
            falling_from = label;
        }
        if (auto jump_target = get_jump(inst)) {
            bb >> cfg.insert(*jump_target);
        }

        if (std::holds_alternative<Exit>(inst)) {
            bb >> cfg.get_node(cfg.exit_label());
        }
    }
    if (falling_from) {
        if (must_have_exit) {
            throw std::invalid_argument{"fallthrough in last instruction"};
        } else {
            cfg.get_node(*falling_from) >> cfg.get_node(cfg.exit_label());
        }
    }

    // Now replace macros. We have to do this as a second pass so that
    // we only add new nodes that are actually reachable, based on the
    // results of the first pass.
    for (auto& [label, inst, _] : insts) {
        if (const auto pins = std::get_if<CallLocal>(&inst)) {
            add_cfg_nodes(cfg, label, pins->target);
        }
    }

    return cfg;
}

/// Get the inverse of a given comparison operation.
static Condition::Op reverse(const Condition::Op op) {
    switch (op) {
    case Condition::Op::EQ: return Condition::Op::NE;
    case Condition::Op::NE: return Condition::Op::EQ;

    case Condition::Op::GE: return Condition::Op::LT;
    case Condition::Op::LT: return Condition::Op::GE;

    case Condition::Op::SGE: return Condition::Op::SLT;
    case Condition::Op::SLT: return Condition::Op::SGE;

    case Condition::Op::LE: return Condition::Op::GT;
    case Condition::Op::GT: return Condition::Op::LE;

    case Condition::Op::SLE: return Condition::Op::SGT;
    case Condition::Op::SGT: return Condition::Op::SLE;

    case Condition::Op::SET: return Condition::Op::NSET;
    case Condition::Op::NSET: return Condition::Op::SET;
    }
    assert(false);
    return {};
}

/// Get the inverse of a given comparison condition.
static Condition reverse(const Condition& cond) {
    return {.op = reverse(cond.op), .left = cond.left, .right = cond.right, .is64 = cond.is64};
}

template <typename T>
static vector<label_t> unique(const std::pair<T, T>& be) {
    vector<label_t> res;
    std::unique_copy(be.first, be.second, std::back_inserter(res));
    return res;
}

/// Get a non-deterministic version of a control-flow graph,
/// i.e., where instead of using if/else, both branches are taken
/// simultaneously, and are replaced by Assume instructions
/// immediately after the branch.
static cfg_t to_nondet(const cfg_t& cfg) {
    cfg_t res;
    for (auto const& [this_label, bb] : cfg) {
        basic_block_t& newbb = res.insert(this_label);

        for (const auto& ins : bb) {
            if (!std::holds_alternative<Jmp>(ins)) {
                newbb.insert(ins);
            }
        }

        for (const label_t& prev_label : bb.prev_blocks_set()) {
            bool is_one = cfg.get_node(prev_label).next_blocks_set().size() > 1;
            basic_block_t& pbb = res.insert(is_one ? label_t::make_jump(prev_label, this_label) : prev_label);
            pbb >> newbb;
        }
        // note the special case where we jump to fallthrough
        auto nextlist = bb.next_blocks_set();
        if (nextlist.size() == 2) {
            label_t mid_label = this_label;
            auto jmp = std::get<Jmp>(*bb.rbegin());

            nextlist.erase(jmp.target);
            label_t fallthrough = *nextlist.begin();

            vector<std::tuple<label_t, Condition>> jumps{
                {jmp.target, *jmp.cond},
                {fallthrough, reverse(*jmp.cond)},
            };
            for (auto const& [next_label, cond1] : jumps) {
                label_t jump_label = label_t::make_jump(mid_label, next_label);
                basic_block_t& jump_bb = res.insert(jump_label);
                jump_bb.insert<Assume>(cond1);
                newbb >> jump_bb;
                jump_bb >> res.insert(next_label);
            }
        } else {
            for (const auto& label : nextlist) {
                newbb >> res.insert(label);
            }
        }
    }
    return res;
}

/// Get the type of given instruction.
/// Most of these type names are also statistics header labels.
static std::string instype(Instruction ins) {
    if (const auto pcall = std::get_if<Call>(&ins)) {
        if (pcall->is_map_lookup) {
            return "call_1";
        }
        if (pcall->pairs.empty()) {
            if (std::ranges::all_of(pcall->singles,
                                    [](const ArgSingle kr) { return kr.kind == ArgSingle::Kind::ANYTHING; })) {
                return "call_nomem";
            }
        }
        return "call_mem";
    } else if (std::holds_alternative<Callx>(ins)) {
        return "callx";
    } else if (const auto pimm = std::get_if<Mem>(&ins)) {
        return pimm->is_load ? "load" : "store";
    } else if (std::holds_alternative<Atomic>(ins)) {
        return "load_store";
    } else if (std::holds_alternative<Packet>(ins)) {
        return "packet_access";
    } else if (const auto pins = std::get_if<Bin>(&ins)) {
        switch (pins->op) {
        case Bin::Op::MOV:
        case Bin::Op::MOVSX8:
        case Bin::Op::MOVSX16:
        case Bin::Op::MOVSX32: return "assign";
        default: return "arith";
        }
    } else if (std::holds_alternative<Un>(ins)) {
        return "arith";
    } else if (std::holds_alternative<LoadMapFd>(ins)) {
        return "assign";
    } else if (std::holds_alternative<Assume>(ins)) {
        return "assume";
    } else {
        return "other";
    }
}

std::vector<std::string> stats_headers() {
    return {
        "basic_blocks", "joins",      "other",      "jumps",         "assign",  "arith",
        "load",         "store",      "load_store", "packet_access", "call_1",  "call_mem",
        "call_nomem",   "reallocate", "map_in_map", "arith64",       "arith32",
    };
}

std::map<std::string, int> collect_stats(const cfg_t& cfg) {
    std::map<std::string, int> res;
    for (const auto& h : stats_headers()) {
        res[h] = 0;
    }
    for (const auto& this_label : cfg.labels()) {
        res["basic_blocks"]++;
        basic_block_t const& bb = cfg.get_node(this_label);

        for (Instruction ins : bb) {
            if (const auto pins = std::get_if<LoadMapFd>(&ins)) {
                if (pins->mapfd == -1) {
                    res["map_in_map"] = 1;
                }
            }
            if (const auto pins = std::get_if<Call>(&ins)) {
                if (pins->reallocate_packet) {
                    res["reallocate"] = 1;
                }
            }
            if (const auto pins = std::get_if<Bin>(&ins)) {
                res[pins->is64 ? "arith64" : "arith32"]++;
            }
            res[instype(ins)]++;
        }
        if (unique(bb.prev_blocks()).size() > 1) {
            res["joins"]++;
        }
        if (unique(bb.prev_blocks()).size() > 1) {
            res["jumps"]++;
        }
    }
    return res;
}

cfg_t prepare_cfg(const InstructionSeq& prog, const program_info& info, const bool simplify,
                  const bool must_have_exit) {
    // Convert the instruction sequence to a deterministic control-flow graph.
    cfg_t det_cfg = instruction_seq_to_cfg(prog, must_have_exit);

    // Annotate the CFG by adding in assertions before every memory instruction.
    explicate_assertions(det_cfg, info);

    // Translate conditional jumps to non-deterministic jumps.
    cfg_t cfg = to_nondet(det_cfg);

    // Except when debugging, combine chains of instructions into
    // basic blocks where possible, i.e., into a range of instructions
    // where there is a single entry point and a single exit point.
    // An abstract interpreter will keep values at every basic block,
    // so the fewer basic blocks we have, the less information it has to
    // keep track of.
    if (simplify) {
        cfg.simplify();
    }

    return cfg;
}

1	// Copyright (c) Prevail Verifier contributors.
2	// SPDX-License-Identifier: MIT
3	#include <cassert>
4
5	#include <algorithm>
6	#include <map>
7	#include <optional>
8	#include <string>
9	#include <vector>
10
11	#include "asm_syntax.hpp"
12	#include "crab/cfg.hpp"
13
14	using std::optional;
15	using std::set;
16	using std::string;
17	using std::to_string;
18	using std::vector;
19
20	static optional<label_t> get_jump(Instruction ins) {	285,178✔
21	if (const auto pins = std::get_if<Jmp>(&ins)) {	285,178✔
22	return pins->target;	29,720✔
23	}
24	return {};	255,458✔
25	}
26
27	static bool has_fall(const Instruction& ins) {	285,178✔
28	if (std::holds_alternative<Exit>(ins)) {	285,178✔
29	return false;	719✔
30	}
31
32	if (const auto pins = std::get_if<Jmp>(&ins)) {	283,740✔
33	if (!pins->cond) {	29,720✔
34	return false;	2,245✔
35	}
36	}
37
38	return true;	139,625✔
39	}
40
41	/// Update a control-flow graph to inline function macros.
42	static void add_cfg_nodes(cfg_t& cfg, const label_t& caller_label, const label_t& entry_label) {	122✔
43	bool first = true;	122✔
44
45	// Get the label of the node to go to on returning from the macro.
46	basic_block_t& exit_to_node = cfg.get_node(cfg.next_nodes(caller_label).front());	122✔
47
48	// Construct the variable prefix to use for the new stack frame,
49	// and store a copy in the CallLocal instruction since the instruction-specific
50	// labels may only exist until the CFG is simplified.
51	basic_block_t& caller_node = cfg.get_node(caller_label);	122✔
52	std::string stack_frame_prefix = to_string(caller_label);	122✔
53	for (auto& inst : caller_node) {	244✔
54	if (const auto pcall = std::get_if<CallLocal>(&inst)) {	183✔
55	pcall->stack_frame_prefix = stack_frame_prefix;	183✔
56	}
57	}
58
59	// Walk the transitive closure of CFG nodes starting at entry_label and ending at
60	// any exit instruction.
61	std::set macro_labels{entry_label};	322✔
62	std::set seen_labels{entry_label};	322✔
63	while (!macro_labels.empty()) {	406✔
64	label_t macro_label = *macro_labels.begin();	288✔
65	macro_labels.erase(macro_label);	288✔
66
67	if (stack_frame_prefix == macro_label.stack_frame_prefix) {	288✔
68	throw std::runtime_error{stack_frame_prefix + ": illegal recursion"};	6✔
69	}
70
71	// Clone the macro block into a new block with the new stack frame prefix.
72	const label_t label(macro_label.from, macro_label.to, stack_frame_prefix);	426✔
73	auto& bb = cfg.insert(label);	284✔
74	for (auto inst : cfg.get_node(macro_label)) {	568✔
75	if (const auto pexit = std::get_if<Exit>(&inst)) {	284✔
76	pexit->stack_frame_prefix = label.stack_frame_prefix;	124✔
77	} else if (const auto pcall = std::get_if<Call>(&inst)) {	223✔
78	pcall->stack_frame_prefix = label.stack_frame_prefix;	2✔
79	}
80	bb.insert(inst);	426✔
81	}	284✔
82
83	if (first) {	284✔
84	// Add an edge from the caller to the new block.
85	first = false;	122✔
86	caller_node >> bb;	122✔
87	}
88
89	// Add an edge from any other predecessors.
90	for (const auto& prev_macro_nodes = cfg.prev_nodes(macro_label);	426✔
91	const auto& prev_macro_label : prev_macro_nodes) {	596✔
92	const label_t prev_label(prev_macro_label.from, prev_macro_label.to, to_string(caller_label));	255✔
93	if (const auto& labels = cfg.labels(); std::ranges::find(labels, prev_label) != labels.end()) {	170✔
94	cfg.get_node(prev_label) >> bb;	164✔
95	}	170✔
96	}	170✔
97
98	// Walk all successor nodes.
99	for (const auto& next_macro_nodes = cfg.next_nodes(macro_label);	571✔
100	const auto& next_macro_label : next_macro_nodes) {	716✔
101	if (next_macro_label == cfg.exit_label()) {	435✔
102	// This is an exit transition, so add edge to the block to execute
103	// upon returning from the macro.
104	bb >> exit_to_node;	122✔
105	} else if (!seen_labels.contains(next_macro_label)) {	168✔
106	// Push any other unprocessed successor label onto the list to be processed.
107	if (!macro_labels.contains(next_macro_label)) {	168✔
108	macro_labels.insert(next_macro_label);	166✔
109	}
110	seen_labels.insert(macro_label);	168✔
111	}
112	}
113	}	288✔
114
115	// Remove the original edge from the caller node to its successor,
116	// since processing now goes through the function macro instead.
117	caller_node -= exit_to_node;	118✔
118
119	// Finally, recurse to replace any nested function macros.
120	string caller_label_str = to_string(caller_label);	118✔
121	long stack_frame_depth = std::ranges::count(caller_label_str, STACK_FRAME_DELIMITER) + 2;	118✔
122	for (auto& macro_label : seen_labels) {	242✔
123	for (const label_t label(macro_label.from, macro_label.to, caller_label_str);	385✔
124	const auto& inst : cfg.get_node(label)) {	355✔
125	if (const auto pins = std::get_if<CallLocal>(&inst)) {	216✔
126	if (stack_frame_depth >= MAX_CALL_STACK_FRAMES) {	74✔
127	throw std::runtime_error{"too many call stack frames"};	4✔
128	}
129	add_cfg_nodes(cfg, label, pins->target);	70✔
130	}
131	}	154✔
132	}
133	}	203✔
134
135	/// Convert an instruction sequence to a control-flow graph (CFG).
136	static cfg_t instruction_seq_to_cfg(const InstructionSeq& insts, const bool must_have_exit) {	2,460✔
137	cfg_t cfg;	2,460✔
138	std::optional<label_t> falling_from = {};	2,460✔
139	bool first = true;	2,460✔
140
141	// Do a first pass ignoring all function macro calls.
142	for (const auto& [label, inst, _] : insts) {	287,638✔
143
144	if (std::holds_alternative<Undefined>(inst)) {	285,178✔
UNCOV 145	continue;	×
146	}
147
148	auto& bb = cfg.insert(label);	285,178✔
149
150	if (first) {	285,178✔
151	first = false;	2,460✔
152	cfg.get_node(cfg.entry_label()) >> bb;	4,920✔
153	}
154
155	bb.insert(inst);	285,178✔
156	if (falling_from) {	285,178✔
157	cfg.get_node(*falling_from) >> bb;	278,046✔
158	falling_from = {};	278,046✔
159	}
160	if (has_fall(inst)) {	285,178✔
161	falling_from = label;	279,250✔
162	}
163	if (auto jump_target = get_jump(inst)) {	712,945✔
164	bb >> cfg.insert(*jump_target);	29,720✔
165	}	142,589✔
166
167	if (std::holds_alternative<Exit>(inst)) {	285,178✔
168	bb >> cfg.get_node(cfg.exit_label());	2,876✔
169	}
170	}
171	if (falling_from) {	2,460✔
172	if (must_have_exit) {	1,204✔
UNCOV 173	throw std::invalid_argument{"fallthrough in last instruction"};	×
174	} else {
175	cfg.get_node(*falling_from) >> cfg.get_node(cfg.exit_label());	2,412✔
176	}
177	}
178
179	// Now replace macros. We have to do this as a second pass so that
180	// we only add new nodes that are actually reachable, based on the
181	// results of the first pass.
182	for (auto& [label, inst, _] : insts) {	287,582✔
183	if (const auto pins = std::get_if<CallLocal>(&inst)) {	285,152✔
184	add_cfg_nodes(cfg, label, pins->target);	52✔
185	}
186	}
187
188	return cfg;	3,678✔
189	}	2,464✔
190
191	/// Get the inverse of a given comparison operation.
192	static Condition::Op reverse(const Condition::Op op) {	25,228✔
193	switch (op) {	25,228✔
194	case Condition::Op::EQ: return Condition::Op::NE;	5,165✔
195	case Condition::Op::NE: return Condition::Op::EQ;	4,394✔
196
197	case Condition::Op::GE: return Condition::Op::LT;	147✔
198	case Condition::Op::LT: return Condition::Op::GE;	240✔
199
200	case Condition::Op::SGE: return Condition::Op::SLT;	15✔
201	case Condition::Op::SLT: return Condition::Op::SGE;	616✔
202
203	case Condition::Op::LE: return Condition::Op::GT;	20✔
204	case Condition::Op::GT: return Condition::Op::LE;	1,048✔
205
206	case Condition::Op::SLE: return Condition::Op::SGT;	21✔
207	case Condition::Op::SGT: return Condition::Op::SLE;	933✔
208
209	case Condition::Op::SET: return Condition::Op::NSET;	13✔
210	case Condition::Op::NSET: return Condition::Op::SET;	2✔
211	}
212	assert(false);
213	return {};
214	}
215
216	/// Get the inverse of a given comparison condition.
217	static Condition reverse(const Condition& cond) {	25,228✔
218	return {.op = reverse(cond.op), .left = cond.left, .right = cond.right, .is64 = cond.is64};	37,842✔
219	}
220
221	template <typename T>
UNCOV 222	static vector<label_t> unique(const std::pair<T, T>& be) {	×
223	vector<label_t> res;	×
224	std::unique_copy(be.first, be.second, std::back_inserter(res));	×
225	return res;	×
226	}	×
227
228	/// Get a non-deterministic version of a control-flow graph,
229	/// i.e., where instead of using if/else, both branches are taken
230	/// simultaneously, and are replaced by Assume instructions
231	/// immediately after the branch.
232	static cfg_t to_nondet(const cfg_t& cfg) {	2,452✔
233	cfg_t res;	2,452✔
234	for (auto const& [this_label, bb] : cfg) {	292,690✔
235	basic_block_t& newbb = res.insert(this_label);	290,238✔
236
237	for (const auto& ins : bb) {	880,020✔
238	if (!std::holds_alternative<Jmp>(ins)) {	589,782✔
239	newbb.insert(ins);	854,947✔
240	}
241	}
242
243	for (const label_t& prev_label : bb.prev_blocks_set()) {	603,252✔
244	bool is_one = cfg.get_node(prev_label).next_blocks_set().size() > 1;	313,014✔
245	basic_block_t& pbb = res.insert(is_one ? label_t::make_jump(prev_label, this_label) : prev_label);	444,293✔
246	pbb >> newbb;	313,014✔
247	}
248	// note the special case where we jump to fallthrough
249	auto nextlist = bb.next_blocks_set();	290,238✔
250	if (nextlist.size() == 2) {	290,238✔
251	label_t mid_label = this_label;	25,228✔
252	auto jmp = std::get<Jmp>(*bb.rbegin());	25,228✔
253
254	nextlist.erase(jmp.target);	25,228✔
255	label_t fallthrough = *nextlist.begin();	25,228✔
256
257	vector<std::tuple<label_t, Condition>> jumps{	12,614✔
258	{jmp.target, *jmp.cond},
259	{fallthrough, reverse(*jmp.cond)},	37,842✔
260	};	126,140✔
261	for (auto const& [next_label, cond1] : jumps) {	75,684✔
262	label_t jump_label = label_t::make_jump(mid_label, next_label);	50,456✔
263	basic_block_t& jump_bb = res.insert(jump_label);	50,456✔
264	jump_bb.insert<Assume>(cond1);	50,456✔
265	newbb >> jump_bb;	50,456✔
266	jump_bb >> res.insert(next_label);	50,456✔
267	}	50,456✔
268	} else {	25,228✔
269	for (const auto& label : nextlist) {	527,568✔
270	newbb >> res.insert(label);	262,558✔
271	}
272	}
273	}	290,238✔
274	return res;	2,452✔
UNCOV 275	}	×
276
277	/// Get the type of given instruction.
278	/// Most of these type names are also statistics header labels.
UNCOV 279	static std::string instype(Instruction ins) {	×
280	if (const auto pcall = std::get_if<Call>(&ins)) {	×
281	if (pcall->is_map_lookup) {	×
282	return "call_1";	×
283	}
UNCOV 284	if (pcall->pairs.empty()) {	×
285	if (std::ranges::all_of(pcall->singles,	×
286	[](const ArgSingle kr) { return kr.kind == ArgSingle::Kind::ANYTHING; })) {
UNCOV 287	return "call_nomem";	×
288	}
289	}
UNCOV 290	return "call_mem";	×
291	} else if (std::holds_alternative<Callx>(ins)) {	×
292	return "callx";	×
293	} else if (const auto pimm = std::get_if<Mem>(&ins)) {	×
294	return pimm->is_load ? "load" : "store";	×
295	} else if (std::holds_alternative<Atomic>(ins)) {
UNCOV 296	return "load_store";	×
297	} else if (std::holds_alternative<Packet>(ins)) {
UNCOV 298	return "packet_access";	×
299	} else if (const auto pins = std::get_if<Bin>(&ins)) {	×
300	switch (pins->op) {	×
301	case Bin::Op::MOV:	×
302	case Bin::Op::MOVSX8:
303	case Bin::Op::MOVSX16:
UNCOV 304	case Bin::Op::MOVSX32: return "assign";	×
305	default: return "arith";	×
306	}
307	} else if (std::holds_alternative<Un>(ins)) {
UNCOV 308	return "arith";	×
309	} else if (std::holds_alternative<LoadMapFd>(ins)) {
UNCOV 310	return "assign";	×
311	} else if (std::holds_alternative<Assume>(ins)) {
UNCOV 312	return "assume";	×
313	} else {
UNCOV 314	return "other";	×
315	}
316	}
317
UNCOV 318	std::vector<std::string> stats_headers() {	×
319	return {
320	"basic_blocks", "joins", "other", "jumps", "assign", "arith",
321	"load", "store", "load_store", "packet_access", "call_1", "call_mem",
322	"call_nomem", "reallocate", "map_in_map", "arith64", "arith32",
UNCOV 323	};	×
324	}
325
UNCOV 326	std::map<std::string, int> collect_stats(const cfg_t& cfg) {	×
327	std::map<std::string, int> res;	×
328	for (const auto& h : stats_headers()) {	×
329	res[h] = 0;	×
330	}	×
331	for (const auto& this_label : cfg.labels()) {	×
332	res["basic_blocks"]++;	×
333	basic_block_t const& bb = cfg.get_node(this_label);	×
334
UNCOV 335	for (Instruction ins : bb) {	×
336	if (const auto pins = std::get_if<LoadMapFd>(&ins)) {	×
337	if (pins->mapfd == -1) {	×
338	res["map_in_map"] = 1;	×
339	}
340	}
UNCOV 341	if (const auto pins = std::get_if<Call>(&ins)) {	×
342	if (pins->reallocate_packet) {	×
343	res["reallocate"] = 1;	×
344	}
345	}
UNCOV 346	if (const auto pins = std::get_if<Bin>(&ins)) {	×
347	res[pins->is64 ? "arith64" : "arith32"]++;	×
348	}
UNCOV 349	res[instype(ins)]++;	×
350	}	×
351	if (unique(bb.prev_blocks()).size() > 1) {	×
352	res["joins"]++;	×
353	}
UNCOV 354	if (unique(bb.prev_blocks()).size() > 1) {	×
355	res["jumps"]++;	×
356	}
UNCOV 357	}	×
358	return res;	×
359	}	×
360
361	cfg_t prepare_cfg(const InstructionSeq& prog, const program_info& info, const bool simplify,	2,460✔
362	const bool must_have_exit) {
363	// Convert the instruction sequence to a deterministic control-flow graph.
364	cfg_t det_cfg = instruction_seq_to_cfg(prog, must_have_exit);	2,460✔
365
366	// Annotate the CFG by adding in assertions before every memory instruction.
367	explicate_assertions(det_cfg, info);	2,452✔
368
369	// Translate conditional jumps to non-deterministic jumps.
370	cfg_t cfg = to_nondet(det_cfg);	2,452✔
371
372	// Except when debugging, combine chains of instructions into
373	// basic blocks where possible, i.e., into a range of instructions
374	// where there is a single entry point and a single exit point.
375	// An abstract interpreter will keep values at every basic block,
376	// so the fewer basic blocks we have, the less information it has to
377	// keep track of.
378	if (simplify) {	2,452✔
379	cfg.simplify();	1,104✔
380	}
381
382	return cfg;	3,678✔
383	}	2,452✔

vbpf / ebpf-verifier / 11674460316

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous