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