Bug Summary

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