Universal Translating Library

Universal Translating Library (UTL) is a set of building blocks that contain elaborate state-of-the-art tools for program analysis, debugging, optimization, compilation and parallelization, available as source code or runtime libraries. Blocks may be used to create your own compiler at a fraction of the regular cost.

UTL includes algorithms of both intra- and inter-procedural data- and control-flow analyses, various loop and acyclic part control transformations, a number of inter-procedural optimizations etc.

Each block is implemented as a complete and independent product. Blocks may be used within in-built full compilation schemes, or may be easily combined into any new compilation scheme.

The implemented algorithms have passed approbation in industrial optimizing compilers and have proven their high effectiveness.

Analyzer blocks:

Data Flow Analyzer - Value Numbering
Control Flow Analyzer
Loop invariants detection
Inductive variables detection
Loop data dependence analysis
Local points-to analysis
Acyclic data dependence analysis
Interprocedural Control Flow Analyzer
Interprocedural Data Flow Analyzer - Flow/Context Sensitive/Insensitive Propagator (constants, alignments, ranges, points-to), Value Numbering, Heap modeling
Static Profiler

Optimizer blocks:

Constant Propagation
Peephole
CSE
GCP
RLE, RSE
LCM (PRE)
DCE
Loop invariants motion (forward/backward)
Scalar replacement
Strength reduction
IV reduction/substitution
Expression balancing and reassociation
Predicate optimizations
Tail duplication
Black Hole
If-optimization
Loop Nesting
Loop Unroll
Loop Peeling
Loop Unswitching
Loop Splitting (by condition, by index)
Loop Unroll & Fusion
Run Time Memory Disambiguation
Loop versioning
Prefetch
Software pipelining by kernel recognition
Loop Vector Invariant Removing
Loop Blocking
Loop Skewing
Loop Interchange
Data Reorganization
Call site prefetch
Vectorization
Multithreading
Static Profiler
Scheduling (including predication, speculation utilization)
Acyclic Region List Scheduler
Modulo scheduler (vector register SWP)
Acyclic Global Scheduler
Cyclic Global Scheduler
SWP Loops Register Allocator
Global Register Allocator