Pass Netlist to Router

[amin1377]

Problem

To enable flat_routing in VPR, router should be able to work with both ClusteredNetlist and AtomNetlist. To do so, I added a parameter of type Netlist, the parent class for the mentioned classes, to router functions.

The problem is that Netlist is a template class, and the template values for ClusterNetlist and AtomNetlist are different. To circumvent this problem, I assigned a default template value to the Netlist class and inherited AtomNetlist and ClusteredNetlist template values from that. Now, I can pass ClusteredNetlist or AtomNetlist to a function that accepts Netlist.

However, since the template values for ClusterNetlist(or AtomNetlist) and Netlist are different, sanitizer raises errors whenever Netlist is accessed during routing.

Defenition of Netlist:

template < typename BlockId = ParentBlockId, typename PortId = ParentPortId, typename PinId = ParentPinId, typename NetId = ParentNetId>
class Netlist { ... }

Defenition of AtomNetlist:

class AtomNetlist : public Netlist<AtomBlockId, AtomPortId, AtomPinId, AtomNetId> { ... };

Definition of ClusteredNetlist:

class ClusteredNetlist : public Netlist<ClusterBlockId, ClusterPortId, ClusterPinId, ClusterNetId> { ... };

Ids:

AtomBLockId and ClusterBlockId are inherited from ParentBLockId, AtomNetId and ClusterNetId are inherited from ParentNetId, and so on.

Example of a function that accepts Netlist:

static bool try_timing_driven_route_tmpl(const Netlist<>& netlist, .. );

How I pass Netlist to the function:

try_timing_driven_route_tmpl((const Netlist<>&) g_vpr_ctx.atom().nlist, .. );

@vaughnbetz @hzeller

[amin1377]

Sanitizer Output File

Here is one of the output files when -fsanitize=undefined is enabled.

Valgring Output File

Here, you can find the output of running Valgrind on the same program that sanitizer was run on it. As you can see, Valgrind did not raise any error.

Sample Sanitizer Error:

There are some errors:
/root/vtr-verilog-to-routing/vtr-verilog-to-routing/vpr/src/route/annotate_routing.cpp:40:38: runtime error: member call on address 0x562e0a5350e8 which does not point to an object of type 'Netlist'
0x562e0a5350e8: note: object is of type 'ClusteredNetlist'
2e 56 00 00 10 c2 cc 03 2e 56 00 00 00 51 53 0a 2e 56 00 00 0d 00 00 00 00 00 00 00 72 61 79 67
^~~~~~~~~~~~~~~~~~~~~~~
vptr for 'ClusteredNetlist'

Direct leak of 32 byte(s) in 1 object(s) allocated from:
#0 0x562e037aea6e in __interceptor_realloc (/root/vtr-verilog-to-routing/vtr-verilog-to-routing/build/vpr/vpr+0x97fea6e)
#1 0x7f81df963a32 (/usr/lib/x86_64-linux-gnu/libstdc++.so.6+0xaaa32)
#2 0x7f81df96cae3 (/usr/lib/x86_64-linux-gnu/libstdc++.so.6+0xb3ae3)
#3 0x7f81df96d3ec in __cxa_demangle (/usr/lib/x86_64-linux-gnu/libstdc++.so.6+0xb43ec)
#4 0x7f81de5c9317 (/usr/lib/x86_64-linux-gnu/libubsan.so.1+0x28317)
#5 0x7f81de5c79ba (/usr/lib/x86_64-linux-gnu/libubsan.so.1+0x269ba)
#6 0x7f81de5a7ca1 (/usr/lib/x86_64-linux-gnu/libubsan.so.1+0x6ca1)
#7 0x7f81de5a8d2e (/usr/lib/x86_64-linux-gnu/libubsan.so.1+0x7d2e)
#8 0x7f81de5aeb6d (/usr/lib/x86_64-linux-gnu/libubsan.so.1+0xdb6d)
#9 0x7f81de5aef10 in __ubsan_handle_dynamic_type_cache_miss (/usr/lib/x86_64-linux-gnu/libubsan.so.1+0xdf10)
#10 0x562e015f3dd1 in load_channel_occupancies /root/vtr-verilog-to-routing/vtr-verilog-to-routing/vpr/src/base/stats.cpp:252
#11 0x562e015f3dd1 in get_channel_occupancy_stats /root/vtr-verilog-to-routing/vtr-verilog-to-routing/vpr/src/base/stats.cpp:188
#12 0x562e015f3dd1 in routing_stats(Netlist<vtr::StrongId<general_blk_id_tag, int, -1>, vtr::StrongId<general_port_id_tag, int, -1>, vtr::StrongId<general_pin_id_tag, int, -1>, vtr::StrongId<general_net_id_tag, int, -1> > const&, bool, e_route_type, std::vector<t_segment_inf, std::allocator<t_segment_inf> >&, float, float, float, e_directionality, int, bool) /root/vtr-verilog-to-routing/vtr-verilog-to-routing/vpr/src/base/stats.cpp:67
#13 0x562e03222190 in vpr_analysis(Netlist<vtr::StrongId<general_blk_id_tag, int, -1>, vtr::StrongId<general_port_id_tag, int, -1>, vtr::StrongId<general_pin_id_tag, int, -1>, vtr::StrongId<general_net_id_tag, int, -1> > const&, t_vpr_setup&, t_arch const&, RouteStatus const&, bool) /root/vtr-verilog-to-routing/vtr-verilog-to-routing/vpr/src/base/vpr_api.cpp:1398
#14 0x562e0323bed3 in vpr_analysis_flow(Netlist<vtr::StrongId<general_blk_id_tag, int, -1>, vtr::StrongId<general_port_id_tag, int, -1>, vtr::StrongId<general_pin_id_tag, int, -1>, vtr::StrongId<general_net_id_tag, int, -1> > const&, t_vpr_setup&, t_arch const&, RouteStatus const&, bool) /root/vtr-verilog-to-routing/vtr-verilog-to-routing/vpr/src/base/vpr_api.cpp:1375
#15 0x562e0002cb42 in vpr_flow(t_vpr_setup&, t_arch&) /root/vtr-verilog-to-routing/vtr-verilog-to-routing/vpr/src/base/vpr_api.cpp:401
#16 0x562e0002cb42 in main /root/vtr-verilog-to-routing/vtr-verilog-to-routing/vpr/src/main.cpp:62
#17 0x7f81ddfb9c86 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21c86)
#18 0x562e00041699 in _start (/root/vtr-verilog-to-routing/vtr-verilog-to-routing/build/vpr/vpr+0x6091699)

Solution

These errors are complaining about accessing a ClusterNetlist type while Netlist is expected. As I explained in the previous comment, ClusterNetlist is inherited from Netlist.

To pass the CI Tests, I remove "-fsanitize=undefined" from sanitizer flags in CMake file.

Any Suggestion?

@hzeller: This kind of inheritance was the fastest way I could think about to get the flat_routing running. For the future, I am thinking about creating another class, e.g. RouterNetlist, which has a reference to both netlists and use that in the routing functions. If you have any other suggestions on how to implement it, I would appreciate it.

[vaughnbetz]

1. It's interesting that these errors only occur after the main router runs, so they aren't happening all the time when you use the router netlist. The router must use some base netlist methods too so I wonder why they don't also give a type mismatch error?
2. The sanitizers are flagging a bunch of memory leaks (in strange routines, like is_global, that seem unlikely to leak memory) while valgrind doesn't. Do these sanitizer memory leaks show up all the time, or only on your branch where you have added flat routing? Not sure why we're getting them, but if they show up all the time and you're sure they're not real we could add them to the sanitizer suppression file.
3. Could we make these go away with an explicit cast? If I'm reading these correctly, the undefined error is that it thinks we're calling a Netlist method with a ClusteredNetlist. But that should work since CluseteredNetlist is derived class of Netlist.

[vaughnbetz]

There also appears to be a finer granularity to turn off error checking in the sanitizers, so possibly we could turn off less (although it seems we'd have to specify a lot of options then, as undefined is a catch all for ~30 checks.

[amin1377]

1. It's interesting that these errors only occur after the main router runs, so they aren't happening all the time when you use the router netlist. The router must use some base netlist methods too so I wonder why they don't also give a type mismatch error?
2. The sanitizers are flagging a bunch of memory leaks (in strange routines, like is_global, that seem unlikely to leak memory) while valgrind doesn't. Do these sanitizer memory leaks show up all the time, or only on your branch where you have added flat routing? Not sure why we're getting them, but if they show up all the time and you're sure they're not real we could add them to the sanitizer suppression file.
3. Could we make these go away with an explicit cast? If I'm reading these correctly, the undefined error is that it thinks we're calling a Netlist method with a ClusteredNetlist. But that should work since CluseteredNetlist is derived class of Netlist.

1: The attached file is for a run that the minimum channel width is not specified, so router is called several times. For the first router run, it printed out some errors, but for the subsequent runs, it didn't print anything.

2: I ran the master branch with the same argument as the attached output files, and it did not print the same errors. I checked the reported leaks related to calling "net_is_global" function, and since these error are being raised during routing, based on the printed function call hierarchy, I believe they are caused by casting Clustered/AtomNetlist to Netlist.

3: I am already using explicit type casting. When I want to pass a ClusterNetlist or an AtomNetlist to a function, I should do an explicit type casting. This is because the parent netlist class is a template class. Thus, if I want to do a normal upcasting, the template values for the Netlist class that the function accepts should be equal to the template values of the Netlist Class which ClusterNetlist is inherited, which is not the case. The template values for the function's netlist are: ParentNetId, ParentBlockId, etc, and the Netlist's template values that ClusterNetlist is inherited from are: ClusterNetId, ClusterBlockId, etc.