<story><title>What are the ways compilers recognize complex patterns?</title><url>https://langdev.stackexchange.com/questions/3942/what-are-the-ways-compilers-recognize-complex-patterns</url></story><parent_chain><item><author>pizlonator</author><text>Canonical forms, smart stuff, a lot of hardcoding.&lt;p&gt;Canonical forms are the really important part. Simple example: there are multiple ways a program might say “X * 2”. You could shift left by 1. You could multiple by 2. You could add X to itself. The idea of canonical forms is that in one pass, the compiler will pattern match all the ways you can do this and reduce all of them to the same canonical form - say, left shift by 1. Then, subsequent passes that want to catch more complex uses of that construct only have to look for one version of it (left shift 1) and not all three.&lt;p&gt;Here’s a more complex case. Ternary expressions in C and if-else statements have the same representation in llvm IR generated by clang: basic blocks and branches. There are multiple ways of representing the data flow (could use allocas and stores&amp;#x2F;loads or SSA data flow) but both the sroa and mem2reg passes will canonicalize to SSA. And, last I checked llvm says that the preferred canonical form of a if-then-else is a select (I.e. conditional move) whenever the two are equivalent. So, no matter what you use to write the equivalent of std::min - macros, templates, whatever, coding style don’t matter - you will end up eventually with a select instruction whose predicate is a comparison. Then - if your CPU supports doing min in a single instruction, it’s trivial for the instruction selector to just look for that kind of select. This happens not because every way of writing min is hardcoded, but because multiple rounds of canonicalization (clang using basic blocks and branches for both if&amp;#x2F;else and ternaries, sroa and mem2reg preferring SSA, and if conversion preferring select) gets you there.&lt;p&gt;A lot of this is hardcoding, but it’s not the boring “hardcode everything” kind of approach, but rather, it’s about using multiple phases that each produce increasingly canonical code that makes subsequent pattern matching simpler.</text></item></parent_chain><comment><author>Agentlien</author><text>This makes so much sense to me!&lt;p&gt;I once ended up using a similar approach for a small project at work[0]. It&amp;#x27;s a tool for cleaning up automatically generated shader files to make them easier to read and optimize. It works entirely by running a series of regex replacements in succession. I very quickly found that picking the order of these passes allowed me to create a lot more opportunities for improvements because I could make more assumptions about the form and patterns of the code. It also really helped that the original generated code was very formulaic.&lt;p&gt;[0] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;Agentlien&amp;#x2F;ShaderCleanup&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;Agentlien&amp;#x2F;ShaderCleanup&lt;/a&gt;</text></comment>
<story><title>What are the ways compilers recognize complex patterns?</title><url>https://langdev.stackexchange.com/questions/3942/what-are-the-ways-compilers-recognize-complex-patterns</url></story><parent_chain><item><author>pizlonator</author><text>Canonical forms, smart stuff, a lot of hardcoding.&lt;p&gt;Canonical forms are the really important part. Simple example: there are multiple ways a program might say “X * 2”. You could shift left by 1. You could multiple by 2. You could add X to itself. The idea of canonical forms is that in one pass, the compiler will pattern match all the ways you can do this and reduce all of them to the same canonical form - say, left shift by 1. Then, subsequent passes that want to catch more complex uses of that construct only have to look for one version of it (left shift 1) and not all three.&lt;p&gt;Here’s a more complex case. Ternary expressions in C and if-else statements have the same representation in llvm IR generated by clang: basic blocks and branches. There are multiple ways of representing the data flow (could use allocas and stores&amp;#x2F;loads or SSA data flow) but both the sroa and mem2reg passes will canonicalize to SSA. And, last I checked llvm says that the preferred canonical form of a if-then-else is a select (I.e. conditional move) whenever the two are equivalent. So, no matter what you use to write the equivalent of std::min - macros, templates, whatever, coding style don’t matter - you will end up eventually with a select instruction whose predicate is a comparison. Then - if your CPU supports doing min in a single instruction, it’s trivial for the instruction selector to just look for that kind of select. This happens not because every way of writing min is hardcoded, but because multiple rounds of canonicalization (clang using basic blocks and branches for both if&amp;#x2F;else and ternaries, sroa and mem2reg preferring SSA, and if conversion preferring select) gets you there.&lt;p&gt;A lot of this is hardcoding, but it’s not the boring “hardcode everything” kind of approach, but rather, it’s about using multiple phases that each produce increasingly canonical code that makes subsequent pattern matching simpler.</text></item></parent_chain><comment><author>dartos</author><text>So you hardcode canonical forms to simplify them down to a common form so that you only need to hardcode one kind of form for the next pass?</text></comment>