@inproceedings{specialize:pldi12,
    author = "Wu, Jingyue and Tang, Yang and Hu, Gang and Cui, Heming and Yang, Junfeng",
    abstract = "Parallel programs are known to be difficult to analyze. A key reason is that they typically have an enormous number of execution interleavings, or schedules. Static analysis over all schedules requires over-approximations, resulting in poor precision; dynamic analysis rarely covers more than a tiny fraction of all schedules. We propose an approach called schedule specialization to analyze a parallel program over only a small set of schedules for precision, and then enforce these schedules at runtime for soundness of the static analysis results. We build a schedule specialization framework for C/C++ multithreaded programs that use Pthreads. Our framework avoids the need to modify every analysis to be schedule-aware by specializing a program into a simpler program based on a schedule, so that the resultant program can be analyzed with stock analyses for improved precision. Moreover, our framework provides a precise schedule-aware def-use analysis on memory locations, enabling us to build three highly precise analyses: an alias analyzer, a data-race detector, and a path slicer. Evaluation on 17 programs, including 2 real-world programs and 15 popular benchmarks, shows that analyses using our framework reduced may-aliases by 61.9\%, false race reports by 69\%, and path slices by 48.7\%; and detected 7 unknown bugs in well-checked programs.",
    ids = "wu:pldi12",
    title = "Sound and Precise Analysis of Parallel Programs through Schedule Specialization",
    booktitle = "Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)",
    month = "June",
    year = "2012",
    pages = "205--216",
    doi = "10.1145/2254064.2254090",
    pdfurl = "https://dl.acm.org/doi/pdf/10.1145/2254064.2254090"
}