Bug Summary

File:llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
Warning:line 961, 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 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20201217111122+722247c8124/build-llvm/lib/Transforms/Instrumentation -I /build/llvm-toolchain-snapshot-12~++20201217111122+722247c8124/llvm/lib/Transforms/Instrumentation -I /build/llvm-toolchain-snapshot-12~++20201217111122+722247c8124/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20201217111122+722247c8124/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/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/local/include -internal-isystem /usr/lib/llvm-12/lib/clang/12.0.0/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-12~++20201217111122+722247c8124/build-llvm/lib/Transforms/Instrumentation -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20201217111122+722247c8124=. -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 -o /tmp/scan-build-2020-12-17-211521-24385-1 -x c++ /build/llvm-toolchain-snapshot-12~++20201217111122+722247c8124/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp

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

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