/* 
 * Prepacking: Group together technology-mapped netlist blocks before packing.  
 * This gives hints to the packer on what groups of blocks to keep together during packing.
 * Primary purpose:
 *    1) "Forced" packs (eg LUT+FF pair)
 *    2) Carry-chains
 * Duties: Find pack patterns in architecture, find pack patterns in netlist.
 *
 * Author: Jason Luu
 * March 12, 2012
 */

#include <cstdio>
#include <cstring>
#include <fstream>
#include <queue>
#include <stack>
#include <map>
using namespace std;

#include "vtr_util.h"
#include "vtr_assert.h"
#include "vtr_memory.h"

#include "vpr_types.h"
#include "vpr_error.h"

#include "read_xml_arch_file.h"
#include "globals.h"
#include "atom_netlist.h"
#include "hash.h"
#include "prepack.h"
#include "vpr_utils.h"
#include "echo_files.h"
#include "pack_patterns.h"

/*****************************************/
/*Local Function Declaration			 */
/*****************************************/
static int add_pattern_name_to_hash(t_hash **nhash,
		const char *pattern_name, int *ncount);
static void discover_pattern_names_in_pb_graph_node(
		t_pb_graph_node *pb_graph_node, t_hash **nhash,
		int *ncount, int depth);
static void forward_infer_pattern(t_pb_graph_pin *pb_graph_pin);
static void backward_infer_pattern(t_pb_graph_pin *pb_graph_pin);
static t_pack_patterns *alloc_and_init_pattern_list_from_hash(const int ncount,
		t_hash **nhash);
static t_pb_graph_edge * find_expansion_edge_of_pattern(const int pattern_index,
		const t_pb_graph_node *pb_graph_node);
static void forward_expand_pack_pattern_from_edge(
		const t_pb_graph_edge *expansion_edge,
		t_pack_patterns *list_of_packing_patterns,
		const int curr_pattern_index, int *L_num_blocks, const bool make_root_of_chain);
static void backward_expand_pack_pattern_from_edge(
		const t_pb_graph_edge* expansion_edge,
		t_pack_patterns *list_of_packing_patterns,
		const int curr_pattern_index, t_pb_graph_pin *destination_pin,
		t_pack_pattern_block *destination_block, int *L_num_blocks);
static int compare_pack_pattern(const t_pack_patterns *pattern_a, const t_pack_patterns *pattern_b);
static void free_pack_pattern(t_pack_pattern_block *pattern_block, t_pack_pattern_block **pattern_block_list);
static t_pack_molecule *try_create_molecule(
		t_pack_patterns *list_of_pack_patterns, 
        std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules,
        const int pack_pattern_index,
		AtomBlockId blk_id);
static bool try_expand_molecule(t_pack_molecule *molecule,
        const std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules,
		const AtomBlockId blk_id,
		const t_pack_pattern_block *current_pattern_block);
static void print_pack_molecules(const char *fname,
		const t_pack_patterns *list_of_pack_patterns, const int num_pack_patterns,
		const t_pack_molecule *list_of_molecules);
static void print_pack_pattern(FILE* fp, 
                               const t_pack_patterns& pack_pattern);
static void print_pack_pattern_block(FILE* fp, 
                               const t_pack_pattern_block* pack_pattern_block,
                               int depth);
static void print_pack_pattern_connection(FILE* fp, 
                               const t_pack_pattern_connections* conn,
                               int depth);
static t_pb_graph_node* get_expected_lowest_cost_primitive_for_atom_block(const AtomBlockId blk_id);
static t_pb_graph_node* get_expected_lowest_cost_primitive_for_atom_block_in_pb_graph_node(const AtomBlockId blk_id, t_pb_graph_node *curr_pb_graph_node, float *cost);
static AtomBlockId find_new_root_atom_for_chain(const AtomBlockId blk_id, const t_pack_patterns *list_of_pack_pattern, 
        const std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules);

static PackMolecules create_molecules(const std::vector<NetlistPatternMatch> netlist_matches, const AtomNetlist& netlist);
static PackMolecule create_molecule(const NetlistPatternMatch& match, const AtomNetlist& netlist);
static std::string name_molecule(const NetlistPatternMatch& match, PackMolecule& molecule);
static std::multimap<AtomBlockId,PackMoleculeId> build_atom_molecules_lookup(const vtr::vector<PackMoleculeId,PackMolecule>& molecules);
static bool verify_molecules_contain_all_atoms(const PackMolecules& molecules, const AtomNetlist& netlist);

static void write_pack_molecules(std::ostream& os, const PackMolecules& molecules);
static void write_pack_molecule(std::ostream& os, const PackMolecules& molecules, const PackMoleculeId molecule_id);

static void write_pack_pattern_matches(std::ostream& os, const std::vector<NetlistPatternMatch>& raw_netlist_matches, const AtomNetlist& netlist);
static void write_pack_pattern_match(std::ostream& os, const NetlistPatternMatch& match, const AtomNetlist& netlist);
/*****************************************/
/*Function Definitions					 */
/*****************************************/

/**
 * Find all packing patterns in architecture 
 * [0..num_packing_patterns-1]
 *
 * Limitations: Currently assumes that forced pack nets must be single-fanout
 * as this covers all the reasonable architectures we wanted.
 * More complicated structures should probably be handled either downstream 
 * (general packing) or upstream (in tech mapping).
 * If this limitation is too constraining, code is designed so that this limitation can be removed.
 */
t_pack_patterns *alloc_and_load_pack_patterns(int *num_packing_patterns) {
	int i, j, ncount, k;
	int L_num_blocks;
	t_hash **nhash;
	t_pack_patterns *list_of_packing_patterns;
	t_pb_graph_edge *expansion_edge;
    auto& device_ctx = g_vpr_ctx.device();

	/* alloc and initialize array of packing patterns based on architecture complex blocks */
	nhash = alloc_hash_table();
	ncount = 0;
	for (i = 0; i < device_ctx.num_block_types; i++) {
        //vtr::printf("Looking for pack patterns within %s\n", device_ctx.block_types[i].name);
		discover_pattern_names_in_pb_graph_node(
				device_ctx.block_types[i].pb_graph_head, nhash, &ncount, 1);
	}

	list_of_packing_patterns = alloc_and_init_pattern_list_from_hash(ncount, nhash);

	/* load packing patterns by traversing the edges to find edges belonging to pattern */
	for (i = 0; i < ncount; i++) {
		for (j = 0; j < device_ctx.num_block_types; j++) {
            //vtr::printf("Creating pack pattern %d for %s\n", i, device_ctx.block_types[j].name);
			expansion_edge = find_expansion_edge_of_pattern(i, device_ctx.block_types[j].pb_graph_head);
			if (expansion_edge == nullptr) {
				continue;
			}
			L_num_blocks = 0;
			list_of_packing_patterns[i].base_cost = 0;
			backward_expand_pack_pattern_from_edge(expansion_edge,
					list_of_packing_patterns, i, nullptr, nullptr, &L_num_blocks);
			list_of_packing_patterns[i].num_blocks = L_num_blocks;

			/* Default settings: A section of a netlist must match all blocks in a pack 
             * pattern before it can be made a molecule except for carry-chains.  
             * For carry-chains, since carry-chains are typically quite flexible in terms 
             * of size, it is optional whether or not an atom in a netlist matches any 
             * particular block inside the chain */
			list_of_packing_patterns[i].is_block_optional = (bool*) vtr::malloc(L_num_blocks * sizeof(bool));
			for(k = 0; k < L_num_blocks; k++) {
				list_of_packing_patterns[i].is_block_optional[k] = false;
				if(list_of_packing_patterns[i].is_chain && list_of_packing_patterns[i].root_block->block_id != k) {
					list_of_packing_patterns[i].is_block_optional[k] = true;
				}
			}
			break;
		}
	}

    //Sanity check, every pattern should have a root block
    for(i = 0; i < ncount; ++i) {
        if(list_of_packing_patterns[i].root_block == nullptr) {
            VPR_THROW(VPR_ERROR_ARCH, "Failed to find root block for pack pattern %s", list_of_packing_patterns[i].name);
        }
    }

	free_hash_table(nhash);

	*num_packing_patterns = ncount;


	return list_of_packing_patterns;
}

/**
 * Adds pack pattern name to hashtable of pack pattern names.
 */
static int add_pattern_name_to_hash(t_hash **nhash,
		const char *pattern_name, int *ncount) {
	t_hash *hash_value;

	hash_value = insert_in_hash_table(nhash, pattern_name, *ncount);
	if (hash_value->count == 1) {
		VTR_ASSERT(*ncount == hash_value->index);
		(*ncount)++;
	}
	return hash_value->index;
}

/**
 * Locate all pattern names 
 * Side-effect: set all pb_graph_node temp_scratch_pad field to NULL
 *				For cases where a pattern inference is "obvious", mark it as obvious.
 */
static void discover_pattern_names_in_pb_graph_node(
		t_pb_graph_node *pb_graph_node, t_hash **nhash,
		int *ncount, int depth) {
	int i, j, k, m;
	int index;
	bool hasPattern;
	/* Iterate over all edges to discover if an edge in current physical block belongs to a pattern 
	 If edge does, then record the name of the pattern in a hash table
	 */

	if (pb_graph_node == nullptr) {
		return;
	}

	pb_graph_node->temp_scratch_pad = nullptr;

	for (i = 0; i < pb_graph_node->num_input_ports; i++) {
		for (j = 0; j < pb_graph_node->num_input_pins[i]; j++) {
			hasPattern = false;
			for (k = 0; k < pb_graph_node->input_pins[i][j].num_output_edges; k++) {
				for (m = 0; m < pb_graph_node->input_pins[i][j].output_edges[k]->num_pack_patterns; m++) {
					hasPattern = true;
					index = add_pattern_name_to_hash(nhash,
									pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_names[m],
									ncount);
					if (pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices == nullptr) {
						pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices = (int*)
								vtr::malloc( pb_graph_node->input_pins[i][j].output_edges[k]->num_pack_patterns * sizeof(int));
					}
					pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices[m] = index;
                    //vtr::printf("%sFound pack pattern '%s' (index %d) to input pin %s[%d].%s[%d]\n", 
                                //vtr::indent(depth, "  ").c_str(),
                                //pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_names[m],
                                //index,
                                //pb_graph_node->pb_type->name,
                                //pb_graph_node->placement_index,
                                //pb_graph_node->input_pins[i][j].port->name,
                                //pb_graph_node->input_pins[i][j].pin_number
                                //);
				}								
			}
			if (hasPattern == true) {
				forward_infer_pattern(&pb_graph_node->input_pins[i][j]);
				backward_infer_pattern(&pb_graph_node->input_pins[i][j]);
			}
		}
	}

	for (i = 0; i < pb_graph_node->num_output_ports; i++) {
		for (j = 0; j < pb_graph_node->num_output_pins[i]; j++) {
			hasPattern = false;
			for (k = 0; k < pb_graph_node->output_pins[i][j].num_output_edges; k++) {
				for (m = 0; m < pb_graph_node->output_pins[i][j].output_edges[k]->num_pack_patterns; m++) {
					hasPattern = true;
					index = add_pattern_name_to_hash(nhash,
									pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_names[m],
									ncount);
					if (pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices == nullptr) {
						pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices = (int*)
								vtr::malloc( pb_graph_node->output_pins[i][j].output_edges[k]->num_pack_patterns * sizeof(int));
					}
					pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices[m] = index;
                    //vtr::printf("%sFound pack pattern '%s' (index %d) from output pin %s[%d].%s[%d]\n", 
                                //vtr::indent(depth, "  ").c_str(),
                                //pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_names[m],
                                //index,
                                //pb_graph_node->pb_type->name,
                                //pb_graph_node->placement_index,
                                //pb_graph_node->output_pins[i][j].port->name,
                                //pb_graph_node->output_pins[i][j].pin_number
                                //);
				}
			}
			if (hasPattern == true) {
				forward_infer_pattern(&pb_graph_node->output_pins[i][j]);
				backward_infer_pattern(&pb_graph_node->output_pins[i][j]);
			}
		}
	}

	for (i = 0; i < pb_graph_node->num_clock_ports; i++) {
		for (j = 0; j < pb_graph_node->num_clock_pins[i]; j++) {
			hasPattern = false;
			for (k = 0; k < pb_graph_node->clock_pins[i][j].num_output_edges; k++) {
				for (m = 0; m < pb_graph_node->clock_pins[i][j].output_edges[k]->num_pack_patterns; m++) {
					hasPattern = true;
					index = add_pattern_name_to_hash(nhash,
									pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_names[m],
									ncount);
					if (pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices == nullptr) {
						pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices = (int*)
								vtr::malloc( pb_graph_node->clock_pins[i][j].output_edges[k]->num_pack_patterns * sizeof(int));
					}
					pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices[m] = index;
                    //vtr::printf("%sFound pack pattern '%s' (index %d) to clock pin %s[%d].%s[%d]\n", 
                                //vtr::indent(depth, "  ").c_str(),
                                //pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_names[m],
                                //index,
                                //pb_graph_node->pb_type->name,
                                //pb_graph_node->placement_index,
                                //pb_graph_node->clock_pins[i][j].port->name,
                                //pb_graph_node->clock_pins[i][j].pin_number
                                //);
				}
			}
			if (hasPattern == true) {
				forward_infer_pattern(&pb_graph_node->clock_pins[i][j]);
				backward_infer_pattern(&pb_graph_node->clock_pins[i][j]);
			}
		}
	}

	for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
		for (j = 0; j < pb_graph_node->pb_type->modes[i].num_pb_type_children; j++) {
			for (k = 0; k < pb_graph_node->pb_type->modes[i].pb_type_children[j].num_pb; k++) {
				discover_pattern_names_in_pb_graph_node(
						&pb_graph_node->child_pb_graph_nodes[i][j][k], nhash,
						ncount, depth + 1);
			}
		}
	}
}

/**
 * In obvious cases where a pattern edge has only one path to go, set that path to be inferred 
 */
static void forward_infer_pattern(t_pb_graph_pin *pb_graph_pin) {
	if (pb_graph_pin->num_output_edges == 1 && pb_graph_pin->output_edges[0]->num_pack_patterns == 0 && pb_graph_pin->output_edges[0]->infer_pattern == false) {
		pb_graph_pin->output_edges[0]->infer_pattern = true;
		if (pb_graph_pin->output_edges[0]->num_output_pins == 1) {
			forward_infer_pattern(pb_graph_pin->output_edges[0]->output_pins[0]);
		}
	}
}
static void backward_infer_pattern(t_pb_graph_pin *pb_graph_pin) {
	if (pb_graph_pin->num_input_edges == 1 && pb_graph_pin->input_edges[0]->num_pack_patterns == 0 && pb_graph_pin->input_edges[0]->infer_pattern == false) {
		pb_graph_pin->input_edges[0]->infer_pattern = true;
		if (pb_graph_pin->input_edges[0]->num_input_pins == 1) {
			backward_infer_pattern(pb_graph_pin->input_edges[0]->input_pins[0]);
		}
	}
}

/**
 * Allocates memory for models and loads the name of the packing pattern 
 * so that it can be identified and loaded with more complete information later
 */
static t_pack_patterns *alloc_and_init_pattern_list_from_hash(const int ncount,
		t_hash **nhash) {
	t_pack_patterns *nlist;
	t_hash_iterator hash_iter;
	t_hash *curr_pattern;

	nlist = (t_pack_patterns*)vtr::calloc(ncount, sizeof(t_pack_patterns));

	hash_iter = start_hash_table_iterator();
	curr_pattern = get_next_hash(nhash, &hash_iter);
	while (curr_pattern != nullptr) {
		VTR_ASSERT(nlist[curr_pattern->index].name == nullptr);
		nlist[curr_pattern->index].name = vtr::strdup(curr_pattern->name);
		nlist[curr_pattern->index].root_block = nullptr;
		nlist[curr_pattern->index].is_chain = false;
		nlist[curr_pattern->index].index = curr_pattern->index;
        //vtr::printf("Allocating Pack Pattern %d: %s\n", curr_pattern->index, curr_pattern->name);

		curr_pattern = get_next_hash(nhash, &hash_iter);
	}
	return nlist;
}

void free_list_of_pack_patterns(t_pack_patterns *list_of_pack_patterns, const int num_packing_patterns) {
	int i, j, num_pack_pattern_blocks;
	t_pack_pattern_block **pattern_block_list;
	if (list_of_pack_patterns != nullptr) {
		for (i = 0; i < num_packing_patterns; i++) {
			num_pack_pattern_blocks = list_of_pack_patterns[i].num_blocks;
			pattern_block_list = (t_pack_pattern_block **)vtr::calloc(num_pack_pattern_blocks, sizeof(t_pack_pattern_block *));
			free(list_of_pack_patterns[i].name);
			free(list_of_pack_patterns[i].is_block_optional);
			free_pack_pattern(list_of_pack_patterns[i].root_block, pattern_block_list);
			for (j = 0; j < num_pack_pattern_blocks; j++) {
				free(pattern_block_list[j]);
			}
			free(pattern_block_list);
		}
		free(list_of_pack_patterns);
	}
}

/**
 * Locate first edge that belongs to pattern index 
 */
static t_pb_graph_edge * find_expansion_edge_of_pattern(const int pattern_index,
		const t_pb_graph_node *pb_graph_node) {
	int i, j, k, m;
	t_pb_graph_edge * edge;
	/* Iterate over all edges to discover if an edge in current physical block belongs to a pattern 
	 If edge does, then return that edge
	 */

	if (pb_graph_node == nullptr) {
		return nullptr;
	}

	for (i = 0; i < pb_graph_node->num_input_ports; i++) {
		for (j = 0; j < pb_graph_node->num_input_pins[i]; j++) {
			for (k = 0; k < pb_graph_node->input_pins[i][j].num_output_edges; k++) {
				for (m = 0; m < pb_graph_node->input_pins[i][j].output_edges[k]->num_pack_patterns; m++) {
					if (pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices[m] == pattern_index) {
                        //vtr::printf("Found expansion edge on input pin %s.%s[%d] edge %d pattern %d\n",
                                    //pb_graph_node->pb_type->name,
                                    //pb_graph_node->input_pins[i][j].port->name,
                                    //pb_graph_node->input_pins[i][j].pin_number,
                                    //k,
                                    //pattern_index);
						return pb_graph_node->input_pins[i][j].output_edges[k];
					}
				}
			}
		}
	}

	for (i = 0; i < pb_graph_node->num_output_ports; i++) {
		for (j = 0; j < pb_graph_node->num_output_pins[i]; j++) {
			for (k = 0; k < pb_graph_node->output_pins[i][j].num_output_edges; k++) {
				for (m = 0; m < pb_graph_node->output_pins[i][j].output_edges[k]->num_pack_patterns; m++) {
					if (pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices[m] == pattern_index) {
                        //vtr::printf("Found expansion edge on output pin %s.%s[%d] edge %d pattern %d\n",
                                    //pb_graph_node->pb_type->name,
                                    //pb_graph_node->output_pins[i][j].port->name,
                                    //pb_graph_node->output_pins[i][j].pin_number,
                                    //k,
                                    //pattern_index);
						return pb_graph_node->output_pins[i][j].output_edges[k];
					}
				}
			}
		}
	}

	for (i = 0; i < pb_graph_node->num_clock_ports; i++) {
		for (j = 0; j < pb_graph_node->num_clock_pins[i]; j++) {
			for (k = 0; k < pb_graph_node->clock_pins[i][j].num_output_edges; k++) {
				for (m = 0; m < pb_graph_node->clock_pins[i][j].output_edges[k]->num_pack_patterns; m++) {
					if (pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices[m] == pattern_index) {
                        //vtr::printf("Found expansion edge on clock pin %s.%s[%d] edge %d pattern %d\n",
                                    //pb_graph_node->pb_type->name,
                                    //pb_graph_node->clock_pins[i][j].port->name,
                                    //pb_graph_node->clock_pins[i][j].pin_number,
                                    //k,
                                    //pattern_index);
						return pb_graph_node->clock_pins[i][j].output_edges[k];
					}
				}
			}
		}
	}

	for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
		for (j = 0; j < pb_graph_node->pb_type->modes[i].num_pb_type_children; j++) {
			for (k = 0; k < pb_graph_node->pb_type->modes[i].pb_type_children[j].num_pb; k++) {
				edge = find_expansion_edge_of_pattern(pattern_index, &pb_graph_node->child_pb_graph_nodes[i][j][k]);
				if (edge != nullptr) {
					return edge;
				}
			}
		}
	}
	return nullptr;
}

/** 
 * Find if receiver of edge is in the same pattern, if yes, add to pattern
 *  Convention: Connections are made on backward expansion only (to make future 
 *              multi-fanout support easier) so this function will not update connections
 */
static void forward_expand_pack_pattern_from_edge(
		const t_pb_graph_edge* expansion_edge,
		t_pack_patterns *list_of_packing_patterns,
		const int curr_pattern_index, int *L_num_blocks, bool make_root_of_chain) {
	int i, j, k;
	int iport, ipin, iedge;
	bool found; /* Error checking, ensure only one fan-out for each pattern net */
	t_pack_pattern_block *destination_block = nullptr;
	t_pb_graph_node *destination_pb_graph_node = nullptr;

	found = expansion_edge->infer_pattern;
	for (i = 0;	!found && i < expansion_edge->num_pack_patterns; i++) {
		if (expansion_edge->pack_pattern_indices[i] == curr_pattern_index) {
			found = true;
		}
	}
	if (!found) {
		return;
	}

    //vtr::printf("Forward expanding pattern %d edge (%s)\n",
                //curr_pattern_index,
                //describe_pb_graph_edge_hierarchy(expansion_edge).c_str());
	found = false;
	for (i = 0; i < expansion_edge->num_output_pins; i++) {
		if (expansion_edge->output_pins[i]->parent_node->pb_type->num_modes == 0) {
			destination_pb_graph_node = expansion_edge->output_pins[i]->parent_node;
			VTR_ASSERT(found == false);
			/* Check assumption that each forced net has only one fan-out */
			/* This is the destination node */
			found = true;

			/* If this pb_graph_node is part not of the current pattern index, put it in and expand all its edges */
			if (destination_pb_graph_node->temp_scratch_pad == nullptr
					|| ((t_pack_pattern_block*) destination_pb_graph_node->temp_scratch_pad)->pattern_index != curr_pattern_index) {
				destination_block = (t_pack_pattern_block*)vtr::calloc(1, sizeof(t_pack_pattern_block));
				list_of_packing_patterns[curr_pattern_index].base_cost += compute_primitive_base_cost(destination_pb_graph_node);
				destination_block->block_id = *L_num_blocks;
				(*L_num_blocks)++;
				destination_pb_graph_node->temp_scratch_pad =
						(void *) destination_block;
				destination_block->pattern_index = curr_pattern_index;
				destination_block->pb_type = destination_pb_graph_node->pb_type;
				for (iport = 0; iport < destination_pb_graph_node->num_input_ports; iport++) {
					for (ipin = 0; ipin < destination_pb_graph_node->num_input_pins[iport]; ipin++) {
						for (iedge = 0; iedge < destination_pb_graph_node->input_pins[iport][ipin].num_input_edges; iedge++) {
							backward_expand_pack_pattern_from_edge(
									destination_pb_graph_node->input_pins[iport][ipin].input_edges[iedge],
									list_of_packing_patterns,
									curr_pattern_index,
									&destination_pb_graph_node->input_pins[iport][ipin],
									destination_block, L_num_blocks);
						}
					}
				}
				for (iport = 0; iport < destination_pb_graph_node->num_output_ports; iport++) {
					for (ipin = 0; ipin < destination_pb_graph_node->num_output_pins[iport]; ipin++) {
						for (iedge = 0; iedge < destination_pb_graph_node->output_pins[iport][ipin].num_output_edges; iedge++) {
							forward_expand_pack_pattern_from_edge(
									destination_pb_graph_node->output_pins[iport][ipin].output_edges[iedge],
									list_of_packing_patterns,
									curr_pattern_index, L_num_blocks, false);
						}
					}
				}
				for (iport = 0; iport < destination_pb_graph_node->num_clock_ports; iport++) {
					for (ipin = 0; ipin < destination_pb_graph_node->num_clock_pins[iport]; ipin++) {
						for (iedge = 0; iedge < destination_pb_graph_node->clock_pins[iport][ipin].num_input_edges; iedge++) {
							backward_expand_pack_pattern_from_edge(
									destination_pb_graph_node->clock_pins[iport][ipin].input_edges[iedge],
									list_of_packing_patterns,
									curr_pattern_index,
									&destination_pb_graph_node->clock_pins[iport][ipin],
									destination_block, L_num_blocks);
						}
					}
				}
			} 
			if (((t_pack_pattern_block*) destination_pb_graph_node->temp_scratch_pad)->pattern_index
							== curr_pattern_index) {
				if(make_root_of_chain == true) {
					list_of_packing_patterns[curr_pattern_index].chain_root_pin = expansion_edge->output_pins[i];
					list_of_packing_patterns[curr_pattern_index].root_block = destination_block;
				}
			}
		} else {
			for (j = 0; j < expansion_edge->output_pins[i]->num_output_edges; j++) {
				if (expansion_edge->output_pins[i]->output_edges[j]->infer_pattern == true) {
					forward_expand_pack_pattern_from_edge(
							expansion_edge->output_pins[i]->output_edges[j],
							list_of_packing_patterns, curr_pattern_index,
							L_num_blocks, make_root_of_chain);
				} else {
					for (k = 0; k < expansion_edge->output_pins[i]->output_edges[j]->num_pack_patterns; k++) {
						if (expansion_edge->output_pins[i]->output_edges[j]->pack_pattern_indices[k] == curr_pattern_index) {
							if (found == true) {
								/* Check assumption that each forced net has only one fan-out */
								vpr_throw(VPR_ERROR_PACK, __FILE__, __LINE__, 
										"Invalid packing pattern defined.  Multi-fanout nets not supported when specifying pack patterns.\n"
										"Problem on %s[%d].%s[%d] for pattern %s\n",
										expansion_edge->output_pins[i]->parent_node->pb_type->name,
										expansion_edge->output_pins[i]->parent_node->placement_index,
										expansion_edge->output_pins[i]->port->name,
										expansion_edge->output_pins[i]->pin_number,
                                        list_of_packing_patterns[curr_pattern_index].name);
							}
							found = true;
							forward_expand_pack_pattern_from_edge(
									expansion_edge->output_pins[i]->output_edges[j],
									list_of_packing_patterns,
									curr_pattern_index, L_num_blocks, make_root_of_chain);
						}
					}
				}
			}
		}
	}

}

/** 
 * Find if driver of edge is in the same pattern, if yes, add to pattern
 *  Convention: Connections are made on backward expansion only (to make future multi-
 *               fanout support easier) so this function must update both source and 
 *               destination blocks
 */
static void backward_expand_pack_pattern_from_edge(
		const t_pb_graph_edge* expansion_edge,
		t_pack_patterns *list_of_packing_patterns,
		const int curr_pattern_index, t_pb_graph_pin *destination_pin,
		t_pack_pattern_block *destination_block, int *L_num_blocks) {
	int i, j, k;
	int iport, ipin, iedge;
	bool found; /* Error checking, ensure only one fan-out for each pattern net */
	t_pack_pattern_block *source_block = nullptr;
	t_pb_graph_node *source_pb_graph_node = nullptr;
	t_pack_pattern_connections *pack_pattern_connection = nullptr;

	found = expansion_edge->infer_pattern;
	for (i = 0;	!found && i < expansion_edge->num_pack_patterns; i++) {
		if (expansion_edge->pack_pattern_indices[i] == curr_pattern_index) {
			found = true;
		}
	}
	if (!found) {
		return;
	}

    //vtr::printf("Backward expanding pattern %d edge (%s)\n",
                //curr_pattern_index,
                //describe_pb_graph_edge_hierarchy(expansion_edge).c_str());
	found = false;
	for (i = 0; i < expansion_edge->num_input_pins; i++) {
		if (expansion_edge->input_pins[i]->parent_node->pb_type->num_modes == 0) {
			source_pb_graph_node = expansion_edge->input_pins[i]->parent_node;
			VTR_ASSERT(found == false);
			/* Check assumption that each forced net has only one fan-out */
			/* This is the source node for destination */
			found = true;

            //vtr::printf("\tBackward expanding pattern %d edge input pin '%s' (no modes)\n",
                        //curr_pattern_index,
                        //describe_pb_graph_pin_hierarchy(expansion_edge->input_pins[i]).c_str());

			/* If this pb_graph_node is part not of the current pattern index, put it in and expand all its edges */
			source_block = (t_pack_pattern_block*) source_pb_graph_node->temp_scratch_pad;
			if (source_block == nullptr
                || source_block->pattern_index != curr_pattern_index) {

				source_block = (t_pack_pattern_block *)vtr::calloc(1, sizeof(t_pack_pattern_block));
				source_block->block_id = *L_num_blocks;
				(*L_num_blocks)++;
				list_of_packing_patterns[curr_pattern_index].base_cost += compute_primitive_base_cost(source_pb_graph_node);
				source_pb_graph_node->temp_scratch_pad = (void *) source_block;
				source_block->pattern_index = curr_pattern_index;
				source_block->pb_type = source_pb_graph_node->pb_type;

                //vtr::printf("\tAdding pattern %d source block %s[%d]\n",
                            //curr_pattern_index,
                            //source_pb_graph_node->pb_type->name,
                            //source_pb_graph_node->placement_index);

				if (list_of_packing_patterns[curr_pattern_index].root_block == nullptr) {
					list_of_packing_patterns[curr_pattern_index].root_block = source_block;
                    //vtr::printf("\t\tAdded as pattern %d root block\n", curr_pattern_index);
				}

				for (iport = 0; iport < source_pb_graph_node->num_input_ports; iport++) {
					for (ipin = 0; ipin < source_pb_graph_node->num_input_pins[iport]; ipin++) {
						for (iedge = 0; iedge < source_pb_graph_node->input_pins[iport][ipin].num_input_edges; iedge++) {
							backward_expand_pack_pattern_from_edge(
									source_pb_graph_node->input_pins[iport][ipin].input_edges[iedge],
									list_of_packing_patterns,
									curr_pattern_index,
									&source_pb_graph_node->input_pins[iport][ipin],
									source_block, L_num_blocks);
						}
					}
				}
				for (iport = 0; iport < source_pb_graph_node->num_output_ports; iport++) {
					for (ipin = 0; ipin < source_pb_graph_node->num_output_pins[iport]; ipin++) {
						for (iedge = 0; iedge < source_pb_graph_node->output_pins[iport][ipin].num_output_edges; iedge++) {
							forward_expand_pack_pattern_from_edge(
									source_pb_graph_node->output_pins[iport][ipin].output_edges[iedge],
									list_of_packing_patterns,
									curr_pattern_index, L_num_blocks, false);
						}
					}
				}
				for (iport = 0; iport < source_pb_graph_node->num_clock_ports; iport++) {
					for (ipin = 0; ipin < source_pb_graph_node->num_clock_pins[iport]; ipin++) {
						for (iedge = 0; iedge < source_pb_graph_node->clock_pins[iport][ipin].num_input_edges; iedge++) {
							backward_expand_pack_pattern_from_edge(
									source_pb_graph_node->clock_pins[iport][ipin].input_edges[iedge],
									list_of_packing_patterns,
									curr_pattern_index,
									&source_pb_graph_node->clock_pins[iport][ipin],
									source_block, L_num_blocks);
						}
					}
				}
			}
			if (destination_pin != nullptr) {
				VTR_ASSERT( ((t_pack_pattern_block*)source_pb_graph_node->temp_scratch_pad)->pattern_index == curr_pattern_index);

				source_block = (t_pack_pattern_block*) source_pb_graph_node->temp_scratch_pad;

                //Create the connection
				pack_pattern_connection = (t_pack_pattern_connections *)vtr::calloc(1, sizeof(t_pack_pattern_connections));
				pack_pattern_connection->from_block = source_block;
				pack_pattern_connection->from_pin = expansion_edge->input_pins[i];
				pack_pattern_connection->to_block = destination_block;
				pack_pattern_connection->to_pin = destination_pin;

                //Add the new connection to the source block
				pack_pattern_connection->next = source_block->connections;
				source_block->connections = pack_pattern_connection;

                //Create a duplicate connection to store with the sink block
				pack_pattern_connection = (t_pack_pattern_connections *)vtr::calloc(1, sizeof(t_pack_pattern_connections));
				pack_pattern_connection->from_block = source_block;
				pack_pattern_connection->from_pin = expansion_edge->input_pins[i];
				pack_pattern_connection->to_block = destination_block;
				pack_pattern_connection->to_pin = destination_pin;

                //Add the duplicate connection to the destination block
				pack_pattern_connection->next = destination_block->connections;
				destination_block->connections = pack_pattern_connection;

                //vtr::printf("\tAdding connection %s -> %s\n",
                            //describe_pb_graph_pin_hierarchy(pack_pattern_connection->from_pin).c_str(),
                            //describe_pb_graph_pin_hierarchy(pack_pattern_connection->to_pin).c_str());

				if (source_block == destination_block) {
					vpr_throw(VPR_ERROR_PACK, __FILE__, __LINE__, 
							"Invalid packing pattern defined. Source and destination block are the same (%s).\n",
							source_block->pb_type->name);
				}
			}
		} else {
			if(expansion_edge->input_pins[i]->num_input_edges == 0) {
				if(expansion_edge->input_pins[i]->parent_node->pb_type->parent_mode == nullptr) {
					/* This pack pattern extends to CLB input pin, thus it extends across multiple logic blocks, treat as a chain */
					list_of_packing_patterns[curr_pattern_index].is_chain = true;
					forward_expand_pack_pattern_from_edge(
									expansion_edge,
									list_of_packing_patterns,
									curr_pattern_index, L_num_blocks, true);
				}
			} else {
				for (j = 0; j < expansion_edge->input_pins[i]->num_input_edges; j++) {
					if (expansion_edge->input_pins[i]->input_edges[j]->infer_pattern == true) {
						backward_expand_pack_pattern_from_edge(
								expansion_edge->input_pins[i]->input_edges[j],
								list_of_packing_patterns, curr_pattern_index,
								destination_pin, destination_block, L_num_blocks);
					} else {
						for (k = 0; k < expansion_edge->input_pins[i]->input_edges[j]->num_pack_patterns; k++) {
							if (expansion_edge->input_pins[i]->input_edges[j]->pack_pattern_indices[k] == curr_pattern_index) {
								VTR_ASSERT(found == false);
								/* Check assumption that each forced net has only one fan-out */
								found = true;
								backward_expand_pack_pattern_from_edge(
										expansion_edge->input_pins[i]->input_edges[j],
										list_of_packing_patterns,
										curr_pattern_index, destination_pin,
										destination_block, L_num_blocks);
							}
						}
					}
				}
			}
		}
	}
}

/**
 * Pre-pack atoms in netlist to molecules
 * 1.  Single atoms are by definition a molecule.
 * 2.  Forced pack molecules are groupings of atoms that matches a t_pack_pattern definition.
 * 3.  Chained molecules are molecules that follow a carry-chain style pattern,
 *     ie. a single linear chain that can be split across multiple complex blocks
 */
t_pack_molecule *alloc_and_load_pack_molecules(
		t_pack_patterns *list_of_pack_patterns,
        std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules,
        std::unordered_map<AtomBlockId,t_pb_graph_node*>& expected_lowest_cost_pb_gnode,
		const int num_packing_patterns) {
	int i, j, best_pattern;
	t_pack_molecule *list_of_molecules_head;
	t_pack_molecule *cur_molecule;
	bool *is_used;
    auto& atom_ctx = g_vpr_ctx.atom();

	is_used = (bool*)vtr::calloc(num_packing_patterns, sizeof(bool));

	cur_molecule = list_of_molecules_head = nullptr;

	/* Find forced pack patterns
	 * Simplifying assumptions: Each atom can map to at most one molecule, 
     *                          use first-fit mapping based on priority of pattern
	 * TODO: Need to investigate better mapping strategies than first-fit 
     */
	for (i = 0; i < num_packing_patterns; i++) {
		best_pattern = 0;
		for(j = 1; j < num_packing_patterns; j++) {
			if(is_used[best_pattern]) {
				best_pattern = j;
			} else if (is_used[j] == false && compare_pack_pattern(&list_of_pack_patterns[j], &list_of_pack_patterns[best_pattern]) == 1) {
				best_pattern = j;
			}
		}
		VTR_ASSERT(is_used[best_pattern] == false);
		is_used[best_pattern] = true;

        auto blocks = atom_ctx.nlist.blocks();
        for(auto blk_iter = blocks.begin(); blk_iter != blocks.end(); ++blk_iter) {
            auto blk_id = *blk_iter;

            cur_molecule = try_create_molecule(list_of_pack_patterns, atom_molecules, best_pattern, blk_id);
            if (cur_molecule != nullptr) {
                cur_molecule->next = list_of_molecules_head;
                /* In the event of multiple molecules with the same atom block pattern, 
                 * bias to use the molecule with less costly physical resources first */
                /* TODO: Need to normalize magical number 100 */
                cur_molecule->base_gain = cur_molecule->num_blocks - (cur_molecule->pack_pattern->base_cost / 100);
                list_of_molecules_head = cur_molecule;

                //Note: atom_molecules is an (ordered) multimap so the last molecule 
                //      inserted for a given blk_id will be the last valid element 
                //      in the equal_range
                auto rng = atom_molecules.equal_range(blk_id); //The range of molecules matching this block
                bool range_empty = (rng.first == rng.second);
                bool cur_was_last_inserted = false;
                if (!range_empty) {
                    auto last_valid_iter = --rng.second; //Iterator to last element (only valid if range is not empty)
                    cur_was_last_inserted = (last_valid_iter->second == cur_molecule);
                }
                if(range_empty || !cur_was_last_inserted) {
                    /* molecule did not cover current atom (possibly because molecule created is
                     * part of a long chain that extends past multiple logic blocks), try again */
                    --blk_iter;
                }
            }
		}
	}
	free(is_used);

	/* List all atom blocks as a molecule for blocks that do not belong to any molecules.
	 This allows the packer to be consistent as it now packs molecules only instead of atoms and molecules

	 If a block belongs to a molecule, then carrying the single atoms around can make the packing problem
	 more difficult because now it needs to consider splitting molecules.
	 */
    for(auto blk_id : atom_ctx.nlist.blocks()) {

        expected_lowest_cost_pb_gnode[blk_id] = get_expected_lowest_cost_primitive_for_atom_block(blk_id);

        auto rng = atom_molecules.equal_range(blk_id);
        bool rng_empty = (rng.first == rng.second);
		if (rng_empty) {
			cur_molecule = new t_pack_molecule;
			cur_molecule->valid = true;
			cur_molecule->type = MOLECULE_SINGLE_ATOM;
			cur_molecule->num_blocks = 1;
			cur_molecule->root = 0;
			cur_molecule->num_ext_inputs = atom_ctx.nlist.block_input_pins(blk_id).size();
			cur_molecule->pack_pattern = nullptr;

            cur_molecule->atom_block_ids = {blk_id};

			cur_molecule->next = list_of_molecules_head;
			cur_molecule->base_gain = 1;
			list_of_molecules_head = cur_molecule;

            atom_molecules.insert({blk_id, cur_molecule});
		}
	}

	if (getEchoEnabled() && isEchoFileEnabled(E_ECHO_PRE_PACKING_MOLECULES_AND_PATTERNS)) {
		print_pack_molecules(getEchoFileName(E_ECHO_PRE_PACKING_MOLECULES_AND_PATTERNS),
				list_of_pack_patterns, num_packing_patterns,
				list_of_molecules_head);
	}

	return list_of_molecules_head;
}


static void free_pack_pattern(t_pack_pattern_block *pattern_block, t_pack_pattern_block **pattern_block_list) {
	t_pack_pattern_connections *connection, *next;
	if (pattern_block == nullptr || pattern_block->block_id == OPEN) {
		/* already traversed, return */
		return; 
	}
	pattern_block_list[pattern_block->block_id] = pattern_block;
	pattern_block->block_id = OPEN;
	connection = pattern_block->connections;
	while (connection) {
		free_pack_pattern(connection->from_block, pattern_block_list);
		free_pack_pattern(connection->to_block, pattern_block_list);
		next = connection->next;
		free(connection);
		connection = next;
	}
}

/**
 * Given a pattern and an atom block to serve as the root block, determine if 
 * the candidate atom block serving as the root node matches the pattern.
 * If yes, return the molecule with this atom block as the root, if not, return NULL
 *
 * Limitations: Currently assumes that forced pack nets must be single-fanout as 
 *              this covers all the reasonable architectures we wanted. More complicated 
 *              structures should probably be handled either downstream (general packing) 
 *              or upstream (in tech mapping).
 *              If this limitation is too constraining, code is designed so that this limitation can be removed
 *
 * Side Effect: If successful, link atom to molecule
 */
static t_pack_molecule *try_create_molecule(
		t_pack_patterns *list_of_pack_patterns, 
        std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules,
        const int pack_pattern_index,
		AtomBlockId blk_id) {
	int i;
	t_pack_molecule *molecule;

	bool failed = false;

	{
		molecule = new t_pack_molecule;
		molecule->valid = true;
		molecule->type = MOLECULE_FORCED_PACK;
		molecule->pack_pattern = &list_of_pack_patterns[pack_pattern_index];
		if (molecule->pack_pattern == nullptr) {failed = true; goto end_prolog;}

        molecule->atom_block_ids = std::vector<AtomBlockId>(molecule->pack_pattern->num_blocks); //Initializes invalid

		molecule->num_blocks = list_of_pack_patterns[pack_pattern_index].num_blocks;
		if (molecule->num_blocks == 0) {failed = true; goto end_prolog;}

		if (list_of_pack_patterns[pack_pattern_index].root_block == nullptr) {failed = true; goto end_prolog;}
		molecule->root = list_of_pack_patterns[pack_pattern_index].root_block->block_id;
		molecule->num_ext_inputs = 0;

		if(list_of_pack_patterns[pack_pattern_index].is_chain == true) {
			/* A chain pattern extends beyond a single logic block so we must find 
             * the blk_id that matches with the portion of a chain for this particular logic block */
			blk_id = find_new_root_atom_for_chain(blk_id, &list_of_pack_patterns[pack_pattern_index], atom_molecules);
		}
	}

	end_prolog:

	if (!failed && blk_id && try_expand_molecule(molecule, atom_molecules, blk_id,
			molecule->pack_pattern->root_block) == true) {
		/* Success! commit module */
		for (i = 0; i < molecule->pack_pattern->num_blocks; i++) {
            auto blk_id2 = molecule->atom_block_ids[i];
			if(!blk_id2) {
				VTR_ASSERT(list_of_pack_patterns[pack_pattern_index].is_block_optional[i] == true);
				continue;
			}			

            atom_molecules.insert({blk_id2, molecule});
		}
	} else {
		failed = true;
	}

	if (failed == true) {
		/* Does not match pattern, free molecule */
		delete molecule;
		molecule = nullptr;
	}
	return molecule;
}

/**
 * Determine if atom block can match with the pattern to form a molecule
 * return true if it matches, return false otherwise
 */
static bool try_expand_molecule(t_pack_molecule *molecule,
        const std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules,
		const AtomBlockId blk_id,
		const t_pack_pattern_block *current_pattern_block) {
	int ipin;
	bool success;
	bool is_optional;
	bool *is_block_optional;
	t_pack_pattern_connections *cur_pack_pattern_connection;

    auto& atom_ctx = g_vpr_ctx.atom();

	is_block_optional = molecule->pack_pattern->is_block_optional;
	is_optional = is_block_optional[current_pattern_block->block_id];

    /* If the block in the pattern has already been visited, then there is no need to revisit it */
	if (molecule->atom_block_ids[current_pattern_block->block_id]) {
		if (molecule->atom_block_ids[current_pattern_block->block_id] != blk_id) {
			/* Mismatch between the visited block and the current block implies 
             * that the current netlist structure does not match the expected pattern, 
             * return whether or not this matters */
			return is_optional;
		} else {
			molecule->num_ext_inputs--; /* This block is revisited, implies net is entirely internal to molecule, reduce count */
			return true;
		}
	}

	/* This node has never been visited */
	/* Simplifying assumption: An atom can only map to one molecule */
    auto rng = atom_molecules.equal_range(blk_id);
    bool rng_empty = rng.first == rng.second;
	if(!rng_empty) {
		/* This block is already in a molecule, return whether or not this matters */
		return is_optional;
	}

	if (primitive_type_feasible(blk_id, current_pattern_block->pb_type)) {

		success = true;
		/* If the primitive types match, store it, expand it and explore neighbouring nodes */


        /* store that this node has been visited */
		molecule->atom_block_ids[current_pattern_block->block_id] = blk_id;

		molecule->num_ext_inputs += atom_ctx.nlist.block_input_pins(blk_id).size();
		
		cur_pack_pattern_connection = current_pattern_block->connections;
		while (cur_pack_pattern_connection != nullptr && success == true) {
			if (cur_pack_pattern_connection->from_block == current_pattern_block) {
				/* find net corresponding to pattern */
                AtomPortId port_id = atom_ctx.nlist.find_atom_port(blk_id, cur_pack_pattern_connection->from_pin->port->model_port);
                if(!port_id) {
                    //No matching port, we may be at the end
                    success = is_block_optional[cur_pack_pattern_connection->to_block->block_id];
                } else {
                    ipin = cur_pack_pattern_connection->from_pin->pin_number;
                    AtomNetId net_id = atom_ctx.nlist.port_net(port_id, ipin);

                    /* Check if net is valid */
                    if (!net_id || atom_ctx.nlist.net_sinks(net_id).size() != 1) { /* One fanout assumption */
                        success = is_block_optional[cur_pack_pattern_connection->to_block->block_id];
                    } else {
                        auto net_sinks = atom_ctx.nlist.net_sinks(net_id);
                        VTR_ASSERT(net_sinks.size() == 1);

                        auto sink_pin_id = *net_sinks.begin();
                        auto sink_blk_id = atom_ctx.nlist.pin_block(sink_pin_id);

                        success = try_expand_molecule(molecule, atom_molecules, sink_blk_id,
                                    cur_pack_pattern_connection->to_block);
                    }
                }
			} else {
				VTR_ASSERT(cur_pack_pattern_connection->to_block == current_pattern_block);
				/* find net corresponding to pattern */

                auto port_id = atom_ctx.nlist.find_atom_port(blk_id, cur_pack_pattern_connection->to_pin->port->model_port);
                VTR_ASSERT(port_id);
				ipin = cur_pack_pattern_connection->to_pin->pin_number;

                AtomNetId net_id;
				if (cur_pack_pattern_connection->to_pin->port->model_port->is_clock) {
                    VTR_ASSERT(ipin == 1); //TODO: support multi-clock primitives
					net_id = atom_ctx.nlist.port_net(port_id, ipin);
				} else {
					net_id = atom_ctx.nlist.port_net(port_id, ipin);
				}
				/* Check if net is valid */
				if (!net_id || atom_ctx.nlist.net_sinks(net_id).size() != 1) { /* One fanout assumption */
					success = is_block_optional[cur_pack_pattern_connection->from_block->block_id];
				} else {
                    auto driver_blk_id = atom_ctx.nlist.net_driver_block(net_id);
					success = try_expand_molecule(molecule, atom_molecules, driver_blk_id,
                                cur_pack_pattern_connection->from_block);
				}
			}
			cur_pack_pattern_connection = cur_pack_pattern_connection->next;
		}
	} else {
		success = is_optional;
	}

	return success;
}

static void print_pack_molecules(const char *fname,
		const t_pack_patterns *list_of_pack_patterns, const int num_pack_patterns,
		const t_pack_molecule *list_of_molecules) {
	int i;
	FILE *fp;
	const t_pack_molecule *list_of_molecules_current;
    auto& atom_ctx = g_vpr_ctx.atom();

	fp = std::fopen(fname, "w");
	fprintf(fp, "# of pack patterns %d\n", num_pack_patterns);
		
	for (i = 0; i < num_pack_patterns; i++) {
        print_pack_pattern(fp, list_of_pack_patterns[i]);
        fprintf(fp, "\n");
	}

	list_of_molecules_current = list_of_molecules;
	while (list_of_molecules_current != nullptr) {
		if (list_of_molecules_current->type == MOLECULE_SINGLE_ATOM) {
			fprintf(fp, "\nmolecule type: atom\n");
			fprintf(fp, "\tpattern index %d: atom block %s\n", i,
					atom_ctx.nlist.block_name(list_of_molecules_current->atom_block_ids[0]).c_str());
		} else if (list_of_molecules_current->type == MOLECULE_FORCED_PACK) {
			fprintf(fp, "\nmolecule type: %s\n",
					list_of_molecules_current->pack_pattern->name);
			for (i = 0; i < list_of_molecules_current->pack_pattern->num_blocks;
					i++) {
				if(!list_of_molecules_current->atom_block_ids[i]) {
					fprintf(fp, "\tpattern index %d: empty \n",	i);
				} else {
					fprintf(fp, "\tpattern index %d: atom block %s",
						i,
						atom_ctx.nlist.block_name(list_of_molecules_current->atom_block_ids[i]).c_str());
					if(list_of_molecules_current->pack_pattern->root_block->block_id == i) {
						fprintf(fp, " root node\n");
					} else {
						fprintf(fp, "\n");
					}
				}
			}
		} else {
			VTR_ASSERT(0);
		}
		list_of_molecules_current = list_of_molecules_current->next;
	}

	fclose(fp);
}

static void print_pack_pattern(FILE* fp, 
                               const t_pack_patterns& pack_pattern) {

    VTR_ASSERT(pack_pattern.root_block);
    fprintf(fp, "pack_pattern_index: %d block_count: %d name: '%s' root: '%s' is_chain: %d",
            pack_pattern.index,
            pack_pattern.num_blocks,
            pack_pattern.name,
            pack_pattern.root_block->pb_type->name,
            pack_pattern.is_chain);
    if (pack_pattern.chain_root_pin) {
        fprintf(fp, " chain_root_pin: '%s'",
                describe_pb_graph_pin_hierarchy(pack_pattern.chain_root_pin).c_str());
    } else {
        fprintf(fp, " chain_root_pin: none");
    }
    fprintf(fp, "\n");

    print_pack_pattern_block(fp, pack_pattern.root_block, 1);
}

static void print_pack_pattern_block(FILE* fp, 
                               const t_pack_pattern_block* pack_pattern_block,
                               int depth) {
    fprintf(fp, "%sblock: %s",
            vtr::indent(depth, "  ").c_str(),
            describe_pb_type_hierarchy(pack_pattern_block->pb_type).c_str());
    if (!pack_pattern_block->connections) {
        fprintf(fp, " (no outgoing pack patterns)");
    }
    fprintf(fp, "\n");

    for (t_pack_pattern_connections* conn = pack_pattern_block->connections; conn != nullptr; conn = conn->next) {
        if (conn->from_block != pack_pattern_block) continue; //Only print connections where current is source
        print_pack_pattern_connection(fp, conn, depth + 1);
        print_pack_pattern_block(fp, conn->to_block, depth + 2);
    }
}

static void print_pack_pattern_connection(FILE* fp, 
                               const t_pack_pattern_connections* conn,
                               int depth) {
    fprintf(fp, "%sconn: %s -> %s\n",
            vtr::indent(depth, "  ").c_str(),
            describe_pb_graph_pin_hierarchy(conn->from_pin).c_str(),
            describe_pb_graph_pin_hierarchy(conn->to_pin).c_str());
}


/* Search through all primitives and return the lowest cost primitive that fits this atom block */
static t_pb_graph_node* get_expected_lowest_cost_primitive_for_atom_block(const AtomBlockId blk_id) {
	int i;
	float cost, best_cost;
	t_pb_graph_node *current, *best;
    auto& device_ctx = g_vpr_ctx.device();

	best_cost = UNDEFINED;
	best = nullptr;
	current = nullptr;
	for(i = 0; i < device_ctx.num_block_types; i++) {
		cost = UNDEFINED;
		current = get_expected_lowest_cost_primitive_for_atom_block_in_pb_graph_node(blk_id, device_ctx.block_types[i].pb_graph_head, &cost);
		if(cost != UNDEFINED) {
			if(best_cost == UNDEFINED || best_cost > cost) {
				best_cost = cost;
				best = current;
			}
		}
	}

    if(!best) {
        auto& atom_ctx = g_vpr_ctx.atom();
        VPR_THROW(VPR_ERROR_PACK, "Failed to find any location to pack primitive of type '%s' in architecture",
                  atom_ctx.nlist.block_model(blk_id)->name);
    }

	return best;
}

static t_pb_graph_node *get_expected_lowest_cost_primitive_for_atom_block_in_pb_graph_node(const AtomBlockId blk_id, t_pb_graph_node *curr_pb_graph_node, float *cost) {
	t_pb_graph_node *best, *cur;
	float cur_cost, best_cost;
	int i, j;

	best = nullptr;
	best_cost = UNDEFINED;
	if(curr_pb_graph_node == nullptr) {
		return nullptr;
	}

	if(curr_pb_graph_node->pb_type->blif_model != nullptr) {
		if(primitive_type_feasible(blk_id, curr_pb_graph_node->pb_type)) {
			cur_cost = compute_primitive_base_cost(curr_pb_graph_node);
			if(best_cost == UNDEFINED || best_cost > cur_cost) {
				best_cost = cur_cost;
				best = curr_pb_graph_node;
			}
		}
	} else {
		for(i = 0; i < curr_pb_graph_node->pb_type->num_modes; i++) {
			for(j = 0; j < curr_pb_graph_node->pb_type->modes[i].num_pb_type_children; j++) {
				*cost = UNDEFINED;
				cur = get_expected_lowest_cost_primitive_for_atom_block_in_pb_graph_node(blk_id, &curr_pb_graph_node->child_pb_graph_nodes[i][j][0], cost);
				if(cur != nullptr) {
					if(best == nullptr || best_cost > *cost) {
						best = cur;
						best_cost = *cost;
					}
				}
			}
		}
	}

	*cost = best_cost;
	return best;
}


/* Determine which of two pack pattern should take priority */
static int compare_pack_pattern(const t_pack_patterns *pattern_a, const t_pack_patterns *pattern_b) {
	float base_gain_a, base_gain_b, diff;

	/* Bigger patterns should take higher priority than smaller patterns because they are harder to fit */
	if (pattern_a->num_blocks > pattern_b->num_blocks) {
		return 1;
	} else if (pattern_a->num_blocks < pattern_b->num_blocks) {
		return -1;
	}

	base_gain_a = pattern_a->base_cost;
	base_gain_b = pattern_b->base_cost;
	diff = base_gain_a - base_gain_b;

	/* Less costly patterns should be used before more costly patterns */
	if (diff < 0) {
		return 1;
	}
	if (diff > 0) {
		return -1;
	}
	return 0;
}

/* A chain can extend across multiple atom blocks.  Must segment the chain to fit in an atom 
 * block by identifying the actual atom that forms the root of the new chain.
 * Returns AtomBlockId::INVALID() if this block_index doesn't match up with any chain
 *
 * Assumes that the root of a chain is the primitive that starts the chain or is driven from outside the logic block
 * block_index: index of current atom
 * list_of_pack_pattern: ptr to current chain pattern
 */
static AtomBlockId find_new_root_atom_for_chain(const AtomBlockId blk_id, const t_pack_patterns *list_of_pack_pattern,
        const std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules) {
    AtomBlockId new_root_blk_id;
	t_pb_graph_pin *root_ipin;
	t_pb_graph_node *root_pb_graph_node;
	t_model_ports *model_port;
	
    auto& atom_ctx = g_vpr_ctx.atom();

	VTR_ASSERT(list_of_pack_pattern->is_chain == true);
	root_ipin = list_of_pack_pattern->chain_root_pin;
	root_pb_graph_node = root_ipin->parent_node;

	if(primitive_type_feasible(blk_id, root_pb_graph_node->pb_type) == false) {
		return AtomBlockId::INVALID();
	}

	/* Assign driver furthest up the chain that matches the root node and is unassigned to a molecule as the root */
	model_port = root_ipin->port->model_port;

    AtomPortId port_id = atom_ctx.nlist.find_atom_port(blk_id, model_port);
    if(!port_id) {
        //There is no port with the chain connection on this block, it must be the furthest
        //up the chain, so return it as root
        return blk_id;
    }

	AtomNetId driving_net_id = atom_ctx.nlist.port_net(port_id, root_ipin->pin_number);
	if(!driving_net_id) {
        //There is no net associated with the chain connection on this block, it must be the furthest
        //up the chain, so return it as root
		return blk_id;
	}

    auto driver_pin_id = atom_ctx.nlist.net_driver(driving_net_id);
	AtomBlockId driver_blk_id = atom_ctx.nlist.pin_block(driver_pin_id);

    auto rng = atom_molecules.equal_range(driver_blk_id);
    bool rng_empty = (rng.first == rng.second);
	if(!rng_empty) {
		/* Driver is used/invalid, so current block is the furthest up the chain, return it */
		return blk_id;
	}

	new_root_blk_id = find_new_root_atom_for_chain(driver_blk_id, list_of_pack_pattern, atom_molecules);
	if(!new_root_blk_id) {
		return blk_id;
	} else {
		return new_root_blk_id;
	}
}

PackMolecules prepack(const DeviceContext& device_ctx, const AtomContext& atom_ctx) {

    //Identify the architecural pack patterns
    auto arch_pack_patterns = identify_arch_pack_patterns(device_ctx);

    //Debug
    for (auto& arch_pattern : arch_pack_patterns) {
        std::ofstream ofs("arch_pack_pattern." + arch_pattern.name + ".echo");
        write_arch_pack_pattern_dot(ofs, arch_pattern);
    }

    //Convert them to netlist patterns
    auto netlist_pack_patterns = abstract_arch_pack_patterns(arch_pack_patterns);

    //Add the default atom pattern to match any blocks not covered by
    //an architectural pattern
    netlist_pack_patterns.push_back(create_atom_default_pack_pattern());

    //Debug
    for (auto& netlist_pattern : netlist_pack_patterns) {
        std::ofstream ofs("netlist_pack_pattern." + netlist_pattern.name + ".echo");
        write_netlist_pack_pattern_dot(ofs, netlist_pattern);
    }

    //Find the matching patterns in the netlist
    std::vector<NetlistPatternMatch> raw_netlist_matches;
    for (auto& netlist_pattern : netlist_pack_patterns) {
        auto netlist_pattern_matches = collect_pattern_matches_in_netlist(netlist_pattern, atom_ctx.nlist);

        raw_netlist_matches.insert(raw_netlist_matches.end(), netlist_pattern_matches.begin(), netlist_pattern_matches.end());
    }

    { //Debug
        std::ofstream ofs_matches("pack_pattern_matches.echo");
        write_pack_pattern_matches(ofs_matches, raw_netlist_matches, atom_ctx.nlist);
    }

    //Some matches may be redundant or invalid (e.g. match only external blocks), so remove them
    auto final_netlist_matches = filter_netlist_pattern_matches(raw_netlist_matches);

    //Convert the final matches to molecules for use during packing
    PackMolecules molecules = create_molecules(final_netlist_matches, atom_ctx.nlist);

    { //Debug
        std::ofstream ofs_molecules("pack_molecules.echo");
        write_pack_molecules(ofs_molecules, molecules);
    }

    verify_molecules_contain_all_atoms(molecules, atom_ctx.nlist);

    return molecules;
}

static PackMolecules create_molecules(const std::vector<NetlistPatternMatch> netlist_matches, const AtomNetlist& netlist) {
    PackMolecules molecules;

    for (auto& match : netlist_matches) {
        //Reserve Id
        PackMoleculeId molecule_id = PackMoleculeId(molecules.pack_molecules.size());
        molecules.pack_molecule_ids.push_back(molecule_id);

        //Build molecule
        molecules.pack_molecules.push_back(create_molecule(match, netlist));
    }

    //Reverse look-up from atom to molecule
    molecules.atom_molecules = build_atom_molecules_lookup(molecules.pack_molecules);

    return molecules;
}

static PackMolecule create_molecule(const NetlistPatternMatch& match, const AtomNetlist& netlist) {
    PackMolecule molecule;

    std::map<AtomBlockId,MoleculeBlockId> atom_to_molecule_block;

    for (auto atom_blk : match.internal_blocks) {
        MoleculeBlockId id = molecule.create_block(PackMolecule::BlockType::INTERNAL, atom_blk);
        atom_to_molecule_block[atom_blk] = id;
    }

    for (auto atom_blk : match.external_blocks) {
        MoleculeBlockId id = molecule.create_block(PackMolecule::BlockType::EXTERNAL, atom_blk);
        atom_to_molecule_block[atom_blk] = id;
    }

    std::map<AtomPinId,MoleculePinId> atom_to_molecule_pin;
    std::map<MoleculePinId,MoleculeEdgeId> molecule_driver_pin_to_edge;
    for (const auto& netlist_edge : match.netlist_edges) {

        //Find or create driver pin
        AtomPinId atom_driver_pin = netlist_edge.from_pin;
        VTR_ASSERT(netlist.pin_type(atom_driver_pin) == PinType::DRIVER);
        AtomBlockId atom_driver_block = netlist.pin_block(atom_driver_pin);

        VTR_ASSERT(atom_to_molecule_block.count(atom_driver_block));
        MoleculeBlockId molecule_driver_block = atom_to_molecule_block[atom_driver_block];

        MoleculePinId molecule_driver_pin;
        if (!atom_to_molecule_pin.count(atom_driver_pin)) {
            //Create
            molecule_driver_pin = molecule.create_pin(molecule_driver_block, atom_driver_pin, false);
            atom_to_molecule_pin[atom_driver_pin] = molecule_driver_pin;
        } else {
            //Existing
            molecule_driver_pin = atom_to_molecule_pin[atom_driver_pin];
        }

        //Find or create sink pin
        AtomPinId atom_sink_pin = netlist_edge.to_pin;
        VTR_ASSERT(netlist.pin_type(atom_sink_pin) == PinType::SINK);
        AtomBlockId atom_sink_block = netlist.pin_block(atom_sink_pin);

        VTR_ASSERT(atom_to_molecule_block.count(atom_sink_block));
        MoleculeBlockId molecule_sink_block = atom_to_molecule_block[atom_sink_block];

        MoleculePinId molecule_sink_pin;
        if (!atom_to_molecule_pin.count(atom_sink_pin)) {
            //Create
            molecule_sink_pin = molecule.create_pin(molecule_sink_block, atom_sink_pin, true);
            atom_to_molecule_pin[atom_sink_pin] = molecule_sink_pin;
        } else {
            //Existing
            molecule_sink_pin = atom_to_molecule_pin[atom_sink_pin];
        }

        //Find or create the edge
        MoleculeEdgeId molecule_edge;
        if (!molecule_driver_pin_to_edge.count(molecule_driver_pin)) {
            //Create
            molecule_edge = molecule.create_edge(molecule_driver_pin);
            molecule_driver_pin_to_edge[molecule_driver_pin] = molecule_edge;
        } else {
            //Existing
            molecule_edge = molecule_driver_pin_to_edge[molecule_driver_pin];
        }

        //Record the edge between source/sink
        molecule.add_edge_sink(molecule_edge, molecule_sink_pin);
    }

    //Record the root
    for (auto& block : molecule.blocks()) {
        if (molecule.block_input_pins(block).empty()) {
            VTR_ASSERT(!molecule.root_block());
            molecule.set_root_block(block);
        }
    }

    //Determine the gain
    //
    // In the event of multiple molecules with the same atom block pattern, 
    // bias to use the molecule with less costly physical resources first
    // TODO: Need to normalize magical number 100
    float base_gain = molecule.blocks().size() - (match.base_cost / 100);
    molecule.set_base_gain(base_gain);

    molecule.set_name(name_molecule(match, molecule));

    return molecule;
}

static std::string name_molecule(const NetlistPatternMatch& match, PackMolecule& molecule) {
    //Find first non-external block
    std::string internal_block_name;
    for (auto molecule_blk : molecule.blocks()) {
        auto atom_name = g_vpr_ctx.atom().nlist.block_name(molecule.block_atom(molecule_blk));

        internal_block_name = atom_name; 

        if (molecule.block_type(molecule_blk) == PackMolecule::BlockType::INTERNAL) {
            break; //Preferr to name based on internal molecule, otherwise use external
        }
    }
    VTR_ASSERT(!internal_block_name.empty());

    if (match.pattern_name == ATOM_DEFAULT_PACK_PATTERN_NAME) {
        //Just the atom name
        return internal_block_name;
    } else {
        //First atom name prefixed with pattern name
        return match.pattern_name + ":" + internal_block_name;
    }
}

static std::multimap<AtomBlockId,PackMoleculeId> build_atom_molecules_lookup(const vtr::vector<PackMoleculeId,PackMolecule>& molecules) {
    std::multimap<AtomBlockId,PackMoleculeId> atom_molecules;

    size_t idx = 0;
    for (const auto& molecule : molecules) {
        PackMoleculeId molecule_id(idx);

        for (MoleculeBlockId molecule_blk_id : molecule.blocks()) {
            if (molecule.block_type(molecule_blk_id) != PackMolecule::BlockType::INTERNAL) continue;
            AtomBlockId atom_blk_id = molecule.block_atom(molecule_blk_id);
            
            atom_molecules.insert({atom_blk_id, molecule_id});
        }
        ++idx;
    }
    return atom_molecules;
}

static bool verify_molecules_contain_all_atoms(const PackMolecules& molecules, const AtomNetlist& netlist) {
    //Record atom blocks
    std::set<AtomBlockId> netlist_blocks(netlist.blocks().begin(), netlist.blocks().end());

    //Record molecule blocks
    std::set<AtomBlockId> molecule_blocks;
    for (const PackMolecule& molecule : molecules.pack_molecules) {
        for (auto& block_id : molecule.blocks()) {
            molecule_blocks.insert(molecule.block_atom(block_id));
        }
    }

    std::set<AtomBlockId> in_molecules_but_not_netlist;
    std::set_difference(molecule_blocks.begin(), molecule_blocks.end(),
                        netlist_blocks.begin(), netlist_blocks.end(),
                        std::inserter(in_molecules_but_not_netlist, in_molecules_but_not_netlist.begin()));

    std::set<AtomBlockId> in_netlist_but_not_molecules;
    std::set_difference(netlist_blocks.begin(), netlist_blocks.end(),
                        molecule_blocks.begin(), molecule_blocks.end(),
                        std::inserter(in_netlist_but_not_molecules, in_netlist_but_not_molecules.begin()));

    if (!in_molecules_but_not_netlist.empty() || !in_netlist_but_not_molecules.empty()) {
        std::string msg = vtr::string_fmt("Inconsistent blocks in netlist and molecules\n");


        if (!in_molecules_but_not_netlist.empty()) {
            msg += vtr::string_fmt("  The following blocks are in molecules but missing from netlist:\n");
            for (auto blk : in_molecules_but_not_netlist) {
                msg += vtr::string_fmt("    %s\n", netlist.block_name(blk).c_str());
            }
        }

        if (!in_netlist_but_not_molecules.empty()) {
            msg += vtr::string_fmt("  The following blocks are in netlist but missing from molecules:\n");
            for (auto blk : in_netlist_but_not_molecules) {
                msg += vtr::string_fmt("    %s\n", netlist.block_name(blk).c_str());
            }
        }

        VPR_THROW(VPR_ERROR_PACK, msg.c_str());
    }

    VTR_ASSERT(in_molecules_but_not_netlist.empty() && in_netlist_but_not_molecules.empty());
    return true;
}

static void write_pack_molecules(std::ostream& os, const PackMolecules& molecules) {
    os << "#Pack Molecules\n";
    for (size_t i = 0; i < molecules.pack_molecules.size(); ++i) {
        write_pack_molecule(os, molecules, PackMoleculeId(i));
    }
    os << "\n";

    auto& netlist = g_vpr_ctx.atom().nlist;
    os << "#Atom Molecules\n";
    for (auto atom : netlist.blocks()) {
        os << "Atom(" << size_t(atom) << "): '" << netlist.block_name(atom) << "'\n";
        auto range = molecules.atom_molecules.equal_range(atom);
        for (auto kv : vtr::make_range(range.first, range.second)) {
            PackMoleculeId molecule_id = kv.second;
            os << "\tMolecule(" << size_t(molecule_id) << ")\n";
        }
    }

}

static void write_pack_molecule(std::ostream& os, const PackMolecules& molecules, const PackMoleculeId molecule_id) {
    auto& netlist = g_vpr_ctx.atom().nlist;

    os << "Molecule(" << size_t(molecule_id) << "):\n";
    auto& molecule = molecules.pack_molecules[molecule_id];
    for (auto blk : molecule.blocks()) {
        AtomBlockId atom = molecule.block_atom(blk);
        
        os << "\t";
        os << "Block(" << size_t(blk) << ") ";
        if (molecule.block_type(blk) == PackMolecule::BlockType::INTERNAL) {
            os << "Internal";
        } else {
            VTR_ASSERT(molecule.block_type(blk) == PackMolecule::BlockType::EXTERNAL);
            os << "External";
        }
        os << ": '" << netlist.block_name(atom) << "'";
        os << " (" << netlist.block_model(atom)->name << ")\n";
    }

    for (auto edge : molecule.edges()) {
        MoleculePinId driver_pin = molecule.edge_driver(edge);
        AtomPinId atom_driver_pin = molecule.pin_atom(driver_pin);
        AtomNetId atom_net = netlist.pin_net(atom_driver_pin);
        os << "\tEdge(" << size_t(edge) << "): Net '" << netlist.net_name(atom_net) << "'\n";
        for (MoleculePinId sink_pin : molecule.edge_sinks(edge)) {
            AtomPinId atom_sink_pin = molecule.pin_atom(sink_pin);
            VTR_ASSERT(netlist.pin_net(atom_sink_pin) == atom_net);

            os << "\t\t" << netlist.pin_name(atom_driver_pin) << " -> " << netlist.pin_name(atom_sink_pin) << ")\n";
        }
    }
    os << "\tBase Gain: " << molecule.base_gain() << "\n";
    os << "\tRoot: Block(" << size_t(molecule.root_block()) << ")\n";
    os << "\tName: " << molecule.name() << "\n";
}

static void write_pack_pattern_matches(std::ostream& os, const std::vector<NetlistPatternMatch>& raw_netlist_matches, const AtomNetlist& netlist) {
    os << "#Netlist pattern matches\n";
    size_t i = 0;
    for (auto& match : raw_netlist_matches) {
        os <<"Match: " << i << "\n";
        write_pack_pattern_match(os, match, netlist);
        os << "\n";

        ++i;
    }
}

static void write_pack_pattern_match(std::ostream& os, const NetlistPatternMatch& match, const AtomNetlist& netlist) {
    os << "\tPattern: " << match.pattern_name << "\n";
    for (auto blk : match.internal_blocks) {
        os << "\tInternal Block: " << netlist.block_name(blk) << "\n";
    }
    for (auto blk : match.external_blocks) {
        os << "\tExternal Block: " << netlist.block_name(blk) << "\n";
    }
    os << "\tBase Cost: " << match.base_cost << "\n";
}