vpr/SRC/pack/cluster.c

Go to the documentation of this file.

/**
 * @file
 *
 * Main clustering algorithm
 * Author(s): Vaughn Betz (first revision - VPack), Alexander Marquardt (second revision - T-VPack), Jason Luu (third revision - AAPack)
 * June 8, 2011
 */

#include <stdio.h>
#include <assert.h>
#include <string.h>

#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "cluster.h"
#include "heapsort.h"
#include "output_clustering.h"
#include "output_blif.h"
#include "SetupGrid.h"
#include "read_xml_arch_file.h"
#include "cluster_legality.h"
#include "path_delay2.h"
#include "path_delay.h"

#define AAPACK_MAX_FEASIBLE_BLOCK_ARRAY_SIZE 30      /**< This value is used to determine the max size of the priority queue for candidates that pass the early filter legality test but not the more detailed routing test */

#define SCALE_NUM_PATHS 1e-2     /**< this value is used as a multiplier to assign a    
                                  * slightly higher criticality value to nets that    
                                  * affect a large number of critical paths versus    
                                  * nets that do not have such a broad effect.        
                                  * Note that this multiplier is intentionally very    
                                  * small compared to the total criticality because   
                                  * we want to make sure that vpack_net criticality is      
                                  * primarily determined by slacks, with this acting  
                                  * only as a tie-breaker between otherwise equal nets
                                  */
#define SCALE_DISTANCE_VAL 1e-4  /**< this value is used as a multiplier to assign a    
                                  * slightly higher criticality value to nets that    
                                  * are otherwise equal but one is  farther           
                                  * from sources (the farther one being made slightly 
                                  * more critical)                                    
                                  */


enum e_gain_update {GAIN, NO_GAIN};
enum e_feasibility {FEASIBLE, INFEASIBLE};
enum e_gain_type {HILL_CLIMBING, NOT_HILL_CLIMBING};
enum e_removal_policy {REMOVE_CLUSTERED, LEAVE_CLUSTERED};
enum e_net_relation_to_clustered_block {INPUT, OUTPUT};

/** Linked list structure.  Stores one integer (iblk). */
struct s_ilink {int iblk; struct s_ilink *next;};


/** 1/MARKED_FRAC is the fraction of nets or blocks that must be
 * marked in order for the brute force (go through the whole    
 * data structure linearly) gain update etc. code to be used.   
 * This is done for speed only; make MARKED_FRAC whatever       
 * number speeds the code up most.                              
 */
#define MARKED_FRAC 2   

/** Keeps a linked list of the unclustered blocks to speed up looking for 
 * unclustered blocks with a certain number of *external* inputs.        
 * [0..lut_size].  Unclustered_list_head[i] points to the head of the   
 * list of blocks with i inputs to be hooked up via external interconnect. 
 */
static struct s_ilink *unclustered_list_head;
int unclustered_list_head_size;
static struct s_ilink *memory_pool; /**< Declared here so I can free easily.*/

/** Does the logical_block that drives the output of this vpack_net also appear as a   
 * receiver (input) pin of the vpack_net?  [0..num_logical_nets-1].  If so, then by how much? This is used     
 * in the gain routines to avoid double counting the connections from   
 * the current cluster to other blocks (hence yielding better           
 * clusterings).  The only time a logical_block should connect to the same vpack_net  
 * twice is when one connection is an output and the other is an input, 
 * so this should take care of all multiple connections.                
 */
static int *net_output_feeds_driving_block_input;

static int hack_frac_lut_no_legality;
static int hack_force_safe_latch;

static int indexofcrit; /**< index of next most timing critical block */

/**@{*/
/** Timing information for blocks */
static float *criticality = NULL;
static int *critindexarray = NULL;
/**@}*/

static float **net_pin_backward_criticality = NULL;
static float **net_pin_forward_criticality = NULL;



/*****************************************/
/*local functions*/
/*****************************************/

static int num_ext_inputs (int iblk);
static void check_clocks (boolean *is_clock);

static int get_max_cluster_size(t_pb_type *pb_type);
static int get_max_primitive_inputs(t_pb_type *pb_type);
static int get_max_pb_depth(t_pb_type *pb_type);

#if 0
static void check_for_duplicate_inputs ();
#endif 
static boolean is_logical_blk_in_pb(int iblk, t_pb *pb);

static void add_blk_to_pb_stats_candidates(int iblk, float *gain, t_pb *pb);

static void alloc_and_init_clustering (boolean global_clocks, float alpha, float beta, int max_cluster_size, int max_primitive_inputs, int max_pb_depth, int max_models);
static void free_pb_stats_recursive (t_pb *pb, int max_models);
static boolean outputs_clocks_and_models_feasible (enum e_packer_algorithm packer_algorithm, int iblk, boolean *is_clock, t_pb *cur_pb);
static boolean models_feasible(enum e_packer_algorithm packer_algorithm, int iblk, const t_pb_type *cur_pb_type, t_pb *cur_pb, int mode);
static boolean primitive_feasible(int iblk, t_pb *cur_pb);
static boolean primitive_type_feasible(int iblk, const t_pb_type *cur_pb_type, t_pb *memory_class_pb, int sibling_memory_blk);


static int get_logical_block_by_num_ext_inputs (INP enum e_packer_algorithm packer_algorithm,
                                                                                INOUTP t_pb *cur_pb,
                                                                                INP int ext_inps, 
                                                                                INP enum e_removal_policy remove_flag);

static int get_free_logical_block_with_most_ext_inputs_for_cluster (INP enum e_packer_algorithm packer_algorithm,
                                                                                                                                        INOUTP t_pb *cur_pb);

static int get_seed_logical_block_with_most_ext_inputs (int max_primitive_inputs);
static void alloc_and_load_pb_stats (t_pb *pb, int max_models, int max_cluster_size, int max_primitive_inputs);

static enum e_block_pack_status alloc_and_load_pb(INP enum e_packer_algorithm packer_algorithm, INP t_pb_graph_node *pb_graph_node, INP int iblock, INOUTP t_pb * pb, INP int max_models, INP int max_cluster_size, INP int max_primitive_inputs);

static void update_connection_gain_values (int inet, int clustered_block, t_pb * cur_pb,
                                                enum e_net_relation_to_clustered_block net_relation_to_clustered_block);

static void update_length_gain_values (int inet, int clustered_block, t_pb* cur_pb,
                                                enum e_net_relation_to_clustered_block net_relation_to_clustered_block);

static void mark_and_update_partial_gain (int inet, 
                                                                                  enum e_gain_update gain_flag, 
                                                                                  int clustered_block, 
                                                                                  int port_on_clustered_block, 
                                                                                  int pin_on_clustered_block,
                                                                                  boolean timing_driven, 
                                                                                  boolean connection_driven,
                                                                                  enum e_net_relation_to_clustered_block net_relation_to_clustered_block);

static void update_total_gain(float alpha, float beta, boolean timing_driven, boolean 
                              connection_driven, boolean global_clocks, t_pb *pb);

static void update_cluster_stats (      INP int new_blk,
                                                                        INP int clb_index,
                                                                        INP boolean *is_clock, 
                                                                        INP boolean global_clocks, 
                                                                        INP float alpha, 
                                                                        INP float beta,
                                                                        INP boolean timing_driven, 
                                                                        INP boolean connection_driven);

static void start_new_cluster(INP enum e_packer_algorithm packer_algorithm,
                                                          INP const t_arch * arch,
                                                          INOUTP t_block *new_cluster,
                                                          INP int clb_index,
                                                          INP int istart,
                                                                INP float aspect,
                                                                INOUTP int *num_used_instances_type, 
                                                                INOUTP int *num_instances_type,
                                                                INP int num_models,
                                                                INP int max_cluster_size,
                                                                INP int max_primitive_inputs);

static boolean inputs_outputs_models_and_clocks_feasible (INP enum e_packer_algorithm packer_algorithm, int iblk, boolean *is_clock, t_pb *cur_pb);

static int get_highest_gain_logical_block (INP enum e_packer_algorithm packer_algorithm,
                                                                                   INOUTP t_pb *cur_pb,
                                                                        INP boolean *is_clock, 
                                                                        INP boolean (*is_feasible) 
                                                                        (enum e_packer_algorithm packer_algorithm, int iblk, boolean *is_clock, t_pb *cur_pb), 
                                                                        INP enum e_gain_type gain_mode);

static int get_logical_block_for_cluster (INP enum e_packer_algorithm packer_algorithm,
                                                                                  INP t_pb *cur_pb,
                                                                                 INP boolean *is_clock,
                                                                                 INP boolean allow_unrelated_clustering);

static int get_free_logical_block_with_fewest_ext_inputs (INP enum e_packer_algorithm packer_algorithm,
                                                                                                                  INOUTP t_pb *cur_pb);

static int get_most_feasible_logical_block (INOUTP t_pb *cur_pb);

static void alloc_and_load_cluster_info (INP int num_clb, INOUTP t_block *clb);

static void check_clustering (int num_clb, t_block *clb, boolean *is_clock);

static void check_cluster_logical_blocks (t_pb *pb, boolean *blocks_checked);

static int get_most_critical_unclustered_block(void);

static void free_cb (t_pb *pb, int max_models);
static void free_pb_stats(t_pb_stats pb_stats, int max_models);
static void free_pb (t_pb *pb, int max_models);

/*****************************************/
/*globally accessable function*/

/** Does the actual work of clustering multiple VPACK_LUT+FF logic blocks 
 * into clusters.                                                  
 *
 * note: I allow timing_driven and connection_driven to be simultaneously true
 * in this case, connection_driven is responsible for all clustering decisions
 * but timing analysis is still enabled (useful for viewing the constant delay
 * results)
 * Algorithm employed:
 * 1.  Find type that can legally hold block and create cluster with pb info
 * 2.  Populate started cluster
 * 3.  Repeat 1 until no more blocks need to be clustered
 */
void do_clustering (const t_arch *arch, int num_models, boolean global_clocks,
       boolean *is_clock, boolean hill_climbing_flag, 
       char *out_fname, boolean timing_driven, 
       enum e_cluster_seed cluster_seed_type, float alpha, float beta,
       int recompute_timing_after, float block_delay, 
       float intra_cluster_net_delay, float inter_cluster_net_delay,
           float aspect,
       boolean allow_unrelated_clustering, 
       boolean allow_early_exit, boolean connection_driven, 
           enum e_packer_algorithm packer_algorithm,
           boolean hack_no_legal_frac_lut, boolean hack_safe_latch){


 int istart, i, j, k, m, iblk;
 int blocks_since_last_analysis;
 int next_blk, prev_blk;

 int num_blocks_hill_added;
 int num_logical_blocks_clustered;
 int max_cluster_size, cur_cluster_size, max_primitive_inputs, cur_primitive_inputs, max_pb_depth, cur_pb_depth;

 int *hill_climbing_inputs_avail;
 
 t_block *clb; 
 t_pb *cur_pb;
 int num_clb;

 boolean critical_path_minimized;
 boolean early_exit;
 
 enum e_block_pack_status block_pack_status;

 int *num_used_instances_type, *num_instances_type; /* [0..num_types] Holds array for total number of each cluster_type available */
 float **net_slack = NULL;
 float num_paths_scaling, distance_scaling;

 float crit;

 hack_frac_lut_no_legality = hack_no_legal_frac_lut;
 hack_force_safe_latch = hack_safe_latch;

 /* TODO: This is memory inefficient, fix if causes problems */
 clb = my_calloc(num_logical_blocks,sizeof(t_block));
 num_clb = 0;
 istart = NO_CLUSTER;

 /* determine bound on cluster size and primitive input size */
 max_cluster_size = 0;
 max_primitive_inputs = 0;
 max_pb_depth = 0;

 indexofcrit = 0;

 for(i = 0; i < num_types; i++) {
         if(EMPTY_TYPE == &type_descriptors[i]) 
                 continue;
         cur_cluster_size = get_max_cluster_size(type_descriptors[i].pb_type);
         cur_primitive_inputs = get_max_primitive_inputs(type_descriptors[i].pb_type);
         cur_pb_depth = get_max_pb_depth(type_descriptors[i].pb_type);
         if(cur_cluster_size > max_cluster_size) {
                 max_cluster_size = cur_cluster_size;
         }
         if(cur_primitive_inputs > max_primitive_inputs) {
                 max_primitive_inputs = cur_primitive_inputs;
         }
         if(cur_pb_depth > max_pb_depth) {
                 max_pb_depth = cur_pb_depth;
         }
 }

 if(hill_climbing_flag) {
         hill_climbing_inputs_avail = (int *) my_calloc (max_cluster_size + 1, sizeof(int));
 } else {
         hill_climbing_inputs_avail = NULL; /* if used, die hard */
 }

 /* TODO: make better estimate for nx and ny */
 nx = ny = 1;

 check_clocks (is_clock);
#if 0
 check_for_duplicate_inputs ();
#endif
 alloc_and_init_clustering (global_clocks, alpha, beta, max_cluster_size, max_primitive_inputs, max_pb_depth, num_models);

 blocks_since_last_analysis = 0;
 critical_path_minimized = FALSE;
 early_exit = FALSE;
 num_logical_blocks_clustered = 0;
 num_blocks_hill_added = 0;
 num_used_instances_type = (int*)my_calloc (num_types, sizeof (int));
 num_instances_type = (int*)my_calloc (num_types, sizeof (int));
 
 assert(max_cluster_size < MAX_SHORT); /* Limit maximum number of elements for each cluster */
 
 if (timing_driven){
         net_slack = alloc_and_load_pre_packing_timing_graph(block_delay, inter_cluster_net_delay, arch->models);
        load_net_slack(net_slack, 0);
        
        criticality=(float*)my_calloc(num_logical_blocks,sizeof(float));

        critindexarray=(int*)my_malloc(num_logical_blocks*sizeof(int));

        for(i = 0; i < num_logical_blocks; i++) {
                critindexarray[i] = i;
        }

        /* Calculate criticality based on slacks and tie breakers (# paths, distance from source) */
        for(i = 0; i < num_tnodes; i++) {
                iblk = tnode[i].block;
                num_paths_scaling = SCALE_NUM_PATHS * (float)tnode[i].normalized_total_critical_paths;
                distance_scaling = SCALE_DISTANCE_VAL * (float)tnode[i].normalized_T_arr;
                crit = (1 - tnode[i].normalized_slack) + num_paths_scaling + distance_scaling;
                if(criticality[iblk] < crit) {
                        criticality[iblk] = crit;
                }
        }

        net_pin_backward_criticality = (float**)my_calloc(num_logical_nets, sizeof(float*));
        net_pin_forward_criticality = (float**)my_calloc(num_logical_nets, sizeof(float*));
        for(i = 0; i < num_logical_nets; i++) {
                net_pin_backward_criticality[i] = (float *)my_calloc(vpack_net[i].num_sinks + 1, sizeof(float));
                net_pin_forward_criticality[i] = (float *)my_calloc(vpack_net[i].num_sinks + 1, sizeof(float));
                for(j = 0; j <= vpack_net[i].num_sinks; j++) {
                        net_pin_backward_criticality[i][j] = criticality[vpack_net[i].node_block[j]];
                        net_pin_forward_criticality[i][j] = criticality[vpack_net[i].node_block[0]];
                }
        }

        heapsort(critindexarray, criticality, num_logical_blocks, 1);

        /*print_critical_path("clustering_critical_path.echo");*/


   if (cluster_seed_type == VPACK_TIMING){
     istart=get_most_critical_unclustered_block();
   }
   else {/*max input seed*/
        printf("get_seed_logical_block_with_most_ext_inputs\n");
           istart = get_seed_logical_block_with_most_ext_inputs(max_primitive_inputs);
   }
 }
 else /*cluster seed is max input (since there is no timing information)*/{
         istart = get_seed_logical_block_with_most_ext_inputs(max_primitive_inputs);
 }

 while (istart != NO_CLUSTER) {

        reset_legalizer_for_cluster(&clb[num_clb]);
        
        /* start a new cluster and reset all stats */
        start_new_cluster(packer_algorithm, arch, &clb[num_clb], num_clb, istart, aspect, num_used_instances_type, num_instances_type, num_models, max_cluster_size, max_primitive_inputs);
        if(logical_block[istart].type != VPACK_INPAD && logical_block[istart].type != VPACK_OUTPAD) 
        {
                printf("Complex Block %d: %s type %s\n", num_clb, clb[num_clb].name, clb[num_clb].type->name);
                fflush(stdout);
        }
        update_cluster_stats (istart, num_clb, is_clock, global_clocks, alpha, beta, timing_driven, connection_driven);
        num_clb++;
         

    num_logical_blocks_clustered ++;

    if (timing_driven && !early_exit) {
      blocks_since_last_analysis++;
      /*it doesn't make sense to do a timing analysis here since there*
       *is only one logical_block clustered it would not change anything      */
    }
         
        /* First try to pack primitive into cluster, select next block based on closest open sibling if available */
        cur_pb = logical_block[istart].pb->parent_pb;
        prev_blk = NO_CLUSTER;

        while (cur_pb) {
                
                if(packer_algorithm == PACK_BRUTE_FORCE) { /* if using brute force approach, look at all possible free blocks in cluster */
                        cur_pb = clb[num_clb - 1].pb;
                }

                next_blk = get_logical_block_for_cluster(packer_algorithm,
                                                                                cur_pb, 
                                                                                 is_clock,
                                                                                 allow_unrelated_clustering);

                block_pack_status = alloc_and_load_pb(packer_algorithm, cur_pb->pb_graph_node, next_blk, cur_pb, num_models, max_cluster_size, max_primitive_inputs); 
                if(block_pack_status != BLK_PASSED) {
                        if(next_blk != NO_CLUSTER && prev_blk != next_blk) {
                                if(block_pack_status == BLK_FAILED_ROUTE) {
                                        #ifdef DEBUG_FAILED_PACKING_CANDIDATES
                                                printf("NO_ROUTE:%s#%d|%s ", logical_block[next_blk].name, next_blk, logical_block[next_blk].model->name); 
                                        #else
                                                printf(".");
                                        #endif
                                } else {
                                        #ifdef DEBUG_FAILED_PACKING_CANDIDATES
                                                printf("FAILED_CHECK:%s#%d|%s check %d", logical_block[next_blk].name, next_blk, logical_block[next_blk].model->name, block_pack_status); 
                                        #else
                                                printf(".");
                                        #endif
                                }
                                prev_blk = next_blk;
                        } else {
                                prev_blk = NO_CLUSTER;
                                cur_pb = cur_pb->parent_pb;
                        }
                        continue;
                } else {
                        /* Continue packing by filling smallest cluster */
                        if(hack_frac_lut_no_legality) {
                                logical_block[next_blk].clb_index = num_clb - 1;
                        }
                        cur_pb = logical_block[next_blk].pb->parent_pb;
                        prev_blk = NO_CLUSTER;
                        #ifdef DEBUG_FAILED_PACKING_CANDIDATES                  
                                printf("PASSED:%s#%d ", logical_block[next_blk].name, next_blk); 
                        #else
                                printf(".");
                        #endif
                }
                update_cluster_stats (next_blk, num_clb - 1, is_clock, global_clocks, 
                                                alpha, beta, timing_driven, connection_driven);

                num_logical_blocks_clustered ++;

                if (timing_driven && !early_exit) {
                blocks_since_last_analysis++; /* historically, timing slacks were recomputed after X number of blocks were packed, but this doesn't significantly alter results so I (jluu) did not port the code */
        
      }
    }
        if(logical_block[istart].type != VPACK_INPAD && logical_block[istart].type != VPACK_OUTPAD) 
        {
                printf("\n");
        }

        save_cluster_solution();
        if(hack_frac_lut_no_legality) {
                k = 0;
                for(i = 0; i < clb[num_clb-1].pb->pb_graph_node->num_input_ports; i++) {
                        for(j = 0; j < clb[num_clb-1].pb->pb_graph_node->num_input_pins[i]; j++) {
                                while(k < num_logical_nets) { 
                                        if(!clb[num_clb-1].pb->pb_stats.net_output_in_pb[k] && !vpack_net[k].is_global && clb[num_clb-1].pb->pb_stats.num_pins_of_net_in_pb[k] != 0)
                                        {
                                                rr_node[clb[num_clb-1].pb->pb_graph_node->input_pins[i][j].pin_count_in_cluster].net_num = k;
                                                k++; 
                                                break;
                                        }
                                        k++; 
                                }               
                        }
                }
                /* check if nets are overused */
                while(k < num_logical_nets) { 
                        if(!clb[num_clb-1].pb->pb_stats.net_output_in_pb[k] && !vpack_net[k].is_global && clb[num_clb-1].pb->pb_stats.num_pins_of_net_in_pb[k] != 0)
                        {
                                printf(ERRTAG "Too many input nets used in cluster %s\n", clb[num_clb-1].name);
                                assert(0);
                        }
                        k++; 
                }                               
                k = 0;
                for(i = 0; i < clb[num_clb-1].pb->pb_graph_node->num_output_ports; i++) {
                        for(j = 0; j < clb[num_clb-1].pb->pb_graph_node->num_output_pins[i]; j++) {
                                while(k < num_logical_nets) { 
                                        for(m = 0; m <= vpack_net[k].num_sinks; m++) {
                                                if(logical_block[vpack_net[k].node_block[m]].clb_index != num_clb - 1) {
                                                        break;
                                                }
                                        }
                                        if(clb[num_clb-1].pb->pb_stats.net_output_in_pb[k] && (clb[num_clb-1].pb->pb_stats.num_pins_of_net_in_pb[k] < vpack_net[k].num_sinks + 1))
                                        {
                                                rr_node[clb[num_clb-1].pb->pb_graph_node->output_pins[i][j].pin_count_in_cluster].net_num = k;
                                                k++; 
                                                break;
                                        }
                                        k++; 
                                }
                        }
                }
                while(k < num_logical_nets) { 
                        if(clb[num_clb-1].pb->pb_stats.net_output_in_pb[k] && (clb[num_clb-1].pb->pb_stats.num_pins_of_net_in_pb[k] < vpack_net[k].num_sinks + 1))
                        {
                                printf(ERRTAG "Too many output nets used in cluster %s\n", clb[num_clb-1].name);
                                assert(0);
                        }
                        k++; 
                }               
                k = 0;
                for(i = 0; i < clb[num_clb-1].pb->pb_graph_node->num_clock_ports; i++) {
                        for(j = 0; j < clb[num_clb-1].pb->pb_graph_node->num_clock_pins[i]; j++) {
                                while(k < num_logical_nets) { 
                                        if(!clb[num_clb-1].pb->pb_stats.net_output_in_pb[k] && vpack_net[k].is_global && clb[num_clb-1].pb->pb_stats.num_pins_of_net_in_pb[k] != 0)
                                        {
                                                rr_node[clb[num_clb-1].pb->pb_graph_node->clock_pins[i][j].pin_count_in_cluster].net_num = k;
                                                k++; 
                                                break;
                                        }
                                        k++; 
                                }
                        }
                }       
                while(k < num_logical_nets) { 
                        if(!clb[num_clb-1].pb->pb_stats.net_output_in_pb[k] && vpack_net[k].is_global && clb[num_clb-1].pb->pb_stats.num_pins_of_net_in_pb[k] != 0)
                        {
                                printf(ERRTAG "Too many clock nets used in cluster %s\n", clb[num_clb-1].name);
                                assert(0);
                        }
                        k++; 
                }               
        }

    if (timing_driven){
      if (num_blocks_hill_added > 0  && !early_exit) {
                blocks_since_last_analysis += num_blocks_hill_added;
      }

      if (cluster_seed_type == VPACK_TIMING){
        istart=get_most_critical_unclustered_block();
      }
      else { /*max input seed*/
                istart = get_seed_logical_block_with_most_ext_inputs(max_primitive_inputs);
      }
    }
    else /*cluster seed is max input (since there is no timing information)*/
      istart=get_seed_logical_block_with_most_ext_inputs(max_primitive_inputs);

    free_pb_stats_recursive (clb[num_clb-1].pb, num_models);
 }

 if (timing_driven){
   free_timing_graph(net_slack);
 }

 free_cluster_legality_checker();

 alloc_and_load_cluster_info (num_clb, clb); 

 check_clustering (num_clb, clb, is_clock);


 output_clustering(     clb, num_clb, global_clocks, is_clock, out_fname, FALSE);
#ifdef DUMP_BLIF_ECHO
 if(!hack_frac_lut_no_legality) /* must have routing graph before dumping blif */
        output_blif(    clb, num_clb, global_clocks, is_clock, "post_packing_blif.echo", FALSE);
#endif

 if(hill_climbing_flag)
 {
         free (hill_climbing_inputs_avail);
 }

 for(i = 0; i < num_clb; i++) {
         free_cb(clb[i].pb, num_models);
        free(clb[i].name);
        free(clb[i].nets);
        free(clb[i].pb);
 }
 free(clb);

 free (num_used_instances_type);
 free (num_instances_type);
 free (unclustered_list_head);
 free (memory_pool); 
 free (net_output_feeds_driving_block_input);

}

/** Returns the number of input pins on this logical_block that must be hooked 
 * up through external interconnect.  That is, the number of input   
 * pins used - the number which connect (internally) to the outputs.   
 */
static int num_ext_inputs (int iblk) {

 int ext_inps, output_net, ipin, opin;

 t_model_ports *port, *out_port;
 
 /* TODO: process to get ext_inps is slow, should cache in lookup table */
 ext_inps = 0;
 port = logical_block[iblk].model->inputs;
 while(port) {
         if(port->is_clock == FALSE) {
                 for(ipin = 0; ipin < port->size; ipin++) {
                         if(logical_block[iblk].input_nets[port->index][ipin] != OPEN) {
                                 ext_inps++;
                         }
                         out_port = logical_block[iblk].model->outputs;
                         while(out_port) {
                                 for(opin = 0; opin < out_port->size; opin++) {
                                         output_net = logical_block[iblk].output_nets[out_port->index][opin];
                                         if(output_net == OPEN)
                                                continue;
                                        /* TODO: I could speed things up a bit by computing the number of inputs *
                                        * and number of external inputs for each logic logical_block at the start of   *
                                        * clustering and storing them in arrays.  Look into if speed is a      *
                                        * problem.                                                             */

                                         if (logical_block[iblk].input_nets[port->index][ipin] == output_net) {
                                                ext_inps--;
                                                break;
                                        }
                                 }
                                 out_port = out_port->next;
                         }
                 }
         }
         port = port->next;
 }

 assert(ext_inps >= 0);
 
 return (ext_inps);
}


/*****************************************/
/** Checks that nets used as clock inputs to latches are never also used 
 * as VPACK_LUT inputs.  It's electrically questionable, and more importantly 
 * would break the clustering code.                                     
 */
static void check_clocks (boolean *is_clock) {

 int inet, iblk, ipin;
 t_model_ports *port;

 for (iblk=0;iblk<num_logical_blocks;iblk++) {
    if (logical_block[iblk].type != VPACK_OUTPAD) {
                port = logical_block[iblk].model->inputs;
                while(port) {
                   for (ipin = 0; ipin < port->size; ipin++) {
                           inet = logical_block[iblk].input_nets[port->index][ipin]; 
                          if (inet != OPEN) {
                                 if (is_clock[inet]) {
                                        printf("Error in check_clocks.  Net %d (%s) is a clock, but "
                                                   "also\n"
                                                   "\tconnects to a logic block input on logical_block %d (%s).\n", inet, 
                                                   vpack_net[inet].name, iblk, logical_block[iblk].name);
                                        printf("This would break the current clustering "
                                                   "implementation and is electrically\n"
                                                   "\tquestionable, so clustering has been aborted.\n");
                                        exit (1);
                                 }
                          }
                   }
                   port = port->next;
                }
    }
 }
}

static int get_max_cluster_size(t_pb_type *pb_type) {
        int i, j;
        int max_size, temp_size;
        if (pb_type->modes == 0) {
                max_size = pb_type->num_pb;
        } else {
                max_size = 0;
                for(i = 0; i < pb_type->num_modes; i++) {
                        temp_size = 0;
                        for(j = 0; j < pb_type->modes[i].num_pb_type_children; j++) {
                                temp_size += pb_type->modes[i].pb_type_children[j].num_pb * 
                                        get_max_cluster_size(&pb_type->modes[i].pb_type_children[j]);
                        }
                        if(temp_size > max_size) {
                                max_size = temp_size;
                        }
                }
        }
        return max_size;
}


static int get_max_primitive_inputs(t_pb_type *pb_type) {
        int i, j;
        int max_size, temp_size;
        if (pb_type->blif_model != NULL) {
                max_size = pb_type->num_input_pins;
        } else {
                max_size = 0;
                for(i = 0; i < pb_type->num_modes; i++) {
                        temp_size = 0;
                        for(j = 0; j < pb_type->modes[i].num_pb_type_children; j++) {
                                temp_size = get_max_primitive_inputs(&pb_type->modes[i].pb_type_children[j]);
                                if(temp_size > max_size) {
                                        max_size = temp_size;
                                }
                        }
                }
        }
        return max_size;
}

static int get_max_pb_depth(t_pb_type *pb_type) {
        int i, j;
        int max_depth, temp_depth;
        max_depth = pb_type->depth;
        for(i = 0; i < pb_type->num_modes; i++) {
                for(j = 0; j < pb_type->modes[i].num_pb_type_children; j++) {
                        temp_depth = get_max_pb_depth(&pb_type->modes[i].pb_type_children[j]);
                        if(temp_depth > max_depth) {
                                max_depth = temp_depth;
                        }
                }
        }
        return max_depth;
}

/** Determine if logical block is in pb */
static boolean is_logical_blk_in_pb(int iblk, t_pb *pb) {
        t_pb * cur_pb;
        cur_pb = logical_block[iblk].pb;
        while(cur_pb) {
                if(cur_pb == pb) {
                        return TRUE;
                }
                cur_pb = cur_pb->parent_pb;
        }
        return FALSE;
}

/** Add blk to list of feasible blocks sorted according to gain */
static void add_blk_to_pb_stats_candidates(int iblk, float *gain, t_pb *pb) {
        int i, j;
        i = 0;
        if(i == pb->pb_stats.num_marked_models) {
                /* Corresponding model not found, add it */
                pb->pb_stats.num_marked_models++;
                pb->pb_stats.num_feasible_blocks[i] = 1;
                pb->pb_stats.feasible_blocks[i][0] = iblk;
        } else {
                /* found matching model, bubble sort */
                if(pb->pb_stats.num_feasible_blocks[i] >= AAPACK_MAX_FEASIBLE_BLOCK_ARRAY_SIZE - 1) {
                        /* maximum size for array, remove smallest gain element and sort */
                        if(gain[iblk] > gain[pb->pb_stats.feasible_blocks[i][0]]) {
                                /* single loop insertion sort */
                                for(j = 0; j < pb->pb_stats.num_feasible_blocks[i] - 1; j++) {
                                        if(gain[iblk] <= gain[pb->pb_stats.feasible_blocks[i][j + 1]]) {
                                                pb->pb_stats.feasible_blocks[i][j] = iblk;
                                                break;
                                        } else {
                                                pb->pb_stats.feasible_blocks[i][j] = pb->pb_stats.feasible_blocks[i][j + 1];
                                        }
                                }
                                if(j == pb->pb_stats.num_feasible_blocks[i] - 1) {
                                        pb->pb_stats.feasible_blocks[i][j] = iblk;
                                }
                        }
                } else {
                        /* Expand array and single loop insertion sort */
                        for(j = pb->pb_stats.num_feasible_blocks[i] - 1; j >= 0; j--) {
                                if(gain[pb->pb_stats.feasible_blocks[i][j]] > gain[iblk]) {
                                        pb->pb_stats.feasible_blocks[i][j + 1] = pb->pb_stats.feasible_blocks[i][j];
                                } else {
                                        pb->pb_stats.feasible_blocks[i][j + 1] = iblk;
                                        break;
                                }
                        }
                        if(j < 0) {
                                pb->pb_stats.feasible_blocks[i][0] = iblk;
                        }
                        pb->pb_stats.num_feasible_blocks[i]++;
                }
        }
}



/*****************************************/
/** Allocates the main data structures used for clustering and properly 
 * initializes them.                                                   
 */
static void alloc_and_init_clustering (boolean global_clocks, 
                                                                           float alpha, float beta, 
                                                                           int max_cluster_size, 
                                                                           int max_primitive_inputs, 
                                                                           int max_pb_depth, 
                                                                           int max_models) {

 int i, ext_inps, ipin, driving_blk, inet;
 struct s_ilink *next_ptr;
 
 alloc_and_load_cluster_legality_checker();

 for (i=0;i<num_logical_blocks;i++) {
        logical_block[i].clb_index = NO_CLUSTER;                        
 }

 unclustered_list_head = (struct s_ilink *) my_calloc(max_primitive_inputs + 1, sizeof(struct s_ilink));
 unclustered_list_head_size = max_primitive_inputs + 1;

 for (i = 0; i <= max_primitive_inputs; i++) {
    unclustered_list_head[i].next = NULL;
 }
 
 
 memory_pool = (struct s_ilink *) my_malloc (num_logical_blocks * sizeof (struct s_ilink));
 next_ptr = memory_pool;
 
 for (i=0;i<num_logical_blocks;i++) {
   ext_inps = num_ext_inputs(i);
   next_ptr->next = unclustered_list_head[ext_inps].next;
   unclustered_list_head[ext_inps].next = next_ptr;
   next_ptr->iblk = i;
   next_ptr++;
 }


 net_output_feeds_driving_block_input = (int *) my_malloc (
                 num_logical_nets * sizeof (int));

        for (inet=0;inet<num_logical_nets;inet++) {
                net_output_feeds_driving_block_input[inet] = 0;
                driving_blk = vpack_net[inet].node_block[0];
                for (ipin=1;ipin<=vpack_net[inet].num_sinks;ipin++) {
                        if (vpack_net[inet].node_block[ipin] == driving_blk) {
                                net_output_feeds_driving_block_input[inet]++;
                        }
                }
        }
}


/*****************************************/
static void free_pb_stats_recursive (t_pb *pb, int max_models) {

        int i, j;
        /* Releases all the memory used by clustering data structures.   */
        if(pb) {
                if(pb->pb_graph_node != NULL) {
                        if(pb->pb_graph_node->pb_type->num_modes != 0) {
                                for(i = 0; i < pb->pb_graph_node->pb_type->modes[pb->mode].num_pb_type_children; i++) {
                                        for(j = 0; j < pb->pb_graph_node->pb_type->modes[pb->mode].pb_type_children[i].num_pb; j++) {
                                                if(pb->child_pbs && pb->child_pbs[i]) {
                                                        free_pb_stats_recursive (&pb->child_pbs[i][j], max_models);
                                                }
                                        }
                                }
                        }
                }
                free_pb_stats(pb->pb_stats, max_models);
        }
}


/*****************************************/
/** Checks if logical_block iblk could be adding to the open cluster without 
 * violating clocking constraints.  Returns TRUE if it's OK.  Some  
 * parameters are unused since this function needs the same inter-  
 * face as the other feasibility checkers.                          
 */
static boolean outputs_clocks_and_models_feasible (enum e_packer_algorithm packer_algorithm, int iblk, boolean *is_clock, t_pb *cur_pb) {

 int inet, depth, clocks_avail;
 t_model_ports *port;
 int ipin, output_net, outputs_avail;
 boolean clocks_feasible, outputs_feasible;
 t_pb * temp_pb;

 /* Assumptions: 1. Clock network unique, can only connect to clock network */
 /*              2. Logic block output can't internally connect to clocks. */
 clocks_feasible = outputs_feasible = TRUE;
 temp_pb = cur_pb;
 while(temp_pb && clocks_feasible && outputs_feasible) {
        depth = temp_pb->pb_graph_node->pb_type->depth;

        clocks_avail = cur_pb->pb_stats.clocks_avail;
        if(clocks_avail == NOT_VALID) {
                clocks_avail = temp_pb->pb_graph_node->pb_type->num_clock_pins;
        }

         inet = logical_block[iblk].clock_net;
         if (inet != OPEN) {
                 if (temp_pb->pb_stats.num_pins_of_net_in_pb[inet] == 0) {
                   clocks_avail--;
                }   
                else if (temp_pb->pb_stats.num_pins_of_net_in_pb[inet] == 1 &&
                   temp_pb->pb_stats.net_output_in_pb[inet]) {
                   clocks_avail--;
                }   
         }

         
         outputs_avail = temp_pb->pb_stats.outputs_avail;

         port = logical_block[iblk].model->outputs;
         while(port) {
                /* Outputs that connect to internal blocks free up an input pin. */
                 for(ipin = 0; ipin < port->size; ipin++) {
                         output_net = logical_block[iblk].output_nets[port->index][ipin];
                         if (output_net != OPEN) {
                                 if(temp_pb->pb_stats.num_pins_of_net_in_pb[output_net] >= vpack_net[output_net].num_sinks - net_output_feeds_driving_block_input[output_net]) {
                                         if((temp_pb->pb_stats.num_pins_of_net_in_pb[output_net] != vpack_net[output_net].num_sinks - net_output_feeds_driving_block_input[output_net])) {
                                                 printf("[INTERNAL ERROR] net %d %s %d != %d\n", output_net, vpack_net[output_net].name,
                                                         temp_pb->pb_stats.num_pins_of_net_in_pb[output_net], vpack_net[output_net].num_sinks - net_output_feeds_driving_block_input[output_net]);
                                         }
                                         assert(temp_pb->pb_stats.num_pins_of_net_in_pb[output_net] == vpack_net[output_net].num_sinks - net_output_feeds_driving_block_input[output_net]);
                                 } else {
                                         outputs_avail--;
                                 }
                         }
                 }
                 port = port->next;
         }

         port = logical_block[iblk].model->inputs;
         while(port) {
                 if(port->is_clock == TRUE) {
                         port = port->next;
                         continue;
                 }
                 for (ipin = 0; ipin < port->size; ipin++) {
                        inet = logical_block[iblk].input_nets[port->index][ipin];
                        if(inet != OPEN) {
                                if(temp_pb->pb_stats.net_output_in_pb[inet] && 
                                        temp_pb->pb_stats.num_pins_of_net_in_pb[inet] + net_output_feeds_driving_block_input[inet] == vpack_net[inet].num_sinks) {
                                        outputs_avail++;
                                }
                        }
                 }
                port = port->next;
         }

         clocks_feasible = (clocks_avail >= 0); 
         outputs_feasible = (outputs_avail >= 0);

         temp_pb = temp_pb->parent_pb;
 }

 if(models_feasible(packer_algorithm, iblk, cur_pb->pb_graph_node->pb_type, cur_pb, cur_pb->mode)) {
         if (clocks_feasible && outputs_feasible) 
                return (TRUE);
         else
                return (FALSE);
 } else {
         return FALSE;
 } 
}


static boolean models_feasible(enum e_packer_algorithm packer_algorithm, int iblk, const t_pb_type *cur_pb_type, t_pb *cur_pb, int mode) {
        struct s_linked_vptr *cur_model;
        int i, j, k, cur_ptr;
        struct s_ilink *ptr;
        boolean feasible;
        const t_pb_type *child_pb_type;
        
        cur_model = cur_pb_type->models_contained;


        assert(cur_pb == NULL || cur_pb->pb_graph_node->pb_type == cur_pb_type);
        assert(cur_pb == NULL || cur_pb->mode == mode);

        feasible = FALSE;
        while(cur_model) {
                if(cur_model->data_vptr == logical_block[iblk].model) {
                        feasible = TRUE;
                        break;
                }
                cur_model = cur_model->next;
        }

        if(!feasible) {
                return FALSE;
        }
        if(packer_algorithm == PACK_BRUTE_FORCE) {
                /* let the brute force packer determine if an empty slot exists */
                return TRUE;
        }

        feasible = FALSE;

        if(cur_pb_type->num_modes == 0) {
                if(hack_force_safe_latch) {
                        /* TODO: Either remove hack or actually make it a feature properly
                        
                           hack to make the LUT get packed before the LATCH gets packed for cases that the LATCH can be absorbed
                           for fracturable LUT architectures
                        */
                        if(strcmp(logical_block[iblk].model->name, "latch") == 0) {
                                i = logical_block[iblk].input_nets[0][0];
                                j = vpack_net[i].node_block[0];
                                if(logical_block[j].clb_index == NO_CLUSTER && vpack_net[i].num_sinks == 1 && 
                                        strcmp(logical_block[j].model->name, "names") == 0) {
                                        cur_ptr = logical_block[j].model->inputs[0].size;
                                        ptr = unclustered_list_head[cur_ptr].next;
                                        while(ptr == NULL && cur_ptr > 0) {
                                                cur_ptr--;
                                                ptr = unclustered_list_head[cur_ptr].next;
                                        }
                                        if (cur_ptr > 2)
                                                return FALSE;
                                }
                        }
                }

                return primitive_type_feasible(iblk, cur_pb_type, NULL, OPEN);
        }

        for(i = 0; i < cur_pb_type->modes[mode].num_pb_type_children; i++) {
                child_pb_type = &cur_pb_type->modes[mode].pb_type_children[i];
                if(cur_pb) {
                        for(k = 0; k < child_pb_type->num_pb && cur_pb->child_pbs && cur_pb->child_pbs[i]; k++) {
                                if(cur_pb->child_pbs[i][k].name == NULL) {
                                        break;
                                }
                        }
                        if(k == child_pb_type->num_pb) { 
                                /* no free child */
                                continue;
                        }
                }
                if(child_pb_type->num_modes == 0) {
                        feasible = primitive_type_feasible(iblk, &cur_pb_type->modes[mode].pb_type_children[i], NULL, OPEN);
                        if(feasible) {
                                return TRUE;
                        }
                } else {
                        for(j = 0; j < cur_pb_type->modes[mode].pb_type_children[i].num_modes; j++) {
                                feasible = models_feasible(packer_algorithm, iblk, &cur_pb_type->modes[mode].pb_type_children[i], NULL, j);
                                if(feasible) {
                                        return TRUE;
                                }
                        }
                }
        }

        return FALSE;
}

static boolean primitive_feasible(int iblk, t_pb *cur_pb) {
        const t_pb_type *cur_pb_type;
        int i;
        t_pb *memory_class_pb; /* Used for memory class only, for memories, open pins must be the same among siblings */
        int sibling_memory_blk;
        
        cur_pb_type = cur_pb->pb_graph_node->pb_type;
        memory_class_pb = NULL;
        sibling_memory_blk = OPEN;

        assert(cur_pb_type->num_modes == 0); /* primitive */
        if(cur_pb->logical_block != OPEN) {
                /* This pb already has a logical block */
                return FALSE;
        }

        if(cur_pb_type->class_type == MEMORY_CLASS) {
                /* memory class is special, all siblings must share all nets, including open nets, with the exception of data nets */
                /* find sibling if one exists */
                memory_class_pb = cur_pb->parent_pb;
                for(i = 0; i < cur_pb_type->parent_mode->num_pb_type_children; i++) {
                        if(memory_class_pb->child_pbs[cur_pb->mode][i].name != NULL && memory_class_pb->child_pbs[cur_pb->mode][i].logical_block != OPEN) {
                                sibling_memory_blk = memory_class_pb->child_pbs[cur_pb->mode][i].logical_block;
                        }
                }
                if(sibling_memory_blk == OPEN) {
                        memory_class_pb = NULL;
                }
        }

        return primitive_type_feasible(iblk, cur_pb_type, memory_class_pb, sibling_memory_blk);
}

static boolean primitive_type_feasible(int iblk, const t_pb_type *cur_pb_type, t_pb *memory_class_pb, int sibling_memory_blk) {
        t_model_ports *port;
        int i, j;
        boolean second_pass;

        /* check if ports are big enough */
        /* for memories, also check that pins are the same with existing siblings */
        port = logical_block[iblk].model->inputs;
        second_pass = FALSE;
        while(port || !second_pass) {
                /* TODO: This is slow if the number of ports are large, fix if becomes a problem */
                if(!port) {
                        second_pass = TRUE;
                        port = logical_block[iblk].model->outputs;
                }
                for(i = 0; i < cur_pb_type->num_ports; i++) {
                        if(cur_pb_type->ports[i].model_port == port) {
                                /* TODO: This is slow, I only need to check from 0 if it is a memory block, other blocks I can check from port->size onwards */
                                for(j = 0; j < port->size; j++) {
                                        if(port->dir == IN_PORT && !port->is_clock) {
                                                if(memory_class_pb) {
                                                        if(strstr(cur_pb_type->ports[i].port_class, "data") != cur_pb_type->ports[i].port_class) {
                                                                if(logical_block[iblk].input_nets[port->index][j] != logical_block[sibling_memory_blk].input_nets[port->index][j]) {
                                                                        return FALSE;
                                                                }
                                                        }
                                                }
                                                if(logical_block[iblk].input_nets[port->index][j] != OPEN && j >= cur_pb_type->ports[i].num_pins) {
                                                        return FALSE;
                                                }
                                        } else if(port->dir == OUT_PORT) {
                                                if(memory_class_pb) {
                                                        if(strstr(cur_pb_type->ports[i].port_class, "data") != cur_pb_type->ports[i].port_class) {
                                                                if(logical_block[iblk].output_nets[port->index][j] != logical_block[sibling_memory_blk].output_nets[port->index][j]) {
                                                                        return FALSE;
                                                                }
                                                        }
                                                }
                                                if(logical_block[iblk].output_nets[port->index][j] != OPEN && j >= cur_pb_type->ports[i].num_pins) {
                                                        return FALSE;
                                                }
                                        } else {
                                                assert(port->dir == IN_PORT && port->is_clock);
                                                assert(j == 0);
                                                if(memory_class_pb) {
                                                        if(logical_block[iblk].clock_net != logical_block[sibling_memory_blk].clock_net) {
                                                                return FALSE;
                                                        }
                                                }
                                                if(logical_block[iblk].clock_net != OPEN && j >= cur_pb_type->ports[i].num_pins) {
                                                        return FALSE;
                                                }
                                        }
                                }
                                break;
                        }
                }
                if(i == cur_pb_type->num_ports) {
                        if((logical_block[iblk].model->inputs != NULL && !second_pass) ||
                                logical_block[iblk].model->outputs != NULL && second_pass) {
                                /* physical port not found */
                                return FALSE;
                        }
                }
                if(port) {
                        port = port->next;
                }
        }
        return TRUE;
}

/*****************************************/
/** This routine returns a logical_block which has not been clustered, has  
 * no connection to the current cluster, satisfies the cluster     
 * clock constraints, is a valid subblock inside the cluster, does not exceed the cluster subblock units available,
 *      and has ext_inps external inputs.  If        
 * there is no such logical_block it returns NO_CLUSTER.  Remove_flag      
 * controls whether or not blocks that have already been clustered 
 * are removed from the unclustered_list data structures.  NB:     
 * to get a logical_block regardless of clock constraints just set clocks_avail > 0.                                                      
 */
static int get_logical_block_by_num_ext_inputs (            INP enum e_packer_algorithm packer_algorithm,
                                                                                                                INOUTP t_pb *cur_pb, 
                                                                                                                INP int ext_inps, 
                                                                                                                INP enum e_removal_policy remove_flag) {

 struct s_ilink *ptr, *prev_ptr;
 int ilogical_blk;
 
 prev_ptr = &unclustered_list_head[ext_inps];
 ptr = unclustered_list_head[ext_inps].next;
 
 while (ptr != NULL) {
         ilogical_blk = ptr->iblk;
         /* TODO: Get better candidate logical block in future, eg. return most timing critical or some other smarter metric */
         if (logical_block[ilogical_blk].clb_index == NO_CLUSTER) {
                if (outputs_clocks_and_models_feasible(packer_algorithm, ilogical_blk, NULL, cur_pb)) {
                        return ilogical_blk;
                }

       prev_ptr = ptr;

    }

    else if (remove_flag == REMOVE_CLUSTERED) {
       prev_ptr->next = ptr->next;
    }

    ptr = ptr->next;
 }

 return NO_CLUSTER;
}


/*****************************************/
/** This routine is used to find new blocks for clustering when there are no feasible       
 * blocks with any attraction to the current cluster (i.e. it finds       
 * blocks which are unconnected from the current cluster).  It returns    
 * the logical_block with the largest number of used inputs that satisfies the    
 * clocking and number of inputs constraints.  If no suitable logical_block is    
 * found, the routine returns NO_CLUSTER.                                 
 */
static int get_free_logical_block_with_most_ext_inputs_for_cluster (INP enum e_packer_algorithm packer_algorithm,
                                                                                                                                        INOUTP t_pb *cur_pb) {
 int ext_inps;
 int best_block;

 int inputs_avail;

 inputs_avail = cur_pb->pb_stats.inputs_avail;
 if(inputs_avail == NOT_VALID) {
         inputs_avail = cur_pb->pb_graph_node->pb_type->num_input_pins;
 }

 best_block = NO_CLUSTER;

 if(inputs_avail >= unclustered_list_head_size) {
         inputs_avail = unclustered_list_head_size - 1;
 }
 
 for (ext_inps = inputs_avail; ext_inps >= 0; ext_inps--) {
    best_block = get_logical_block_by_num_ext_inputs (packer_algorithm, cur_pb, ext_inps, REMOVE_CLUSTERED);
        if (best_block != NO_CLUSTER) {
       break;
        }
 }
 return best_block;
}

/*****************************************/
/** This routine is used to find the first seed logical_block for the clustering.  It returns    
 * the logical_block with the largest number of used inputs that satisfies the    
 * clocking and number of inputs constraints.  If no suitable logical_block is    
 * found, the routine returns NO_CLUSTER.                                 
 */
static int get_seed_logical_block_with_most_ext_inputs (int max_primitive_inputs) {

 int iblk, ext_inps;
 struct s_ilink *ptr, *prev_ptr;

 iblk = NO_CLUSTER;
 
 for (ext_inps=max_primitive_inputs;ext_inps>=0;ext_inps--) {
        prev_ptr = &unclustered_list_head[ext_inps];
        ptr = unclustered_list_head[ext_inps].next;
        
        while (ptr != NULL) {
                iblk = ptr->iblk;
                        
                if (logical_block[iblk].clb_index == NO_CLUSTER) {
                        prev_ptr->next = ptr->next; /* remove blk from list */
                        break;
                } else {
                        iblk = NO_CLUSTER;
                }

                prev_ptr = ptr;
                ptr = ptr->next;
        }

    if (iblk != NO_CLUSTER) 
       return (iblk);
 }

 return (NO_CLUSTER);   /* No suitable logical_block found. */
}


/*****************************************/
/* Call this routine when starting to fill up a new cluster.  It resets 
 * the gain vector, etc.                                                
 */
static void alloc_and_load_pb_stats (t_pb *pb, int max_models, int max_cluster_size, int max_primitive_inputs) {

 int j;

/* If statement below is for speed.  If nets are reasonably low-fanout,  *
 * only a relatively small number of blocks will be marked, and updating *
 * only those logical_block structures will be fastest.  If almost all blocks    *
 * have been touched it should be faster to just run through them all    *
 * in order (less addressing and better cache locality).                 */


        pb->pb_stats.gain = (float *) my_malloc (num_logical_blocks * sizeof (float));
        pb->pb_stats.lengthgain=(float*) my_malloc (num_logical_blocks * sizeof (float));
        pb->pb_stats.sharinggain=(float*) my_malloc (num_logical_blocks * sizeof (float));
        pb->pb_stats.hillgain =(float*) my_malloc (num_logical_blocks * sizeof (float));
        pb->pb_stats.connectiongain = (float*) my_malloc (num_logical_blocks * sizeof (float));
        pb->pb_stats.inputs_avail = NOT_VALID;
        pb->pb_stats.outputs_avail = NOT_VALID;
        pb->pb_stats.clocks_avail = NOT_VALID;
        pb->pb_stats.num_marked_models = 0;
        pb->pb_stats.cur_marked_model = NOT_VALID;
        pb->pb_stats.num_feasible_blocks = my_calloc(max_models, sizeof(int));
        pb->pb_stats.feasible_blocks = my_malloc(max_models * sizeof(int*));

         
        for (j=0;j<max_models;j++) {
                pb->pb_stats.feasible_blocks[j] = (int*) my_malloc (AAPACK_MAX_FEASIBLE_BLOCK_ARRAY_SIZE * sizeof (int));
        }

        for (j=0;j<num_logical_blocks;j++) {
                pb->pb_stats.gain[j] = 0.0;
                pb->pb_stats.lengthgain[j]= 0.0;
                pb->pb_stats.connectiongain[j] = 0;
                pb->pb_stats.sharinggain[j]=NOT_VALID;
                pb->pb_stats.hillgain[j]=NOT_VALID;
        }

        pb->pb_stats.num_pins_of_net_in_pb = (int *) my_malloc (num_logical_nets * sizeof(int));
        pb->pb_stats.net_output_in_pb = (boolean *) my_malloc (num_logical_nets * sizeof(boolean));

        for (j=0;j<num_logical_nets;j++) {
                pb->pb_stats.num_pins_of_net_in_pb[j] = 0;
                pb->pb_stats.net_output_in_pb[j] = FALSE;
        }
         
        pb->pb_stats.marked_nets = (int *) my_malloc ((max_primitive_inputs + 2) * max_cluster_size * sizeof(int));
        pb->pb_stats.marked_blocks = (int *) my_malloc (num_logical_blocks * sizeof(int));

        pb->pb_stats.num_marked_nets = 0;
        pb->pb_stats.num_marked_blocks = 0;

}
/*****************************************/

/** Allocate space within pb and load data for it given the current logical block. 
 *      Note: pb space and parent info must be loaded before calling this function
 *
 * TODO: add-in some heuristic for determing which pb to select if there are multiple choices
 */
static enum e_block_pack_status alloc_and_load_pb(INP enum e_packer_algorithm packer_algorithm, INP t_pb_graph_node *pb_graph_node, INP int iblock, 
                                                          INOUTP t_pb * pb, INP int max_models, int max_cluster_size, int max_primitive_inputs) {
        int i, j, k;
        const t_pb_type *pb_type;

        boolean is_primitive;
        enum e_block_pack_status block_pack_status;

        pb->pb_graph_node = pb_graph_node;
        pb->logical_block = NO_CLUSTER;

        block_pack_status = BLK_STATUS_UNDEFINED;

        if(iblock == NO_CLUSTER) {
                return BLK_FAILED_FEASIBLE;
        }

        pb_type = pb_graph_node->pb_type;
                
        is_primitive = (pb_type->num_modes == 0);

        /* TODO: It would be good to save and prune away nodes of types that I know won't fit, that way, I don't have to traverse the tree
        for types that don't work, this runtime optimization can be done later */
        if(is_primitive) { 
                if(!primitive_feasible(iblock, pb)) {
                        return BLK_FAILED_FEASIBLE;
                }
                assert(pb->logical_block == OPEN);
                /* check if I can add and route this block, if they yes, then success, if not, fail */
                if(hack_frac_lut_no_legality) {
                        block_pack_status = BLK_PASSED;
                        pb->logical_block = iblock;
                        logical_block[iblock].pb = pb;
                } else {
                        block_pack_status = try_add_block_to_current_cluster_and_primitive(iblock, pb);
                }
                if(block_pack_status == BLK_PASSED) {
                        pb->name = my_strdup(logical_block[iblock].name);
                } 
        } else {
                if(pb->child_pbs == NULL) {
                        /* first time here so must allocate space and determine mode of operation */
                        for(i = 0; i < pb_type->num_modes && block_pack_status != BLK_PASSED; i++) {
                                pb->mode = i;
                                if(!models_feasible(packer_algorithm, iblock, pb_type, pb, pb->mode)) {
                                        continue;
                                }
                                set_pb_mode(pb, 0, 0); /* default mode is to use mode 1 */
                                set_pb_mode(pb, i, 1);
                                pb->child_pbs = my_calloc(pb_type->modes[i].num_pb_type_children, sizeof(t_pb *));

                                for(j = 0; j < pb_type->modes[i].num_pb_type_children; j++) {
                                        /* allocate space for children if first time allocating space */
                                        pb->child_pbs[j] = my_calloc(pb_type->modes[i].pb_type_children[j].num_pb, sizeof(t_pb));
                                        for(k = 0; k < pb_type->modes[i].pb_type_children[j].num_pb; k++) {
                                                pb->child_pbs[j][k].parent_pb = pb;
                                                alloc_and_load_pb_stats(&pb->child_pbs[j][k], max_models, max_cluster_size, max_primitive_inputs);
                                        }
                                }
                                for(j = 0; j < pb_type->modes[i].num_pb_type_children && block_pack_status != BLK_PASSED; j++) {
                                        for(k = 0; k < pb_type->modes[i].pb_type_children[j].num_pb && block_pack_status != BLK_PASSED; k++) {
                                                block_pack_status = alloc_and_load_pb(packer_algorithm, &pb_graph_node->child_pb_graph_nodes[i][j][k], iblock, &pb->child_pbs[j][k], max_models, max_cluster_size, max_primitive_inputs);
                                                if(block_pack_status == BLK_FAILED_FEASIBLE) {
                                                        /* sibling blocks differ only in interconnect, 
                                                          if feasibility fails then it is failing on something other than interconnect
                                                          therefore, no point trying the same thing for siblings */
                                                        break;
                                                }
                                        }
                                }
                                if(block_pack_status == BLK_PASSED) {
                                        pb->name = my_strdup(logical_block[iblock].name);
                                } else {
                                        set_pb_mode(pb, i, 0); /* default mode is to use mode 1 */
                                        set_pb_mode(pb, 0, 1);
                                        for(j = 0; j < pb_type->modes[i].num_pb_type_children; j++) {
                                                if(pb->child_pbs[j] != NULL) {
                                                        for(k = 0; k < pb_type->modes[i].pb_type_children[j].num_pb; k++) {
                                                                free_pb_stats(pb->child_pbs[j][k].pb_stats, max_models);
                                                        }
                                                        free(pb->child_pbs[j]);
                                                }
                                        }
                                        free(pb->child_pbs);
                                        pb->child_pbs = NULL;
                                }
                        }
                } else {
                        /* 
                         * Another block has been allocated inside so must select placement carefully 
                         */
                        i = pb->mode;
                        if(!models_feasible(packer_algorithm, iblock, pb_type, pb, pb->mode)) {
                                block_pack_status = BLK_FAILED_FEASIBLE;
                        } else {
                                for(j = 0; j < pb_type->modes[i].num_pb_type_children && block_pack_status != BLK_PASSED; j++) {
                                        for(k = 0; k < pb_type->modes[i].pb_type_children[j].num_pb && block_pack_status != BLK_PASSED; k++) {
                                                /* Simple heuristic: assume that any packed cluster is well-packed, try to pack into new child only */
                                                /* Brute force heuristic: traverse whole tree always */
                                                if(pb->child_pbs[j][k].name == NULL) {
                                                        block_pack_status = alloc_and_load_pb(packer_algorithm, &pb_graph_node->child_pb_graph_nodes[i][j][k], iblock, &pb->child_pbs[j][k], max_models, max_cluster_size, max_primitive_inputs);
                                                } else if (packer_algorithm == PACK_BRUTE_FORCE && pb_type->modes[i].pb_type_children[j].num_modes != 0) {
                                                        block_pack_status = alloc_and_load_pb(packer_algorithm, &pb_graph_node->child_pb_graph_nodes[i][j][k], iblock, &pb->child_pbs[j][k], max_models, max_cluster_size, max_primitive_inputs);
                                                }
                                                if(block_pack_status == BLK_FAILED_FEASIBLE && packer_algorithm != PACK_BRUTE_FORCE) {
                                                        /* Children blocks differ only in routing, don't continue if feasibility fails 
                                                           Brute force algorithm may have just ran into a node that was full, therefore it should not break out
                                                        */
                                                        break;
                                                }
                                        }
                                }
                        }
                }
        }

        return block_pack_status;
}

/** This function is called when the connectiongain values on the vpack_net
 * inet require updating.   */
static void update_connection_gain_values (int inet, int clustered_block, t_pb *cur_pb, enum e_net_relation_to_clustered_block net_relation_to_clustered_block) {

  int iblk, ipin;
  int clb_index;
  int num_internal_connections, num_open_connections, num_stuck_connections;

  num_internal_connections = num_open_connections = num_stuck_connections = 0;

  clb_index = logical_block[clustered_block].clb_index;

  /* may wish to speed things up by ignoring clock nets since they are high fanout */
  
  for (ipin=0;ipin<=vpack_net[inet].num_sinks;ipin++) {
        iblk = vpack_net[inet].node_block[ipin];
        if (logical_block[iblk].clb_index == clb_index && is_logical_blk_in_pb(iblk, logical_block[clustered_block].pb)) {
                num_internal_connections++;
        } else if (logical_block[iblk].clb_index == OPEN) {
                num_open_connections++;
        } else {
                num_stuck_connections++;
        }
  }

  if (net_relation_to_clustered_block==OUTPUT){
    for (ipin=1;ipin<=vpack_net[inet].num_sinks;ipin++) {
                iblk = vpack_net[inet].node_block[ipin];
                if (logical_block[iblk].clb_index == NO_CLUSTER) {
                        /* Only works if net has one connection to block, TODO: handle case where net has multi-connection to block */
                        if(num_internal_connections > 1) {
                                cur_pb->pb_stats.connectiongain[iblk] -= 1 /(float)(vpack_net[inet].num_sinks - (num_internal_connections - 1) + 1 + 1 * num_stuck_connections);
                        }
                        cur_pb->pb_stats.connectiongain[iblk] += 1 /(float)(vpack_net[inet].num_sinks - num_internal_connections + 1 + 1 * num_stuck_connections);
                }
    }
  }

  if(net_relation_to_clustered_block==INPUT){ 
    /*Calculate the connectiongain for the logical_block which is driving *
     *the vpack_net that is an input to a logical_block in the cluster */

          iblk=vpack_net[inet].node_block[0];
    if (logical_block[iblk].clb_index == NO_CLUSTER) {
                if(num_internal_connections > 1) {
                        cur_pb->pb_stats.connectiongain[iblk] -= 1 / (float)(vpack_net[inet].num_sinks - (num_internal_connections - 1) + 1 + 1 * num_stuck_connections);
                }
                cur_pb->pb_stats.connectiongain[iblk] += 1 / (float)(vpack_net[inet].num_sinks - num_internal_connections + 1 + 1 * num_stuck_connections);
    }
  }
}
/*****************************************/
/** This function is called when the length_gain values on the vpack_net
 * inet requires updating.   
 */
static void update_length_gain_values (int inet, int clustered_block, t_pb *cur_pb,
                                           enum  e_net_relation_to_clustered_block net_relation_to_clustered_block) {

  float lengain;
  int newblk, ifirst;
  int iblk, ipin;

/* Check if this vpack_net lists its driving logical_block twice.  If so, avoid  *
 * double counting this logical_block by skipping the first (driving) pin. */
   if (net_output_feeds_driving_block_input[inet] == FALSE) 
    ifirst = 0;
  else
    ifirst = 1;

  if (net_relation_to_clustered_block == OUTPUT && !vpack_net[inet].is_global){
          for (ipin=ifirst; ipin <= vpack_net[inet].num_sinks; ipin++) {
                iblk = vpack_net[inet].node_block[ipin];
                if (logical_block[iblk].clb_index == NO_CLUSTER) {
                        lengain=net_pin_backward_criticality[inet][ipin];
                        if (lengain>cur_pb->pb_stats.lengthgain[iblk])
                                cur_pb->pb_stats.lengthgain[iblk]=lengain;
                }
          }
  }

  if(net_relation_to_clustered_block == INPUT && !vpack_net[inet].is_global){ 
    /*Calculate the length gain for the logical_block which is driving *
     *the vpack_net that is an input to a logical_block in the cluster */
          newblk = vpack_net[inet].node_block[0];               
          if (logical_block[newblk].clb_index == NO_CLUSTER) {
                  for (ipin=1; ipin <= vpack_net[inet].num_sinks; ipin++) {
                        lengain=net_pin_forward_criticality[inet][ipin];
                        if (lengain>cur_pb->pb_stats.lengthgain[newblk])
                                cur_pb->pb_stats.lengthgain[newblk]=lengain;
                        
                  }
          }
  }
}
/*****************************************/
/** Updates the marked data structures, and if gain_flag is GAIN,  
 * the gain when a logic logical_block is added to a cluster.  The        
 * sharinggain is the number of inputs that a logical_block shares with   
 * blocks that are already in the cluster. Hillgain is the        
 * reduction in number of pins-required by adding a logical_block to the  
 * cluster. The lengthgain is the criticality of the most critical
 * vpack_net between this logical_block and a logical_block in the cluster.             
 */
static void mark_and_update_partial_gain (int inet, 
       enum e_gain_update gain_flag, int clustered_block, int port_on_clustered_block, int pin_on_clustered_block,
       boolean timing_driven, boolean connection_driven, enum e_net_relation_to_clustered_block net_relation_to_clustered_block) {


 int iblk, ipin, ifirst;
 t_pb *cur_pb;

 cur_pb = logical_block[clustered_block].pb->parent_pb;

 while(cur_pb) {
         /* Mark vpack_net as being visited, if necessary. */

         if (cur_pb->pb_stats.num_pins_of_net_in_pb[inet] == 0) {
                cur_pb->pb_stats.marked_nets[cur_pb->pb_stats.num_marked_nets] = inet;
                cur_pb->pb_stats.num_marked_nets++;
         }

        /* Update gains of affected blocks. */

         if (gain_flag == GAIN) {

        /* Check if this vpack_net lists its driving logical_block twice.  If so, avoid  *
         * double counting this logical_block by skipping the first (driving) pin. */
          
                if (net_output_feeds_driving_block_input[inet] == 0) 
                   ifirst = 0;
                else
                   ifirst = 1;
               
           if (cur_pb->pb_stats.num_pins_of_net_in_pb[inet]==0) {
                   for (ipin=ifirst;ipin<=vpack_net[inet].num_sinks;ipin++) {
                           iblk = vpack_net[inet].node_block[ipin];
                           if (logical_block[iblk].clb_index == NO_CLUSTER) {

                 if (cur_pb->pb_stats.sharinggain[iblk] == NOT_VALID) {
                   cur_pb->pb_stats.marked_blocks[cur_pb->pb_stats.num_marked_blocks] = iblk;
                   cur_pb->pb_stats.num_marked_blocks++;
                   cur_pb->pb_stats.sharinggain[iblk]=1;
                   cur_pb->pb_stats.hillgain[iblk] = 1 - num_ext_inputs (iblk);
                 }
                 else {
                   cur_pb->pb_stats.sharinggain[iblk]++;
                   cur_pb->pb_stats.hillgain[iblk]++;
                 }
                   }
                 }
           }

           if (connection_driven) {
                   update_connection_gain_values(inet, clustered_block, cur_pb, net_relation_to_clustered_block);                  
           }
           
           if (timing_driven) {
                 update_length_gain_values(inet, clustered_block, cur_pb, net_relation_to_clustered_block);
           }           
         }
            
         cur_pb->pb_stats.num_pins_of_net_in_pb[inet]++;
         cur_pb = cur_pb->parent_pb;
 }
}

/*****************************************/
/** Updates the total  gain array to reflect the desired tradeoff between
 * input sharing (sharinggain) and path_length minimization (lengthgain)
 */
static void update_total_gain(float alpha, float beta, boolean timing_driven, boolean 
                              connection_driven, boolean global_clocks, t_pb *pb){

  int i, iblk, j, k;
  t_pb * cur_pb;
  int num_input_pins, num_output_pins;
  int num_used_input_pins, num_used_output_pins;
  t_model_ports *port;

  cur_pb = pb;
  while(cur_pb) {

          for (i=0;i<cur_pb->pb_stats.num_marked_blocks;i++) {
                  iblk=cur_pb->pb_stats.marked_blocks[i];

                  /* Todo: This was used to explore different normalization options, can be made more efficient once we decide on which one to use*/
                  num_input_pins = 0;
                  port = logical_block[iblk].model->inputs;
                  j =0;
                  num_used_input_pins = 0;
                  while(port) {
                           num_input_pins += port->size;
                           if(!port->is_clock) {
                                   for(k = 0; k < port->size; k++) {
                                           if(logical_block[iblk].input_nets[j][k] != OPEN) {
                                                        num_used_input_pins++;
                                           }
                                   }
                                   j++;
                           }
                           port = port->next;
                   }
                  if(num_input_pins == 0) {
                           num_input_pins = 1;
                  }
                  
                   num_used_output_pins = 0;
                   j = 0;
                   num_output_pins = 0;
                   port = logical_block[iblk].model->outputs;
                   while(port) {
                           num_output_pins += port->size;
                                for(k = 0; k < port->size; k++) {
                                   if(logical_block[iblk].output_nets[j][k] != OPEN) {
                                                num_used_output_pins++;
                                   }
                                }
                           port = port->next;
                           j++;
                   }
                   /* end todo */
                          
              /* Calculate area-only cost function */
                  if (connection_driven) {
                        /*try to absorb as many connections as possible*/
                           /* TODO: change back to used pins when done testing */
                           cur_pb->pb_stats.gain[iblk] = ((1-beta)*(float)cur_pb->pb_stats.sharinggain[iblk] + beta*(float)cur_pb->pb_stats.connectiongain[iblk])/(num_input_pins + num_output_pins);
                           /* cur_pb->pb_stats.gain[iblk] = ((1-beta)*(float)cur_pb->pb_stats.sharinggain[iblk] + beta*(float)cur_pb->pb_stats.connectiongain[iblk])/(num_used_input_pins + num_used_output_pins); */
                  } else {
                          /*cur_pb->pb_stats.gain[iblk] = ((float)cur_pb->pb_stats.sharinggain[iblk])/(num_used_input_pins + num_used_output_pins); */
                          cur_pb->pb_stats.gain[iblk] = ((float)cur_pb->pb_stats.sharinggain[iblk])/(num_input_pins + num_output_pins);
                  }

                  /* Add in timing driven cost into cost function */
                  if (timing_driven) {
                          cur_pb->pb_stats.gain[iblk] = alpha*cur_pb->pb_stats.lengthgain[iblk] + (1.0-alpha)*(float)cur_pb->pb_stats.gain[iblk];
                  }
          }
          cur_pb = cur_pb->parent_pb;
  }
}

/*****************************************/
/** Updates cluster stats such as gain, used pins, and clock structures.  */
static void update_cluster_stats (      INP int new_blk,
                                                                        INP int clb_index,
                                                                        INP boolean *is_clock, 
                                                                        INP boolean global_clocks, 
                                                                        INP float alpha, 
                                                                        INP float beta,
                                                                        INP boolean timing_driven, 
                                                                        INP boolean connection_driven) {


 int i, ipin, inet, depth;
 t_model_ports *port;
 t_pb *cur_pb;

 /* TODO: what a scary comment from Vaughn, we'll have to watch out for this causing problems */
/* Output can be open so the check is necessary.  I don't change  *
 * the gain for clock outputs when clocks are globally distributed  *
 * because I assume there is no real need to pack similarly clocked *
 * FFs together then.  Note that by updating the gain when the      *
 * clock driver is placed in a cluster implies that the output of   *
 * LUTs can be connected to clock inputs internally.  Probably not  *
 * true, but it doesn't make much difference, since it will still   *
 * make local routing of this clock very short, and none of my      *
 * benchmarks actually generate local clocks (all come from pads).  */


 logical_block[new_blk].clb_index = clb_index;

 cur_pb = logical_block[new_blk].pb->parent_pb;
 while(cur_pb) {
        depth = cur_pb->pb_graph_node->pb_type->depth;
        /* reset list of feasible blocks */
        for (i=0;i<cur_pb->pb_stats.num_marked_models;i++){ 
                cur_pb->pb_stats.num_feasible_blocks[i] = 0;
        }
        cur_pb->pb_stats.num_marked_models = 0;
        cur_pb->pb_stats.cur_marked_model = NOT_VALID;
        
        /* determine valid pins */
        if (cur_pb->pb_stats.inputs_avail == NOT_VALID)
                cur_pb->pb_stats.inputs_avail = cur_pb->pb_graph_node->pb_type->num_input_pins;

        if (cur_pb->pb_stats.outputs_avail == NOT_VALID)
                cur_pb->pb_stats.outputs_avail = cur_pb->pb_graph_node->pb_type->num_output_pins;

        if (cur_pb->pb_stats.clocks_avail == NOT_VALID)
                cur_pb->pb_stats.clocks_avail = cur_pb->pb_graph_node->pb_type->num_clock_pins;

        cur_pb = cur_pb->parent_pb;
 }  

 port = logical_block[new_blk].model->outputs;
 while(port) {
         for(ipin = 0; ipin < port->size; ipin++) {
                 inet = logical_block[new_blk].output_nets[port->index][ipin];    /* Output pin first. */
                 if (inet != OPEN) {
                        if (!is_clock[inet] || !global_clocks) 
                                mark_and_update_partial_gain (inet, GAIN, new_blk, port->index, ipin, 
                                                        timing_driven, connection_driven, OUTPUT);
                        else
                                mark_and_update_partial_gain (inet, NO_GAIN, new_blk, port->index, ipin, 
                                                        timing_driven, connection_driven, OUTPUT);

                        cur_pb = logical_block[new_blk].pb->parent_pb;
                        while(cur_pb) {
                                depth = cur_pb->pb_graph_node->pb_type->depth;
                                cur_pb->pb_stats.net_output_in_pb[inet] = TRUE;

                                if (cur_pb->pb_stats.num_pins_of_net_in_pb[inet] > 1 && !is_clock[inet])
                                        cur_pb->pb_stats.inputs_avail++;

                                if (cur_pb->pb_stats.num_pins_of_net_in_pb[inet] + 
                                        net_output_feeds_driving_block_input[inet] != vpack_net[inet].num_sinks + 1) {
                                                cur_pb->pb_stats.outputs_avail--;
                                } else if (hack_frac_lut_no_legality) {
                                        if(depth > 1)
                                                cur_pb->pb_stats.outputs_avail--; /* frac lut cannot absorb pins after the top two levels  */
                                }

                                cur_pb = cur_pb->parent_pb;
                        }
                 }
         }
         port = port->next;
 }
 port = logical_block[new_blk].model->inputs;
 while(port) {
         if(port->is_clock) {
                 port = port->next;
                 continue;
         }
         for (ipin=0; ipin<port->size; ipin++) {   /*  VPACK_BLOCK input pins. */

                 inet = logical_block[new_blk].input_nets[port->index][ipin];
                if (inet != OPEN) {
                   mark_and_update_partial_gain (inet, GAIN, new_blk, port->index, ipin, timing_driven, connection_driven, INPUT);
                   cur_pb = logical_block[new_blk].pb->parent_pb;
                   while(cur_pb) {
                                depth = cur_pb->pb_graph_node->pb_type->depth;
                                
                                if (cur_pb->pb_stats.num_pins_of_net_in_pb[inet] == 1) 
                                        cur_pb->pb_stats.inputs_avail--;

                                assert(cur_pb->pb_stats.inputs_avail >= 0);
                                if (cur_pb->pb_stats.net_output_in_pb[inet] &&
                                        cur_pb->pb_stats.num_pins_of_net_in_pb[inet] == vpack_net[inet].num_sinks + 1) {
                                                cur_pb->pb_stats.outputs_avail++;
                                                if (hack_frac_lut_no_legality && depth > 1)
                                                        cur_pb->pb_stats.outputs_avail--; /* frac lut cannot absorb pins after the top two levels */
                                }

                                cur_pb = cur_pb->parent_pb;
                        }
                }
         }
         port = port->next;
 }


/* Note:  The code below ONLY WORKS when nets that go to clock inputs *
 * NEVER go to the input of a VPACK_COMB.  It doesn't really make electrical *
 * sense for that to happen, and I check this in the check_clocks     *
 * function.  Don't disable that sanity check.                        */
 inet = logical_block[new_blk].clock_net;    /* Clock input pin. */
 if (inet != OPEN) {
         if (global_clocks) 
       mark_and_update_partial_gain (inet, NO_GAIN, new_blk, 0, 
                                     0, timing_driven,
                                     connection_driven, INPUT);
    else
       mark_and_update_partial_gain (inet, GAIN, new_blk, 0, 
                                     0, timing_driven,
                                     connection_driven, INPUT);


        cur_pb = logical_block[new_blk].pb->parent_pb;
   while(cur_pb) {
                depth = cur_pb->pb_graph_node->pb_type->depth;
                
                if (cur_pb->pb_stats.num_pins_of_net_in_pb[inet] == 1) {
                        cur_pb->pb_stats.clocks_avail--;
                }
                else if (cur_pb->pb_stats.num_pins_of_net_in_pb[inet] == 2 && cur_pb->pb_stats.net_output_in_pb[inet]) {
                        cur_pb->pb_stats.clocks_avail--;
                }
        /* Note: unlike inputs, I'm currently assuming there is no internal *
         * connection in a cluster from VPACK_LUT outputs to clock inputs.        */
                
                cur_pb = cur_pb->parent_pb;
        }
 }

 update_total_gain(alpha, beta, timing_driven, connection_driven, global_clocks, logical_block[new_blk].pb->parent_pb);

}


/** Given a starting seed block, start_new_cluster determines the next cluster type to use. 
 *   It expands the FPGA if it cannot find a legal cluster for the logical block
 */
static void start_new_cluster(INP enum e_packer_algorithm packer_algorithm,
                                                          INP const t_arch * arch,
                                                          INOUTP t_block *new_cluster,
                                                            INP int clb_index,
                                                                INP int istart,
                                                                INP float aspect,
                                                                INOUTP int *num_used_instances_type, 
                                                                INOUTP int *num_instances_type,
                                                                INP int num_models,
                                                                INP int max_cluster_size,
                                                                INP int max_primitive_inputs) {
 int i, j;
 boolean success;

 assert(new_cluster->name == NULL); /* Check if this cluster is really empty */

 /* Allocate a dummy initial cluster and load a logical block as a seed and check if it is legal */
 new_cluster->name = my_malloc(strlen(logical_block[istart].name) + 4);
 sprintf(new_cluster->name, "cb.%s", logical_block[istart].name);
 new_cluster->nets = NULL;
 new_cluster->type = NULL;
 new_cluster->pb = NULL;
 new_cluster->x = UNDEFINED;
 new_cluster->y = UNDEFINED;
 new_cluster->z = UNDEFINED;

 success = FALSE;

 while(!success) {
         for(i = 0; i < num_types; i++) {
                if(num_used_instances_type[i] < num_instances_type[i]) {
                        new_cluster->type = &type_descriptors[i];
                        if(new_cluster->type == EMPTY_TYPE) {
                                continue;
                        }
                        new_cluster->pb = my_calloc(1, sizeof(t_pb));
                        alloc_and_load_pb_stats(new_cluster->pb, num_models, max_cluster_size, max_primitive_inputs);
                        new_cluster->pb->parent_pb = NULL;
                        new_cluster->pb->pb_graph_node = new_cluster->type->pb_graph_head;
                        
                        alloc_and_load_legalizer_for_cluster(new_cluster, clb_index, arch);
                        for(j = 0; j < new_cluster->type->pb_graph_head->pb_type->num_modes && !success; j++) {
                                new_cluster->pb->mode = j;
                                if(models_feasible(packer_algorithm, istart, new_cluster->pb->pb_graph_node->pb_type, new_cluster->pb, new_cluster->pb->mode)) {
                                        success = (BLK_PASSED == alloc_and_load_pb(packer_algorithm, new_cluster->type->pb_graph_head, istart, new_cluster->pb, num_models, max_cluster_size, max_primitive_inputs)); 
                                }
                        }                        
                        if(success) {
                                
                                if(hack_frac_lut_no_legality) {
                                        logical_block[istart].clb_index = clb_index;
                                }
                                /* TODO: For now, just grab any working cluster, in the future, heuristic needed to grab best complex block based on supply and demand */
                                break;
                        } else {
                                free_legalizer_for_cluster(new_cluster);
                                free_pb_stats(new_cluster->pb->pb_stats, num_models);
                                free(new_cluster->pb);
                        }                       
                }
         }

         /* Expand FPGA size and recalculate number of available cluster types*/
         if (!success) {
                if(aspect >= 1.0)
                {
                    ny++;
                    nx = nint(ny * aspect);
                }
            else
                {
                    nx++;
                    ny = nint(nx / aspect);
                }
                printf("Not enough resources expand FPGA size to x = %d y = %d\n", nx, ny);
                if((nx > MAX_SHORT) || (ny > MAX_SHORT)) {
                        printf("Circuit cannot pack into architecture, architecture size (nx = %d, ny = %d) exceeds packer range.\n", nx, ny);
                        exit(1);
                }
                alloc_and_load_grid(num_instances_type);
                freeGrid();
         }
 }
 num_used_instances_type[new_cluster->type->index]++;
}


/*****************************************/
/** Checks if adding iblk to the currently open cluster would violate 
 * the cluster input and clock pin limitations.  Returns TRUE if     
 * iblk can be added to the cluster, FALSE otherwise.                
 */
static boolean inputs_outputs_models_and_clocks_feasible (INP enum e_packer_algorithm packer_algorithm, int iblk, boolean *is_clock, t_pb *cur_pb) {

 int ipin, inet, output_net;
 t_model_ports *port;
 t_pb* temp_pb;
 boolean inputs_feasible = TRUE;
 
 int inputs_avail;
 
 temp_pb = cur_pb;
 while(temp_pb && inputs_feasible) {
         inputs_avail = temp_pb->pb_stats.inputs_avail;
         if(inputs_avail == NOT_VALID) {
                 inputs_avail = temp_pb->pb_graph_node->pb_type->num_input_pins;
         }

         port = logical_block[iblk].model->outputs;
         while(port) {
                /* Outputs that connect to internal blocks free up an input pin. */
                 for(ipin = 0; ipin < port->size; ipin++) {
                         output_net = logical_block[iblk].output_nets[port->index][ipin];
                         if (output_net != OPEN && temp_pb->pb_stats.num_pins_of_net_in_pb[output_net] != 0 && !is_clock[output_net])
                                inputs_avail++;
                 }
                 port = port->next;
         }

         port = logical_block[iblk].model->inputs;
         while(port) {
                if(!port->is_clock) {
                /* Inputs that do not connect to an output pin of an internal block (including this one) require an input pin. */
                 for (ipin = 0; ipin < port->size; ipin++) {
                        inet = logical_block[iblk].input_nets[port->index][ipin];
                        if (inet != OPEN && temp_pb->pb_stats.num_pins_of_net_in_pb[inet] == 0) {
                                if(net_output_feeds_driving_block_input[inet] == 0) {
                                        inputs_avail--;
                                } 
                        }
                 }
                }
                port = port->next;
         }
         inputs_feasible = (inputs_avail >= 0);
         temp_pb = temp_pb->parent_pb;
 }
 if (outputs_clocks_and_models_feasible (packer_algorithm, iblk, is_clock, cur_pb) == FALSE) 
    return (FALSE); 

 if (inputs_feasible) 
    return (TRUE);
 else
    return (FALSE);
}

/*****************************************/
/** This routine populates a list of feasible blocks outside the cluster then returns the best one for the list    
 * not currently in a cluster and satisfies the feasibility     
 * function passed in as is_feasible.  If there are no feasible 
 * blocks it returns NO_CLUSTER.                                
 */
static int get_highest_gain_logical_block ( INP enum e_packer_algorithm packer_algorithm,
                                                                                   INOUTP t_pb *cur_pb,
                                                                                                INP boolean *is_clock, 
                                                                                                INP boolean (*is_feasible) (enum e_packer_algorithm packer_algorithm, int iblk, boolean *is_clock, t_pb *cur_pb), 
                                                                                                INP enum e_gain_type gain_mode) {

        int i, j, iblk, index;
        int best_hillgain;
        float best_gain;

        int best_block;

        best_gain = (float)NOT_VALID + 1.0; 
        best_hillgain=NOT_VALID+1;

        best_block = NO_CLUSTER;

        if(cur_pb->pb_stats.cur_marked_model == NOT_VALID) {
                /* Divide into two cases for speed only. */
                /* Typical case:  not too many blocks have been marked. */

                if (cur_pb->pb_stats.num_marked_blocks < num_logical_blocks / MARKED_FRAC) {
                        for (i=0;i<cur_pb->pb_stats.num_marked_blocks;i++) {
                                iblk = cur_pb->pb_stats.marked_blocks[i];
                                if (logical_block[iblk].clb_index == NO_CLUSTER) {
                                        if (gain_mode != HILL_CLIMBING){
                                                if (is_feasible (packer_algorithm, iblk, is_clock, cur_pb)) {
                                                        add_blk_to_pb_stats_candidates(iblk, cur_pb->pb_stats.gain, cur_pb);
                                                        if (cur_pb->pb_stats.gain[iblk] > best_gain) {
                                                                best_gain = cur_pb->pb_stats.gain[iblk];
                                                                best_block = iblk;
                                                        }
                                                }                                                       
                                        }
                                        else{  /*hill climbing*/
                                                if (is_feasible (packer_algorithm, iblk, is_clock, cur_pb)) {
                                                        add_blk_to_pb_stats_candidates(iblk, cur_pb->pb_stats.hillgain, cur_pb);
                                                        if (cur_pb->pb_stats.hillgain[iblk] > best_hillgain) {
                                                                best_hillgain = cur_pb->pb_stats.hillgain[iblk];
                                                                best_block = iblk;
                                                        }
                                                }                                               
                                        }
                                }
                        }
                }
                else {        /* Some high fanout nets marked lots of blocks. */
                        for (iblk=0;iblk<num_logical_blocks;iblk++) {
                                if (logical_block[iblk].clb_index == NO_CLUSTER) {
                                        if (gain_mode != HILL_CLIMBING){
                                                if (is_feasible (packer_algorithm, iblk, is_clock, cur_pb)) {
                                                        add_blk_to_pb_stats_candidates(iblk, cur_pb->pb_stats.gain, cur_pb);
                                                        if (cur_pb->pb_stats.gain[iblk] > best_gain) {
                                                                best_gain = cur_pb->pb_stats.gain[iblk];
                                                                best_block = iblk;
                                                        }
                                                }       
                                        }
                                        else{ /*hill climbing*/
                                                if (is_feasible (packer_algorithm, iblk, is_clock, cur_pb)) {
                                                        add_blk_to_pb_stats_candidates(iblk, cur_pb->pb_stats.hillgain, cur_pb);
                                                        if (cur_pb->pb_stats.hillgain[iblk] > best_hillgain) {
                                                                best_hillgain = cur_pb->pb_stats.hillgain[iblk];
                                                                best_block = iblk;
                                                        }
                                                }       
                                        }
                                }
                        }
                }

                for(i = 0; i < cur_pb->pb_stats.num_marked_models; i++) {
                        index = cur_pb->pb_stats.feasible_blocks[i][cur_pb->pb_stats.num_feasible_blocks[i] - 1];
                        if (gain_mode != HILL_CLIMBING) {
                                if(cur_pb->pb_stats.gain[index] == cur_pb->pb_stats.gain[best_block]) {
                                        cur_pb->pb_stats.cur_marked_model = i;
                                        break;
                                }
                        } else {
                                if(cur_pb->pb_stats.hillgain[index] == cur_pb->pb_stats.hillgain[best_block]) {
                                        cur_pb->pb_stats.cur_marked_model = i;
                                        break;
                                }
                        }
                }
                assert(cur_pb->pb_stats.num_marked_models == 0 || i < cur_pb->pb_stats.num_marked_models);
        }

        if(cur_pb->pb_stats.cur_marked_model == NOT_VALID) {
                return NO_CLUSTER;
        }

        for(i = 0; i < cur_pb->pb_stats.num_marked_models; i++) {
                for(j = 0; j < cur_pb->pb_stats.num_feasible_blocks[i]; j++) {
                        if(cur_pb->pb_stats.num_feasible_blocks[cur_pb->pb_stats.cur_marked_model] != 0) {
                                cur_pb->pb_stats.num_feasible_blocks[cur_pb->pb_stats.cur_marked_model]--;
                                index = cur_pb->pb_stats.num_feasible_blocks[cur_pb->pb_stats.cur_marked_model];
                                iblk = cur_pb->pb_stats.feasible_blocks[cur_pb->pb_stats.cur_marked_model][index];
                                cur_pb->pb_stats.cur_marked_model = (cur_pb->pb_stats.cur_marked_model + 1) % cur_pb->pb_stats.num_marked_models;
                                return iblk;
                        }
                }
        }

        return NO_CLUSTER;
}


/*****************************************/
/** Finds the vpack block with the the greatest gain that satisifies the      
 * input, clock and capacity constraints of a cluster that are       
 * passed in.  If no suitable vpack block is found it returns NO_CLUSTER.   
 */
static int get_logical_block_for_cluster (      INP enum e_packer_algorithm packer_algorithm,
                                                                                        INOUTP t_pb *cur_pb,
                                                                                        INP boolean *is_clock,
                                                                                        INP boolean allow_unrelated_clustering) {

 int best_block;

 /* If cannot pack into primitive, try packing into cluster */


 best_block = get_highest_gain_logical_block (packer_algorithm, cur_pb, is_clock, inputs_outputs_models_and_clocks_feasible,
                                                 NOT_HILL_CLIMBING);

/* If no blocks have any gain to the current cluster, the code above *
 * will not find anything.  However, another logical_block with no inputs in *
 * common with the cluster may still be inserted into the cluster.   */

 if (allow_unrelated_clustering)
   if (best_block == NO_CLUSTER) 
     best_block = get_free_logical_block_with_most_ext_inputs_for_cluster (packer_algorithm, cur_pb);

 return best_block;
}

/*****************************************/
static void alloc_and_load_cluster_info (INP int num_clb, INOUTP t_block *clb) {

        /* Loads all missing clustering info necessary to complete clustering.  */
        int i, j, i_clb, node_index, ipin, iclass;
        int inport, outport, clockport;
        
        const t_pb_type * pb_type;
        t_pb *pb;
        
        for(i_clb = 0; i_clb < num_clb; i_clb++) {
                rr_node = clb[i_clb].pb->rr_graph;
                pb_type = clb[i_clb].pb->pb_graph_node->pb_type;
                pb = clb[i_clb].pb;

                clb[i_clb].nets = my_malloc(clb[i_clb].type->num_pins * sizeof(int));
                for(i = 0; i < clb[i_clb].type->num_pins; i++) {
                        clb[i_clb].nets[i] = OPEN;
                }

                inport = outport = clockport = 0;       
                ipin = 0;
                /* Assume top-level pb and clb share a one-to-one connection */
                for(i = 0; i < pb_type->num_ports; i++) {
                        if(!pb_type->ports[i].is_clock && pb_type->ports[i].type == IN_PORT) {
                                for(j = 0; j < pb_type->ports[i].num_pins; j++) {
                                        iclass = clb[i_clb].type->pin_class[ipin];
                                        assert(clb[i_clb].type->class_inf[iclass].type == RECEIVER);
                                        assert(!clb[i_clb].type->is_global_pin[ipin]);
                                        node_index = pb->pb_graph_node->input_pins[inport][j].pin_count_in_cluster;
                                        clb[i_clb].nets[ipin] = rr_node[node_index].net_num;
                                        ipin++;
                                }
                                inport++;
                        } else if(pb_type->ports[i].type == OUT_PORT) {
                                for(j = 0; j < pb_type->ports[i].num_pins; j++) {
                                        iclass = clb[i_clb].type->pin_class[ipin];
                                        assert(clb[i_clb].type->class_inf[iclass].type == DRIVER);
                                        node_index = pb->pb_graph_node->output_pins[outport][j].pin_count_in_cluster;
                                        clb[i_clb].nets[ipin] = rr_node[node_index].net_num;
                                        ipin++;
                                }
                                outport++;
                        } else {
                                assert(pb_type->ports[i].is_clock && pb_type->ports[i].type == IN_PORT);
                                for(j = 0; j < pb_type->ports[i].num_pins; j++) {
                                        iclass = clb[i_clb].type->pin_class[ipin];
                                        assert(clb[i_clb].type->class_inf[iclass].type == RECEIVER);
                                        assert(clb[i_clb].type->is_global_pin[ipin]);
                                        node_index = pb->pb_graph_node->clock_pins[clockport][j].pin_count_in_cluster;
                                        clb[i_clb].nets[ipin] = rr_node[node_index].net_num;
                                        ipin++;
                                }
                                clockport++;
                        }
                }
        }
}

/* TODO: Add more error checking, too light */
/*****************************************/
static void check_clustering (int num_clb, t_block *clb, boolean *is_clock) {
        int i;
        t_pb * cur_pb;
        boolean *blocks_checked;

        blocks_checked = my_calloc(num_logical_blocks, sizeof(boolean));

        /* 
         * Check that each logical block connects to one primitive and that the primitive links up to the parent clb
         */
        for(i = 0; i < num_blocks; i++) {
                if(logical_block[i].pb->logical_block != i) {
                        printf(ERRTAG "pb %s does not contain logical block %s but logical block %s #%d links to pb\n",
                                        logical_block[i].pb->name, logical_block[i].name, logical_block[i].name, i);
                        exit(1);
                }
                cur_pb = logical_block[i].pb;
                assert(strcmp(cur_pb->name, logical_block[i].name) == 0);
                while(cur_pb->parent_pb) {
                        cur_pb = cur_pb->parent_pb;
                        assert(cur_pb->name);
                }
                if(cur_pb != clb[num_clb].pb) {
                        printf(ERRTAG "CLB %s does not match CLB contained by pb %s\n",
                                cur_pb->name, logical_block[i].pb->name);
                        exit(1);
                }
        }

        /* Check that I do not have spurious links in children pbs */
        for(i = 0; i < num_clb; i++) {
                check_cluster_logical_blocks(clb[i].pb, blocks_checked);
        }

        for(i = 0; i < num_logical_blocks; i++) {
                if(blocks_checked[i] == FALSE) {
                        printf(ERRTAG "Logical block %s #%d not found in any cluster\n", logical_block[i].name, i);
                        exit(1);
                }
        }

        free(blocks_checked);
}

/* TODO: May want to check that all logical blocks are actually reached (low priority, nice to have) */
static void check_cluster_logical_blocks (t_pb *pb, boolean *blocks_checked) {
        int i, j;
        const t_pb_type *pb_type;
        boolean has_child;

        has_child = FALSE;
        pb_type = pb->pb_graph_node->pb_type;
        if(pb_type->num_modes == 0) {
                /* primitive */
                if(pb->logical_block != OPEN) {
                        if(blocks_checked[pb->logical_block] != FALSE) {
                                printf(ERRTAG "pb %s contains logical block %s #%d but logical block is already contained in another pb\n",
                                        pb->name, logical_block[pb->logical_block].name, pb->logical_block);
                                exit(1);
                        }
                        blocks_checked[pb->logical_block] = TRUE;
                        if(pb != logical_block[pb->logical_block].pb) {
                                printf(ERRTAG "pb %s contains logical block %s #%d but logical block does not link to pb\n",
                                        pb->name, logical_block[pb->logical_block].name, pb->logical_block);
                                exit(1);
                        }
                }
        } else {
                /* this is a container pb, all container pbs must contain children */
                for(i = 0; i < pb_type->modes[pb->mode].num_pb_type_children; i++) {
                        for(j = 0; j < pb_type->modes[pb->mode].pb_type_children[i].num_pb; j++) {
                                if(pb->child_pbs[i] != NULL) {
                                        if(pb->child_pbs[i][j].name != NULL) {
                                                has_child = TRUE;
                                                check_cluster_logical_blocks(&pb->child_pbs[i][j], blocks_checked);
                                        }
                                }
                        }       
                }
                assert(has_child);
        }
}

/** calculate_timing_information must be called before this, or this function
 * will return garbage 
 */
static int get_most_critical_unclustered_block(void) {
  /*indexofcrit is a global variable that is reset to 0 each time a          *
   *timing analysis is done (reset in  sort_blocks_by_criticality)           */
 
  int critidx, blkidx;

  for (critidx=indexofcrit; critidx<num_logical_blocks; critidx++) {
    blkidx=critindexarray[critidx];
        if (logical_block[blkidx].clb_index == NO_CLUSTER) {
      indexofcrit=critidx+1;
      return(blkidx);
    }
  }

  /*if it makes it to here , there are no more blocks available*/
  return(NO_CLUSTER);
}

static void free_cb (t_pb *pb, int max_models) {
        const t_pb_type * pb_type;
        int i, total_nodes;
        
        pb_type = pb->pb_graph_node->pb_type;
        
        total_nodes = pb->pb_graph_node->total_pb_pins + pb_type->num_input_pins + pb_type->num_output_pins + pb_type->num_clock_pins;

        for(i = 0; i < total_nodes; i++) {
                if(pb->rr_graph[i].edges != NULL) {
                        free(pb->rr_graph[i].edges);
                }
                if(pb->rr_graph[i].switches != NULL) {
                        free(pb->rr_graph[i].switches);
                }
        }
        free(pb->rr_graph);
        free_pb(pb, max_models);
}


static void free_pb (t_pb *pb, int max_models) {
        const t_pb_type * pb_type;
        int i, j, mode;

        pb_type = pb->pb_graph_node->pb_type;
        
        if(pb_type->blif_model == NULL) {
                mode = pb->mode;
                for(i = 0; i < pb_type->modes[mode].num_pb_type_children && pb->child_pbs != NULL; i++) {
                        for(j = 0; j < pb_type->modes[mode].pb_type_children[i].num_pb && pb->child_pbs[i] != NULL; j++) {
                                if(pb->child_pbs[i][j].name != NULL) {
                                        free_pb(&pb->child_pbs[i][j], max_models);
                                }
                        }
                        if(pb->child_pbs[i])
                                free(pb->child_pbs[i]);
                }
                if(pb->child_pbs);
                        free(pb->child_pbs);
                free(pb->name);
        } else {
                /* Primitive */
                if(pb->name)
                        free(pb->name);
                pb->name = NULL;
        }
}

static void free_pb_stats(t_pb_stats pb_stats, int max_models) {
        int i;

        if(pb_stats.gain != NULL) {
                free(pb_stats.gain);
                free(pb_stats.lengthgain);
                free(pb_stats.sharinggain);
                free(pb_stats.hillgain);
                free(pb_stats.connectiongain);
                free(pb_stats.num_feasible_blocks);

                for(i = 0; i < max_models; i ++) {
                        free(pb_stats.feasible_blocks[i]);
                }
                free(pb_stats.feasible_blocks);

                free(pb_stats.num_pins_of_net_in_pb);
                free(pb_stats.net_output_in_pb);
                free(pb_stats.marked_nets);
                free(pb_stats.marked_blocks);   

                pb_stats.gain = NULL;           
        }
}