From d761cc1dfa7bb55c0c995dd409025147a51c1258 Mon Sep 17 00:00:00 2001 From: Adam Nemet Date: Fri, 25 Apr 2014 21:02:21 +0000 Subject: [PATCH] [LoopStrengthReduce] Don't trim formula that uses a subset of required registers Consider this use from the new testcase: LSR Use: Kind=ICmpZero, Offsets={0}, widest fixup type: i32 reg({1000,+,-1}<%for.body>) -3003 + reg({3,+,3}<%for.body>) -1001 + reg({1,+,1}<%for.body>) -1000 + reg({0,+,1}<%for.body>) -3000 + reg({0,+,3}<%for.body>) reg({-1000,+,1}<%for.body>) reg({-3000,+,3}<%for.body>) This is the last use we consider for a solution in SolveRecurse, so CurRegs is a large set. (CurRegs is the set of registers that are needed by the previously visited uses in the in-progress solution.) ReqRegs is { {3,+,3}<%for.body>, {1,+,1}<%for.body> } This is the intersection of the regs used by any of the formulas for the current use and CurRegs. Now, the code requires a formula to contain *all* these regs (the comment is simply wrong), otherwise the formula is immediately disqualified. Obviously, no formula for this use contains two regs so they will all get disqualified. The fix modifies the check to allow the formula in this case. The idea is that neither of these formulae is introducing any new registers which is the point of this early pruning as far as I understand. In terms of set arithmetic, we now allow formulas whose used regs are a subset of the required regs not just the other way around. There are few more loops in the test-suite that are now successfully LSRed. I have benchmarked those and found very minimal change. Fixes git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207271 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopStrengthReduce.cpp | 21 ++++++----- .../LoopStrengthReduce/ARM64/lit.local.cfg | 2 +- .../LoopStrengthReduce/ARM64/req-regs.c | 36 +++++++++++++++++++ 3 files changed, 49 insertions(+), 10 deletions(-) create mode 100644 test/Transforms/LoopStrengthReduce/ARM64/req-regs.c diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 16a001ad934..13e4fceec66 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -256,7 +256,7 @@ struct Formula { void InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE); - unsigned getNumRegs() const; + size_t getNumRegs() const; Type *getType() const; void DeleteBaseReg(const SCEV *&S); @@ -351,7 +351,7 @@ void Formula::InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) { /// getNumRegs - Return the total number of register operands used by this /// formula. This does not include register uses implied by non-constant /// addrec strides. -unsigned Formula::getNumRegs() const { +size_t Formula::getNumRegs() const { return !!ScaledReg + BaseRegs.size(); } @@ -4132,19 +4132,22 @@ void LSRInstance::SolveRecurse(SmallVectorImpl &Solution, E = LU.Formulae.end(); I != E; ++I) { const Formula &F = *I; - // Ignore formulae which do not use any of the required registers. - bool SatisfiedReqReg = true; + // Ignore formulae which may not be ideal in terms of register reuse of + // ReqRegs. The formula should use all required registers before + // introducing new ones. + int NumReqRegsToFind = std::min(F.getNumRegs(), ReqRegs.size()); for (SmallSetVector::const_iterator J = ReqRegs.begin(), JE = ReqRegs.end(); J != JE; ++J) { const SCEV *Reg = *J; - if ((!F.ScaledReg || F.ScaledReg != Reg) && - std::find(F.BaseRegs.begin(), F.BaseRegs.end(), Reg) == + if ((F.ScaledReg && F.ScaledReg == Reg) || + std::find(F.BaseRegs.begin(), F.BaseRegs.end(), Reg) != F.BaseRegs.end()) { - SatisfiedReqReg = false; - break; + --NumReqRegsToFind; + if (NumReqRegsToFind == 0) + break; } } - if (!SatisfiedReqReg) { + if (NumReqRegsToFind != 0) { // If none of the formulae satisfied the required registers, then we could // clear ReqRegs and try again. Currently, we simply give up in this case. continue; diff --git a/test/Transforms/LoopStrengthReduce/ARM64/lit.local.cfg b/test/Transforms/LoopStrengthReduce/ARM64/lit.local.cfg index a49957999f0..f8162f04c5f 100644 --- a/test/Transforms/LoopStrengthReduce/ARM64/lit.local.cfg +++ b/test/Transforms/LoopStrengthReduce/ARM64/lit.local.cfg @@ -1,4 +1,4 @@ -config.suffixes = ['.ll'] +config.suffixes = ['.ll' '.c'] targets = set(config.root.targets_to_build.split()) if not 'ARM64' in targets: diff --git a/test/Transforms/LoopStrengthReduce/ARM64/req-regs.c b/test/Transforms/LoopStrengthReduce/ARM64/req-regs.c new file mode 100644 index 00000000000..0c3c1dd5035 --- /dev/null +++ b/test/Transforms/LoopStrengthReduce/ARM64/req-regs.c @@ -0,0 +1,36 @@ +// RUN: clang %s -O3 -target arm64-apple-ios -o - -S -mllvm -debug-only=loop-reduce 2>&1| FileCheck %s +// REQUIRES: asserts + +// LSR used to fail here due to a bug in the ReqRegs test. To complicate +// things, this could only be reproduced with clang because the uses would +// come out in different order when invoked through llc. + +// CHECK: The chosen solution requires +// CHECK-NOT: No Satisfactory Solution + +typedef unsigned long iter_t; +void use_int(int result); + +struct _state { + int N; + int M; + int K; + double* data; +}; +void +do_integer_add(iter_t iterations, void* cookie) +{ + struct _state *pState = (struct _state*)cookie; + register int i; + register int a = pState->N + 57; + + while (iterations-- > 0) { + for (i = 1; i < 1001; ++i) { + a=a+a+i; a=a+a+i; a=a+a+i; a=a+a+i; + a=a+a+i; a=a+a+i; a=a+a+i; a=a+a+i; + a=a+a+i; a=a+a+i; + + } + } + use_int(a); +} -- 2.34.1