Please enable JavaScript.

Coggle requires JavaScript to display documents.

Computer Science - Coggle Diagram

- - - - Model
        
        Database Server
        
        Client Machine
      - Disadvantages
        
        Scalability
        
        Security
      - Advantages
        
        Low Maintanence
    - - Model
        
        Business Layer
        
        Handles query processing
        
        Data Layer
        
        Client Layer
      - Disadvantages
        
        High Maintenance
    - - Levels
        
        Physical Level
        
        Physical Schema
        
        Handled by DB admin
        
        Data maybe stored centrally or distributed
        
        Datastructure used for storing data, Index etc.
        
        View Level
        
        External Schema
        
        The interface for end-user
        
        Frontend Designer
        
        Logical Level
        
        Conceptual Schema
        
        ER-Model
        
        DB Designer
      - Motivation
        
        Data Independence
        
        Hide details of data location, format etc. from user
        
        Types
        
        Logical Data Independence
        
        Implemented using Views, only some columns are displayed
        
        Logical Scheme can change but view will not be affected
        
        Physical Data Independence
        
        Storage Structure
        
        DS Change
        
        index change
        
        Logical schema does not depend on where and how data is stored.
    - - Hierarchical
      - Relational
      - Network
      - ER
      - Object Oriented
  - - - Ellipse
      - Types
        
        Stored Vs Derived
        
        Derived -> Dotted Ellipse
        
        Key/Unique Vs Non-Key
        
        Key -> Underline of Attribute name inside ellipse
        
        Simple Vs Composite
        
        Composite -> Hierarchy of Ellipse
        
        Required Vs Optional
        
        Single Vs Multivalued
        
        Single -> Single Ellipse
        
        Multi -> Double Ellipse
        
        Complex (Composite + Multivalued)
        
        Prime Attribute
    - - Diamond
      - Degrees of Relationship(Cardinality)
        
        1-M/M-1
        
        Primary Key should be from M-side table
        
        Merging can be done for Relation table and M-side table
        
        1-1
        
        1-1 Relationship Table Reduction by merging tables
        
        Can be merged to either table
        
        M-N
        
        Referencing Table
        
        Primary Key = Composite Key of the PK of the tables being related
        
        Cannot be reduced
      - Relationship Table
        
        Foreign Key
        
        Primary Key of another table
        
        Descriptive Attribute
        
        Attributes of Relationship Tables
    - - Rectangle
  - - - Key that can determine all columns
      - Attribute
        
        Prime
        
        Non-Prime
    - - Candidate Key + Extra Key
  - - - Row Level
        
        Solution: Use primary key which should be unique and non-NULL
    - - Deletion Anomaly
      - Updation Anomaly
      - Insertion Anomaly
    - - First Normal Form
        
        Criteria
        
        Table should not contain any multi-valued attribute
        
        Solutions
        
        Multiple Columns, one column for each attribute
        
        Split into Base Table and Referencing Table
        
        Insert one row for each attribute
      - Second Normal Form
        
        Criteria
        
        Must be in First Normal Form
        
        All the non-prime attributes should be fully dependent on the candidate key
        
        There should be no partial dependency in the relation
        
        Solution
        
        Split into multiple tables
      - Third Normal Form
        
        Criteria
        
        Must be in Second Normal Form
        
        There should be no transitive dependency in the relation
        
        Solution
        
        Split into multiple tables
        
        Finding Transitive Dependency
        
        For each FD
        
        LHS must be CK or SK
        
        RHS is a prime attribute
  - - - Consistency
      - Isolation
      - Atomicity
      - Durability
    - - W-R
      - W-W
      - R-W
    - - 2PL(Phase Lock)
      - Timestamp Protocol
  - - - DCL
      - DDL
      - DML
    - - Unique Key Constraint
      - Check Constraint
      - Primary Key Constraint
      - Default Constraint
      - Not NULL Constraint
    - - NotIn
      - Any
      - In
      - All
  - - - Role based security
    - - Constraints ensure there is no data redundancy
  - - - Combine all the RHS from the functional relations
      - Add all attributes to the candidate which are not the combined RHS
      - Start adding to the candidate key and use attributes from RHS to add more attributes to the RHS using the functional relations
  - - - X: Determinant Attribute
      - Y: Dependent Attribute
    - - Y is a subset of X
      - Intersection of XY will not be NULL
    - - Union
        
        If X -> Y and X -> Z then X -> YZ
      - Decomposition
        
        If X -> YZ then X -> Y and X -> Z
      - Transitive
        
        If X -> Y and Y -> Z then X -> Z
      - Pseudotransitivity
        
        If X -> Y and WY -> Z then WX -> Z
      - Aumentation
        
        If X -> Y then XZ -> YZ
      - Composition
        
        If X -> Y and Z -> W then XZ -> W
      - Reflexivity
        
        If Y is a subset of X then X -> Y
- - - - Finite State Machine or Finite Automaton
        
        Types
        
        Deterministic Finite Automaton(DFA)
        
        Terms
        
        Alphabet Σ
        
        Set of Accept/Final States: F ⊆ Q
        
        States: Q
        
        Language Of Machine
        
        M = (Q, Σ, δ, q0 , F )
        
        Start State: q0 ∈ Q
        
        Transition Function
        
        δ : Q × Σ→Q is the transition function
        
        Properties
        
        2 more items...
        
        DFA Design Rules
        
        Create state transitions based on reading input
        
        Mark start state and end states
        
        Identify Information that should be tracked and map to states
        
        Extended Transition Function
        
        δ̂ (q, w) = {p 1 , p 2 , ... p k }
        
        δ̂ (p i , a) = S i for i = 1, 2,...k
        
        δ̂(q, wa) = S 1 ∪ S 2 ∪... ∪ S k
        
        Equivalence of NFA and DFA
        
        Generalised Non-Deterministic Finite Automaton(GNFA)
        
        NFA with the transitions being labelled by regular expressions
        
        Definition
        
        5-tuple, (Q,∑, δ, qstart, qaccept)
        
        Q is the finite set of states
        
        ∑ is the input alphabet
        
        δ : (Q - {qaccept} x (Q - { qstart }) → R is the transition function, where R is the set of all regular expressions over ∑
        
        qstart is the start state
        
        qaccept is the accept state
        
        Note
        
        2 more items...
        
        Acceptance Criteria
        
        A GNFA accepts a string w in ∑* if w = w1w2...wk, where each wi is in ∑*
        
        q0 is the start state
        
        qk is the accept state
        
        for each i, wi ∊ L(Ri) where Ri = δ(qi-1, qi); that is, where Ri is the expression on the arrow from qi-1 to qi
        
        State Elimination
        
        Any state except the start state and the accept state of a GNFA can be eliminated to obtain a new equivalent GNFA with one fewer states
        
        Non-Deterministic Automaton(NFA)
        
        Epsilon Closure
        
        Epsilon closure of a state is simply the set of all states that we can reach by ε input. This includes the current state as well.
        
        Extended Transition Function
        
        δ̂ (q, w) = {p 1 , p 2 , ... p k }
        
        δ̂ (p i , a) = S i for i = 1, 2,...k
        
        δ̂ (q, wa) = ∪ e-closure(S 1 ∪ S 2 ∪... ∪ S k )
        
        Terms
        
        States
        
        Accept State
        
        Alphabet
        
        Start State
        
        Transition Function
        
        P(Q) = Power Set
        
        δ : Q × Σε → P(Q)
        
        Regular Lanuages
        
        A language is called a regular language if some finite automaton recognizes it.
        
        Formal Definition of Computation
        
        M = (Q, Σ, δ, q 0 , F )
        
        w = w 1 w 2 · · · wn be a string
        
        M accepts w if
        
        sequence of states r 0 , r 1 , . . . , r n in Q exists with three conditions
        
        δ(r i , w i+1 ) = r i+1 , for i = 0, . . . , n − 1
        
        rn ∈ F
        
        r 0 = q 0
        
        M recognizes language A if A = {w| M accepts w}
      - Regular Operations
        
        Types
        
        Star
        
        Unary
        
        Union
        
        Proof of Closed Operation
        
        M 1 recognize A 1 , where M 1 = (Q 1 , Σ, δ 1 , q 1 , F 1 )
        
        M 2 recognize A 2 , where M 2 = (Q 2 , Σ, δ 2 , q 2 , F 2 )
        
        Construct M to recognize A 1 ∪ A 2 , where M = (Q, Σ, δ, q 0 , F )
        
        Q = {(r 1 , r 2 )| r 1 ∈ Q 1 and r 2 ∈ Q 2 }
        
        Σ, the alphabet, is the same as in M 1 and M 2
        
        Σ = Σ 1 ∪ Σ 2 if alphabets are different for the two languages
        
        δ ((r 1 , r 2 ), a) = (δ 1 (r 1 , a), δ 2 (r 2 , a))
        
        F = {(r 1 , r 2 )| r 1 ∈ F 1 or r 2 ∈ F 2 }
        
        Concatenation
        
        Binary
        
        Closed Operation
        
        Operation on collection of objects is closed if the output of the operations belongs to the same class
      - Regular Expressions
        
        R is a regular expression if R is
        
        ∅
        
        ∅
        represents the language that doesn’t contain any strings
        
        (R 1 ∪ R 2 ), where R 1 and R 2 are regular expressions
        
        ε
        
        The expression ε represents
        the language containing a single string—namely, the empty string
        
        (R 1 ◦ R 2 ), where R 1 and R 2 are regular expressions
        
        a for some a in the alphabet Σ
        
        (R 1 ∗ ), where R 1 is a regular expression
        
        Shorthands
        
        R+ is shorthand for RR ∗
        
        Rk be shorthand for the concatenation of k R’s
        with each other
        
        L(R) is the language of R
        
        Regular Expressions are equivalent to finite Automata
        
        Special Rules
        
        R ∪ ∅ = R
        
        R ◦ ε = R
        
        R ∪ ε may not equal R
        
        if R = 0, then L(R) = {0} but L(R ∪ ε) = {0, ε}
        
        R ◦ ∅ may not equal R
        
        if R = 0, then L(R) = {0} but L(R ◦ ∅) = ∅
      - Non-Regular Languages
        
        Non-regularity Test
        
        Non-regularity test based on Myhill-Nerode's theorem
        
        Indistinguishability of strings
        
        Strings x and y in Σ* are indistinguishable with respect to a language L if and only if for every string z in Σ*, either xz and yz are both in L or they are both not in L
        
        Pumping Lemma
      - Pumping Lemma
        
        It states that if a language is regular, then any long enough string of the language has a substring which can be repeated any number of times with the resultant strings still in the language
        
        Theorem
        
        Suppose that a language L is regular. Then there is an FA that accepts L
        
        Let n be the number of states of that FA
        
        Then for any string x in L with |x| >= n, there are strings u, v and w which satisfy the following relationships:
        
        x = uvw
        
        |uv| <= n
        
        |v| > 0 and
        
        for every integer m >= 0, uv^mw q0 ∈ L
      - Conversion
        
        NFA without ε to DFA
        
        NFA with ε to NFA without ε
        
        Steps
        
        Find e-closure of each state
        
        Find the transition on each state for each element
        
        If the ε-closure of a state
        contains a final state then make the state final
        
        NFA with ε to DFA
        
        Steps
        
        Find power set of states of NFA
        
        Compute ε-closure of each state
        
        Find the initial state by finding the e-closure of the initial state
        
        Explore the states that are valid states in DFA starting at the new initial state
        
        Subset Construction Method
        
        DFA to GNFA
        
        Steps
        
        Adding a new start state with an ε transition to the old start state
        
        Adding a new accepting state and adding ε transitions from all old accepting states to the new one.
        
        Definining the transition function δ' for the GNFA in terms of the transition function δ for the DFA by
        δ'(qi, qj) = a if and only if δ(qi, a) = qj
      - Representation
        
        Transition diagram
        
        Transition table
      - Extended Transition Function
        
        Describes what happens when we start in any state and follow any sequence of inputs
        
        If δ is our transition function, then the extended transition function is denoted by ˆδ
        
        The extended transition function is a function that takes a state
        q and a string w and returns a state p
      - DFA Minimization
        
        Every regular set has a minimal DFA
        that is unique up to isomorphism
        
        there is a purely mechanical method for
        constructing it from any given DFA for A
        
        Steps
        
        Get rid of inaccessible states
        
        Collapse “equivalent” states
        
        Equivalence Relation
        
        p ≈ q def ⇐⇒ ∀x ∈ Σ ∗ (δb(p, x) ∈ F ⇐⇒ δ^(q, x) ∈ F)
        
        collapsing criterion
        
        reflexive: p ≈ p for all p
        
        symmetric: if p ≈ q, then q ≈ p
        
        transitive: if p ≈ q and q ≈ r, then p ≈ r
        
        ≈ partitions the set on which it is defined into
        disjoint equivalence classes
        
        [p] def = {q | q ≈ p}
        
        Every element p ∈ Q is contained in exactly one equivalence class [p] : p ≈ q ⇐⇒ [p] = [q]
        
        quotient construction
        
        M/≈ def = (Q' , Σ, δ' , s' , F')
        
        Q' def = {[p] | p ∈ Q}
        
        Algorithm
        
        Equivalence Theorem
        
        Construct ∏ K+1 from ∏ K by partitioning further
        
        Let Q 1K be any subset in ∏ K . If q 1 and q 2 are in Q 1K they are (K + 1)-equivalent
        provided δ(q 1 , a) and δ(q 2 , a) are K-equivalent
        
        Find out whether δ(q 1 , a) and δ(q 2 , a) are in the same equivalence class in ∏ K for every a ∈ ∑. If so, q 1 and q 2 are (k + 1)-equivalent. This way Q i k is further divided into (K + 1)-equivalence classes. Repeat this for every Q i k in ∏ K to get all the
        elements of ∏ K + 1
        
        Construct ∏ n for n = 1, 2, 3, ... until ∏ n = ∏ n + 1
        
        Construct the minimum state DFA with the states obtained by equivalent classes π n
        
        Initially construct 0-equivalence class by ∏ 0 = {Q1^0 , Q2^0 } where Q1^0 is the set of final states and Q2^0 = Q - Q1^0 is the set of non-final states.
        
        Myhill-Nerode Theorem
  - - - Union
      - Intersection
      - Cartesian/Cross Product
    - - Domain
      - Range
    - - Equivalence Relation
        
        Symmetric
        
        Transitive
        
        Reflexive
    - - Nodes/Vertices
        
        Degree of Node
      - Edges
      - Self-Loop
      - G = (V={V1, V2, V3 ...}, E={(V1, V2), ((V2, V3), ...})
      - Labelled Graph
      - Subgraph
      - Path
        
        Simple Path
        
        Cycle
        
        Simple Cycle
      - Connected Graph
      - Tree
        
        No Simple Cycles
      - Directed Graph
        
        In-Degree
        
        Out-Degree
        
        Directed Path
    - - Alphabet
      - Symbols
      - String
        
        Substring
        
        Empty String
        
        Length of String
        
        Conctenation
        
        Order
        
        Lexicographic Order
        
        Shortlex/String Order
        
        Prefix
        
        Proper Prefix
        
        Language
        
        Prefix-Free
    - - Boolean values
        
        True
        
        False
      - Boolean Operations
        
        Negation/NOT
        
        Conjunction/AND
        
        Disjunction/OR
        
        Exclusive-Or/XOR
        
        Equality
        
        Implication
        
        Distributive Law
    - - Proof By Construction
      - Proof By Contradiction
      - Proof By Induction
  - - - A context-free grammar is a 4-tuple (V, Σ, R, S), where
        
        Σ is a finite set, disjoint from V , called the terminals
        
        R is a finite set of rules, with each rule being a variable and a
        string of variables and terminals
        
        V is a finite set called the variables
        
        S ∈ V is the start variable
    - - Language of Grammar
        
        {w ∈ Σ ∗ | S ⇒ w}
      - Yield
        
        A → w
        
        uAv yields uwv
      - Derive
        
        u *⇒ v
        
        u 1 , u 2 , . . . , u k exists for k ≥ 0
        
        u ⇒ u 1 ⇒ u 2 ⇒ . . . ⇒ u k ⇒ v
    - - Rules
        
        A → a
        
        A → BC
        
        B and C may not be the start variable
        
        S → ε, where S is the start variable
      - Any context-free language is generated by a context-free grammar in Chomsky normal form
    - - A pushdown automaton is a 6-tuple (Q, Σ, Γ, δ, q 0 , F ), where Q, Σ, Γ, and F are all finite sets, and
        
        Q is the set of states
        
        Σ is the input alphabet
        
        Γ is the stack alphabet
        
        δ : Q × Σ ε × Γ ε −→P(Q × Γ ε ) is the transition function
        
        q 0 ∈ Q is the start state
        
        F ⊆ Q is the set of accept states
      - Deterministic PDA
        
        Less power full than NDPDA
        
        At each step of its computation, the DPDA has at most one way to proceed according to its transition function
        
        Defining DPDA s is more
        complicated than defining
        DFAs
        
        DPDA s may read an input symbol without popping a stack symbol, and vice versa
        
        Accordingly, we allow ε-moves in the DPDA ’s transition function even though ε-moves are prohibited in DFAs
        
        These ε-moves take two forms
        
        ε-input moves corresponding to δ(q, ε, x)
        
        ε-stack moves corresponding to δ(q, a, ε)
        
        A move may combine both forms, corresponding to δ(q, ε, ε)
        
        If a DPDA can make an ε-move in a certain situation, it is prohibited from making a move in that same situation that involves processing a symbol instead of ε
        
        Definition
        
        6-tuple (Q, Σ, Γ, δ, q 0 , F )
        
        Q is the set of states
        
        Σ is the input alphabet
        
        Γ is the stack alphabet
        
        δ : Q × Σ ε × Γ ε −→(Q × Γ ε ) ∪ {∅} is the transition function
        
        q 0 ∈ Q is the start state
        
        F ⊆ Q is the set of accept states
        
        For every q ∈ Q, a ∈ Σ, and x ∈ Γ, exactly one of the values
        δ(q, a, x), δ(q, a, ε), δ(q, ε, x), and δ(q, ε, ε)
        is not ∅
        
        Non-Deterministic PDA
        
        There are multiple parallel copies of the machine running at once,
        each of which has its own stack
      - Computation
        
        Accepts input w if w can be written as w = w 1 w 2 · · · w m , where
        
        each w i ∈ Σ ε
        
        sequences of states r 0 , r 1 , . . . , r m ∈ Q
        
        strings s 0 , s 1 , . . . , s m ∈ Γ ∗
        
        Conditions
        
        r 0 = q 0 and s 0 = ε
        
        For i = 0, . . . , m − 1, we have (r i+1 , b) ∈ δ(r i , w i+1 , a), where s i = at and s i+1 = bt for some a, b ∈ Γ ε and t ∈ Γ ∗ .
        
        r m ∈ F
    - - A language is context-free iff there is some CFG
        that generates it
      - A language is
        context-free iff there is some PDA that recognizes it
      - CFG are equivalent to PDA
    - - The languages that are recognizable by deterministic pushdown automata ( DPDA s) are called deterministic context-free languages ( DCFL s)
      - The parsing problem is generally easier for DCFL s than for CFL s
- - - - Function
      - Instruction
      - MachineInstr
      - BasicBlock
      - MachineFunction
    - - Module
        
        The contents of an entire LLVM file, either assembly or bitcode, are said to define an LLVM module.
        
        The module is the LLVM IR top-level data structure.
        
        Contains
        
        Each module contains a sequence of functions, which contains a sequence of basic blocks that contain a sequence of instructions.
        
        Global Variables
        
        Target Data Layout
        
        External Function Prototypes
        
        Data Structure Declarations
        
        Symbol Table Entries
        
        Modules may be combined together with the LLVM linker.
        
        merges function (and global variable) definitions
        
        resolves forward declarations
        
        merges symbol table entries
      - Syntax
        
        LLVM Local Values
        
        LLVM local values are the analogs of the registers in the assembly language and can have any name that starts with the % symbol.
        
        global identifiers use @
      - Properties
        
        Single Static Assignment
        
        NNo value that is reassigned; each value has only a single assignment that defines it.
        
        Each use of a value can immediately be traced back to the sole instruction responsible for its definition.
        
        Three Address Instructions
        
        Code is organized as three-address instructions.
        
        Data processing instructions have two source operands and place the result in a distinct destination operand.
        
        It has an infinite number of registers.
      - Types
        
        Arbitrary-sized integers in the iN form; common examples are i32, i64, and i128
        
        Floating-point types, such as the 32-bit single precision float and 64-bit double precision double
      - Reference
      - Identifiers
        
        Types
        
        Global
        
        Local
      - Linkage Types
        
        weak
        
        common
        
        linkonce
        
        appending
        
        available_externally
        
        extern_weak
        
        internal
        
        linkonce_odr, weak_odr
        
        private
        
        external
      - Calling Conventions
        
        anyregcc
        
        preserve_mostcc
        
        webkit_jscc
        
        preserve_allcc
        
        cc 11
        
        cxx_fast_tlscc
        
        cc 10
        
        swiftcc
        
        coldcc
        
        tailcc
        
        fastcc
        
        cfguard_checkcc
        
        ccc
        
        cc <n>
      - Visibility Styles
        
        hidden
        
        protected
        
        default
      - Global Variables
        
        Regions of memory allocated at compilation time instead of runtime
        
        Global variable definitions must be initialized
        
        Global variables in other translation units can also be declared, in which case they don’t have an initializer
        
        Global variables can optionally specify a linkage type
      - Functions
        
        Function Definition
        
        Consist of
        
        optional linkage type
        
        optional runtime preemption specifier
        
        optional visibility style
        
        optional DLL storage class
        
        optional calling convention
        
        optional unnamed_addr attribute
        
        optional parameter attribute for the return type
        
        a function name
        
        argument list (each with optional parameter attributes)
        
        optional function attributes
        
        an optional address space
        
        optional section
        
        optional alignment
        
        optional comdat
        
        optional garbage collector name
        
        optional prefix
        
        optional prologue
        
        optional personality
        
        optional list of attached metadata
        
        an opening curly brace
        
        list of basic blocks
        
        closing curly brace
        
        “define” keyword
        
        Function Declaration
        
        Consist Of
        
        return type
        
        n optional parameter attribute for the return type
        
        optional address space
        
        function name
        
        optional unnamed_addr or local_unnamed_addr attribute
        
        possibly empty list of arguments
        
        optional calling convention
        
        optional alignment
        
        optional DLL storage class
        
        optional garbage collector name
        
        optional visibility style
        
        optional prefix
        
        optional linkage type
        
        optional prologue
        
        “declare” keyword
      - Instructions
        
        Terminator Instructions
      - Type System
        
        A strong type system makes it easier to read the generated code and enables novel analyses and transformations that are not feasible to perform on normal three address code representations.
        
        The LLVM type system is one of the most important features of the intermediate representation.
        
        Being typed enables a number of optimizations to be performed on the intermediate representation directly, without having to do extra analyses on the side before the transformation
        
        Types
        
        Void Type
        
        Function Type
        
        First Class Types
        
        Single Value Types
        
        Integer Type
        
        Floating Point Types
        
        X86_mmx Type
        
        Pointer Type
        
        Vector Type
        
        Label Type
        
        Token Type
        
        Aggregate Types
        
        Array Type
        
        Structure Type
        
        Opaque Structure Types
      - Intrinsic Functions
        
        LLVM supports the notion of an “intrinsic function”
        
        These functions have well known names and semantics and are required to follow certain restrictions.
        
        Overall, these intrinsics represent an extension mechanism for the LLVM language that does not require changing all of the transformations in LLVM when adding to the language (or the bitcode reader/writer, the parser, etc...).
        
        Intrinsic function names must all start with an “llvm.” prefix.This prefix is reserved in LLVM for intrinsic names; thus, function names may not begin with this prefix.
        
        Intrinsic functions must always be external functions: you cannot define the body of intrinsic functions.
        
        Intrinsic functions may only be used in call or invoke instructions: it is illegal to take the address of an intrinsic function.
        
        Additionally, because intrinsic functions are part of the LLVM language, it is required if any are added that they be documented
        
        List Of Intrinsics
        
        Variable Argument Handling Intrinsics
        
        Accurate Garbage Collection Intrinsics
        
        Code Generator Intrinsics
        
        Standard C Library Intrinsics
        
        Bit Manipulation Intrinsics
        
        Arithmetic with Overflow Intrinsics
        
        Specialised Arithmetic Intrinsics
        
        Experimental Vector Reduction Intrinsics
        
        Half Precision Floating Point Intrinsics
        
        Debugger Intrinsics
        
        Exception Handling Intrinsics
        
        Trampoline Intrinsics
        
        Masked Vector Load and Store Intrinsics
        
        Masked Vector Gather and Scatter Intrinsics
        
        Memory Use Markers
        
        Constrained Floating Point Intrinsics
        
        Constrained libm-equivalent Intrinsics
        
        General Intrinsics
        
        Stack Map Intrinsics
        
        Element Wise Atomic Memory Intrinsics
      - Metadata
        
        LLVM IR allows metadata to be attached to instructions in the program that can convey extra information about the code to the optimizers and code generator.
        
        Primitives
        
        strings
        
        nodes
        
        All metadata are identified in syntax by a exclamation point (‘!‘)
        
        A named metadata is a collection of metadata nodes, which can be looked up in the module symbol table.
        
        Metadata can be used as function arguments.
        
        Metadata can be attached to an instruction.
        
        Metadata can also be attached to a function or a global variable.
        
        A transformation is required to drop any metadata attachment that it does not know or know it can’t preserve.
        
        Specialized Metadata Nodes
        
        Their fields are labelled, and can be specified in any order.
        
        These aren’t inherently debug info centric, but currently all the specialized metadata nodes are related to debug info.
        
        Specialized metadata nodes are custom data structures in metadata (as opposed to generic tuples).
        
        List
        
        DICompileUnit
        
        DIFile
        
        DIBasicType
        
        DISubroutineType
        
        DIDerivedType
        
        DICompositeType
        
        DISubrange
    - - Documents
        
        Rational Document
        
        Language Reference
        
        Operation Definition Specification
        
        Graph Rewrite Tutorial
        
        Table Driven Declarative Rewrite Rule
        
        Dialect Conversion
        
        Traits
        
        Defining a dialect
        
        Creating Dialect
      - Intended for easy expression and optimization of computations involving deep loop nests and dense matrices of high dimensionality.
      - MLIR is a compiler intermediate representation with similarities to traditional three-address SSA representations (like LLVM IR or SIL ), but which introduces notions from the polyhedral loop optimization works as first class concepts.
      - This hybrid design is optimized to represent, analyze, and transform high level dataflow graphs as well as target-specific code generated for high performance data parallel systems.
      - Beyond its representational capabilities, its single continuous design provides a framework to lower from dataflow graphs to high performance target specific code.
      - MLIR uses ideas drawn from IRs of LLVM and Swift for lower level constructs while combining them with ideas from the polyhedral abstraction to represent loop nests, multidimensional data (tensors), and transformations on these entities as first class concepts in the IR.
      - Declarative Rewrite Rule
        
        The declarative rewrite rule is operation-based
        
        It describes a rule to match against a directed acyclic graph (DAG) of operations
        
        Generate DAGs of operations
        
        It is good at expressing op to op conversions
        
        not that well suited for, say, converting an op into a loop nest
      - Dialect
        
        TFRT Dialect
        
        tfrt_base.td
        
        basic_kernels.td
        
        OpBase.td
        
        Define Dialect programatically
      - High-Level Structure
        
        Graph-like data structure of nodes, called Operations
        
        edges, called Values
        
        Each Value is the result of exactly one Operation or Block Argument, and has a Value Type defined by the type system
        
        Operations are contained in Blocks and Blocks are contained in Regions
        
        Operations are also ordered within their containing block and Blocks are ordered in their containing region, although this order may or may not be semantically meaningful in a given kind of region )
        
        Operations may also contain regions, enabling hierarchical structures to be represented
        
        Operations can represent many different concepts
        
        higher-level concepts like
        
        function definitions
        
        function calls
        
        buffer allocations
        
        view or slices of buffers
        
        process creation
        
        lower-level concepts like
        
        target-specific instructions
        
        configuration registers
        
        target-independent arithmetic
        
        logic gates
        
        the set of operations usable in MLIR can be arbitrarily extended.
        
        Adding Ops Programatically
        
        MLIR also provides an extensible framework for transformations on operations, using familiar concepts of compiler Passes
        
        Traits
        
        Traits are a mechanism which abstracts implementation details and properties that are common across many different attributes/operations/types/etc..
        
        Attribute Traits
        
        Op Traits
        
        Type Trait
      - Language
        
        Region
        
        A region is an ordered list of MLIR Blocks
        
        The semantics within a region is not imposed by the IR
        
        The containing operation defines the semantics of the regions it contains
        
        MLIR currently defines two kinds of regions:
        
        SSACFG regions , which describe control flow between blocks
        
        Graph regions
        
        The kinds of regions within an operation are described using the RegionKindInterface
        
        Regions do not have a name or an address, only the blocks contained in a region do.
        
        Regions must be contained within operations and have no type or attributes.
        
        The first block in the region is a special block called the ‘entry block’.
        
        The arguments to the entry block are also the arguments of the region itself.
        
        The entry block cannot be listed as a successor of any other block.
        
        Syntax
        
        region ::= { block* }
        
        Value Scoping
        
        Regions provide hierarchical encapsulation of programs
        
        Regions provides a natural scoping for value visibility
        
        Operations inside a region can reference values defined outside of the region whenever it would have been legal for operands of the enclosing operation to reference those values
        
        MLIR defines a generalized ‘hierarchical dominance’ concept that operates across hierarchy and defines whether a value is ‘in scope’ and can be used by a particular operation
        
        Whether a value can be used by another operation in the same region is defined by the kind of region.
        
        A value defined in a region can be used by an operation which has a parent in the same region, if and only if the parent could use the value
        
        A value defined by an argument to a region can always be used by any operation deeply contained in the region.
        
        A value defined in a region can never be used outside of the region.
        
        Regions are impossible to reference. No reference, so no arbitrary access.
        
        Control Flow and SSACFG Regions
        
        In MLIR, control flow semantics of a region is indicated by RegionKind::SSACFG
        
        Informally, these regions support semantics where operations in a region ‘execute sequentially’
        
        Before an operation executes, its operands have well-defined values.
        
        After an operation executes, the operands have the same values and results also have well-defined values.
        
        After an operation executes, the next operation in the block executes until the operation is the terminator operation at the end of a block, in which case some other operation will execute.
        
        The determination of the next instruction to execute is the ‘passing of control flow’.
        
        In general, when control flow is passed to an operation, MLIR does not restrict when control flow enters or exits the regions contained in that operation.
        
        However, when control flow enters a region, it always begins in the first block of the region, called the entry block.
        
        Terminator operations ending each block represent control flow by explicitly specifying the successor blocks of the block. :red_flag:
        
        Control flow can only pass to one of the specified successor blocks as in a branch operation, or back to the containing operation as in a return operation. :red_flag:
        
        Terminator operations without successors can only pass control back to the containing operation.
        
        Within these restrictions, the particular semantics of terminator operations is determined by the specific dialect operations involved.
        
        Blocks (other than the entry block) that are not listed as a successor of a terminator operation are defined to be unreachable and can be removed without affecting the semantics of the containing operation.
        
        Although control flow always enters a region through the entry block, control flow may exit a region through any block with an appropriate terminator.
        
        The standard dialect leverages this capability to define operations with Single-Entry-Multiple-Exit (SEME) regions, possibly flowing through different blocks in the region and exiting through any block with a return operation.
        
        This behavior is similar to that of a function body in most programming languages. In addition, control flow may also not reach the end of a block or region, for example if a function call does not return.
        
        Operations with Multiple Regions
        
        An operation containing multiple regions also completely determines the semantics of those regions.
        
        In particular, when control flow is passed to an operation, it may transfer control flow to any contained region.
        
        When control flow exits a region and is returned to the containing operation, the containing operation may pass control flow to any region in the same operation
        
        An operation may also pass control flow to multiple contained regions concurrently.
        
        An operation may also pass control flow into regions that were specified in other operations, in particular those that defined the values or symbols the given operation uses as in a call operation.
        
        This passage of control is generally independent of passage of control flow through the basic blocks of the containing region.
        
        Closure
        
        Regions allow defining an operation that creates a closure, for example by “boxing” the body of the region into a value they produce.
        
        It remains up to the operation to define its semantics
        
        Note that if an operation triggers asynchronous execution of the region, it is under the responsibility of the operation caller to wait for the region to be executed guaranteeing that any directly used values remain live.
        
        Graph Regions
        
        In MLIR, graph-like semantics in a region is indicated by RegionKind::Graph
        
        Graph regions are appropriate for concurrent semantics without control flow, or for modeling generic directed graph data structures.
        
        Graph regions are appropriate for representing cyclic relationships between coupled values where there is no fundamental order to the relationships.
        
        For instance, operations in a graph region may represent independent threads of control with values representing streams of data.
        
        As usual in MLIR, the particular semantics of a region is completely determined by its containing operation
        
        Graph regions may only contain a single basic block (the entry block)
        
        In graph regions, MLIR operations naturally represent nodes, while each MLIR value represents a multi-edge connecting a single source node and multiple destination nodes.
        
        Currently graph regions are arbitrarily limited to a single basic block, although there is no particular semantic reason for this limitation.
        
        This limitation has been added to make it easier to stabilize the pass infrastructure and commonly used passes for processing graph regions to properly handle feedback loops
        
        Multi-block regions may be allowed in the future if use cases that require it arise.
        
        All values defined in the region as results of operations are in scope within the region and can be accessed by any other operation in the region.
        
        the order of operations within a block and the order of blocks in a region is not semantically meaningful and non-terminator operations may be freely reordered,
        
        Other kinds of graphs, such as graphs with multiple source nodes and multiple destination nodes, can also be represented by representing graph edges as MLIR operations.
        
        Arguments and Results
        
        The arguments of the first block of a region are treated as arguments of the region.
        
        The source of these arguments is defined by the semantics of the parent operation.
        
        They may correspond to some of the values the operation itself uses.
        
        Regions produce a (possibly empty) list of values.
        
        The operation semantics defines the relation between the region results and the operation results.
        
        Operations
        
        Syntax
        
        operation ::= op-result-list? (generic-operation | custom-operation)
        trailing-location?
        
        generic-operation ::= string-literal ( value-use-list? ) successor-list?
        (( region-list ))? attribute-dict? : function-type
        
        custom-operation ::= bare-id custom-operation-format
        
        op-result-list ::= op-result (, op-result)* =
        
        op-result ::= value-id (: integer-literal)
        
        successor-list ::= successor (, successor)*
        
        successor ::= caret-id (: bb-arg-list)?
        
        region-list ::= region (, region)*
        
        trailing-location ::= (loc ( location ))?
        
        MLIR introduces a uniform concept called operations to enable describing many different levels of abstractions and computations.
        
        Operations in MLIR are fully extensible (there is no fixed list of operations) and have application-specific semantics.
        
        For example, MLIR supports target-independent operations , affine operations , and target-specific machine operations
        
        internal representation
        
        an operation is identified by a unique string (e.g. dim, tf.Conv2d, x86.repmovsb, ppc.eieio, etc),
        
        can return zero or more results
        
        take zero or more operands
        
        may have zero or more attributes
        
        may have zero or more successors
        
        zero or more enclosed regions
        
        The generic printing form includes all these elements literally, with a function type to indicate the types of the results and operands.
        
        In addition to the basic syntax above, dialects may register known operations.
        
        This allows those dialects to support custom assembly form for parsing and printing operations
        
        Types
        
        Terminator Operations
        
        These are a special category of operations that must terminate a block
        
        These operations may also have a list of successors ( blocks and their arguments)
        
        Module
        
        Syntax
        
        module ::= module symbol-ref-id? (attributes attribute-dict)? region
        
        An MLIR Module represents a top-level container operation.
        
        It contains a single SSACFG region containing a single block which can contain any operations
        
        Operations within this region cannot implicitly capture values defined outside the module, i.e. Modules are IsolatedFromAbove
        
        Modules have an optional symbol name which can be used to refer to them in operations.
        
        Functions
        
        An MLIR Function is an operation with a name containing a single SSACFG region .
        
        Operations within this region cannot implicitly capture values defined outside of the function, i.e. Functions are IsolatedFromAbove
        
        All external references must use function arguments or attributes that establish a symbolic connection (e.g. symbols referenced by name via a string attribute like SymbolRefAttr ):
        
        Syntax
        
        function ::= func function-signature function-attributes? function-body?
        
        function-signature ::= symbol-ref-id ( argument-list )
        (-> function-result-list)?
        
        argument-list ::= (named-argument (, named-argument)) | /empty*/
        
        argument-list ::= (type attribute-dict? (, type attribute-dict?)) | /empty*/
        
        named-argument ::= value-id : type attribute-dict?
        
        function-result-list ::= function-result-list-parens
        | non-function-type
        
        function-result-list-parens ::= ( )
        | ( function-result-list-no-parens )
        
        function-result-list-no-parens ::= function-result (, function-result)*
        
        function-result ::= type attribute-dict?
        
        function-attributes ::= `attributes` attribute-dict
        
        function-body ::= region
        
        Example:
        
        3 more items...
        
        An external function declaration (used when referring to a function declared in some other module) has no body.
        
        While the MLIR textual form provides a nice inline syntax for function arguments, they are internally represented as “block arguments” to the first block in the region.
        
        Only dialect attribute names may be specified in the attribute dictionaries for function arguments, results, or the function itself.
        
        Blocks
        
        Syntax
        
        block ::= block-label operation+
        
        block-label ::= block-id block-arg-list? :
        
        block-id ::= caret-id
        
        caret-id ::= ^ suffix-id
        
        value-id-and-type ::= value-id : type
        
        value-id-and-type-list ::= value-id-and-type (, value-id-and-type)*
        
        block-arg-list ::= ( value-id-and-type-list? )
        
        A Block is an ordered list of operations, concluding with a single terminator operation .
        
        In SSACFG regions , each block represents a compiler basic block where instructions inside the block are executed in order and terminator operations implement control flow branches between basic blocks
        
        Blocks in MLIR take a list of block arguments, notated in a function-like way.
        
        Block arguments are bound to values specified by the semantics of individual operations.
        
        Block arguments of the entry block of a region are also arguments to the region and the values bound to these arguments are determined by the semantics of the containing operation
        
        Block arguments of other blocks are determined by the semantics of terminator operations, e.g. Branches, which have the block as a successor.
        
        In regions with control flow , MLIR leverages this structure to implicitly represent the passage of control-flow dependent values without the complex nuances of PHI nodes in traditional SSA representations
        
        Note that values which are not control-flow dependent can be referenced directly and do not need to be passed through block arguments
        
        Type System
        
        Syntax
        
        type ::= type-alias | dialect-type | standard-type
        
        type-list-no-parens ::= type (, type)*
        
        type-list-parens ::= ( )
        | ( type-list-no-parens )
        
        ssa-use-and-type ::= ssa-use : type
        
        ssa-use-and-type-list ::= ssa-use-and-type (, ssa-use-and-type)*
        
        Type Aliases
        
        Syntax
        
        type-alias-def ::= '!' alias-name '=' 'type' type
        
        type-alias ::= '!' alias-name
        
        MLIR supports defining named aliases for types.
        
        A type alias is an identifier that can be used in the place of the type that it defines.
        
        These aliases must be defined before their uses
        
        Alias names may not contain a ‘.', since those names are reserved for dialect types
        
        Dialect Types
        
        Syntax
        
        dialect-namespace ::= bare-id
        
        opaque-dialect-item ::= dialect-namespace '<' string-literal '>'
        
        pretty-dialect-item ::= dialect-namespace '.' pretty-dialect-item-lead-ident
        pretty-dialect-item-body?
        
        pretty-dialect-item-lead-ident ::= '[A-Za-z][A-Za-z0-9._]*'
        
        pretty-dialect-item-body ::= '<' pretty-dialect-item-contents+ '>'
        
        pretty-dialect-item-contents ::= pretty-dialect-item-body
        | '(' pretty-dialect-item-contents+ ')'
        | '[' pretty-dialect-item-contents+ ']'
        | '{' pretty-dialect-item-contents+ '}'
        | '[^[<({>])}\0]+'
        
        dialect-type ::= '!' opaque-dialect-item
        
        dialect-type ::= '!' pretty-dialect-item
        
        Standard Types
        
        Syntax
        
        standard-type ::= complex-type
        | float-type
        | function-type
        | index-type
        | integer-type
        | memref-type
        | none-type
        | tensor-type
        | tuple-type
        | vector-type
        
        Complex Type
        
        Syntax
        
        complex-type ::= complex < type >
        
        The value of complex type represents a complex number with a parameterized element type, which is composed of a real and imaginary value of that element type
        
        The element must be a floating point or integer scalar type
        
        Floating Point Types
        
        Syntax
        
        float-type ::= f16 | bf16 | f32 | f64
        
        Function Type
        
        Syntax
        
        function-result-type ::= type-list-parens
        | non-function-type
        
        function-type ::= type-list-parens -> function-result-type
        
        MLIR supports first-class functions: for example, the constant operation produces the address of a function as a value
        
        This value may be passed to and returned from functions, merged across control flow boundaries with block arguments , and called with the call_indirect operation
        
        Function types are also used to indicate the arguments and results of operations
        
        Index Type
        
        Syntax
        
        index-type ::= index
        
        The index type is a signless integer whose size is equal to the natural machine word of the target ( rationale ) and is used by the affine constructs in MLIR
        
        Unlike fixed-size integers, it cannot be used as an element of vector, tensor or memref type ( rationale )
        
        Integer Type
        
        Syntax
        
        signed-integer-type ::= si [1-9][0-9]*
        
        unsigned-integer-type ::= ui [1-9][0-9]*
        
        signless-integer-type ::= i [1-9][0-9]*
        
        integer-type ::= signed-integer-type |
        unsigned-integer-type |
        signless-integer-type
        
        MLIR supports arbitrary precision integer types
        
        Integer types have a designated width and may have signedness semantics
        
        Quantized Integer Type Discussion
        
        Memref Type
        
        Syntax
        
        memref-type ::= ranked-memref-type | unranked-memref-type
        
        ranked-memref-type ::= memref < dimension-list-ranked tensor-memref-element-type
        (, layout-specification)? |
        (, memory-space)? >
        
        unranked-memref-type ::= memref <*x tensor-memref-element-type
        (, memory-space)? >
        
        stride-list ::= [ (dimension (, dimension)*)? ]
        
        strided-layout ::= offset: dimension , strides: stride-list
        
        layout-specification ::= semi-affine-map | strided-layout
        
        memory-space ::= integer-literal / | TODO: address-space-id /
        
        A memref type is a reference to a region of memory (similar to a buffer pointer, but more powerful).
        
        The buffer pointed to by a memref can be allocated, aliased and deallocated
        
        A memref can be used to read and write data from/to the memory region which it references
        
        Memref types use the same shape specifier as tensor types. Note that memref<f32>, memref<0 x f32>, memref<1 x 0 x f32>, and memref<0 x 1 x f32> are all different types.
        
        A memref is allowed to have an unknown rank (e.g. memref<*xf32>). The purpose of unranked memrefs is to allow external library functions to receive memref arguments of any rank without versioning the functions based on the rank. Other uses of this type are disallowed or will have undefined behavior.
        
        Attributes
        
        Syntax
        
        attribute-dict ::= { } | { attribute-entry (, attribute-entry)* }
        
        attribute-entry ::= dialect-attribute-entry | dependent-attribute-entry
        
        dialect-attribute-entry ::= dialect-namespace . bare-id = attribute-value
        
        dependent-attribute-entry ::= dependent-attribute-name = attribute-value
        
        dependent-attribute-name ::= ((letter|[]) (letter|digit|[$])*) | string-literal
        
        attribute-value ::= attribute-alias | dialect-attribute | standard-attribute
        
        attribute-alias ::= '#' alias-name '=' attribute-value
        
        attribute-alias ::= '#' alias-name
        
        Attributes are the mechanism for specifying constant data on operations in places where a variable is never allowed - e.g. the index of a dim operation , or the stride of a convolution.
        
        They consist of a name and a concrete attribute value.
        
        The set of expected attributes, their structure, and their interpretation are all contextually dependent on what they are attached to.
        
        There are two main classes of attributes: dependent and dialect.
        
        Dependent attributes derive their structure and meaning from what they are attached to; e.g., the meaning of the index attribute on a dim operation is defined by the dim operation.
        
        Dialect attributes, on the other hand, derive their context and meaning from a specific dialect.
        
        Attribute Alias
        
        An attribute alias is an identifier that can be used in the place of the attribute that it defines.
        
        MLIR supports defining named aliases for attribute values
        
        Alias names may not contain a ‘.', since those names are reserved for dialect attributes
        
        Dialect Attribute Values
        
        Dialects may define custom attribute values
        
        The syntactic structure of these values is identical to custom dialect type values, except
        
        Dialect attributes values are distinguished with a leading ‘#',
        
        Dialect types are distinguished with a leading ‘!'
        
        Standard Attribute Values
        
        Standard attributes are a core set of dialect attributes that are defined in a builtin dialect and thus available to all users of MLIR
        
        Syntax
        
        standard-attribute ::= affine-map-attribute
        | array-attribute
        | bool-attribute
        | dictionary-attribute
        | elements-attribute
        | float-attribute
        | integer-attribute
        | integer-set-attribute
        | string-attribute
        | symbol-ref-attribute
        | type-attribute
        | unit-attribute
        
        Types
        
        AffineMap Attribute
        
        Array Attribute
        
        Boolean Attribute
        
        Dictionary Attribute
        
        Elements Attributes
        
        Dense Elements Attribute
        
        Opaque Elements Attribute
        
        Sparse Elements Attribute
        
        Float Attribute
        
        Integer Attribute
        
        Integer Set Attribute
        
        String Attribute
        
        Symbol Reference Attribute
        
        Type Attribute
        
        Unit Attribute
      - Pass Infrastructure
        
        Operation Pass
        
        In MLIR, the main unit of abstraction and transformation is an operation
        
        The pass manager is designed to work on instances of operations at different levels of nesting
        
        All passes in MLIR derive from OperationPass
        
        Restrictions
        
        Restrction 1
        
        Modify anything within the parent block/region/operation/etc, outside of the current operation being operated on
        
        This includes adding or removing operations from the parent block.
        
        Restriction 2
        
        Maintain pass state across invocations of runOnOperation
        
        A pass may be run on several different operations with no guarantee of execution order
        
        When multithreading, a specific pass instance may not even execute on all operations within the module
        
        As such, a pass should not rely on running on all operations.
        
        Restriction 3
        
        Modify the state of another operation not nested within the current operation being operated on
        
        Other threads may be operating on different operations within the module simultaneously
        
        Restriction 4
        
        Maintain any global mutable state, e.g. static variables within the source file
        
        All mutable state should be maintained by an instance of the pass.
        
        Restriction 5
        
        Must be copy-constructible, multiple instances of the pass may be created by the pass manager to process operations in parallel
        
        Restriction 6
        
        Inspect the IR of sibling operations
        
        Other threads may be modifying these operations in parallel
        
        Types
        
        Op-Specific
        
        An op-specific operation pass operates explicitly on a given operation type
        
        This operation type must adhere to the restrictions set by the pass manager for pass execution
        
        Adherence
        
        Inherit from the CRTP class OperationPass and provide the operation type as an additional template parameter.
        
        Override the virtual void runOnOperation() method
        
        Op-Agnostic
        
        An op-agnostic pass operates on the operation type of the pass manager that it is added to.
        
        This means that a pass that operates on several different operation types in the same way only needs one implementation.
        
        Adherence
        
        Inherit from the CRTP class OperationPass
        
        Override the virtual void runOnOperation() method
        
        Passes represent the basic infrastructure for transformation and optimization
        
        Analysis Management
        
        Conceptually similar to transformation passes, except that they compute information on a specific operation without modifying it
        
        In MLIR, analyses are not passes but free-standing classes that are computed lazily on-demand and cached to avoid unnecessary recomputation
        
        Adherence
        
        Provide a valid constructor taking an Operation*
        
        Must not modify the given operation
        
        Hooks to control various behavior
        
        bool isInvalidated(const AnalysisManager::PreservedAnalyses &)
        
        Given a preserved analysis set, the analysis returns true if it should truly be invalidated
        
        This allows for more fine-tuned invalidation in cases where an analysis wasn’t explicitly marked preserved, but may be preserved (or invalidated) based upon other properties such as analyses sets
        
        Querying Analyses
        
        The base OperationPass class provides utilities for querying and preserving analyses for the current operation being processed
        
        Utilities
        
        getAnalysis<>
        
        Get an analysis for the current operation, constructing it if necessary.
        
        getCachedAnalysis<>
        
        Get an analysis for the current operation, if it already exists.
        
        getCachedParentAnalysis<>
        
        Get an analysis for a given parent operation, if it exists
        
        getChildAnalysis<>
        
        Get an analysis for a given child operation, constructing it if necessary
        
        getCachedChildAnalysis<>
        
        Get an analysis for a given child operation, if it exists.
        
        Preserving Analyses
        
        Analyses that are constructed after being queried by a pass are cached to avoid unnecessary computation if they are requested again later
        
        To avoid stale analyses, all analyses are assumed to be invalidated by a pass
        
        To avoid invalidation, a pass must specifically mark analyses that are known to be preserved.
        
        Utilities
        
        markAllAnalysesPreserved
        
        markAnalysesPreserved<>
        
        Pass Failure
        
        Passes in MLIR are allowed to gracefully fail
        
        This may happen if some invariant of the pass was broken, potentially leaving the IR in some invalid state
        
        If such a situation occurs, the pass can directly signal a failure to the pass manager
        
        If a pass signaled a failure when executing, no other passes in the pipeline will execute and the PassManager::run will return failure
        
        Failure signaling is provided in the form of a signalPassFailure method
        
        Pass Manager
        
        The PassManager class is used to configure and run a pipeline
        
        OpPassManager
        
        The OpPassManager class is used to schedule passes to run at a specific level of nesting
        
        An OpPassManager is essentially a collection of passes to execute on an operation of a given type
        
        Operation Type Adherence
        
        Must be registered and marked IsolatedFromAbove
        
        Passes are expected to not modify operations at or above the current operation being processed
        
        If the operation is not isolated, it may inadvertently modify the use-list of an operation it is not supposed
        
        Passes can be added to a pass manager via addPass
        
        The pass must either be an op-specific pass operating on the same operation type as OpPassManager, or an op-agnostic pass
        
        An OpPassManager cannot be created directly, but must be explicitly nested within another OpPassManager via the nest<> method
        
        This method takes the operation type that the nested pass manager will operate on
        
        At the top-level, a PassManager acts as an OpPassManager that operates on the module operation
        
        Nesting in this sense, corresponds to the structural nesting within Regions of the IR
        
        Pipelines are then run over a single operation at a time
        
        Benefits
        
        This improves the cache behavior of the compiler, because it is only touching a single function at a time, instead of traversing the entire program
        
        This improves multi-threading performance by reducing the number of jobs that need to be scheduled, as well as increasing the efficiency of each job. An entire function pipeline can be run on each function asynchronously.
        
        Registration
        
        Pass Registration
        
        Registering a pass class takes the form
        
        static PassRegistration<MyPass> pass("command-line-arg", "description");
        
        MyPass is the name of the derived pass class
        
        “command-line-arg” is the argument to use on the command line to invoke the pass from mlir-opt
        
        “description” is a description of the pass
        
        For passes that cannot be default-constructed, PassRegistration accepts an optional third argument that takes a callback to create the pass
        
        static PassRegistration<MyParametricPass> pass(
        "command-line-arg", "description",
        -> std::unique_ptr<Pass> {
        std::unique_ptr<Pass> p = std::make_unique<MyParametricPass>(/options/);
        /... non-trivial-logic to configure the pass .../;
        return p;
        });
        
        PassRegistration class is a utility to register derived pass classes so that they may be created, and inspected, by utilities like mlir-opt.
        
        Pass Pipeline Registration
        
        MLIR allows for registering custom pass pipelines
        
        This allows for custom pipelines to be available to tools like mlir-opt in the same way that passes are, which is useful for encapsulating common pipelines like the “-O1” series of passes
        
        PassPipelineRegistration
        
        void pipelineBuilder(OpPassManager &pm) {
        pm.addPass(std::make_unique<MyPass>());
        pm.addPass(std::make_unique<MyOtherPass>());
        }
        
        static PassPipelineRegistration<> pipeline(
        "command-line-arg", "description", pipelineBuilder);
        
        static PassPipelineRegistration<> pipeline(
        "command-line-arg", "description", {
        pm.addPass(std::make_unique<MyPass>());
        pm.addPass(std::make_unique<MyOtherPass>());
        });
        
        Textual Pass Pipeline Specification
        
        Syntax
        
        pipeline ::= op-name ( pipeline-element (, pipeline-element)* )
        
        pipeline-element ::= pipeline | (pass-name | pass-pipeline-name) options?
        
        options ::= '{' (key ('=' value)?)+ '}'
        
        op-name
        
        1 more item...
        
        pass-name | pass-pipeline-name
        
        1 more item...
        
        options
        
        1 more item...
      - Dialect Conversion
        
        MLIR provides a framework in which to perform operation conversions between, and within dialects
        
        This framework allows for transforming illegal operations to those supported by a provided conversion target, via a set of pattern-based operation rewriting patterns.
        
        Modes of Conversion
        
        Full Conversion
        
        A full conversion legalizes all input operations, and is only successful if all operations are properly legalized to the given conversion target.
        
        This ensures that only known operations will exist after the conversion process.
        
        A full conversion can be applied via applyFullConversion
        
        Analysis Conversion
        
        An analysis conversion will analyze which operations are legalizable to the given conversion target if a conversion were to be applied.
        
        This is done by performing a ‘partial’ conversion and recording which operations would have been successfully converted if successful
        
        No rewrites, or transformations, are actually applied to the input operations.
        
        An analysis conversion can be applied via applyAnalysisConversion
        
        Partial Conversion
        
        A partial conversion will legalize as many operations to the target as possible, but will allow pre-existing operations that were not explicitly marked as “illegal” to remain unconverted.
        
        This allows for partially lowering parts of the input in the presence of unknown operations.
        
        A partial conversion can be applied via applyPartialConversion
        
        Conversion Target
        
        The conversion target is a formal definition of what is considered to be legal during the conversion process.
        
        The final operations generated by the conversion framework must be marked as legal on the ConversionTarget for the rewrite to be a success
        
        Depending on the conversion mode, existing operations need not always be legal.
        
        Legality
        
        Legality Actions
        
        Legal
        
        This action signals that every instance of a given operation is legal, i.e. any combination of attributes, operands, types, etc. are valid
        
        Dynamic
        
        This action signals that only some instances of a given operation are legal.
        
        This allows for defining fine-tune constraints, e.g. saying that addi is only legal when operating on 32-bit integers
        
        If a specific handler is not provided when setting the action, the target must override the isDynamicallyLegal hook provided by ConversionTarget
        
        Illegal
        
        This action signals that no instance of a given operation is legal.
        
        Operations marked as “illegal” must always be converted for the conversion to be successful
        
        This action also allows for selectively marking specific operations as illegal in an otherwise legal dialect
        
        Recursive Legality
        
        In some cases, it may be desirable to mark entire regions as legal.
        
        This provides an additional granularity of context to the concept of “legal”.
        
        If an operation is marked recursively legal, either statically or dynamically, then all of the operations nested within are also considered legal even if they would otherwise be considered “illegal”
        
        An operation can be marked via markOpRecursivelyLegal<>
        
        Rewrite Pattern Specification
        
        A set of legalization patterns must be provided to transform illegal operations into legal ones.
        
        The patterns provided do not need to generate operations that are directly legal on the target
        
        The framework will automatically build a graph of conversions to convert non-legal operations into a set of legal ones.
        
        Conversion Patterns
        
        Along with the general RewritePattern classes, the conversion framework provides a special type of rewrite pattern that can be used when a pattern relies on interacting with constructs specific to the conversion process, the ConversionPattern
        
        The conversion process does not necessarily update operations in-place and instead creates a mapping of events such as replacements and erasures, and only applies them when the entire conversion process is successful.
        
        Certain classes of patterns rely on using the updated/remapped operands of an operation, such as when the types of results defined by an operation have changed.
        
        The general Rewrite Patterns can no longer be used in these situations, as the types of the operands of the operation being matched will not correspond with those expected by the user.
        
        This pattern provides, as an additional argument to the matchAndRewrite and rewrite methods, the list of operands that the operation should use after conversion.
        
        If an operand was the result of a non-converted operation, for example if it was already legal, the original operand is used.
        
        This means that the operands provided always have a 1-1 non-null correspondence with the operands on the operation.
        
        The original operands of the operation are still intact and may be inspected as normal.
        
        These patterns also utilize a special PatternRewriter, ConversionPatternRewriter, that provides special hooks for use with the conversion infrastructure.
        
        Type Safety
        
        The types of the remapped operands provided to a conversion pattern must be of a type expected by the pattern.
        
        The expected types of a pattern are determined by a provided TypeConverter
        
        If no type converter is provided, the types of the remapped operands are expected to match the types of the original operands
        
        If a type converter is provided, the types of the remapped operands are expected to be legal as determined by the converter
        
        If the remapped operand types are not of an expected type, and a materialization to the expected type could not be performed, the pattern fails application before the matchAndRewrite hook is invoked
        
        This ensures that patterns do not have to explicitly ensure type safety, or sanitize the types of the incoming remapped operands
        
        Type Conversion
        
        It is sometimes necessary as part of a conversion to convert the set types of being operated on.
        
        In these cases, a TypeConverter object may be defined that details how types should be converted when interfacing with a pattern
        
        A TypeConverter may be used to convert the signatures of block arguments and regions, to define the expected inputs types of the pattern, and to reconcile type differences in general
        
        Type Converter
        
        The TypeConverter contains several hooks for detailing how to convert types, and how to materialize conversions between types in various situations.
        
        Aspects
        
        Conversion
        
        If the source type is already “legal”, it should convert to itself
        
        Type conversions are specified via the addConversion method.
        
        A conversion describes how a given illegal source Type should be converted to N target types.
        
        Materialization
        
        A materialization describes how a set of values should be converted to a single value of a desired type
        
        An important distinction with a conversion is that a materialization can produce IR, whereas a conversion cannot
        
        materializations are used by the conversion framework to ensure type safety during the conversion process
        
        Types
        
        3 more items...
        
        Region Signature Conversion
        
        From the perspective of type conversion, the types of block arguments are a bit special
        
        Throughout the conversion process, blocks may move between regions of different operations
        
        Given this, the conversion of the types for blocks must be done explicitly via a conversion pattern
        
        To convert the types of block arguments within a Region, a custom hook on the ConversionPatternRewriter must be invoked; convertRegionTypes
        
        This hook uses a provided type converter to apply type conversions to all blocks within a given region, and all blocks that move into that region
        
        the conversions performed by this method use the argument materialization hook on the TypeConverter
        
        This hook also takes an optional TypeConverter::SignatureConversion parameter that applies a custom conversion to the entry block of the region
        
        The types of the entry block arguments are often tied semantically to details on the operation
        
        To convert the signature of just the region entry block, and not any other blocks within the region, the applySignatureConversion hook may be used instead
      - Creating a Dialect
        
        Public Dialect Directory Structure
        
        mlir/lib/Dialect/Foo/IR (for operations)
        
        The ‘IR’ directory typically contains implementations of functions for the dialect which are not automatically generated by ODS
        
        These are typically defined in FooDialect.cpp, which includes FooOps.cpp.inc and FooOpsInterfaces.h.inc
        
        mlir/lib/Dialect/Foo/Transforms (for transforms)
        
        The ‘Transforms’ directory contains rewrite rules for the dialect, typically described in TableGen file using the DDR format
        
        mlir/lib/Dialect/Foo (for sources)
        
        mlir/test/Dialect/Foo (for tests)
        
        mlir/include/mlir/Dialect/Foo (for public include files)
        
        Along with other public headers, the ‘include’ directory contains a TableGen file in the ODS format , describing the operations in the dialect.
        
        This is used to generate operation declarations (FooOps.h.inc) and definitions (FooOps.cpp.inc) and operation interface declarations (FooOpsInterfaces.h.inc) and definitions (FooOpsInterfaces.cpp.inc).
      - Operation Definition Specification(ODS)
        
        MLIR supports defining operations in a table-driven manner
        
        This is achieved via TableGen , which is both a generic language and its tooling to maintain records of domain-specific information
        
        Facts regarding an operation are specified concisely into a TableGen record, which will be expanded into an equivalent mlir::Op C++ template specialization at compiler build time
        
        MLIR allows pluggable dialects, and dialects contain, among others, a list of operations
        
        This open and extensible ecosystem leads to the “stringly” type IR problem, e.g., repetitive string comparisons during optimization and analysis passes, unintuitive accessor methods (e.g., generic/error prone getOperand(3) vs self-documenting getStride()) with more generic return types, verbose and generic constructors without default arguments, verbose textual IR dump, and so on
        
        Operation verification is
        
        best case: a central string-to-verification-function map
        
        middle case: duplication of verification across the code base
        
        worst case: no verification functions
        
        The fix is to support defining ops in a table-driven manner
        
        Then for each dialect, we can have a central place that contains everything you need to know about each op, including its constraints, custom assembly form, etc.
        
        This description is also used to generate helper functions and classes to allow building, verification, parsing, printing, analysis, and many more
        
        Benefits
        
        Single source of truth
        
        We strive to encode all facts regarding an operation into the record, so that readers don’t need to jump among code snippets to fully understand an operation
        
        Removing boilerplate
        
        We can automatically generate operand/attribute/result getter methods, operation build methods, operation verify methods, and many more utilities from the record
        
        This greatly reduces the boilerplate needed for defining a new op
        
        Facilitating auto-generation
        
        The usage of these operation information records are by no means limited to op definition itself
        
        We can use them to drive the auto-generation of many other components, like computation graph serialization.
        
        TableGen Syntax
        
        TableGen class is similar to C++ class; it can be templated and subclassed
        
        TableGen def is similar to C++ object; it can be declared by specializing a TableGen class (e.g., def MyDef : MyClass<...>;) or completely independently (e.g., def MyDef;). It cannot be further templated or subclassed
        
        dag
        
        TableGen dag is a dedicated type for directed acyclic graph of elements
        
        A dag has one operator and zero or more arguments
        
        Its syntax is (operator arg0, arg1, argN).
        
        The operator can be any TableGen def; an argument can be anything, including dag itself
        
        We can have names attached to both the operator and the arguments like (MyOp:$op_name MyArg:$arg_name).
        
        Operation Definition
        
        MLIR defines several common constructs to help operation definition and provide their semantics via a special TableGen backend : OpDefinitionsGen
        
        These constructs are defined in OpBase.td
        
        The main ones are
        
        The Op class: It is the main construct for defining operations. All facts regarding the operation are specified when specializing this class, with the help of the following constructs.
        
        The Dialect class: Operations belonging to one logical group are placed in the same dialect. The Dialect class contains dialect-level information
        
        The OpTrait class hierarchy: They are used to specify special properties and constraints of the operation, including whether the operation has side effect or whether its output has the same shape as the input
        
        The ins/outs marker: These are two special makers builtin to the OpDefinitionsGen backend. They lead the definitions of operands/attributes and results respectively
        
        The TypeConstraint class hierarchy: They are used to specify the constraints over operands or results. A notable subclass hierarchy is Type, which stands for constraints for common C++ types.
        
        The AttrConstraint class hierarchy: They are used to specify the constraints over attributes. A notable subclass hierarchy is Attr, which stands for constraints for attributes whose values are of common types
        
        Operation name
        
        The operation name is a unique identifier of the operation within MLIR
        
        This is the equivalent of the mnemonic in assembly language
        
        It is used for parsing and printing in the textual format
        
        It is also used for pattern matching in graph rewrites
        
        The full operation name is composed of the dialect name and the op name, with the former provided via the dialect and the latter provided as the second template parameter to the Op class
        
        Operation documentation
        
        This includes both a one-line summary and a longer human-readable description
        
        They will be used to drive automatic generation of dialect documentation
        
        They need to be provided in the operation’s definition body
        
        Syntax
        
        let summary = "...";
        
        let description = [{
        ...
        }];
        
        description should be written in Markdown syntax
        
        Place documentation at the beginning of the operation definition
        
        The summary should be short and concise. It should be a one-liner without trailing punctuation. Put expanded explanation in description.
        
        Operation arguments
        
        Types
        
        operands
        
        Operands are runtime values produced by other ops
        
        attributes
        
        attributes are compile-time known constant values
        
        Types
        
        2 more items...
        
        Both operands and attributes are specified inside the dag-typed arguments, led by ins
        
        Syntax
        
        let arguments = (ins
        <type-constraint>:$<operand-name>,
        ...
        <attr-constraint>:$<attr-name>,
        ...
        );
        
        There is no requirements on the relative order of operands and attributes; they can mix freely.
        
        The relative order of operands themselves matters
        
        From each named argument a named getter will be generated that returns the argument with the return type (in the case of attributes the return type will be constructed from the storage type, while for operands it will be Value).
        
        Each attribute’s raw value (e.g., as stored) can also be accessed via generated <name>Attr getters for use in transformation passes where the more user friendly return type is less suitable
        
        All the arguments should be named to
        
        provide documentation
        
        drive auto-generation of getter methods
        
        provide a handle to reference for other places like constraints
        
        Variadic operands
        
        To declare a variadic operand, wrap the TypeConstraint for the operand with Variadic<...>
        
        Normally operations have no variadic operands or just one variadic operand
        
        For the latter case, it is easy to deduce which dynamic operands are for the static variadic operand definition
        
        Though, if an operation has more than one variable length operands (either optional or variadic), it would be impossible to attribute dynamic operands to the corresponding static variadic operand definitions without further information from the operation
        
        Therefore, either the SameVariadicOperandSize or AttrSizedOperandSegments trait is needed to indicate that all variable length operands have the same number of dynamic values
        
        Optional operands
        
        To declare an optional operand, wrap the TypeConstraint for the operand with Optional<...>
        
        Normally operations have no optional operands or just one optional operand. For the latter case, it is easy to deduce which dynamic operands are for the static operand definition
        
        Though, if an operation has more than one variable length operands (either optional or variadic), it would be impossible to attribute dynamic operands to the corresponding static variadic operand definitions without further information from the operation
        
        Therefore, either the SameVariadicOperandSize or AttrSizedOperandSegments trait is needed to indicate that all variable length operands have the same number of dynamic values
      - Table-driven Declarative Rewrite Rule (DRR)
        
        In addition to subclassing the mlir::RewritePattern C++ class, MLIR also supports defining rewrite rules in a declarative manner
        
        This is achieved via TableGen
        
        The rewrite rules are specified concisely in a TableGen record, which will be expanded into an equivalent mlir::RewritePattern subclass at compiler build time
        
        Benefits
        
        Being declarative
        
        The pattern creator just needs to state the rewrite pattern declaratively, without worrying about the concrete C++ methods to call
        
        Removing boilerplate and showing
        the very essence of the rewrite
        
        mlir::RewritePattern is already good at hiding boilerplate for defining a rewrite rule
        
        But we still need to write the class and function structures required by the C++ programming language, inspect ops for matching, and call op build() methods for constructing
        
        These statements are typically quite simple and similar, so they can be further condensed with auto-generation
        
        Because we reduce the boilerplate to the bare minimum, the declarative rewrite rule will just contain the very essence of the rewrite
        
        This makes it very easy to understand the pattern
        
        Strengths and Limitations
        
        operation-based
        
        it describes a rule to match against a directed acyclic graph (DAG) of operations and generate DAGs of operations
        
        it is good at expressing op to op conversions
        
        Limitations
        
        Matching and generating ops with regions.
        
        Matching and generating ops with block arguments.
        
        Matching multi-result ops in nested patterns.
        
        Matching and generating variadic operand/result ops in nested patterns.
        
        Packing and unpacking variadic operands/results during generation.
        
        NativeCodeCall returning more than one results.
        
        Rule Definition
        
        Core Construct
        
        class Pattern<
        dag sourcePattern, list<dag> resultPatterns,
        list<dag> additionalConstraints = [],
        dag benefitsAdded = (addBenefit 0)>;
        
        A declarative rewrite rule contains two main components:
        
        A source pattern, which is used for matching a DAG of operations
        
        One or more result patterns, which are used for generating DAGs of operations to replace the matched DAG of operations.
        
        We allow multiple result patterns to support multi-result ops and auxiliary ops , but frequently we just want to convert one DAG of operations to another DAG of operations
        
        There is a handy wrapper of Pattern, Pat, which takes a single result pattern
        
        class Pat<
        dag sourcePattern, dag resultPattern,
        list<dag> additionalConstraints = [],
        dag benefitsAdded = (addBenefit 0)> :
        Pattern<sourcePattern, [resultPattern], additionalConstraints, benefitAdded>;
        
        Source Pattern
        
        The source pattern is for matching a DAG of operations
        
        Arguments in the dag object are intended to capture the op arguments
        
        They can also be used to further limit the match criteria
        
        The capturing is done by specifying a symbol starting with the $ sign, while further constraints are introduced by specifying a TypeConstraint (for an operand) or a AttrConstraint (for an attribute)
        
        Binding op arguments and limiting the match
        
        Matching DAG of operations
        
        Result pattern
        
        The result pattern is for generating a DAG of operations
        
        Arguments in the dag object are intended to reference values captured in the source pattern and potentially apply transformations
        
        Referencing bound symbols
        
        Building operations
        
        Generating DAG of operations
        
        Binding op results
        
        NativeCodeCall: transforming the generated op
        
        NativeCodeCall placeholders
        
        Customizing entire op building
        
        Supporting auxiliary ops
        
        Supporting multi-result ops
      - Usage
        
        Define multiple outputs from a function
        
        %result:2
        
        Using
        
        %result#0
        
        %result#1
        
        ! Usage
        
        Type Alias
        
        Example
        
        !avx_m128 = type vector<4 x f32>
        
        "foo"(%x) : !avx_m128 -> ()
        
        @ Usage
        
        symbol-ref-id ::= `@` (suffix-id | string-literal)
        
        Examples
        
        function-signature ::= symbol-ref-id ( argument-list )
        (-> function-result-list)?
        
        symbol-ref-attribute ::= symbol-ref-id (:: symbol-ref-id)*
        
        module ::= module symbol-ref-id? (attributes attribute-dict)? region
        
        % Usage
        
        Defining Variables
      - Identifiers and keywords
        
        Syntax
        
        bare-id ::= (letter|[_]) (letter|digit|[_$.])*
        
        bare-id-list ::= bare-id (`,` bare-id)*
        
        suffix-id ::= (digit+ | ((letter|id-punct) (letter|id-punct|digit)*))
        
        value-id ::= `%` suffix-id
        
        symbol-ref-id ::= `@` (suffix-id | string-literal)
        
        value-id-list ::= value-id (`,` value-id)*
        
        value-use ::= value-id
        
        value-use-list ::= value-use (`,` value-use)*
        
        Identifiers name entities such as values, types and functions, and are chosen by the writer of MLIR code
        
        Identifiers may be descriptive (e.g. %batch_size, @matmul), or may be non-descriptive when they are auto-generated (e.g. %23, @func42)
        
        Identifier names for values may be used in an MLIR text file but are not persisted as part of the IR - the printer will give them anonymous names like %42
        
        MLIR guarantees identifiers never collide with keywords by prefixing identifiers with a sigil (e.g. %, #, @, ^, !)
        
        In certain unambiguous contexts (e.g. affine expressions), identifiers are not prefixed, for brevity
        
        New keywords may be added to future versions of MLIR without danger of collision with existing identifiers
        
        Value identifiers are only in scope for the (nested) region in which they are defined and cannot be accessed or referenced outside of that region
        
        Argument identifiers in mapping functions are in scope for the mapping body
        
        Particular operations may further limit which identifiers are in scope in their regions
        
        Function identifiers and mapping identifiers are associated with Symbols and have scoping rules dependent on symbol attributes
        
        Common syntax
        
        Syntax
        
        digit ::= [0-9]
        
        hex_digit ::= [0-9a-fA-F]
        
        letter ::= [a-zA-Z]
        
        id-punct ::= [$._-]
        
        integer-literal ::= decimal-literal | hexadecimal-literal
        
        decimal-literal ::= digit+
        
        hexadecimal-literal ::= 0x hex_digit+
        
        float-literal ::= [-+]?[0-9]+[.][0-9]*([eE][-+]?[0-9]+)?
        
        string-literal ::= " [^"\n\f\v\r]* " TODO: define escaping rules
      - Toy Language
        
        Learnings
        
        ODS verify C++ blob
    - - Documents
        
        Intro
        
        Language Reference
      - Concepts
        
        Records
        
        Types
        
        Abstract Records/Classes
        
        Purpose
        
        In order to reduce the complexity of TableGen files, classes are used to abstract out groups of record fields.
        
        Example
        
        3 more items...
        
        Hierarchy
        
        TableGen allows an arbitrary hierarchy of classes
        
        Abstract classes for two concepts can share a third superclass that abstracts common “sub-concepts” from the two original concepts
        
        Concrete Records/Records
        
        Names
        
        Name is associated with
        
        An optional list of superclasses
        
        A list of fields with values
        
        The fields are the primary data that backends will process
        
        TableGen assigns no meanings to fields
        
        The meanings are entirely up to the backends and the programs that incorporate the output of those backends
        
        Both classes and concrete records can include fields that are uninitialized
        
        The uninitialized “value” is represented by a question mark (?).
        
        Classes often have uninitialized fields that are expected to be filled in when those classes are inherited by concrete records.
        
        Even so, some fields of concrete records may remain uninitialized.
        
        Records have a unique name chosen by programmer or tablegen
        
        Template Arguments
        
        In order to make classes more useful, a concrete record (or another class) can request a class as a superclass and pass template arguments to it
        
        These template arguments can be used in the fields of the superclass to initialize them in a custom manner
        
        record or class A can request superclass S with one set of template arguments, while record or class B can request S with a different set of arguments
        
        Without template arguments, many more classes would be required, one for each combination of the template arguments.
        
        Multiclass
        
        TableGen provides multiclasses to collect a group of record definitions in one place
        
        A multiclass is a sort of macro that can be “invoked” to define multiple concrete records all at once
        
        A multiclass can inherit from other multiclasses, which means that the multiclass inherits all the definitions from its parent multiclasses.
        
        Backend
        
        A backend processes some subset of the concrete records built by the TableGen parser and emits the output files.
        
        These files are usually C++ .inc files that are included by the programs that require the data in those records.
        
        a backend can produce any type of output files.
      - Source Files
        
        TableGen source files are plain ASCII text files. The files can contain statements, comments, and blank lines
        
        The standard file extension for TableGen files is .td
        
        Includes
        
        there is an include mechanism that allows one file to include the content of another file
        
        Pre-Processing
        
        TableGen supports a simple preprocessor that can be used to conditionalize portions of .td files
      - Lexical Analysis
        
        The lexical and syntax notation used here is intended to imitate Python’s notation
        
        In particular, for lexical definitions, the productions operate at the character level and there is no implied whitespace between elements
        
        The syntax definitions operate at the token level, so there is implied whitespace between tokens.
        
        Formfeed characters may be used freely in files to produce page breaks when the file is printed for review.
        
        TableGen also provides simple Preprocessing Facilities.
        
        Punctuation Characters
        
        [ ] { } ( ) < > : ; . = ? #
        
        Comments
        
        BCPL-style comments //
        
        Nestable C-style comments (/ ... /).
        
        Literals
        
        Numeric literals
        
        Syntax
        
        DecimalInteger ::= ["+" | "-"] ("0"..."9")+
        
        HexInteger ::= "0x" ("0"..."9" | "a"..."f" | "A"..."F")+
        
        BinInteger ::= "0b" ("0" | "1")+
        
        TokInteger ::= DecimalInteger | HexInteger | BinInteger
        
        string literals
        
        Syntax
        
        TokCodeFragment ::= "[{" (shortest text not containing "}]") "}]"
        
        TokString ::= '"' (non-'"' characters and escapes) '"'
        
        Escape Sequence
        
        \\ \' \" \t \n
        
        Identifiers
        
        Syntax
        
        ualpha ::= "a"..."z" | "A"..."Z" | "_"
        
        TokIdentifier ::= ("0"..."9") * ualpha (ualpha | "0"..."9")*
        
        TokVarName ::= "$" ualpha (ualpha | "0"..."9")*
        
        Reserved Keywords
        
        bit bits class code dag
        def else foreach defm defset
        defvar field if in include
        int let list multiclass string
        then
        
        Bang operators
        
        Syntax
        
        BangOperator ::= one of
        !add !and !cast !con !dag
        !empty !eq !foldl !foreach !ge
        !getop !gt !head !if !isa
        !le !listconcat !listsplat !lt !mul
        !ne !or !setop !shl !size
        !sra !srl !strconcat !subst !tail
        
        CondOperator ::= !cond
        
        Include files
        
        Syntax
        
        IncludeDirective ::= "include" TokString
        
        preprocessor directives
        
        PreprocessorDirective ::= "#define" | "#ifdef" | "#ifndef"
        
        Types
        
        Syntax
        
        Type ::= "bit" | "int" | "string" | "code" | "dag"
        | "bits" "<" TokInteger ">"
        | "list" "<" Type ">"
        | ClassID
        
        ClassID ::= TokIdentifier
        
        The TableGen language is statically typed, using a simple but complete type system.
        
        Uses
        
        check for errors
        
        perform implicit conversions
        
        help interface designers constrain the allowed input
        
        Every value is required to have an associated type
        
        Categories
        
        low-level types (e.g., bit)
        
        high-level types (e.g., dag)
        
        List
        
        bit
        
        int
        
        string
        
        code
        
        bits<n>
        
        list<type>
        
        dag
        
        ClassID
      - Values and Expressions
        
        Values
        
        Syntax
        
        Value ::= SimpleValue ValueSuffix*
        
        ValueSuffix ::= "{" RangeList "}"
        | "[" RangeList "]"
        | "." TokIdentifier
        
        RangeList ::= RangePiece ("," RangePiece)*
        
        RangePiece ::= TokInteger
        | TokInteger "..." TokInteger
        | TokInteger "-" TokInteger
        | TokInteger TokInteger
        
        Simple values
        
        Syntax
        
        SimpleValue ::= TokInteger | TokString+ | TokCodeFragment
        
        SimpleValue3 ::= "{" [ValueList] "}"
        
        ValueList ::= ValueListNE
        
        ValueListNE ::= Value ("," Value)*
        
        SimpleValue2 ::= "?"
        
        A value can be an integer literal, a string literal, or a code fragment literal.
        
        Multiple adjacent string literals are concatenated as in C/C++; the simple value is the concatenation of the strings.
        
        Code fragments become strings and then are indistinguishable from them.
        
        Suffixed values
        
        SimpleValue can be specified with certain suffixes.
        
        The purpose of a suffix is to obtain a subvalue of the primary value. Here are the possible suffixes for some primary value.
        
        Examples
        
        value{17}
        
        The final value is bit 17 of the integer value (note the braces)
        
        value{8..15}
        
        The final value is bits 8–15 of the integer value. The order of the bits can be reversed by specifying {15..8}.
        
        value[4..7,17,2..3,4]
        
        The final value is a new list that is a slice of the list value (note the brackets). The new list contains elements 4, 5, 6, 7, 17, 2, 3, and 4.
        
        value. field
        
        The final value is the value of the specified field in the specified record value.
      - Statements
        
        Syntax
        
        TableGenFile ::= Statement*
        
        Statement ::= Class | Def | Defm | Defset | Defvar | Foreach
        | If | Let | MultiClass
        
        statements may appear at the top level of TableGen source files.
        
        class
        
        Syntax
        
        Class ::= "class" ClassID [TemplateArgList] RecordBody
        
        TemplateArgList ::= "<" TemplateArgDecl ("," TemplateArgDecl)* ">"
        
        TemplateArgDecl ::= Type TokIdentifier ["=" Value]
        
        Template Parameters
        
        These template arguments are specified each time the class is inherited by another class or record.
        
        A class can be parameterized by a list of “template arguments,” whose values can be used in the class’s record body.
        
        If a template argument is not assigned a default value with =, it is uninitialized (has the “value” ?) and must be specified in the template argument list when the class is inherited.
        
        If an argument is assigned a default value, then it need not be specified in the argument list.
        
        The template argument default values are evaluated from left to right.
        
        RecordBody can include a list of superclasses from which the current class inherits, along with field definitions and other statements.
        
        When a class C inherits from another class D, the fields of D are effectively merged into the fields of C.
        
        A given class can only be defined once.
        
        A class statement is considered to define the class if any of the following are true
        
        The TemplateArgList is present
        
        The ParentClassList in the RecordBody is present
        
        The Body in the RecordBody is present and not empty
        
        Empty Class
        
        You can declare an empty class by specifying an empty TemplateArgList and an empty RecordBody
        
        This can serve as a restricted form of forward declaration
        
        records derived from a forward-declared class will inherit no fields from it, because those records are built when their declarations are parsed, and thus before the class is finally defined.
        
        NAME
        
        Every class has an implicit template argument named NAME (uppercse), which is bound to the name of the Def or Defm inheriting the class
        
        The value of NAME is undefined if the class is inherited by an anonymous record
        
        Record Bodies
        
        Syntax
        
        RecordBody ::= ParentClassList Body
        
        ParentClassList ::= [":" ParentClassListNE]
        
        ParentClassListNE ::= ClassRef ("," ClassRef)*
        
        ClassRef ::= (ClassID | MultiClassID) ["<" ValueList ">"]
        
        Body ::= ";" | "{" BodyItem* "}"
        
        BodyItem ::= Type TokIdentifier ["=" Value] ";"
        | "let" TokIdentifier ["{" RangeList "}"] "=" Value ";"
        | "defvar" TokIdentifier "=" Value ";"
        
        Record bodies appear in both class and record definitions
        
        A record body can include a parent class list, which specifies the classes from which the current class or record inherits fields.
        
        Such classes are called the superclasses or parent classes of the class or record
        
        The record body also includes the main body of the definition, which contains the specification of the fields of the class or record.
        
        A ParentClassList containing a MultiClassID is valid only in the class list of a defm statement
        
        In that case, the ID must be the name of a multiclass.
        
        A field definition in the body specifies a field to be included in the class or record.
        
        If no initial value is specified, then the field’s value is uninitialized.
        
        The type must be specified; TableGen will not infer it from the value
        
        The let form is used to reset a field to a new value.
        
        This can be done for fields defined directly in the body or fields inherited from superclasses.
        
        A RangeList can be specified to reset certain bits in a bit<n> field
        
        defvar
        
        The defvar form defines a variable whose value can be used in other value expressions within the body.
        
        Variables are provided to hold temporary values while processing the body
        
        Concrete Records
        
        Syntax
        
        Def ::= "def" [NameValue] RecordBody
        
        NameValue ::= Value
        
        A def statement defines a new concrete record.
        
        name field
        
        The name value is optional.
        
        If specified, it is parsed in a special mode where undefined (unrecognized) identifiers are interpreted as literal strings.
        
        In particular, global identifiers are considered unrecognized
        
        These include global variables defined by defvar and defset
        
        If no name value is given, the record is anonymous.
        
        The final name of an anonymous record is unspecified but globally unique.
        
        Special handling occurs if a def appears inside a multiclass statement
        
        A record can inherit from one or more classes by specifying the ParentClassList clause at the beginning of its record body
        
        All of the fields in the parent classes are added to the record.
        
        If two or more parent classes provide the same field, the record ends up with the field value of the last parent class.
        
        As a special case, the name of a record can be passed in a template argument to that record’s superclasses
  - - - Tiling on Polytopes
- - - - Binary Codes
      - Binary Coded Decimal
      - TBD
    - - 1's Complement
        
        The ones' complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s)
        
        The ones' complement of the number then behaves like the negative of the original number in some arithmetic operations
        
        To within a constant (of −1), the ones' complement behaves like the negative of the original number with binary addition
        
        Unlike two's complement, these numbers have not seen widespread use because of issues such as the offset of −1, that negating zero results in a distinct negative zero bit pattern, less simplicity with arithmetic borrowing, etc
        
        Operations
        
        Subtractions by 1’s Complement
        
        Take 1’s complement of the subtrahend
        
        If the result of above addition has carry bit 1, then add it to the least significant bit (LSB) of given result
        
        If there is no carry bit 1, then take 1’s complement of the result which will be negative
        
        Number Systems
        
        Decimal
        
        Binary
        
        Hexadecimal
        
        0-9, A-F
        
        Octal
        
        Base-r
        
        The coefficients a j range in value from 0 to r – 1
        
        Base Conversion
        
        Integer Part
        
        Decimal to R
        
        Divide by R till quotient becomes 0
        
        Binary to Hex/Octal
        
        Group bits by 4/3
        
        Fraction Part
        
        Decimal to R
        
        Multiply by R till fraction becomes zero, which may or not happen(recurring decimal)
        
        Binary to Hex/Octal
        
        Group bits by 4/3
        
        Combinations
        
        Decimal To Binary
        
        Decimal To Hex
        
        Decimal To Octal
      - 2's Complement
      - Complements
        
        Types
        
        r's Complement
        
        r^n – N for N ≠ 0 and 0 for N = 0
        
        Given a positive number N in base r with an integer part of n digits
        
        (r-1)'s Complement
        
        Given a positive number N in base r with an integer part of n digits and a fraction part of m digits
        
        r^n - r^–m – N
        
        Complements are used in digital computers for simplifying the subtraction operation and for
        logical manipulations
    - - Consists of
        
        A set of operators
        
        Theorems, Axioms, Postulates
        
        Theorems
        
        Theorem 1
        
        x • x = x
        
        x + x = x
        
        Theorem 2
        
        x + 1 = 1
        
        x • 0 = 0
        
        Theorem 3, Involution
        
        (x′)′ = x
        
        Theorem 4, Associative
        
        x + (y + z) = (x + y) + z
        
        x(yz) = (xy) z
        
        Theorem 5, Demorgan
        
        (x + y)′ = x′ y′
        
        (xy)′ = x′ + y′
        
        Theorem 6, Absorption
        
        x + xy = x
        
        x(x + y) = x
        
        Postulates(Huntington)
        
        Postulate 2
        
        x + 0 = x
        
        x • 1 = x
        
        Postulate 3
        
        x + y = y + x
        
        xy = yx
        
        Postulate 4
        
        x (y + z) = xy + xz
        
        x + yz = (x + y) (x + z)
        
        A set of elements
        
        {0, 1}
        
        Properties
        
        Duality Principle
        
        Operator Precedence
        
        NOT
        
        AND
        
        Parentheses
        
        OR
      - Venn Diagram
      - Boolean Functions
        
        A Boolean function is an expression formed with
        binary variables, the two binary operators OR and AND, the unary operator NOT, parentheses, and equal sign
        
        Canonical Form
        
        Minterms
        
        Standard Product
        
        Sum of minterms
        
        Designated with m
        
        F(A,B,C) = ∑ (1,4, 5,6,7)
        
        Maxterms
        
        Standard Sum
        
        Product of maxterms
        
        Designated with M
        
        F(x,y,z) = ∏(0,2, 4, 5)
        
        Truth Table to Boolean Function
        
        A Boolean function may be expressed algebraically from a given truth table by forming a minterm for each combination of the variables which produces a 1 in the function, and then tak-
        ing the OR of all those terms.
        
        A Boolean function may be expressed algebraically from a given truth table by forming a maxterm for each combination of the variables which produces a 0 in the function, and then taking the AND of all those terms.
        
        Conversion between Canonical Forms
        
        the maxterm with subscript j is a complement of the minterm with the same subscript j
        
        Steps
        
        interchange the symbols ∑ and ∏
        
        list those numbers missing from the original form
        
        Standard Forms
        
        Terms may not contain all the literals
        
        Types
        
        Sum of Products
        
        Product of Sums
        
        Simplification of Boolean Functions
        
        Minimization
        
        Karnaugh map
        
        Representation
        
        Each square represents one minterm
        
        A Boolean function is recognized graphically in the map from the area enclosed by those squares whose minterms are included in the function.
        
        The map is a diagram made up of squares
        
        Minimization
        
        Group 1s by power of 2
        
        Remove the variables which are both 0 and 1 inside the group
        
        Handle Don't Cares
        
        Combine across edges
        
        3 more items...
        
        Implicants
        
        Prime Implicants
        
        Essential Prime Implicants
        
        Redundant Prime Implicants
        
        Selective Prime Implicants
        
        Tabulation Method
        
        Prime-implicants
      - Boolean Expressions
        
        F 7 = x +y
        
        OR
        
        F 8 = (x + y)′
        
        NOR
        
        x ↓ y
        
        F 6 = xy′ + x′y
        
        x or y but not both
        
        Exclusive-OR
        
        F 9 = xy + x′y′
        
        F 5 = y
        
        Transfer
        
        F 10 = y′
        
        F 4 = x′y
        
        y but not x
        
        y/x
        
        F 11 = x + y′
        
        If y then x
        
        x ⊂ y
        
        F 3 = x
        
        F 12 = x′
        
        F 2 = xy′
        
        x but not y
        
        x/y
        
        F 13 = x′ + y
        
        If x then y
        
        x ⊃ y
        
        F 1 = xy
        
        AND
        
        x and y
        
        F 14 = (xy)′
        
        NAND
        
        x↑y
        
        F 0 = 0
        
        F 15 = 1
      - Logic Gates
        
        AND, OR, NAND, NOR, exclusive-OR, and equivalence, are used as standard gates in digital design
        
        Extension to Multiple Inputs
        
        A gate can be extended to have multiple inputs if the binary operation it represents is
        commutative and associative
        
        NAND NOR multiple inputs
        
        x ↓ y ↓ z = (x + y + z)′
        
        x ↑ y ↑ z = (xyz)′
      - Logic
        
        Combinational
        
        Types
        
        Adders
        
        Full Adders
        
        Parallal Adder
        
        Half Adders
        
        Subtractor
        
        Half Subtractor
        
        Full Subtractor
        
        Code Converters
        
        Magnitude Comparator
        
        Decoder
        
        Demultiplexer
        
        Encoder
        
        Multiplexer
        
        Implementation
        
        Universal Gates
        
        NOR
        
        NAND
        
        Sequential
        
        Flip-Flops
        
        JK Flip-Flop
        
        D Flip-Flop
        
        SR Flip-Flop(Latch)
        
        T Flip-Flop
  - - - Microoperations
        
        The operations executed on data stored in registers are called microoperations
        
        A microoperation is an elementary operation performed on the information stored in one or more registers
        
        The result of the operation may replace the previous
        binary information of a register or may be transferred to another register
        
        Examples
        
        shift
        
        count
        
        clear
        
        load
        
        Categories
        
        Arithmetic
        
        ALU
        
        Logic
        
        Register Transfer
        
        Shift
      - Register Representation
        
        Computer registers are designated by capital letters (sometimes followed by numerals) to denote the function of the register
        
        The individual flip-flops in an n-bit register are num-
        bered in sequence from 0 through n — 1, starting from 0 in the rightmost position and increasing the numbers toward the left
        
        The most common way to represent a register is by a rectangular box with the name of the register inside
        
        Bit Representation
        
        The individual bits can be distinguished
        
        The numbering of bits in a 16-bit register can be marked on top of the box
        
        Bits 0 through 7 are assigned the symbol L (for low byte)
        
        Bits 8 through 15 are assigned the symbol H (for high byte)
        
        The symbol PC (0–7) or PC (L) refers to the low-order byte and PC(8–15) or PC(H ) to the high-order byte
      - Syntax
        
        Replacement Operator ←
        
        R2 ← R1
        
        denotes a transfer of the content of register R1 into register R2. It designates a replacement of the content of R 2 by the content of R1. By definition, the content of the source register R1 does not change after the transfer
        
        A statement that specifies a register transfer implies that circuits are available from the outputs of the source register to the inputs of the destination register and that the destination register has a parallel load capability
        
        BUS
        
        BUS ← C
        
        R1 ← BUS
        
        Control Function
        
        transfer to occurs under predetermined control condition P
        
        P : R2 ← R1
        
        It symbolizes the requirement that the transfer operation be executed by the hardware only if P = 1
        
        The control condition is terminated with a colon
        
        Comma
        
        Separates two microoperations
        
        T : R2 ← R1, R1 ← R2
    - - The sequence of microoperations performed on the binary information
        stored in the registers
      - The control that initiates the sequence of microoperations
      - The set of registers it contains and their function
    - - A typical digital computer has many registers, and paths must be provided to transfer information from one register to another
      - The number of wires will be excessive if separate lines are used between each register and all other registers in the system
      - A more efficient scheme for transferring information
        between registers in a multiple-register configuration is a common bus system
      - A bus structure consists of a set of common lines, one for each bit of a register, through which binary information is transferred one at a time
      - Control signals determine which register is selected by the bus during each particular register transfer
      - A bus system will multiplex k registers of n bits each to pro-
        duce an n-line common bus. The number of multiplexers needed to construct the bus is equal to n, the number of bits in each register. The size of each multiplexer must be k x 1 since it multiplexes k data lines
      - The transfer of information from a bus into one of many destination registers can be accomplished by connecting the bus lines to the inputs of all destination registers and activating the load control of the particular destination register selected
      - Three-State Bus Buffers
        
        A bus system can be constructed with three-state gates instead of multiplexers
        
        A three-state gate is a digital circuit that exhibits three states
        
        Two of the states are signals equivalent to logic 1 and 0 as in a conventional gate
        
        The third state is a high-impedance state
        
        The high-impedance state behaves like an open circuit, which means that the output is disconnected and does not have a logic significance
        
        Most commonly used in the design of a bus system is the buffer gate
        
        Control Input
        
        1
        
        Behave like a normal buffer
        
        0
        
        Output is disabled with high impedance state
        
        Because of this feature, a large number of three-state gate outputs can be connected with wires to form a common bus line without endangering loading effects
    - - Operations
        
        Read
        
        The transfer of information from a memory word to the outside environment is called a read operation
        
        Write
        
        The transfer of new information to be stored into the memory is
        called a write operation
      - Memory Representation
        
        The particular memory word among the many available is selected by the memory address during the transfer
        
        A memory word will be symbolized by the letter M
        
        It is necessary to specify the address of M when writing memory transfer operations
        
        This will be done by enclosing the address in square brackets following the letter M
        
        Examples
        
        Read
        
        The data are transferred to another register, called the data register, symbolized by DR
        
        Read: DR ← M [AR]
        
        Consider a memory unit that receives the address from a register, called the address register, symbolized by AR
        
        Write
        
        Assume that the input data are in register R1 and the address is in AR
        
        Write: M [AR] ← R1
- - - - Propositions
        
        A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both
        
        propositional variables (or sentential variables)
      - Truth Vaue
        
        True
        
        False
      - Atomic Propositions
      - Compound Propositions
      - Logical Operators
        
        Negation
        
        Connectives
        
        Exclusive Or
        
        Conjunction
        
        Disjunction
      - Conditional Statements
        
        Contrapositive
        
        Inverse
        
        Converse
      - Truth Table