Reddit mentions of Optimizing Compilers for Modern Architectures: A Dependence-based Approach

Just want to add a couple of things:

1. Despite the significant practical and theoretical challenges mentioned by the other commenters, it is amazing that compilers nonetheless can parallelize some code in specific cases in which it can prove that the parallelizing transformation is equivalent. These automatic parallelization transformations are quite limited for the reasons already discussed. For example, compilers can sometimes use SIMD instructions when it detects repeated computations within a loop. Here's an article about how LLVM auto-vectorizes code. Of course, SIMD isn't multithreading specifically, but it is parallelization nonetheless.
   
   
2. u/Pantajones and u/Tai9ch explained about the centrality of dependencies to the problem of automatic parallelization, and your comment about "dependency trees" is an insightful one. If you want to learn more about how these ideas can be applied to building an optimizing compiler, I recommend Optimizing Compilers for Modern Architectures: A Dependence-based Approach by Randy Allen and Ken Kennedy. Be warned: It's an advanced book that focuses on theory, not a book for beginners.

Just read the table of contents of a couple of advanced compiler books:

Advanced Compiler Design and Implementation

Optimizing Compilers for Modern Architectures: A Dependence-based Approach

It is a different ball game.

For compilers:

• Dragon Book is a good intro text
  
• Kennedy/Allen is a good advanced text
  
  Types and Programming Languages by Pierce is also a must read for theory people.