Bug Summary

File:llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
Warning:line 959, column 5
Forming reference to null pointer

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ControlHeightReduction.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/Transforms/Instrumentation -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/Transforms/Instrumentation -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/Transforms/Instrumentation -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-04-14-063029-18377-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp

/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp

1//===-- ControlHeightReduction.cpp - Control Height Reduction -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass merges conditional blocks of code and reduces the number of
10// conditional branches in the hot paths based on profiles.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/Instrumentation/ControlHeightReduction.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/ADT/StringSet.h"
19#include "llvm/Analysis/BlockFrequencyInfo.h"
20#include "llvm/Analysis/GlobalsModRef.h"
21#include "llvm/Analysis/OptimizationRemarkEmitter.h"
22#include "llvm/Analysis/ProfileSummaryInfo.h"
23#include "llvm/Analysis/RegionInfo.h"
24#include "llvm/Analysis/RegionIterator.h"
25#include "llvm/Analysis/ValueTracking.h"
26#include "llvm/IR/CFG.h"
27#include "llvm/IR/Dominators.h"
28#include "llvm/IR/IRBuilder.h"
29#include "llvm/IR/MDBuilder.h"
30#include "llvm/InitializePasses.h"
31#include "llvm/Support/BranchProbability.h"
32#include "llvm/Support/CommandLine.h"
33#include "llvm/Support/MemoryBuffer.h"
34#include "llvm/Transforms/Utils.h"
35#include "llvm/Transforms/Utils/BasicBlockUtils.h"
36#include "llvm/Transforms/Utils/Cloning.h"
37#include "llvm/Transforms/Utils/ValueMapper.h"
38
39#include <set>
40#include <sstream>
41
42using namespace llvm;
43
44#define DEBUG_TYPE"chr" "chr"
45
46#define CHR_DEBUG(X)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { X; } } while (false)
LLVM_DEBUG(X)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { X; } } while (false)
47
48static cl::opt<bool> ForceCHR("force-chr", cl::init(false), cl::Hidden,
49 cl::desc("Apply CHR for all functions"));
50
51static cl::opt<double> CHRBiasThreshold(
52 "chr-bias-threshold", cl::init(0.99), cl::Hidden,
53 cl::desc("CHR considers a branch bias greater than this ratio as biased"));
54
55static cl::opt<unsigned> CHRMergeThreshold(
56 "chr-merge-threshold", cl::init(2), cl::Hidden,
57 cl::desc("CHR merges a group of N branches/selects where N >= this value"));
58
59static cl::opt<std::string> CHRModuleList(
60 "chr-module-list", cl::init(""), cl::Hidden,
61 cl::desc("Specify file to retrieve the list of modules to apply CHR to"));
62
63static cl::opt<std::string> CHRFunctionList(
64 "chr-function-list", cl::init(""), cl::Hidden,
65 cl::desc("Specify file to retrieve the list of functions to apply CHR to"));
66
67static StringSet<> CHRModules;
68static StringSet<> CHRFunctions;
69
70static void parseCHRFilterFiles() {
71 if (!CHRModuleList.empty()) {
72 auto FileOrErr = MemoryBuffer::getFile(CHRModuleList);
73 if (!FileOrErr) {
74 errs() << "Error: Couldn't read the chr-module-list file " << CHRModuleList << "\n";
75 std::exit(1);
76 }
77 StringRef Buf = FileOrErr->get()->getBuffer();
78 SmallVector<StringRef, 0> Lines;
79 Buf.split(Lines, '\n');
80 for (StringRef Line : Lines) {
81 Line = Line.trim();
82 if (!Line.empty())
83 CHRModules.insert(Line);
84 }
85 }
86 if (!CHRFunctionList.empty()) {
87 auto FileOrErr = MemoryBuffer::getFile(CHRFunctionList);
88 if (!FileOrErr) {
89 errs() << "Error: Couldn't read the chr-function-list file " << CHRFunctionList << "\n";
90 std::exit(1);
91 }
92 StringRef Buf = FileOrErr->get()->getBuffer();
93 SmallVector<StringRef, 0> Lines;
94 Buf.split(Lines, '\n');
95 for (StringRef Line : Lines) {
96 Line = Line.trim();
97 if (!Line.empty())
98 CHRFunctions.insert(Line);
99 }
100 }
101}
102
103namespace {
104class ControlHeightReductionLegacyPass : public FunctionPass {
105public:
106 static char ID;
107
108 ControlHeightReductionLegacyPass() : FunctionPass(ID) {
109 initializeControlHeightReductionLegacyPassPass(
110 *PassRegistry::getPassRegistry());
111 parseCHRFilterFiles();
112 }
113
114 bool runOnFunction(Function &F) override;
115 void getAnalysisUsage(AnalysisUsage &AU) const override {
116 AU.addRequired<BlockFrequencyInfoWrapperPass>();
117 AU.addRequired<DominatorTreeWrapperPass>();
118 AU.addRequired<ProfileSummaryInfoWrapperPass>();
119 AU.addRequired<RegionInfoPass>();
120 AU.addPreserved<GlobalsAAWrapperPass>();
121 }
122};
123} // end anonymous namespace
124
125char ControlHeightReductionLegacyPass::ID = 0;
126
127INITIALIZE_PASS_BEGIN(ControlHeightReductionLegacyPass,static void *initializeControlHeightReductionLegacyPassPassOnce
(PassRegistry &Registry) {
128 "chr",static void *initializeControlHeightReductionLegacyPassPassOnce
(PassRegistry &Registry) {
129 "Reduce control height in the hot paths",static void *initializeControlHeightReductionLegacyPassPassOnce
(PassRegistry &Registry) {
130 false, false)static void *initializeControlHeightReductionLegacyPassPassOnce
(PassRegistry &Registry) {
131INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)initializeBlockFrequencyInfoWrapperPassPass(Registry);
132INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
133INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)initializeProfileSummaryInfoWrapperPassPass(Registry);
134INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)initializeRegionInfoPassPass(Registry);
135INITIALIZE_PASS_END(ControlHeightReductionLegacyPass,PassInfo *PI = new PassInfo( "Reduce control height in the hot paths"
, "chr", &ControlHeightReductionLegacyPass::ID, PassInfo::
NormalCtor_t(callDefaultCtor<ControlHeightReductionLegacyPass
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeControlHeightReductionLegacyPassPassFlag
; void llvm::initializeControlHeightReductionLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeControlHeightReductionLegacyPassPassFlag
, initializeControlHeightReductionLegacyPassPassOnce, std::ref
(Registry)); }
136 "chr",PassInfo *PI = new PassInfo( "Reduce control height in the hot paths"
, "chr", &ControlHeightReductionLegacyPass::ID, PassInfo::
NormalCtor_t(callDefaultCtor<ControlHeightReductionLegacyPass
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeControlHeightReductionLegacyPassPassFlag
; void llvm::initializeControlHeightReductionLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeControlHeightReductionLegacyPassPassFlag
, initializeControlHeightReductionLegacyPassPassOnce, std::ref
(Registry)); }
137 "Reduce control height in the hot paths",PassInfo *PI = new PassInfo( "Reduce control height in the hot paths"
, "chr", &ControlHeightReductionLegacyPass::ID, PassInfo::
NormalCtor_t(callDefaultCtor<ControlHeightReductionLegacyPass
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeControlHeightReductionLegacyPassPassFlag
; void llvm::initializeControlHeightReductionLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeControlHeightReductionLegacyPassPassFlag
, initializeControlHeightReductionLegacyPassPassOnce, std::ref
(Registry)); }
138 false, false)PassInfo *PI = new PassInfo( "Reduce control height in the hot paths"
, "chr", &ControlHeightReductionLegacyPass::ID, PassInfo::
NormalCtor_t(callDefaultCtor<ControlHeightReductionLegacyPass
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeControlHeightReductionLegacyPassPassFlag
; void llvm::initializeControlHeightReductionLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeControlHeightReductionLegacyPassPassFlag
, initializeControlHeightReductionLegacyPassPassOnce, std::ref
(Registry)); }
139
140FunctionPass *llvm::createControlHeightReductionLegacyPass() {
141 return new ControlHeightReductionLegacyPass();
142}
143
144namespace {
145
146struct CHRStats {
147 CHRStats() : NumBranches(0), NumBranchesDelta(0),
148 WeightedNumBranchesDelta(0) {}
149 void print(raw_ostream &OS) const {
150 OS << "CHRStats: NumBranches " << NumBranches
151 << " NumBranchesDelta " << NumBranchesDelta
152 << " WeightedNumBranchesDelta " << WeightedNumBranchesDelta;
153 }
154 uint64_t NumBranches; // The original number of conditional branches /
155 // selects
156 uint64_t NumBranchesDelta; // The decrease of the number of conditional
157 // branches / selects in the hot paths due to CHR.
158 uint64_t WeightedNumBranchesDelta; // NumBranchesDelta weighted by the profile
159 // count at the scope entry.
160};
161
162// RegInfo - some properties of a Region.
163struct RegInfo {
164 RegInfo() : R(nullptr), HasBranch(false) {}
165 RegInfo(Region *RegionIn) : R(RegionIn), HasBranch(false) {}
166 Region *R;
167 bool HasBranch;
168 SmallVector<SelectInst *, 8> Selects;
169};
170
171typedef DenseMap<Region *, DenseSet<Instruction *>> HoistStopMapTy;
172
173// CHRScope - a sequence of regions to CHR together. It corresponds to a
174// sequence of conditional blocks. It can have subscopes which correspond to
175// nested conditional blocks. Nested CHRScopes form a tree.
176class CHRScope {
177 public:
178 CHRScope(RegInfo RI) : BranchInsertPoint(nullptr) {
179 assert(RI.R && "Null RegionIn")((RI.R && "Null RegionIn") ? static_cast<void> (
0) : __assert_fail ("RI.R && \"Null RegionIn\"", "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 179, __PRETTY_FUNCTION__))
;
180 RegInfos.push_back(RI);
181 }
182
183 Region *getParentRegion() {
184 assert(RegInfos.size() > 0 && "Empty CHRScope")((RegInfos.size() > 0 && "Empty CHRScope") ? static_cast
<void> (0) : __assert_fail ("RegInfos.size() > 0 && \"Empty CHRScope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 184, __PRETTY_FUNCTION__))
;
185 Region *Parent = RegInfos[0].R->getParent();
186 assert(Parent && "Unexpected to call this on the top-level region")((Parent && "Unexpected to call this on the top-level region"
) ? static_cast<void> (0) : __assert_fail ("Parent && \"Unexpected to call this on the top-level region\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 186, __PRETTY_FUNCTION__))
;
187 return Parent;
188 }
189
190 BasicBlock *getEntryBlock() {
191 assert(RegInfos.size() > 0 && "Empty CHRScope")((RegInfos.size() > 0 && "Empty CHRScope") ? static_cast
<void> (0) : __assert_fail ("RegInfos.size() > 0 && \"Empty CHRScope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 191, __PRETTY_FUNCTION__))
;
192 return RegInfos.front().R->getEntry();
193 }
194
195 BasicBlock *getExitBlock() {
196 assert(RegInfos.size() > 0 && "Empty CHRScope")((RegInfos.size() > 0 && "Empty CHRScope") ? static_cast
<void> (0) : __assert_fail ("RegInfos.size() > 0 && \"Empty CHRScope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 196, __PRETTY_FUNCTION__))
;
197 return RegInfos.back().R->getExit();
198 }
199
200 bool appendable(CHRScope *Next) {
201 // The next scope is appendable only if this scope is directly connected to
202 // it (which implies it post-dominates this scope) and this scope dominates
203 // it (no edge to the next scope outside this scope).
204 BasicBlock *NextEntry = Next->getEntryBlock();
205 if (getExitBlock() != NextEntry)
206 // Not directly connected.
207 return false;
208 Region *LastRegion = RegInfos.back().R;
209 for (BasicBlock *Pred : predecessors(NextEntry))
210 if (!LastRegion->contains(Pred))
211 // There's an edge going into the entry of the next scope from outside
212 // of this scope.
213 return false;
214 return true;
215 }
216
217 void append(CHRScope *Next) {
218 assert(RegInfos.size() > 0 && "Empty CHRScope")((RegInfos.size() > 0 && "Empty CHRScope") ? static_cast
<void> (0) : __assert_fail ("RegInfos.size() > 0 && \"Empty CHRScope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 218, __PRETTY_FUNCTION__))
;
219 assert(Next->RegInfos.size() > 0 && "Empty CHRScope")((Next->RegInfos.size() > 0 && "Empty CHRScope"
) ? static_cast<void> (0) : __assert_fail ("Next->RegInfos.size() > 0 && \"Empty CHRScope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 219, __PRETTY_FUNCTION__))
;
220 assert(getParentRegion() == Next->getParentRegion() &&((getParentRegion() == Next->getParentRegion() && "Must be siblings"
) ? static_cast<void> (0) : __assert_fail ("getParentRegion() == Next->getParentRegion() && \"Must be siblings\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 221, __PRETTY_FUNCTION__))
221 "Must be siblings")((getParentRegion() == Next->getParentRegion() && "Must be siblings"
) ? static_cast<void> (0) : __assert_fail ("getParentRegion() == Next->getParentRegion() && \"Must be siblings\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 221, __PRETTY_FUNCTION__))
;
222 assert(getExitBlock() == Next->getEntryBlock() &&((getExitBlock() == Next->getEntryBlock() && "Must be adjacent"
) ? static_cast<void> (0) : __assert_fail ("getExitBlock() == Next->getEntryBlock() && \"Must be adjacent\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 223, __PRETTY_FUNCTION__))
223 "Must be adjacent")((getExitBlock() == Next->getEntryBlock() && "Must be adjacent"
) ? static_cast<void> (0) : __assert_fail ("getExitBlock() == Next->getEntryBlock() && \"Must be adjacent\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 223, __PRETTY_FUNCTION__))
;
224 RegInfos.append(Next->RegInfos.begin(), Next->RegInfos.end());
225 Subs.append(Next->Subs.begin(), Next->Subs.end());
226 }
227
228 void addSub(CHRScope *SubIn) {
229#ifndef NDEBUG
230 bool IsChild = false;
231 for (RegInfo &RI : RegInfos)
232 if (RI.R == SubIn->getParentRegion()) {
233 IsChild = true;
234 break;
235 }
236 assert(IsChild && "Must be a child")((IsChild && "Must be a child") ? static_cast<void
> (0) : __assert_fail ("IsChild && \"Must be a child\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 236, __PRETTY_FUNCTION__))
;
237#endif
238 Subs.push_back(SubIn);
239 }
240
241 // Split this scope at the boundary region into two, which will belong to the
242 // tail and returns the tail.
243 CHRScope *split(Region *Boundary) {
244 assert(Boundary && "Boundary null")((Boundary && "Boundary null") ? static_cast<void>
(0) : __assert_fail ("Boundary && \"Boundary null\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 244, __PRETTY_FUNCTION__))
;
245 assert(RegInfos.begin()->R != Boundary &&((RegInfos.begin()->R != Boundary && "Can't be split at beginning"
) ? static_cast<void> (0) : __assert_fail ("RegInfos.begin()->R != Boundary && \"Can't be split at beginning\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 246, __PRETTY_FUNCTION__))
246 "Can't be split at beginning")((RegInfos.begin()->R != Boundary && "Can't be split at beginning"
) ? static_cast<void> (0) : __assert_fail ("RegInfos.begin()->R != Boundary && \"Can't be split at beginning\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 246, __PRETTY_FUNCTION__))
;
247 auto BoundaryIt = llvm::find_if(
248 RegInfos, [&Boundary](const RegInfo &RI) { return Boundary == RI.R; });
249 if (BoundaryIt == RegInfos.end())
250 return nullptr;
251 ArrayRef<RegInfo> TailRegInfos(BoundaryIt, RegInfos.end());
252 DenseSet<Region *> TailRegionSet;
253 for (const RegInfo &RI : TailRegInfos)
254 TailRegionSet.insert(RI.R);
255
256 auto TailIt =
257 std::stable_partition(Subs.begin(), Subs.end(), [&](CHRScope *Sub) {
258 assert(Sub && "null Sub")((Sub && "null Sub") ? static_cast<void> (0) : __assert_fail
("Sub && \"null Sub\"", "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 258, __PRETTY_FUNCTION__))
;
259 Region *Parent = Sub->getParentRegion();
260 if (TailRegionSet.count(Parent))
261 return false;
262
263 assert(llvm::any_of(((llvm::any_of( RegInfos, [&Parent](const RegInfo &RI
) { return Parent == RI.R; }) && "Must be in head") ?
static_cast<void> (0) : __assert_fail ("llvm::any_of( RegInfos, [&Parent](const RegInfo &RI) { return Parent == RI.R; }) && \"Must be in head\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 266, __PRETTY_FUNCTION__))
264 RegInfos,((llvm::any_of( RegInfos, [&Parent](const RegInfo &RI
) { return Parent == RI.R; }) && "Must be in head") ?
static_cast<void> (0) : __assert_fail ("llvm::any_of( RegInfos, [&Parent](const RegInfo &RI) { return Parent == RI.R; }) && \"Must be in head\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 266, __PRETTY_FUNCTION__))
265 [&Parent](const RegInfo &RI) { return Parent == RI.R; }) &&((llvm::any_of( RegInfos, [&Parent](const RegInfo &RI
) { return Parent == RI.R; }) && "Must be in head") ?
static_cast<void> (0) : __assert_fail ("llvm::any_of( RegInfos, [&Parent](const RegInfo &RI) { return Parent == RI.R; }) && \"Must be in head\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 266, __PRETTY_FUNCTION__))
266 "Must be in head")((llvm::any_of( RegInfos, [&Parent](const RegInfo &RI
) { return Parent == RI.R; }) && "Must be in head") ?
static_cast<void> (0) : __assert_fail ("llvm::any_of( RegInfos, [&Parent](const RegInfo &RI) { return Parent == RI.R; }) && \"Must be in head\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 266, __PRETTY_FUNCTION__))
;
267 return true;
268 });
269 ArrayRef<CHRScope *> TailSubs(TailIt, Subs.end());
270
271 assert(HoistStopMap.empty() && "MapHoistStops must be empty")((HoistStopMap.empty() && "MapHoistStops must be empty"
) ? static_cast<void> (0) : __assert_fail ("HoistStopMap.empty() && \"MapHoistStops must be empty\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 271, __PRETTY_FUNCTION__))
;
272 auto *Scope = new CHRScope(TailRegInfos, TailSubs);
273 RegInfos.erase(BoundaryIt, RegInfos.end());
274 Subs.erase(TailIt, Subs.end());
275 return Scope;
276 }
277
278 bool contains(Instruction *I) const {
279 BasicBlock *Parent = I->getParent();
280 for (const RegInfo &RI : RegInfos)
281 if (RI.R->contains(Parent))
282 return true;
283 return false;
284 }
285
286 void print(raw_ostream &OS) const;
287
288 SmallVector<RegInfo, 8> RegInfos; // Regions that belong to this scope
289 SmallVector<CHRScope *, 8> Subs; // Subscopes.
290
291 // The instruction at which to insert the CHR conditional branch (and hoist
292 // the dependent condition values).
293 Instruction *BranchInsertPoint;
294
295 // True-biased and false-biased regions (conditional blocks),
296 // respectively. Used only for the outermost scope and includes regions in
297 // subscopes. The rest are unbiased.
298 DenseSet<Region *> TrueBiasedRegions;
299 DenseSet<Region *> FalseBiasedRegions;
300 // Among the biased regions, the regions that get CHRed.
301 SmallVector<RegInfo, 8> CHRRegions;
302
303 // True-biased and false-biased selects, respectively. Used only for the
304 // outermost scope and includes ones in subscopes.
305 DenseSet<SelectInst *> TrueBiasedSelects;
306 DenseSet<SelectInst *> FalseBiasedSelects;
307
308 // Map from one of the above regions to the instructions to stop
309 // hoisting instructions at through use-def chains.
310 HoistStopMapTy HoistStopMap;
311
312 private:
313 CHRScope(ArrayRef<RegInfo> RegInfosIn, ArrayRef<CHRScope *> SubsIn)
314 : RegInfos(RegInfosIn.begin(), RegInfosIn.end()),
315 Subs(SubsIn.begin(), SubsIn.end()), BranchInsertPoint(nullptr) {}
316};
317
318class CHR {
319 public:
320 CHR(Function &Fin, BlockFrequencyInfo &BFIin, DominatorTree &DTin,
321 ProfileSummaryInfo &PSIin, RegionInfo &RIin,
322 OptimizationRemarkEmitter &OREin)
323 : F(Fin), BFI(BFIin), DT(DTin), PSI(PSIin), RI(RIin), ORE(OREin) {}
324
325 ~CHR() {
326 for (CHRScope *Scope : Scopes) {
327 delete Scope;
328 }
329 }
330
331 bool run();
332
333 private:
334 // See the comments in CHR::run() for the high level flow of the algorithm and
335 // what the following functions do.
336
337 void findScopes(SmallVectorImpl<CHRScope *> &Output) {
338 Region *R = RI.getTopLevelRegion();
339 if (CHRScope *Scope = findScopes(R, nullptr, nullptr, Output)) {
340 Output.push_back(Scope);
341 }
342 }
343 CHRScope *findScopes(Region *R, Region *NextRegion, Region *ParentRegion,
344 SmallVectorImpl<CHRScope *> &Scopes);
345 CHRScope *findScope(Region *R);
346 void checkScopeHoistable(CHRScope *Scope);
347
348 void splitScopes(SmallVectorImpl<CHRScope *> &Input,
349 SmallVectorImpl<CHRScope *> &Output);
350 SmallVector<CHRScope *, 8> splitScope(CHRScope *Scope,
351 CHRScope *Outer,
352 DenseSet<Value *> *OuterConditionValues,
353 Instruction *OuterInsertPoint,
354 SmallVectorImpl<CHRScope *> &Output,
355 DenseSet<Instruction *> &Unhoistables);
356
357 void classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes);
358 void classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope);
359
360 void filterScopes(SmallVectorImpl<CHRScope *> &Input,
361 SmallVectorImpl<CHRScope *> &Output);
362
363 void setCHRRegions(SmallVectorImpl<CHRScope *> &Input,
364 SmallVectorImpl<CHRScope *> &Output);
365 void setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope);
366
367 void sortScopes(SmallVectorImpl<CHRScope *> &Input,
368 SmallVectorImpl<CHRScope *> &Output);
369
370 void transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes);
371 void transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs);
372 void cloneScopeBlocks(CHRScope *Scope,
373 BasicBlock *PreEntryBlock,
374 BasicBlock *ExitBlock,
375 Region *LastRegion,
376 ValueToValueMapTy &VMap);
377 BranchInst *createMergedBranch(BasicBlock *PreEntryBlock,
378 BasicBlock *EntryBlock,
379 BasicBlock *NewEntryBlock,
380 ValueToValueMapTy &VMap);
381 void fixupBranchesAndSelects(CHRScope *Scope,
382 BasicBlock *PreEntryBlock,
383 BranchInst *MergedBR,
384 uint64_t ProfileCount);
385 void fixupBranch(Region *R,
386 CHRScope *Scope,
387 IRBuilder<> &IRB,
388 Value *&MergedCondition, BranchProbability &CHRBranchBias);
389 void fixupSelect(SelectInst* SI,
390 CHRScope *Scope,
391 IRBuilder<> &IRB,
392 Value *&MergedCondition, BranchProbability &CHRBranchBias);
393 void addToMergedCondition(bool IsTrueBiased, Value *Cond,
394 Instruction *BranchOrSelect,
395 CHRScope *Scope,
396 IRBuilder<> &IRB,
397 Value *&MergedCondition);
398
399 Function &F;
400 BlockFrequencyInfo &BFI;
401 DominatorTree &DT;
402 ProfileSummaryInfo &PSI;
403 RegionInfo &RI;
404 OptimizationRemarkEmitter &ORE;
405 CHRStats Stats;
406
407 // All the true-biased regions in the function
408 DenseSet<Region *> TrueBiasedRegionsGlobal;
409 // All the false-biased regions in the function
410 DenseSet<Region *> FalseBiasedRegionsGlobal;
411 // All the true-biased selects in the function
412 DenseSet<SelectInst *> TrueBiasedSelectsGlobal;
413 // All the false-biased selects in the function
414 DenseSet<SelectInst *> FalseBiasedSelectsGlobal;
415 // A map from biased regions to their branch bias
416 DenseMap<Region *, BranchProbability> BranchBiasMap;
417 // A map from biased selects to their branch bias
418 DenseMap<SelectInst *, BranchProbability> SelectBiasMap;
419 // All the scopes.
420 DenseSet<CHRScope *> Scopes;
421};
422
423} // end anonymous namespace
424
425static inline
426raw_ostream LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) &operator<<(raw_ostream &OS,
427 const CHRStats &Stats) {
428 Stats.print(OS);
429 return OS;
430}
431
432static inline
433raw_ostream &operator<<(raw_ostream &OS, const CHRScope &Scope) {
434 Scope.print(OS);
435 return OS;
436}
437
438static bool shouldApply(Function &F, ProfileSummaryInfo& PSI) {
439 if (ForceCHR)
440 return true;
441
442 if (!CHRModuleList.empty() || !CHRFunctionList.empty()) {
443 if (CHRModules.count(F.getParent()->getName()))
444 return true;
445 return CHRFunctions.count(F.getName());
446 }
447
448 assert(PSI.hasProfileSummary() && "Empty PSI?")((PSI.hasProfileSummary() && "Empty PSI?") ? static_cast
<void> (0) : __assert_fail ("PSI.hasProfileSummary() && \"Empty PSI?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 448, __PRETTY_FUNCTION__))
;
449 return PSI.isFunctionEntryHot(&F);
450}
451
452static void LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) dumpIR(Function &F, const char *Label,
453 CHRStats *Stats) {
454 StringRef FuncName = F.getName();
455 StringRef ModuleName = F.getParent()->getName();
456 (void)(FuncName); // Unused in release build.
457 (void)(ModuleName); // Unused in release build.
458 CHR_DEBUG(dbgs() << "CHR IR dump " << Label << " " << ModuleName << " "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "CHR IR dump " << Label <<
" " << ModuleName << " " << FuncName; } } while
(false)
459 << FuncName)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "CHR IR dump " << Label <<
" " << ModuleName << " " << FuncName; } } while
(false)
;
460 if (Stats)
461 CHR_DEBUG(dbgs() << " " << *Stats)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << " " << *Stats; } } while (false
)
;
462 CHR_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "\n"; } } while (false)
;
463 CHR_DEBUG(F.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { F.dump(); } } while (false)
;
464}
465
466void CHRScope::print(raw_ostream &OS) const {
467 assert(RegInfos.size() > 0 && "Empty CHRScope")((RegInfos.size() > 0 && "Empty CHRScope") ? static_cast
<void> (0) : __assert_fail ("RegInfos.size() > 0 && \"Empty CHRScope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 467, __PRETTY_FUNCTION__))
;
468 OS << "CHRScope[";
469 OS << RegInfos.size() << ", Regions[";
470 for (const RegInfo &RI : RegInfos) {
471 OS << RI.R->getNameStr();
472 if (RI.HasBranch)
473 OS << " B";
474 if (RI.Selects.size() > 0)
475 OS << " S" << RI.Selects.size();
476 OS << ", ";
477 }
478 if (RegInfos[0].R->getParent()) {
479 OS << "], Parent " << RegInfos[0].R->getParent()->getNameStr();
480 } else {
481 // top level region
482 OS << "]";
483 }
484 OS << ", Subs[";
485 for (CHRScope *Sub : Subs) {
486 OS << *Sub << ", ";
487 }
488 OS << "]]";
489}
490
491// Return true if the given instruction type can be hoisted by CHR.
492static bool isHoistableInstructionType(Instruction *I) {
493 return isa<BinaryOperator>(I) || isa<CastInst>(I) || isa<SelectInst>(I) ||
494 isa<GetElementPtrInst>(I) || isa<CmpInst>(I) ||
495 isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
496 isa<ShuffleVectorInst>(I) || isa<ExtractValueInst>(I) ||
497 isa<InsertValueInst>(I);
498}
499
500// Return true if the given instruction can be hoisted by CHR.
501static bool isHoistable(Instruction *I, DominatorTree &DT) {
502 if (!isHoistableInstructionType(I))
503 return false;
504 return isSafeToSpeculativelyExecute(I, nullptr, &DT);
505}
506
507// Recursively traverse the use-def chains of the given value and return a set
508// of the unhoistable base values defined within the scope (excluding the
509// first-region entry block) or the (hoistable or unhoistable) base values that
510// are defined outside (including the first-region entry block) of the
511// scope. The returned set doesn't include constants.
512static const std::set<Value *> &
513getBaseValues(Value *V, DominatorTree &DT,
514 DenseMap<Value *, std::set<Value *>> &Visited) {
515 auto It = Visited.find(V);
516 if (It != Visited.end()) {
517 return It->second;
518 }
519 std::set<Value *> Result;
520 if (auto *I = dyn_cast<Instruction>(V)) {
521 // We don't stop at a block that's not in the Scope because we would miss
522 // some instructions that are based on the same base values if we stop
523 // there.
524 if (!isHoistable(I, DT)) {
525 Result.insert(I);
526 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
527 }
528 // I is hoistable above the Scope.
529 for (Value *Op : I->operands()) {
530 const std::set<Value *> &OpResult = getBaseValues(Op, DT, Visited);
531 Result.insert(OpResult.begin(), OpResult.end());
532 }
533 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
534 }
535 if (isa<Argument>(V)) {
536 Result.insert(V);
537 }
538 // We don't include others like constants because those won't lead to any
539 // chance of folding of conditions (eg two bit checks merged into one check)
540 // after CHR.
541 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
542}
543
544// Return true if V is already hoisted or can be hoisted (along with its
545// operands) above the insert point. When it returns true and HoistStops is
546// non-null, the instructions to stop hoisting at through the use-def chains are
547// inserted into HoistStops.
548static bool
549checkHoistValue(Value *V, Instruction *InsertPoint, DominatorTree &DT,
550 DenseSet<Instruction *> &Unhoistables,
551 DenseSet<Instruction *> *HoistStops,
552 DenseMap<Instruction *, bool> &Visited) {
553 assert(InsertPoint && "Null InsertPoint")((InsertPoint && "Null InsertPoint") ? static_cast<
void> (0) : __assert_fail ("InsertPoint && \"Null InsertPoint\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 553, __PRETTY_FUNCTION__))
;
554 if (auto *I = dyn_cast<Instruction>(V)) {
555 auto It = Visited.find(I);
556 if (It != Visited.end()) {
557 return It->second;
558 }
559 assert(DT.getNode(I->getParent()) && "DT must contain I's parent block")((DT.getNode(I->getParent()) && "DT must contain I's parent block"
) ? static_cast<void> (0) : __assert_fail ("DT.getNode(I->getParent()) && \"DT must contain I's parent block\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 559, __PRETTY_FUNCTION__))
;
560 assert(DT.getNode(InsertPoint->getParent()) && "DT must contain Destination")((DT.getNode(InsertPoint->getParent()) && "DT must contain Destination"
) ? static_cast<void> (0) : __assert_fail ("DT.getNode(InsertPoint->getParent()) && \"DT must contain Destination\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 560, __PRETTY_FUNCTION__))
;
561 if (Unhoistables.count(I)) {
562 // Don't hoist if they are not to be hoisted.
563 Visited[I] = false;
564 return false;
565 }
566 if (DT.dominates(I, InsertPoint)) {
567 // We are already above the insert point. Stop here.
568 if (HoistStops)
569 HoistStops->insert(I);
570 Visited[I] = true;
571 return true;
572 }
573 // We aren't not above the insert point, check if we can hoist it above the
574 // insert point.
575 if (isHoistable(I, DT)) {
576 // Check operands first.
577 DenseSet<Instruction *> OpsHoistStops;
578 bool AllOpsHoisted = true;
579 for (Value *Op : I->operands()) {
580 if (!checkHoistValue(Op, InsertPoint, DT, Unhoistables, &OpsHoistStops,
581 Visited)) {
582 AllOpsHoisted = false;
583 break;
584 }
585 }
586 if (AllOpsHoisted) {
587 CHR_DEBUG(dbgs() << "checkHoistValue " << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "checkHoistValue " << *I <<
"\n"; } } while (false)
;
588 if (HoistStops)
589 HoistStops->insert(OpsHoistStops.begin(), OpsHoistStops.end());
590 Visited[I] = true;
591 return true;
592 }
593 }
594 Visited[I] = false;
595 return false;
596 }
597 // Non-instructions are considered hoistable.
598 return true;
599}
600
601// Returns true and sets the true probability and false probability of an
602// MD_prof metadata if it's well-formed.
603static bool checkMDProf(MDNode *MD, BranchProbability &TrueProb,
604 BranchProbability &FalseProb) {
605 if (!MD) return false;
606 MDString *MDName = cast<MDString>(MD->getOperand(0));
607 if (MDName->getString() != "branch_weights" ||
608 MD->getNumOperands() != 3)
609 return false;
610 ConstantInt *TrueWeight = mdconst::extract<ConstantInt>(MD->getOperand(1));
611 ConstantInt *FalseWeight = mdconst::extract<ConstantInt>(MD->getOperand(2));
612 if (!TrueWeight || !FalseWeight)
613 return false;
614 uint64_t TrueWt = TrueWeight->getValue().getZExtValue();
615 uint64_t FalseWt = FalseWeight->getValue().getZExtValue();
616 uint64_t SumWt = TrueWt + FalseWt;
617
618 assert(SumWt >= TrueWt && SumWt >= FalseWt &&((SumWt >= TrueWt && SumWt >= FalseWt &&
"Overflow calculating branch probabilities.") ? static_cast<
void> (0) : __assert_fail ("SumWt >= TrueWt && SumWt >= FalseWt && \"Overflow calculating branch probabilities.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 619, __PRETTY_FUNCTION__))
619 "Overflow calculating branch probabilities.")((SumWt >= TrueWt && SumWt >= FalseWt &&
"Overflow calculating branch probabilities.") ? static_cast<
void> (0) : __assert_fail ("SumWt >= TrueWt && SumWt >= FalseWt && \"Overflow calculating branch probabilities.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 619, __PRETTY_FUNCTION__))
;
620
621 // Guard against 0-to-0 branch weights to avoid a division-by-zero crash.
622 if (SumWt == 0)
623 return false;
624
625 TrueProb = BranchProbability::getBranchProbability(TrueWt, SumWt);
626 FalseProb = BranchProbability::getBranchProbability(FalseWt, SumWt);
627 return true;
628}
629
630static BranchProbability getCHRBiasThreshold() {
631 return BranchProbability::getBranchProbability(
632 static_cast<uint64_t>(CHRBiasThreshold * 1000000), 1000000);
633}
634
635// A helper for CheckBiasedBranch and CheckBiasedSelect. If TrueProb >=
636// CHRBiasThreshold, put Key into TrueSet and return true. If FalseProb >=
637// CHRBiasThreshold, put Key into FalseSet and return true. Otherwise, return
638// false.
639template <typename K, typename S, typename M>
640static bool checkBias(K *Key, BranchProbability TrueProb,
641 BranchProbability FalseProb, S &TrueSet, S &FalseSet,
642 M &BiasMap) {
643 BranchProbability Threshold = getCHRBiasThreshold();
644 if (TrueProb >= Threshold) {
645 TrueSet.insert(Key);
646 BiasMap[Key] = TrueProb;
647 return true;
648 } else if (FalseProb >= Threshold) {
649 FalseSet.insert(Key);
650 BiasMap[Key] = FalseProb;
651 return true;
652 }
653 return false;
654}
655
656// Returns true and insert a region into the right biased set and the map if the
657// branch of the region is biased.
658static bool checkBiasedBranch(BranchInst *BI, Region *R,
659 DenseSet<Region *> &TrueBiasedRegionsGlobal,
660 DenseSet<Region *> &FalseBiasedRegionsGlobal,
661 DenseMap<Region *, BranchProbability> &BranchBiasMap) {
662 if (!BI->isConditional())
663 return false;
664 BranchProbability ThenProb, ElseProb;
665 if (!checkMDProf(BI->getMetadata(LLVMContext::MD_prof),
666 ThenProb, ElseProb))
667 return false;
668 BasicBlock *IfThen = BI->getSuccessor(0);
669 BasicBlock *IfElse = BI->getSuccessor(1);
670 assert((IfThen == R->getExit() || IfElse == R->getExit()) &&(((IfThen == R->getExit() || IfElse == R->getExit()) &&
IfThen != IfElse && "Invariant from findScopes") ? static_cast
<void> (0) : __assert_fail ("(IfThen == R->getExit() || IfElse == R->getExit()) && IfThen != IfElse && \"Invariant from findScopes\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 672, __PRETTY_FUNCTION__))
671 IfThen != IfElse &&(((IfThen == R->getExit() || IfElse == R->getExit()) &&
IfThen != IfElse && "Invariant from findScopes") ? static_cast
<void> (0) : __assert_fail ("(IfThen == R->getExit() || IfElse == R->getExit()) && IfThen != IfElse && \"Invariant from findScopes\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 672, __PRETTY_FUNCTION__))
672 "Invariant from findScopes")(((IfThen == R->getExit() || IfElse == R->getExit()) &&
IfThen != IfElse && "Invariant from findScopes") ? static_cast
<void> (0) : __assert_fail ("(IfThen == R->getExit() || IfElse == R->getExit()) && IfThen != IfElse && \"Invariant from findScopes\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 672, __PRETTY_FUNCTION__))
;
673 if (IfThen == R->getExit()) {
674 // Swap them so that IfThen/ThenProb means going into the conditional code
675 // and IfElse/ElseProb means skipping it.
676 std::swap(IfThen, IfElse);
677 std::swap(ThenProb, ElseProb);
678 }
679 CHR_DEBUG(dbgs() << "BI " << *BI << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "BI " << *BI << " "; }
} while (false)
;
680 CHR_DEBUG(dbgs() << "ThenProb " << ThenProb << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "ThenProb " << ThenProb <<
" "; } } while (false)
;
681 CHR_DEBUG(dbgs() << "ElseProb " << ElseProb << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "ElseProb " << ElseProb <<
"\n"; } } while (false)
;
682 return checkBias(R, ThenProb, ElseProb,
683 TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,
684 BranchBiasMap);
685}
686
687// Returns true and insert a select into the right biased set and the map if the
688// select is biased.
689static bool checkBiasedSelect(
690 SelectInst *SI, Region *R,
691 DenseSet<SelectInst *> &TrueBiasedSelectsGlobal,
692 DenseSet<SelectInst *> &FalseBiasedSelectsGlobal,
693 DenseMap<SelectInst *, BranchProbability> &SelectBiasMap) {
694 BranchProbability TrueProb, FalseProb;
695 if (!checkMDProf(SI->getMetadata(LLVMContext::MD_prof),
696 TrueProb, FalseProb))
697 return false;
698 CHR_DEBUG(dbgs() << "SI " << *SI << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "SI " << *SI << " "; }
} while (false)
;
699 CHR_DEBUG(dbgs() << "TrueProb " << TrueProb << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "TrueProb " << TrueProb <<
" "; } } while (false)
;
700 CHR_DEBUG(dbgs() << "FalseProb " << FalseProb << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "FalseProb " << FalseProb <<
"\n"; } } while (false)
;
701 return checkBias(SI, TrueProb, FalseProb,
702 TrueBiasedSelectsGlobal, FalseBiasedSelectsGlobal,
703 SelectBiasMap);
704}
705
706// Returns the instruction at which to hoist the dependent condition values and
707// insert the CHR branch for a region. This is the terminator branch in the
708// entry block or the first select in the entry block, if any.
709static Instruction* getBranchInsertPoint(RegInfo &RI) {
710 Region *R = RI.R;
711 BasicBlock *EntryBB = R->getEntry();
712 // The hoist point is by default the terminator of the entry block, which is
713 // the same as the branch instruction if RI.HasBranch is true.
714 Instruction *HoistPoint = EntryBB->getTerminator();
715 for (SelectInst *SI : RI.Selects) {
716 if (SI->getParent() == EntryBB) {
717 // Pick the first select in Selects in the entry block. Note Selects is
718 // sorted in the instruction order within a block (asserted below).
719 HoistPoint = SI;
720 break;
721 }
722 }
723 assert(HoistPoint && "Null HoistPoint")((HoistPoint && "Null HoistPoint") ? static_cast<void
> (0) : __assert_fail ("HoistPoint && \"Null HoistPoint\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 723, __PRETTY_FUNCTION__))
;
724#ifndef NDEBUG
725 // Check that HoistPoint is the first one in Selects in the entry block,
726 // if any.
727 DenseSet<Instruction *> EntryBlockSelectSet;
728 for (SelectInst *SI : RI.Selects) {
729 if (SI->getParent() == EntryBB) {
730 EntryBlockSelectSet.insert(SI);
731 }
732 }
733 for (Instruction &I : *EntryBB) {
734 if (EntryBlockSelectSet.contains(&I)) {
735 assert(&I == HoistPoint &&((&I == HoistPoint && "HoistPoint must be the first one in Selects"
) ? static_cast<void> (0) : __assert_fail ("&I == HoistPoint && \"HoistPoint must be the first one in Selects\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 736, __PRETTY_FUNCTION__))
736 "HoistPoint must be the first one in Selects")((&I == HoistPoint && "HoistPoint must be the first one in Selects"
) ? static_cast<void> (0) : __assert_fail ("&I == HoistPoint && \"HoistPoint must be the first one in Selects\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 736, __PRETTY_FUNCTION__))
;
737 break;
738 }
739 }
740#endif
741 return HoistPoint;
742}
743
744// Find a CHR scope in the given region.
745CHRScope * CHR::findScope(Region *R) {
746 CHRScope *Result = nullptr;
747 BasicBlock *Entry = R->getEntry();
748 BasicBlock *Exit = R->getExit(); // null if top level.
749 assert(Entry && "Entry must not be null")((Entry && "Entry must not be null") ? static_cast<
void> (0) : __assert_fail ("Entry && \"Entry must not be null\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 749, __PRETTY_FUNCTION__))
;
750 assert((Exit == nullptr) == (R->isTopLevelRegion()) &&(((Exit == nullptr) == (R->isTopLevelRegion()) && "Only top level region has a null exit"
) ? static_cast<void> (0) : __assert_fail ("(Exit == nullptr) == (R->isTopLevelRegion()) && \"Only top level region has a null exit\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 751, __PRETTY_FUNCTION__))
751 "Only top level region has a null exit")(((Exit == nullptr) == (R->isTopLevelRegion()) && "Only top level region has a null exit"
) ? static_cast<void> (0) : __assert_fail ("(Exit == nullptr) == (R->isTopLevelRegion()) && \"Only top level region has a null exit\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 751, __PRETTY_FUNCTION__))
;
752 if (Entry)
753 CHR_DEBUG(dbgs() << "Entry " << Entry->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Entry " << Entry->getName
() << "\n"; } } while (false)
;
754 else
755 CHR_DEBUG(dbgs() << "Entry null\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Entry null\n"; } } while (false)
;
756 if (Exit)
757 CHR_DEBUG(dbgs() << "Exit " << Exit->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Exit " << Exit->getName(
) << "\n"; } } while (false)
;
758 else
759 CHR_DEBUG(dbgs() << "Exit null\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Exit null\n"; } } while (false)
;
760 // Exclude cases where Entry is part of a subregion (hence it doesn't belong
761 // to this region).
762 bool EntryInSubregion = RI.getRegionFor(Entry) != R;
763 if (EntryInSubregion)
764 return nullptr;
765 // Exclude loops
766 for (BasicBlock *Pred : predecessors(Entry))
767 if (R->contains(Pred))
768 return nullptr;
769 if (Exit) {
770 // Try to find an if-then block (check if R is an if-then).
771 // if (cond) {
772 // ...
773 // }
774 auto *BI = dyn_cast<BranchInst>(Entry->getTerminator());
775 if (BI)
776 CHR_DEBUG(dbgs() << "BI.isConditional " << BI->isConditional() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "BI.isConditional " << BI->
isConditional() << "\n"; } } while (false)
;
777 else
778 CHR_DEBUG(dbgs() << "BI null\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "BI null\n"; } } while (false)
;
779 if (BI && BI->isConditional()) {
780 BasicBlock *S0 = BI->getSuccessor(0);
781 BasicBlock *S1 = BI->getSuccessor(1);
782 CHR_DEBUG(dbgs() << "S0 " << S0->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "S0 " << S0->getName() <<
"\n"; } } while (false)
;
783 CHR_DEBUG(dbgs() << "S1 " << S1->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "S1 " << S1->getName() <<
"\n"; } } while (false)
;
784 if (S0 != S1 && (S0 == Exit || S1 == Exit)) {
785 RegInfo RI(R);
786 RI.HasBranch = checkBiasedBranch(
787 BI, R, TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,
788 BranchBiasMap);
789 Result = new CHRScope(RI);
790 Scopes.insert(Result);
791 CHR_DEBUG(dbgs() << "Found a region with a branch\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Found a region with a branch\n"; }
} while (false)
;
792 ++Stats.NumBranches;
793 if (!RI.HasBranch) {
794 ORE.emit([&]() {
795 return OptimizationRemarkMissed(DEBUG_TYPE"chr", "BranchNotBiased", BI)
796 << "Branch not biased";
797 });
798 }
799 }
800 }
801 }
802 {
803 // Try to look for selects in the direct child blocks (as opposed to in
804 // subregions) of R.
805 // ...
806 // if (..) { // Some subregion
807 // ...
808 // }
809 // if (..) { // Some subregion
810 // ...
811 // }
812 // ...
813 // a = cond ? b : c;
814 // ...
815 SmallVector<SelectInst *, 8> Selects;
816 for (RegionNode *E : R->elements()) {
817 if (E->isSubRegion())
818 continue;
819 // This returns the basic block of E if E is a direct child of R (not a
820 // subregion.)
821 BasicBlock *BB = E->getEntry();
822 // Need to push in the order to make it easier to find the first Select
823 // later.
824 for (Instruction &I : *BB) {
825 if (auto *SI = dyn_cast<SelectInst>(&I)) {
826 Selects.push_back(SI);
827 ++Stats.NumBranches;
828 }
829 }
830 }
831 if (Selects.size() > 0) {
832 auto AddSelects = [&](RegInfo &RI) {
833 for (auto *SI : Selects)
834 if (checkBiasedSelect(SI, RI.R,
835 TrueBiasedSelectsGlobal,
836 FalseBiasedSelectsGlobal,
837 SelectBiasMap))
838 RI.Selects.push_back(SI);
839 else
840 ORE.emit([&]() {
841 return OptimizationRemarkMissed(DEBUG_TYPE"chr", "SelectNotBiased", SI)
842 << "Select not biased";
843 });
844 };
845 if (!Result) {
846 CHR_DEBUG(dbgs() << "Found a select-only region\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Found a select-only region\n"; } }
while (false)
;
847 RegInfo RI(R);
848 AddSelects(RI);
849 Result = new CHRScope(RI);
850 Scopes.insert(Result);
851 } else {
852 CHR_DEBUG(dbgs() << "Found select(s) in a region with a branch\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Found select(s) in a region with a branch\n"
; } } while (false)
;
853 AddSelects(Result->RegInfos[0]);
854 }
855 }
856 }
857
858 if (Result) {
859 checkScopeHoistable(Result);
860 }
861 return Result;
862}
863
864// Check that any of the branch and the selects in the region could be
865// hoisted above the the CHR branch insert point (the most dominating of
866// them, either the branch (at the end of the first block) or the first
867// select in the first block). If the branch can't be hoisted, drop the
868// selects in the first blocks.
869//
870// For example, for the following scope/region with selects, we want to insert
871// the merged branch right before the first select in the first/entry block by
872// hoisting c1, c2, c3, and c4.
873//
874// // Branch insert point here.
875// a = c1 ? b : c; // Select 1
876// d = c2 ? e : f; // Select 2
877// if (c3) { // Branch
878// ...
879// c4 = foo() // A call.
880// g = c4 ? h : i; // Select 3
881// }
882//
883// But suppose we can't hoist c4 because it's dependent on the preceding
884// call. Then, we drop Select 3. Furthermore, if we can't hoist c2, we also drop
885// Select 2. If we can't hoist c3, we drop Selects 1 & 2.
886void CHR::checkScopeHoistable(CHRScope *Scope) {
887 RegInfo &RI = Scope->RegInfos[0];
888 Region *R = RI.R;
889 BasicBlock *EntryBB = R->getEntry();
890 auto *Branch = RI.HasBranch ?
1
Assuming field 'HasBranch' is false
2
'?' condition is false
891 cast<BranchInst>(EntryBB->getTerminator()) : nullptr;
892 SmallVector<SelectInst *, 8> &Selects = RI.Selects;
893 if (RI.HasBranch
2.1
Field 'HasBranch' is false
2.1
Field 'HasBranch' is false
|| !Selects.empty()) {
3
Calling 'SmallVectorBase::empty'
6
Returning from 'SmallVectorBase::empty'
7
Taking true branch
894 Instruction *InsertPoint = getBranchInsertPoint(RI);
895 CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "InsertPoint " << *InsertPoint
<< "\n"; } } while (false)
;
8
Assuming 'DebugFlag' is false
9
Loop condition is false. Exiting loop
896 // Avoid a data dependence from a select or a branch to a(nother)
897 // select. Note no instruction can't data-depend on a branch (a branch
898 // instruction doesn't produce a value).
899 DenseSet<Instruction *> Unhoistables;
900 // Initialize Unhoistables with the selects.
901 for (SelectInst *SI : Selects) {
10
Assuming '__begin2' is equal to '__end2'
902 Unhoistables.insert(SI);
903 }
904 // Remove Selects that can't be hoisted.
905 for (auto it = Selects.begin(); it != Selects.end(); ) {
11
Assuming the condition is false
12
Loop condition is false. Execution continues on line 929
906 SelectInst *SI = *it;
907 if (SI == InsertPoint) {
908 ++it;
909 continue;
910 }
911 DenseMap<Instruction *, bool> Visited;
912 bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint,
913 DT, Unhoistables, nullptr, Visited);
914 if (!IsHoistable) {
915 CHR_DEBUG(dbgs() << "Dropping select " << *SI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Dropping select " << *SI <<
"\n"; } } while (false)
;
916 ORE.emit([&]() {
917 return OptimizationRemarkMissed(DEBUG_TYPE"chr",
918 "DropUnhoistableSelect", SI)
919 << "Dropped unhoistable select";
920 });
921 it = Selects.erase(it);
922 // Since we are dropping the select here, we also drop it from
923 // Unhoistables.
924 Unhoistables.erase(SI);
925 } else
926 ++it;
927 }
928 // Update InsertPoint after potentially removing selects.
929 InsertPoint = getBranchInsertPoint(RI);
13
Value assigned to 'InsertPoint'
930 CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "InsertPoint " << *InsertPoint
<< "\n"; } } while (false)
;
14
Assuming 'DebugFlag' is true
15
Assuming the condition is false
16
Taking false branch
17
Loop condition is false. Exiting loop
931 if (RI.HasBranch && InsertPoint != Branch) {
18
Assuming field 'HasBranch' is true
19
Assuming 'InsertPoint' is equal to 'Branch'
20
Taking false branch
932 DenseMap<Instruction *, bool> Visited;
933 bool IsHoistable = checkHoistValue(Branch->getCondition(), InsertPoint,
934 DT, Unhoistables, nullptr, Visited);
935 if (!IsHoistable) {
936 // If the branch isn't hoistable, drop the selects in the entry
937 // block, preferring the branch, which makes the branch the hoist
938 // point.
939 assert(InsertPoint != Branch && "Branch must not be the hoist point")((InsertPoint != Branch && "Branch must not be the hoist point"
) ? static_cast<void> (0) : __assert_fail ("InsertPoint != Branch && \"Branch must not be the hoist point\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 939, __PRETTY_FUNCTION__))
;
940 CHR_DEBUG(dbgs() << "Dropping selects in entry block \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Dropping selects in entry block \n"
; } } while (false)
;
941 CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { for (SelectInst *SI : Selects) { dbgs() << "SI "
<< *SI << "\n"; }; } } while (false)
942 for (SelectInst *SI : Selects) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { for (SelectInst *SI : Selects) { dbgs() << "SI "
<< *SI << "\n"; }; } } while (false)
943 dbgs() << "SI " << *SI << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { for (SelectInst *SI : Selects) { dbgs() << "SI "
<< *SI << "\n"; }; } } while (false)
944 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { for (SelectInst *SI : Selects) { dbgs() << "SI "
<< *SI << "\n"; }; } } while (false)
;
945 for (SelectInst *SI : Selects) {
946 ORE.emit([&]() {
947 return OptimizationRemarkMissed(DEBUG_TYPE"chr",
948 "DropSelectUnhoistableBranch", SI)
949 << "Dropped select due to unhoistable branch";
950 });
951 }
952 llvm::erase_if(Selects, [EntryBB](SelectInst *SI) {
953 return SI->getParent() == EntryBB;
954 });
955 Unhoistables.clear();
956 InsertPoint = Branch;
957 }
958 }
959 CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "InsertPoint " << *InsertPoint
<< "\n"; } } while (false)
;
21
Assuming 'DebugFlag' is true
22
Assuming the condition is true
23
Taking true branch
24
Forming reference to null pointer
960#ifndef NDEBUG
961 if (RI.HasBranch) {
962 assert(!DT.dominates(Branch, InsertPoint) &&((!DT.dominates(Branch, InsertPoint) && "Branch can't be already above the hoist point"
) ? static_cast<void> (0) : __assert_fail ("!DT.dominates(Branch, InsertPoint) && \"Branch can't be already above the hoist point\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 963, __PRETTY_FUNCTION__))
963 "Branch can't be already above the hoist point")((!DT.dominates(Branch, InsertPoint) && "Branch can't be already above the hoist point"
) ? static_cast<void> (0) : __assert_fail ("!DT.dominates(Branch, InsertPoint) && \"Branch can't be already above the hoist point\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 963, __PRETTY_FUNCTION__))
;
964 DenseMap<Instruction *, bool> Visited;
965 assert(checkHoistValue(Branch->getCondition(), InsertPoint,((checkHoistValue(Branch->getCondition(), InsertPoint, DT,
Unhoistables, nullptr, Visited) && "checkHoistValue for branch"
) ? static_cast<void> (0) : __assert_fail ("checkHoistValue(Branch->getCondition(), InsertPoint, DT, Unhoistables, nullptr, Visited) && \"checkHoistValue for branch\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 967, __PRETTY_FUNCTION__))
966 DT, Unhoistables, nullptr, Visited) &&((checkHoistValue(Branch->getCondition(), InsertPoint, DT,
Unhoistables, nullptr, Visited) && "checkHoistValue for branch"
) ? static_cast<void> (0) : __assert_fail ("checkHoistValue(Branch->getCondition(), InsertPoint, DT, Unhoistables, nullptr, Visited) && \"checkHoistValue for branch\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 967, __PRETTY_FUNCTION__))
967 "checkHoistValue for branch")((checkHoistValue(Branch->getCondition(), InsertPoint, DT,
Unhoistables, nullptr, Visited) && "checkHoistValue for branch"
) ? static_cast<void> (0) : __assert_fail ("checkHoistValue(Branch->getCondition(), InsertPoint, DT, Unhoistables, nullptr, Visited) && \"checkHoistValue for branch\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 967, __PRETTY_FUNCTION__))
;
968 }
969 for (auto *SI : Selects) {
970 assert(!DT.dominates(SI, InsertPoint) &&((!DT.dominates(SI, InsertPoint) && "SI can't be already above the hoist point"
) ? static_cast<void> (0) : __assert_fail ("!DT.dominates(SI, InsertPoint) && \"SI can't be already above the hoist point\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 971, __PRETTY_FUNCTION__))
971 "SI can't be already above the hoist point")((!DT.dominates(SI, InsertPoint) && "SI can't be already above the hoist point"
) ? static_cast<void> (0) : __assert_fail ("!DT.dominates(SI, InsertPoint) && \"SI can't be already above the hoist point\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 971, __PRETTY_FUNCTION__))
;
972 DenseMap<Instruction *, bool> Visited;
973 assert(checkHoistValue(SI->getCondition(), InsertPoint, DT,((checkHoistValue(SI->getCondition(), InsertPoint, DT, Unhoistables
, nullptr, Visited) && "checkHoistValue for selects")
? static_cast<void> (0) : __assert_fail ("checkHoistValue(SI->getCondition(), InsertPoint, DT, Unhoistables, nullptr, Visited) && \"checkHoistValue for selects\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 975, __PRETTY_FUNCTION__))
974 Unhoistables, nullptr, Visited) &&((checkHoistValue(SI->getCondition(), InsertPoint, DT, Unhoistables
, nullptr, Visited) && "checkHoistValue for selects")
? static_cast<void> (0) : __assert_fail ("checkHoistValue(SI->getCondition(), InsertPoint, DT, Unhoistables, nullptr, Visited) && \"checkHoistValue for selects\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 975, __PRETTY_FUNCTION__))
975 "checkHoistValue for selects")((checkHoistValue(SI->getCondition(), InsertPoint, DT, Unhoistables
, nullptr, Visited) && "checkHoistValue for selects")
? static_cast<void> (0) : __assert_fail ("checkHoistValue(SI->getCondition(), InsertPoint, DT, Unhoistables, nullptr, Visited) && \"checkHoistValue for selects\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 975, __PRETTY_FUNCTION__))
;
976 }
977 CHR_DEBUG(dbgs() << "Result\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Result\n"; } } while (false)
;
978 if (RI.HasBranch) {
979 CHR_DEBUG(dbgs() << "BI " << *Branch << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "BI " << *Branch << "\n"
; } } while (false)
;
980 }
981 for (auto *SI : Selects) {
982 CHR_DEBUG(dbgs() << "SI " << *SI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "SI " << *SI << "\n"; }
} while (false)
;
983 }
984#endif
985 }
986}
987
988// Traverse the region tree, find all nested scopes and merge them if possible.
989CHRScope * CHR::findScopes(Region *R, Region *NextRegion, Region *ParentRegion,
990 SmallVectorImpl<CHRScope *> &Scopes) {
991 CHR_DEBUG(dbgs() << "findScopes " << R->getNameStr() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "findScopes " << R->getNameStr
() << "\n"; } } while (false)
;
992 CHRScope *Result = findScope(R);
993 // Visit subscopes.
994 CHRScope *ConsecutiveSubscope = nullptr;
995 SmallVector<CHRScope *, 8> Subscopes;
996 for (auto It = R->begin(); It != R->end(); ++It) {
997 const std::unique_ptr<Region> &SubR = *It;
998 auto NextIt = std::next(It);
999 Region *NextSubR = NextIt != R->end() ? NextIt->get() : nullptr;
1000 CHR_DEBUG(dbgs() << "Looking at subregion " << SubR.get()->getNameStr()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Looking at subregion " << SubR
.get()->getNameStr() << "\n"; } } while (false)
1001 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Looking at subregion " << SubR
.get()->getNameStr() << "\n"; } } while (false)
;
1002 CHRScope *SubCHRScope = findScopes(SubR.get(), NextSubR, R, Scopes);
1003 if (SubCHRScope) {
1004 CHR_DEBUG(dbgs() << "Subregion Scope " << *SubCHRScope << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Subregion Scope " << *SubCHRScope
<< "\n"; } } while (false)
;
1005 } else {
1006 CHR_DEBUG(dbgs() << "Subregion Scope null\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Subregion Scope null\n"; } } while
(false)
;
1007 }
1008 if (SubCHRScope) {
1009 if (!ConsecutiveSubscope)
1010 ConsecutiveSubscope = SubCHRScope;
1011 else if (!ConsecutiveSubscope->appendable(SubCHRScope)) {
1012 Subscopes.push_back(ConsecutiveSubscope);
1013 ConsecutiveSubscope = SubCHRScope;
1014 } else
1015 ConsecutiveSubscope->append(SubCHRScope);
1016 } else {
1017 if (ConsecutiveSubscope) {
1018 Subscopes.push_back(ConsecutiveSubscope);
1019 }
1020 ConsecutiveSubscope = nullptr;
1021 }
1022 }
1023 if (ConsecutiveSubscope) {
1024 Subscopes.push_back(ConsecutiveSubscope);
1025 }
1026 for (CHRScope *Sub : Subscopes) {
1027 if (Result) {
1028 // Combine it with the parent.
1029 Result->addSub(Sub);
1030 } else {
1031 // Push Subscopes as they won't be combined with the parent.
1032 Scopes.push_back(Sub);
1033 }
1034 }
1035 return Result;
1036}
1037
1038static DenseSet<Value *> getCHRConditionValuesForRegion(RegInfo &RI) {
1039 DenseSet<Value *> ConditionValues;
1040 if (RI.HasBranch) {
1041 auto *BI = cast<BranchInst>(RI.R->getEntry()->getTerminator());
1042 ConditionValues.insert(BI->getCondition());
1043 }
1044 for (SelectInst *SI : RI.Selects) {
1045 ConditionValues.insert(SI->getCondition());
1046 }
1047 return ConditionValues;
1048}
1049
1050
1051// Determine whether to split a scope depending on the sets of the branch
1052// condition values of the previous region and the current region. We split
1053// (return true) it if 1) the condition values of the inner/lower scope can't be
1054// hoisted up to the outer/upper scope, or 2) the two sets of the condition
1055// values have an empty intersection (because the combined branch conditions
1056// won't probably lead to a simpler combined condition).
1057static bool shouldSplit(Instruction *InsertPoint,
1058 DenseSet<Value *> &PrevConditionValues,
1059 DenseSet<Value *> &ConditionValues,
1060 DominatorTree &DT,
1061 DenseSet<Instruction *> &Unhoistables) {
1062 assert(InsertPoint && "Null InsertPoint")((InsertPoint && "Null InsertPoint") ? static_cast<
void> (0) : __assert_fail ("InsertPoint && \"Null InsertPoint\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1062, __PRETTY_FUNCTION__))
;
1063 CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "shouldSplit " << *InsertPoint
<< " PrevConditionValues "; for (Value *V : PrevConditionValues
) { dbgs() << *V << ", "; } dbgs() << " ConditionValues "
; for (Value *V : ConditionValues) { dbgs() << *V <<
", "; } dbgs() << "\n"; } } while (false)
1064 dbgs() << "shouldSplit " << *InsertPoint << " PrevConditionValues ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "shouldSplit " << *InsertPoint
<< " PrevConditionValues "; for (Value *V : PrevConditionValues
) { dbgs() << *V << ", "; } dbgs() << " ConditionValues "
; for (Value *V : ConditionValues) { dbgs() << *V <<
", "; } dbgs() << "\n"; } } while (false)
1065 for (Value *V : PrevConditionValues) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "shouldSplit " << *InsertPoint
<< " PrevConditionValues "; for (Value *V : PrevConditionValues
) { dbgs() << *V << ", "; } dbgs() << " ConditionValues "
; for (Value *V : ConditionValues) { dbgs() << *V <<
", "; } dbgs() << "\n"; } } while (false)
1066 dbgs() << *V << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "shouldSplit " << *InsertPoint
<< " PrevConditionValues "; for (Value *V : PrevConditionValues
) { dbgs() << *V << ", "; } dbgs() << " ConditionValues "
; for (Value *V : ConditionValues) { dbgs() << *V <<
", "; } dbgs() << "\n"; } } while (false)
1067 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "shouldSplit " << *InsertPoint
<< " PrevConditionValues "; for (Value *V : PrevConditionValues
) { dbgs() << *V << ", "; } dbgs() << " ConditionValues "
; for (Value *V : ConditionValues) { dbgs() << *V <<
", "; } dbgs() << "\n"; } } while (false)
1068 dbgs() << " ConditionValues ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "shouldSplit " << *InsertPoint
<< " PrevConditionValues "; for (Value *V : PrevConditionValues
) { dbgs() << *V << ", "; } dbgs() << " ConditionValues "
; for (Value *V : ConditionValues) { dbgs() << *V <<
", "; } dbgs() << "\n"; } } while (false)
1069 for (Value *V : ConditionValues) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "shouldSplit " << *InsertPoint
<< " PrevConditionValues "; for (Value *V : PrevConditionValues
) { dbgs() << *V << ", "; } dbgs() << " ConditionValues "
; for (Value *V : ConditionValues) { dbgs() << *V <<
", "; } dbgs() << "\n"; } } while (false)
1070 dbgs() << *V << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "shouldSplit " << *InsertPoint
<< " PrevConditionValues "; for (Value *V : PrevConditionValues
) { dbgs() << *V << ", "; } dbgs() << " ConditionValues "
; for (Value *V : ConditionValues) { dbgs() << *V <<
", "; } dbgs() << "\n"; } } while (false)
1071 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "shouldSplit " << *InsertPoint
<< " PrevConditionValues "; for (Value *V : PrevConditionValues
) { dbgs() << *V << ", "; } dbgs() << " ConditionValues "
; for (Value *V : ConditionValues) { dbgs() << *V <<
", "; } dbgs() << "\n"; } } while (false)
1072 dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "shouldSplit " << *InsertPoint
<< " PrevConditionValues "; for (Value *V : PrevConditionValues
) { dbgs() << *V << ", "; } dbgs() << " ConditionValues "
; for (Value *V : ConditionValues) { dbgs() << *V <<
", "; } dbgs() << "\n"; } } while (false)
;
1073 // If any of Bases isn't hoistable to the hoist point, split.
1074 for (Value *V : ConditionValues) {
1075 DenseMap<Instruction *, bool> Visited;
1076 if (!checkHoistValue(V, InsertPoint, DT, Unhoistables, nullptr, Visited)) {
1077 CHR_DEBUG(dbgs() << "Split. checkHoistValue false " << *V << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Split. checkHoistValue false " <<
*V << "\n"; } } while (false)
;
1078 return true; // Not hoistable, split.
1079 }
1080 }
1081 // If PrevConditionValues or ConditionValues is empty, don't split to avoid
1082 // unnecessary splits at scopes with no branch/selects. If
1083 // PrevConditionValues and ConditionValues don't intersect at all, split.
1084 if (!PrevConditionValues.empty() && !ConditionValues.empty()) {
1085 // Use std::set as DenseSet doesn't work with set_intersection.
1086 std::set<Value *> PrevBases, Bases;
1087 DenseMap<Value *, std::set<Value *>> Visited;
1088 for (Value *V : PrevConditionValues) {
1089 const std::set<Value *> &BaseValues = getBaseValues(V, DT, Visited);
1090 PrevBases.insert(BaseValues.begin(), BaseValues.end());
1091 }
1092 for (Value *V : ConditionValues) {
1093 const std::set<Value *> &BaseValues = getBaseValues(V, DT, Visited);
1094 Bases.insert(BaseValues.begin(), BaseValues.end());
1095 }
1096 CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "PrevBases "; for (Value *V : PrevBases
) { dbgs() << *V << ", "; } dbgs() << " Bases "
; for (Value *V : Bases) { dbgs() << *V << ", "; }
dbgs() << "\n"; } } while (false)
1097 dbgs() << "PrevBases ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "PrevBases "; for (Value *V : PrevBases
) { dbgs() << *V << ", "; } dbgs() << " Bases "
; for (Value *V : Bases) { dbgs() << *V << ", "; }
dbgs() << "\n"; } } while (false)
1098 for (Value *V : PrevBases) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "PrevBases "; for (Value *V : PrevBases
) { dbgs() << *V << ", "; } dbgs() << " Bases "
; for (Value *V : Bases) { dbgs() << *V << ", "; }
dbgs() << "\n"; } } while (false)
1099 dbgs() << *V << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "PrevBases "; for (Value *V : PrevBases
) { dbgs() << *V << ", "; } dbgs() << " Bases "
; for (Value *V : Bases) { dbgs() << *V << ", "; }
dbgs() << "\n"; } } while (false)
1100 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "PrevBases "; for (Value *V : PrevBases
) { dbgs() << *V << ", "; } dbgs() << " Bases "
; for (Value *V : Bases) { dbgs() << *V << ", "; }
dbgs() << "\n"; } } while (false)
1101 dbgs() << " Bases ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "PrevBases "; for (Value *V : PrevBases
) { dbgs() << *V << ", "; } dbgs() << " Bases "
; for (Value *V : Bases) { dbgs() << *V << ", "; }
dbgs() << "\n"; } } while (false)
1102 for (Value *V : Bases) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "PrevBases "; for (Value *V : PrevBases
) { dbgs() << *V << ", "; } dbgs() << " Bases "
; for (Value *V : Bases) { dbgs() << *V << ", "; }
dbgs() << "\n"; } } while (false)
1103 dbgs() << *V << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "PrevBases "; for (Value *V : PrevBases
) { dbgs() << *V << ", "; } dbgs() << " Bases "
; for (Value *V : Bases) { dbgs() << *V << ", "; }
dbgs() << "\n"; } } while (false)
1104 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "PrevBases "; for (Value *V : PrevBases
) { dbgs() << *V << ", "; } dbgs() << " Bases "
; for (Value *V : Bases) { dbgs() << *V << ", "; }
dbgs() << "\n"; } } while (false)
1105 dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "PrevBases "; for (Value *V : PrevBases
) { dbgs() << *V << ", "; } dbgs() << " Bases "
; for (Value *V : Bases) { dbgs() << *V << ", "; }
dbgs() << "\n"; } } while (false)
;
1106 std::vector<Value *> Intersection;
1107 std::set_intersection(PrevBases.begin(), PrevBases.end(), Bases.begin(),
1108 Bases.end(), std::back_inserter(Intersection));
1109 if (Intersection.empty()) {
1110 // Empty intersection, split.
1111 CHR_DEBUG(dbgs() << "Split. Intersection empty\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Split. Intersection empty\n"; } }
while (false)
;
1112 return true;
1113 }
1114 }
1115 CHR_DEBUG(dbgs() << "No split\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "No split\n"; } } while (false)
;
1116 return false; // Don't split.
1117}
1118
1119static void getSelectsInScope(CHRScope *Scope,
1120 DenseSet<Instruction *> &Output) {
1121 for (RegInfo &RI : Scope->RegInfos)
1122 for (SelectInst *SI : RI.Selects)
1123 Output.insert(SI);
1124 for (CHRScope *Sub : Scope->Subs)
1125 getSelectsInScope(Sub, Output);
1126}
1127
1128void CHR::splitScopes(SmallVectorImpl<CHRScope *> &Input,
1129 SmallVectorImpl<CHRScope *> &Output) {
1130 for (CHRScope *Scope : Input) {
1131 assert(!Scope->BranchInsertPoint &&((!Scope->BranchInsertPoint && "BranchInsertPoint must not be set"
) ? static_cast<void> (0) : __assert_fail ("!Scope->BranchInsertPoint && \"BranchInsertPoint must not be set\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1132, __PRETTY_FUNCTION__))
1132 "BranchInsertPoint must not be set")((!Scope->BranchInsertPoint && "BranchInsertPoint must not be set"
) ? static_cast<void> (0) : __assert_fail ("!Scope->BranchInsertPoint && \"BranchInsertPoint must not be set\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1132, __PRETTY_FUNCTION__))
;
1133 DenseSet<Instruction *> Unhoistables;
1134 getSelectsInScope(Scope, Unhoistables);
1135 splitScope(Scope, nullptr, nullptr, nullptr, Output, Unhoistables);
1136 }
1137#ifndef NDEBUG
1138 for (CHRScope *Scope : Output) {
1139 assert(Scope->BranchInsertPoint && "BranchInsertPoint must be set")((Scope->BranchInsertPoint && "BranchInsertPoint must be set"
) ? static_cast<void> (0) : __assert_fail ("Scope->BranchInsertPoint && \"BranchInsertPoint must be set\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1139, __PRETTY_FUNCTION__))
;
1140 }
1141#endif
1142}
1143
1144SmallVector<CHRScope *, 8> CHR::splitScope(
1145 CHRScope *Scope,
1146 CHRScope *Outer,
1147 DenseSet<Value *> *OuterConditionValues,
1148 Instruction *OuterInsertPoint,
1149 SmallVectorImpl<CHRScope *> &Output,
1150 DenseSet<Instruction *> &Unhoistables) {
1151 if (Outer) {
1152 assert(OuterConditionValues && "Null OuterConditionValues")((OuterConditionValues && "Null OuterConditionValues"
) ? static_cast<void> (0) : __assert_fail ("OuterConditionValues && \"Null OuterConditionValues\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1152, __PRETTY_FUNCTION__))
;
1153 assert(OuterInsertPoint && "Null OuterInsertPoint")((OuterInsertPoint && "Null OuterInsertPoint") ? static_cast
<void> (0) : __assert_fail ("OuterInsertPoint && \"Null OuterInsertPoint\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1153, __PRETTY_FUNCTION__))
;
1154 }
1155 bool PrevSplitFromOuter = true;
1156 DenseSet<Value *> PrevConditionValues;
1157 Instruction *PrevInsertPoint = nullptr;
1158 SmallVector<CHRScope *, 8> Splits;
1159 SmallVector<bool, 8> SplitsSplitFromOuter;
1160 SmallVector<DenseSet<Value *>, 8> SplitsConditionValues;
1161 SmallVector<Instruction *, 8> SplitsInsertPoints;
1162 SmallVector<RegInfo, 8> RegInfos(Scope->RegInfos); // Copy
1163 for (RegInfo &RI : RegInfos) {
1164 Instruction *InsertPoint = getBranchInsertPoint(RI);
1165 DenseSet<Value *> ConditionValues = getCHRConditionValuesForRegion(RI);
1166 CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "ConditionValues "; for (Value *V :
ConditionValues) { dbgs() << *V << ", "; } dbgs(
) << "\n"; } } while (false)
1167 dbgs() << "ConditionValues ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "ConditionValues "; for (Value *V :
ConditionValues) { dbgs() << *V << ", "; } dbgs(
) << "\n"; } } while (false)
1168 for (Value *V : ConditionValues) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "ConditionValues "; for (Value *V :
ConditionValues) { dbgs() << *V << ", "; } dbgs(
) << "\n"; } } while (false)
1169 dbgs() << *V << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "ConditionValues "; for (Value *V :
ConditionValues) { dbgs() << *V << ", "; } dbgs(
) << "\n"; } } while (false)
1170 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "ConditionValues "; for (Value *V :
ConditionValues) { dbgs() << *V << ", "; } dbgs(
) << "\n"; } } while (false)
1171 dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "ConditionValues "; for (Value *V :
ConditionValues) { dbgs() << *V << ", "; } dbgs(
) << "\n"; } } while (false)
;
1172 if (RI.R == RegInfos[0].R) {
1173 // First iteration. Check to see if we should split from the outer.
1174 if (Outer) {
1175 CHR_DEBUG(dbgs() << "Outer " << *Outer << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Outer " << *Outer << "\n"
; } } while (false)
;
1176 CHR_DEBUG(dbgs() << "Should split from outer at "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Should split from outer at " <<
RI.R->getNameStr() << "\n"; } } while (false)
1177 << RI.R->getNameStr() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Should split from outer at " <<
RI.R->getNameStr() << "\n"; } } while (false)
;
1178 if (shouldSplit(OuterInsertPoint, *OuterConditionValues,
1179 ConditionValues, DT, Unhoistables)) {
1180 PrevConditionValues = ConditionValues;
1181 PrevInsertPoint = InsertPoint;
1182 ORE.emit([&]() {
1183 return OptimizationRemarkMissed(DEBUG_TYPE"chr",
1184 "SplitScopeFromOuter",
1185 RI.R->getEntry()->getTerminator())
1186 << "Split scope from outer due to unhoistable branch/select "
1187 << "and/or lack of common condition values";
1188 });
1189 } else {
1190 // Not splitting from the outer. Use the outer bases and insert
1191 // point. Union the bases.
1192 PrevSplitFromOuter = false;
1193 PrevConditionValues = *OuterConditionValues;
1194 PrevConditionValues.insert(ConditionValues.begin(),
1195 ConditionValues.end());
1196 PrevInsertPoint = OuterInsertPoint;
1197 }
1198 } else {
1199 CHR_DEBUG(dbgs() << "Outer null\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Outer null\n"; } } while (false)
;
1200 PrevConditionValues = ConditionValues;
1201 PrevInsertPoint = InsertPoint;
1202 }
1203 } else {
1204 CHR_DEBUG(dbgs() << "Should split from prev at "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Should split from prev at " <<
RI.R->getNameStr() << "\n"; } } while (false)
1205 << RI.R->getNameStr() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Should split from prev at " <<
RI.R->getNameStr() << "\n"; } } while (false)
;
1206 if (shouldSplit(PrevInsertPoint, PrevConditionValues, ConditionValues,
1207 DT, Unhoistables)) {
1208 CHRScope *Tail = Scope->split(RI.R);
1209 Scopes.insert(Tail);
1210 Splits.push_back(Scope);
1211 SplitsSplitFromOuter.push_back(PrevSplitFromOuter);
1212 SplitsConditionValues.push_back(PrevConditionValues);
1213 SplitsInsertPoints.push_back(PrevInsertPoint);
1214 Scope = Tail;
1215 PrevConditionValues = ConditionValues;
1216 PrevInsertPoint = InsertPoint;
1217 PrevSplitFromOuter = true;
1218 ORE.emit([&]() {
1219 return OptimizationRemarkMissed(DEBUG_TYPE"chr",
1220 "SplitScopeFromPrev",
1221 RI.R->getEntry()->getTerminator())
1222 << "Split scope from previous due to unhoistable branch/select "
1223 << "and/or lack of common condition values";
1224 });
1225 } else {
1226 // Not splitting. Union the bases. Keep the hoist point.
1227 PrevConditionValues.insert(ConditionValues.begin(), ConditionValues.end());
1228 }
1229 }
1230 }
1231 Splits.push_back(Scope);
1232 SplitsSplitFromOuter.push_back(PrevSplitFromOuter);
1233 SplitsConditionValues.push_back(PrevConditionValues);
1234 assert(PrevInsertPoint && "Null PrevInsertPoint")((PrevInsertPoint && "Null PrevInsertPoint") ? static_cast
<void> (0) : __assert_fail ("PrevInsertPoint && \"Null PrevInsertPoint\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1234, __PRETTY_FUNCTION__))
;
1235 SplitsInsertPoints.push_back(PrevInsertPoint);
1236 assert(Splits.size() == SplitsConditionValues.size() &&((Splits.size() == SplitsConditionValues.size() && Splits
.size() == SplitsSplitFromOuter.size() && Splits.size
() == SplitsInsertPoints.size() && "Mismatching sizes"
) ? static_cast<void> (0) : __assert_fail ("Splits.size() == SplitsConditionValues.size() && Splits.size() == SplitsSplitFromOuter.size() && Splits.size() == SplitsInsertPoints.size() && \"Mismatching sizes\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1238, __PRETTY_FUNCTION__))
1237 Splits.size() == SplitsSplitFromOuter.size() &&((Splits.size() == SplitsConditionValues.size() && Splits
.size() == SplitsSplitFromOuter.size() && Splits.size
() == SplitsInsertPoints.size() && "Mismatching sizes"
) ? static_cast<void> (0) : __assert_fail ("Splits.size() == SplitsConditionValues.size() && Splits.size() == SplitsSplitFromOuter.size() && Splits.size() == SplitsInsertPoints.size() && \"Mismatching sizes\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1238, __PRETTY_FUNCTION__))
1238 Splits.size() == SplitsInsertPoints.size() && "Mismatching sizes")((Splits.size() == SplitsConditionValues.size() && Splits
.size() == SplitsSplitFromOuter.size() && Splits.size
() == SplitsInsertPoints.size() && "Mismatching sizes"
) ? static_cast<void> (0) : __assert_fail ("Splits.size() == SplitsConditionValues.size() && Splits.size() == SplitsSplitFromOuter.size() && Splits.size() == SplitsInsertPoints.size() && \"Mismatching sizes\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1238, __PRETTY_FUNCTION__))
;
1239 for (size_t I = 0; I < Splits.size(); ++I) {
1240 CHRScope *Split = Splits[I];
1241 DenseSet<Value *> &SplitConditionValues = SplitsConditionValues[I];
1242 Instruction *SplitInsertPoint = SplitsInsertPoints[I];
1243 SmallVector<CHRScope *, 8> NewSubs;
1244 DenseSet<Instruction *> SplitUnhoistables;
1245 getSelectsInScope(Split, SplitUnhoistables);
1246 for (CHRScope *Sub : Split->Subs) {
1247 SmallVector<CHRScope *, 8> SubSplits = splitScope(
1248 Sub, Split, &SplitConditionValues, SplitInsertPoint, Output,
1249 SplitUnhoistables);
1250 llvm::append_range(NewSubs, SubSplits);
1251 }
1252 Split->Subs = NewSubs;
1253 }
1254 SmallVector<CHRScope *, 8> Result;
1255 for (size_t I = 0; I < Splits.size(); ++I) {
1256 CHRScope *Split = Splits[I];
1257 if (SplitsSplitFromOuter[I]) {
1258 // Split from the outer.
1259 Output.push_back(Split);
1260 Split->BranchInsertPoint = SplitsInsertPoints[I];
1261 CHR_DEBUG(dbgs() << "BranchInsertPoint " << *SplitsInsertPoints[I]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "BranchInsertPoint " << *SplitsInsertPoints
[I] << "\n"; } } while (false)
1262 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "BranchInsertPoint " << *SplitsInsertPoints
[I] << "\n"; } } while (false)
;
1263 } else {
1264 // Connected to the outer.
1265 Result.push_back(Split);
1266 }
1267 }
1268 if (!Outer)
1269 assert(Result.empty() &&((Result.empty() && "If no outer (top-level), must return no nested ones"
) ? static_cast<void> (0) : __assert_fail ("Result.empty() && \"If no outer (top-level), must return no nested ones\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1270, __PRETTY_FUNCTION__))
1270 "If no outer (top-level), must return no nested ones")((Result.empty() && "If no outer (top-level), must return no nested ones"
) ? static_cast<void> (0) : __assert_fail ("Result.empty() && \"If no outer (top-level), must return no nested ones\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1270, __PRETTY_FUNCTION__))
;
1271 return Result;
1272}
1273
1274void CHR::classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes) {
1275 for (CHRScope *Scope : Scopes) {
1276 assert(Scope->TrueBiasedRegions.empty() && Scope->FalseBiasedRegions.empty() && "Empty")((Scope->TrueBiasedRegions.empty() && Scope->FalseBiasedRegions
.empty() && "Empty") ? static_cast<void> (0) : __assert_fail
("Scope->TrueBiasedRegions.empty() && Scope->FalseBiasedRegions.empty() && \"Empty\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1276, __PRETTY_FUNCTION__))
;
1277 classifyBiasedScopes(Scope, Scope);
1278 CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1279 dbgs() << "classifyBiasedScopes " << *Scope << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1280 dbgs() << "TrueBiasedRegions ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1281 for (Region *R : Scope->TrueBiasedRegions) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1282 dbgs() << R->getNameStr() << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1283 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1284 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1285 dbgs() << "FalseBiasedRegions ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1286 for (Region *R : Scope->FalseBiasedRegions) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1287 dbgs() << R->getNameStr() << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1288 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1289 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1290 dbgs() << "TrueBiasedSelects ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1291 for (SelectInst *SI : Scope->TrueBiasedSelects) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1292 dbgs() << *SI << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1293 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1294 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1295 dbgs() << "FalseBiasedSelects ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1296 for (SelectInst *SI : Scope->FalseBiasedSelects) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1297 dbgs() << *SI << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1298 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
1299 dbgs() << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "classifyBiasedScopes " << *
Scope << "\n"; dbgs() << "TrueBiasedRegions "; for
(Region *R : Scope->TrueBiasedRegions) { dbgs() << R
->getNameStr() << ", "; } dbgs() << "\n"; dbgs
() << "FalseBiasedRegions "; for (Region *R : Scope->
FalseBiasedRegions) { dbgs() << R->getNameStr() <<
", "; } dbgs() << "\n"; dbgs() << "TrueBiasedSelects "
; for (SelectInst *SI : Scope->TrueBiasedSelects) { dbgs()
<< *SI << ", "; } dbgs() << "\n"; dbgs() <<
"FalseBiasedSelects "; for (SelectInst *SI : Scope->FalseBiasedSelects
) { dbgs() << *SI << ", "; } dbgs() << "\n"
;; } } while (false)
;
1300 }
1301}
1302
1303void CHR::classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope) {
1304 for (RegInfo &RI : Scope->RegInfos) {
1305 if (RI.HasBranch) {
1306 Region *R = RI.R;
1307 if (TrueBiasedRegionsGlobal.contains(R))
1308 OutermostScope->TrueBiasedRegions.insert(R);
1309 else if (FalseBiasedRegionsGlobal.contains(R))
1310 OutermostScope->FalseBiasedRegions.insert(R);
1311 else
1312 llvm_unreachable("Must be biased")::llvm::llvm_unreachable_internal("Must be biased", "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1312)
;
1313 }
1314 for (SelectInst *SI : RI.Selects) {
1315 if (TrueBiasedSelectsGlobal.contains(SI))
1316 OutermostScope->TrueBiasedSelects.insert(SI);
1317 else if (FalseBiasedSelectsGlobal.contains(SI))
1318 OutermostScope->FalseBiasedSelects.insert(SI);
1319 else
1320 llvm_unreachable("Must be biased")::llvm::llvm_unreachable_internal("Must be biased", "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1320)
;
1321 }
1322 }
1323 for (CHRScope *Sub : Scope->Subs) {
1324 classifyBiasedScopes(Sub, OutermostScope);
1325 }
1326}
1327
1328static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope) {
1329 unsigned NumBiased = Scope->TrueBiasedRegions.size() +
1330 Scope->FalseBiasedRegions.size() +
1331 Scope->TrueBiasedSelects.size() +
1332 Scope->FalseBiasedSelects.size();
1333 return NumBiased >= CHRMergeThreshold;
1334}
1335
1336void CHR::filterScopes(SmallVectorImpl<CHRScope *> &Input,
1337 SmallVectorImpl<CHRScope *> &Output) {
1338 for (CHRScope *Scope : Input) {
1339 // Filter out the ones with only one region and no subs.
1340 if (!hasAtLeastTwoBiasedBranches(Scope)) {
1341 CHR_DEBUG(dbgs() << "Filtered out by biased branches truthy-regions "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Filtered out by biased branches truthy-regions "
<< Scope->TrueBiasedRegions.size() << " falsy-regions "
<< Scope->FalseBiasedRegions.size() << " true-selects "
<< Scope->TrueBiasedSelects.size() << " false-selects "
<< Scope->FalseBiasedSelects.size() << "\n"; }
} while (false)
1342 << Scope->TrueBiasedRegions.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Filtered out by biased branches truthy-regions "
<< Scope->TrueBiasedRegions.size() << " falsy-regions "
<< Scope->FalseBiasedRegions.size() << " true-selects "
<< Scope->TrueBiasedSelects.size() << " false-selects "
<< Scope->FalseBiasedSelects.size() << "\n"; }
} while (false)
1343 << " falsy-regions " << Scope->FalseBiasedRegions.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Filtered out by biased branches truthy-regions "
<< Scope->TrueBiasedRegions.size() << " falsy-regions "
<< Scope->FalseBiasedRegions.size() << " true-selects "
<< Scope->TrueBiasedSelects.size() << " false-selects "
<< Scope->FalseBiasedSelects.size() << "\n"; }
} while (false)
1344 << " true-selects " << Scope->TrueBiasedSelects.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Filtered out by biased branches truthy-regions "
<< Scope->TrueBiasedRegions.size() << " falsy-regions "
<< Scope->FalseBiasedRegions.size() << " true-selects "
<< Scope->TrueBiasedSelects.size() << " false-selects "
<< Scope->FalseBiasedSelects.size() << "\n"; }
} while (false)
1345 << " false-selects " << Scope->FalseBiasedSelects.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Filtered out by biased branches truthy-regions "
<< Scope->TrueBiasedRegions.size() << " falsy-regions "
<< Scope->FalseBiasedRegions.size() << " true-selects "
<< Scope->TrueBiasedSelects.size() << " false-selects "
<< Scope->FalseBiasedSelects.size() << "\n"; }
} while (false)
;
1346 ORE.emit([&]() {
1347 return OptimizationRemarkMissed(
1348 DEBUG_TYPE"chr",
1349 "DropScopeWithOneBranchOrSelect",
1350 Scope->RegInfos[0].R->getEntry()->getTerminator())
1351 << "Drop scope with < "
1352 << ore::NV("CHRMergeThreshold", CHRMergeThreshold)
1353 << " biased branch(es) or select(s)";
1354 });
1355 continue;
1356 }
1357 Output.push_back(Scope);
1358 }
1359}
1360
1361void CHR::setCHRRegions(SmallVectorImpl<CHRScope *> &Input,
1362 SmallVectorImpl<CHRScope *> &Output) {
1363 for (CHRScope *Scope : Input) {
1364 assert(Scope->HoistStopMap.empty() && Scope->CHRRegions.empty() &&((Scope->HoistStopMap.empty() && Scope->CHRRegions
.empty() && "Empty") ? static_cast<void> (0) : __assert_fail
("Scope->HoistStopMap.empty() && Scope->CHRRegions.empty() && \"Empty\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1365, __PRETTY_FUNCTION__))
1365 "Empty")((Scope->HoistStopMap.empty() && Scope->CHRRegions
.empty() && "Empty") ? static_cast<void> (0) : __assert_fail
("Scope->HoistStopMap.empty() && Scope->CHRRegions.empty() && \"Empty\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1365, __PRETTY_FUNCTION__))
;
1366 setCHRRegions(Scope, Scope);
1367 Output.push_back(Scope);
1368 CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1369 dbgs() << "setCHRRegions HoistStopMap " << *Scope << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1370 for (auto pair : Scope->HoistStopMap) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1371 Region *R = pair.first;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1372 dbgs() << "Region " << R->getNameStr() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1373 for (Instruction *I : pair.second) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1374 dbgs() << "HoistStop " << *I << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1375 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1376 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1377 dbgs() << "CHRRegions" << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1378 for (RegInfo &RI : Scope->CHRRegions) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1379 dbgs() << RI.R->getNameStr() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
1380 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "setCHRRegions HoistStopMap " <<
*Scope << "\n"; for (auto pair : Scope->HoistStopMap
) { Region *R = pair.first; dbgs() << "Region " <<
R->getNameStr() << "\n"; for (Instruction *I : pair
.second) { dbgs() << "HoistStop " << *I << "\n"
; } } dbgs() << "CHRRegions" << "\n"; for (RegInfo
&RI : Scope->CHRRegions) { dbgs() << RI.R->getNameStr
() << "\n"; }; } } while (false)
;
1381 }
1382}
1383
1384void CHR::setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope) {
1385 DenseSet<Instruction *> Unhoistables;
1386 // Put the biased selects in Unhoistables because they should stay where they
1387 // are and constant-folded after CHR (in case one biased select or a branch
1388 // can depend on another biased select.)
1389 for (RegInfo &RI : Scope->RegInfos) {
1390 for (SelectInst *SI : RI.Selects) {
1391 Unhoistables.insert(SI);
1392 }
1393 }
1394 Instruction *InsertPoint = OutermostScope->BranchInsertPoint;
1395 for (RegInfo &RI : Scope->RegInfos) {
1396 Region *R = RI.R;
1397 DenseSet<Instruction *> HoistStops;
1398 bool IsHoisted = false;
1399 if (RI.HasBranch) {
1400 assert((OutermostScope->TrueBiasedRegions.contains(R) ||(((OutermostScope->TrueBiasedRegions.contains(R) || OutermostScope
->FalseBiasedRegions.contains(R)) && "Must be truthy or falsy"
) ? static_cast<void> (0) : __assert_fail ("(OutermostScope->TrueBiasedRegions.contains(R) || OutermostScope->FalseBiasedRegions.contains(R)) && \"Must be truthy or falsy\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1402, __PRETTY_FUNCTION__))
1401 OutermostScope->FalseBiasedRegions.contains(R)) &&(((OutermostScope->TrueBiasedRegions.contains(R) || OutermostScope
->FalseBiasedRegions.contains(R)) && "Must be truthy or falsy"
) ? static_cast<void> (0) : __assert_fail ("(OutermostScope->TrueBiasedRegions.contains(R) || OutermostScope->FalseBiasedRegions.contains(R)) && \"Must be truthy or falsy\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1402, __PRETTY_FUNCTION__))
1402 "Must be truthy or falsy")(((OutermostScope->TrueBiasedRegions.contains(R) || OutermostScope
->FalseBiasedRegions.contains(R)) && "Must be truthy or falsy"
) ? static_cast<void> (0) : __assert_fail ("(OutermostScope->TrueBiasedRegions.contains(R) || OutermostScope->FalseBiasedRegions.contains(R)) && \"Must be truthy or falsy\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1402, __PRETTY_FUNCTION__))
;
1403 auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1404 // Note checkHoistValue fills in HoistStops.
1405 DenseMap<Instruction *, bool> Visited;
1406 bool IsHoistable = checkHoistValue(BI->getCondition(), InsertPoint, DT,
1407 Unhoistables, &HoistStops, Visited);
1408 assert(IsHoistable && "Must be hoistable")((IsHoistable && "Must be hoistable") ? static_cast<
void> (0) : __assert_fail ("IsHoistable && \"Must be hoistable\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1408, __PRETTY_FUNCTION__))
;
1409 (void)(IsHoistable); // Unused in release build
1410 IsHoisted = true;
1411 }
1412 for (SelectInst *SI : RI.Selects) {
1413 assert((OutermostScope->TrueBiasedSelects.contains(SI) ||(((OutermostScope->TrueBiasedSelects.contains(SI) || OutermostScope
->FalseBiasedSelects.contains(SI)) && "Must be true or false biased"
) ? static_cast<void> (0) : __assert_fail ("(OutermostScope->TrueBiasedSelects.contains(SI) || OutermostScope->FalseBiasedSelects.contains(SI)) && \"Must be true or false biased\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1415, __PRETTY_FUNCTION__))
1414 OutermostScope->FalseBiasedSelects.contains(SI)) &&(((OutermostScope->TrueBiasedSelects.contains(SI) || OutermostScope
->FalseBiasedSelects.contains(SI)) && "Must be true or false biased"
) ? static_cast<void> (0) : __assert_fail ("(OutermostScope->TrueBiasedSelects.contains(SI) || OutermostScope->FalseBiasedSelects.contains(SI)) && \"Must be true or false biased\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1415, __PRETTY_FUNCTION__))
1415 "Must be true or false biased")(((OutermostScope->TrueBiasedSelects.contains(SI) || OutermostScope
->FalseBiasedSelects.contains(SI)) && "Must be true or false biased"
) ? static_cast<void> (0) : __assert_fail ("(OutermostScope->TrueBiasedSelects.contains(SI) || OutermostScope->FalseBiasedSelects.contains(SI)) && \"Must be true or false biased\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1415, __PRETTY_FUNCTION__))
;
1416 // Note checkHoistValue fills in HoistStops.
1417 DenseMap<Instruction *, bool> Visited;
1418 bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint, DT,
1419 Unhoistables, &HoistStops, Visited);
1420 assert(IsHoistable && "Must be hoistable")((IsHoistable && "Must be hoistable") ? static_cast<
void> (0) : __assert_fail ("IsHoistable && \"Must be hoistable\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1420, __PRETTY_FUNCTION__))
;
1421 (void)(IsHoistable); // Unused in release build
1422 IsHoisted = true;
1423 }
1424 if (IsHoisted) {
1425 OutermostScope->CHRRegions.push_back(RI);
1426 OutermostScope->HoistStopMap[R] = HoistStops;
1427 }
1428 }
1429 for (CHRScope *Sub : Scope->Subs)
1430 setCHRRegions(Sub, OutermostScope);
1431}
1432
1433static bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2) {
1434 return Scope1->RegInfos[0].R->getDepth() < Scope2->RegInfos[0].R->getDepth();
1435}
1436
1437void CHR::sortScopes(SmallVectorImpl<CHRScope *> &Input,
1438 SmallVectorImpl<CHRScope *> &Output) {
1439 Output.resize(Input.size());
1440 llvm::copy(Input, Output.begin());
1441 llvm::stable_sort(Output, CHRScopeSorter);
1442}
1443
1444// Return true if V is already hoisted or was hoisted (along with its operands)
1445// to the insert point.
1446static void hoistValue(Value *V, Instruction *HoistPoint, Region *R,
1447 HoistStopMapTy &HoistStopMap,
1448 DenseSet<Instruction *> &HoistedSet,
1449 DenseSet<PHINode *> &TrivialPHIs,
1450 DominatorTree &DT) {
1451 auto IT = HoistStopMap.find(R);
1452 assert(IT != HoistStopMap.end() && "Region must be in hoist stop map")((IT != HoistStopMap.end() && "Region must be in hoist stop map"
) ? static_cast<void> (0) : __assert_fail ("IT != HoistStopMap.end() && \"Region must be in hoist stop map\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1452, __PRETTY_FUNCTION__))
;
1453 DenseSet<Instruction *> &HoistStops = IT->second;
1454 if (auto *I = dyn_cast<Instruction>(V)) {
1455 if (I == HoistPoint)
1456 return;
1457 if (HoistStops.count(I))
1458 return;
1459 if (auto *PN = dyn_cast<PHINode>(I))
1460 if (TrivialPHIs.count(PN))
1461 // The trivial phi inserted by the previous CHR scope could replace a
1462 // non-phi in HoistStops. Note that since this phi is at the exit of a
1463 // previous CHR scope, which dominates this scope, it's safe to stop
1464 // hoisting there.
1465 return;
1466 if (HoistedSet.count(I))
1467 // Already hoisted, return.
1468 return;
1469 assert(isHoistableInstructionType(I) && "Unhoistable instruction type")((isHoistableInstructionType(I) && "Unhoistable instruction type"
) ? static_cast<void> (0) : __assert_fail ("isHoistableInstructionType(I) && \"Unhoistable instruction type\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1469, __PRETTY_FUNCTION__))
;
1470 assert(DT.getNode(I->getParent()) && "DT must contain I's block")((DT.getNode(I->getParent()) && "DT must contain I's block"
) ? static_cast<void> (0) : __assert_fail ("DT.getNode(I->getParent()) && \"DT must contain I's block\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1470, __PRETTY_FUNCTION__))
;
1471 assert(DT.getNode(HoistPoint->getParent()) &&((DT.getNode(HoistPoint->getParent()) && "DT must contain HoistPoint block"
) ? static_cast<void> (0) : __assert_fail ("DT.getNode(HoistPoint->getParent()) && \"DT must contain HoistPoint block\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1472, __PRETTY_FUNCTION__))
1472 "DT must contain HoistPoint block")((DT.getNode(HoistPoint->getParent()) && "DT must contain HoistPoint block"
) ? static_cast<void> (0) : __assert_fail ("DT.getNode(HoistPoint->getParent()) && \"DT must contain HoistPoint block\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1472, __PRETTY_FUNCTION__))
;
1473 if (DT.dominates(I, HoistPoint))
1474 // We are already above the hoist point. Stop here. This may be necessary
1475 // when multiple scopes would independently hoist the same
1476 // instruction. Since an outer (dominating) scope would hoist it to its
1477 // entry before an inner (dominated) scope would to its entry, the inner
1478 // scope may see the instruction already hoisted, in which case it
1479 // potentially wrong for the inner scope to hoist it and could cause bad
1480 // IR (non-dominating def), but safe to skip hoisting it instead because
1481 // it's already in a block that dominates the inner scope.
1482 return;
1483 for (Value *Op : I->operands()) {
1484 hoistValue(Op, HoistPoint, R, HoistStopMap, HoistedSet, TrivialPHIs, DT);
1485 }
1486 I->moveBefore(HoistPoint);
1487 HoistedSet.insert(I);
1488 CHR_DEBUG(dbgs() << "hoistValue " << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "hoistValue " << *I <<
"\n"; } } while (false)
;
1489 }
1490}
1491
1492// Hoist the dependent condition values of the branches and the selects in the
1493// scope to the insert point.
1494static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint,
1495 DenseSet<PHINode *> &TrivialPHIs,
1496 DominatorTree &DT) {
1497 DenseSet<Instruction *> HoistedSet;
1498 for (const RegInfo &RI : Scope->CHRRegions) {
1499 Region *R = RI.R;
1500 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1501 bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);
1502 if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1503 auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1504 hoistValue(BI->getCondition(), HoistPoint, R, Scope->HoistStopMap,
1505 HoistedSet, TrivialPHIs, DT);
1506 }
1507 for (SelectInst *SI : RI.Selects) {
1508 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1509 bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);
1510 if (!(IsTrueBiased || IsFalseBiased))
1511 continue;
1512 hoistValue(SI->getCondition(), HoistPoint, R, Scope->HoistStopMap,
1513 HoistedSet, TrivialPHIs, DT);
1514 }
1515 }
1516}
1517
1518// Negate the predicate if an ICmp if it's used only by branches or selects by
1519// swapping the operands of the branches or the selects. Returns true if success.
1520static bool negateICmpIfUsedByBranchOrSelectOnly(ICmpInst *ICmp,
1521 Instruction *ExcludedUser,
1522 CHRScope *Scope) {
1523 for (User *U : ICmp->users()) {
1524 if (U == ExcludedUser)
1525 continue;
1526 if (isa<BranchInst>(U) && cast<BranchInst>(U)->isConditional())
1527 continue;
1528 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == ICmp)
1529 continue;
1530 return false;
1531 }
1532 for (User *U : ICmp->users()) {
1533 if (U == ExcludedUser)
1534 continue;
1535 if (auto *BI = dyn_cast<BranchInst>(U)) {
1536 assert(BI->isConditional() && "Must be conditional")((BI->isConditional() && "Must be conditional") ? static_cast
<void> (0) : __assert_fail ("BI->isConditional() && \"Must be conditional\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1536, __PRETTY_FUNCTION__))
;
1537 BI->swapSuccessors();
1538 // Don't need to swap this in terms of
1539 // TrueBiasedRegions/FalseBiasedRegions because true-based/false-based
1540 // mean whehter the branch is likely go into the if-then rather than
1541 // successor0/successor1 and because we can tell which edge is the then or
1542 // the else one by comparing the destination to the region exit block.
1543 continue;
1544 }
1545 if (auto *SI = dyn_cast<SelectInst>(U)) {
1546 // Swap operands
1547 SI->swapValues();
1548 SI->swapProfMetadata();
1549 if (Scope->TrueBiasedSelects.count(SI)) {
1550 assert(Scope->FalseBiasedSelects.count(SI) == 0 &&((Scope->FalseBiasedSelects.count(SI) == 0 && "Must not be already in"
) ? static_cast<void> (0) : __assert_fail ("Scope->FalseBiasedSelects.count(SI) == 0 && \"Must not be already in\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1551, __PRETTY_FUNCTION__))
1551 "Must not be already in")((Scope->FalseBiasedSelects.count(SI) == 0 && "Must not be already in"
) ? static_cast<void> (0) : __assert_fail ("Scope->FalseBiasedSelects.count(SI) == 0 && \"Must not be already in\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1551, __PRETTY_FUNCTION__))
;
1552 Scope->FalseBiasedSelects.insert(SI);
1553 } else if (Scope->FalseBiasedSelects.count(SI)) {
1554 assert(Scope->TrueBiasedSelects.count(SI) == 0 &&((Scope->TrueBiasedSelects.count(SI) == 0 && "Must not be already in"
) ? static_cast<void> (0) : __assert_fail ("Scope->TrueBiasedSelects.count(SI) == 0 && \"Must not be already in\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1555, __PRETTY_FUNCTION__))
1555 "Must not be already in")((Scope->TrueBiasedSelects.count(SI) == 0 && "Must not be already in"
) ? static_cast<void> (0) : __assert_fail ("Scope->TrueBiasedSelects.count(SI) == 0 && \"Must not be already in\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1555, __PRETTY_FUNCTION__))
;
1556 Scope->TrueBiasedSelects.insert(SI);
1557 }
1558 continue;
1559 }
1560 llvm_unreachable("Must be a branch or a select")::llvm::llvm_unreachable_internal("Must be a branch or a select"
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1560)
;
1561 }
1562 ICmp->setPredicate(CmpInst::getInversePredicate(ICmp->getPredicate()));
1563 return true;
1564}
1565
1566// A helper for transformScopes. Insert a trivial phi at the scope exit block
1567// for a value that's defined in the scope but used outside it (meaning it's
1568// alive at the exit block).
1569static void insertTrivialPHIs(CHRScope *Scope,
1570 BasicBlock *EntryBlock, BasicBlock *ExitBlock,
1571 DenseSet<PHINode *> &TrivialPHIs) {
1572 SmallSetVector<BasicBlock *, 8> BlocksInScope;
1573 for (RegInfo &RI : Scope->RegInfos) {
1574 for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1575 // sub-Scopes.
1576 BlocksInScope.insert(BB);
1577 }
1578 }
1579 CHR_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { { dbgs() << "Inserting redundant phis\n"; for
(BasicBlock *BB : BlocksInScope) dbgs() << "BlockInScope "
<< BB->getName() << "\n"; }; } } while (false
)
1580 dbgs() << "Inserting redundant phis\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { { dbgs() << "Inserting redundant phis\n"; for
(BasicBlock *BB : BlocksInScope) dbgs() << "BlockInScope "
<< BB->getName() << "\n"; }; } } while (false
)
1581 for (BasicBlock *BB : BlocksInScope)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { { dbgs() << "Inserting redundant phis\n"; for
(BasicBlock *BB : BlocksInScope) dbgs() << "BlockInScope "
<< BB->getName() << "\n"; }; } } while (false
)
1582 dbgs() << "BlockInScope " << BB->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { { dbgs() << "Inserting redundant phis\n"; for
(BasicBlock *BB : BlocksInScope) dbgs() << "BlockInScope "
<< BB->getName() << "\n"; }; } } while (false
)
1583 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { { dbgs() << "Inserting redundant phis\n"; for
(BasicBlock *BB : BlocksInScope) dbgs() << "BlockInScope "
<< BB->getName() << "\n"; }; } } while (false
)
;
1584 for (BasicBlock *BB : BlocksInScope) {
1585 for (Instruction &I : *BB) {
1586 SmallVector<Instruction *, 8> Users;
1587 for (User *U : I.users()) {
1588 if (auto *UI = dyn_cast<Instruction>(U)) {
1589 if (BlocksInScope.count(UI->getParent()) == 0 &&
1590 // Unless there's already a phi for I at the exit block.
1591 !(isa<PHINode>(UI) && UI->getParent() == ExitBlock)) {
1592 CHR_DEBUG(dbgs() << "V " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "V " << I << "\n"; } }
while (false)
;
1593 CHR_DEBUG(dbgs() << "Used outside scope by user " << *UI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Used outside scope by user " <<
*UI << "\n"; } } while (false)
;
1594 Users.push_back(UI);
1595 } else if (UI->getParent() == EntryBlock && isa<PHINode>(UI)) {
1596 // There's a loop backedge from a block that's dominated by this
1597 // scope to the entry block.
1598 CHR_DEBUG(dbgs() << "V " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "V " << I << "\n"; } }
while (false)
;
1599 CHR_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Used at entry block (for a back edge) by a phi user "
<< *UI << "\n"; } } while (false)
1600 << "Used at entry block (for a back edge) by a phi user "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Used at entry block (for a back edge) by a phi user "
<< *UI << "\n"; } } while (false)
1601 << *UI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Used at entry block (for a back edge) by a phi user "
<< *UI << "\n"; } } while (false)
;
1602 Users.push_back(UI);
1603 }
1604 }
1605 }
1606 if (Users.size() > 0) {
1607 // Insert a trivial phi for I (phi [&I, P0], [&I, P1], ...) at
1608 // ExitBlock. Replace I with the new phi in UI unless UI is another
1609 // phi at ExitBlock.
1610 PHINode *PN = PHINode::Create(I.getType(), pred_size(ExitBlock), "",
1611 &ExitBlock->front());
1612 for (BasicBlock *Pred : predecessors(ExitBlock)) {
1613 PN->addIncoming(&I, Pred);
1614 }
1615 TrivialPHIs.insert(PN);
1616 CHR_DEBUG(dbgs() << "Insert phi " << *PN << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Insert phi " << *PN <<
"\n"; } } while (false)
;
1617 for (Instruction *UI : Users) {
1618 for (unsigned J = 0, NumOps = UI->getNumOperands(); J < NumOps; ++J) {
1619 if (UI->getOperand(J) == &I) {
1620 UI->setOperand(J, PN);
1621 }
1622 }
1623 CHR_DEBUG(dbgs() << "Updated user " << *UI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Updated user " << *UI <<
"\n"; } } while (false)
;
1624 }
1625 }
1626 }
1627 }
1628}
1629
1630// Assert that all the CHR regions of the scope have a biased branch or select.
1631static void LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__))
1632assertCHRRegionsHaveBiasedBranchOrSelect(CHRScope *Scope) {
1633#ifndef NDEBUG
1634 auto HasBiasedBranchOrSelect = [](RegInfo &RI, CHRScope *Scope) {
1635 if (Scope->TrueBiasedRegions.count(RI.R) ||
1636 Scope->FalseBiasedRegions.count(RI.R))
1637 return true;
1638 for (SelectInst *SI : RI.Selects)
1639 if (Scope->TrueBiasedSelects.count(SI) ||
1640 Scope->FalseBiasedSelects.count(SI))
1641 return true;
1642 return false;
1643 };
1644 for (RegInfo &RI : Scope->CHRRegions) {
1645 assert(HasBiasedBranchOrSelect(RI, Scope) &&((HasBiasedBranchOrSelect(RI, Scope) && "Must have biased branch or select"
) ? static_cast<void> (0) : __assert_fail ("HasBiasedBranchOrSelect(RI, Scope) && \"Must have biased branch or select\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1646, __PRETTY_FUNCTION__))
1646 "Must have biased branch or select")((HasBiasedBranchOrSelect(RI, Scope) && "Must have biased branch or select"
) ? static_cast<void> (0) : __assert_fail ("HasBiasedBranchOrSelect(RI, Scope) && \"Must have biased branch or select\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1646, __PRETTY_FUNCTION__))
;
1647 }
1648#endif
1649}
1650
1651// Assert that all the condition values of the biased branches and selects have
1652// been hoisted to the pre-entry block or outside of the scope.
1653static void LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) assertBranchOrSelectConditionHoisted(
1654 CHRScope *Scope, BasicBlock *PreEntryBlock) {
1655 CHR_DEBUG(dbgs() << "Biased regions condition values \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Biased regions condition values \n"
; } } while (false)
;
1656 for (RegInfo &RI : Scope->CHRRegions) {
1657 Region *R = RI.R;
1658 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1659 bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);
1660 if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1661 auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1662 Value *V = BI->getCondition();
1663 CHR_DEBUG(dbgs() << *V << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << *V << "\n"; } } while (false
)
;
1664 if (auto *I = dyn_cast<Instruction>(V)) {
1665 (void)(I); // Unused in release build.
1666 assert((I->getParent() == PreEntryBlock ||(((I->getParent() == PreEntryBlock || !Scope->contains(
I)) && "Must have been hoisted to PreEntryBlock or outside the scope"
) ? static_cast<void> (0) : __assert_fail ("(I->getParent() == PreEntryBlock || !Scope->contains(I)) && \"Must have been hoisted to PreEntryBlock or outside the scope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1668, __PRETTY_FUNCTION__))
1667 !Scope->contains(I)) &&(((I->getParent() == PreEntryBlock || !Scope->contains(
I)) && "Must have been hoisted to PreEntryBlock or outside the scope"
) ? static_cast<void> (0) : __assert_fail ("(I->getParent() == PreEntryBlock || !Scope->contains(I)) && \"Must have been hoisted to PreEntryBlock or outside the scope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1668, __PRETTY_FUNCTION__))
1668 "Must have been hoisted to PreEntryBlock or outside the scope")(((I->getParent() == PreEntryBlock || !Scope->contains(
I)) && "Must have been hoisted to PreEntryBlock or outside the scope"
) ? static_cast<void> (0) : __assert_fail ("(I->getParent() == PreEntryBlock || !Scope->contains(I)) && \"Must have been hoisted to PreEntryBlock or outside the scope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1668, __PRETTY_FUNCTION__))
;
1669 }
1670 }
1671 for (SelectInst *SI : RI.Selects) {
1672 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1673 bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);
1674 if (!(IsTrueBiased || IsFalseBiased))
1675 continue;
1676 Value *V = SI->getCondition();
1677 CHR_DEBUG(dbgs() << *V << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << *V << "\n"; } } while (false
)
;
1678 if (auto *I = dyn_cast<Instruction>(V)) {
1679 (void)(I); // Unused in release build.
1680 assert((I->getParent() == PreEntryBlock ||(((I->getParent() == PreEntryBlock || !Scope->contains(
I)) && "Must have been hoisted to PreEntryBlock or outside the scope"
) ? static_cast<void> (0) : __assert_fail ("(I->getParent() == PreEntryBlock || !Scope->contains(I)) && \"Must have been hoisted to PreEntryBlock or outside the scope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1682, __PRETTY_FUNCTION__))
1681 !Scope->contains(I)) &&(((I->getParent() == PreEntryBlock || !Scope->contains(
I)) && "Must have been hoisted to PreEntryBlock or outside the scope"
) ? static_cast<void> (0) : __assert_fail ("(I->getParent() == PreEntryBlock || !Scope->contains(I)) && \"Must have been hoisted to PreEntryBlock or outside the scope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1682, __PRETTY_FUNCTION__))
1682 "Must have been hoisted to PreEntryBlock or outside the scope")(((I->getParent() == PreEntryBlock || !Scope->contains(
I)) && "Must have been hoisted to PreEntryBlock or outside the scope"
) ? static_cast<void> (0) : __assert_fail ("(I->getParent() == PreEntryBlock || !Scope->contains(I)) && \"Must have been hoisted to PreEntryBlock or outside the scope\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1682, __PRETTY_FUNCTION__))
;
1683 }
1684 }
1685 }
1686}
1687
1688void CHR::transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs) {
1689 CHR_DEBUG(dbgs() << "transformScopes " << *Scope << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "transformScopes " << *Scope
<< "\n"; } } while (false)
;
1690
1691 assert(Scope->RegInfos.size() >= 1 && "Should have at least one Region")((Scope->RegInfos.size() >= 1 && "Should have at least one Region"
) ? static_cast<void> (0) : __assert_fail ("Scope->RegInfos.size() >= 1 && \"Should have at least one Region\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1691, __PRETTY_FUNCTION__))
;
1692 Region *FirstRegion = Scope->RegInfos[0].R;
1693 BasicBlock *EntryBlock = FirstRegion->getEntry();
1694 Region *LastRegion = Scope->RegInfos[Scope->RegInfos.size() - 1].R;
1695 BasicBlock *ExitBlock = LastRegion->getExit();
1696 Optional<uint64_t> ProfileCount = BFI.getBlockProfileCount(EntryBlock);
1697
1698 if (ExitBlock) {
1699 // Insert a trivial phi at the exit block (where the CHR hot path and the
1700 // cold path merges) for a value that's defined in the scope but used
1701 // outside it (meaning it's alive at the exit block). We will add the
1702 // incoming values for the CHR cold paths to it below. Without this, we'd
1703 // miss updating phi's for such values unless there happens to already be a
1704 // phi for that value there.
1705 insertTrivialPHIs(Scope, EntryBlock, ExitBlock, TrivialPHIs);
1706 }
1707
1708 // Split the entry block of the first region. The new block becomes the new
1709 // entry block of the first region. The old entry block becomes the block to
1710 // insert the CHR branch into. Note DT gets updated. Since DT gets updated
1711 // through the split, we update the entry of the first region after the split,
1712 // and Region only points to the entry and the exit blocks, rather than
1713 // keeping everything in a list or set, the blocks membership and the
1714 // entry/exit blocks of the region are still valid after the split.
1715 CHR_DEBUG(dbgs() << "Splitting entry block " << EntryBlock->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Splitting entry block " << EntryBlock
->getName() << " at " << *Scope->BranchInsertPoint
<< "\n"; } } while (false)
1716 << " at " << *Scope->BranchInsertPoint << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Splitting entry block " << EntryBlock
->getName() << " at " << *Scope->BranchInsertPoint
<< "\n"; } } while (false)
;
1717 BasicBlock *NewEntryBlock =
1718 SplitBlock(EntryBlock, Scope->BranchInsertPoint, &DT);
1719 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&((NewEntryBlock->getSinglePredecessor() == EntryBlock &&
"NewEntryBlock's only pred must be EntryBlock") ? static_cast
<void> (0) : __assert_fail ("NewEntryBlock->getSinglePredecessor() == EntryBlock && \"NewEntryBlock's only pred must be EntryBlock\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1720, __PRETTY_FUNCTION__))
1720 "NewEntryBlock's only pred must be EntryBlock")((NewEntryBlock->getSinglePredecessor() == EntryBlock &&
"NewEntryBlock's only pred must be EntryBlock") ? static_cast
<void> (0) : __assert_fail ("NewEntryBlock->getSinglePredecessor() == EntryBlock && \"NewEntryBlock's only pred must be EntryBlock\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1720, __PRETTY_FUNCTION__))
;
1721 FirstRegion->replaceEntryRecursive(NewEntryBlock);
1722 BasicBlock *PreEntryBlock = EntryBlock;
1723
1724 ValueToValueMapTy VMap;
1725 // Clone the blocks in the scope (excluding the PreEntryBlock) to split into a
1726 // hot path (originals) and a cold path (clones) and update the PHIs at the
1727 // exit block.
1728 cloneScopeBlocks(Scope, PreEntryBlock, ExitBlock, LastRegion, VMap);
1729
1730 // Replace the old (placeholder) branch with the new (merged) conditional
1731 // branch.
1732 BranchInst *MergedBr = createMergedBranch(PreEntryBlock, EntryBlock,
1733 NewEntryBlock, VMap);
1734
1735#ifndef NDEBUG
1736 assertCHRRegionsHaveBiasedBranchOrSelect(Scope);
1737#endif
1738
1739 // Hoist the conditional values of the branches/selects.
1740 hoistScopeConditions(Scope, PreEntryBlock->getTerminator(), TrivialPHIs, DT);
1741
1742#ifndef NDEBUG
1743 assertBranchOrSelectConditionHoisted(Scope, PreEntryBlock);
1744#endif
1745
1746 // Create the combined branch condition and constant-fold the branches/selects
1747 // in the hot path.
1748 fixupBranchesAndSelects(Scope, PreEntryBlock, MergedBr,
1749 ProfileCount ? ProfileCount.getValue() : 0);
1750}
1751
1752// A helper for transformScopes. Clone the blocks in the scope (excluding the
1753// PreEntryBlock) to split into a hot path and a cold path and update the PHIs
1754// at the exit block.
1755void CHR::cloneScopeBlocks(CHRScope *Scope,
1756 BasicBlock *PreEntryBlock,
1757 BasicBlock *ExitBlock,
1758 Region *LastRegion,
1759 ValueToValueMapTy &VMap) {
1760 // Clone all the blocks. The original blocks will be the hot-path
1761 // CHR-optimized code and the cloned blocks will be the original unoptimized
1762 // code. This is so that the block pointers from the
1763 // CHRScope/Region/RegionInfo can stay valid in pointing to the hot-path code
1764 // which CHR should apply to.
1765 SmallVector<BasicBlock*, 8> NewBlocks;
1766 for (RegInfo &RI : Scope->RegInfos)
1767 for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1768 // sub-Scopes.
1769 assert(BB != PreEntryBlock && "Don't copy the preetntry block")((BB != PreEntryBlock && "Don't copy the preetntry block"
) ? static_cast<void> (0) : __assert_fail ("BB != PreEntryBlock && \"Don't copy the preetntry block\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1769, __PRETTY_FUNCTION__))
;
1770 BasicBlock *NewBB = CloneBasicBlock(BB, VMap, ".nonchr", &F);
1771 NewBlocks.push_back(NewBB);
1772 VMap[BB] = NewBB;
1773 }
1774
1775 // Place the cloned blocks right after the original blocks (right before the
1776 // exit block of.)
1777 if (ExitBlock)
1778 F.getBasicBlockList().splice(ExitBlock->getIterator(),
1779 F.getBasicBlockList(),
1780 NewBlocks[0]->getIterator(), F.end());
1781
1782 // Update the cloned blocks/instructions to refer to themselves.
1783 for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i)
1784 for (Instruction &I : *NewBlocks[i])
1785 RemapInstruction(&I, VMap,
1786 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1787
1788 // Add the cloned blocks to the PHIs of the exit blocks. ExitBlock is null for
1789 // the top-level region but we don't need to add PHIs. The trivial PHIs
1790 // inserted above will be updated here.
1791 if (ExitBlock)
1792 for (PHINode &PN : ExitBlock->phis())
1793 for (unsigned I = 0, NumOps = PN.getNumIncomingValues(); I < NumOps;
1794 ++I) {
1795 BasicBlock *Pred = PN.getIncomingBlock(I);
1796 if (LastRegion->contains(Pred)) {
1797 Value *V = PN.getIncomingValue(I);
1798 auto It = VMap.find(V);
1799 if (It != VMap.end()) V = It->second;
1800 assert(VMap.find(Pred) != VMap.end() && "Pred must have been cloned")((VMap.find(Pred) != VMap.end() && "Pred must have been cloned"
) ? static_cast<void> (0) : __assert_fail ("VMap.find(Pred) != VMap.end() && \"Pred must have been cloned\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1800, __PRETTY_FUNCTION__))
;
1801 PN.addIncoming(V, cast<BasicBlock>(VMap[Pred]));
1802 }
1803 }
1804}
1805
1806// A helper for transformScope. Replace the old (placeholder) branch with the
1807// new (merged) conditional branch.
1808BranchInst *CHR::createMergedBranch(BasicBlock *PreEntryBlock,
1809 BasicBlock *EntryBlock,
1810 BasicBlock *NewEntryBlock,
1811 ValueToValueMapTy &VMap) {
1812 BranchInst *OldBR = cast<BranchInst>(PreEntryBlock->getTerminator());
1813 assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == NewEntryBlock &&((OldBR->isUnconditional() && OldBR->getSuccessor
(0) == NewEntryBlock && "SplitBlock did not work correctly!"
) ? static_cast<void> (0) : __assert_fail ("OldBR->isUnconditional() && OldBR->getSuccessor(0) == NewEntryBlock && \"SplitBlock did not work correctly!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1814, __PRETTY_FUNCTION__))
1814 "SplitBlock did not work correctly!")((OldBR->isUnconditional() && OldBR->getSuccessor
(0) == NewEntryBlock && "SplitBlock did not work correctly!"
) ? static_cast<void> (0) : __assert_fail ("OldBR->isUnconditional() && OldBR->getSuccessor(0) == NewEntryBlock && \"SplitBlock did not work correctly!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1814, __PRETTY_FUNCTION__))
;
1815 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&((NewEntryBlock->getSinglePredecessor() == EntryBlock &&
"NewEntryBlock's only pred must be EntryBlock") ? static_cast
<void> (0) : __assert_fail ("NewEntryBlock->getSinglePredecessor() == EntryBlock && \"NewEntryBlock's only pred must be EntryBlock\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1816, __PRETTY_FUNCTION__))
1816 "NewEntryBlock's only pred must be EntryBlock")((NewEntryBlock->getSinglePredecessor() == EntryBlock &&
"NewEntryBlock's only pred must be EntryBlock") ? static_cast
<void> (0) : __assert_fail ("NewEntryBlock->getSinglePredecessor() == EntryBlock && \"NewEntryBlock's only pred must be EntryBlock\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1816, __PRETTY_FUNCTION__))
;
1817 assert(VMap.find(NewEntryBlock) != VMap.end() &&((VMap.find(NewEntryBlock) != VMap.end() && "NewEntryBlock must have been copied"
) ? static_cast<void> (0) : __assert_fail ("VMap.find(NewEntryBlock) != VMap.end() && \"NewEntryBlock must have been copied\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1818, __PRETTY_FUNCTION__))
1818 "NewEntryBlock must have been copied")((VMap.find(NewEntryBlock) != VMap.end() && "NewEntryBlock must have been copied"
) ? static_cast<void> (0) : __assert_fail ("VMap.find(NewEntryBlock) != VMap.end() && \"NewEntryBlock must have been copied\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1818, __PRETTY_FUNCTION__))
;
1819 OldBR->dropAllReferences();
1820 OldBR->eraseFromParent();
1821 // The true predicate is a placeholder. It will be replaced later in
1822 // fixupBranchesAndSelects().
1823 BranchInst *NewBR = BranchInst::Create(NewEntryBlock,
1824 cast<BasicBlock>(VMap[NewEntryBlock]),
1825 ConstantInt::getTrue(F.getContext()));
1826 PreEntryBlock->getInstList().push_back(NewBR);
1827 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&((NewEntryBlock->getSinglePredecessor() == EntryBlock &&
"NewEntryBlock's only pred must be EntryBlock") ? static_cast
<void> (0) : __assert_fail ("NewEntryBlock->getSinglePredecessor() == EntryBlock && \"NewEntryBlock's only pred must be EntryBlock\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1828, __PRETTY_FUNCTION__))
1828 "NewEntryBlock's only pred must be EntryBlock")((NewEntryBlock->getSinglePredecessor() == EntryBlock &&
"NewEntryBlock's only pred must be EntryBlock") ? static_cast
<void> (0) : __assert_fail ("NewEntryBlock->getSinglePredecessor() == EntryBlock && \"NewEntryBlock's only pred must be EntryBlock\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1828, __PRETTY_FUNCTION__))
;
1829 return NewBR;
1830}
1831
1832// A helper for transformScopes. Create the combined branch condition and
1833// constant-fold the branches/selects in the hot path.
1834void CHR::fixupBranchesAndSelects(CHRScope *Scope,
1835 BasicBlock *PreEntryBlock,
1836 BranchInst *MergedBR,
1837 uint64_t ProfileCount) {
1838 Value *MergedCondition = ConstantInt::getTrue(F.getContext());
1839 BranchProbability CHRBranchBias(1, 1);
1840 uint64_t NumCHRedBranches = 0;
1841 IRBuilder<> IRB(PreEntryBlock->getTerminator());
1842 for (RegInfo &RI : Scope->CHRRegions) {
1843 Region *R = RI.R;
1844 if (RI.HasBranch) {
1845 fixupBranch(R, Scope, IRB, MergedCondition, CHRBranchBias);
1846 ++NumCHRedBranches;
1847 }
1848 for (SelectInst *SI : RI.Selects) {
1849 fixupSelect(SI, Scope, IRB, MergedCondition, CHRBranchBias);
1850 ++NumCHRedBranches;
1851 }
1852 }
1853 Stats.NumBranchesDelta += NumCHRedBranches - 1;
1854 Stats.WeightedNumBranchesDelta += (NumCHRedBranches - 1) * ProfileCount;
1855 ORE.emit([&]() {
1856 return OptimizationRemark(DEBUG_TYPE"chr",
1857 "CHR",
1858 // Refer to the hot (original) path
1859 MergedBR->getSuccessor(0)->getTerminator())
1860 << "Merged " << ore::NV("NumCHRedBranches", NumCHRedBranches)
1861 << " branches or selects";
1862 });
1863 MergedBR->setCondition(MergedCondition);
1864 uint32_t Weights[] = {
1865 static_cast<uint32_t>(CHRBranchBias.scale(1000)),
1866 static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000)),
1867 };
1868 MDBuilder MDB(F.getContext());
1869 MergedBR->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
1870 CHR_DEBUG(dbgs() << "CHR branch bias " << Weights[0] << ":" << Weights[1]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "CHR branch bias " << Weights
[0] << ":" << Weights[1] << "\n"; } } while
(false)
1871 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "CHR branch bias " << Weights
[0] << ":" << Weights[1] << "\n"; } } while
(false)
;
1872}
1873
1874// A helper for fixupBranchesAndSelects. Add to the combined branch condition
1875// and constant-fold a branch in the hot path.
1876void CHR::fixupBranch(Region *R, CHRScope *Scope,
1877 IRBuilder<> &IRB,
1878 Value *&MergedCondition,
1879 BranchProbability &CHRBranchBias) {
1880 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1881 assert((IsTrueBiased || Scope->FalseBiasedRegions.count(R)) &&(((IsTrueBiased || Scope->FalseBiasedRegions.count(R)) &&
"Must be truthy or falsy") ? static_cast<void> (0) : __assert_fail
("(IsTrueBiased || Scope->FalseBiasedRegions.count(R)) && \"Must be truthy or falsy\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1882, __PRETTY_FUNCTION__))
1882 "Must be truthy or falsy")(((IsTrueBiased || Scope->FalseBiasedRegions.count(R)) &&
"Must be truthy or falsy") ? static_cast<void> (0) : __assert_fail
("(IsTrueBiased || Scope->FalseBiasedRegions.count(R)) && \"Must be truthy or falsy\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1882, __PRETTY_FUNCTION__))
;
1883 auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1884 assert(BranchBiasMap.find(R) != BranchBiasMap.end() &&((BranchBiasMap.find(R) != BranchBiasMap.end() && "Must be in the bias map"
) ? static_cast<void> (0) : __assert_fail ("BranchBiasMap.find(R) != BranchBiasMap.end() && \"Must be in the bias map\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1885, __PRETTY_FUNCTION__))
1885 "Must be in the bias map")((BranchBiasMap.find(R) != BranchBiasMap.end() && "Must be in the bias map"
) ? static_cast<void> (0) : __assert_fail ("BranchBiasMap.find(R) != BranchBiasMap.end() && \"Must be in the bias map\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1885, __PRETTY_FUNCTION__))
;
1886 BranchProbability Bias = BranchBiasMap[R];
1887 assert(Bias >= getCHRBiasThreshold() && "Must be highly biased")((Bias >= getCHRBiasThreshold() && "Must be highly biased"
) ? static_cast<void> (0) : __assert_fail ("Bias >= getCHRBiasThreshold() && \"Must be highly biased\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1887, __PRETTY_FUNCTION__))
;
1888 // Take the min.
1889 if (CHRBranchBias > Bias)
1890 CHRBranchBias = Bias;
1891 BasicBlock *IfThen = BI->getSuccessor(1);
1892 BasicBlock *IfElse = BI->getSuccessor(0);
1893 BasicBlock *RegionExitBlock = R->getExit();
1894 assert(RegionExitBlock && "Null ExitBlock")((RegionExitBlock && "Null ExitBlock") ? static_cast<
void> (0) : __assert_fail ("RegionExitBlock && \"Null ExitBlock\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1894, __PRETTY_FUNCTION__))
;
1895 assert((IfThen == RegionExitBlock || IfElse == RegionExitBlock) &&(((IfThen == RegionExitBlock || IfElse == RegionExitBlock) &&
IfThen != IfElse && "Invariant from findScopes") ? static_cast
<void> (0) : __assert_fail ("(IfThen == RegionExitBlock || IfElse == RegionExitBlock) && IfThen != IfElse && \"Invariant from findScopes\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1896, __PRETTY_FUNCTION__))
1896 IfThen != IfElse && "Invariant from findScopes")(((IfThen == RegionExitBlock || IfElse == RegionExitBlock) &&
IfThen != IfElse && "Invariant from findScopes") ? static_cast
<void> (0) : __assert_fail ("(IfThen == RegionExitBlock || IfElse == RegionExitBlock) && IfThen != IfElse && \"Invariant from findScopes\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1896, __PRETTY_FUNCTION__))
;
1897 if (IfThen == RegionExitBlock) {
1898 // Swap them so that IfThen means going into it and IfElse means skipping
1899 // it.
1900 std::swap(IfThen, IfElse);
1901 }
1902 CHR_DEBUG(dbgs() << "IfThen " << IfThen->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "IfThen " << IfThen->getName
() << " IfElse " << IfElse->getName() <<
"\n"; } } while (false)
1903 << " IfElse " << IfElse->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "IfThen " << IfThen->getName
() << " IfElse " << IfElse->getName() <<
"\n"; } } while (false)
;
1904 Value *Cond = BI->getCondition();
1905 BasicBlock *HotTarget = IsTrueBiased ? IfThen : IfElse;
1906 bool ConditionTrue = HotTarget == BI->getSuccessor(0);
1907 addToMergedCondition(ConditionTrue, Cond, BI, Scope, IRB,
1908 MergedCondition);
1909 // Constant-fold the branch at ClonedEntryBlock.
1910 assert(ConditionTrue == (HotTarget == BI->getSuccessor(0)) &&((ConditionTrue == (HotTarget == BI->getSuccessor(0)) &&
"The successor shouldn't change") ? static_cast<void> (
0) : __assert_fail ("ConditionTrue == (HotTarget == BI->getSuccessor(0)) && \"The successor shouldn't change\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1911, __PRETTY_FUNCTION__))
1911 "The successor shouldn't change")((ConditionTrue == (HotTarget == BI->getSuccessor(0)) &&
"The successor shouldn't change") ? static_cast<void> (
0) : __assert_fail ("ConditionTrue == (HotTarget == BI->getSuccessor(0)) && \"The successor shouldn't change\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1911, __PRETTY_FUNCTION__))
;
1912 Value *NewCondition = ConditionTrue ?
1913 ConstantInt::getTrue(F.getContext()) :
1914 ConstantInt::getFalse(F.getContext());
1915 BI->setCondition(NewCondition);
1916}
1917
1918// A helper for fixupBranchesAndSelects. Add to the combined branch condition
1919// and constant-fold a select in the hot path.
1920void CHR::fixupSelect(SelectInst *SI, CHRScope *Scope,
1921 IRBuilder<> &IRB,
1922 Value *&MergedCondition,
1923 BranchProbability &CHRBranchBias) {
1924 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1925 assert((IsTrueBiased ||(((IsTrueBiased || Scope->FalseBiasedSelects.count(SI)) &&
"Must be biased") ? static_cast<void> (0) : __assert_fail
("(IsTrueBiased || Scope->FalseBiasedSelects.count(SI)) && \"Must be biased\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1926, __PRETTY_FUNCTION__))
1926 Scope->FalseBiasedSelects.count(SI)) && "Must be biased")(((IsTrueBiased || Scope->FalseBiasedSelects.count(SI)) &&
"Must be biased") ? static_cast<void> (0) : __assert_fail
("(IsTrueBiased || Scope->FalseBiasedSelects.count(SI)) && \"Must be biased\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1926, __PRETTY_FUNCTION__))
;
1927 assert(SelectBiasMap.find(SI) != SelectBiasMap.end() &&((SelectBiasMap.find(SI) != SelectBiasMap.end() && "Must be in the bias map"
) ? static_cast<void> (0) : __assert_fail ("SelectBiasMap.find(SI) != SelectBiasMap.end() && \"Must be in the bias map\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1928, __PRETTY_FUNCTION__))
1928 "Must be in the bias map")((SelectBiasMap.find(SI) != SelectBiasMap.end() && "Must be in the bias map"
) ? static_cast<void> (0) : __assert_fail ("SelectBiasMap.find(SI) != SelectBiasMap.end() && \"Must be in the bias map\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1928, __PRETTY_FUNCTION__))
;
1929 BranchProbability Bias = SelectBiasMap[SI];
1930 assert(Bias >= getCHRBiasThreshold() && "Must be highly biased")((Bias >= getCHRBiasThreshold() && "Must be highly biased"
) ? static_cast<void> (0) : __assert_fail ("Bias >= getCHRBiasThreshold() && \"Must be highly biased\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp"
, 1930, __PRETTY_FUNCTION__))
;
1931 // Take the min.
1932 if (CHRBranchBias > Bias)
1933 CHRBranchBias = Bias;
1934 Value *Cond = SI->getCondition();
1935 addToMergedCondition(IsTrueBiased, Cond, SI, Scope, IRB,
1936 MergedCondition);
1937 Value *NewCondition = IsTrueBiased ?
1938 ConstantInt::getTrue(F.getContext()) :
1939 ConstantInt::getFalse(F.getContext());
1940 SI->setCondition(NewCondition);
1941}
1942
1943// A helper for fixupBranch/fixupSelect. Add a branch condition to the merged
1944// condition.
1945void CHR::addToMergedCondition(bool IsTrueBiased, Value *Cond,
1946 Instruction *BranchOrSelect,
1947 CHRScope *Scope,
1948 IRBuilder<> &IRB,
1949 Value *&MergedCondition) {
1950 if (IsTrueBiased) {
1951 MergedCondition = IRB.CreateAnd(MergedCondition, Cond);
1952 } else {
1953 // If Cond is an icmp and all users of V except for BranchOrSelect is a
1954 // branch, negate the icmp predicate and swap the branch targets and avoid
1955 // inserting an Xor to negate Cond.
1956 bool Done = false;
1957 if (auto *ICmp = dyn_cast<ICmpInst>(Cond))
1958 if (negateICmpIfUsedByBranchOrSelectOnly(ICmp, BranchOrSelect, Scope)) {
1959 MergedCondition = IRB.CreateAnd(MergedCondition, Cond);
1960 Done = true;
1961 }
1962 if (!Done) {
1963 Value *Negate = IRB.CreateXor(
1964 ConstantInt::getTrue(F.getContext()), Cond);
1965 MergedCondition = IRB.CreateAnd(MergedCondition, Negate);
1966 }
1967 }
1968}
1969
1970void CHR::transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes) {
1971 unsigned I = 0;
1972 DenseSet<PHINode *> TrivialPHIs;
1973 for (CHRScope *Scope : CHRScopes) {
1974 transformScopes(Scope, TrivialPHIs);
1975 CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { std::ostringstream oss; oss << " after transformScopes "
<< I++; dumpIR(F, oss.str().c_str(), nullptr); } } while
(false)
1976 std::ostringstream oss;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { std::ostringstream oss; oss << " after transformScopes "
<< I++; dumpIR(F, oss.str().c_str(), nullptr); } } while
(false)
1977 oss << " after transformScopes " << I++;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { std::ostringstream oss; oss << " after transformScopes "
<< I++; dumpIR(F, oss.str().c_str(), nullptr); } } while
(false)
1978 dumpIR(F, oss.str().c_str(), nullptr))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { std::ostringstream oss; oss << " after transformScopes "
<< I++; dumpIR(F, oss.str().c_str(), nullptr); } } while
(false)
;
1979 (void)I;
1980 }
1981}
1982
1983static void LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__))
1984dumpScopes(SmallVectorImpl<CHRScope *> &Scopes, const char *Label) {
1985 dbgs() << Label << " " << Scopes.size() << "\n";
1986 for (CHRScope *Scope : Scopes) {
1987 dbgs() << *Scope << "\n";
1988 }
1989}
1990
1991bool CHR::run() {
1992 if (!shouldApply(F, PSI))
1993 return false;
1994
1995 CHR_DEBUG(dumpIR(F, "before", nullptr))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dumpIR(F, "before", nullptr); } } while (false)
;
1996
1997 bool Changed = false;
1998 {
1999 CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs());
} } while (false)
2000 dbgs() << "RegionInfo:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs());
} } while (false)
2001 RI.print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs());
} } while (false)
;
2002
2003 // Recursively traverse the region tree and find regions that have biased
2004 // branches and/or selects and create scopes.
2005 SmallVector<CHRScope *, 8> AllScopes;
2006 findScopes(AllScopes);
2007 CHR_DEBUG(dumpScopes(AllScopes, "All scopes"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dumpScopes(AllScopes, "All scopes"); } } while (false
)
;
2008
2009 // Split the scopes if 1) the conditiona values of the biased
2010 // branches/selects of the inner/lower scope can't be hoisted up to the
2011 // outermost/uppermost scope entry, or 2) the condition values of the biased
2012 // branches/selects in a scope (including subscopes) don't share at least
2013 // one common value.
2014 SmallVector<CHRScope *, 8> SplitScopes;
2015 splitScopes(AllScopes, SplitScopes);
2016 CHR_DEBUG(dumpScopes(SplitScopes, "Split scopes"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dumpScopes(SplitScopes, "Split scopes"); } } while
(false)
;
2017
2018 // After splitting, set the biased regions and selects of a scope (a tree
2019 // root) that include those of the subscopes.
2020 classifyBiasedScopes(SplitScopes);
2021 CHR_DEBUG(dbgs() << "Set per-scope bias " << SplitScopes.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "Set per-scope bias " << SplitScopes
.size() << "\n"; } } while (false)
;
2022
2023 // Filter out the scopes that has only one biased region or select (CHR
2024 // isn't useful in such a case).
2025 SmallVector<CHRScope *, 8> FilteredScopes;
2026 filterScopes(SplitScopes, FilteredScopes);
2027 CHR_DEBUG(dumpScopes(FilteredScopes, "Filtered scopes"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dumpScopes(FilteredScopes, "Filtered scopes"); } }
while (false)
;
2028
2029 // Set the regions to be CHR'ed and their hoist stops for each scope.
2030 SmallVector<CHRScope *, 8> SetScopes;
2031 setCHRRegions(FilteredScopes, SetScopes);
2032 CHR_DEBUG(dumpScopes(SetScopes, "Set CHR regions"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dumpScopes(SetScopes, "Set CHR regions"); } } while
(false)
;
2033
2034 // Sort CHRScopes by the depth so that outer CHRScopes comes before inner
2035 // ones. We need to apply CHR from outer to inner so that we apply CHR only
2036 // to the hot path, rather than both hot and cold paths.
2037 SmallVector<CHRScope *, 8> SortedScopes;
2038 sortScopes(SetScopes, SortedScopes);
2039 CHR_DEBUG(dumpScopes(SortedScopes, "Sorted scopes"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dumpScopes(SortedScopes, "Sorted scopes"); } } while
(false)
;
2040
2041 CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs());
} } while (false)
2042 dbgs() << "RegionInfo:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs());
} } while (false)
2043 RI.print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs());
} } while (false)
;
2044
2045 // Apply the CHR transformation.
2046 if (!SortedScopes.empty()) {
2047 transformScopes(SortedScopes);
2048 Changed = true;
2049 }
2050 }
2051
2052 if (Changed) {
2053 CHR_DEBUG(dumpIR(F, "after", &Stats))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("chr")) { dumpIR(F, "after", &Stats); } } while (false)
;
2054 ORE.emit([&]() {
2055 return OptimizationRemark(DEBUG_TYPE"chr", "Stats", &F)
2056 << ore::NV("Function", &F) << " "
2057 << "Reduced the number of branches in hot paths by "
2058 << ore::NV("NumBranchesDelta", Stats.NumBranchesDelta)
2059 << " (static) and "
2060 << ore::NV("WeightedNumBranchesDelta", Stats.WeightedNumBranchesDelta)
2061 << " (weighted by PGO count)";
2062 });
2063 }
2064
2065 return Changed;
2066}
2067
2068bool ControlHeightReductionLegacyPass::runOnFunction(Function &F) {
2069 BlockFrequencyInfo &BFI =
2070 getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
2071 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2072 ProfileSummaryInfo &PSI =
2073 getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
2074 RegionInfo &RI = getAnalysis<RegionInfoPass>().getRegionInfo();
2075 std::unique_ptr<OptimizationRemarkEmitter> OwnedORE =
2076 std::make_unique<OptimizationRemarkEmitter>(&F);
2077 return CHR(F, BFI, DT, PSI, RI, *OwnedORE.get()).run();
2078}
2079
2080namespace llvm {
2081
2082ControlHeightReductionPass::ControlHeightReductionPass() {
2083 parseCHRFilterFiles();
2084}
2085
2086PreservedAnalyses ControlHeightReductionPass::run(
2087 Function &F,
2088 FunctionAnalysisManager &FAM) {
2089 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
2090 auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
2091 auto &MAMProxy = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
2092 auto &PSI = *MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
2093 auto &RI = FAM.getResult<RegionInfoAnalysis>(F);
2094 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
2095 bool Changed = CHR(F, BFI, DT, PSI, RI, ORE).run();
2096 if (!Changed)
2097 return PreservedAnalyses::all();
2098 auto PA = PreservedAnalyses();
2099 PA.preserve<GlobalsAA>();
2100 return PA;
2101}
2102
2103} // namespace llvm

/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h

1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the SmallVector class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_SMALLVECTOR_H
14#define LLVM_ADT_SMALLVECTOR_H
15
16#include "llvm/ADT/iterator_range.h"
17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/ErrorHandling.h"
19#include "llvm/Support/MathExtras.h"
20#include "llvm/Support/MemAlloc.h"
21#include "llvm/Support/type_traits.h"
22#include <algorithm>
23#include <cassert>
24#include <cstddef>
25#include <cstdlib>
26#include <cstring>
27#include <initializer_list>
28#include <iterator>
29#include <limits>
30#include <memory>
31#include <new>
32#include <type_traits>
33#include <utility>
34
35namespace llvm {
36
37/// This is all the stuff common to all SmallVectors.
38///
39/// The template parameter specifies the type which should be used to hold the
40/// Size and Capacity of the SmallVector, so it can be adjusted.
41/// Using 32 bit size is desirable to shrink the size of the SmallVector.
42/// Using 64 bit size is desirable for cases like SmallVector<char>, where a
43/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
44/// buffering bitcode output - which can exceed 4GB.
45template <class Size_T> class SmallVectorBase {
46protected:
47 void *BeginX;
48 Size_T Size = 0, Capacity;
49
50 /// The maximum value of the Size_T used.
51 static constexpr size_t SizeTypeMax() {
52 return std::numeric_limits<Size_T>::max();
53 }
54
55 SmallVectorBase() = delete;
56 SmallVectorBase(void *FirstEl, size_t TotalCapacity)
57 : BeginX(FirstEl), Capacity(TotalCapacity) {}
58
59 /// This is a helper for \a grow() that's out of line to reduce code
60 /// duplication. This function will report a fatal error if it can't grow at
61 /// least to \p MinSize.
62 void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);
63
64 /// This is an implementation of the grow() method which only works
65 /// on POD-like data types and is out of line to reduce code duplication.
66 /// This function will report a fatal error if it cannot increase capacity.
67 void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
68
69public:
70 size_t size() const { return Size; }
71 size_t capacity() const { return Capacity; }
72
73 LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; }
4
Assuming field 'Size' is not equal to 0, which participates in a condition later
5
Returning zero, which participates in a condition later
74
75 /// Set the array size to \p N, which the current array must have enough
76 /// capacity for.
77 ///
78 /// This does not construct or destroy any elements in the vector.
79 ///
80 /// Clients can use this in conjunction with capacity() to write past the end
81 /// of the buffer when they know that more elements are available, and only
82 /// update the size later. This avoids the cost of value initializing elements
83 /// which will only be overwritten.
84 void set_size(size_t N) {
85 assert(N <= capacity())((N <= capacity()) ? static_cast<void> (0) : __assert_fail
("N <= capacity()", "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 85, __PRETTY_FUNCTION__))
;
86 Size = N;
87 }
88};
89
90template <class T>
91using SmallVectorSizeType =
92 typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
93 uint32_t>::type;
94
95/// Figure out the offset of the first element.
96template <class T, typename = void> struct SmallVectorAlignmentAndSize {
97 alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
98 SmallVectorBase<SmallVectorSizeType<T>>)];
99 alignas(T) char FirstEl[sizeof(T)];
100};
101
102/// This is the part of SmallVectorTemplateBase which does not depend on whether
103/// the type T is a POD. The extra dummy template argument is used by ArrayRef
104/// to avoid unnecessarily requiring T to be complete.
105template <typename T, typename = void>
106class SmallVectorTemplateCommon
107 : public SmallVectorBase<SmallVectorSizeType<T>> {
108 using Base = SmallVectorBase<SmallVectorSizeType<T>>;
109
110 /// Find the address of the first element. For this pointer math to be valid
111 /// with small-size of 0 for T with lots of alignment, it's important that
112 /// SmallVectorStorage is properly-aligned even for small-size of 0.
113 void *getFirstEl() const {
114 return const_cast<void *>(reinterpret_cast<const void *>(
115 reinterpret_cast<const char *>(this) +
116 offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl
)
));
117 }
118 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
119
120protected:
121 SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
122
123 void grow_pod(size_t MinSize, size_t TSize) {
124 Base::grow_pod(getFirstEl(), MinSize, TSize);
125 }
126
127 /// Return true if this is a smallvector which has not had dynamic
128 /// memory allocated for it.
129 bool isSmall() const { return this->BeginX == getFirstEl(); }
130
131 /// Put this vector in a state of being small.
132 void resetToSmall() {
133 this->BeginX = getFirstEl();
134 this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
135 }
136
137 /// Return true if V is an internal reference to the given range.
138 bool isReferenceToRange(const void *V, const void *First, const void *Last) const {
139 // Use std::less to avoid UB.
140 std::less<> LessThan;
141 return !LessThan(V, First) && LessThan(V, Last);
142 }
143
144 /// Return true if V is an internal reference to this vector.
145 bool isReferenceToStorage(const void *V) const {
146 return isReferenceToRange(V, this->begin(), this->end());
147 }
148
149 /// Return true if First and Last form a valid (possibly empty) range in this
150 /// vector's storage.
151 bool isRangeInStorage(const void *First, const void *Last) const {
152 // Use std::less to avoid UB.
153 std::less<> LessThan;
154 return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
155 !LessThan(this->end(), Last);
156 }
157
158 /// Return true unless Elt will be invalidated by resizing the vector to
159 /// NewSize.
160 bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
161 // Past the end.
162 if (LLVM_LIKELY(!isReferenceToStorage(Elt))__builtin_expect((bool)(!isReferenceToStorage(Elt)), true))
163 return true;
164
165 // Return false if Elt will be destroyed by shrinking.
166 if (NewSize <= this->size())
167 return Elt < this->begin() + NewSize;
168
169 // Return false if we need to grow.
170 return NewSize <= this->capacity();
171 }
172
173 /// Check whether Elt will be invalidated by resizing the vector to NewSize.
174 void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
175 assert(isSafeToReferenceAfterResize(Elt, NewSize) &&((isSafeToReferenceAfterResize(Elt, NewSize) && "Attempting to reference an element of the vector in an operation "
"that invalidates it") ? static_cast<void> (0) : __assert_fail
("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 177, __PRETTY_FUNCTION__))
176 "Attempting to reference an element of the vector in an operation "((isSafeToReferenceAfterResize(Elt, NewSize) && "Attempting to reference an element of the vector in an operation "
"that invalidates it") ? static_cast<void> (0) : __assert_fail
("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 177, __PRETTY_FUNCTION__))
177 "that invalidates it")((isSafeToReferenceAfterResize(Elt, NewSize) && "Attempting to reference an element of the vector in an operation "
"that invalidates it") ? static_cast<void> (0) : __assert_fail
("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 177, __PRETTY_FUNCTION__))
;
178 }
179
180 /// Check whether Elt will be invalidated by increasing the size of the
181 /// vector by N.
182 void assertSafeToAdd(const void *Elt, size_t N = 1) {
183 this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
184 }
185
186 /// Check whether any part of the range will be invalidated by clearing.
187 void assertSafeToReferenceAfterClear(const T *From, const T *To) {
188 if (From == To)
189 return;
190 this->assertSafeToReferenceAfterResize(From, 0);
191 this->assertSafeToReferenceAfterResize(To - 1, 0);
192 }
193 template <
194 class ItTy,
195 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
196 bool> = false>
197 void assertSafeToReferenceAfterClear(ItTy, ItTy) {}
198
199 /// Check whether any part of the range will be invalidated by growing.
200 void assertSafeToAddRange(const T *From, const T *To) {
201 if (From == To)
202 return;
203 this->assertSafeToAdd(From, To - From);
204 this->assertSafeToAdd(To - 1, To - From);
205 }
206 template <
207 class ItTy,
208 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
209 bool> = false>
210 void assertSafeToAddRange(ItTy, ItTy) {}
211
212 /// Reserve enough space to add one element, and return the updated element
213 /// pointer in case it was a reference to the storage.
214 template <class U>
215 static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
216 size_t N) {
217 size_t NewSize = This->size() + N;
218 if (LLVM_LIKELY(NewSize <= This->capacity())__builtin_expect((bool)(NewSize <= This->capacity()), true
)
)
219 return &Elt;
220
221 bool ReferencesStorage = false;
222 int64_t Index = -1;
223 if (!U::TakesParamByValue) {
224 if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))__builtin_expect((bool)(This->isReferenceToStorage(&Elt
)), false)
) {
225 ReferencesStorage = true;
226 Index = &Elt - This->begin();
227 }
228 }
229 This->grow(NewSize);
230 return ReferencesStorage ? This->begin() + Index : &Elt;
231 }
232
233public:
234 using size_type = size_t;
235 using difference_type = ptrdiff_t;
236 using value_type = T;
237 using iterator = T *;
238 using const_iterator = const T *;
239
240 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
241 using reverse_iterator = std::reverse_iterator<iterator>;
242
243 using reference = T &;
244 using const_reference = const T &;
245 using pointer = T *;
246 using const_pointer = const T *;
247
248 using Base::capacity;
249 using Base::empty;
250 using Base::size;
251
252 // forward iterator creation methods.
253 iterator begin() { return (iterator)this->BeginX; }
254 const_iterator begin() const { return (const_iterator)this->BeginX; }
255 iterator end() { return begin() + size(); }
256 const_iterator end() const { return begin() + size(); }
257
258 // reverse iterator creation methods.
259 reverse_iterator rbegin() { return reverse_iterator(end()); }
260 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
261 reverse_iterator rend() { return reverse_iterator(begin()); }
262 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
263
264 size_type size_in_bytes() const { return size() * sizeof(T); }
265 size_type max_size() const {
266 return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
267 }
268
269 size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
270
271 /// Return a pointer to the vector's buffer, even if empty().
272 pointer data() { return pointer(begin()); }
273 /// Return a pointer to the vector's buffer, even if empty().
274 const_pointer data() const { return const_pointer(begin()); }
275
276 reference operator[](size_type idx) {
277 assert(idx < size())((idx < size()) ? static_cast<void> (0) : __assert_fail
("idx < size()", "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 277, __PRETTY_FUNCTION__))
;
278 return begin()[idx];
279 }
280 const_reference operator[](size_type idx) const {
281 assert(idx < size())((idx < size()) ? static_cast<void> (0) : __assert_fail
("idx < size()", "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 281, __PRETTY_FUNCTION__))
;
282 return begin()[idx];
283 }
284
285 reference front() {
286 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 286, __PRETTY_FUNCTION__))
;
287 return begin()[0];
288 }
289 const_reference front() const {
290 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 290, __PRETTY_FUNCTION__))
;
291 return begin()[0];
292 }
293
294 reference back() {
295 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 295, __PRETTY_FUNCTION__))
;
296 return end()[-1];
297 }
298 const_reference back() const {
299 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 299, __PRETTY_FUNCTION__))
;
300 return end()[-1];
301 }
302};
303
304/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
305/// method implementations that are designed to work with non-trivial T's.
306///
307/// We approximate is_trivially_copyable with trivial move/copy construction and
308/// trivial destruction. While the standard doesn't specify that you're allowed
309/// copy these types with memcpy, there is no way for the type to observe this.
310/// This catches the important case of std::pair<POD, POD>, which is not
311/// trivially assignable.
312template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
313 (is_trivially_move_constructible<T>::value) &&
314 std::is_trivially_destructible<T>::value>
315class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
316 friend class SmallVectorTemplateCommon<T>;
317
318protected:
319 static constexpr bool TakesParamByValue = false;
320 using ValueParamT = const T &;
321
322 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
323
324 static void destroy_range(T *S, T *E) {
325 while (S != E) {
326 --E;
327 E->~T();
328 }
329 }
330
331 /// Move the range [I, E) into the uninitialized memory starting with "Dest",
332 /// constructing elements as needed.
333 template<typename It1, typename It2>
334 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
335 std::uninitialized_copy(std::make_move_iterator(I),
336 std::make_move_iterator(E), Dest);
337 }
338
339 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
340 /// constructing elements as needed.
341 template<typename It1, typename It2>
342 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
343 std::uninitialized_copy(I, E, Dest);
344 }
345
346 /// Grow the allocated memory (without initializing new elements), doubling
347 /// the size of the allocated memory. Guarantees space for at least one more
348 /// element, or MinSize more elements if specified.
349 void grow(size_t MinSize = 0);
350
351 /// Create a new allocation big enough for \p MinSize and pass back its size
352 /// in \p NewCapacity. This is the first section of \a grow().
353 T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
354 return static_cast<T *>(
355 SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow(
356 MinSize, sizeof(T), NewCapacity));
357 }
358
359 /// Move existing elements over to the new allocation \p NewElts, the middle
360 /// section of \a grow().
361 void moveElementsForGrow(T *NewElts);
362
363 /// Transfer ownership of the allocation, finishing up \a grow().
364 void takeAllocationForGrow(T *NewElts, size_t NewCapacity);
365
366 /// Reserve enough space to add one element, and return the updated element
367 /// pointer in case it was a reference to the storage.
368 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
369 return this->reserveForParamAndGetAddressImpl(this, Elt, N);
370 }
371
372 /// Reserve enough space to add one element, and return the updated element
373 /// pointer in case it was a reference to the storage.
374 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
375 return const_cast<T *>(
376 this->reserveForParamAndGetAddressImpl(this, Elt, N));
377 }
378
379 static T &&forward_value_param(T &&V) { return std::move(V); }
380 static const T &forward_value_param(const T &V) { return V; }
381
382 void growAndAssign(size_t NumElts, const T &Elt) {
383 // Grow manually in case Elt is an internal reference.
384 size_t NewCapacity;
385 T *NewElts = mallocForGrow(NumElts, NewCapacity);
386 std::uninitialized_fill_n(NewElts, NumElts, Elt);
387 this->destroy_range(this->begin(), this->end());
388 takeAllocationForGrow(NewElts, NewCapacity);
389 this->set_size(NumElts);
390 }
391
392 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
393 // Grow manually in case one of Args is an internal reference.
394 size_t NewCapacity;
395 T *NewElts = mallocForGrow(0, NewCapacity);
396 ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);
397 moveElementsForGrow(NewElts);
398 takeAllocationForGrow(NewElts, NewCapacity);
399 this->set_size(this->size() + 1);
400 return this->back();
401 }
402
403public:
404 void push_back(const T &Elt) {
405 const T *EltPtr = reserveForParamAndGetAddress(Elt);
406 ::new ((void *)this->end()) T(*EltPtr);
407 this->set_size(this->size() + 1);
408 }
409
410 void push_back(T &&Elt) {
411 T *EltPtr = reserveForParamAndGetAddress(Elt);
412 ::new ((void *)this->end()) T(::std::move(*EltPtr));
413 this->set_size(this->size() + 1);
414 }
415
416 void pop_back() {
417 this->set_size(this->size() - 1);
418 this->end()->~T();
419 }
420};
421
422// Define this out-of-line to dissuade the C++ compiler from inlining it.
423template <typename T, bool TriviallyCopyable>
424void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
425 size_t NewCapacity;
426 T *NewElts = mallocForGrow(MinSize, NewCapacity);
427 moveElementsForGrow(NewElts);
428 takeAllocationForGrow(NewElts, NewCapacity);
429}
430
431// Define this out-of-line to dissuade the C++ compiler from inlining it.
432template <typename T, bool TriviallyCopyable>
433void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow(
434 T *NewElts) {
435 // Move the elements over.
436 this->uninitialized_move(this->begin(), this->end(), NewElts);
437
438 // Destroy the original elements.
439 destroy_range(this->begin(), this->end());
440}
441
442// Define this out-of-line to dissuade the C++ compiler from inlining it.
443template <typename T, bool TriviallyCopyable>
444void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow(
445 T *NewElts, size_t NewCapacity) {
446 // If this wasn't grown from the inline copy, deallocate the old space.
447 if (!this->isSmall())
448 free(this->begin());
449
450 this->BeginX = NewElts;
451 this->Capacity = NewCapacity;
452}
453
454/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
455/// method implementations that are designed to work with trivially copyable
456/// T's. This allows using memcpy in place of copy/move construction and
457/// skipping destruction.
458template <typename T>
459class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
460 friend class SmallVectorTemplateCommon<T>;
461
462protected:
463 /// True if it's cheap enough to take parameters by value. Doing so avoids
464 /// overhead related to mitigations for reference invalidation.
465 static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
466
467 /// Either const T& or T, depending on whether it's cheap enough to take
468 /// parameters by value.
469 using ValueParamT =
470 typename std::conditional<TakesParamByValue, T, const T &>::type;
471
472 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
473
474 // No need to do a destroy loop for POD's.
475 static void destroy_range(T *, T *) {}
476
477 /// Move the range [I, E) onto the uninitialized memory
478 /// starting with "Dest", constructing elements into it as needed.
479 template<typename It1, typename It2>
480 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
481 // Just do a copy.
482 uninitialized_copy(I, E, Dest);
483 }
484
485 /// Copy the range [I, E) onto the uninitialized memory
486 /// starting with "Dest", constructing elements into it as needed.
487 template<typename It1, typename It2>
488 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
489 // Arbitrary iterator types; just use the basic implementation.
490 std::uninitialized_copy(I, E, Dest);
491 }
492
493 /// Copy the range [I, E) onto the uninitialized memory
494 /// starting with "Dest", constructing elements into it as needed.
495 template <typename T1, typename T2>
496 static void uninitialized_copy(
497 T1 *I, T1 *E, T2 *Dest,
498 std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
499 T2>::value> * = nullptr) {
500 // Use memcpy for PODs iterated by pointers (which includes SmallVector
501 // iterators): std::uninitialized_copy optimizes to memmove, but we can
502 // use memcpy here. Note that I and E are iterators and thus might be
503 // invalid for memcpy if they are equal.
504 if (I != E)
505 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
506 }
507
508 /// Double the size of the allocated memory, guaranteeing space for at
509 /// least one more element or MinSize if specified.
510 void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
511
512 /// Reserve enough space to add one element, and return the updated element
513 /// pointer in case it was a reference to the storage.
514 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
515 return this->reserveForParamAndGetAddressImpl(this, Elt, N);
516 }
517
518 /// Reserve enough space to add one element, and return the updated element
519 /// pointer in case it was a reference to the storage.
520 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
521 return const_cast<T *>(
522 this->reserveForParamAndGetAddressImpl(this, Elt, N));
523 }
524
525 /// Copy \p V or return a reference, depending on \a ValueParamT.
526 static ValueParamT forward_value_param(ValueParamT V) { return V; }
527
528 void growAndAssign(size_t NumElts, T Elt) {
529 // Elt has been copied in case it's an internal reference, side-stepping
530 // reference invalidation problems without losing the realloc optimization.
531 this->set_size(0);
532 this->grow(NumElts);
533 std::uninitialized_fill_n(this->begin(), NumElts, Elt);
534 this->set_size(NumElts);
535 }
536
537 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
538 // Use push_back with a copy in case Args has an internal reference,
539 // side-stepping reference invalidation problems without losing the realloc
540 // optimization.
541 push_back(T(std::forward<ArgTypes>(Args)...));
542 return this->back();
543 }
544
545public:
546 void push_back(ValueParamT Elt) {
547 const T *EltPtr = reserveForParamAndGetAddress(Elt);
548 memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
549 this->set_size(this->size() + 1);
550 }
551
552 void pop_back() { this->set_size(this->size() - 1); }
553};
554
555/// This class consists of common code factored out of the SmallVector class to
556/// reduce code duplication based on the SmallVector 'N' template parameter.
557template <typename T>
558class SmallVectorImpl : public SmallVectorTemplateBase<T> {
559 using SuperClass = SmallVectorTemplateBase<T>;
560
561public:
562 using iterator = typename SuperClass::iterator;
563 using const_iterator = typename SuperClass::const_iterator;
564 using reference = typename SuperClass::reference;
565 using size_type = typename SuperClass::size_type;
566
567protected:
568 using SmallVectorTemplateBase<T>::TakesParamByValue;
569 using ValueParamT = typename SuperClass::ValueParamT;
570
571 // Default ctor - Initialize to empty.
572 explicit SmallVectorImpl(unsigned N)
573 : SmallVectorTemplateBase<T>(N) {}
574
575public:
576 SmallVectorImpl(const SmallVectorImpl &) = delete;
577
578 ~SmallVectorImpl() {
579 // Subclass has already destructed this vector's elements.
580 // If this wasn't grown from the inline copy, deallocate the old space.
581 if (!this->isSmall())
582 free(this->begin());
583 }
584
585 void clear() {
586 this->destroy_range(this->begin(), this->end());
587 this->Size = 0;
588 }
589
590private:
591 template <bool ForOverwrite> void resizeImpl(size_type N) {
592 if (N < this->size()) {
593 this->pop_back_n(this->size() - N);
594 } else if (N > this->size()) {
595 this->reserve(N);
596 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
597 if (ForOverwrite)
598 new (&*I) T;
599 else
600 new (&*I) T();
601 this->set_size(N);
602 }
603 }
604
605public:
606 void resize(size_type N) { resizeImpl<false>(N); }
607
608 /// Like resize, but \ref T is POD, the new values won't be initialized.
609 void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
610
611 void resize(size_type N, ValueParamT NV) {
612 if (N == this->size())
613 return;
614
615 if (N < this->size()) {
616 this->pop_back_n(this->size() - N);
617 return;
618 }
619
620 // N > this->size(). Defer to append.
621 this->append(N - this->size(), NV);
622 }
623
624 void reserve(size_type N) {
625 if (this->capacity() < N)
626 this->grow(N);
627 }
628
629 void pop_back_n(size_type NumItems) {
630 assert(this->size() >= NumItems)((this->size() >= NumItems) ? static_cast<void> (
0) : __assert_fail ("this->size() >= NumItems", "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 630, __PRETTY_FUNCTION__))
;
631 this->destroy_range(this->end() - NumItems, this->end());
632 this->set_size(this->size() - NumItems);
633 }
634
635 LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
636 T Result = ::std::move(this->back());
637 this->pop_back();
638 return Result;
639 }
640
641 void swap(SmallVectorImpl &RHS);
642
643 /// Add the specified range to the end of the SmallVector.
644 template <typename in_iter,
645 typename = std::enable_if_t<std::is_convertible<
646 typename std::iterator_traits<in_iter>::iterator_category,
647 std::input_iterator_tag>::value>>
648 void append(in_iter in_start, in_iter in_end) {
649 this->assertSafeToAddRange(in_start, in_end);
650 size_type NumInputs = std::distance(in_start, in_end);
651 this->reserve(this->size() + NumInputs);
652 this->uninitialized_copy(in_start, in_end, this->end());
653 this->set_size(this->size() + NumInputs);
654 }
655
656 /// Append \p NumInputs copies of \p Elt to the end.
657 void append(size_type NumInputs, ValueParamT Elt) {
658 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
659 std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
660 this->set_size(this->size() + NumInputs);
661 }
662
663 void append(std::initializer_list<T> IL) {
664 append(IL.begin(), IL.end());
665 }
666
667 void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }
668
669 void assign(size_type NumElts, ValueParamT Elt) {
670 // Note that Elt could be an internal reference.
671 if (NumElts > this->capacity()) {
672 this->growAndAssign(NumElts, Elt);
673 return;
674 }
675
676 // Assign over existing elements.
677 std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
678 if (NumElts > this->size())
679 std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
680 else if (NumElts < this->size())
681 this->destroy_range(this->begin() + NumElts, this->end());
682 this->set_size(NumElts);
683 }
684
685 // FIXME: Consider assigning over existing elements, rather than clearing &
686 // re-initializing them - for all assign(...) variants.
687
688 template <typename in_iter,
689 typename = std::enable_if_t<std::is_convertible<
690 typename std::iterator_traits<in_iter>::iterator_category,
691 std::input_iterator_tag>::value>>
692 void assign(in_iter in_start, in_iter in_end) {
693 this->assertSafeToReferenceAfterClear(in_start, in_end);
694 clear();
695 append(in_start, in_end);
696 }
697
698 void assign(std::initializer_list<T> IL) {
699 clear();
700 append(IL);
701 }
702
703 void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }
704
705 iterator erase(const_iterator CI) {
706 // Just cast away constness because this is a non-const member function.
707 iterator I = const_cast<iterator>(CI);
708
709 assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.")((this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("this->isReferenceToStorage(CI) && \"Iterator to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 709, __PRETTY_FUNCTION__))
;
710
711 iterator N = I;
712 // Shift all elts down one.
713 std::move(I+1, this->end(), I);
714 // Drop the last elt.
715 this->pop_back();
716 return(N);
717 }
718
719 iterator erase(const_iterator CS, const_iterator CE) {
720 // Just cast away constness because this is a non-const member function.
721 iterator S = const_cast<iterator>(CS);
722 iterator E = const_cast<iterator>(CE);
723
724 assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.")((this->isRangeInStorage(S, E) && "Range to erase is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("this->isRangeInStorage(S, E) && \"Range to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 724, __PRETTY_FUNCTION__))
;
725
726 iterator N = S;
727 // Shift all elts down.
728 iterator I = std::move(E, this->end(), S);
729 // Drop the last elts.
730 this->destroy_range(I, this->end());
731 this->set_size(I - this->begin());
732 return(N);
733 }
734
735private:
736 template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
737 // Callers ensure that ArgType is derived from T.
738 static_assert(
739 std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
740 T>::value,
741 "ArgType must be derived from T!");
742
743 if (I == this->end()) { // Important special case for empty vector.
744 this->push_back(::std::forward<ArgType>(Elt));
745 return this->end()-1;
746 }
747
748 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")((this->isReferenceToStorage(I) && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 748, __PRETTY_FUNCTION__))
;
749
750 // Grow if necessary.
751 size_t Index = I - this->begin();
752 std::remove_reference_t<ArgType> *EltPtr =
753 this->reserveForParamAndGetAddress(Elt);
754 I = this->begin() + Index;
755
756 ::new ((void*) this->end()) T(::std::move(this->back()));
757 // Push everything else over.
758 std::move_backward(I, this->end()-1, this->end());
759 this->set_size(this->size() + 1);
760
761 // If we just moved the element we're inserting, be sure to update
762 // the reference (never happens if TakesParamByValue).
763 static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
764 "ArgType must be 'T' when taking by value!");
765 if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
766 ++EltPtr;
767
768 *I = ::std::forward<ArgType>(*EltPtr);
769 return I;
770 }
771
772public:
773 iterator insert(iterator I, T &&Elt) {
774 return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
775 }
776
777 iterator insert(iterator I, const T &Elt) {
778 return insert_one_impl(I, this->forward_value_param(Elt));
779 }
780
781 iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
782 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
783 size_t InsertElt = I - this->begin();
784
785 if (I == this->end()) { // Important special case for empty vector.
786 append(NumToInsert, Elt);
787 return this->begin()+InsertElt;
788 }
789
790 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")((this->isReferenceToStorage(I) && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 790, __PRETTY_FUNCTION__))
;
791
792 // Ensure there is enough space, and get the (maybe updated) address of
793 // Elt.
794 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);
795
796 // Uninvalidate the iterator.
797 I = this->begin()+InsertElt;
798
799 // If there are more elements between the insertion point and the end of the
800 // range than there are being inserted, we can use a simple approach to
801 // insertion. Since we already reserved space, we know that this won't
802 // reallocate the vector.
803 if (size_t(this->end()-I) >= NumToInsert) {
804 T *OldEnd = this->end();
805 append(std::move_iterator<iterator>(this->end() - NumToInsert),
806 std::move_iterator<iterator>(this->end()));
807
808 // Copy the existing elements that get replaced.
809 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
810
811 // If we just moved the element we're inserting, be sure to update
812 // the reference (never happens if TakesParamByValue).
813 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
814 EltPtr += NumToInsert;
815
816 std::fill_n(I, NumToInsert, *EltPtr);
817 return I;
818 }
819
820 // Otherwise, we're inserting more elements than exist already, and we're
821 // not inserting at the end.
822
823 // Move over the elements that we're about to overwrite.
824 T *OldEnd = this->end();
825 this->set_size(this->size() + NumToInsert);
826 size_t NumOverwritten = OldEnd-I;
827 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
828
829 // If we just moved the element we're inserting, be sure to update
830 // the reference (never happens if TakesParamByValue).
831 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
832 EltPtr += NumToInsert;
833
834 // Replace the overwritten part.
835 std::fill_n(I, NumOverwritten, *EltPtr);
836
837 // Insert the non-overwritten middle part.
838 std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
839 return I;
840 }
841
842 template <typename ItTy,
843 typename = std::enable_if_t<std::is_convertible<
844 typename std::iterator_traits<ItTy>::iterator_category,
845 std::input_iterator_tag>::value>>
846 iterator insert(iterator I, ItTy From, ItTy To) {
847 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
848 size_t InsertElt = I - this->begin();
849
850 if (I == this->end()) { // Important special case for empty vector.
851 append(From, To);
852 return this->begin()+InsertElt;
853 }
854
855 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")((this->isReferenceToStorage(I) && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/ADT/SmallVector.h"
, 855, __PRETTY_FUNCTION__))
;
856
857 // Check that the reserve that follows doesn't invalidate the iterators.
858 this->assertSafeToAddRange(From, To);
859
860 size_t NumToInsert = std::distance(From, To);
861
862 // Ensure there is enough space.
863 reserve(this->size() + NumToInsert);
864
865 // Uninvalidate the iterator.
866 I = this->begin()+InsertElt;
867
868 // If there are more elements between the insertion point and the end of the
869 // range than there are being inserted, we can use a simple approach to
870 // insertion. Since we already reserved space, we know that this won't
871 // reallocate the vector.
872 if (size_t(this->end()-I) >= NumToInsert) {
873 T *OldEnd = this->end();
874 append(std::move_iterator<iterator>(this->end() - NumToInsert),
875 std::move_iterator<iterator>(this->end()));
876
877 // Copy the existing elements that get replaced.
878 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
879
880 std::copy(From, To, I);
881 return I;
882 }
883
884 // Otherwise, we're inserting more elements than exist already, and we're
885 // not inserting at the end.
886
887 // Move over the elements that we're about to overwrite.
888 T *OldEnd = this->end();
889 this->set_size(this->size() + NumToInsert);
890 size_t NumOverwritten = OldEnd-I;
891 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
892
893 // Replace the overwritten part.
894 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
895 *J = *From;
896 ++J; ++From;
897 }
898
899 // Insert the non-overwritten middle part.
900 this->uninitialized_copy(From, To, OldEnd);
901 return I;
902 }
903
904 void insert(iterator I, std::initializer_list<T> IL) {
905 insert(I, IL.begin(), IL.end());
906 }
907
908 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
909 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
910 return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);
911
912 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
913 this->set_size(this->size() + 1);
914 return this->back();
915 }
916
917 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
918
919 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
920
921 bool operator==(const SmallVectorImpl &RHS) const {
922 if (this->size() != RHS.size()) return false;
923 return std::equal(this->begin(), this->end(), RHS.begin());
924 }
925 bool operator!=(const SmallVectorImpl &RHS) const {
926 return !(*this == RHS);
927 }
928
929 bool operator<(const SmallVectorImpl &RHS) const {
930 return std::lexicographical_compare(this->begin(), this->end(),
931 RHS.begin(), RHS.end());
932 }
933};
934
935template <typename T>
936void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
937 if (this == &RHS) return;
938
939 // We can only avoid copying elements if neither vector is small.
940 if (!this->isSmall() && !RHS.isSmall()) {
941 std::swap(this->BeginX, RHS.BeginX);
942 std::swap(this->Size, RHS.Size);
943 std::swap(this->Capacity, RHS.Capacity);
944 return;
945 }
946 this->reserve(RHS.size());
947 RHS.reserve(this->size());
948
949 // Swap the shared elements.
950 size_t NumShared = this->size();
951 if (NumShared > RHS.size()) NumShared = RHS.size();
952 for (size_type i = 0; i != NumShared; ++i)
953 std::swap((*this)[i], RHS[i]);
954
955 // Copy over the extra elts.
956 if (this->size() > RHS.size()) {
957 size_t EltDiff = this->size() - RHS.size();
958 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
959 RHS.set_size(RHS.size() + EltDiff);
960 this->destroy_range(this->begin()+NumShared, this->end());
961 this->set_size(NumShared);
962 } else if (RHS.size() > this->size()) {
963 size_t EltDiff = RHS.size() - this->size();
964 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
965 this->set_size(this->size() + EltDiff);
966 this->destroy_range(RHS.begin()+NumShared, RHS.end());
967 RHS.set_size(NumShared);
968 }
969}
970
971template <typename T>
972SmallVectorImpl<T> &SmallVectorImpl<T>::
973 operator=(const SmallVectorImpl<T> &RHS) {
974 // Avoid self-assignment.
975 if (this == &RHS) return *this;
976
977 // If we already have sufficient space, assign the common elements, then
978 // destroy any excess.
979 size_t RHSSize = RHS.size();
980 size_t CurSize = this->size();
981 if (CurSize >= RHSSize) {
982 // Assign common elements.
983 iterator NewEnd;
984 if (RHSSize)
985 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
986 else
987 NewEnd = this->begin();
988
989 // Destroy excess elements.
990 this->destroy_range(NewEnd, this->end());
991
992 // Trim.
993 this->set_size(RHSSize);
994 return *this;
995 }
996
997 // If we have to grow to have enough elements, destroy the current elements.
998 // This allows us to avoid copying them during the grow.
999 // FIXME: don't do this if they're efficiently moveable.
1000 if (this->capacity() < RHSSize) {
1001 // Destroy current elements.
1002 this->clear();
1003 CurSize = 0;
1004 this->grow(RHSSize);
1005 } else if (CurSize) {
1006 // Otherwise, use assignment for the already-constructed elements.
1007 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
1008 }
1009
1010 // Copy construct the new elements in place.
1011 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
1012 this->begin()+CurSize);
1013
1014 // Set end.
1015 this->set_size(RHSSize);
1016 return *this;
1017}
1018
1019template <typename T>
1020SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
1021 // Avoid self-assignment.
1022 if (this == &RHS) return *this;
1023
1024 // If the RHS isn't small, clear this vector and then steal its buffer.
1025 if (!RHS.isSmall()) {
1026 this->destroy_range(this->begin(), this->end());
1027 if (!this->isSmall()) free(this->begin());
1028 this->BeginX = RHS.BeginX;
1029 this->Size = RHS.Size;
1030 this->Capacity = RHS.Capacity;
1031 RHS.resetToSmall();
1032 return *this;
1033 }
1034
1035 // If we already have sufficient space, assign the common elements, then
1036 // destroy any excess.
1037 size_t RHSSize = RHS.size();
1038 size_t CurSize = this->size();
1039 if (CurSize >= RHSSize) {
1040 // Assign common elements.
1041 iterator NewEnd = this->begin();
1042 if (RHSSize)
1043 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
1044
1045 // Destroy excess elements and trim the bounds.
1046 this->destroy_range(NewEnd, this->end());
1047 this->set_size(RHSSize);
1048
1049 // Clear the RHS.
1050 RHS.clear();
1051
1052 return *this;
1053 }
1054
1055 // If we have to grow to have enough elements, destroy the current elements.
1056 // This allows us to avoid copying them during the grow.
1057 // FIXME: this may not actually make any sense if we can efficiently move
1058 // elements.
1059 if (this->capacity() < RHSSize) {
1060 // Destroy current elements.
1061 this->clear();
1062 CurSize = 0;
1063 this->grow(RHSSize);
1064 } else if (CurSize) {
1065 // Otherwise, use assignment for the already-constructed elements.
1066 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
1067 }
1068
1069 // Move-construct the new elements in place.
1070 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
1071 this->begin()+CurSize);
1072
1073 // Set end.
1074 this->set_size(RHSSize);
1075
1076 RHS.clear();
1077 return *this;
1078}
1079
1080/// Storage for the SmallVector elements. This is specialized for the N=0 case
1081/// to avoid allocating unnecessary storage.
1082template <typename T, unsigned N>
1083struct SmallVectorStorage {
1084 alignas(T) char InlineElts[N * sizeof(T)];
1085};
1086
1087/// We need the storage to be properly aligned even for small-size of 0 so that
1088/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
1089/// well-defined.
1090template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
1091
1092/// Forward declaration of SmallVector so that
1093/// calculateSmallVectorDefaultInlinedElements can reference
1094/// `sizeof(SmallVector<T, 0>)`.
1095template <typename T, unsigned N> class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector;
1096
1097/// Helper class for calculating the default number of inline elements for
1098/// `SmallVector<T>`.
1099///
1100/// This should be migrated to a constexpr function when our minimum
1101/// compiler support is enough for multi-statement constexpr functions.
1102template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
1103 // Parameter controlling the default number of inlined elements
1104 // for `SmallVector<T>`.
1105 //
1106 // The default number of inlined elements ensures that
1107 // 1. There is at least one inlined element.
1108 // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
1109 // it contradicts 1.
1110 static constexpr size_t kPreferredSmallVectorSizeof = 64;
1111
1112 // static_assert that sizeof(T) is not "too big".
1113 //
1114 // Because our policy guarantees at least one inlined element, it is possible
1115 // for an arbitrarily large inlined element to allocate an arbitrarily large
1116 // amount of inline storage. We generally consider it an antipattern for a
1117 // SmallVector to allocate an excessive amount of inline storage, so we want
1118 // to call attention to these cases and make sure that users are making an
1119 // intentional decision if they request a lot of inline storage.
1120 //
1121 // We want this assertion to trigger in pathological cases, but otherwise
1122 // not be too easy to hit. To accomplish that, the cutoff is actually somewhat
1123 // larger than kPreferredSmallVectorSizeof (otherwise,
1124 // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
1125 // pattern seems useful in practice).
1126 //
1127 // One wrinkle is that this assertion is in theory non-portable, since
1128 // sizeof(T) is in general platform-dependent. However, we don't expect this
1129 // to be much of an issue, because most LLVM development happens on 64-bit
1130 // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
1131 // 32-bit hosts, dodging the issue. The reverse situation, where development
1132 // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
1133 // 64-bit host, is expected to be very rare.
1134 static_assert(
1135 sizeof(T) <= 256,
1136 "You are trying to use a default number of inlined elements for "
1137 "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
1138 "explicit number of inlined elements with `SmallVector<T, N>` to make "
1139 "sure you really want that much inline storage.");
1140
1141 // Discount the size of the header itself when calculating the maximum inline
1142 // bytes.
1143 static constexpr size_t PreferredInlineBytes =
1144 kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
1145 static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
1146 static constexpr size_t value =
1147 NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1148};
1149
1150/// This is a 'vector' (really, a variable-sized array), optimized
1151/// for the case when the array is small. It contains some number of elements
1152/// in-place, which allows it to avoid heap allocation when the actual number of
1153/// elements is below that threshold. This allows normal "small" cases to be
1154/// fast without losing generality for large inputs.
1155///
1156/// \note
1157/// In the absence of a well-motivated choice for the number of inlined
1158/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
1159/// omitting the \p N). This will choose a default number of inlined elements
1160/// reasonable for allocation on the stack (for example, trying to keep \c
1161/// sizeof(SmallVector<T>) around 64 bytes).
1162///
1163/// \warning This does not attempt to be exception safe.
1164///
1165/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
1166template <typename T,
1167 unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
1168class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>,
1169 SmallVectorStorage<T, N> {
1170public:
1171 SmallVector() : SmallVectorImpl<T>(N) {}
1172
1173 ~SmallVector() {
1174 // Destroy the constructed elements in the vector.
1175 this->destroy_range(this->begin(), this->end());
1176 }
1177
1178 explicit SmallVector(size_t Size, const T &Value = T())
1179 : SmallVectorImpl<T>(N) {
1180 this->assign(Size, Value);
1181 }
1182
1183 template <typename ItTy,
1184 typename = std::enable_if_t<std::is_convertible<
1185 typename std::iterator_traits<ItTy>::iterator_category,
1186 std::input_iterator_tag>::value>>
1187 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
1188 this->append(S, E);
1189 }
1190
1191 template <typename RangeTy>
1192 explicit SmallVector(const iterator_range<RangeTy> &R)
1193 : SmallVectorImpl<T>(N) {
1194 this->append(R.begin(), R.end());
1195 }
1196
1197 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
1198 this->assign(IL);
1199 }
1200
1201 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
1202 if (!RHS.empty())
1203 SmallVectorImpl<T>::operator=(RHS);
1204 }
1205
1206 SmallVector &operator=(const SmallVector &RHS) {
1207 SmallVectorImpl<T>::operator=(RHS);
1208 return *this;
1209 }
1210
1211 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
1212 if (!RHS.empty())
1213 SmallVectorImpl<T>::operator=(::std::move(RHS));
1214 }
1215
1216 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
1217 if (!RHS.empty())
1218 SmallVectorImpl<T>::operator=(::std::move(RHS));
1219 }
1220
1221 SmallVector &operator=(SmallVector &&RHS) {
1222 SmallVectorImpl<T>::operator=(::std::move(RHS));
1223 return *this;
1224 }
1225
1226 SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
1227 SmallVectorImpl<T>::operator=(::std::move(RHS));
1228 return *this;
1229 }
1230
1231 SmallVector &operator=(std::initializer_list<T> IL) {
1232 this->assign(IL);
1233 return *this;
1234 }
1235};
1236
1237template <typename T, unsigned N>
1238inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1239 return X.capacity_in_bytes();
1240}
1241
1242/// Given a range of type R, iterate the entire range and return a
1243/// SmallVector with elements of the vector. This is useful, for example,
1244/// when you want to iterate a range and then sort the results.
1245template <unsigned Size, typename R>
1246SmallVector<typename std::remove_const<typename std::remove_reference<
1247 decltype(*std::begin(std::declval<R &>()))>::type>::type,
1248 Size>
1249to_vector(R &&Range) {
1250 return {std::begin(Range), std::end(Range)};
1251}
1252
1253} // end namespace llvm
1254
1255namespace std {
1256
1257 /// Implement std::swap in terms of SmallVector swap.
1258 template<typename T>
1259 inline void
1260 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
1261 LHS.swap(RHS);
1262 }
1263
1264 /// Implement std::swap in terms of SmallVector swap.
1265 template<typename T, unsigned N>
1266 inline void
1267 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
1268 LHS.swap(RHS);
1269 }
1270
1271} // end namespace std
1272
1273#endif // LLVM_ADT_SMALLVECTOR_H