diff --git a/llvm/include/llvm/Analysis/Delinearization.h b/llvm/include/llvm/Analysis/Delinearization.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/Delinearization.h @@ -0,0 +1,33 @@ +//===---- Delinearization.h - MultiDimensional Index Delinearization ------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This implements an analysis pass that tries to delinearize all GEP +// instructions in all loops using the SCEV analysis functionality. This pass is +// only used for testing purposes: if your pass needs delinearization, please +// use the on-demand SCEVAddRecExpr::delinearize() function. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_DELINEARIZATION_H +#define LLVM_ANALYSIS_DELINEARIZATION_H + +#include "llvm/IR/PassManager.h" +#include "llvm/Support/raw_ostream.h" + +namespace llvm { +struct DelinearizationPrinterPass + : public PassInfoMixin { + explicit DelinearizationPrinterPass(raw_ostream &OS); + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + +private: + raw_ostream &OS; +}; +} // namespace llvm + +#endif // LLVM_ANALYSIS_DELINEARIZATION_H diff --git a/llvm/lib/Analysis/Delinearization.cpp b/llvm/lib/Analysis/Delinearization.cpp --- a/llvm/lib/Analysis/Delinearization.cpp +++ b/llvm/lib/Analysis/Delinearization.cpp @@ -13,6 +13,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Analysis/Delinearization.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ScalarEvolution.h" @@ -23,6 +24,7 @@ #include "llvm/IR/InstIterator.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/LLVMContext.h" +#include "llvm/IR/PassManager.h" #include "llvm/IR/Type.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" @@ -54,22 +56,8 @@ void print(raw_ostream &O, const Module *M = nullptr) const override; }; -} // end anonymous namespace - -void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); - AU.addRequired(); -} - -bool Delinearization::runOnFunction(Function &F) { - this->F = &F; - SE = &getAnalysis().getSE(); - LI = &getAnalysis().getLoopInfo(); - return false; -} - -void Delinearization::print(raw_ostream &O, const Module *) const { +void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI, + ScalarEvolution *SE) { O << "Delinearization on function " << F->getName() << ":\n"; for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { Instruction *Inst = &(*I); @@ -120,6 +108,25 @@ } } +} // end anonymous namespace + +void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); + AU.addRequired(); +} + +bool Delinearization::runOnFunction(Function &F) { + this->F = &F; + SE = &getAnalysis().getSE(); + LI = &getAnalysis().getLoopInfo(); + return false; +} + +void Delinearization::print(raw_ostream &O, const Module *) const { + printDelinearization(O, F, LI, SE); +} + char Delinearization::ID = 0; static const char delinearization_name[] = "Delinearization"; INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true, @@ -128,3 +135,12 @@ INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true) FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; } + +DelinearizationPrinterPass::DelinearizationPrinterPass(raw_ostream &OS) + : OS(OS) {} +PreservedAnalyses DelinearizationPrinterPass::run(Function &F, + FunctionAnalysisManager &AM) { + printDelinearization(OS, &F, &AM.getResult(F), + &AM.getResult(F)); + return PreservedAnalyses::all(); +} diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -29,6 +29,7 @@ #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/DDG.h" +#include "llvm/Analysis/Delinearization.h" #include "llvm/Analysis/DemandedBits.h" #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/DominanceFrontier.h" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -247,6 +247,7 @@ FUNCTION_PASS("print", DependenceAnalysisPrinterPass(dbgs())) FUNCTION_PASS("print", DominatorTreePrinterPass(dbgs())) FUNCTION_PASS("print", PostDominatorTreePrinterPass(dbgs())) +FUNCTION_PASS("print", DelinearizationPrinterPass(dbgs())) FUNCTION_PASS("print", DemandedBitsPrinterPass(dbgs())) FUNCTION_PASS("print", DominanceFrontierPrinterPass(dbgs())) FUNCTION_PASS("print", FunctionPropertiesPrinterPass(dbgs())) diff --git a/llvm/test/Analysis/Delinearization/a.ll b/llvm/test/Analysis/Delinearization/a.ll --- a/llvm/test/Analysis/Delinearization/a.ll +++ b/llvm/test/Analysis/Delinearization/a.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; ; void foo(long n, long m, long o, int A[n][m][o]) { ; for (long i = 0; i < n; i++) diff --git a/llvm/test/Analysis/Delinearization/constant_functions_multi_dim.ll b/llvm/test/Analysis/Delinearization/constant_functions_multi_dim.ll --- a/llvm/test/Analysis/Delinearization/constant_functions_multi_dim.ll +++ b/llvm/test/Analysis/Delinearization/constant_functions_multi_dim.ll @@ -1,4 +1,5 @@ -; RUN: opt -delinearize -analyze < %s | FileCheck %s +; RUN: opt -delinearize -analyze -enable-new-pm=0 < %s | FileCheck %s +; RUN: opt -passes='print' -disable-output < %s 2>&1 | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" diff --git a/llvm/test/Analysis/Delinearization/divide_by_one.ll b/llvm/test/Analysis/Delinearization/divide_by_one.ll --- a/llvm/test/Analysis/Delinearization/divide_by_one.ll +++ b/llvm/test/Analysis/Delinearization/divide_by_one.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s target datalayout = "e-m:e-p:32:32-i1:32-i64:64-a:0-n32" diff --git a/llvm/test/Analysis/Delinearization/gcd_multiply_expr.ll b/llvm/test/Analysis/Delinearization/gcd_multiply_expr.ll --- a/llvm/test/Analysis/Delinearization/gcd_multiply_expr.ll +++ b/llvm/test/Analysis/Delinearization/gcd_multiply_expr.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -basic-aa -da -analyze -delinearize +; RUN: opt < %s -basic-aa -da -analyze -enable-new-pm=0 -delinearize +; RUN: opt < %s -aa-pipeline=basic-aa -passes='require,print' -disable-output ; ; a, b, c, d, g, h; ; char *f; diff --git a/llvm/test/Analysis/Delinearization/himeno_1.ll b/llvm/test/Analysis/Delinearization/himeno_1.ll --- a/llvm/test/Analysis/Delinearization/himeno_1.ll +++ b/llvm/test/Analysis/Delinearization/himeno_1.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; #define MR(mt,n,r,c,d) mt->m[(n) * mt->mrows * mt->mcols * mt->mdeps + (r) * mt->mcols* mt->mdeps + (c) * mt->mdeps + (d)] ; diff --git a/llvm/test/Analysis/Delinearization/himeno_2.ll b/llvm/test/Analysis/Delinearization/himeno_2.ll --- a/llvm/test/Analysis/Delinearization/himeno_2.ll +++ b/llvm/test/Analysis/Delinearization/himeno_2.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; #define MR(mt,n,r,c,d) mt->m[(n) * mt->mrows * mt->mcols * mt->mdeps + (r) * mt->mcols* mt->mdeps + (c) * mt->mdeps + (d)] ; diff --git a/llvm/test/Analysis/Delinearization/iv_times_constant_in_subscript.ll b/llvm/test/Analysis/Delinearization/iv_times_constant_in_subscript.ll --- a/llvm/test/Analysis/Delinearization/iv_times_constant_in_subscript.ll +++ b/llvm/test/Analysis/Delinearization/iv_times_constant_in_subscript.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; Derived from the following code: ; diff --git a/llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll b/llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll --- a/llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll +++ b/llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; void foo(long n, long m, long o, double A[n][m][o]) { ; diff --git a/llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll b/llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll --- a/llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll +++ b/llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; void foo(long n, long m, long o, long p, double A[n][m][o+p]) { ; diff --git a/llvm/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll b/llvm/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll --- a/llvm/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll +++ b/llvm/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; void foo(long n, long m, long o, double A[n][m][o], long p, long q, long r) { ; diff --git a/llvm/test/Analysis/Delinearization/multidim_only_ivs_2d.ll b/llvm/test/Analysis/Delinearization/multidim_only_ivs_2d.ll --- a/llvm/test/Analysis/Delinearization/multidim_only_ivs_2d.ll +++ b/llvm/test/Analysis/Delinearization/multidim_only_ivs_2d.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; Derived from the following code: ; diff --git a/llvm/test/Analysis/Delinearization/multidim_only_ivs_2d_nested.ll b/llvm/test/Analysis/Delinearization/multidim_only_ivs_2d_nested.ll --- a/llvm/test/Analysis/Delinearization/multidim_only_ivs_2d_nested.ll +++ b/llvm/test/Analysis/Delinearization/multidim_only_ivs_2d_nested.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; XFAIL: * ; We do not recognize anymore variable size arrays. diff --git a/llvm/test/Analysis/Delinearization/multidim_only_ivs_3d.ll b/llvm/test/Analysis/Delinearization/multidim_only_ivs_3d.ll --- a/llvm/test/Analysis/Delinearization/multidim_only_ivs_3d.ll +++ b/llvm/test/Analysis/Delinearization/multidim_only_ivs_3d.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; void foo(long n, long m, long o, double A[n][m][o]) { ; diff --git a/llvm/test/Analysis/Delinearization/multidim_only_ivs_3d_cast.ll b/llvm/test/Analysis/Delinearization/multidim_only_ivs_3d_cast.ll --- a/llvm/test/Analysis/Delinearization/multidim_only_ivs_3d_cast.ll +++ b/llvm/test/Analysis/Delinearization/multidim_only_ivs_3d_cast.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s ; void foo(int n, int m, int o, double A[n][m][o]) { ; ; for (int i = 0; i < n; i++) diff --git a/llvm/test/Analysis/Delinearization/multidim_two_accesses_different_delinearization.ll b/llvm/test/Analysis/Delinearization/multidim_two_accesses_different_delinearization.ll --- a/llvm/test/Analysis/Delinearization/multidim_two_accesses_different_delinearization.ll +++ b/llvm/test/Analysis/Delinearization/multidim_two_accesses_different_delinearization.ll @@ -1,4 +1,5 @@ -; RUN: opt -basic-aa -da -analyze < %s +; RUN: opt -basic-aa -da -analyze -enable-new-pm=0 < %s +; RUN: opt -aa-pipeline=basic-aa -passes='require,print' -disable-output < %s target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" diff --git a/llvm/test/Analysis/Delinearization/parameter_addrec_product.ll b/llvm/test/Analysis/Delinearization/parameter_addrec_product.ll --- a/llvm/test/Analysis/Delinearization/parameter_addrec_product.ll +++ b/llvm/test/Analysis/Delinearization/parameter_addrec_product.ll @@ -1,4 +1,5 @@ -; RUN: opt -delinearize -analyze < %s | FileCheck %s +; RUN: opt -delinearize -analyze -enable-new-pm=0 < %s | FileCheck %s +; RUN: opt -passes='print' -disable-output < %s 2>&1 | FileCheck %s ; ; void foo(float *A, long *p) { ; for (long i = 0; i < 100; i++) diff --git a/llvm/test/Analysis/Delinearization/terms_with_identity_factor.ll b/llvm/test/Analysis/Delinearization/terms_with_identity_factor.ll --- a/llvm/test/Analysis/Delinearization/terms_with_identity_factor.ll +++ b/llvm/test/Analysis/Delinearization/terms_with_identity_factor.ll @@ -1,5 +1,6 @@ ; REQUIRES: asserts -; RUN: opt < %s -analyze -delinearize -debug 2>&1 | FileCheck %s +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize -debug 2>&1 | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output -debug 2>&1 2>&1 | FileCheck %s ; void foo (int m, int n, char *A) { ; for (int i=0; i < m; i++) ; for(int j=0; j< n; j++) diff --git a/llvm/test/Analysis/Delinearization/type_mismatch.ll b/llvm/test/Analysis/Delinearization/type_mismatch.ll --- a/llvm/test/Analysis/Delinearization/type_mismatch.ll +++ b/llvm/test/Analysis/Delinearization/type_mismatch.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize +; RUN: opt < %s -passes='print' -disable-output ; REQUIRES: asserts ; Test that SCEV divide code doesn't crash when attempting to create a SCEV diff --git a/llvm/test/Analysis/Delinearization/undef.ll b/llvm/test/Analysis/Delinearization/undef.ll --- a/llvm/test/Analysis/Delinearization/undef.ll +++ b/llvm/test/Analysis/Delinearization/undef.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -analyze -delinearize +; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize +; RUN: opt < %s -passes='print' -disable-output target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"