c++ - Why does the compiler warn about uninitialized edge iterator in some optimization levels?

Question

I have minimized the reproducible example as far as I was able to. In it, I loop over all edges in the boost graph and get a warning that I don't understand. Please explain to me why I am getting this warning, and perhaps also why it only appears in certain optimization levels.

/*
 *  reproducing the warning about maybe uninitialized edge iterator
 */
#include <vector>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>

typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> traits;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property,
    boost::property<boost::edge_capacity_t, long>> graph;

typedef traits::vertex_descriptor vertex_desc;
typedef traits::edge_descriptor edge_desc;
typedef boost::graph_traits<graph>::edge_iterator edge_iterator;

int main(){
    // build a graph
    graph G(10);
    // get its capacity map
    auto c_map = boost::get(boost::edge_capacity, G);
    // get a handle to the first vertex
    vertex_desc source = boost::vertex(0, G);
    // add an edge, with a capacity of 1
    edge_desc e = boost::add_edge(boost::vertex(0, G), boost::vertex(1, G), G).first;
    c_map[e] = 1;
    // loop over all edges in the graph
    std::pair<edge_iterator, edge_iterator> eip = boost::edges(G);
    for (edge_iterator eit = eip.first; eit != eip.second; eit++){
        edge_desc e = *eit;
        vertex_desc a = boost::source(e, G);
        vertex_desc b = boost::target(e, G);
        bool source_involved = ((a == source) || (b == source));
        std::cout << (source_involved ? "yes" : "no") << std::endl;
    }
}

Compiled with -O0 or -O1, there are no warnings:

g++ -std=c++14 -Wall -Wextra -O0 repro.cpp -o repro.exe

Compiled with -O2 I get this warning:

# g++ -std=c++14 -Wall -Wextra -O2 repro.cpp -o repro.exe
repro.cpp: In function 'int main()':
repro.cpp:28:24: warning: '*((void*)& eit +48)' may be used uninitialized in this function [-Wmaybe-uninitialized]
     for (edge_iterator eit = eip.first; eit != eip.second; eit++){
                        ^~~

And compiled with -O3, -O4, -O5 I get a similar warning, but in ugly:

# g++ -std=c++14 -Wall -Wextra -O3 repro.cpp -o repro.exe
repro.cpp: In function 'int main()':
repro.cpp:28:24: warning: '*((void*)(& eit)+32).__gnu_cxx::__normal_iterator<boost::detail::stored_edge_property<long unsigned int, boost::property<boost::edge_capacity_t, long int> >*, std::vector<boost::detail::stored_edge_property<long unsigned int, boost::property<boost::edge_capacity_t, long int> >, std::allocator<boost::detail::stored_edge_property<long unsigned int, boost::property<boost::edge_capacity_t, long int> > > > >::_M_current' may be used uninitialized in this function [-Wmaybe-uninitialized]
     for (edge_iterator eit = eip.first; eit != eip.second; eit++){

My g++ --version is

g++ (Ubuntu 8.4.0-1ubuntu1~18.04) 8.4.0

And I'm running in docker

# uname -a
Linux 88157d45c773 5.4.0-58-generic #64~18.04.1-Ubuntu SMP Wed Dec 9 17:11:11 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

The warning does appear in -std=c++11 and -std=c++14 but not in -std=c++17, it seems.

What is this warning telling me? What is the issue?

Answer 1

As I commented, this is likely a compiler issue with specific compiler versions, where inlining+dead code elision leads to spurious unused variable warnings.

I don't see much virtue in finding whether there has been a bug report linked to the fix. Instead, let me show you more elegant ways to write the code in c++14.

Not intended as an answer to the question as posed. though by sheer coincidence, the specific warnings you encounter might be gone.

I post the answer for inspiration/educational value as I see a lot of copy/past BGL that is badly behind the times.

Live On Wandbox

#include <boost/graph/adjacency_list.hpp>
#include <iostream>
#include <vector>

using capacity_prop = boost::property<boost::edge_capacity_t, long>;

using graph = boost::adjacency_list<
                    boost::vecS, boost::vecS, boost::directedS,
                    boost::no_property, capacity_prop
                >;

int main() {
    graph G(10);
    auto add = [&G](auto a, auto b, auto c) {
        add_edge(vertex(a, G), vertex(b, G), capacity_prop{c}, G);
    };
    add(0, 1, 1);
    add(1, 2, 2);
    add(1, 3, 3);
    add(1, 7, 4);
    add(1, 8, 5);
    add(2, 5, 6);
    add(5, 3, 7);
    add(5, 0, 8);
    add(7, 0, 9);

    auto const s = vertex(0, G);

    for (auto e : boost::make_iterator_range(edges(G))) {
        auto a = source(e, G);
        auto b = target(e, G);
        std::cout << e << " involves " << s << "? "
            << std::boolalpha << (a == s || b == s) << std::endl;
    }
}

Prints

(0,1) involves 0? true
(1,2) involves 0? false
(1,3) involves 0? false
(1,7) involves 0? false
(1,8) involves 0? false
(2,5) involves 0? false
(5,3) involves 0? false
(5,0) involves 0? true
(7,0) involves 0? true

C++17 Bonus

It would make it easier to write the initialization code more naturally

for (auto [a,b,c] : { std::tuple
        {0, 1, 1}, {1, 2, 2}, {1, 3, 3},
        {1, 7, 4}, {1, 8, 5}, {2, 5, 6},
        {5, 3, 7}, {5, 0, 8}, {7, 0, 9}, })
{
    add_edge(vertex(a, G), vertex(b, G), capacity_prop{c}, G);
}

Logic Bonus

If really you wanted to find just the set of edges involving vertex s, you could write it like this and probably be more efficient:

Live On Wandbox

auto const s = vertex(2, G); // different example
auto [f,l] = out_edges(s, G);
edge_set involved(f, l);

for (auto e : make_iterator_range(edges(G)))
    if (target(e, G) == s)
        involved.insert(e);

for (auto e : involved)
    std::cout << e << " ";

Prints

(1,2) (2,5) 

As one would expect.

Performance Tip

If you can tweak the graph model, there's even better performance to be had by changing it to maintain bidirectional edges for the adjacency_list:

std::set<graph::edge_descriptor> involved;

auto insert = [&](auto range) { involved.insert(range.first, range.second); };
insert(out_edges(s, G));
insert(in_edges(s, G));

Or, indeed, just print them immediately:

for (auto e : make_iterator_range(out_edges(s, G)))
    std::cout << e << " ";
for (auto e : make_iterator_range(in_edges(s, G)))
    std::cout << e << " ";

See it Live Ob Wandbox

Printing the same.

Whether or not this improves performance for your application depends mostly on whether you have more mutations or more queries on the graph.

PS

Here's the graph I made for the example for reference

This is the result of doing

boost::dynamic_properties dp;
dp.property("node_id", get(boost::vertex_index, G));
dp.property("label", get(boost::edge_capacity, G));
write_graphviz_dp(std::cout, G, dp);

And using dot (e.g. online)