Classical Compilers
Production implementations of compiler algorithms and techniques
Repositories
(7)dotnet/runtime
gcc-mirror/gcc
golang/go
llvm/llvm-project
openjdk/jdk
rust-lang/rust
swiftlang/swift
Papers
(100)32-bit cyclic redundancy codes for Internet applications
Standardized 32-bit Cyclic Redundancy Codes provide fewer bits of guaranteed error detection than they could, achieving a Hamming Distance (HD) of only 4 for maximum-length Ethernet messages, whereas HD=6 is possible. Although research has revealed i...
Alias burying: Unique variables without destructive reads
Abstract An unshared object can be accessed without regard to possible conflicts with other parts of a system, whether concurrent or single‐threaded. A unique variable (sometimes known as a ‘free’ or ‘linear’ variable) is one that either is null or e...
AN ANALYSIS OF THE LANCZOS GAMMA APPROXIMATION
This thesis is an analysis of C . Lanczos' approximation of the classical gamma function Γ(z + 1) as given in his 1964 paper "A Precision Approximation of the Gamma Function". The purposes of this study are: (i) to explain the details of Lanczos' pap...
A Time and Space-Efficient Compositional Method for Prime and Test Paths Generation.
This paper investigates the problem of prime and test paths generation, which is an important problem in ensuring path coverage in software testing. Most existing methods for prime/test paths generation have little success in generating the set of al...
BlockQuicksort: Avoiding Branch Mispredictions in Quicksort
Since the work of Kaligosi and Sanders (2006), it is well-known that Quicksort - which is commonly considered as one of the fastest in-place sorting algorithms - suffers in an essential way from branch mispredictions. We present a novel approach to a...
Fast Deterministic Selection.
The selection problem, in forms such as finding the median or choosing the k top ranked items in a dataset, is a core task in computing with numerous applications in fields as diverse as statistics, databases, Machine Learning, finance, biology, and ...
Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries
On common processors, integer multiplication is many times faster than integer division. Dividing a numerator n by a divisor d is mathematically equivalent to multiplication by the inverse of the divisor (n / d = n x 1/d). If the divisor is known in ...
Graph-Based Algorithms for Boolean Function Manipulation
In this paper we present a new data structure for representing Boolean functions and an associated set of manipulation algorithms. Functions are represented by directed, acyclic graphs in a manner similar to the representations introduced by Lee [1] ...
How to make ad-hoc polymorphism less ad hoc
This paper presents type classes, a new approach to ad-hoc polymorphism. Type classes permit overloading of arithmetic operators such as multiplication, and generalise the "eqtype variables" of Standard ML. Type classes extend the Hindley/Milner poly...
Macros that Work Together
Abstract Racket is a large language that is built mostly within itself. Unlike the usual approach taken by non-Lisp languages, the self-hosting of Racket is not a matter of bootstrapping one implementation through a previous implementation, but inste...
Optimization of cyclic redundancy-check codes with 24 and 32 parity bits
The method developed by T. Fujiwara et al. (1985) for efficiently computing the minimum distance of shortened Hamming codes using the weight distribution of their dual codes is extended to treat arbitrary shortened cyclic codes. Using this method imp...
Practical type inference for arbitrary-rank types
Abstract Haskell's popularity has driven the need for ever more expressive type system features, most of which threaten the decidability and practicality of Damas-Milner type inference. One such feature is the ability to write functions with higher-r...
Scrambled Linear Pseudorandom Number Generators
$\mathbf F_2$-linear pseudorandom number generators are very popular due to their high speed, to the ease with which generators with a sizable state space can be created, and to their provable theoretical properties. However, they suffer from linear ...
Taming the wildcards: combining definition- and use-site variance
Variance allows the safe integration of parametric and subtype polymorphism. Two flavors of variance, definition-site versus use-site variance, have been studied and have had their merits hotly debated. Definition-site variance (as in Scala and C#) o...
Three layer cake for shared-memory programming
There are many different styles of parallel programming for shared-memory hardware. Each style has strengths, but can conflict with other styles. How can we use a variety of these styles in one program and minimize their conflict and maximize perform...
Work-first and help-first scheduling policies for async-finish task parallelism
Multiple programming models are emerging to address an increased need for dynamic task parallelism in applications for multicore processors and shared-address-space parallel computing. Examples include OpenMP 3.0, Java Concurrency Utilities, Microsof...
Xorshift RNGs
Description of a class of simple, extremely fast random number generators (RNGs) with periods 2k - 1 for k = 32, 64, 96, 128, 160, 192. These RNGs seem to pass tests of randomness very well.