diff options
| author | dim <dim@FreeBSD.org> | 2017-04-02 17:24:58 +0000 |
|---|---|---|
| committer | dim <dim@FreeBSD.org> | 2017-04-02 17:24:58 +0000 |
| commit | 60b571e49a90d38697b3aca23020d9da42fc7d7f (patch) | |
| tree | 99351324c24d6cb146b6285b6caffa4d26fce188 /contrib/llvm/lib/Transforms/Scalar/LoopSink.cpp | |
| parent | bea1b22c7a9bce1dfdd73e6e5b65bc4752215180 (diff) | |
| download | FreeBSD-src-60b571e49a90d38697b3aca23020d9da42fc7d7f.zip FreeBSD-src-60b571e49a90d38697b3aca23020d9da42fc7d7f.tar.gz | |
Update clang, llvm, lld, lldb, compiler-rt and libc++ to 4.0.0 release:
MFC r309142 (by emaste):
Add WITH_LLD_AS_LD build knob
If set it installs LLD as /usr/bin/ld. LLD (as of version 3.9) is not
capable of linking the world and kernel, but can self-host and link many
substantial applications. GNU ld continues to be used for the world and
kernel build, regardless of how this knob is set.
It is on by default for arm64, and off for all other CPU architectures.
Sponsored by: The FreeBSD Foundation
MFC r310840:
Reapply 310775, now it also builds correctly if lldb is disabled:
Move llvm-objdump from CLANG_EXTRAS to installed by default
We currently install three tools from binutils 2.17.50: as, ld, and
objdump. Work is underway to migrate to a permissively-licensed
tool-chain, with one goal being the retirement of binutils 2.17.50.
LLVM's llvm-objdump is intended to be compatible with GNU objdump
although it is currently missing some options and may have formatting
differences. Enable it by default for testing and further investigation.
It may later be changed to install as /usr/bin/objdump, it becomes a
fully viable replacement.
Reviewed by: emaste
Differential Revision: https://reviews.freebsd.org/D8879
MFC r312855 (by emaste):
Rename LLD_AS_LD to LLD_IS_LD, for consistency with CLANG_IS_CC
Reported by: Dan McGregor <dan.mcgregor usask.ca>
MFC r313559 | glebius | 2017-02-10 18:34:48 +0100 (Fri, 10 Feb 2017) | 5 lines
Don't check struct rtentry on FreeBSD, it is an internal kernel structure.
On other systems it may be API structure for SIOCADDRT/SIOCDELRT.
Reviewed by: emaste, dim
MFC r314152 (by jkim):
Remove an assembler flag, which is redundant since r309124. The upstream
took care of it by introducing a macro NO_EXEC_STACK_DIRECTIVE.
http://llvm.org/viewvc/llvm-project?rev=273500&view=rev
Reviewed by: dim
MFC r314564:
Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ to
4.0.0 (branches/release_40 296509). The release will follow soon.
Please note that from 3.5.0 onwards, clang, llvm and lldb require C++11
support to build; see UPDATING for more information.
Also note that as of 4.0.0, lld should be able to link the base system
on amd64 and aarch64. See the WITH_LLD_IS_LLD setting in src.conf(5).
Though please be aware that this is work in progress.
Release notes for llvm, clang and lld will be available here:
<http://releases.llvm.org/4.0.0/docs/ReleaseNotes.html>
<http://releases.llvm.org/4.0.0/tools/clang/docs/ReleaseNotes.html>
<http://releases.llvm.org/4.0.0/tools/lld/docs/ReleaseNotes.html>
Thanks to Ed Maste, Jan Beich, Antoine Brodin and Eric Fiselier for
their help.
Relnotes: yes
Exp-run: antoine
PR: 215969, 216008
MFC r314708:
For now, revert r287232 from upstream llvm trunk (by Daniil Fukalov):
[SCEV] limit recursion depth of CompareSCEVComplexity
Summary:
CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled
loop) and runs almost infinite time.
Added cache of "equal" SCEV pairs to earlier cutoff of further
estimation. Recursion depth limit was also introduced as a parameter.
Reviewers: sanjoy
Subscribers: mzolotukhin, tstellarAMD, llvm-commits
Differential Revision: https://reviews.llvm.org/D26389
This commit is the cause of excessive compile times on skein_block.c
(and possibly other files) during kernel builds on amd64.
We never saw the problematic behavior described in this upstream commit,
so for now it is better to revert it. An upstream bug has been filed
here: https://bugs.llvm.org/show_bug.cgi?id=32142
Reported by: mjg
MFC r314795:
Reapply r287232 from upstream llvm trunk (by Daniil Fukalov):
[SCEV] limit recursion depth of CompareSCEVComplexity
Summary:
CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled
loop) and runs almost infinite time.
Added cache of "equal" SCEV pairs to earlier cutoff of further
estimation. Recursion depth limit was also introduced as a parameter.
Reviewers: sanjoy
Subscribers: mzolotukhin, tstellarAMD, llvm-commits
Differential Revision: https://reviews.llvm.org/D26389
Pull in r296992 from upstream llvm trunk (by Sanjoy Das):
[SCEV] Decrease the recursion threshold for CompareValueComplexity
Fixes PR32142.
r287232 accidentally increased the recursion threshold for
CompareValueComplexity from 2 to 32. This change reverses that
change by introducing a separate flag for CompareValueComplexity's
threshold.
The latter revision fixes the excessive compile times for skein_block.c.
MFC r314907 | mmel | 2017-03-08 12:40:27 +0100 (Wed, 08 Mar 2017) | 7 lines
Unbreak ARMv6 world.
The new compiler_rt library imported with clang 4.0.0 have several fatal
issues (non-functional __udivsi3 for example) with ARM specific instrict
functions. As temporary workaround, until upstream solve these problems,
disable all thumb[1][2] related feature.
MFC r315016:
Update clang, llvm, lld, lldb, compiler-rt and libc++ to 4.0.0 release.
We were already very close to the last release candidate, so this is a
pretty minor update.
Relnotes: yes
MFC r316005:
Revert r314907, and pull in r298713 from upstream compiler-rt trunk (by
Weiming Zhao):
builtins: Select correct code fragments when compiling for Thumb1/Thum2/ARM ISA.
Summary:
Value of __ARM_ARCH_ISA_THUMB isn't based on the actual compilation
mode (-mthumb, -marm), it reflect's capability of given CPU.
Due to this:
- use __tbumb__ and __thumb2__ insteand of __ARM_ARCH_ISA_THUMB
- use '.thumb' directive consistently in all affected files
- decorate all thumb functions using
DEFINE_COMPILERRT_THUMB_FUNCTION()
---------
Note: This patch doesn't fix broken Thumb1 variant of __udivsi3 !
Reviewers: weimingz, rengolin, compnerd
Subscribers: aemerson, dim
Differential Revision: https://reviews.llvm.org/D30938
Discussed with: mmel
Diffstat (limited to 'contrib/llvm/lib/Transforms/Scalar/LoopSink.cpp')
| -rw-r--r-- | contrib/llvm/lib/Transforms/Scalar/LoopSink.cpp | 335 |
1 files changed, 335 insertions, 0 deletions
diff --git a/contrib/llvm/lib/Transforms/Scalar/LoopSink.cpp b/contrib/llvm/lib/Transforms/Scalar/LoopSink.cpp new file mode 100644 index 0000000..f3f4152 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Scalar/LoopSink.cpp @@ -0,0 +1,335 @@ +//===-- LoopSink.cpp - Loop Sink Pass ------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass does the inverse transformation of what LICM does. +// It traverses all of the instructions in the loop's preheader and sinks +// them to the loop body where frequency is lower than the loop's preheader. +// This pass is a reverse-transformation of LICM. It differs from the Sink +// pass in the following ways: +// +// * It only handles sinking of instructions from the loop's preheader to the +// loop's body +// * It uses alias set tracker to get more accurate alias info +// * It uses block frequency info to find the optimal sinking locations +// +// Overall algorithm: +// +// For I in Preheader: +// InsertBBs = BBs that uses I +// For BB in sorted(LoopBBs): +// DomBBs = BBs in InsertBBs that are dominated by BB +// if freq(DomBBs) > freq(BB) +// InsertBBs = UseBBs - DomBBs + BB +// For BB in InsertBBs: +// Insert I at BB's beginning +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AliasSetTracker.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/Loads.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Metadata.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/LoopUtils.h" +using namespace llvm; + +#define DEBUG_TYPE "loopsink" + +STATISTIC(NumLoopSunk, "Number of instructions sunk into loop"); +STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop"); + +static cl::opt<unsigned> SinkFrequencyPercentThreshold( + "sink-freq-percent-threshold", cl::Hidden, cl::init(90), + cl::desc("Do not sink instructions that require cloning unless they " + "execute less than this percent of the time.")); + +static cl::opt<unsigned> MaxNumberOfUseBBsForSinking( + "max-uses-for-sinking", cl::Hidden, cl::init(30), + cl::desc("Do not sink instructions that have too many uses.")); + +/// Return adjusted total frequency of \p BBs. +/// +/// * If there is only one BB, sinking instruction will not introduce code +/// size increase. Thus there is no need to adjust the frequency. +/// * If there are more than one BB, sinking would lead to code size increase. +/// In this case, we add some "tax" to the total frequency to make it harder +/// to sink. E.g. +/// Freq(Preheader) = 100 +/// Freq(BBs) = sum(50, 49) = 99 +/// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to +/// BBs as the difference is too small to justify the code size increase. +/// To model this, The adjusted Freq(BBs) will be: +/// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold% +static BlockFrequency adjustedSumFreq(SmallPtrSetImpl<BasicBlock *> &BBs, + BlockFrequencyInfo &BFI) { + BlockFrequency T = 0; + for (BasicBlock *B : BBs) + T += BFI.getBlockFreq(B); + if (BBs.size() > 1) + T /= BranchProbability(SinkFrequencyPercentThreshold, 100); + return T; +} + +/// Return a set of basic blocks to insert sinked instructions. +/// +/// The returned set of basic blocks (BBsToSinkInto) should satisfy: +/// +/// * Inside the loop \p L +/// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto +/// that domintates the UseBB +/// * Has minimum total frequency that is no greater than preheader frequency +/// +/// The purpose of the function is to find the optimal sinking points to +/// minimize execution cost, which is defined as "sum of frequency of +/// BBsToSinkInto". +/// As a result, the returned BBsToSinkInto needs to have minimum total +/// frequency. +/// Additionally, if the total frequency of BBsToSinkInto exceeds preheader +/// frequency, the optimal solution is not sinking (return empty set). +/// +/// \p ColdLoopBBs is used to help find the optimal sinking locations. +/// It stores a list of BBs that is: +/// +/// * Inside the loop \p L +/// * Has a frequency no larger than the loop's preheader +/// * Sorted by BB frequency +/// +/// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()). +/// To avoid expensive computation, we cap the maximum UseBBs.size() in its +/// caller. +static SmallPtrSet<BasicBlock *, 2> +findBBsToSinkInto(const Loop &L, const SmallPtrSetImpl<BasicBlock *> &UseBBs, + const SmallVectorImpl<BasicBlock *> &ColdLoopBBs, + DominatorTree &DT, BlockFrequencyInfo &BFI) { + SmallPtrSet<BasicBlock *, 2> BBsToSinkInto; + if (UseBBs.size() == 0) + return BBsToSinkInto; + + BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end()); + SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB; + + // For every iteration: + // * Pick the ColdestBB from ColdLoopBBs + // * Find the set BBsDominatedByColdestBB that satisfy: + // - BBsDominatedByColdestBB is a subset of BBsToSinkInto + // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB + // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove + // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to + // BBsToSinkInto + for (BasicBlock *ColdestBB : ColdLoopBBs) { + BBsDominatedByColdestBB.clear(); + for (BasicBlock *SinkedBB : BBsToSinkInto) + if (DT.dominates(ColdestBB, SinkedBB)) + BBsDominatedByColdestBB.insert(SinkedBB); + if (BBsDominatedByColdestBB.size() == 0) + continue; + if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) > + BFI.getBlockFreq(ColdestBB)) { + for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) { + BBsToSinkInto.erase(DominatedBB); + } + BBsToSinkInto.insert(ColdestBB); + } + } + + // If the total frequency of BBsToSinkInto is larger than preheader frequency, + // do not sink. + if (adjustedSumFreq(BBsToSinkInto, BFI) > + BFI.getBlockFreq(L.getLoopPreheader())) + BBsToSinkInto.clear(); + return BBsToSinkInto; +} + +// Sinks \p I from the loop \p L's preheader to its uses. Returns true if +// sinking is successful. +// \p LoopBlockNumber is used to sort the insertion blocks to ensure +// determinism. +static bool sinkInstruction(Loop &L, Instruction &I, + const SmallVectorImpl<BasicBlock *> &ColdLoopBBs, + const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber, + LoopInfo &LI, DominatorTree &DT, + BlockFrequencyInfo &BFI) { + // Compute the set of blocks in loop L which contain a use of I. + SmallPtrSet<BasicBlock *, 2> BBs; + for (auto &U : I.uses()) { + Instruction *UI = cast<Instruction>(U.getUser()); + // We cannot sink I to PHI-uses. + if (dyn_cast<PHINode>(UI)) + return false; + // We cannot sink I if it has uses outside of the loop. + if (!L.contains(LI.getLoopFor(UI->getParent()))) + return false; + BBs.insert(UI->getParent()); + } + + // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max + // BBs.size() to avoid expensive computation. + // FIXME: Handle code size growth for min_size and opt_size. + if (BBs.size() > MaxNumberOfUseBBsForSinking) + return false; + + // Find the set of BBs that we should insert a copy of I. + SmallPtrSet<BasicBlock *, 2> BBsToSinkInto = + findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI); + if (BBsToSinkInto.empty()) + return false; + + // Copy the final BBs into a vector and sort them using the total ordering + // of the loop block numbers as iterating the set doesn't give a useful + // order. No need to stable sort as the block numbers are a total ordering. + SmallVector<BasicBlock *, 2> SortedBBsToSinkInto; + SortedBBsToSinkInto.insert(SortedBBsToSinkInto.begin(), BBsToSinkInto.begin(), + BBsToSinkInto.end()); + std::sort(SortedBBsToSinkInto.begin(), SortedBBsToSinkInto.end(), + [&](BasicBlock *A, BasicBlock *B) { + return *LoopBlockNumber.find(A) < *LoopBlockNumber.find(B); + }); + + BasicBlock *MoveBB = *SortedBBsToSinkInto.begin(); + // FIXME: Optimize the efficiency for cloned value replacement. The current + // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()). + for (BasicBlock *N : SortedBBsToSinkInto) { + if (N == MoveBB) + continue; + // Clone I and replace its uses. + Instruction *IC = I.clone(); + IC->setName(I.getName()); + IC->insertBefore(&*N->getFirstInsertionPt()); + // Replaces uses of I with IC in N + for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE;) { + Use &U = *UI++; + auto *I = cast<Instruction>(U.getUser()); + if (I->getParent() == N) + U.set(IC); + } + // Replaces uses of I with IC in blocks dominated by N + replaceDominatedUsesWith(&I, IC, DT, N); + DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName() + << '\n'); + NumLoopSunkCloned++; + } + DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n'); + NumLoopSunk++; + I.moveBefore(&*MoveBB->getFirstInsertionPt()); + + return true; +} + +/// Sinks instructions from loop's preheader to the loop body if the +/// sum frequency of inserted copy is smaller than preheader's frequency. +static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI, + DominatorTree &DT, + BlockFrequencyInfo &BFI, + ScalarEvolution *SE) { + BasicBlock *Preheader = L.getLoopPreheader(); + if (!Preheader) + return false; + + // Enable LoopSink only when runtime profile is available. + // With static profile, the sinking decision may be sub-optimal. + if (!Preheader->getParent()->getEntryCount()) + return false; + + const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader); + // If there are no basic blocks with lower frequency than the preheader then + // we can avoid the detailed analysis as we will never find profitable sinking + // opportunities. + if (all_of(L.blocks(), [&](const BasicBlock *BB) { + return BFI.getBlockFreq(BB) > PreheaderFreq; + })) + return false; + + bool Changed = false; + AliasSetTracker CurAST(AA); + + // Compute alias set. + for (BasicBlock *BB : L.blocks()) + CurAST.add(*BB); + + // Sort loop's basic blocks by frequency + SmallVector<BasicBlock *, 10> ColdLoopBBs; + SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber; + int i = 0; + for (BasicBlock *B : L.blocks()) + if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) { + ColdLoopBBs.push_back(B); + LoopBlockNumber[B] = ++i; + } + std::stable_sort(ColdLoopBBs.begin(), ColdLoopBBs.end(), + [&](BasicBlock *A, BasicBlock *B) { + return BFI.getBlockFreq(A) < BFI.getBlockFreq(B); + }); + + // Traverse preheader's instructions in reverse order becaue if A depends + // on B (A appears after B), A needs to be sinked first before B can be + // sinked. + for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) { + Instruction *I = &*II++; + // No need to check for instruction's operands are loop invariant. + assert(L.hasLoopInvariantOperands(I) && + "Insts in a loop's preheader should have loop invariant operands!"); + if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr)) + continue; + if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI)) + Changed = true; + } + + if (Changed && SE) + SE->forgetLoopDispositions(&L); + return Changed; +} + +namespace { +struct LegacyLoopSinkPass : public LoopPass { + static char ID; + LegacyLoopSinkPass() : LoopPass(ID) { + initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnLoop(Loop *L, LPPassManager &LPM) override { + if (skipLoop(L)) + return false; + + auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>(); + return sinkLoopInvariantInstructions( + *L, getAnalysis<AAResultsWrapperPass>().getAAResults(), + getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), + getAnalysis<DominatorTreeWrapperPass>().getDomTree(), + getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(), + SE ? &SE->getSE() : nullptr); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + AU.addRequired<BlockFrequencyInfoWrapperPass>(); + getLoopAnalysisUsage(AU); + } +}; +} + +char LegacyLoopSinkPass::ID = 0; +INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, + false) +INITIALIZE_PASS_DEPENDENCY(LoopPass) +INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) +INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) + +Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); } |
