Convert Loop Metadata to Asserts to help Loop rotation #227

F-Stuckmann · 2024-10-28T16:55:15Z

note the first commit will be removed once the ( #225 ) is merged

Please note: I am still going through QoR to make sure I am not introducing any functional errors.

llvm/include/llvm/Transforms/Utils/LoopMetadata.h

llvm/lib/Transforms/Utils/LoopMetadata.cpp

llvm/include/llvm/Transforms/Utils/LoopMetadata.h

llvm/lib/Transforms/Utils/LoopMetadata.cpp

llvm/include/llvm/Transforms/Utils/LoopMetadata.h

llvm/lib/Transforms/Utils/LoopMetadata.cpp

llvm/test/Transforms/Util/loop-metadata.ll

llvm/include/llvm/Transforms/Utils/LoopMetadata.h

llvm/lib/Transforms/Utils/LoopMetadata.cpp

llvm/include/llvm/Transforms/Utils/LoopMetadata.h

llvm/lib/Transforms/Utils/LoopMetadata.cpp

llvm/lib/Passes/PassBuilderPipelines.cpp

F-Stuckmann · 2024-12-03T10:57:59Z

Only add assumption if the assumption at the first iteration can be guaranteed to be loop invariant.

F-Stuckmann · 2024-12-03T10:59:17Z

rebased to aie-public

llvm/lib/Transforms/Utils/LoopIterCountAssumptions.cpp

llvm/tools/dsymutil/CMakeLists.txt

andcarminati · 2024-12-06T10:21:49Z

Maybe you can fix the CI failure by running your test under x86?

F-Stuckmann · 2024-12-10T09:53:55Z

I moved the pass between LICM and loop rotate, so that the loop invariance check is simplified and performed by LICM. This behavior is demonstrated by unittests.

Additionally, the assumption is inserted into the Preheader, so that the loop header is not evaluated to true and converted into an endless loop.

gbossu · 2024-12-10T10:54:32Z

llvm/test/Transforms/Util/loop-iter-count-assumptions.ll

+; NOTE: Example file for converting loop iter count to assumptions in the Loop
+;
+; RUN: opt -S -passes='loop-iter-count-assumptions' -verify-each   < %s | FileCheck %s
+; RUN: opt -S -passes='loop-mssa(licm,loop-iter-count-assumptions)' -verify-each   < %s | FileCheck %s --check-prefix=LICM


That's a really huge file now. I think the first RUN line isn't all that useful anymore, because your pass is now inserted after LICM in the pass pipeline. Testing it independently outside of its expected conditions doesn't show too much.

Maybe it would make sense to only keep:

opt -S -passes='loop-mssa(licm,loop-iter-count-assumptions)' -verify-each < %s | FileCheck %s --check-prefix=ASSUME

opt -S -passes='default<O2>' --enable-loop-iter-count-assumptions=1 -start-before='licm' -stop-after='loop-rotate' -verify-each -o - < %s | FileCheck %s --check-prefix=ROTATE

Nit: I would even only test loop-mssa(licm,loop-iter-count-assumptions) in that file to keep it concise and easy to read. Then we can have a separate "integration test" which runs from licm to loop-rotate with one or two cases. But that's a personal preference at this point :)

I wanted to have the end to end test, so that non-obvious errors get shown immediately, i.e. endless loops.

But sure, now that i am through the testing and know what the expected results are, I can remove it. The integration test is only interesting for edge cases, which would duplicates large parts of the unittest, which is the original reason I had them in the same file.

gbossu · 2024-12-10T10:59:56Z

llvm/lib/Transforms/Utils/LoopIterCountAssumptions.cpp

+  // return LHS
+  Value *LHS = expandValueAtZeroIteration(LoopCmpInstr.getOperand(0), SE,
+                                          Expander, &LoopCmpInstr);
+  LHS = getLoopInvariant(LHS, DT, &CurrentLoop);


See my comment here https://github.com/Xilinx/llvm-aie/pull/227/files#r1869145688

I think it is a bit confusing that expandValueAtZeroIteration potentially returns something that isn't the value at iteration 0. This LHS = getLoopInvariant(LHS, DT, &CurrentLoop); should be inlined into expandValueAtZeroIteration. If the latter cannot be sure that the returned value is exactly the one at iteration 0, it should return nullptr.

That is a more concise way of looking at expandValueAtZeroIteration

I updated it accordingly.

andcarminati · 2024-12-10T14:42:05Z

clang/lib/Driver/ToolChains/AIE.cpp

@@ -163,6 +163,9 @@ void AIEToolChain::addClangTargetOptions(

  // Extend the max limit of the search depth in BasicAA
  CC1Args.append({"-mllvm", "-basic-aa-max-lookup-search-depth=10"});
+
+  // enable Loop Iteration Count Assumptions


nit: Enable.

andcarminati · 2024-12-10T14:43:10Z

clang/lib/Driver/ToolChains/AIE.cpp

@@ -163,6 +163,9 @@ void AIEToolChain::addClangTargetOptions(

  // Extend the max limit of the search depth in BasicAA
  CC1Args.append({"-mllvm", "-basic-aa-max-lookup-search-depth=10"});
+
+  // enable Loop Iteration Count Assumptions
+  CC1Args.append({"-mllvm", "-enable-loop-iter-count-assumptions=1"});


nit: it is better to use boolean because it is the correct type for the flag.

llvm/lib/Target/AIE/AIEBaseTargetMachine.cpp

F-Stuckmann · 2024-12-11T14:50:11Z

Assumption Insertion: Evaluate at MinIterCount to not introduce loop guards after loop unrolling
Assumption Insertion: Evaluate at Iteration 0, so that EQ/NE and variable stepsizes can be processed. Hint: EQ/NE only get this assumption inserted

I also only lazily insert the Iteration 0 assumption so that the IR changes are minimal.

QoR improves by 1.14% and program memory by 0.73%, when this pass is enabled vs with the builtin_assumes

llvm/lib/Transforms/Utils/LoopIterCountAssumptions.cpp

…for AIE targets

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/include/llvm/Transforms/Utils/LoopMetadata.h Outdated Show resolved Hide resolved

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/include/llvm/Transforms/Utils/LoopMetadata.h Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/include/llvm/Transforms/Utils/LoopMetadata.h Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/include/llvm/Transforms/Utils/LoopMetadata.h Outdated Show resolved Hide resolved

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/include/llvm/Transforms/Utils/LoopMetadata.h Outdated Show resolved Hide resolved

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/include/llvm/Transforms/Utils/LoopMetadata.h Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/include/llvm/Transforms/Utils/LoopMetadata.h Outdated Show resolved Hide resolved

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/test/Transforms/Util/loop-metadata.ll Outdated Show resolved Hide resolved

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/include/llvm/Transforms/Utils/LoopMetadata.h Outdated Show resolved Hide resolved

gbossu reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

andcarminati reviewed Oct 29, 2024

View reviewed changes

llvm/lib/Transforms/Utils/LoopMetadata.cpp Outdated Show resolved Hide resolved

martien-de-jong reviewed Oct 29, 2024

View reviewed changes