[LibVTRUtil] Confusing API for vtr::rect

[AlexandreSinger]

While working on the initial placer in VTR, I found a bug when the code is performing centroid placement and is determining if a centroid placement is legal or not:

vtr-verilog-to-routing/vpr/src/place/initial_placement.cpp

Lines 302 to 333 in 848d1e7

	static bool is_loc_legal(const t_pl_loc& loc,
	const PartitionRegion& pr,
	t_logical_block_type_ptr block_type) {
	const auto& grid = g_vpr_ctx.device().grid;
	bool legal = false;
	//Check if the location is within its constraint region
	for (const auto& reg : pr.get_regions()) {
	const vtr::Rect<int>& reg_rect = reg.get_rect();
	const auto [layer_low, layer_high] = reg.get_layer_range();
	if (loc.layer > layer_high || loc.layer < layer_low) {
	continue;
	}
	if (reg_rect.contains({loc.x, loc.y})) {
	//check if the location is compatible with the block type
	const auto& type = grid.get_physical_type({loc.x, loc.y, loc.layer});
	int height_offset = grid.get_height_offset({loc.x, loc.y, loc.layer});
	int width_offset = grid.get_width_offset({loc.x, loc.y, loc.layer});
	if (is_tile_compatible(type, block_type)) {
	//Check if the location is an anchor position
	if (height_offset == 0 && width_offset == 0) {
	legal = true;
	break;
	}
	}
	}
	}
	return legal;
	}

The issue is that the code creates a partition region that is the size of the device for unconstrained blocks. For example, for an 11x11 architecture it creates a rectangle from (0, 0) to (10, 10). The problem is that this code uses the contains method from vtr::rect. This does not include the top-right edges; so any centroids which were placed on the top-right edge of the device were being wrongfully rejected.

vtr-verilog-to-routing/libs/libvtrutil/src/vtr_geometry.h

Lines 171 to 181 in 848d1e7

	///@brief Returns true if the point is fully contained within the rectangle (excluding the top-right edges)
	bool contains(Point<T> point) const;
	///@brief Returns true if the point is strictly contained within the region (excluding all edges)
	bool strictly_contains(Point<T> point) const;
	///@brief Returns true if the point is coincident with the rectangle (including the top-right edges)
	bool coincident(Point<T> point) const;
	///@brief Returns true if other is contained within the rectangle (including all edges)
	bool contains(const Rect<T>& other) const;

An easy fix for this problem is to use the coincident method instead; however, there may be other misunderstandings throughout VTR which need to be investigated.

In reality, this interface is a little confusing, and these methods should be renamed or even removed if they are not being used.

We will need to look through the code for cases where these methods are used and ensure they are correct.

[AlexandreSinger]

@soheilshahrouz @vaughnbetz FYI, this was the issue that I found in the initial placer.

[vaughnbetz]

Good catch, and this is bizarre. I'm not sure why we'd want two definitions of contains/coincident. I agree it should be at least renamed, and if there is no good use case for the current coincident vs. contains we should remove one (I vote for coincident) and have the other do the usual check where you include the edges.

[vaughnbetz]

It might be that since these methods were defined with a template parameter someone was worried about the version not checking for inclusion / equality (although I'm not sure why). The behaviour doesn't make sense for an though, and I suspect it doesn't make much difference for