Add loop inversion pass (#2899)

* Generalize collectInductionValues

* Support affine transformations of loop index as induction variables

* Test for generalized induction value collection

* Neaten inductive variable finding

* Make types more specific

* Add loop inversion pass

* Test output changes after loop inversion

* Store the type of implication success when finding inductive variables

* Test that loop induction finding does not alway succeed

* Support chains of additions and branches of additions in induction variable finding

* Use c++17 for downstream compilers

* Wiggle expected output for cross compile test after loop inversion

* Add loop inversion test

* Simplify IfElse instructions with a single trivial block

* Invert loops with a user inserted break

* Limit loop inversion to loops with a 4 instruction or less comparison block

* regenerate vs projects

1 files changed, 19 insertions, 0 deletions

diff --git a/source/slang/slang-lower-to-ir.cpp b/source/slang/slang-lower-to-ir.cpp
index 74ece5bc9..1ed79fbe3 100644
--- a/source/slang/slang-lower-to-ir.cpp
+++ b/source/slang/slang-lower-to-ir.cpp
@@ -9,6 +9,7 @@
 #include "../core/slang-performance-profiler.h"
 
 #include "slang-check.h"
+#include "slang-ir-loop-inversion.h"
 #include "slang-ir.h"
 #include "slang-ir-constexpr.h"
 #include "slang-ir-dce.h"
@@ -9702,6 +9703,24 @@ RefPtr<IRModule> generateIRForTranslationUnit(
     //
     performMandatoryEarlyInlining(module);
 
+    // Where possible, move loop condition checks to the end of loops, and wrap
+    // the loop in an 'if(condition)'.
+    // This makes it so that if sccp can see that the loop will always loop
+    // at least once it can record this information by removing the outer
+    // conditional.
+    // This has advantages:
+    // - Uninitialized variable usage detection doesn't have to
+    //   worry about a loop never being executed.
+    // - The loop condition is evaluated one fewer times.
+    // - Allegedly better performance on pipelined processors:
+    //   https://en.wikipedia.org/wiki/Loop_inversion
+    //
+    // And disadvantages
+    // - If sccp is unable to eliminate the outer 'if' then we end up with
+    //   duplicated code the the conditional value. Users don't tend to put
+    //   huge gobs of code in the conditional expression in loops however.
+    invertLoops(module);
+
     // Next, attempt to promote local variables to SSA
     // temporaries and do basic simplifications.
     //