Bug Summary

File:lib/Transforms/Instrumentation/ControlHeightReduction.cpp
Warning:line 926, column 42
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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