Other

vtr_expr_eval

This file implements an expression evaluator.

The expression evaluator is capable of performing many operations on given variables, after parsing the expression. The parser goes character by character and identifies the type of char or chars. (e.g bracket, comma, number, operator, variable). The supported operations include addition, subtraction, multiplication, division, finding max, min, gcd, lcm, as well as boolean operators such as &&, ||, ==, >=, <= etc. The result is returned as an int value and operation precedence is taken into account. (e.g given 3-2*4, the result will be -5). This class is also used to parse expressions indicating breakpoints. The breakpoint expressions consist of variable names such as move_num, temp_num, from_block etc, and boolean operators (e.g move_num == 3). Multiple breakpoints can be expressed in one expression

Functions

BreakpointStateGlobals *get_bp_state_globals(): returns the global variable that holds all values that can trigger a breakpoint and are updated by the router and placer

namespace vtr

Enums

enum e_formula_obj

Used to identify the type of symbolic formula object.

Values:

enumerator E_FML_UNDEFINED

enumerator E_FML_NUMBER

enumerator E_FML_BRACKET

enumerator E_FML_COMMA

enumerator E_FML_OPERATOR

enumerator E_FML_VARIABLE

enumerator E_FML_NUM_FORMULA_OBJS

enum e_operator

Used to identify an operator in a formula.

Values:

enumerator E_OP_UNDEFINED

enumerator E_OP_ADD

enumerator E_OP_SUB

enumerator E_OP_MULT

enumerator E_OP_DIV

enumerator E_OP_MIN

enumerator E_OP_MAX

enumerator E_OP_GCD

enumerator E_OP_LCM

enumerator E_OP_AND

enumerator E_OP_OR

enumerator E_OP_GT

enumerator E_OP_LT

enumerator E_OP_GTE

enumerator E_OP_LTE

enumerator E_OP_EQ

enumerator E_OP_MOD

enumerator E_OP_AA

enumerator E_OP_NUM_OPS

enum e_compound_operator

Used to identify operators with more than one character.

Values:

enumerator E_COM_OP_UNDEFINED

enumerator E_COM_OP_AND

enumerator E_COM_OP_OR

enumerator E_COM_OP_EQ

enumerator E_COM_OP_AA

enumerator E_COM_OP_GTE

enumerator E_COM_OP_LTE

class Formula_Object

A class represents an object in a formula.

This object can be any of the following:

a number
a bracket
an operator
a variable

Public Functions

inline Formula_Object(): constructor

inline std::string to_string() const: convert enum to string

Public Members

t_formula_obj type: indicates the type of formula object this is

union u_Data

object data, accessed based on what kind of object this is

Public Members

int num: for number objects

t_operator op: for operator objects

bool left_bracket: for bracket objects — specifies if this is a left bracket

class FormulaParser

A class to parse formula.

Public Functions

int parse_formula(const std::string &formula, const t_formula_data &mydata, bool is_breakpoint = false): returns integer result according to specified formula and data

int parse_piecewise_formula(const char *formula, const t_formula_data &mydata): returns integer result according to specified piece-wise formula and data

Public Static Functions

static bool is_piecewise_formula(const char *formula): checks if the specified formula is piece-wise defined

class t_formula_data

a class to hold the formula data

Public Functions

inline void clear(): clears all the formula data

inline void set_var_value(std::string_view var, int value): set the value of a specific part of the formula

inline int get_var_value(std::string_view var) const: get the value of a specific part of the formula.

vtr_color_map

namespace vtr

template<class T> struct Color: #include <vtr_color_map.h>

A container to save the rgb components of a color.

class ColorMap

#include <vtr_color_map.h>

A class that holds a complete color map.

Public Functions

ColorMap(float min, float max, const std::vector<Color<float>> &color_data): color map constructor

virtual ~ColorMap() = default: color map destructor

Color<float> color(float value) const: Returns the full color corresponding to the input value.

float min() const: Return the min Color of this color map.

float max() const: Return the max color of this color map.

float range() const: Return the range of the color map.

class InfernoColorMap : public vtr::ColorMap 

#include <vtr_color_map.h>

Public Functions

InfernoColorMap(float min, float max)

class PlasmaColorMap : public vtr::ColorMap 

#include <vtr_color_map.h>

Public Functions

PlasmaColorMap(float min, float max)

class ViridisColorMap : public vtr::ColorMap 

#include <vtr_color_map.h>

Public Functions

ViridisColorMap(float min, float max)

vtr_digest

std::string vtr::secure_digest_file(std::string_view filepath): Generate a secure hash of the file at filepath.

std::string vtr::secure_digest_stream(std::istream &is): Generate a secure hash of a stream.

vtr_logic

namespace vtr

Enums

enum class LogicValue

This class represents the different supported logic values.

Values:

enumerator FALSE

enumerator TRUE

enumerator DONT_CARE

enumerator UNKNOWN

enumerator NUM_LOGIC_VALUE_TYPES

vtr_math

This file defines some math operations.

namespace vtr

Functions

constexpr int nint(float val): Integer rounding conversion for floats.

template<typename T> T safe_ratio(T numerator, T denominator): Returns a ‘safe’ ratio which evaluates to zero if the denominator is zero.

template<typename ResultTy = double, typename InputIterator> ResultTy median_presorted(const InputIterator first, const InputIterator last): Returns the median of the elements in range [first, last) If there are an odd number of elements in the range, returns the average of the two middle elements (equal distance from the start and end). NOTE: This method assumes that the container that first and last point to are pre-sorted.

template<typename ResultTy = double, typename Container> ResultTy median(Container c): Returns the median of a whole container, assuming the container has not been pre-sorted. Note: This function is pass by value since the container needs to be sorted. If the container is already sorted, use median_presorted to avoid the copy.

template<typename ResultTy = double, typename Container> ResultTy median_presorted(const Container &c): Returns the median of a whole container, assuming that it is already sorted.

template<typename InputIterator> double geomean(const InputIterator first, const InputIterator last, double init = 1.)

Returns the geometric mean of the elements in range [first, last)

To avoid potential round-off issues we transform the standard formula:

 geomean = ( v_1 * v_2 * ... * v_n) ^ (1/n)

by taking the log:

 geomean = exp( (1 / n) * (log(v_1) + log(v_2) + ... + log(v_n)))

template<typename Container> double geomean(const Container &c): Returns the geometric mean of a whole container.

template<typename InputIterator> double arithmean(const InputIterator first, const InputIterator last, double init = 0.): Returns the arithmetic mean of the elements in range [first, last)

template<typename Container> double arithmean(const Container &c): Returns the aritmatic mean of a whole container.

template<typename T> static T gcd(T x, T y)

Returns the greatest common divisor of x and y.

Note that T should be an integral type

template<typename T> T lcm(T x, T y)

Return the least common multiple of x and y.

Note that T should be an integral type

template<class T> bool isclose(T a, T b, T rel_tol, T abs_tol): Return true if a and b values are close to each other.

template<class T> bool isclose(T a, T b): Return true if a and b values are close to each other (using the default tolerances)

namespace vtr

Functions

int ipow(int base, int exp): Calculates the value pow(base, exp)

template<typename X, typename Y> Y linear_interpolate_or_extrapolate(const std::map<X, Y> *xy_map, X requested_x)

Linear interpolation/Extrapolation.

Performs linear interpolation or extrapolation on the set of (x,y) values specified by the xy_map. A requested x value is passed in, and we return the interpolated/extrapolated y value at this requested value of x. Meant for maps where both key and element are numbers. This is specifically enforced by the explicit instantiations below this function. i.e. only templates using those types listed in the explicit instantiations below are allowed

template double linear_interpolate_or_extrapolate (const std::map< int, double > *xy_map, int requested_x)

template double linear_interpolate_or_extrapolate (const std::map< double, double > *xy_map, double requested_x)

vtr_ostream_guard

namespace vtr

class OsFormatGuard

#include <vtr_ostream_guard.h>

A RAII guard class to ensure restoration of output stream format.

Public Functions

inline explicit OsFormatGuard(std::ostream &os): constructor

inline ~OsFormatGuard(): destructor

OsFormatGuard(const OsFormatGuard&) = delete

OsFormatGuard &operator=(const OsFormatGuard&) = delete

OsFormatGuard(const OsFormatGuard&&) = delete

OsFormatGuard &operator=(const OsFormatGuard&&) = delete

vtr_path

This file defines some useful utilities to handle paths.

std::array<std::string, 2> vtr::split_ext(const std::string &filename): Splits off the name and extension (including “.”) of the specified filename.

std::string vtr::basename(const std::string &path)

Returns the basename of path (i.e. the last filename component)

For example, the path “/home/user/my_files/test.blif” -> “test.blif”

std::string vtr::dirname(const std::string &path)

Returns the dirname of path (i.e. everything except the last filename component)

For example, the path “/home/user/my_files/test.blif” -> “/home/user/my_files/”

std::string vtr::getcwd(): Returns the current working directory.

vtr_random

namespace vtr

Functions

template<typename Iter> void shuffle(Iter first, Iter last, RngContainer &rng)

Portable/invariant version of std::shuffle.

Note that std::shuffle relies on std::uniform_int_distribution which can produce different sequences across different compilers/compiler versions.

This version should be deterministic/invariant. However, since it uses vtr::irand(), may not be as well distributed as std::shuffle.

namespace vtr

vtr_rusage

namespace vtr

Functions

size_t get_max_rss(): Returns the maximum resident set size in bytes, or zero if unable to determine.

vtr_sentinels

This header defines different sentinel value classes.

namespace vtr

template<class T> class DefaultSentinel

#include <vtr_sentinels.h>

The Default sentinel value class.

Some specialized containers like vtr::linear_map and vtr::vector_map require sentinel values to mark invalid/uninitialized values. By convention, such containers query the sentinel objects static INVALID() member function to retrieve the sentinel value.

These classes allows users to specify a custom sentinel value.

Usually the containers default to DefaultSentinel

The sentinel value is the default constructed value of the type

template<class T> class DefaultSentinel<T*>: #include <vtr_sentinels.h>

Specialization for pointer types.

template<class T, T val> class CustomSentinel: #include <vtr_sentinels.h>

The sentile value is a specified value of the type.

vtr_string_interning

Provides basic string interning, along with pattern splitting suitable for use with FASM.

For reference, string interning refers to keeping a unique copy of a string in storage, and then handing out an id to that storage location, rather than keeping the string around. This deduplicates memory overhead for strings.

This string internment has an additional feature that is splitting the input string into “parts” based on ‘.’, which happens to be the feature separator for FASM. This means the string “TILE.CLB.A” and “TILE.CLB.B” would be made up of the intern ids for {“TILE”, “CLB”, “A”} and {“TILE”, “CLB”, “B”} respectively, allowing some internal deduplication.

Strings can contain up to kMaxParts, before they will be interned as their whole string.

Interned strings (interned_string) that come from the same internment object (string_internment) can safely be checked for equality and hashed without touching the underlying string. Lexicographical comparisons (e.g. <) requires reconstructing the string.

Basic usage:

Create a string_internment
Invoke string_internment::intern_string, which returns the interned_string object that is the interned string’s unique identifier. This identifier can be checked for equality or hashed. If string_internment::intern_string is called with the same string, a value equivalent interned_string object will be returned.
If the original string is required, interned_string::get can be invoked to copy the string into a std::string. interned_string also provides iteration via begin/end, however the begin method requires a pointer to original string_internment object. This is not suitable for range iteration, so the method interned_string::bind can be used to create a bound_interned_string that can be used in a range iteration context.

For reference, the reason that interned_string’s does not have a reference back to the string_internment object is to keep their memory footprint lower.

class string_internment

Storage of interned string, and object capable of generating new interned_string objects.

Public Functions

inline interned_string intern_string(std::string_view view)

Intern a string, and return a unique identifier to that string.

If interned_string is ever called with two strings of the same value, the interned_string will be equal.

inline std::string_view get_string(StringId id) const: Retrieve a string part based on id. This method should not generally be called directly.

inline size_t unique_strings() const: Number of unique string parts stored.

class interned_string

Interned string value returned from a string_internment object.

This is a value object without allocation. It can be checked for equality and hashed safely against other interned_string’s generated from the same string_internment.

Public Functions

inline interned_string(std::array<StringId, kMaxParts> intern_ids, size_t n): constructor

inline void get(const string_internment *internment, std::string *output) const

Copy the underlying string into output.

internment must the object that generated this interned_string.

inline std::string get(const string_internment *internment) const

Returns the underlying string as a std::string.

This method will allocated memory.

inline bound_interned_string bind(const string_internment *internment) const

Bind the parent string_internment and return a bound_interned_string object.

That bound_interned_string lifetime must be shorter than this interned_string object lifetime, as bound_interned_string contains a reference this object, along with a reference to the internment object.

inline interned_string_iterator begin(const string_internment *internment) const: begin() function

inline interned_string_iterator end() const: end() function

Friends

friend bool operator==(interned_string lhs, interned_string rhs) noexcept: == operator

friend bool operator!=(interned_string lhs, interned_string rhs) noexcept: != operator

class bound_interned_string

A interned_string bound to it’s string_internment object.

This object is heavier than just an interned_string. This object holds a pointer to interned_string, so its lifetime must be shorter than the parent interned_string.

Public Functions

inline bound_interned_string(const string_internment *internment, const interned_string *str): constructor

inline interned_string_iterator begin() const: return an iterator to the first part of the interned_string

inline interned_string_iterator end() const: return an iterator to the last part of the interned_string

class interned_string_iterator

Iterator over interned string.

This object is much heavier memory wise than interned_string, so do not store these.

This iterator only accommodates the forward_iterator concept.

Do no construct this iterator directly. Use either bound_interned_string::begin/end or interned_string;:begin/end.

Public Functions

inline interned_string_iterator(const string_internment *internment, std::array<StringId, kMaxParts> intern_ids, size_t n)

constructor for interned string iterator.

Do no construct this iterator directly. Use either bound_interned_string::begin/end or interned_string;:begin/end.

inline interned_string_iterator &operator++(): Increment operator for interned_string_iterator.

inline interned_string_iterator operator++(int): Increment operator for interned_string_iterator.

Friends

friend bool operator==(const interned_string_iterator &lhs, const interned_string_iterator &rhs): == operator

vtr_token

Tokenizer.

Author: Jason Luu @Date July 22, 2009

Enums

enum class e_token_type

Token types.

Values:

enumerator NULL_TOKEN

enumerator STRING

enumerator INT

enumerator OPEN_SQUARE_BRACKET

enumerator CLOSE_SQUARE_BRACKET

enumerator OPEN_SQUIG_BRACKET

enumerator CLOSE_SQUIG_BRACKET

enumerator COLON

enumerator DOT

Functions

void my_atof_2D(float **matrix, const int max_i, const int max_j, std::string_view instring): Returns a 2D array representing the atof result of all the input string entries separated by whitespace.

bool check_my_atof_2D(const int max_i, const int max_j, std::string_view instring, int *num_entries)

Checks if the number of entries (separated by whitespace) matches the expected number (max_i * max_j)

can be used before calling my_atof_2D

struct t_token

#include <vtr_token.h>

Token structure.

Public Members

e_token_type type

std::string data

class Tokens

#include <vtr_token.h>

Public Functions

Tokens(std::string_view inString): Creates tokens for a given string.

const t_token &operator[](size_t idx) const

inline size_t size() const

Private Members

std::vector<t_token> tokens_

Private Static Attributes

static const t_token null_token_ = {e_token_type::NULL_TOKEN, ""}

vtr_util

namespace vtr

Functions

template<typename Iter> std::string join(Iter begin, Iter end, std::string_view delim)

Joins a sequence by a specified delimiter.

Template join function implementation.

For example the sequence {“home”, “user”, “my_files”, “test.blif”} with delim=”/” would return “home/user/my_files/test.blif”

template<typename Container> std::string join(Container container, std::string_view delim)

template<typename T> std::string join(std::initializer_list<T> list, std::string_view delim)

template<typename ...Conditions> bool exactly_k_conditions(int k, Conditions... conditions)

template<typename Container> void uniquify(Container container)

Template uniquify function implementation.

Removes repeated elements in the container

char *getline(char *&_lineptr, FILE *_stream)

namespace vtr

Functions

std::string replace_first(std::string_view input, std::string_view search, std::string_view replace): Returns ‘input’ with the first instance of ‘search’ replaced with ‘replace’.

std::string replace_all(std::string_view input, std::string_view search, std::string_view replace): Returns ‘input’ with all instances of ‘search’ replaced with ‘replace’.

bool starts_with(const std::string &str, std::string_view prefix): Returns true if str starts with prefix.

std::string string_fmt(const char *fmt, ...): Returns a std::string formatted using a printf-style format string.

std::string vstring_fmt(const char *fmt, va_list args): Returns a std::string formatted using a printf-style format string taking an explicit va_list.

char *strncpy(char *dest, const char *src, size_t size): An alternate for strncpy since strncpy doesn’t work as most people would expect. This ensures null termination.

char *strdup(const char *str)