Compiler Ontology

AI SEARCH

FLOW ALGEBRA — COMPILER ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/programming/compiler-ontology.html

FLOW COMPILER_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Programming"
    ONTOLOGY = "Compiler Ontology"
    PURPOSE = "Formalise compiler components, source-language processing, intermediate representations, semantic analysis, optimisation, code generation, diagnostics and compilation relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    COMPILER
    COMPILER_FRONT_END
    COMPILER_MIDDLE_END
    COMPILER_BACK_END
    SOURCE_LANGUAGE
    TARGET_LANGUAGE
    SOURCE_CODE
    SOURCE_FILE
    TOKEN
    LEXEME
    LEXER
    LEXICAL_ANALYSIS
    PARSER
    PARSING
    GRAMMAR
    ABSTRACT_SYNTAX_TREE
    AST_NODE
    SEMANTIC_ANALYSIS
    SYMBOL
    SYMBOL_TABLE
    IDENTIFIER
    SCOPE
    NAMESPACE
    BINDING
    TYPE
    TYPE_SYSTEM
    TYPE_CHECKING
    TYPE_INFERENCE
    INTERMEDIATE_REPRESENTATION
    IR
    CONTROL_FLOW_GRAPH
    BASIC_BLOCK
    DATA_FLOW
    STATIC_SINGLE_ASSIGNMENT
    SSA
    OPTIMISATION
    LOCAL_OPTIMISATION
    GLOBAL_OPTIMISATION
    LOOP_OPTIMISATION
    DEAD_CODE_ELIMINATION
    CONSTANT_FOLDING
    CONSTANT_PROPAGATION
    INLINING
    COMMON_SUBEXPRESSION_ELIMINATION
    REGISTER_ALLOCATION
    INSTRUCTION_SELECTION
    INSTRUCTION_SCHEDULING
    CODE_GENERATION
    TARGET_ARCHITECTURE
    ASSEMBLY_CODE
    MACHINE_CODE
    OBJECT_CODE
    OBJECT_FILE
    DEBUG_INFORMATION
    DIAGNOSTIC
    WARNING
    ERROR
    SYNTAX_ERROR
    SEMANTIC_ERROR
    TYPE_ERROR
    COMPILATION_UNIT
    BUILD
    LINKER
    LIBRARY
    DEPENDENCY
    COMPILER_FLAG
    OPTIMISATION_LEVEL
    TOOLCHAIN
    ABI
    VERSION
    LANGUAGE_VERSION
    CONFIGURATION
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    COMPILES
    COMPILES_TO
    TARGETS
    TOKENISES
    PARSES
    PRODUCES
    TRANSFORMS
    ANALYSES
    DEFINES
    DECLARES
    REFERENCES
    RESOLVES_TO
    BINDS_TO
    HAS_TYPE
    CHECKS_TYPE
    LOWERS_TO
    OPTIMISES
    ELIMINATES
    FOLDS
    PROPAGATES
    INLINES
    SELECTS_INSTRUCTION
    ALLOCATES_REGISTER
    SCHEDULES_INSTRUCTION
    GENERATES
    EMITS
    REPORTS
    HAS_WARNING
    HAS_ERROR
    USES_GRAMMAR
    USES_IR
    USES_ABI
    HAS_FLAG
    HAS_OPTIMISATION_LEVEL
    HAS_VERSION
    HAS_CONFIGURATION
    DEPENDS_ON
    PRECEDES
    FOLLOWS
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    MAPS_TO
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    SOURCE_CODE
    SOURCE_FILES
    LANGUAGE_SPECIFICATIONS
    LANGUAGE_VERSION_DATA
    GRAMMAR_DEFINITIONS
    TYPE_DEFINITIONS
    SYMBOL_DATA
    COMPILER_CONFIGURATION
    COMPILER_FLAGS
    OPTIMISATION_LEVELS
    TARGET_ARCHITECTURE_DATA
    ABI_DATA
    INTERMEDIATE_REPRESENTATIONS
    COMPILER_TRACES
    DIAGNOSTICS
    OBJECT_FILES
    VERSION_DATA
    TOOLCHAIN_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_COMPILER_IDENTIFIERS
    NORMALISE_COMPILER_NAMES
    NORMALISE_COMPILER_VERSIONS
    NORMALISE_LANGUAGE_NAMES
    NORMALISE_LANGUAGE_VERSIONS
    NORMALISE_TARGET_ARCHITECTURES
    NORMALISE_ABI_NAMES
    NORMALISE_COMPILER_FLAGS
    NORMALISE_OPTIMISATION_LEVELS
    NORMALISE_SYMBOL_IDENTIFIERS
    NORMALISE_TYPE_NAMES
    NORMALISE_IR_NAMES
    NORMALISE_DIAGNOSTIC_TYPES
    RESOLVE_COMPILER_AND_SYMBOL_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS COMPILATION_PIPELINE {
    SOURCE_CODE
      -> LEXICAL_ANALYSIS
      -> PARSING
      -> ABSTRACT_SYNTAX_TREE
      -> SEMANTIC_ANALYSIS
      -> INTERMEDIATE_REPRESENTATION
      -> OPTIMISATION
      -> CODE_GENERATION
      -> ASSEMBLY_OR_OBJECT_CODE
      -> OUTPUT_ARTIFACT
  }

  PROCESS LEXICAL_REASONING {
    SOURCE_TEXT
      -> CHARACTER_STREAM

    CHARACTER_STREAM
      -> LEXER

    LEXER
      -> TOKEN_STREAM

    INVALID_LEXEME
      -> LEXICAL_DIAGNOSTIC
  }

  PROCESS PARSING_REASONING {
    TOKEN_STREAM + GRAMMAR
      -> PARSER

    PARSER
      -> PARSE_STRUCTURE

    VALID_STRUCTURE
      -> ABSTRACT_SYNTAX_TREE

    INVALID_STRUCTURE
      -> SYNTAX_ERROR
  }

  PROCESS SEMANTIC_REASONING {
    ABSTRACT_SYNTAX_TREE
      -> SCOPE_AND_SYMBOL_ANALYSIS

    SCOPE_AND_SYMBOL_ANALYSIS
      -> SYMBOL_BINDINGS

    SYMBOL_BINDINGS
      -> TYPE_ANALYSIS

    TYPE_ANALYSIS
      -> VALID_TYPED_TREE
      OR -> SEMANTIC_OR_TYPE_ERROR
  }

  PROCESS IR_REASONING {
    VALID_TYPED_TREE
      -> IR_GENERATION

    IR_GENERATION
      -> INTERMEDIATE_REPRESENTATION

    INTERMEDIATE_REPRESENTATION
      -> CONTROL_FLOW_GRAPH
      -> DATA_FLOW_RELATIONS

    OPTIONAL
      -> SSA_TRANSFORMATION
  }

  PROCESS OPTIMISATION_REASONING {
    INTERMEDIATE_REPRESENTATION
      -> OPTIMISATION_PASSES

    OPTIMISATION_PASSES
      -> CONSTANT_FOLDING
      -> CONSTANT_PROPAGATION
      -> DEAD_CODE_ELIMINATION
      -> INLINING
      -> LOOP_OPTIMISATION
      -> COMMON_SUBEXPRESSION_ELIMINATION

    OPTIMISED_IR
      -> SEMANTIC_PRESERVATION_CHECK
  }

  PROCESS CODE_GENERATION_REASONING {
    OPTIMISED_OR_UNOPTIMISED_IR
      -> INSTRUCTION_SELECTION

    INSTRUCTION_SELECTION
      -> TARGET_INSTRUCTIONS

    TARGET_INSTRUCTIONS
      -> REGISTER_ALLOCATION

    REGISTER_ALLOCATION
      -> INSTRUCTION_SCHEDULING

    INSTRUCTION_SCHEDULING
      -> ASSEMBLY_OR_MACHINE_CODE

    OUTPUT
      -> OBJECT_FILE
  }

  PROCESS DIAGNOSTIC_REASONING {
    COMPILATION_STAGE
      -> DETECTED_ISSUE

    DETECTED_ISSUE
      -> ERROR_OR_WARNING

    ERROR_OR_WARNING
      -> SOURCE_LOCATION
      -> DIAGNOSTIC_MESSAGE
      -> RELATED_CONTEXT

    FATAL_ERROR
      -> COMPILATION_FAILURE
  }

  PROCESS TARGET_REASONING {
    SOURCE_PROGRAM + TARGET_ARCHITECTURE + ABI
      -> TARGET_CONFIGURATION

    TARGET_CONFIGURATION
      -> DATA_LAYOUT
      -> CALLING_CONVENTION
      -> INSTRUCTION_SET
      -> REGISTER_MODEL

    TARGET_CONFIGURATION
      -> CODE_GENERATION_CONSTRAINTS
  }

  RULES {
    IF SOURCE_CODE_IS_COMPILED
    THEN REQUIRE {
      SOURCE_LANGUAGE
      LANGUAGE_VERSION_OR_DIALECT
      COMPILER_VERSION
      TARGET_CONTEXT
      CONFIGURATION
    }

    IF IDENTIFIER_IS_REFERENCED
    THEN REQUIRE SYMBOL_AND_SCOPE_RESOLUTION

    IF OPTIMISATION_TRANSFORMS_IR
    THEN PRESERVE_REQUIRED_PROGRAM_SEMANTICS

    IF COMPILATION_SUCCEEDS
    THEN DO_NOT_AUTOMATICALLY_ASSERT PROGRAM_CORRECTNESS

    IF WARNING_IS_EMITTED
    THEN DO_NOT_AUTOMATICALLY_ASSERT COMPILATION_FAILURE

    IF SAME_SOURCE_IS_COMPILED_WITH_DIFFERENT_FLAGS
    THEN PRESERVE_CONFIGURATION_DIFFERENCE

    IF TARGET_ARCHITECTURE_DIFFERS
    THEN DO_NOT_ASSUME_IDENTICAL_GENERATED_CODE

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND COMPILER_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        COMPILER_VERSION_CERTAINTY,
        LANGUAGE_VERSION_CERTAINTY,
        CONFIGURATION_CERTAINTY,
        TARGET_CERTAINTY,
        SYMBOL_RESOLUTION_COMPLETENESS,
        IR_TRACE_COMPLETENESS,
        DIAGNOSTIC_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF COMPILER_FLAGS_OR_TARGET_ARE_UNKNOWN
    THEN REDUCE_OUTPUT_INFERENCE_CONFIDENCE

    IF OPTIMISATION_PIPELINE_IS_UNKNOWN
    THEN REDUCE_TRANSFORMATION_INFERENCE_CONFIDENCE

    IF REPRODUCIBLE_BUILD_CONFIRMS_OUTPUT
    THEN INCREASE CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        COMPILER_IDENTIFIER,
        COMPILER_VERSION,
        SOURCE_LANGUAGE_VERSION,
        TARGET_ARCHITECTURE,
        ABI,
        CONFIGURATION
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    COMPILER != PROGRAMMING_LANGUAGE
    SOURCE_CODE != OBJECT_CODE
    TOKEN_STREAM != ABSTRACT_SYNTAX_TREE
    SYNTAX_ERROR != SEMANTIC_ERROR
    SYMBOL != IDENTIFIER_TEXT_ALONE
    IR != MACHINE_CODE
    OPTIMISATION != SEMANTIC_CHANGE_WHEN_CORRECTLY_APPLIED
    COMPILATION_SUCCESS != PROGRAM_CORRECTNESS
    WARNING != ERROR
    OBJECT_FILE != FINAL_EXECUTABLE_IN_ALL_BUILD_MODELS
    SAME_SOURCE != SAME_BINARY_WITH_DIFFERENT_COMPILERS_OR_FLAGS
    COMPILER_VERSION_AFFECTS_GENERATED_OUTPUT
    TARGET_ARCHITECTURE_AND_ABI_AFFECT_CODE_GENERATION
    BUILD_CONFIGURATION_AFFECTS_OUTPUT
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_COMPILER_IDENTIFIER
    CHECK_COMPILER_VERSION
    CHECK_SOURCE_LANGUAGE
    CHECK_LANGUAGE_VERSION
    CHECK_LEXICAL_STRUCTURE
    CHECK_PARSE_STRUCTURE
    CHECK_SYMBOL_BINDINGS
    CHECK_TYPE_RELATIONS
    CHECK_IR_RELATIONS
    CHECK_OPTIMISATION_RELATIONS
    CHECK_TARGET_ARCHITECTURE
    CHECK_ABI
    CHECK_CODE_GENERATION
    CHECK_DIAGNOSTICS
    CHECK_COMPILER_FLAGS
    CHECK_CONFIGURATION
    CHECK_OUTPUT_ARTIFACT
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_COMPILER_ENTITIES
    LEXICAL_RELATIONS
    PARSE_RELATIONS
    ABSTRACT_SYNTAX_RELATIONS
    SYMBOL_BINDINGS
    TYPE_RELATIONS
    INTERMEDIATE_REPRESENTATION_RELATIONS
    CONTROL_AND_DATA_FLOW_RELATIONS
    OPTIMISATION_RELATIONS
    TARGET_RELATIONS
    CODE_GENERATION_RELATIONS
    OBJECT_CODE_RELATIONS
    DIAGNOSTIC_RELATIONS
    COMPILATION_TRACES
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON SOURCE_CONFIGURATION_OR_TARGET_CHANGE {
      NORMALISE
      REPROCESS_LEXICAL_AND_PARSE_STAGES
      RESOLVE_SYMBOLS
      RECHECK_TYPES
      REGENERATE_IR
      REAPPLY_OPTIMISATION_PIPELINE
      REGENERATE_TARGET_CODE
      UPDATE_DIAGNOSTICS
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON COMPILER_OR_TOOLCHAIN_VERSION_CHANGE {
      UPDATE_COMPILER_CONTEXT
      UPDATE_PASS_AND_TARGET_BEHAVIOUR
      RECHECK_SEMANTIC_EQUIVALENCE
      RECOMPUTE_AFFECTED_RELATIONS
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_COMPILER
      BY_SOURCE_LANGUAGE
      BY_LANGUAGE_VERSION
      BY_TOKEN
      BY_AST
      BY_SYMBOL
      BY_TYPE
      BY_IR
      BY_OPTIMISATION
      BY_TARGET
      BY_ABI
      BY_DIAGNOSTIC
      BY_OUTPUT_ARTIFACT
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      TRACE_COMPILATION_PIPELINE
      ANALYSE_LEXICAL_PROCESSING
      ANALYSE_PARSING
      ANALYSE_SEMANTICS_AND_TYPES
      TRACE_IR_GENERATION
      ANALYSE_OPTIMISATIONS
      TRACE_CODE_GENERATION
      ANALYSE_DIAGNOSTICS
      ANALYSE_TARGET_CONTEXT
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_COMPILER_FROM_LANGUAGE
      DISTINGUISH_SOURCE_AST_IR_AND_MACHINE_CODE
      PRESERVE_COMPILER_LANGUAGE_TARGET_ABI_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_WARNING_FROM_ERROR
      DISTINGUISH_COMPILATION_SUCCESS_FROM_PROGRAM_CORRECTNESS
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_COMPILER_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              COMPILER_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW