prepack.h File Reference

#include "arch_types.h"
#include "util.h"

Include dependency graph for prepack.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
t_pack_patterns *	alloc_and_load_pack_patterns (OUTP int *num_packing_patterns)
void	free_list_of_pack_patterns (INP t_pack_patterns *list_of_pack_patterns, INP int num_packing_patterns)
t_pack_molecule *	alloc_and_load_pack_molecules (INP t_pack_patterns *list_of_pack_patterns, INP int num_packing_patterns, OUTP int *num_pack_molecule)

Function Documentation

t_pack_molecule* alloc_and_load_pack_molecules	(	INP t_pack_patterns *	list_of_pack_patterns,
		INP int	num_packing_patterns,
		OUTP int *	num_pack_molecule
	)

Pre-pack atoms in netlist to molecules

1. Single atoms are by definition a molecule.
2. Forced pack molecules are groupings of atoms that matches a t_pack_pattern definition.
3. Chained molecules are molecules that follow a carry-chain style pattern: ie. a single linear chain that can be split across multiple complex blocks

Definition at line 756 of file prepack.c.

                                                                   {
    int i, j, best_pattern;
    t_pack_molecule *list_of_molecules_head;
    t_pack_molecule *cur_molecule;
    boolean *is_used;

    is_used = (boolean*)my_calloc(num_packing_patterns, sizeof(boolean));

    cur_molecule = list_of_molecules_head = NULL;

    /* Find forced pack patterns */
    /* Simplifying assumptions: Each atom can map to at most one molecule, use first-fit mapping based on priority of pattern */
    /* TODO: Need to investigate better mapping strategies than first-fit */
    for (i = 0; i < num_packing_patterns; i++) {
        best_pattern = 0;
        for(j = 1; j < num_packing_patterns; j++) {
            if(is_used[best_pattern]) {
                best_pattern = j;
            } else if (is_used[j] == FALSE && compare_pack_pattern(&list_of_pack_patterns[j], &list_of_pack_patterns[best_pattern]) == 1) {
                best_pattern = j;
            }
        }
        assert(is_used[best_pattern] == FALSE);
        is_used[best_pattern] = TRUE;
        for (j = 0; j < num_logical_blocks; j++) {
            cur_molecule = try_create_molecule(list_of_pack_patterns, best_pattern, j);
            if (cur_molecule != NULL) {
                cur_molecule->next = list_of_molecules_head;
                /* In the event of multiple molecules with the same logical block pattern, bias to use the molecule with less costly physical resources first */
                /* TODO: Need to normalize magical number 100 */
                cur_molecule->base_gain = cur_molecule->num_blocks
                        - (cur_molecule->pack_pattern->base_cost / 100);
                list_of_molecules_head = cur_molecule;
                if(logical_block[j].packed_molecules == NULL || logical_block[j].packed_molecules->data_vptr != cur_molecule) {
                    /* molecule did not cover current atom (possibly because molecule created is part of a long chain that extends past multiple logic blocks), try again */
                    j--;
                }
            }
        }
    }
    free(is_used);

    /* List all logical blocks as a molecule for blocks that do not belong to any molecules.
     This allows the packer to be consistent as it now packs molecules only instead of atoms and molecules

     If a block belongs to a molecule, then carrying the single atoms around can make the packing problem
     more difficult because now it needs to consider splitting molecules.
     */
    for (i = 0; i < num_logical_blocks; i++) {
        logical_block[i].expected_lowest_cost_primitive = get_expected_lowest_cost_primitive_for_logical_block(i);
        if (logical_block[i].packed_molecules == NULL) {
            cur_molecule = (t_pack_molecule*) my_calloc(1,
                    sizeof(t_pack_molecule));
            cur_molecule->valid = TRUE;
            cur_molecule->type = MOLECULE_SINGLE_ATOM;
            cur_molecule->num_blocks = 1;
            cur_molecule->root = 0;
            cur_molecule->num_ext_inputs = logical_block[i].used_input_pins;
            cur_molecule->chain_pattern = NULL;
            cur_molecule->pack_pattern = NULL;
            cur_molecule->logical_block_ptrs = (t_logical_block**) my_malloc(
                    1 * sizeof(t_logical_block*));
            cur_molecule->logical_block_ptrs[0] = &logical_block[i];
            cur_molecule->next = list_of_molecules_head;
            cur_molecule->base_gain = 1;
            list_of_molecules_head = cur_molecule;

            logical_block[i].packed_molecules = (struct s_linked_vptr*) my_calloc(1,
                    sizeof(struct s_linked_vptr));
            logical_block[i].packed_molecules->data_vptr = (void*) cur_molecule;
        }
    }

    if (getEchoEnabled() && isEchoFileEnabled(E_ECHO_PRE_PACKING_MOLECULES_AND_PATTERNS)) {
        print_pack_molecules(getEchoFileName(E_ECHO_PRE_PACKING_MOLECULES_AND_PATTERNS),
                list_of_pack_patterns, num_packing_patterns,
                list_of_molecules_head);
    }

    return list_of_molecules_head;
}

Here is the call graph for this function:

Here is the caller graph for this function:

t_pack_patterns* alloc_and_load_pack_patterns

(

OUTP int *

num_packing_patterns

)

Find all packing patterns in architecture [0..num_packing_patterns-1]

Limitations: Currently assumes that forced pack nets must be single-fanout as this covers all the reasonable architectures we wanted. More complicated structures should probably be handled either downstream (general packing) or upstream (in tech mapping) If this limitation is too constraining, code is designed so that this limitation can be removed

Definition at line 75 of file prepack.c.

                                                                              {
    int i, j, ncount, k;
    int L_num_blocks;
    struct s_hash **nhash;
    t_pack_patterns *list_of_packing_patterns;
    t_pb_graph_edge *expansion_edge;

    /* alloc and initialize array of packing patterns based on architecture complex blocks */
    nhash = alloc_hash_table();
    ncount = 0;
    for (i = 0; i < num_types; i++) {
        discover_pattern_names_in_pb_graph_node(
                type_descriptors[i].pb_graph_head, nhash, &ncount);
    }

    list_of_packing_patterns = alloc_and_init_pattern_list_from_hash(ncount,
            nhash);

    /* load packing patterns by traversing the edges to find edges belonging to pattern */
    for (i = 0; i < ncount; i++) {
        for (j = 0; j < num_types; j++) {
            expansion_edge = find_expansion_edge_of_pattern(i,
                    type_descriptors[j].pb_graph_head);
            if (expansion_edge == NULL) {
                continue;
            }
            L_num_blocks = 0;
            list_of_packing_patterns[i].base_cost = 0;
            backward_expand_pack_pattern_from_edge(expansion_edge,
                    list_of_packing_patterns, i, NULL, NULL, &L_num_blocks);
            list_of_packing_patterns[i].num_blocks = L_num_blocks;

            /* Default settings: A section of a netlist must match all blocks in a pack pattern before it can be made a molecule except for carry-chains.  For carry-chains, since carry-chains are typically
            quite flexible in terms of size, it is optional whether or not an atom in a netlist matches any particular block inside the chain */
            list_of_packing_patterns[i].is_block_optional = (boolean*) my_malloc(L_num_blocks * sizeof(boolean));
            for(k = 0; k < L_num_blocks; k++) {
                list_of_packing_patterns[i].is_block_optional[k] = FALSE;
                if(list_of_packing_patterns[i].is_chain && list_of_packing_patterns[i].root_block->block_id != k) {
                    list_of_packing_patterns[i].is_block_optional[k] = TRUE;
                }
            }
            break;
        }
    }

    free_hash_table(nhash);

    *num_packing_patterns = ncount;

    return list_of_packing_patterns;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void free_list_of_pack_patterns	(	INP t_pack_patterns *	list_of_pack_patterns,
		INP int	num_packing_patterns
	)

Definition at line 319 of file prepack.c.

                                                                                                          {
    int i, j, num_pack_pattern_blocks;
    t_pack_pattern_block **pattern_block_list;
    if (list_of_pack_patterns != NULL) {
        for (i = 0; i < num_packing_patterns; i++) {
            num_pack_pattern_blocks = list_of_pack_patterns[i].num_blocks;
            pattern_block_list = (t_pack_pattern_block **)my_calloc(num_pack_pattern_blocks, sizeof(t_pack_pattern_block *));
            free(list_of_pack_patterns[i].name);
            free(list_of_pack_patterns[i].is_block_optional);
            free_pack_pattern(list_of_pack_patterns[i].root_block, pattern_block_list);
            for (j = 0; j < num_pack_pattern_blocks; j++) {
                free(pattern_block_list[j]);
            }
            free(pattern_block_list);
        }
        free(list_of_pack_patterns);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function: