From a0ee2bf671d61d1e2b561db3966e57ffc802040f Mon Sep 17 00:00:00 2001 From: Ellie Hermaszewska Date: Thu, 17 Aug 2023 13:41:49 +0800 Subject: 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 --- source/slang/slang-lower-to-ir.cpp | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) (limited to 'source/slang/slang-lower-to-ir.cpp') 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 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. // -- cgit v1.2.3