Update comments on pruning functions.
Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com>
diff --git a/vpr/src/route/route_tree_timing.cpp b/vpr/src/route/route_tree_timing.cpp
index d51aa5d..0e1ac4f 100644
--- a/vpr/src/route/route_tree_timing.cpp
+++ b/vpr/src/route/route_tree_timing.cpp
@@ -1070,9 +1070,41 @@
// 3. The node set is not active
//
// Then prune this node.
+ //
if (non_config_node_set_usage != nullptr && node_set != -1 && device_ctx.rr_switch_inf[node->parent_switch].configurable() && (*non_config_node_set_usage)[node_set] == 0) {
// This node should be pruned, re-prune edges once more.
- return prune_route_tree_recurr(node, connections_inf, /*force_prune=*/false, non_config_node_set_usage);
+ //
+ // If the following is true:
+ //
+ // - The node set is unused
+ // (e.g. (*non_config_node_set_usage)[node_set] == 0)
+ // - This particular node still had children
+ // (which is true by virtue of being in this else statement)
+ //
+ // Then that indicates that the node set became unused during the
+ // pruning. One or more of the children of this node will be
+ // pruned if prune_route_tree_recurr is called again, and
+ // eventually the whole node will be prunable.
+ //
+ // Consider the following graph:
+ //
+ // 1 -> 2
+ // 2 -> 3 [non-configurable]
+ // 2 -> 4 [non-configurable]
+ // 3 -> 5
+ // 4 -> 6
+ //
+ // Assume that nodes 5 and 6 do not connect to a sink, so they
+ // will be pruned (as normal). When prune_route_tree_recurr
+ // visits 2 for the first time, node 3 or 4 will remain. This is
+ // because when prune_route_tree_recurr visits 3 or 4, it will
+ // not have visited 4 or 3 (respectively). As a result, either
+ // node 3 or 4 will not be pruned on the first pass, because the
+ // node set usage count will be > 0. However after
+ // prune_route_tree_recurr visits 2, 3 and 4, the node set usage
+ // will be 0, so everything can be pruned.
+ return prune_route_tree_recurr(node, connections_inf,
+ /*force_prune=*/false, non_config_node_set_usage);
}
//An unpruned intermediate node
diff --git a/vpr/src/route/route_tree_timing.h b/vpr/src/route/route_tree_timing.h
index ae67a15..01e4d88 100644
--- a/vpr/src/route/route_tree_timing.h
+++ b/vpr/src/route/route_tree_timing.h
@@ -55,7 +55,17 @@
t_rt_node* traceback_to_route_tree(t_trace* head, std::vector<int>* non_config_node_set_usage);
t_trace* traceback_from_route_tree(ClusterNetId inet, const t_rt_node* root, int num_remaining_sinks);
+// Prune route tree
+//
+// Note that non-configurable node will not be pruned unless the node is
+// being totally ripped up, or the node is congested.
t_rt_node* prune_route_tree(t_rt_node* rt_root, CBRR& connections_inf);
+
+// Prune route tree
+//
+// Note that non-configurable nodes will be pruned if
+// non_config_node_set_usage is provided. prune_route_tree will update
+// non_config_node_set_usage after pruning.
t_rt_node* prune_route_tree(t_rt_node* rt_root, CBRR& connections_inf, std::vector<int>* non_config_node_set_usage);
void pathfinder_update_cost_from_route_tree(const t_rt_node* rt_root, int add_or_sub, float pres_fac);
