Irregularly structured registers are hard to abstract and allocate. Partitioned Boolean quadratic programming (PBQP) is a useful abstraction to represent complex register constraints, even those in highly irregular processors of automated test equipment (ATE) of DRAM memory chips. The PBQP problem is NP-hard, requiring a heuristic solution. If no spill is allowed as in ATE, however, we have to enumerate more to find a solution rather than to approximate, since a spill means a total compilation failure. We propose solving the PBQP problem with deep reinforcement learning (Deep-RL), more specifically, a model-based approach using Monte Carlo tree search and deep neural network as used in Alphazero, a proven Deep-RL technology. Through elaborate training with random PBQP graphs, our Deep-RL solver could cut the search space sharply, making an enumeration-based solution more affordable. Furthermore, by employing backtracking with a proper coloring order, Deep-RL can find a solution with modestly-trained neural networks with even less search space. Our experiments show that Deep-RL can successfully find a solution for 10 product-level ATE programs while searching much fewer (e.g., 1/3,500) states than the previous PBQP enumeration solver. Also, when applied to C programs in llvm-test-suite for regular CPUs, it achieves a competitive performance to the existing PBQP register allocator in LLVM.

Test-pattern programs are for testing DRAM memory chips. They run on a special embedded system called automated test equipment (ATE). Each ATE manufacturer provides its own programming language, which is mostly low level, thus accessing the registers in the ATE directly. The register structure of each ATE is quite different and highly irregular. Since DRAM chipmakers are often equipped with diverse ATEs from different manufacturers, they employ automatic translation of a program developed for one ATE to a program for different ATEs. This raises an irregular register allocation problem during translation. This article proposes a solution based on partitioned Boolean quadratic programming (PBQP). PBQP has been used for a number of compiler optimizations, including paired register allocation , which our ATE register allocation also requires. Moreover, the interleaved processing in ATE incurs complex register constraints, which we could also formulate elegantly with PBQP. The original PBQP solver is not quite appropriate to use, though, since ATE register allocation does not allow spills, so we devised a more elaborate PBQP solver that trades off the allocation time and allocation search space, to find a solution in a reasonable amount of time. Our experimental results with product-level pattern programs show that the proposed register allocator successfully finds valid solutions in all cases, in the order of tenths of seconds.

An Intermediate Representation (IR) used by compilers is normally generated statically , as a result of parsing or analyzing the source program. This paper proposes a completely different type of IR, generated as a result of running the source program, the output-based IR . There is a practical translation problem where such an IR is useful, in the domain of test-pattern programs . Test-pattern programs run on ATE (automatic test equipment), a special embedded system to test semiconductors such as DRAMs. They generate a pattern for each clock, a bit vector input to the pins of the chip. One issue is that different ATEs require different programming since each ATE manufacturer has its own programming language. Nonetheless, we should be able to test a memory chip on different ATEs as long as they generate the same patterns with the same speed. Therefore, a memory chipmaker wants to make a pattern program portable across ATEs, to fully utilize their ATE resources. One solution is translating between pattern programs, for which we need an IR since there are multiple source ATEs and target ATEs. Instead of a conventional, static IR, we propose using the output pattern itself as an IR. Since the pattern is independent of ATEs and easily obtainable, the output-based IR obviates designing a static IR considering all ATE programming languages and hardware differences. Moreover, we might synthesize a better target program from the IR, more optimized to the target ATE. However, the full pattern generated by a product-level pattern program is huge, so we propose using an IR of abbreviated patterns, annotated with the repetition information obtained while executing the source program. Our experimental results with product-level pattern programs show that our approach is feasible.