vpr/src/route/build_switchblocks.cpp

/*
Author(s): Oleg Petelin
Last revised: September, 2015

************ NEW SWITCH BLOCK HIGH-LEVEL DESCRIPTION ************
The new switch block description format allows a much finer level of control over the switch blocks generated by VPR.
Whereas a user previously only had the choice of 'wilton', 'universal', 'subset', or 'full' switch blocks, the new
format allows a user to specify a small set of mathematical formulas that describe the switch block connections. This format
allows the specification of all the switch blocks previously available in VPR as well as a great number of new switch block patterns.

The new switch block description format is loosely based on chapter 7 of Lemieux' and Lewis' "Design of Interconnection Networks
for Programmable Logic" book (2004).


************ FILES AND THEIR PURPOSE ************
The overall flow of parsing and building the new switch blocks involves reading switch block descriptions from the VPR
architecture file and then building the switch blocks according to these descriptions in build_rr_graph (rr_graph.c).
This functionality is split across different files which are described below:

  * read_xml_arch_file.c (under libarchfpga):
    * calls ProcessSwitchblocks which fills s_arch-->switchblocks with info about each user-defined switch blocks
      * calls functions from parse_switchblocks.c to build switch block data structures (reads-in permutation functions
        and wire segment source/dest connection info)
    * ProcessSegments has been modified to give a string name to each segment type (in t_segment_inf).
  * parse_switchblocks.c (under libarchfpga):
    * provides functions to help load switch block data structures during XML parsing of VPR architecture file
    * provides functions to evaluate switch block permutation formulas and return a numeric result
  * SetupVPR.c:
    * SetupRoutingArch copies switch block information from s_arch to s_det_routing_arch
  * physical_types.h (under libarchfpga):
    * defines classes, structs and typedefs for parsing switch blocks from XML architecture file
  * vpr_types.h
    * s_det_routing_arch carries info about custom switch blocks
  * build_switchblocks.c (this file):
    * builds t_sb_connection_map sparse array containing target connections for each wire in each horizontal/vertical channel segment.
      'compute_wire_connections' is the most important function here -- it computes the set of wire segments that a given wire at
      (x, y, from_side, to_side, from_wire) should connect to.
  * rr_graph.c:
    * calls alloc_and_load_switchblock_permutations (from build_switchblocks.c) which creates the t_sb_connection_map
  * rr_graph2.c:
    * get_wire_to_chan_seg is called within get_wire_to_wires which looks at t_sb_connection_map to create the edges that
      connect a source wire segment into a destination channel segment


************ DESCRIPTION OF SWITCH BLOCK SPECIFICATION ************
Some terminology:

  * Wire segment type: a named group of wires defined in the architecture file.
  * Wire subsegment number: a number assigned to a wire subsegment relative to the wire's start coordinate (see diagram below).
       Used to define a collection of wire segments that have a start point in the same column (or row) of the FPGA.
  * Wire switch point: a number assigned to a specific switch block along a wire segment

Ex: for a length-4 unidirectional wire segment going in the decreasing direction:
  wire switch point    0<-------3<-------2<-------1<-------0
  wire subsegment #         3        2        1        0

The new switch block format allows a user to specify mathematical permutation functions that describe how different types of wires will connect at different switchpoinnts. One or more wire types *and* one or more switch points define a set of wires, and each switch block connection is specified in terms of a source and destination set. Specifically, the permutation functions prescribe how a set of from_type/from_switchpoint wires (the source set) in one channel segment should connect to a set of to_type/to_switchpoint wires (the destination set) in an adjacent channel segment. This provides for an abstract but very flexible way of specifying different switch block patterns.

An example from an XML VPR architecture file is given below.

The 'wireconn' entries define ordered source/destination sets of wire segments that should be connected with the specified permutation functions. The wireconn entries essentially "re-index" the channel so that a permutation function of 't/2' means that the t'th wire segment in the source wireconn set should connect to the [(t/2)%W]'th wire segment in the destination set where W is the size, or effective channel width, of the destination set (note that permutation functions are implicitly modulo W so that all functions evaluate to a number that indexes into the destination set).

  <!-- Specify that custom switch blocks will be used. This is backwards compatible with VPR's previous wilton/subset/univeral specification,
       but "custom" is specified instead. -->
  <switch_block type="custom"/>			<-- backwards-compatible with VPR's previous wilton/subset/universal/full specification
  ...
  ...
  <!-- Segment specification is as before, except that a "name" is also specified for each segment. Each segment defines a type of wire. -->
  <segmentlist>
    <segment freq="0.85" name="l4" length="4" type="unidir" Rmetal="232" Cmetal="0.0">
      <mux name="l4_mux"/>
      <sb type="pattern">1 1 1 1 1</sb>
      <cb type="pattern">1 1 1 1</cb>
    </segment>
    <segment freq="0.15" name="l8_global" length="8" type="unidir" Rmetal="33.8" Cmetal="0.0">
      <mux name="l8_mux"/>
      <sb type="pattern">1 1 1 1 1 1 1 1 1</sb>
      <cb type="pattern">1 1 1 1 1 1 1 1</cb>
    </segment>
  </segmentlist>
  ...
  ...
  <!-- Custom switch blocks are declared here -->
  <switchblocklist>
    <!-- Each "switchblock" entry is given a name. Type specifies either a unidirectional or bidirectional switch block -->
    <switchblock name="my_switchblock" type="unidir">
      <!-- Location to implement this switch block (EVERYWHERE/CORE/PERIMETER/CORNER/FRINGE) -->
      <switchblock_location type="EVERYWHERE"/>
      <!-- A list of permutation functions. Any number can be specified (for instance two "lt" entries can be specified to increase
           Fs of connections from the left to the top switch block sides -->
      <switchfuncs>
        <!-- "lr" means left-to-right, "lt" means left to top, etc. Formulas support different operators which are discussed later -->
        <func type="lr" formula="t"/>
        <func type="lt" formula="W-t"/>
        <func type="lb" formula="W+t-1"/>
        <func type="rt" formula="W+t-1"/>
        <func type="br" formula="W-t-2"/>
        <func type="bt" formula="t"/>
        <func type="rl" formula="t"/>
        <func type="tl" formula="W-t"/>
        <func type="bl" formula="W+t-1"/>
        <func type="tr" formula="W+t-1"/>
        <func type="rb" formula="W-t-2"/>
        <func type="tb" formula="t"/>
      </switchfuncs>
      <!-- Wireconn entries define the sets of wires that should be connected with the above permutation functions -->
      <wireconn from_type="l4" to_type="l4" from_switchpoint="0,1,2,3" to_switchpoint="0"/>
      <wireconn from_type="l8_global" to_type="l8_global" from_switchpoint="0,4" to_switchpoint="0"/>
      <wireconn from_type="l8_global" to_type="l4" from_switchpoint="0,4" to_switchpoint="0"/>
    </switchblock>

    <switchblock name="another_switch_block" type="unidir">
      ... switch block description ...
    </switchblock>
  </switchblocklist>

Allowed symmbols and operators for the switch block permutation functions are described below (recall
that formulas are evaluated in 'parse_switchblocks.c'):
  * "+" -- addition
  * "-" -- subtraction
  * "/" -- division
  * "*" -- multiplication
  * "t" -- index of the wire segment in the source set
  * "W" -- size of the destination set

*/

#include <cstring>
#include <algorithm>
#include <iterator>
#include <iostream>

#include "vtr_assert.h"
#include "vtr_memory.h"

#include "vpr_error.h"

#include "build_switchblocks.h"
#include "physical_types.h"
#include "parse_switchblocks.h"

using namespace std;


/************ Defines ************/
/* if defined, switch block patterns are loaded by first computing a row of switch blocks and then
   stamping out the row throughout the FPGA */
//#define FAST_SB_COMPUTATION

/* REF_X/REF_Y set a reference coordinate; some look-up structures in this file are computed relative to
   this reference */
#define REF_X 1			//constexpr int REX_X = 1;	<-- basically C++11 defines; more type-safe
#define REF_Y 1


/************ Classes ************/
/* contains info about a wire segment type */
class Wire_Info{
public:
	int length;		/* the length of this type of wire segment in tiles */
	int num_wires;		/* total number of wires in a channel segment (basically W) */
	int start;		/* the wire index at which this type starts in the channel segment (0..W-1) */

	void set(int len, int wires, int st){
		length = len; num_wires = wires; start = st;
	}
	Wire_Info(){
		this->set(0, 0, 0);
	}
	Wire_Info(int len, int wires, int st){
		this->set(len, wires, st);
	}
};


/************ Typedefs ************/
/* Used to get info about a given wire type based on the name */
typedef map< string, Wire_Info > t_wire_type_sizes;


/************ Function Declarations ************/
/* Counts the number of wires in each wire type in the specified channel */
static void count_wire_type_sizes(t_seg_details *channel, int nodes_per_chan,
			t_wire_type_sizes *wire_type_sizes);

#ifdef FAST_SB_COMPUTATION
/* over all connected wire types (i,j), compute the maximum least common multiple of their wire lengths,
   ie max(LCM(L_i, L_J)) */
static int get_max_lcm(vector<t_switchblock_inf> *switchblocks, t_wire_type_sizes *wire_type_sizes);

/* compute all the switchblocks around the perimeter of the FPGA for the given switchblock and wireconn */
static void compute_perimeter_switchblocks(t_chan_details *chan_details_x, t_chan_details *chan_details_y,
		vector<t_switchblock_inf> *switchblocks, const DeviceGrid& grid, int nodes_per_chan,
		t_wire_type_sizes *wire_type_sizes, e_directionality directionality,
		t_sb_connection_map *sb_conns);

/* computes a horizontal line of switchblocks of size sb_row_size (or of grid.width()-4, whichever is smaller), starting
   at coordinate (1,1) */
static void compute_switchblock_row(int sb_row_size, t_chan_details *chan_details_x, t_chan_details *chan_details_y,
		vector<t_switchblock_inf> *switchblocks, const DeviceGrid& grid, int nodes_per_chan,
		t_wire_type_sizes *wire_type_sizes, e_directionality directionality,
		t_sb_connection_map *sb_row);

/* stamp out a line of horizontal switchblocks starting at coordinates (ref_x, ref_y) and
   continuing on for sb_row_size */
static void stampout_switchblocks_from_row( int sb_row_size,
		int nodes_per_chan,
		const DeviceGrid& grid, t_wire_type_sizes *wire_type_sizes,
		e_directionality directionality, t_sb_connection_map *sb_row,
		t_sb_connection_map *sb_conns );

#endif	//FAST_SB_COMPUTATION

/* Compute the wire(s) that the wire at (x, y, from_side, to_side, from_wire) should connect to.
   sb_conns is updated with the result */
static void compute_wire_connections(int x_coord, int y_coord,
            enum e_side from_side, enum e_side to_side,
            const t_chan_details& chan_details_x, const t_chan_details& chan_details_y,
            t_switchblock_inf *sb,
            const DeviceGrid& grid,
			t_wire_type_sizes *wire_type_sizes, e_directionality directionality,
			t_sb_connection_map *sb_conns);

/* ... sb_conn represents the 'coordinates' of the desired switch block connections */
static void compute_wireconn_connections(const DeviceGrid& grid, e_directionality directionality,
		const t_chan_details& from_chan_details, const t_chan_details& to_chan_details, Switchblock_Lookup sb_conn,
		int from_x, int from_y, int to_x, int to_y, t_rr_type from_chan_type, t_rr_type to_chan_type,
		t_wire_type_sizes *wire_type_sizes, t_switchblock_inf *sb,
		t_wireconn_inf *wireconn_ptr, t_sb_connection_map *sb_conns);

/* returns the wire indices belonging to the types in 'wire_type_vec' and switchpoints in 'points' at the given channel segment */
static void get_switchpoint_wires(const DeviceGrid& grid, const t_seg_details* chan_details,
		t_rr_type chan_type, int x, int y, e_side side, const vector<t_wire_switchpoints>& wire_switchpoints_vec,
		t_wire_type_sizes *wire_type_sizes, bool is_dest, vector<int> *wires);

static const t_chan_details& index_into_correct_chan(int tile_x, int tile_y, enum e_side side,
			const t_chan_details& chan_details_x, const t_chan_details& chan_details_y,
			int *chan_x, int *chan_y,
			t_rr_type* chan_type);

/* checks whether the specified coordinates are out of bounds */
static bool coords_out_of_bounds(const DeviceGrid& grid, int x_coord, int y_coord,
			e_rr_type chan_type);

/* returns the subsegment number of the specified wire at seg_coord*/
static int get_wire_subsegment_num(const DeviceGrid& grid, e_rr_type chan_type,
		    const t_seg_details &wire_details, int seg_coord);

int get_wire_segment_length(const DeviceGrid& grid, e_rr_type chan_type, const t_seg_details &wire_details);

/* Returns the switchpoint of the wire specified by wire_details at a segment coordinate
   of seg_coord, and connection to the sb_side of the switchblock */
static int get_switchpoint_of_wire(const DeviceGrid& grid, e_rr_type chan_type,
		const t_seg_details &wire_details, int seg_coord, e_side sb_side);

/* returns true if the coordinates x/y do not correspond to the location specified by 'location' */
static bool sb_not_here(const DeviceGrid& grid, int x, int y, e_sb_location location);

/* checks if the specified coordinates represent a corner of the FPGA */
static bool is_corner(const DeviceGrid& grid, int x, int y);

/* checks if the specified coordinates correspond to one of the perimeter switchblocks */
static bool is_perimeter(const DeviceGrid& grid, int x, int y);

/* checks if the specified coordinates correspond to the core of the FPGA (i.e. not perimeter) */
static bool is_core(const DeviceGrid& grid, int x, int y);

/* adjusts a negative destination wire index calculated from a permutation formula */
static int adjust_formula_result(int dest_wire, int src_W, int dest_W, int connection_ind);



/************ Function Definitions ************/
/* allocate and build the switchblock permutation map */
t_sb_connection_map * alloc_and_load_switchblock_permutations(
                const t_chan_details& chan_details_x, const t_chan_details& chan_details_y,
                const DeviceGrid& grid,
				vector<t_switchblock_inf> switchblocks,
				t_chan_width *nodes_per_chan, e_directionality directionality){

	/* get a single number for channel width */
	int channel_width = nodes_per_chan->max;
	if (nodes_per_chan->max != nodes_per_chan->x_min || nodes_per_chan->max != nodes_per_chan->y_min){
		vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "Custom switch blocks currently support consistent channel widths only.");
	}

	/* sparse array that will contain switch block connections */
	t_sb_connection_map *sb_conns = new t_sb_connection_map;

	/* We assume that x & y channels have the same ratios of wire types. i.e., looking at a single
	   channel is representative of all channels in the FPGA -- as of 3/9/2013 this is true in VPR */
	t_wire_type_sizes wire_type_sizes;
	count_wire_type_sizes(chan_details_x[0][0], channel_width, &wire_type_sizes);

#ifdef FAST_SB_COMPUTATION
	/******** fast switch block computation method; computes a row of switchblocks then stamps it out everywhere ********/
	/* figure out max(lcm(L_i, L_j)) for all wire lengths belonging to wire types i & j */
	int max_lcm = get_max_lcm(&switchblocks, &wire_type_sizes);
	t_sb_connection_map sb_row;

	/* compute the perimeter switchblocks. unfortunately we can't just compute corners and stamp out the rest because
	   for a unidirectional architecture corners AND perimeter switchblocks require special treatment */
	compute_perimeter_switchblocks( chan_details_x, chan_details_y, &switchblocks,
			grid, channel_width, &wire_type_sizes, directionality, sb_conns);

	/* compute the switchblock row */
	compute_switchblock_row( max_lcm, chan_details_x, chan_details_y, &switchblocks,
			grid, channel_width, &wire_type_sizes, directionality, &sb_row );

	/* stamp-out the switchblock row throughout the rest of the FPGA */
	stampout_switchblocks_from_row( max_lcm, channel_width,
			grid, &wire_type_sizes, directionality, &sb_row, sb_conns );

#else
	/******** slow switch block computation method; computes switchblocks at each coordinate ********/
	/* iterate over all the switchblocks specified in the architecture */
	for (int i_sb = 0; i_sb < (int)switchblocks.size(); i_sb++){
		t_switchblock_inf sb = switchblocks[i_sb];

		/* verify that switchblock type matches specified directionality -- currently we have to stay consistent */
		if (directionality != sb.directionality){
			vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "alloc_and_load_switchblock_connections: Switchblock %s does not match directionality of architecture\n", sb.name.c_str());
		}
		/* Iterate over the x,y coordinates spanning the FPGA. */
		for (size_t x_coord = 0; x_coord < grid.width(); x_coord++){
			for (size_t y_coord = 0; y_coord <= grid.height(); y_coord++){
				if (sb_not_here(grid, x_coord, y_coord, sb.location)){
					continue;
				}
                /* now we iterate over all the potential side1->side2 connections */
                for (e_side from_side : {TOP, RIGHT, BOTTOM, LEFT}) {
                    for (e_side to_side : {TOP, RIGHT, BOTTOM, LEFT}) {

                        /* Fill appropriate entry of the sb_conns map with vector specifying the wires
                           the current wire will connect to */
                        compute_wire_connections(x_coord, y_coord, from_side, to_side,
                                chan_details_x, chan_details_y, &sb, grid,
                                &wire_type_sizes, directionality, sb_conns);

                    }
                }
			}
		}
	}
#endif

	return sb_conns;
}


/* deallocates switch block connections sparse array */
void free_switchblock_permutations(t_sb_connection_map *sb_conns){
	sb_conns->clear();
	delete sb_conns;
	sb_conns = nullptr;
	/* the switch block unordered_map can get quite large and it doesn't seem like the program
	   is interested in releasing the memory back to the OS after the map is cleared.
	   calling malloc_trim forces the program to give unused heap space back to the OS.
	   this significantly reduces memory usage during the routing stage when running multiple
	   large benchmark circuits in parallel. */
    vtr::malloc_trim(0);
	return;
}

#ifdef FAST_SB_COMPUTATION
/* over all connected wire types (i,j), compute the maximum least common multiple of their wire lengths,
   ie max(LCM(L_i, L_J)) */
static int get_max_lcm( vector<t_switchblock_inf> *switchblocks, t_wire_type_sizes *wire_type_sizes){
	int max_lcm = -1;
	int num_sb = (int)switchblocks->size();

	/* over each switchblock */
	for (int isb = 0; isb < num_sb; isb++){
		t_switchblock_inf *sb = &(switchblocks->at(isb));
		int num_wireconns = (int)sb->wireconns.size();
		/* over each wireconn */
		for (int iwc = 0; iwc < num_wireconns; iwc++){
			t_wireconn_inf *wc = &(sb->wireconns[iwc]);
			int num_from_types = (int)wc->from_type.size();
			int num_to_types = (int)wc->to_type.size();
			/* over each from type */
			for (int ifrom = 0; ifrom < num_from_types; ifrom++){
				/* over each to type */
				for (int ito = 0; ito < num_to_types; ito++){
                    if ((*wire_type_sizes).find(wc->from_type[ifrom]) != (*wire_type_sizes).end() &&
                        (*wire_type_sizes).find(wc->to_type[ito]) != (*wire_type_sizes).end()) {
                        // the condition can fail if freq of a seg is 0 (so it is in wc, but not in wire_type_size)
    					int length1 = wire_type_sizes->at(wc->from_type[ifrom]).length;
	    				int length2 = wire_type_sizes->at(wc->to_type[ito]).length;
		    			int current_lcm = vtr::lcm(length1, length2);
			    		if (current_lcm > max_lcm){
						    max_lcm = current_lcm;
					    }
                    }
				}
			}
		}
	}

	return max_lcm;
}

/* computes a horizontal row of switchblocks of size sb_row_size (or of grid.width()-4, whichever is smaller), starting
   at coordinate (1,1) */
static void compute_switchblock_row(int sb_row_size, t_chan_details *chan_details_x, t_chan_details *chan_details_y,
		vector<t_switchblock_inf> *switchblocks, const DeviceGrid& grid, int nodes_per_chan,
		t_wire_type_sizes *wire_type_sizes, e_directionality directionality,
		t_sb_connection_map *sb_row){

	int y = 1;
	for (int isb = 0; isb < (int)switchblocks->size(); isb++){
		t_switchblock_inf *sb = &(switchblocks->at(isb));
		for (int x = 1; x < 1 + sb_row_size; x++){
			if (sb_not_here(grid, x, y, sb->location)){
				continue;
			}
            /* now we iterate over all the potential side1->side2 connections */
            for (e_side from_side : {TOP, RIGHT, BOTTOM, LEFT}) {
                for (e_side to_side : {TOP, RIGHT, BOTTOM, LEFT}) {

                    /* Fill appropriate entry of the sb_conns map with vector specifying the wires
                       the current wire will connect to */
                    compute_wire_connections(x, y, from_side, to_side,
                            chan_details_x, chan_details_y, sb, grid,
                            wire_type_sizes, directionality, sb_row);
                }
            }
		}
	}
}


/* stamp out a row of horizontal switchblocks throughout the FPGA starting at coordinates (ref_x, ref_y) and
   continuing on for sb_row_size */
static void stampout_switchblocks_from_row( int sb_row_size,
		int nodes_per_chan,
		const DeviceGrid& grid, t_wire_type_sizes *wire_type_sizes,
		e_directionality directionality, t_sb_connection_map *sb_row,
		t_sb_connection_map *sb_conns ){

	/* over all x coordinates that may need stamping out */
	for (int x = 1; x < grid.width() - 2; x++){ //-2 for no perim channels
		/* over all y coordinates that may need stamping out */
		for (int y = 1; y < grid.height() - 2; y++){ //-2 for no perim channels
			/* perimeter has been precomputed */
			if ( is_perimeter(grid, x, y) ){
				continue;
			}
			/* over each source side */
            for (e_side from_side : {TOP, RIGHT, BOTTOM, LEFT}) {

				/* over each destination side */
                for (e_side to_side : {TOP, RIGHT, BOTTOM, LEFT}) {

					/* can't connect a side to itself */
					if (from_side == to_side){
						continue;
					}
					/* over each source wire */
					for (int iwire = 0; iwire < nodes_per_chan; iwire++){
						/* get the total x+y distance of the current switchblock from the reference switchblock */
						int distance = (x - REF_X) + (y - REF_Y);
						if (distance < 0){
							distance = sb_row_size - ((-1*distance)%sb_row_size);
						}
						/* figure out the coordinates of the switchblock we want to copy */
						int copy_y = 1;
						int copy_x = 1 + (distance % sb_row_size);	//TODO: based on what? explain staggering pattern

						/* create the indices to key into the switchblock permutation map */
						Switchblock_Lookup my_key(x, y, from_side, to_side, iwire);
						Switchblock_Lookup copy_key(copy_x, copy_y, from_side, to_side, iwire);

						if ( sb_row->count(copy_key) == 0 ){
							continue;
						}

						(*sb_conns)[my_key] = sb_row->at(copy_key);
					}
				}
			}
		}
	}
}


/* compute all the switchblocks around the perimeter of the FPGA for the given switchblock and wireconn */
static void compute_perimeter_switchblocks(t_chan_details *chan_details_x, t_chan_details *chan_details_y,
		vector<t_switchblock_inf> *switchblocks, const DeviceGrid& grid, int nodes_per_chan,
		t_wire_type_sizes *wire_type_sizes, e_directionality directionality,
		t_sb_connection_map *sb_conns){
	int x, y;

	for (int isb = 0; isb < (int)switchblocks->size(); isb++){
		/* along left and right edge */
		x = 0;
		t_switchblock_inf *sb = &(switchblocks->at(isb));
		for (int i = 0; i < 2; i++){				//TODO: can use i+=grid.width()-2 to make more explicit what the ranges of the loop are
			for (y = 0; y < grid.height(); y++){
				if (sb_not_here(grid, x, y, sb->location)){
					continue;
				}
                /* now we iterate over all the potential side1->side2 connections */
                for (e_side from_side : {TOP, RIGHT, BOTTOM, LEFT}) {
                    for (e_side to_side : {TOP, RIGHT, BOTTOM, LEFT}) {

                        /* Fill appropriate entry of the sb_conns map with vector specifying the wires
                           the current wire will connect to */
                        compute_wire_connections(x, y, from_side, to_side,
                                chan_details_x, chan_details_y, sb, grid,
                                wire_type_sizes, directionality, sb_conns);
                    }
                }
			}
			x = grid.width() - 2; //-2 for no perim channels
		}
	}

	for (int isb = 0; isb < (int)switchblocks->size(); isb++){
		/* along bottom and top edge */
		y = 0;
		t_switchblock_inf *sb = &(switchblocks->at(isb));
		for (int i = 0; i < 2; i++){
			for (x = 0; x < grid.width(); x++){
				if (sb_not_here(grid, x, y, sb->location)){
					continue;
				}
                /* now we iterate over all the potential side1->side2 connections */
                for (e_side from_side : {TOP, RIGHT, BOTTOM, LEFT}) {
                    for (e_side to_side : {TOP, RIGHT, BOTTOM, LEFT}) {

                        /* Fill appropriate entry of the sb_conns map with vector specifying the wires
                           the current wire will connect to */
                        compute_wire_connections(x, y, from_side, to_side,
                                chan_details_x, chan_details_y, sb, grid,
                                wire_type_sizes, directionality, sb_conns);
                    }
                }
			}
			y = grid.height() - 2; //-2 for no perim channels
		}
	}
}

#endif	//FAST_SB_COMPUTATION

/* returns true if the coordinates x/y do not correspond to the location specified by 'location' */
static bool sb_not_here(const DeviceGrid& grid, int x, int y, e_sb_location location){
	bool sb_not_here = true;

	switch( location ){
		case E_EVERYWHERE:
			sb_not_here = false;
			break;
		case E_PERIMETER:
			if (is_perimeter(grid, x, y)){
				sb_not_here = false;
			}
			break;
		case E_CORNER:
			if (is_corner(grid, x, y)){
				sb_not_here = false;
			}
			break;
		case E_CORE:
			if (is_core(grid, x, y)){
				sb_not_here = false;
			}
			break;
		case E_FRINGE:
			if (is_perimeter(grid, x, y) && !is_corner(grid, x, y)){
				sb_not_here = false;
			}
			break;
		default:
			vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "sb_not_here: unrecognized location enum: %d\n", location);
			break;
	}
	return sb_not_here;
}


/* checks if the specified coordinates represent a corner of the FPGA */
static bool is_corner(const DeviceGrid& grid, int x, int y){
	bool is_corner = false;
	if ((x == 0 && y == 0) ||
	    (x == 0 && y == int(grid.height()) - 2) || //-2 for no perim channels
	    (x == int(grid.width()) - 2 && y == 0) || //-2 for no perim channels
	    (x == int(grid.width()) - 2 && y == int(grid.height()) - 2)){ //-2 for no perim channels
		is_corner = true;
	}
	return is_corner;
}


/* checks if the specified coordinates correspond to one of the perimeter switchblocks */
static bool is_perimeter(const DeviceGrid& grid, int x, int y){
	bool is_perimeter = false;
	if (x == 0 || x == int(grid.width()) - 2 ||
	    y == 0 || y == int(grid.height()) - 2){
		is_perimeter = true;
	}
	return is_perimeter;
}


/* checks if the specified coordinates correspond to the core of the FPGA (i.e. not perimeter) */
static bool is_core(const DeviceGrid& grid, int x, int y){
	bool is_core = !is_perimeter(grid, x, y);
	return is_core;
}


/* Counts the number of wires in each wire type in the specified channel */
static void count_wire_type_sizes(t_seg_details *channel, int nodes_per_chan,
			t_wire_type_sizes *wire_type_sizes){
	string wire_type;
	string new_type;
	int new_length, length;
	int new_start, start;
	int num_wires = 0;
	Wire_Info wire_info;

	wire_type = channel[0].type_name;
	length = channel[0].length;
	start = 0;
	for (int iwire = 0; iwire < nodes_per_chan; iwire++){
		new_type = channel[iwire].type_name;
		new_length = channel[iwire].length;
		new_start = iwire;
        if (new_type != wire_type){
			wire_info.set(length, num_wires, start);
			(*wire_type_sizes)[wire_type] = wire_info;
			wire_type = new_type;
			length = new_length;
			start = new_start;
			num_wires = 0;
		}
		num_wires++;
	}
	wire_info.set(length, num_wires, start);
	(*wire_type_sizes)[wire_type] = wire_info;

	return;
}


/* returns the wire indices belonging to the types in 'wire_type_vec' and switchpoints in 'points' at the given channel segment */
static void get_switchpoint_wires(const DeviceGrid& grid, const t_seg_details* chan_details,
		t_rr_type chan_type, int x, int y, e_side side, const vector<t_wire_switchpoints>& wire_switchpoints_vec,
		t_wire_type_sizes *wire_type_sizes, bool is_dest, vector<int> *wires){

	wires->clear();

	int seg_coord = x;
	if (chan_type == CHANY){
		seg_coord = y;
	}

	for (const t_wire_switchpoints& wire_switchpoints : wire_switchpoints_vec){

		const auto& wire_type = wire_switchpoints.segment_name;
        const auto& points = wire_switchpoints.switchpoints;

		if ((*wire_type_sizes).find(wire_type) == (*wire_type_sizes).end()) {
		    // wire_type_sizes may not contain wire_type if its seg freq is 0
		    continue;
		}
		/* get the number of wires of given type */
		int num_type_wires = wire_type_sizes->at(wire_type).num_wires;
		/* get the last wire belonging to this type */
		int first_type_wire = wire_type_sizes->at(wire_type).start;
		int last_type_wire = first_type_wire + num_type_wires - 1;


		/* walk through each wire segment of specified type and check whether it matches one
		   of the specified switchpoints */
		for (int iwire = first_type_wire; iwire <= last_type_wire; iwire++){
			e_direction seg_direction = chan_details[iwire].direction;

			/* unidirectional wires going in the decreasing direction can have an outgoing edge
			   only from the top or right switch block sides, and an incoming edge only if they are
			   at the left or bottom sides (analogous for wires going in INC direction) */
			if (side == TOP || side == RIGHT){
				if (seg_direction == DEC_DIRECTION && is_dest){
					continue;
				}
				if (seg_direction == INC_DIRECTION && !is_dest){
					continue;
				}
			} else {
				VTR_ASSERT(side == LEFT || side == BOTTOM);
				if (seg_direction == DEC_DIRECTION && !is_dest){
					continue;
				}
				if (seg_direction == INC_DIRECTION && is_dest){
					continue;
				}
			}

			int wire_switchpoint = get_switchpoint_of_wire(grid, chan_type, chan_details[iwire], seg_coord, side);

			/* check if this wire belongs to one of the specified switchpoints; add it to our 'wires' vector if so */
			if ( find( points.begin(), points.end(), wire_switchpoint ) != points.end() ){
				wires->push_back( iwire );
			}
		}
	}
	sort(wires->begin(), wires->end());
}


/* Compute the wire(s) that the wire at (x, y, from_side, to_side) should connect to.
   sb_conns is updated with the result */
static void compute_wire_connections(int x_coord, int y_coord,
            enum e_side from_side, enum e_side to_side,
            const t_chan_details& chan_details_x, const t_chan_details& chan_details_y,
            t_switchblock_inf* sb,
			const DeviceGrid& grid,
			t_wire_type_sizes *wire_type_sizes,
            e_directionality directionality,
			t_sb_connection_map* sb_conns){

	int from_x, from_y;				/* index into source channel */
	int to_x, to_y;					/* index into destination channel */
	t_rr_type from_chan_type, to_chan_type;		/* the type of channel - i.e. CHANX or CHANY */
	from_x = from_y = to_x = to_y = UNDEFINED;

	SB_Side_Connection side_conn(from_side, to_side);		/* for indexing into this switchblock's permutation funcs */
	Switchblock_Lookup sb_conn(x_coord, y_coord, from_side, to_side);	/* for indexing into FPGA's switchblock map */

	/* can't connect a switchblock side to itself */
	if (from_side == to_side){
		return;
	}
	/* check that the permutation map has an entry for this side combination */
	if (sb->permutation_map.count(side_conn) == 0){
		/* the specified switchblock does not have any permutation funcs for this side1->side2 connection */
		return;
	}

	/* find the correct channel, and the coordinates to index into it for both the source and
	   destination channels. also return the channel type (ie chanx/chany) into which we are
	   indexing */
    /* details for source channel */
    const t_chan_details& from_chan_details = index_into_correct_chan(x_coord, y_coord, from_side, chan_details_x, chan_details_y,
				&from_x, &from_y, &from_chan_type);

    /* details for destination channel */
    const t_chan_details& to_chan_details = index_into_correct_chan(x_coord, y_coord, to_side, chan_details_x, chan_details_y,
				&to_x, &to_y, &to_chan_type);

	/* make sure from_x/y and to_x/y aren't out of bounds */
	if (coords_out_of_bounds(grid, to_x, to_y, to_chan_type) ||
	    coords_out_of_bounds(grid, from_x, from_y, from_chan_type)){
		return;
	}

	/* iterate over all the wire connections specified for this switch block */
	for (int iconn = 0; iconn < (int)sb->wireconns.size(); iconn++){
		/* pointer to a connection specification between wire types/subsegment_nums */
		t_wireconn_inf *wireconn_ptr = &sb->wireconns[iconn];

		/* compute the destination wire segments to which the source wire segment should connect based on the
		   current wireconn */
		compute_wireconn_connections(grid, directionality, from_chan_details, to_chan_details,
						sb_conn, from_x, from_y, to_x, to_y, from_chan_type, to_chan_type, wire_type_sizes,
						sb, wireconn_ptr, sb_conns);
	}

	return;
}


/* computes the destination wire segments that a source wire segment at the coordinate 'sb_conn' (in
   channel segment with coordinate from_x/from_y) should connect to based on the specified 'wireconn_ptr'.
   wireconn_ptr defines the source and destination sets of wire segments (based on wire segment type & switchpoint
   as defined at the top of this file), and the indices of wires to connect to are relative to these sets */
static void compute_wireconn_connections(const DeviceGrid& grid, e_directionality directionality,
		const t_chan_details& from_chan_details, const t_chan_details& to_chan_details, Switchblock_Lookup sb_conn,
		int from_x, int from_y, int to_x, int to_y, t_rr_type from_chan_type, t_rr_type to_chan_type,
		t_wire_type_sizes *wire_type_sizes, t_switchblock_inf *sb,
		t_wireconn_inf *wireconn_ptr, t_sb_connection_map *sb_conns){

	/* vectors that will contain indices of the wires belonging to the source/dest wire types/points */
	vector<int> potential_src_wires;
	vector<int> potential_dest_wires;

	get_switchpoint_wires(grid, from_chan_details[from_x][from_y], from_chan_type, from_x, from_y, sb_conn.from_side,
			wireconn_ptr->from_switchpoint_set, wire_type_sizes, false, &potential_src_wires);

	get_switchpoint_wires(grid, to_chan_details[to_x][to_y], to_chan_type, to_x, to_y, sb_conn.to_side,
			wireconn_ptr->to_switchpoint_set, wire_type_sizes, true, &potential_dest_wires);

    if (potential_src_wires.size() == 0 || potential_dest_wires.size() == 0) {
        //Can't make any connections between empty sets
        return;
    }

	/* At this point the vectors 'potential_src_wires' and 'potential_dest_wires' contain the indices of the from_type/from_point
	   and to_type/to_point wire segments. Now we compute the connections between them, according to permutation functions */
    size_t src_W = potential_src_wires.size();
    size_t dest_W = potential_dest_wires.size();

    //TODO: We could add another user-configurable parameter to control ordering of types in the sets.
    //      Currently we just iterate through them in order, but we could:
    //      * randomly shuffle, or
    //      * interleave (to ensure good diversity)

    //Determine how many connections to make
    size_t num_conns = 0;
    if (wireconn_ptr->num_conns_type == WireConnType::FROM) {
        num_conns = potential_src_wires.size();

    } else if (wireconn_ptr->num_conns_type == WireConnType::TO) {
        num_conns = potential_dest_wires.size();

    } else if (wireconn_ptr->num_conns_type == WireConnType::MIN) {
        num_conns = std::min(potential_src_wires.size(), potential_dest_wires.size());

    } else if (wireconn_ptr->num_conns_type == WireConnType::MAX) {
        num_conns = std::max(potential_src_wires.size(), potential_dest_wires.size());

    } else {
        vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "Unrecognized wireconn type");
    }


    for (size_t iconn = 0; iconn < num_conns; ++iconn) {

        //Select the from wire
        // We modulo by the src set size to wrap around if there are more connections that src wires
        int src_wire_ind = iconn % potential_src_wires.size(); //Index in src set
        int from_wire = potential_src_wires[src_wire_ind]; //Index in channel

        e_direction from_wire_direction = from_chan_details[from_x][from_y][from_wire].direction;
        if (from_wire_direction == INC_DIRECTION) {
            /* if this is a unidirectional wire headed in the increasing direction (relative to coordinate system)
               then switch block source side should be BOTTOM or LEFT */
            if (sb_conn.from_side == TOP || sb_conn.from_side == RIGHT){
                continue;
            }
            VTR_ASSERT(sb_conn.from_side == BOTTOM || sb_conn.from_side == LEFT);
        } else if (from_wire_direction == DEC_DIRECTION){
            /* a wire heading in the decreasing direction can only connect from the TOP or RIGHT sides of a switch block */
            if (sb_conn.from_side == BOTTOM || sb_conn.from_side == LEFT){
                continue;
            }
            VTR_ASSERT(sb_conn.from_side == TOP || sb_conn.from_side == RIGHT);
        } else {
            VTR_ASSERT(from_wire_direction == BI_DIRECTION);
        }

        //Evaluate permutation functions for the from_wire
        SB_Side_Connection side_conn(sb_conn.from_side, sb_conn.to_side);
        vector<string> &permutations_ref = sb->permutation_map[side_conn];
        for (int iperm = 0; iperm < (int)permutations_ref.size(); iperm++){
            /* Convert the symbolic permutation formula to a number */
            t_formula_data formula_data;
            formula_data.set_var_value("W", dest_W);
            formula_data.set_var_value("t", src_wire_ind);
            int raw_dest_wire_ind = get_sb_formula_raw_result(permutations_ref[iperm].c_str(), formula_data);
            int dest_wire_ind = adjust_formula_result(raw_dest_wire_ind, src_W, dest_W, iconn);

            if(dest_wire_ind < 0){
                vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "Got a negative wire from switch block formula %s", permutations_ref[iperm].c_str());
            }

            int to_wire = potential_dest_wires[dest_wire_ind]; //Index in channel

            /* create the struct containing information about the target wire segment which will be added to the
               sb connections map */
            t_switchblock_edge sb_edge;
            sb_edge.from_wire = from_wire;
            sb_edge.to_wire = to_wire;
            sb_edge.switch_ind = to_chan_details[to_x][to_y][to_wire].arch_wire_switch;

            /* and now, finally, add this switchblock connection to the switchblock connections map */
            (*sb_conns)[sb_conn].push_back(sb_edge);

            /* If bidir architecture, implement the reverse connection as well */
            if (BI_DIRECTIONAL == directionality) {
                t_switchblock_edge sb_reverse_edge = sb_edge;
                std::swap(sb_reverse_edge.from_wire, sb_reverse_edge.to_wire);
                //Since we are implementing the reverse connection we have swapped from and to.
                //
                //Coverity flags this (false positive), so annotatate so coverity ignores it:
                // coverity[swapped_arguments : Intentional]
                Switchblock_Lookup sb_conn_reverse(sb_conn.x_coord, sb_conn.y_coord, sb_conn.to_side, sb_conn.from_side);
                (*sb_conns)[sb_conn_reverse].push_back(sb_reverse_edge);
            }
        }
    }
}


/* Here we find the correct channel (x or y), and the coordinates to index into it based on the
   specified tile coordinates and the switchblock side. Also returns the type of channel
   that we are indexing into (ie, CHANX or CHANY */
static const t_chan_details& index_into_correct_chan(int tile_x, int tile_y, enum e_side side,
			const t_chan_details& chan_details_x, const t_chan_details& chan_details_y,
			int *set_x, int *set_y,
			t_rr_type* chan_type){

	*chan_type = CHANX;

	/* here we use the VPR convention that a tile 'owns' the channels directly to the right
	   and above it */
	switch (side){
		case TOP:
			/* this is y-channel belonging to tile above */
			*set_x = tile_x;
			*set_y = tile_y+1;
			*chan_type = CHANY;
			return chan_details_y;
			break;
		case RIGHT:
			/* this is x-channel belonging to tile to the right */
			*set_x = tile_x+1;
			*set_y = tile_y;
			*chan_type = CHANX;
			return chan_details_x;
			break;
		case BOTTOM:
			/* this is y-channel on the right of the tile */
			*set_x = tile_x;
			*set_y = tile_y;
			*chan_type = CHANY;
			return chan_details_y;
			break;
		case LEFT:
			/* this is x-channel on top of the tile */
			*set_x = tile_x;
			*set_y = tile_y;
			*chan_type = CHANX;
			return chan_details_x;
			break;
		default:
			vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "index_into_correct_chan: unknown side specified: %d\n", side);
			break;
	}
    VTR_ASSERT(false);
    return chan_details_x; //Unreachable
}


/* checks whether the specified coordinates are out of bounds */
static bool coords_out_of_bounds(const DeviceGrid& grid, int x_coord, int y_coord,
			e_rr_type chan_type){
	bool result = true;

	if (CHANX == chan_type){
		if (x_coord <=0 || x_coord >= int(grid.width())-1 ||	/* there is no x-channel at x=0 */
		    y_coord < 0 || y_coord >= int(grid.height())-1){
			result = true;
		} else {
			result = false;
		}
	} else if (CHANY == chan_type){
		if (x_coord < 0 || x_coord >= int(grid.width())-1 ||
		    y_coord <= 0 || y_coord >= int(grid.height())-1){	/* there is no y-channel at y=0 */
			result = true;
		} else {
			result = false;
		}

	} else {
		vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "coords_out_of_bounds(): illegal channel type %d\n", chan_type);
	}
	return result;
}

/* returns the subsegment number of the specified wire at seg_coord */
static int get_wire_subsegment_num(const DeviceGrid& grid, e_rr_type chan_type, const t_seg_details &wire_details, int seg_coord){

	/* We get wire subsegment number by comparing the wire's seg_coord to the seg_start of the wire.
	   The offset between seg_start (or seg_end) and seg_coord is the subsegment number

	   Cases:
	   seg starts at bottom but does not extend all the way to the top -- look at seg_end
	   seg starts > bottom and does not extend all the way to top -- look at seg_start
	   seg starts > bottom but terminates all the way at the top -- look at seg_start
	   seg starts at bottom and extends all the way to the top -- look at seg end
	*/

	int subsegment_num;
	int seg_start = wire_details.seg_start;
	int seg_end = wire_details.seg_end;
	e_direction direction = wire_details.direction;
	int wire_length = get_wire_segment_length(grid, chan_type, wire_details);
	int min_seg;

	/* determine the minimum and maximum values that the 'seg' coordinate
	   of a wire can take */
	min_seg = 1;

	if (seg_start != min_seg){
		subsegment_num = seg_coord - seg_start;
	} else {
		subsegment_num = (wire_length-1) - (seg_end - seg_coord);
	}

	/* if this wire is going in the decreasing direction, reverse the subsegment num */
	VTR_ASSERT(seg_end >= seg_start);
	if (direction == DEC_DIRECTION){
		subsegment_num = wire_length-1 - subsegment_num;
	}

	return subsegment_num;
}

/* returns wire segment length based on either:
   1) the wire length specified in the segment details variable for this wire (if this wire segment doesn't span entire FPGA)
   2) the seg_start and seg_end coordinates in the segment details for this wire (if this wire segment spans entire FPGA, as might happen for very long wires)

   Computing the wire segment length in this way help to classify short vs long wire segments according to switchpoint. */
int get_wire_segment_length(const DeviceGrid& grid, e_rr_type chan_type, const t_seg_details &wire_details){
	int wire_length;

	int min_seg = 1;
	int max_seg = grid.width() - 2; //-2 for no perim channels
	if (chan_type == CHANY){
		max_seg = grid.height() - 2; //-2 for no perim channels
	}

	int seg_start = wire_details.seg_start;
	int seg_end = wire_details.seg_end;

	if (seg_start == min_seg && seg_end == max_seg){
		wire_length = seg_end - seg_start + 1;
	} else {
		wire_length = wire_details.length;
	}

	return wire_length;
}


/* Returns the switchpoint of the wire specified by wire_details at a segment coordinate
   of seg_coord, and connection to the sb_side of the switchblock */
static int get_switchpoint_of_wire(const DeviceGrid& grid, e_rr_type chan_type,
		 const t_seg_details &wire_details, int seg_coord, e_side sb_side){

	/* this function calculates the switchpoint of a given wire by first calculating
	   the subsegmennt number of the specified wire. For instance, for a wire with L=4:

		switchpoint:	0-------1-------2-------3-------0
		subsegment_num:	    0       1       2       3

	   So knowing the wire's subsegment_num and which switchblock side it connects to is
	   enough to calculate the switchpoint

	*/

	int switchpoint;

	/* get the minimum and maximum segment coordinate which a wire in this channel type can take */
	int min_seg = 1;
	int max_seg = grid.width() - 2; //-2 for no perim channels
	if (chan_type == CHANY){
		max_seg = grid.height() - 2; //-2 for no perim channels
	}

	/* check whether the current seg_coord/sb_side coordinate specifies a perimeter switch block side at which all wire segments terminate/start.
	   in this case only segments with switchpoints = 0 can exist */
	bool perimeter_connection = false;
	if ((seg_coord == min_seg && (sb_side == RIGHT || sb_side == TOP)) ||
	    (seg_coord == max_seg && (sb_side == LEFT || sb_side == BOTTOM))){
		perimeter_connection = true;
	}

	if (perimeter_connection){
		switchpoint = 0;
	} else {
		int wire_length = get_wire_segment_length(grid, chan_type, wire_details);
		int subsegment_num = get_wire_subsegment_num(grid, chan_type, wire_details, seg_coord);

		e_direction direction = wire_details.direction;
		if (LEFT == sb_side || BOTTOM == sb_side){
			switchpoint = (subsegment_num + 1) % wire_length;
			if (direction == DEC_DIRECTION){
				switchpoint = subsegment_num;
			}
		} else {
			VTR_ASSERT(RIGHT == sb_side || TOP == sb_side);
			switchpoint = subsegment_num;
			if (direction == DEC_DIRECTION){
				switchpoint = (subsegment_num + 1) % wire_length;
			}
		}
	}

	return switchpoint;
}


/* adjusts the destination wire calculated from a permutation formula to account for negative indicies,
 * source wire set offset, and modulo by destination wire set size
 * */
static int adjust_formula_result(int dest_wire, int src_W, int dest_W, int connection_ind) {
	int result = dest_wire;

	if (dest_wire < 0) {
        //Adjust for negative indicies
		int mult = (-1*dest_wire) / dest_W + 1;
		result = dest_wire + mult*dest_W;
	}

    //Offset the destination track by a multiple of src_W to ensure all destination tracks are covered
    //
    // The permutation formula produce a 1-to-1 mapping from src track to dest track (i.e. each source
    // track is mapped to precisely one destination track). This is problematic if we are processing
    // a wireconn which goes through the source set multiple times (e.g. dest set larger than src set while
    // processing a WireConnType::TO), since the permutation formula will only generate src_W track indicies
    // (leaving some of the destination tracks unconnected). To ensure we get different destination tracks on
    // subsequent passes through the same source set, we offset the raw track by a multiple of src_W. Note the
    // use of integer division; src_mult will equal 0 on the first pass, 1 on the second etc.
    int src_mult = connection_ind / src_W;
    result += src_W * src_mult;

    //Final result must be modulo dest_W
	result = (result + dest_W) % dest_W;

	return result;
}