File: | lib/Transforms/Instrumentation/ControlHeightReduction.cpp |
Warning: | line 1064, column 3 Forming reference to null pointer |
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/Support/BranchProbability.h" | |||
31 | #include "llvm/Support/MemoryBuffer.h" | |||
32 | #include "llvm/Transforms/Utils.h" | |||
33 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
34 | #include "llvm/Transforms/Utils/Cloning.h" | |||
35 | #include "llvm/Transforms/Utils/ValueMapper.h" | |||
36 | ||||
37 | #include <set> | |||
38 | #include <sstream> | |||
39 | ||||
40 | using namespace llvm; | |||
41 | ||||
42 | #define DEBUG_TYPE"chr" "chr" | |||
43 | ||||
44 | #define CHR_DEBUG(X)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { X; } } while (false) LLVM_DEBUG(X)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { X; } } while (false) | |||
45 | ||||
46 | static cl::opt<bool> ForceCHR("force-chr", cl::init(false), cl::Hidden, | |||
47 | cl::desc("Apply CHR for all functions")); | |||
48 | ||||
49 | static cl::opt<double> CHRBiasThreshold( | |||
50 | "chr-bias-threshold", cl::init(0.99), cl::Hidden, | |||
51 | cl::desc("CHR considers a branch bias greater than this ratio as biased")); | |||
52 | ||||
53 | static cl::opt<unsigned> CHRMergeThreshold( | |||
54 | "chr-merge-threshold", cl::init(2), cl::Hidden, | |||
55 | cl::desc("CHR merges a group of N branches/selects where N >= this value")); | |||
56 | ||||
57 | static cl::opt<std::string> CHRModuleList( | |||
58 | "chr-module-list", cl::init(""), cl::Hidden, | |||
59 | cl::desc("Specify file to retrieve the list of modules to apply CHR to")); | |||
60 | ||||
61 | static cl::opt<std::string> CHRFunctionList( | |||
62 | "chr-function-list", cl::init(""), cl::Hidden, | |||
63 | cl::desc("Specify file to retrieve the list of functions to apply CHR to")); | |||
64 | ||||
65 | static StringSet<> CHRModules; | |||
66 | static StringSet<> CHRFunctions; | |||
67 | ||||
68 | static void parseCHRFilterFiles() { | |||
69 | if (!CHRModuleList.empty()) { | |||
70 | auto FileOrErr = MemoryBuffer::getFile(CHRModuleList); | |||
71 | if (!FileOrErr) { | |||
72 | errs() << "Error: Couldn't read the chr-module-list file " << CHRModuleList << "\n"; | |||
73 | std::exit(1); | |||
74 | } | |||
75 | StringRef Buf = FileOrErr->get()->getBuffer(); | |||
76 | SmallVector<StringRef, 0> Lines; | |||
77 | Buf.split(Lines, '\n'); | |||
78 | for (StringRef Line : Lines) { | |||
79 | Line = Line.trim(); | |||
80 | if (!Line.empty()) | |||
81 | CHRModules.insert(Line); | |||
82 | } | |||
83 | } | |||
84 | if (!CHRFunctionList.empty()) { | |||
85 | auto FileOrErr = MemoryBuffer::getFile(CHRFunctionList); | |||
86 | if (!FileOrErr) { | |||
87 | errs() << "Error: Couldn't read the chr-function-list file " << CHRFunctionList << "\n"; | |||
88 | std::exit(1); | |||
89 | } | |||
90 | StringRef Buf = FileOrErr->get()->getBuffer(); | |||
91 | SmallVector<StringRef, 0> Lines; | |||
92 | Buf.split(Lines, '\n'); | |||
93 | for (StringRef Line : Lines) { | |||
94 | Line = Line.trim(); | |||
95 | if (!Line.empty()) | |||
96 | CHRFunctions.insert(Line); | |||
97 | } | |||
98 | } | |||
99 | } | |||
100 | ||||
101 | namespace { | |||
102 | class ControlHeightReductionLegacyPass : public FunctionPass { | |||
103 | public: | |||
104 | static char ID; | |||
105 | ||||
106 | ControlHeightReductionLegacyPass() : FunctionPass(ID) { | |||
107 | initializeControlHeightReductionLegacyPassPass( | |||
108 | *PassRegistry::getPassRegistry()); | |||
109 | parseCHRFilterFiles(); | |||
110 | } | |||
111 | ||||
112 | bool runOnFunction(Function &F) override; | |||
113 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
114 | AU.addRequired<BlockFrequencyInfoWrapperPass>(); | |||
115 | AU.addRequired<DominatorTreeWrapperPass>(); | |||
116 | AU.addRequired<ProfileSummaryInfoWrapperPass>(); | |||
117 | AU.addRequired<RegionInfoPass>(); | |||
118 | AU.addPreserved<GlobalsAAWrapperPass>(); | |||
119 | } | |||
120 | }; | |||
121 | } // end anonymous namespace | |||
122 | ||||
123 | char ControlHeightReductionLegacyPass::ID = 0; | |||
124 | ||||
125 | INITIALIZE_PASS_BEGIN(ControlHeightReductionLegacyPass,static void *initializeControlHeightReductionLegacyPassPassOnce (PassRegistry &Registry) { | |||
126 | "chr",static void *initializeControlHeightReductionLegacyPassPassOnce (PassRegistry &Registry) { | |||
127 | "Reduce control height in the hot paths",static void *initializeControlHeightReductionLegacyPassPassOnce (PassRegistry &Registry) { | |||
128 | false, false)static void *initializeControlHeightReductionLegacyPassPassOnce (PassRegistry &Registry) { | |||
129 | INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)initializeBlockFrequencyInfoWrapperPassPass(Registry); | |||
130 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
131 | INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)initializeProfileSummaryInfoWrapperPassPass(Registry); | |||
132 | INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)initializeRegionInfoPassPass(Registry); | |||
133 | 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)); } | |||
134 | "chr",PassInfo *PI = new PassInfo( "Reduce control height in the hot paths" , "chr", &ControlHeightReductionLegacyPass::ID, PassInfo:: NormalCtor_t(callDefaultCtor<ControlHeightReductionLegacyPass >), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeControlHeightReductionLegacyPassPassFlag ; void llvm::initializeControlHeightReductionLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeControlHeightReductionLegacyPassPassFlag , initializeControlHeightReductionLegacyPassPassOnce, std::ref (Registry)); } | |||
135 | "Reduce control height in the hot paths",PassInfo *PI = new PassInfo( "Reduce control height in the hot paths" , "chr", &ControlHeightReductionLegacyPass::ID, PassInfo:: NormalCtor_t(callDefaultCtor<ControlHeightReductionLegacyPass >), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeControlHeightReductionLegacyPassPassFlag ; void llvm::initializeControlHeightReductionLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeControlHeightReductionLegacyPassPassFlag , initializeControlHeightReductionLegacyPassPassOnce, std::ref (Registry)); } | |||
136 | false, false)PassInfo *PI = new PassInfo( "Reduce control height in the hot paths" , "chr", &ControlHeightReductionLegacyPass::ID, PassInfo:: NormalCtor_t(callDefaultCtor<ControlHeightReductionLegacyPass >), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeControlHeightReductionLegacyPassPassFlag ; void llvm::initializeControlHeightReductionLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeControlHeightReductionLegacyPassPassFlag , initializeControlHeightReductionLegacyPassPassOnce, std::ref (Registry)); } | |||
137 | ||||
138 | FunctionPass *llvm::createControlHeightReductionLegacyPass() { | |||
139 | return new ControlHeightReductionLegacyPass(); | |||
140 | } | |||
141 | ||||
142 | namespace { | |||
143 | ||||
144 | struct CHRStats { | |||
145 | CHRStats() : NumBranches(0), NumBranchesDelta(0), | |||
146 | WeightedNumBranchesDelta(0) {} | |||
147 | void print(raw_ostream &OS) const { | |||
148 | OS << "CHRStats: NumBranches " << NumBranches | |||
149 | << " NumBranchesDelta " << NumBranchesDelta | |||
150 | << " WeightedNumBranchesDelta " << WeightedNumBranchesDelta; | |||
151 | } | |||
152 | uint64_t NumBranches; // The original number of conditional branches / | |||
153 | // selects | |||
154 | uint64_t NumBranchesDelta; // The decrease of the number of conditional | |||
155 | // branches / selects in the hot paths due to CHR. | |||
156 | uint64_t WeightedNumBranchesDelta; // NumBranchesDelta weighted by the profile | |||
157 | // count at the scope entry. | |||
158 | }; | |||
159 | ||||
160 | // RegInfo - some properties of a Region. | |||
161 | struct RegInfo { | |||
162 | RegInfo() : R(nullptr), HasBranch(false) {} | |||
163 | RegInfo(Region *RegionIn) : R(RegionIn), HasBranch(false) {} | |||
164 | Region *R; | |||
165 | bool HasBranch; | |||
166 | SmallVector<SelectInst *, 8> Selects; | |||
167 | }; | |||
168 | ||||
169 | typedef DenseMap<Region *, DenseSet<Instruction *>> HoistStopMapTy; | |||
170 | ||||
171 | // CHRScope - a sequence of regions to CHR together. It corresponds to a | |||
172 | // sequence of conditional blocks. It can have subscopes which correspond to | |||
173 | // nested conditional blocks. Nested CHRScopes form a tree. | |||
174 | class CHRScope { | |||
175 | public: | |||
176 | CHRScope(RegInfo RI) : BranchInsertPoint(nullptr) { | |||
177 | assert(RI.R && "Null RegionIn")((RI.R && "Null RegionIn") ? static_cast<void> ( 0) : __assert_fail ("RI.R && \"Null RegionIn\"", "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 177, __PRETTY_FUNCTION__)); | |||
178 | RegInfos.push_back(RI); | |||
179 | } | |||
180 | ||||
181 | Region *getParentRegion() { | |||
182 | assert(RegInfos.size() > 0 && "Empty CHRScope")((RegInfos.size() > 0 && "Empty CHRScope") ? static_cast <void> (0) : __assert_fail ("RegInfos.size() > 0 && \"Empty CHRScope\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 182, __PRETTY_FUNCTION__)); | |||
183 | Region *Parent = RegInfos[0].R->getParent(); | |||
184 | assert(Parent && "Unexpected to call this on the top-level region")((Parent && "Unexpected to call this on the top-level region" ) ? static_cast<void> (0) : __assert_fail ("Parent && \"Unexpected to call this on the top-level region\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 184, __PRETTY_FUNCTION__)); | |||
185 | return Parent; | |||
186 | } | |||
187 | ||||
188 | BasicBlock *getEntryBlock() { | |||
189 | assert(RegInfos.size() > 0 && "Empty CHRScope")((RegInfos.size() > 0 && "Empty CHRScope") ? static_cast <void> (0) : __assert_fail ("RegInfos.size() > 0 && \"Empty CHRScope\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 189, __PRETTY_FUNCTION__)); | |||
190 | return RegInfos.front().R->getEntry(); | |||
191 | } | |||
192 | ||||
193 | BasicBlock *getExitBlock() { | |||
194 | assert(RegInfos.size() > 0 && "Empty CHRScope")((RegInfos.size() > 0 && "Empty CHRScope") ? static_cast <void> (0) : __assert_fail ("RegInfos.size() > 0 && \"Empty CHRScope\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 194, __PRETTY_FUNCTION__)); | |||
195 | return RegInfos.back().R->getExit(); | |||
196 | } | |||
197 | ||||
198 | bool appendable(CHRScope *Next) { | |||
199 | // The next scope is appendable only if this scope is directly connected to | |||
200 | // it (which implies it post-dominates this scope) and this scope dominates | |||
201 | // it (no edge to the next scope outside this scope). | |||
202 | BasicBlock *NextEntry = Next->getEntryBlock(); | |||
203 | if (getExitBlock() != NextEntry) | |||
204 | // Not directly connected. | |||
205 | return false; | |||
206 | Region *LastRegion = RegInfos.back().R; | |||
207 | for (BasicBlock *Pred : predecessors(NextEntry)) | |||
208 | if (!LastRegion->contains(Pred)) | |||
209 | // There's an edge going into the entry of the next scope from outside | |||
210 | // of this scope. | |||
211 | return false; | |||
212 | return true; | |||
213 | } | |||
214 | ||||
215 | void append(CHRScope *Next) { | |||
216 | assert(RegInfos.size() > 0 && "Empty CHRScope")((RegInfos.size() > 0 && "Empty CHRScope") ? static_cast <void> (0) : __assert_fail ("RegInfos.size() > 0 && \"Empty CHRScope\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 216, __PRETTY_FUNCTION__)); | |||
217 | assert(Next->RegInfos.size() > 0 && "Empty CHRScope")((Next->RegInfos.size() > 0 && "Empty CHRScope" ) ? static_cast<void> (0) : __assert_fail ("Next->RegInfos.size() > 0 && \"Empty CHRScope\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 217, __PRETTY_FUNCTION__)); | |||
218 | assert(getParentRegion() == Next->getParentRegion() &&((getParentRegion() == Next->getParentRegion() && "Must be siblings" ) ? static_cast<void> (0) : __assert_fail ("getParentRegion() == Next->getParentRegion() && \"Must be siblings\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 219, __PRETTY_FUNCTION__)) | |||
219 | "Must be siblings")((getParentRegion() == Next->getParentRegion() && "Must be siblings" ) ? static_cast<void> (0) : __assert_fail ("getParentRegion() == Next->getParentRegion() && \"Must be siblings\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 219, __PRETTY_FUNCTION__)); | |||
220 | assert(getExitBlock() == Next->getEntryBlock() &&((getExitBlock() == Next->getEntryBlock() && "Must be adjacent" ) ? static_cast<void> (0) : __assert_fail ("getExitBlock() == Next->getEntryBlock() && \"Must be adjacent\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 221, __PRETTY_FUNCTION__)) | |||
221 | "Must be adjacent")((getExitBlock() == Next->getEntryBlock() && "Must be adjacent" ) ? static_cast<void> (0) : __assert_fail ("getExitBlock() == Next->getEntryBlock() && \"Must be adjacent\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 221, __PRETTY_FUNCTION__)); | |||
222 | for (RegInfo &RI : Next->RegInfos) | |||
223 | RegInfos.push_back(RI); | |||
224 | for (CHRScope *Sub : Next->Subs) | |||
225 | Subs.push_back(Sub); | |||
226 | } | |||
227 | ||||
228 | void addSub(CHRScope *SubIn) { | |||
229 | #ifndef NDEBUG | |||
230 | bool IsChild = false; | |||
231 | for (RegInfo &RI : RegInfos) | |||
232 | if (RI.R == SubIn->getParentRegion()) { | |||
233 | IsChild = true; | |||
234 | break; | |||
235 | } | |||
236 | assert(IsChild && "Must be a child")((IsChild && "Must be a child") ? static_cast<void > (0) : __assert_fail ("IsChild && \"Must be a child\"" , "/build/llvm-toolchain-snapshot-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 246, __PRETTY_FUNCTION__)); | |||
247 | auto BoundaryIt = std::find_if(RegInfos.begin(), RegInfos.end(), | |||
248 | [&Boundary](const RegInfo& RI) { | |||
249 | return Boundary == RI.R; | |||
250 | }); | |||
251 | if (BoundaryIt == RegInfos.end()) | |||
252 | return nullptr; | |||
253 | SmallVector<RegInfo, 8> TailRegInfos; | |||
254 | SmallVector<CHRScope *, 8> TailSubs; | |||
255 | TailRegInfos.insert(TailRegInfos.begin(), BoundaryIt, RegInfos.end()); | |||
256 | RegInfos.resize(BoundaryIt - RegInfos.begin()); | |||
257 | DenseSet<Region *> TailRegionSet; | |||
258 | for (RegInfo &RI : TailRegInfos) | |||
259 | TailRegionSet.insert(RI.R); | |||
260 | for (auto It = Subs.begin(); It != Subs.end(); ) { | |||
261 | CHRScope *Sub = *It; | |||
262 | assert(Sub && "null Sub")((Sub && "null Sub") ? static_cast<void> (0) : __assert_fail ("Sub && \"null Sub\"", "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 262, __PRETTY_FUNCTION__)); | |||
263 | Region *Parent = Sub->getParentRegion(); | |||
264 | if (TailRegionSet.count(Parent)) { | |||
265 | TailSubs.push_back(Sub); | |||
266 | It = Subs.erase(It); | |||
267 | } else { | |||
268 | assert(std::find_if(RegInfos.begin(), RegInfos.end(),((std::find_if(RegInfos.begin(), RegInfos.end(), [&Parent ](const RegInfo& RI) { return Parent == RI.R; }) != RegInfos .end() && "Must be in head") ? static_cast<void> (0) : __assert_fail ("std::find_if(RegInfos.begin(), RegInfos.end(), [&Parent](const RegInfo& RI) { return Parent == RI.R; }) != RegInfos.end() && \"Must be in head\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 272, __PRETTY_FUNCTION__)) | |||
269 | [&Parent](const RegInfo& RI) {((std::find_if(RegInfos.begin(), RegInfos.end(), [&Parent ](const RegInfo& RI) { return Parent == RI.R; }) != RegInfos .end() && "Must be in head") ? static_cast<void> (0) : __assert_fail ("std::find_if(RegInfos.begin(), RegInfos.end(), [&Parent](const RegInfo& RI) { return Parent == RI.R; }) != RegInfos.end() && \"Must be in head\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 272, __PRETTY_FUNCTION__)) | |||
270 | return Parent == RI.R;((std::find_if(RegInfos.begin(), RegInfos.end(), [&Parent ](const RegInfo& RI) { return Parent == RI.R; }) != RegInfos .end() && "Must be in head") ? static_cast<void> (0) : __assert_fail ("std::find_if(RegInfos.begin(), RegInfos.end(), [&Parent](const RegInfo& RI) { return Parent == RI.R; }) != RegInfos.end() && \"Must be in head\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 272, __PRETTY_FUNCTION__)) | |||
271 | }) != RegInfos.end() &&((std::find_if(RegInfos.begin(), RegInfos.end(), [&Parent ](const RegInfo& RI) { return Parent == RI.R; }) != RegInfos .end() && "Must be in head") ? static_cast<void> (0) : __assert_fail ("std::find_if(RegInfos.begin(), RegInfos.end(), [&Parent](const RegInfo& RI) { return Parent == RI.R; }) != RegInfos.end() && \"Must be in head\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 272, __PRETTY_FUNCTION__)) | |||
272 | "Must be in head")((std::find_if(RegInfos.begin(), RegInfos.end(), [&Parent ](const RegInfo& RI) { return Parent == RI.R; }) != RegInfos .end() && "Must be in head") ? static_cast<void> (0) : __assert_fail ("std::find_if(RegInfos.begin(), RegInfos.end(), [&Parent](const RegInfo& RI) { return Parent == RI.R; }) != RegInfos.end() && \"Must be in head\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 272, __PRETTY_FUNCTION__)); | |||
273 | ++It; | |||
274 | } | |||
275 | } | |||
276 | assert(HoistStopMap.empty() && "MapHoistStops must be empty")((HoistStopMap.empty() && "MapHoistStops must be empty" ) ? static_cast<void> (0) : __assert_fail ("HoistStopMap.empty() && \"MapHoistStops must be empty\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 276, __PRETTY_FUNCTION__)); | |||
277 | return new CHRScope(TailRegInfos, TailSubs); | |||
278 | } | |||
279 | ||||
280 | bool contains(Instruction *I) const { | |||
281 | BasicBlock *Parent = I->getParent(); | |||
282 | for (const RegInfo &RI : RegInfos) | |||
283 | if (RI.R->contains(Parent)) | |||
284 | return true; | |||
285 | return false; | |||
286 | } | |||
287 | ||||
288 | void print(raw_ostream &OS) const; | |||
289 | ||||
290 | SmallVector<RegInfo, 8> RegInfos; // Regions that belong to this scope | |||
291 | SmallVector<CHRScope *, 8> Subs; // Subscopes. | |||
292 | ||||
293 | // The instruction at which to insert the CHR conditional branch (and hoist | |||
294 | // the dependent condition values). | |||
295 | Instruction *BranchInsertPoint; | |||
296 | ||||
297 | // True-biased and false-biased regions (conditional blocks), | |||
298 | // respectively. Used only for the outermost scope and includes regions in | |||
299 | // subscopes. The rest are unbiased. | |||
300 | DenseSet<Region *> TrueBiasedRegions; | |||
301 | DenseSet<Region *> FalseBiasedRegions; | |||
302 | // Among the biased regions, the regions that get CHRed. | |||
303 | SmallVector<RegInfo, 8> CHRRegions; | |||
304 | ||||
305 | // True-biased and false-biased selects, respectively. Used only for the | |||
306 | // outermost scope and includes ones in subscopes. | |||
307 | DenseSet<SelectInst *> TrueBiasedSelects; | |||
308 | DenseSet<SelectInst *> FalseBiasedSelects; | |||
309 | ||||
310 | // Map from one of the above regions to the instructions to stop | |||
311 | // hoisting instructions at through use-def chains. | |||
312 | HoistStopMapTy HoistStopMap; | |||
313 | ||||
314 | private: | |||
315 | CHRScope(SmallVector<RegInfo, 8> &RegInfosIn, | |||
316 | SmallVector<CHRScope *, 8> &SubsIn) | |||
317 | : RegInfos(RegInfosIn), Subs(SubsIn), BranchInsertPoint(nullptr) {} | |||
318 | }; | |||
319 | ||||
320 | class CHR { | |||
321 | public: | |||
322 | CHR(Function &Fin, BlockFrequencyInfo &BFIin, DominatorTree &DTin, | |||
323 | ProfileSummaryInfo &PSIin, RegionInfo &RIin, | |||
324 | OptimizationRemarkEmitter &OREin) | |||
325 | : F(Fin), BFI(BFIin), DT(DTin), PSI(PSIin), RI(RIin), ORE(OREin) {} | |||
326 | ||||
327 | ~CHR() { | |||
328 | for (CHRScope *Scope : Scopes) { | |||
329 | delete Scope; | |||
330 | } | |||
331 | } | |||
332 | ||||
333 | bool run(); | |||
334 | ||||
335 | private: | |||
336 | // See the comments in CHR::run() for the high level flow of the algorithm and | |||
337 | // what the following functions do. | |||
338 | ||||
339 | void findScopes(SmallVectorImpl<CHRScope *> &Output) { | |||
340 | Region *R = RI.getTopLevelRegion(); | |||
341 | CHRScope *Scope = findScopes(R, nullptr, nullptr, Output); | |||
342 | if (Scope) { | |||
343 | Output.push_back(Scope); | |||
344 | } | |||
345 | } | |||
346 | CHRScope *findScopes(Region *R, Region *NextRegion, Region *ParentRegion, | |||
347 | SmallVectorImpl<CHRScope *> &Scopes); | |||
348 | CHRScope *findScope(Region *R); | |||
349 | void checkScopeHoistable(CHRScope *Scope); | |||
350 | ||||
351 | void splitScopes(SmallVectorImpl<CHRScope *> &Input, | |||
352 | SmallVectorImpl<CHRScope *> &Output); | |||
353 | SmallVector<CHRScope *, 8> splitScope(CHRScope *Scope, | |||
354 | CHRScope *Outer, | |||
355 | DenseSet<Value *> *OuterConditionValues, | |||
356 | Instruction *OuterInsertPoint, | |||
357 | SmallVectorImpl<CHRScope *> &Output, | |||
358 | DenseSet<Instruction *> &Unhoistables); | |||
359 | ||||
360 | void classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes); | |||
361 | void classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope); | |||
362 | ||||
363 | void filterScopes(SmallVectorImpl<CHRScope *> &Input, | |||
364 | SmallVectorImpl<CHRScope *> &Output); | |||
365 | ||||
366 | void setCHRRegions(SmallVectorImpl<CHRScope *> &Input, | |||
367 | SmallVectorImpl<CHRScope *> &Output); | |||
368 | void setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope); | |||
369 | ||||
370 | void sortScopes(SmallVectorImpl<CHRScope *> &Input, | |||
371 | SmallVectorImpl<CHRScope *> &Output); | |||
372 | ||||
373 | void transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes); | |||
374 | void transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs); | |||
375 | void cloneScopeBlocks(CHRScope *Scope, | |||
376 | BasicBlock *PreEntryBlock, | |||
377 | BasicBlock *ExitBlock, | |||
378 | Region *LastRegion, | |||
379 | ValueToValueMapTy &VMap); | |||
380 | BranchInst *createMergedBranch(BasicBlock *PreEntryBlock, | |||
381 | BasicBlock *EntryBlock, | |||
382 | BasicBlock *NewEntryBlock, | |||
383 | ValueToValueMapTy &VMap); | |||
384 | void fixupBranchesAndSelects(CHRScope *Scope, | |||
385 | BasicBlock *PreEntryBlock, | |||
386 | BranchInst *MergedBR, | |||
387 | uint64_t ProfileCount); | |||
388 | void fixupBranch(Region *R, | |||
389 | CHRScope *Scope, | |||
390 | IRBuilder<> &IRB, | |||
391 | Value *&MergedCondition, BranchProbability &CHRBranchBias); | |||
392 | void fixupSelect(SelectInst* SI, | |||
393 | CHRScope *Scope, | |||
394 | IRBuilder<> &IRB, | |||
395 | Value *&MergedCondition, BranchProbability &CHRBranchBias); | |||
396 | void addToMergedCondition(bool IsTrueBiased, Value *Cond, | |||
397 | Instruction *BranchOrSelect, | |||
398 | CHRScope *Scope, | |||
399 | IRBuilder<> &IRB, | |||
400 | Value *&MergedCondition); | |||
401 | ||||
402 | Function &F; | |||
403 | BlockFrequencyInfo &BFI; | |||
404 | DominatorTree &DT; | |||
405 | ProfileSummaryInfo &PSI; | |||
406 | RegionInfo &RI; | |||
407 | OptimizationRemarkEmitter &ORE; | |||
408 | CHRStats Stats; | |||
409 | ||||
410 | // All the true-biased regions in the function | |||
411 | DenseSet<Region *> TrueBiasedRegionsGlobal; | |||
412 | // All the false-biased regions in the function | |||
413 | DenseSet<Region *> FalseBiasedRegionsGlobal; | |||
414 | // All the true-biased selects in the function | |||
415 | DenseSet<SelectInst *> TrueBiasedSelectsGlobal; | |||
416 | // All the false-biased selects in the function | |||
417 | DenseSet<SelectInst *> FalseBiasedSelectsGlobal; | |||
418 | // A map from biased regions to their branch bias | |||
419 | DenseMap<Region *, BranchProbability> BranchBiasMap; | |||
420 | // A map from biased selects to their branch bias | |||
421 | DenseMap<SelectInst *, BranchProbability> SelectBiasMap; | |||
422 | // All the scopes. | |||
423 | DenseSet<CHRScope *> Scopes; | |||
424 | }; | |||
425 | ||||
426 | } // end anonymous namespace | |||
427 | ||||
428 | static inline | |||
429 | raw_ostream LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) &operator<<(raw_ostream &OS, | |||
430 | const CHRStats &Stats) { | |||
431 | Stats.print(OS); | |||
432 | return OS; | |||
433 | } | |||
434 | ||||
435 | static inline | |||
436 | raw_ostream &operator<<(raw_ostream &OS, const CHRScope &Scope) { | |||
437 | Scope.print(OS); | |||
438 | return OS; | |||
439 | } | |||
440 | ||||
441 | static bool shouldApply(Function &F, ProfileSummaryInfo& PSI) { | |||
442 | if (ForceCHR) | |||
443 | return true; | |||
444 | ||||
445 | if (!CHRModuleList.empty() || !CHRFunctionList.empty()) { | |||
446 | if (CHRModules.count(F.getParent()->getName())) | |||
447 | return true; | |||
448 | return CHRFunctions.count(F.getName()); | |||
449 | } | |||
450 | ||||
451 | assert(PSI.hasProfileSummary() && "Empty PSI?")((PSI.hasProfileSummary() && "Empty PSI?") ? static_cast <void> (0) : __assert_fail ("PSI.hasProfileSummary() && \"Empty PSI?\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 451, __PRETTY_FUNCTION__)); | |||
452 | return PSI.isFunctionEntryHot(&F); | |||
453 | } | |||
454 | ||||
455 | static void LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) dumpIR(Function &F, const char *Label, | |||
456 | CHRStats *Stats) { | |||
457 | StringRef FuncName = F.getName(); | |||
458 | StringRef ModuleName = F.getParent()->getName(); | |||
459 | (void)(FuncName); // Unused in release build. | |||
460 | (void)(ModuleName); // Unused in release build. | |||
461 | CHR_DEBUG(dbgs() << "CHR IR dump " << Label << " " << ModuleName << " "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "CHR IR dump " << Label << " " << ModuleName << " " << FuncName; } } while (false) | |||
462 | << FuncName)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "CHR IR dump " << Label << " " << ModuleName << " " << FuncName; } } while (false); | |||
463 | if (Stats) | |||
464 | CHR_DEBUG(dbgs() << " " << *Stats)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << " " << *Stats; } } while (false ); | |||
465 | CHR_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "\n"; } } while (false); | |||
466 | CHR_DEBUG(F.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { F.dump(); } } while (false); | |||
467 | } | |||
468 | ||||
469 | void CHRScope::print(raw_ostream &OS) const { | |||
470 | assert(RegInfos.size() > 0 && "Empty CHRScope")((RegInfos.size() > 0 && "Empty CHRScope") ? static_cast <void> (0) : __assert_fail ("RegInfos.size() > 0 && \"Empty CHRScope\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 470, __PRETTY_FUNCTION__)); | |||
471 | OS << "CHRScope["; | |||
472 | OS << RegInfos.size() << ", Regions["; | |||
473 | for (const RegInfo &RI : RegInfos) { | |||
474 | OS << RI.R->getNameStr(); | |||
475 | if (RI.HasBranch) | |||
476 | OS << " B"; | |||
477 | if (RI.Selects.size() > 0) | |||
478 | OS << " S" << RI.Selects.size(); | |||
479 | OS << ", "; | |||
480 | } | |||
481 | if (RegInfos[0].R->getParent()) { | |||
482 | OS << "], Parent " << RegInfos[0].R->getParent()->getNameStr(); | |||
483 | } else { | |||
484 | // top level region | |||
485 | OS << "]"; | |||
486 | } | |||
487 | OS << ", Subs["; | |||
488 | for (CHRScope *Sub : Subs) { | |||
489 | OS << *Sub << ", "; | |||
490 | } | |||
491 | OS << "]]"; | |||
492 | } | |||
493 | ||||
494 | // Return true if the given instruction type can be hoisted by CHR. | |||
495 | static bool isHoistableInstructionType(Instruction *I) { | |||
496 | return isa<BinaryOperator>(I) || isa<CastInst>(I) || isa<SelectInst>(I) || | |||
497 | isa<GetElementPtrInst>(I) || isa<CmpInst>(I) || | |||
498 | isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) || | |||
499 | isa<ShuffleVectorInst>(I) || isa<ExtractValueInst>(I) || | |||
500 | isa<InsertValueInst>(I); | |||
501 | } | |||
502 | ||||
503 | // Return true if the given instruction can be hoisted by CHR. | |||
504 | static bool isHoistable(Instruction *I, DominatorTree &DT) { | |||
505 | if (!isHoistableInstructionType(I)) | |||
506 | return false; | |||
507 | return isSafeToSpeculativelyExecute(I, nullptr, &DT); | |||
508 | } | |||
509 | ||||
510 | // Recursively traverse the use-def chains of the given value and return a set | |||
511 | // of the unhoistable base values defined within the scope (excluding the | |||
512 | // first-region entry block) or the (hoistable or unhoistable) base values that | |||
513 | // are defined outside (including the first-region entry block) of the | |||
514 | // scope. The returned set doesn't include constants. | |||
515 | static std::set<Value *> getBaseValues( | |||
516 | Value *V, DominatorTree &DT, | |||
517 | DenseMap<Value *, std::set<Value *>> &Visited) { | |||
518 | if (Visited.count(V)) { | |||
519 | return Visited[V]; | |||
520 | } | |||
521 | std::set<Value *> Result; | |||
522 | if (auto *I = dyn_cast<Instruction>(V)) { | |||
523 | // We don't stop at a block that's not in the Scope because we would miss some | |||
524 | // instructions that are based on the same base values if we stop there. | |||
525 | if (!isHoistable(I, DT)) { | |||
526 | Result.insert(I); | |||
527 | Visited.insert(std::make_pair(V, Result)); | |||
528 | return Result; | |||
529 | } | |||
530 | // I is hoistable above the Scope. | |||
531 | for (Value *Op : I->operands()) { | |||
532 | std::set<Value *> OpResult = getBaseValues(Op, DT, Visited); | |||
533 | Result.insert(OpResult.begin(), OpResult.end()); | |||
534 | } | |||
535 | Visited.insert(std::make_pair(V, Result)); | |||
536 | return Result; | |||
537 | } | |||
538 | if (isa<Argument>(V)) { | |||
539 | Result.insert(V); | |||
540 | Visited.insert(std::make_pair(V, Result)); | |||
541 | return Result; | |||
542 | } | |||
543 | // We don't include others like constants because those won't lead to any | |||
544 | // chance of folding of conditions (eg two bit checks merged into one check) | |||
545 | // after CHR. | |||
546 | Visited.insert(std::make_pair(V, Result)); | |||
547 | return Result; // empty | |||
548 | } | |||
549 | ||||
550 | // Return true if V is already hoisted or can be hoisted (along with its | |||
551 | // operands) above the insert point. When it returns true and HoistStops is | |||
552 | // non-null, the instructions to stop hoisting at through the use-def chains are | |||
553 | // inserted into HoistStops. | |||
554 | static bool | |||
555 | checkHoistValue(Value *V, Instruction *InsertPoint, DominatorTree &DT, | |||
556 | DenseSet<Instruction *> &Unhoistables, | |||
557 | DenseSet<Instruction *> *HoistStops, | |||
558 | DenseMap<Instruction *, bool> &Visited) { | |||
559 | assert(InsertPoint && "Null InsertPoint")((InsertPoint && "Null InsertPoint") ? static_cast< void> (0) : __assert_fail ("InsertPoint && \"Null InsertPoint\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 559, __PRETTY_FUNCTION__)); | |||
560 | if (auto *I = dyn_cast<Instruction>(V)) { | |||
561 | if (Visited.count(I)) { | |||
562 | return Visited[I]; | |||
563 | } | |||
564 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 564, __PRETTY_FUNCTION__)); | |||
565 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 565, __PRETTY_FUNCTION__)); | |||
566 | if (Unhoistables.count(I)) { | |||
567 | // Don't hoist if they are not to be hoisted. | |||
568 | Visited[I] = false; | |||
569 | return false; | |||
570 | } | |||
571 | if (DT.dominates(I, InsertPoint)) { | |||
572 | // We are already above the insert point. Stop here. | |||
573 | if (HoistStops) | |||
574 | HoistStops->insert(I); | |||
575 | Visited[I] = true; | |||
576 | return true; | |||
577 | } | |||
578 | // We aren't not above the insert point, check if we can hoist it above the | |||
579 | // insert point. | |||
580 | if (isHoistable(I, DT)) { | |||
581 | // Check operands first. | |||
582 | DenseSet<Instruction *> OpsHoistStops; | |||
583 | bool AllOpsHoisted = true; | |||
584 | for (Value *Op : I->operands()) { | |||
585 | if (!checkHoistValue(Op, InsertPoint, DT, Unhoistables, &OpsHoistStops, | |||
586 | Visited)) { | |||
587 | AllOpsHoisted = false; | |||
588 | break; | |||
589 | } | |||
590 | } | |||
591 | if (AllOpsHoisted) { | |||
592 | CHR_DEBUG(dbgs() << "checkHoistValue " << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "checkHoistValue " << *I << "\n"; } } while (false); | |||
593 | if (HoistStops) | |||
594 | HoistStops->insert(OpsHoistStops.begin(), OpsHoistStops.end()); | |||
595 | Visited[I] = true; | |||
596 | return true; | |||
597 | } | |||
598 | } | |||
599 | Visited[I] = false; | |||
600 | return false; | |||
601 | } | |||
602 | // Non-instructions are considered hoistable. | |||
603 | return true; | |||
604 | } | |||
605 | ||||
606 | // Returns true and sets the true probability and false probability of an | |||
607 | // MD_prof metadata if it's well-formed. | |||
608 | static bool checkMDProf(MDNode *MD, BranchProbability &TrueProb, | |||
609 | BranchProbability &FalseProb) { | |||
610 | if (!MD) return false; | |||
611 | MDString *MDName = cast<MDString>(MD->getOperand(0)); | |||
612 | if (MDName->getString() != "branch_weights" || | |||
613 | MD->getNumOperands() != 3) | |||
614 | return false; | |||
615 | ConstantInt *TrueWeight = mdconst::extract<ConstantInt>(MD->getOperand(1)); | |||
616 | ConstantInt *FalseWeight = mdconst::extract<ConstantInt>(MD->getOperand(2)); | |||
617 | if (!TrueWeight || !FalseWeight) | |||
618 | return false; | |||
619 | uint64_t TrueWt = TrueWeight->getValue().getZExtValue(); | |||
620 | uint64_t FalseWt = FalseWeight->getValue().getZExtValue(); | |||
621 | uint64_t SumWt = TrueWt + FalseWt; | |||
622 | ||||
623 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 624, __PRETTY_FUNCTION__)) | |||
624 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 624, __PRETTY_FUNCTION__)); | |||
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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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 || !Selects.empty()) { | |||
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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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 | 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) | |||
| ||||
1065 | 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) | |||
1066 | 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) | |||
1067 | 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) | |||
1068 | }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 | 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) | |||
1070 | 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) | |||
1071 | 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) | |||
1072 | }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 | 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); | |||
1074 | assert(InsertPoint && "Null InsertPoint")((InsertPoint && "Null InsertPoint") ? static_cast< void> (0) : __assert_fail ("InsertPoint && \"Null InsertPoint\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1074, __PRETTY_FUNCTION__)); | |||
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 | std::set<Value *> BaseValues = getBaseValues(V, DT, Visited); | |||
1092 | PrevBases.insert(BaseValues.begin(), BaseValues.end()); | |||
1093 | } | |||
1094 | for (Value *V : ConditionValues) { | |||
1095 | 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::set<Value *> Intersection; | |||
1109 | std::set_intersection(PrevBases.begin(), PrevBases.end(), | |||
1110 | Bases.begin(), Bases.end(), | |||
1111 | std::inserter(Intersection, Intersection.begin())); | |||
1112 | if (Intersection.empty()) { | |||
1113 | // Empty intersection, split. | |||
1114 | CHR_DEBUG(dbgs() << "Split. Intersection empty\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Split. Intersection empty\n"; } } while (false); | |||
1115 | return true; | |||
1116 | } | |||
1117 | } | |||
1118 | CHR_DEBUG(dbgs() << "No split\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "No split\n"; } } while (false); | |||
1119 | return false; // Don't split. | |||
1120 | } | |||
1121 | ||||
1122 | static void getSelectsInScope(CHRScope *Scope, | |||
1123 | DenseSet<Instruction *> &Output) { | |||
1124 | for (RegInfo &RI : Scope->RegInfos) | |||
1125 | for (SelectInst *SI : RI.Selects) | |||
1126 | Output.insert(SI); | |||
1127 | for (CHRScope *Sub : Scope->Subs) | |||
1128 | getSelectsInScope(Sub, Output); | |||
1129 | } | |||
1130 | ||||
1131 | void CHR::splitScopes(SmallVectorImpl<CHRScope *> &Input, | |||
1132 | SmallVectorImpl<CHRScope *> &Output) { | |||
1133 | for (CHRScope *Scope : Input) { | |||
1134 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1135, __PRETTY_FUNCTION__)) | |||
1135 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1135, __PRETTY_FUNCTION__)); | |||
1136 | DenseSet<Instruction *> Unhoistables; | |||
1137 | getSelectsInScope(Scope, Unhoistables); | |||
1138 | splitScope(Scope, nullptr, nullptr, nullptr, Output, Unhoistables); | |||
1139 | } | |||
1140 | #ifndef NDEBUG | |||
1141 | for (CHRScope *Scope : Output) { | |||
1142 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1142, __PRETTY_FUNCTION__)); | |||
1143 | } | |||
1144 | #endif | |||
1145 | } | |||
1146 | ||||
1147 | SmallVector<CHRScope *, 8> CHR::splitScope( | |||
1148 | CHRScope *Scope, | |||
1149 | CHRScope *Outer, | |||
1150 | DenseSet<Value *> *OuterConditionValues, | |||
1151 | Instruction *OuterInsertPoint, | |||
1152 | SmallVectorImpl<CHRScope *> &Output, | |||
1153 | DenseSet<Instruction *> &Unhoistables) { | |||
1154 | if (Outer
| |||
1155 | assert(OuterConditionValues && "Null OuterConditionValues")((OuterConditionValues && "Null OuterConditionValues" ) ? static_cast<void> (0) : __assert_fail ("OuterConditionValues && \"Null OuterConditionValues\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1155, __PRETTY_FUNCTION__)); | |||
1156 | assert(OuterInsertPoint && "Null OuterInsertPoint")((OuterInsertPoint && "Null OuterInsertPoint") ? static_cast <void> (0) : __assert_fail ("OuterInsertPoint && \"Null OuterInsertPoint\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1156, __PRETTY_FUNCTION__)); | |||
1157 | } | |||
1158 | bool PrevSplitFromOuter = true; | |||
1159 | DenseSet<Value *> PrevConditionValues; | |||
1160 | Instruction *PrevInsertPoint = nullptr; | |||
1161 | SmallVector<CHRScope *, 8> Splits; | |||
1162 | SmallVector<bool, 8> SplitsSplitFromOuter; | |||
1163 | SmallVector<DenseSet<Value *>, 8> SplitsConditionValues; | |||
1164 | SmallVector<Instruction *, 8> SplitsInsertPoints; | |||
1165 | SmallVector<RegInfo, 8> RegInfos(Scope->RegInfos); // Copy | |||
1166 | for (RegInfo &RI : RegInfos) { | |||
1167 | Instruction *InsertPoint = getBranchInsertPoint(RI); | |||
1168 | DenseSet<Value *> ConditionValues = getCHRConditionValuesForRegion(RI); | |||
1169 | CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "ConditionValues "; for (Value *V : ConditionValues) { dbgs() << *V << ", "; } dbgs( ) << "\n"; } } while (false) | |||
1170 | dbgs() << "ConditionValues ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "ConditionValues "; for (Value *V : ConditionValues) { dbgs() << *V << ", "; } dbgs( ) << "\n"; } } while (false) | |||
1171 | for (Value *V : ConditionValues) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "ConditionValues "; for (Value *V : ConditionValues) { dbgs() << *V << ", "; } dbgs( ) << "\n"; } } while (false) | |||
1172 | dbgs() << *V << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "ConditionValues "; for (Value *V : ConditionValues) { dbgs() << *V << ", "; } dbgs( ) << "\n"; } } while (false) | |||
1173 | }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "ConditionValues "; for (Value *V : ConditionValues) { dbgs() << *V << ", "; } dbgs( ) << "\n"; } } while (false) | |||
1174 | dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "ConditionValues "; for (Value *V : ConditionValues) { dbgs() << *V << ", "; } dbgs( ) << "\n"; } } while (false); | |||
1175 | if (RI.R == RegInfos[0].R) { | |||
1176 | // First iteration. Check to see if we should split from the outer. | |||
1177 | if (Outer) { | |||
1178 | CHR_DEBUG(dbgs() << "Outer " << *Outer << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Outer " << *Outer << "\n" ; } } while (false); | |||
1179 | 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) | |||
1180 | << RI.R->getNameStr() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Should split from outer at " << RI.R->getNameStr() << "\n"; } } while (false); | |||
1181 | if (shouldSplit(OuterInsertPoint, *OuterConditionValues, | |||
1182 | ConditionValues, DT, Unhoistables)) { | |||
1183 | PrevConditionValues = ConditionValues; | |||
1184 | PrevInsertPoint = InsertPoint; | |||
1185 | ORE.emit([&]() { | |||
1186 | return OptimizationRemarkMissed(DEBUG_TYPE"chr", | |||
1187 | "SplitScopeFromOuter", | |||
1188 | RI.R->getEntry()->getTerminator()) | |||
1189 | << "Split scope from outer due to unhoistable branch/select " | |||
1190 | << "and/or lack of common condition values"; | |||
1191 | }); | |||
1192 | } else { | |||
1193 | // Not splitting from the outer. Use the outer bases and insert | |||
1194 | // point. Union the bases. | |||
1195 | PrevSplitFromOuter = false; | |||
1196 | PrevConditionValues = *OuterConditionValues; | |||
1197 | PrevConditionValues.insert(ConditionValues.begin(), | |||
1198 | ConditionValues.end()); | |||
1199 | PrevInsertPoint = OuterInsertPoint; | |||
1200 | } | |||
1201 | } else { | |||
1202 | CHR_DEBUG(dbgs() << "Outer null\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Outer null\n"; } } while (false); | |||
1203 | PrevConditionValues = ConditionValues; | |||
1204 | PrevInsertPoint = InsertPoint; | |||
1205 | } | |||
1206 | } else { | |||
1207 | 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) | |||
1208 | << RI.R->getNameStr() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Should split from prev at " << RI.R->getNameStr() << "\n"; } } while (false); | |||
1209 | if (shouldSplit(PrevInsertPoint, PrevConditionValues, ConditionValues, | |||
1210 | DT, Unhoistables)) { | |||
1211 | CHRScope *Tail = Scope->split(RI.R); | |||
1212 | Scopes.insert(Tail); | |||
1213 | Splits.push_back(Scope); | |||
1214 | SplitsSplitFromOuter.push_back(PrevSplitFromOuter); | |||
1215 | SplitsConditionValues.push_back(PrevConditionValues); | |||
1216 | SplitsInsertPoints.push_back(PrevInsertPoint); | |||
1217 | Scope = Tail; | |||
1218 | PrevConditionValues = ConditionValues; | |||
1219 | PrevInsertPoint = InsertPoint; | |||
1220 | PrevSplitFromOuter = true; | |||
1221 | ORE.emit([&]() { | |||
1222 | return OptimizationRemarkMissed(DEBUG_TYPE"chr", | |||
1223 | "SplitScopeFromPrev", | |||
1224 | RI.R->getEntry()->getTerminator()) | |||
1225 | << "Split scope from previous due to unhoistable branch/select " | |||
1226 | << "and/or lack of common condition values"; | |||
1227 | }); | |||
1228 | } else { | |||
1229 | // Not splitting. Union the bases. Keep the hoist point. | |||
1230 | PrevConditionValues.insert(ConditionValues.begin(), ConditionValues.end()); | |||
1231 | } | |||
1232 | } | |||
1233 | } | |||
1234 | Splits.push_back(Scope); | |||
1235 | SplitsSplitFromOuter.push_back(PrevSplitFromOuter); | |||
1236 | SplitsConditionValues.push_back(PrevConditionValues); | |||
1237 | assert(PrevInsertPoint && "Null PrevInsertPoint")((PrevInsertPoint && "Null PrevInsertPoint") ? static_cast <void> (0) : __assert_fail ("PrevInsertPoint && \"Null PrevInsertPoint\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1237, __PRETTY_FUNCTION__)); | |||
1238 | SplitsInsertPoints.push_back(PrevInsertPoint); | |||
1239 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1241, __PRETTY_FUNCTION__)) | |||
1240 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1241, __PRETTY_FUNCTION__)) | |||
1241 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1241, __PRETTY_FUNCTION__)); | |||
1242 | for (size_t I = 0; I < Splits.size(); ++I) { | |||
1243 | CHRScope *Split = Splits[I]; | |||
1244 | DenseSet<Value *> &SplitConditionValues = SplitsConditionValues[I]; | |||
1245 | Instruction *SplitInsertPoint = SplitsInsertPoints[I]; | |||
1246 | SmallVector<CHRScope *, 8> NewSubs; | |||
1247 | DenseSet<Instruction *> SplitUnhoistables; | |||
1248 | getSelectsInScope(Split, SplitUnhoistables); | |||
1249 | for (CHRScope *Sub : Split->Subs) { | |||
1250 | SmallVector<CHRScope *, 8> SubSplits = splitScope( | |||
1251 | Sub, Split, &SplitConditionValues, SplitInsertPoint, Output, | |||
1252 | SplitUnhoistables); | |||
1253 | NewSubs.insert(NewSubs.end(), SubSplits.begin(), SubSplits.end()); | |||
1254 | } | |||
1255 | Split->Subs = NewSubs; | |||
1256 | } | |||
1257 | SmallVector<CHRScope *, 8> Result; | |||
1258 | for (size_t I = 0; I < Splits.size(); ++I) { | |||
1259 | CHRScope *Split = Splits[I]; | |||
1260 | if (SplitsSplitFromOuter[I]) { | |||
1261 | // Split from the outer. | |||
1262 | Output.push_back(Split); | |||
1263 | Split->BranchInsertPoint = SplitsInsertPoints[I]; | |||
1264 | CHR_DEBUG(dbgs() << "BranchInsertPoint " << *SplitsInsertPoints[I]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "BranchInsertPoint " << *SplitsInsertPoints [I] << "\n"; } } while (false) | |||
1265 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "BranchInsertPoint " << *SplitsInsertPoints [I] << "\n"; } } while (false); | |||
1266 | } else { | |||
1267 | // Connected to the outer. | |||
1268 | Result.push_back(Split); | |||
1269 | } | |||
1270 | } | |||
1271 | if (!Outer) | |||
1272 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1273, __PRETTY_FUNCTION__)) | |||
1273 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1273, __PRETTY_FUNCTION__)); | |||
1274 | return Result; | |||
1275 | } | |||
1276 | ||||
1277 | void CHR::classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes) { | |||
1278 | for (CHRScope *Scope : Scopes) { | |||
1279 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1279, __PRETTY_FUNCTION__)); | |||
1280 | classifyBiasedScopes(Scope, Scope); | |||
1281 | 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) | |||
1282 | 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) | |||
1283 | 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) | |||
1284 | 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) | |||
1285 | 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) | |||
1286 | }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() << "\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) | |||
1288 | 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) | |||
1289 | 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) | |||
1290 | 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) | |||
1291 | }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() << "\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) | |||
1293 | 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) | |||
1294 | 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) | |||
1295 | 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) | |||
1296 | }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() << "\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) | |||
1298 | 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) | |||
1299 | 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) | |||
1300 | 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) | |||
1301 | }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 | 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); | |||
1303 | } | |||
1304 | } | |||
1305 | ||||
1306 | void CHR::classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope) { | |||
1307 | for (RegInfo &RI : Scope->RegInfos) { | |||
1308 | if (RI.HasBranch) { | |||
1309 | Region *R = RI.R; | |||
1310 | if (TrueBiasedRegionsGlobal.count(R) > 0) | |||
1311 | OutermostScope->TrueBiasedRegions.insert(R); | |||
1312 | else if (FalseBiasedRegionsGlobal.count(R) > 0) | |||
1313 | OutermostScope->FalseBiasedRegions.insert(R); | |||
1314 | else | |||
1315 | llvm_unreachable("Must be biased")::llvm::llvm_unreachable_internal("Must be biased", "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1315); | |||
1316 | } | |||
1317 | for (SelectInst *SI : RI.Selects) { | |||
1318 | if (TrueBiasedSelectsGlobal.count(SI) > 0) | |||
1319 | OutermostScope->TrueBiasedSelects.insert(SI); | |||
1320 | else if (FalseBiasedSelectsGlobal.count(SI) > 0) | |||
1321 | OutermostScope->FalseBiasedSelects.insert(SI); | |||
1322 | else | |||
1323 | llvm_unreachable("Must be biased")::llvm::llvm_unreachable_internal("Must be biased", "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1323); | |||
1324 | } | |||
1325 | } | |||
1326 | for (CHRScope *Sub : Scope->Subs) { | |||
1327 | classifyBiasedScopes(Sub, OutermostScope); | |||
1328 | } | |||
1329 | } | |||
1330 | ||||
1331 | static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope) { | |||
1332 | unsigned NumBiased = Scope->TrueBiasedRegions.size() + | |||
1333 | Scope->FalseBiasedRegions.size() + | |||
1334 | Scope->TrueBiasedSelects.size() + | |||
1335 | Scope->FalseBiasedSelects.size(); | |||
1336 | return NumBiased >= CHRMergeThreshold; | |||
1337 | } | |||
1338 | ||||
1339 | void CHR::filterScopes(SmallVectorImpl<CHRScope *> &Input, | |||
1340 | SmallVectorImpl<CHRScope *> &Output) { | |||
1341 | for (CHRScope *Scope : Input) { | |||
1342 | // Filter out the ones with only one region and no subs. | |||
1343 | if (!hasAtLeastTwoBiasedBranches(Scope)) { | |||
1344 | 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) | |||
1345 | << 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) | |||
1346 | << " 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) | |||
1347 | << " 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) | |||
1348 | << " 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); | |||
1349 | ORE.emit([&]() { | |||
1350 | return OptimizationRemarkMissed( | |||
1351 | DEBUG_TYPE"chr", | |||
1352 | "DropScopeWithOneBranchOrSelect", | |||
1353 | Scope->RegInfos[0].R->getEntry()->getTerminator()) | |||
1354 | << "Drop scope with < " | |||
1355 | << ore::NV("CHRMergeThreshold", CHRMergeThreshold) | |||
1356 | << " biased branch(es) or select(s)"; | |||
1357 | }); | |||
1358 | continue; | |||
1359 | } | |||
1360 | Output.push_back(Scope); | |||
1361 | } | |||
1362 | } | |||
1363 | ||||
1364 | void CHR::setCHRRegions(SmallVectorImpl<CHRScope *> &Input, | |||
1365 | SmallVectorImpl<CHRScope *> &Output) { | |||
1366 | for (CHRScope *Scope : Input) { | |||
1367 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1368, __PRETTY_FUNCTION__)) | |||
1368 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1368, __PRETTY_FUNCTION__)); | |||
1369 | setCHRRegions(Scope, Scope); | |||
1370 | Output.push_back(Scope); | |||
1371 | 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) | |||
1372 | 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) | |||
1373 | 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) | |||
1374 | 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) | |||
1375 | 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) | |||
1376 | 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) | |||
1377 | 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) | |||
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 | }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 | 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) | |||
1381 | 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) | |||
1382 | 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) | |||
1383 | })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); | |||
1384 | } | |||
1385 | } | |||
1386 | ||||
1387 | void CHR::setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope) { | |||
1388 | DenseSet<Instruction *> Unhoistables; | |||
1389 | // Put the biased selects in Unhoistables because they should stay where they | |||
1390 | // are and constant-folded after CHR (in case one biased select or a branch | |||
1391 | // can depend on another biased select.) | |||
1392 | for (RegInfo &RI : Scope->RegInfos) { | |||
1393 | for (SelectInst *SI : RI.Selects) { | |||
1394 | Unhoistables.insert(SI); | |||
1395 | } | |||
1396 | } | |||
1397 | Instruction *InsertPoint = OutermostScope->BranchInsertPoint; | |||
1398 | for (RegInfo &RI : Scope->RegInfos) { | |||
1399 | Region *R = RI.R; | |||
1400 | DenseSet<Instruction *> HoistStops; | |||
1401 | bool IsHoisted = false; | |||
1402 | if (RI.HasBranch) { | |||
1403 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1405, __PRETTY_FUNCTION__)) | |||
1404 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1405, __PRETTY_FUNCTION__)) | |||
1405 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1405, __PRETTY_FUNCTION__)); | |||
1406 | auto *BI = cast<BranchInst>(R->getEntry()->getTerminator()); | |||
1407 | // Note checkHoistValue fills in HoistStops. | |||
1408 | DenseMap<Instruction *, bool> Visited; | |||
1409 | bool IsHoistable = checkHoistValue(BI->getCondition(), InsertPoint, DT, | |||
1410 | Unhoistables, &HoistStops, Visited); | |||
1411 | assert(IsHoistable && "Must be hoistable")((IsHoistable && "Must be hoistable") ? static_cast< void> (0) : __assert_fail ("IsHoistable && \"Must be hoistable\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1411, __PRETTY_FUNCTION__)); | |||
1412 | (void)(IsHoistable); // Unused in release build | |||
1413 | IsHoisted = true; | |||
1414 | } | |||
1415 | for (SelectInst *SI : RI.Selects) { | |||
1416 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1418, __PRETTY_FUNCTION__)) | |||
1417 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1418, __PRETTY_FUNCTION__)) | |||
1418 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1418, __PRETTY_FUNCTION__)); | |||
1419 | // Note checkHoistValue fills in HoistStops. | |||
1420 | DenseMap<Instruction *, bool> Visited; | |||
1421 | bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint, DT, | |||
1422 | Unhoistables, &HoistStops, Visited); | |||
1423 | assert(IsHoistable && "Must be hoistable")((IsHoistable && "Must be hoistable") ? static_cast< void> (0) : __assert_fail ("IsHoistable && \"Must be hoistable\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1423, __PRETTY_FUNCTION__)); | |||
1424 | (void)(IsHoistable); // Unused in release build | |||
1425 | IsHoisted = true; | |||
1426 | } | |||
1427 | if (IsHoisted) { | |||
1428 | OutermostScope->CHRRegions.push_back(RI); | |||
1429 | OutermostScope->HoistStopMap[R] = HoistStops; | |||
1430 | } | |||
1431 | } | |||
1432 | for (CHRScope *Sub : Scope->Subs) | |||
1433 | setCHRRegions(Sub, OutermostScope); | |||
1434 | } | |||
1435 | ||||
1436 | bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2) { | |||
1437 | return Scope1->RegInfos[0].R->getDepth() < Scope2->RegInfos[0].R->getDepth(); | |||
1438 | } | |||
1439 | ||||
1440 | void CHR::sortScopes(SmallVectorImpl<CHRScope *> &Input, | |||
1441 | SmallVectorImpl<CHRScope *> &Output) { | |||
1442 | Output.resize(Input.size()); | |||
1443 | llvm::copy(Input, Output.begin()); | |||
1444 | llvm::stable_sort(Output, CHRScopeSorter); | |||
1445 | } | |||
1446 | ||||
1447 | // Return true if V is already hoisted or was hoisted (along with its operands) | |||
1448 | // to the insert point. | |||
1449 | static void hoistValue(Value *V, Instruction *HoistPoint, Region *R, | |||
1450 | HoistStopMapTy &HoistStopMap, | |||
1451 | DenseSet<Instruction *> &HoistedSet, | |||
1452 | DenseSet<PHINode *> &TrivialPHIs, | |||
1453 | DominatorTree &DT) { | |||
1454 | auto IT = HoistStopMap.find(R); | |||
1455 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1455, __PRETTY_FUNCTION__)); | |||
1456 | DenseSet<Instruction *> &HoistStops = IT->second; | |||
1457 | if (auto *I = dyn_cast<Instruction>(V)) { | |||
1458 | if (I == HoistPoint) | |||
1459 | return; | |||
1460 | if (HoistStops.count(I)) | |||
1461 | return; | |||
1462 | if (auto *PN = dyn_cast<PHINode>(I)) | |||
1463 | if (TrivialPHIs.count(PN)) | |||
1464 | // The trivial phi inserted by the previous CHR scope could replace a | |||
1465 | // non-phi in HoistStops. Note that since this phi is at the exit of a | |||
1466 | // previous CHR scope, which dominates this scope, it's safe to stop | |||
1467 | // hoisting there. | |||
1468 | return; | |||
1469 | if (HoistedSet.count(I)) | |||
1470 | // Already hoisted, return. | |||
1471 | return; | |||
1472 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1472, __PRETTY_FUNCTION__)); | |||
1473 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1473, __PRETTY_FUNCTION__)); | |||
1474 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1475, __PRETTY_FUNCTION__)) | |||
1475 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1475, __PRETTY_FUNCTION__)); | |||
1476 | if (DT.dominates(I, HoistPoint)) | |||
1477 | // We are already above the hoist point. Stop here. This may be necessary | |||
1478 | // when multiple scopes would independently hoist the same | |||
1479 | // instruction. Since an outer (dominating) scope would hoist it to its | |||
1480 | // entry before an inner (dominated) scope would to its entry, the inner | |||
1481 | // scope may see the instruction already hoisted, in which case it | |||
1482 | // potentially wrong for the inner scope to hoist it and could cause bad | |||
1483 | // IR (non-dominating def), but safe to skip hoisting it instead because | |||
1484 | // it's already in a block that dominates the inner scope. | |||
1485 | return; | |||
1486 | for (Value *Op : I->operands()) { | |||
1487 | hoistValue(Op, HoistPoint, R, HoistStopMap, HoistedSet, TrivialPHIs, DT); | |||
1488 | } | |||
1489 | I->moveBefore(HoistPoint); | |||
1490 | HoistedSet.insert(I); | |||
1491 | CHR_DEBUG(dbgs() << "hoistValue " << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "hoistValue " << *I << "\n"; } } while (false); | |||
1492 | } | |||
1493 | } | |||
1494 | ||||
1495 | // Hoist the dependent condition values of the branches and the selects in the | |||
1496 | // scope to the insert point. | |||
1497 | static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint, | |||
1498 | DenseSet<PHINode *> &TrivialPHIs, | |||
1499 | DominatorTree &DT) { | |||
1500 | DenseSet<Instruction *> HoistedSet; | |||
1501 | for (const RegInfo &RI : Scope->CHRRegions) { | |||
1502 | Region *R = RI.R; | |||
1503 | bool IsTrueBiased = Scope->TrueBiasedRegions.count(R); | |||
1504 | bool IsFalseBiased = Scope->FalseBiasedRegions.count(R); | |||
1505 | if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) { | |||
1506 | auto *BI = cast<BranchInst>(R->getEntry()->getTerminator()); | |||
1507 | hoistValue(BI->getCondition(), HoistPoint, R, Scope->HoistStopMap, | |||
1508 | HoistedSet, TrivialPHIs, DT); | |||
1509 | } | |||
1510 | for (SelectInst *SI : RI.Selects) { | |||
1511 | bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI); | |||
1512 | bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI); | |||
1513 | if (!(IsTrueBiased || IsFalseBiased)) | |||
1514 | continue; | |||
1515 | hoistValue(SI->getCondition(), HoistPoint, R, Scope->HoistStopMap, | |||
1516 | HoistedSet, TrivialPHIs, DT); | |||
1517 | } | |||
1518 | } | |||
1519 | } | |||
1520 | ||||
1521 | // Negate the predicate if an ICmp if it's used only by branches or selects by | |||
1522 | // swapping the operands of the branches or the selects. Returns true if success. | |||
1523 | static bool negateICmpIfUsedByBranchOrSelectOnly(ICmpInst *ICmp, | |||
1524 | Instruction *ExcludedUser, | |||
1525 | CHRScope *Scope) { | |||
1526 | for (User *U : ICmp->users()) { | |||
1527 | if (U == ExcludedUser) | |||
1528 | continue; | |||
1529 | if (isa<BranchInst>(U) && cast<BranchInst>(U)->isConditional()) | |||
1530 | continue; | |||
1531 | if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == ICmp) | |||
1532 | continue; | |||
1533 | return false; | |||
1534 | } | |||
1535 | for (User *U : ICmp->users()) { | |||
1536 | if (U == ExcludedUser) | |||
1537 | continue; | |||
1538 | if (auto *BI = dyn_cast<BranchInst>(U)) { | |||
1539 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1539, __PRETTY_FUNCTION__)); | |||
1540 | BI->swapSuccessors(); | |||
1541 | // Don't need to swap this in terms of | |||
1542 | // TrueBiasedRegions/FalseBiasedRegions because true-based/false-based | |||
1543 | // mean whehter the branch is likely go into the if-then rather than | |||
1544 | // successor0/successor1 and because we can tell which edge is the then or | |||
1545 | // the else one by comparing the destination to the region exit block. | |||
1546 | continue; | |||
1547 | } | |||
1548 | if (auto *SI = dyn_cast<SelectInst>(U)) { | |||
1549 | // Swap operands | |||
1550 | SI->swapValues(); | |||
1551 | SI->swapProfMetadata(); | |||
1552 | if (Scope->TrueBiasedSelects.count(SI)) { | |||
1553 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1554, __PRETTY_FUNCTION__)) | |||
1554 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1554, __PRETTY_FUNCTION__)); | |||
1555 | Scope->FalseBiasedSelects.insert(SI); | |||
1556 | } else if (Scope->FalseBiasedSelects.count(SI)) { | |||
1557 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1558, __PRETTY_FUNCTION__)) | |||
1558 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1558, __PRETTY_FUNCTION__)); | |||
1559 | Scope->TrueBiasedSelects.insert(SI); | |||
1560 | } | |||
1561 | continue; | |||
1562 | } | |||
1563 | llvm_unreachable("Must be a branch or a select")::llvm::llvm_unreachable_internal("Must be a branch or a select" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1563); | |||
1564 | } | |||
1565 | ICmp->setPredicate(CmpInst::getInversePredicate(ICmp->getPredicate())); | |||
1566 | return true; | |||
1567 | } | |||
1568 | ||||
1569 | // A helper for transformScopes. Insert a trivial phi at the scope exit block | |||
1570 | // for a value that's defined in the scope but used outside it (meaning it's | |||
1571 | // alive at the exit block). | |||
1572 | static void insertTrivialPHIs(CHRScope *Scope, | |||
1573 | BasicBlock *EntryBlock, BasicBlock *ExitBlock, | |||
1574 | DenseSet<PHINode *> &TrivialPHIs) { | |||
1575 | DenseSet<BasicBlock *> BlocksInScopeSet; | |||
1576 | SmallVector<BasicBlock *, 8> BlocksInScopeVec; | |||
1577 | for (RegInfo &RI : Scope->RegInfos) { | |||
1578 | for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the | |||
1579 | // sub-Scopes. | |||
1580 | BlocksInScopeSet.insert(BB); | |||
1581 | BlocksInScopeVec.push_back(BB); | |||
1582 | } | |||
1583 | } | |||
1584 | CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Inserting redudant phis\n"; for ( BasicBlock *BB : BlocksInScopeVec) { dbgs() << "BlockInScope " << BB->getName() << "\n"; }; } } while (false ) | |||
1585 | dbgs() << "Inserting redudant phis\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Inserting redudant phis\n"; for ( BasicBlock *BB : BlocksInScopeVec) { dbgs() << "BlockInScope " << BB->getName() << "\n"; }; } } while (false ) | |||
1586 | for (BasicBlock *BB : BlocksInScopeVec) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Inserting redudant phis\n"; for ( BasicBlock *BB : BlocksInScopeVec) { dbgs() << "BlockInScope " << BB->getName() << "\n"; }; } } while (false ) | |||
1587 | dbgs() << "BlockInScope " << BB->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Inserting redudant phis\n"; for ( BasicBlock *BB : BlocksInScopeVec) { dbgs() << "BlockInScope " << BB->getName() << "\n"; }; } } while (false ) | |||
1588 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Inserting redudant phis\n"; for ( BasicBlock *BB : BlocksInScopeVec) { dbgs() << "BlockInScope " << BB->getName() << "\n"; }; } } while (false ); | |||
1589 | for (BasicBlock *BB : BlocksInScopeVec) { | |||
1590 | for (Instruction &I : *BB) { | |||
1591 | SmallVector<Instruction *, 8> Users; | |||
1592 | for (User *U : I.users()) { | |||
1593 | if (auto *UI = dyn_cast<Instruction>(U)) { | |||
1594 | if (BlocksInScopeSet.count(UI->getParent()) == 0 && | |||
1595 | // Unless there's already a phi for I at the exit block. | |||
1596 | !(isa<PHINode>(UI) && UI->getParent() == ExitBlock)) { | |||
1597 | CHR_DEBUG(dbgs() << "V " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "V " << I << "\n"; } } while (false); | |||
1598 | 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); | |||
1599 | Users.push_back(UI); | |||
1600 | } else if (UI->getParent() == EntryBlock && isa<PHINode>(UI)) { | |||
1601 | // There's a loop backedge from a block that's dominated by this | |||
1602 | // scope to the entry block. | |||
1603 | CHR_DEBUG(dbgs() << "V " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "V " << I << "\n"; } } while (false); | |||
1604 | 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) | |||
1605 | << "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) | |||
1606 | << *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); | |||
1607 | Users.push_back(UI); | |||
1608 | } | |||
1609 | } | |||
1610 | } | |||
1611 | if (Users.size() > 0) { | |||
1612 | // Insert a trivial phi for I (phi [&I, P0], [&I, P1], ...) at | |||
1613 | // ExitBlock. Replace I with the new phi in UI unless UI is another | |||
1614 | // phi at ExitBlock. | |||
1615 | unsigned PredCount = std::distance(pred_begin(ExitBlock), | |||
1616 | pred_end(ExitBlock)); | |||
1617 | PHINode *PN = PHINode::Create(I.getType(), PredCount, "", | |||
1618 | &ExitBlock->front()); | |||
1619 | for (BasicBlock *Pred : predecessors(ExitBlock)) { | |||
1620 | PN->addIncoming(&I, Pred); | |||
1621 | } | |||
1622 | TrivialPHIs.insert(PN); | |||
1623 | CHR_DEBUG(dbgs() << "Insert phi " << *PN << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Insert phi " << *PN << "\n"; } } while (false); | |||
1624 | for (Instruction *UI : Users) { | |||
1625 | for (unsigned J = 0, NumOps = UI->getNumOperands(); J < NumOps; ++J) { | |||
1626 | if (UI->getOperand(J) == &I) { | |||
1627 | UI->setOperand(J, PN); | |||
1628 | } | |||
1629 | } | |||
1630 | CHR_DEBUG(dbgs() << "Updated user " << *UI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Updated user " << *UI << "\n"; } } while (false); | |||
1631 | } | |||
1632 | } | |||
1633 | } | |||
1634 | } | |||
1635 | } | |||
1636 | ||||
1637 | // Assert that all the CHR regions of the scope have a biased branch or select. | |||
1638 | static void LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) | |||
1639 | assertCHRRegionsHaveBiasedBranchOrSelect(CHRScope *Scope) { | |||
1640 | #ifndef NDEBUG | |||
1641 | auto HasBiasedBranchOrSelect = [](RegInfo &RI, CHRScope *Scope) { | |||
1642 | if (Scope->TrueBiasedRegions.count(RI.R) || | |||
1643 | Scope->FalseBiasedRegions.count(RI.R)) | |||
1644 | return true; | |||
1645 | for (SelectInst *SI : RI.Selects) | |||
1646 | if (Scope->TrueBiasedSelects.count(SI) || | |||
1647 | Scope->FalseBiasedSelects.count(SI)) | |||
1648 | return true; | |||
1649 | return false; | |||
1650 | }; | |||
1651 | for (RegInfo &RI : Scope->CHRRegions) { | |||
1652 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1653, __PRETTY_FUNCTION__)) | |||
1653 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1653, __PRETTY_FUNCTION__)); | |||
1654 | } | |||
1655 | #endif | |||
1656 | } | |||
1657 | ||||
1658 | // Assert that all the condition values of the biased branches and selects have | |||
1659 | // been hoisted to the pre-entry block or outside of the scope. | |||
1660 | static void LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) assertBranchOrSelectConditionHoisted( | |||
1661 | CHRScope *Scope, BasicBlock *PreEntryBlock) { | |||
1662 | CHR_DEBUG(dbgs() << "Biased regions condition values \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Biased regions condition values \n" ; } } while (false); | |||
1663 | for (RegInfo &RI : Scope->CHRRegions) { | |||
1664 | Region *R = RI.R; | |||
1665 | bool IsTrueBiased = Scope->TrueBiasedRegions.count(R); | |||
1666 | bool IsFalseBiased = Scope->FalseBiasedRegions.count(R); | |||
1667 | if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) { | |||
1668 | auto *BI = cast<BranchInst>(R->getEntry()->getTerminator()); | |||
1669 | Value *V = BI->getCondition(); | |||
1670 | CHR_DEBUG(dbgs() << *V << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << *V << "\n"; } } while (false ); | |||
1671 | if (auto *I = dyn_cast<Instruction>(V)) { | |||
1672 | (void)(I); // Unused in release build. | |||
1673 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1675, __PRETTY_FUNCTION__)) | |||
1674 | !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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1675, __PRETTY_FUNCTION__)) | |||
1675 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1675, __PRETTY_FUNCTION__)); | |||
1676 | } | |||
1677 | } | |||
1678 | for (SelectInst *SI : RI.Selects) { | |||
1679 | bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI); | |||
1680 | bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI); | |||
1681 | if (!(IsTrueBiased || IsFalseBiased)) | |||
1682 | continue; | |||
1683 | Value *V = SI->getCondition(); | |||
1684 | CHR_DEBUG(dbgs() << *V << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << *V << "\n"; } } while (false ); | |||
1685 | if (auto *I = dyn_cast<Instruction>(V)) { | |||
1686 | (void)(I); // Unused in release build. | |||
1687 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1689, __PRETTY_FUNCTION__)) | |||
1688 | !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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1689, __PRETTY_FUNCTION__)) | |||
1689 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1689, __PRETTY_FUNCTION__)); | |||
1690 | } | |||
1691 | } | |||
1692 | } | |||
1693 | } | |||
1694 | ||||
1695 | void CHR::transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs) { | |||
1696 | CHR_DEBUG(dbgs() << "transformScopes " << *Scope << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "transformScopes " << *Scope << "\n"; } } while (false); | |||
1697 | ||||
1698 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1698, __PRETTY_FUNCTION__)); | |||
1699 | Region *FirstRegion = Scope->RegInfos[0].R; | |||
1700 | BasicBlock *EntryBlock = FirstRegion->getEntry(); | |||
1701 | Region *LastRegion = Scope->RegInfos[Scope->RegInfos.size() - 1].R; | |||
1702 | BasicBlock *ExitBlock = LastRegion->getExit(); | |||
1703 | Optional<uint64_t> ProfileCount = BFI.getBlockProfileCount(EntryBlock); | |||
1704 | ||||
1705 | if (ExitBlock) { | |||
1706 | // Insert a trivial phi at the exit block (where the CHR hot path and the | |||
1707 | // cold path merges) for a value that's defined in the scope but used | |||
1708 | // outside it (meaning it's alive at the exit block). We will add the | |||
1709 | // incoming values for the CHR cold paths to it below. Without this, we'd | |||
1710 | // miss updating phi's for such values unless there happens to already be a | |||
1711 | // phi for that value there. | |||
1712 | insertTrivialPHIs(Scope, EntryBlock, ExitBlock, TrivialPHIs); | |||
1713 | } | |||
1714 | ||||
1715 | // Split the entry block of the first region. The new block becomes the new | |||
1716 | // entry block of the first region. The old entry block becomes the block to | |||
1717 | // insert the CHR branch into. Note DT gets updated. Since DT gets updated | |||
1718 | // through the split, we update the entry of the first region after the split, | |||
1719 | // and Region only points to the entry and the exit blocks, rather than | |||
1720 | // keeping everything in a list or set, the blocks membership and the | |||
1721 | // entry/exit blocks of the region are still valid after the split. | |||
1722 | 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) | |||
1723 | << " at " << *Scope->BranchInsertPoint << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "Splitting entry block " << EntryBlock ->getName() << " at " << *Scope->BranchInsertPoint << "\n"; } } while (false); | |||
1724 | BasicBlock *NewEntryBlock = | |||
1725 | SplitBlock(EntryBlock, Scope->BranchInsertPoint, &DT); | |||
1726 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1727, __PRETTY_FUNCTION__)) | |||
1727 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1727, __PRETTY_FUNCTION__)); | |||
1728 | FirstRegion->replaceEntryRecursive(NewEntryBlock); | |||
1729 | BasicBlock *PreEntryBlock = EntryBlock; | |||
1730 | ||||
1731 | ValueToValueMapTy VMap; | |||
1732 | // Clone the blocks in the scope (excluding the PreEntryBlock) to split into a | |||
1733 | // hot path (originals) and a cold path (clones) and update the PHIs at the | |||
1734 | // exit block. | |||
1735 | cloneScopeBlocks(Scope, PreEntryBlock, ExitBlock, LastRegion, VMap); | |||
1736 | ||||
1737 | // Replace the old (placeholder) branch with the new (merged) conditional | |||
1738 | // branch. | |||
1739 | BranchInst *MergedBr = createMergedBranch(PreEntryBlock, EntryBlock, | |||
1740 | NewEntryBlock, VMap); | |||
1741 | ||||
1742 | #ifndef NDEBUG | |||
1743 | assertCHRRegionsHaveBiasedBranchOrSelect(Scope); | |||
1744 | #endif | |||
1745 | ||||
1746 | // Hoist the conditional values of the branches/selects. | |||
1747 | hoistScopeConditions(Scope, PreEntryBlock->getTerminator(), TrivialPHIs, DT); | |||
1748 | ||||
1749 | #ifndef NDEBUG | |||
1750 | assertBranchOrSelectConditionHoisted(Scope, PreEntryBlock); | |||
1751 | #endif | |||
1752 | ||||
1753 | // Create the combined branch condition and constant-fold the branches/selects | |||
1754 | // in the hot path. | |||
1755 | fixupBranchesAndSelects(Scope, PreEntryBlock, MergedBr, | |||
1756 | ProfileCount ? ProfileCount.getValue() : 0); | |||
1757 | } | |||
1758 | ||||
1759 | // A helper for transformScopes. Clone the blocks in the scope (excluding the | |||
1760 | // PreEntryBlock) to split into a hot path and a cold path and update the PHIs | |||
1761 | // at the exit block. | |||
1762 | void CHR::cloneScopeBlocks(CHRScope *Scope, | |||
1763 | BasicBlock *PreEntryBlock, | |||
1764 | BasicBlock *ExitBlock, | |||
1765 | Region *LastRegion, | |||
1766 | ValueToValueMapTy &VMap) { | |||
1767 | // Clone all the blocks. The original blocks will be the hot-path | |||
1768 | // CHR-optimized code and the cloned blocks will be the original unoptimized | |||
1769 | // code. This is so that the block pointers from the | |||
1770 | // CHRScope/Region/RegionInfo can stay valid in pointing to the hot-path code | |||
1771 | // which CHR should apply to. | |||
1772 | SmallVector<BasicBlock*, 8> NewBlocks; | |||
1773 | for (RegInfo &RI : Scope->RegInfos) | |||
1774 | for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the | |||
1775 | // sub-Scopes. | |||
1776 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1776, __PRETTY_FUNCTION__)); | |||
1777 | BasicBlock *NewBB = CloneBasicBlock(BB, VMap, ".nonchr", &F); | |||
1778 | NewBlocks.push_back(NewBB); | |||
1779 | VMap[BB] = NewBB; | |||
1780 | } | |||
1781 | ||||
1782 | // Place the cloned blocks right after the original blocks (right before the | |||
1783 | // exit block of.) | |||
1784 | if (ExitBlock) | |||
1785 | F.getBasicBlockList().splice(ExitBlock->getIterator(), | |||
1786 | F.getBasicBlockList(), | |||
1787 | NewBlocks[0]->getIterator(), F.end()); | |||
1788 | ||||
1789 | // Update the cloned blocks/instructions to refer to themselves. | |||
1790 | for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) | |||
1791 | for (Instruction &I : *NewBlocks[i]) | |||
1792 | RemapInstruction(&I, VMap, | |||
1793 | RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); | |||
1794 | ||||
1795 | // Add the cloned blocks to the PHIs of the exit blocks. ExitBlock is null for | |||
1796 | // the top-level region but we don't need to add PHIs. The trivial PHIs | |||
1797 | // inserted above will be updated here. | |||
1798 | if (ExitBlock) | |||
1799 | for (PHINode &PN : ExitBlock->phis()) | |||
1800 | for (unsigned I = 0, NumOps = PN.getNumIncomingValues(); I < NumOps; | |||
1801 | ++I) { | |||
1802 | BasicBlock *Pred = PN.getIncomingBlock(I); | |||
1803 | if (LastRegion->contains(Pred)) { | |||
1804 | Value *V = PN.getIncomingValue(I); | |||
1805 | auto It = VMap.find(V); | |||
1806 | if (It != VMap.end()) V = It->second; | |||
1807 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1807, __PRETTY_FUNCTION__)); | |||
1808 | PN.addIncoming(V, cast<BasicBlock>(VMap[Pred])); | |||
1809 | } | |||
1810 | } | |||
1811 | } | |||
1812 | ||||
1813 | // A helper for transformScope. Replace the old (placeholder) branch with the | |||
1814 | // new (merged) conditional branch. | |||
1815 | BranchInst *CHR::createMergedBranch(BasicBlock *PreEntryBlock, | |||
1816 | BasicBlock *EntryBlock, | |||
1817 | BasicBlock *NewEntryBlock, | |||
1818 | ValueToValueMapTy &VMap) { | |||
1819 | BranchInst *OldBR = cast<BranchInst>(PreEntryBlock->getTerminator()); | |||
1820 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1821, __PRETTY_FUNCTION__)) | |||
1821 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1821, __PRETTY_FUNCTION__)); | |||
1822 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1823, __PRETTY_FUNCTION__)) | |||
1823 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1823, __PRETTY_FUNCTION__)); | |||
1824 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1825, __PRETTY_FUNCTION__)) | |||
1825 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1825, __PRETTY_FUNCTION__)); | |||
1826 | OldBR->dropAllReferences(); | |||
1827 | OldBR->eraseFromParent(); | |||
1828 | // The true predicate is a placeholder. It will be replaced later in | |||
1829 | // fixupBranchesAndSelects(). | |||
1830 | BranchInst *NewBR = BranchInst::Create(NewEntryBlock, | |||
1831 | cast<BasicBlock>(VMap[NewEntryBlock]), | |||
1832 | ConstantInt::getTrue(F.getContext())); | |||
1833 | PreEntryBlock->getInstList().push_back(NewBR); | |||
1834 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1835, __PRETTY_FUNCTION__)) | |||
1835 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1835, __PRETTY_FUNCTION__)); | |||
1836 | return NewBR; | |||
1837 | } | |||
1838 | ||||
1839 | // A helper for transformScopes. Create the combined branch condition and | |||
1840 | // constant-fold the branches/selects in the hot path. | |||
1841 | void CHR::fixupBranchesAndSelects(CHRScope *Scope, | |||
1842 | BasicBlock *PreEntryBlock, | |||
1843 | BranchInst *MergedBR, | |||
1844 | uint64_t ProfileCount) { | |||
1845 | Value *MergedCondition = ConstantInt::getTrue(F.getContext()); | |||
1846 | BranchProbability CHRBranchBias(1, 1); | |||
1847 | uint64_t NumCHRedBranches = 0; | |||
1848 | IRBuilder<> IRB(PreEntryBlock->getTerminator()); | |||
1849 | for (RegInfo &RI : Scope->CHRRegions) { | |||
1850 | Region *R = RI.R; | |||
1851 | if (RI.HasBranch) { | |||
1852 | fixupBranch(R, Scope, IRB, MergedCondition, CHRBranchBias); | |||
1853 | ++NumCHRedBranches; | |||
1854 | } | |||
1855 | for (SelectInst *SI : RI.Selects) { | |||
1856 | fixupSelect(SI, Scope, IRB, MergedCondition, CHRBranchBias); | |||
1857 | ++NumCHRedBranches; | |||
1858 | } | |||
1859 | } | |||
1860 | Stats.NumBranchesDelta += NumCHRedBranches - 1; | |||
1861 | Stats.WeightedNumBranchesDelta += (NumCHRedBranches - 1) * ProfileCount; | |||
1862 | ORE.emit([&]() { | |||
1863 | return OptimizationRemark(DEBUG_TYPE"chr", | |||
1864 | "CHR", | |||
1865 | // Refer to the hot (original) path | |||
1866 | MergedBR->getSuccessor(0)->getTerminator()) | |||
1867 | << "Merged " << ore::NV("NumCHRedBranches", NumCHRedBranches) | |||
1868 | << " branches or selects"; | |||
1869 | }); | |||
1870 | MergedBR->setCondition(MergedCondition); | |||
1871 | SmallVector<uint32_t, 2> Weights; | |||
1872 | Weights.push_back(static_cast<uint32_t>(CHRBranchBias.scale(1000))); | |||
1873 | Weights.push_back(static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000))); | |||
1874 | MDBuilder MDB(F.getContext()); | |||
1875 | MergedBR->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights)); | |||
1876 | 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) | |||
1877 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "CHR branch bias " << Weights [0] << ":" << Weights[1] << "\n"; } } while (false); | |||
1878 | } | |||
1879 | ||||
1880 | // A helper for fixupBranchesAndSelects. Add to the combined branch condition | |||
1881 | // and constant-fold a branch in the hot path. | |||
1882 | void CHR::fixupBranch(Region *R, CHRScope *Scope, | |||
1883 | IRBuilder<> &IRB, | |||
1884 | Value *&MergedCondition, | |||
1885 | BranchProbability &CHRBranchBias) { | |||
1886 | bool IsTrueBiased = Scope->TrueBiasedRegions.count(R); | |||
1887 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1888, __PRETTY_FUNCTION__)) | |||
1888 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1888, __PRETTY_FUNCTION__)); | |||
1889 | auto *BI = cast<BranchInst>(R->getEntry()->getTerminator()); | |||
1890 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1891, __PRETTY_FUNCTION__)) | |||
1891 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1891, __PRETTY_FUNCTION__)); | |||
1892 | BranchProbability Bias = BranchBiasMap[R]; | |||
1893 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1893, __PRETTY_FUNCTION__)); | |||
1894 | // Take the min. | |||
1895 | if (CHRBranchBias > Bias) | |||
1896 | CHRBranchBias = Bias; | |||
1897 | BasicBlock *IfThen = BI->getSuccessor(1); | |||
1898 | BasicBlock *IfElse = BI->getSuccessor(0); | |||
1899 | BasicBlock *RegionExitBlock = R->getExit(); | |||
1900 | assert(RegionExitBlock && "Null ExitBlock")((RegionExitBlock && "Null ExitBlock") ? static_cast< void> (0) : __assert_fail ("RegionExitBlock && \"Null ExitBlock\"" , "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1900, __PRETTY_FUNCTION__)); | |||
1901 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1902, __PRETTY_FUNCTION__)) | |||
1902 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1902, __PRETTY_FUNCTION__)); | |||
1903 | if (IfThen == RegionExitBlock) { | |||
1904 | // Swap them so that IfThen means going into it and IfElse means skipping | |||
1905 | // it. | |||
1906 | std::swap(IfThen, IfElse); | |||
1907 | } | |||
1908 | CHR_DEBUG(dbgs() << "IfThen " << IfThen->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "IfThen " << IfThen->getName () << " IfElse " << IfElse->getName() << "\n"; } } while (false) | |||
1909 | << " IfElse " << IfElse->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "IfThen " << IfThen->getName () << " IfElse " << IfElse->getName() << "\n"; } } while (false); | |||
1910 | Value *Cond = BI->getCondition(); | |||
1911 | BasicBlock *HotTarget = IsTrueBiased ? IfThen : IfElse; | |||
1912 | bool ConditionTrue = HotTarget == BI->getSuccessor(0); | |||
1913 | addToMergedCondition(ConditionTrue, Cond, BI, Scope, IRB, | |||
1914 | MergedCondition); | |||
1915 | // Constant-fold the branch at ClonedEntryBlock. | |||
1916 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1917, __PRETTY_FUNCTION__)) | |||
1917 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1917, __PRETTY_FUNCTION__)); | |||
1918 | Value *NewCondition = ConditionTrue ? | |||
1919 | ConstantInt::getTrue(F.getContext()) : | |||
1920 | ConstantInt::getFalse(F.getContext()); | |||
1921 | BI->setCondition(NewCondition); | |||
1922 | } | |||
1923 | ||||
1924 | // A helper for fixupBranchesAndSelects. Add to the combined branch condition | |||
1925 | // and constant-fold a select in the hot path. | |||
1926 | void CHR::fixupSelect(SelectInst *SI, CHRScope *Scope, | |||
1927 | IRBuilder<> &IRB, | |||
1928 | Value *&MergedCondition, | |||
1929 | BranchProbability &CHRBranchBias) { | |||
1930 | bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI); | |||
1931 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1932, __PRETTY_FUNCTION__)) | |||
1932 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1932, __PRETTY_FUNCTION__)); | |||
1933 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1934, __PRETTY_FUNCTION__)) | |||
1934 | "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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1934, __PRETTY_FUNCTION__)); | |||
1935 | BranchProbability Bias = SelectBiasMap[SI]; | |||
1936 | 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-10~svn374877/lib/Transforms/Instrumentation/ControlHeightReduction.cpp" , 1936, __PRETTY_FUNCTION__)); | |||
1937 | // Take the min. | |||
1938 | if (CHRBranchBias > Bias) | |||
1939 | CHRBranchBias = Bias; | |||
1940 | Value *Cond = SI->getCondition(); | |||
1941 | addToMergedCondition(IsTrueBiased, Cond, SI, Scope, IRB, | |||
1942 | MergedCondition); | |||
1943 | Value *NewCondition = IsTrueBiased ? | |||
1944 | ConstantInt::getTrue(F.getContext()) : | |||
1945 | ConstantInt::getFalse(F.getContext()); | |||
1946 | SI->setCondition(NewCondition); | |||
1947 | } | |||
1948 | ||||
1949 | // A helper for fixupBranch/fixupSelect. Add a branch condition to the merged | |||
1950 | // condition. | |||
1951 | void CHR::addToMergedCondition(bool IsTrueBiased, Value *Cond, | |||
1952 | Instruction *BranchOrSelect, | |||
1953 | CHRScope *Scope, | |||
1954 | IRBuilder<> &IRB, | |||
1955 | Value *&MergedCondition) { | |||
1956 | if (IsTrueBiased) { | |||
1957 | MergedCondition = IRB.CreateAnd(MergedCondition, Cond); | |||
1958 | } else { | |||
1959 | // If Cond is an icmp and all users of V except for BranchOrSelect is a | |||
1960 | // branch, negate the icmp predicate and swap the branch targets and avoid | |||
1961 | // inserting an Xor to negate Cond. | |||
1962 | bool Done = false; | |||
1963 | if (auto *ICmp = dyn_cast<ICmpInst>(Cond)) | |||
1964 | if (negateICmpIfUsedByBranchOrSelectOnly(ICmp, BranchOrSelect, Scope)) { | |||
1965 | MergedCondition = IRB.CreateAnd(MergedCondition, Cond); | |||
1966 | Done = true; | |||
1967 | } | |||
1968 | if (!Done) { | |||
1969 | Value *Negate = IRB.CreateXor( | |||
1970 | ConstantInt::getTrue(F.getContext()), Cond); | |||
1971 | MergedCondition = IRB.CreateAnd(MergedCondition, Negate); | |||
1972 | } | |||
1973 | } | |||
1974 | } | |||
1975 | ||||
1976 | void CHR::transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes) { | |||
1977 | unsigned I = 0; | |||
1978 | DenseSet<PHINode *> TrivialPHIs; | |||
1979 | for (CHRScope *Scope : CHRScopes) { | |||
1980 | transformScopes(Scope, TrivialPHIs); | |||
1981 | 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) | |||
1982 | 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) | |||
1983 | 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) | |||
1984 | 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); | |||
1985 | (void)I; | |||
1986 | } | |||
1987 | } | |||
1988 | ||||
1989 | static void LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) | |||
1990 | dumpScopes(SmallVectorImpl<CHRScope *> &Scopes, const char *Label) { | |||
1991 | dbgs() << Label << " " << Scopes.size() << "\n"; | |||
1992 | for (CHRScope *Scope : Scopes) { | |||
1993 | dbgs() << *Scope << "\n"; | |||
1994 | } | |||
1995 | } | |||
1996 | ||||
1997 | bool CHR::run() { | |||
1998 | if (!shouldApply(F, PSI)) | |||
1999 | return false; | |||
2000 | ||||
2001 | CHR_DEBUG(dumpIR(F, "before", nullptr))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dumpIR(F, "before", nullptr); } } while (false); | |||
2002 | ||||
2003 | bool Changed = false; | |||
2004 | { | |||
2005 | CHR_DEBUG
("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs()); } } while (false) | |||
2006 | dbgs() << "RegionInfo:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs()); } } while (false) | |||
2007 | RI.print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs()); } } while (false); | |||
2008 | ||||
2009 | // Recursively traverse the region tree and find regions that have biased | |||
2010 | // branches and/or selects and create scopes. | |||
2011 | SmallVector<CHRScope *, 8> AllScopes; | |||
2012 | findScopes(AllScopes); | |||
2013 | CHR_DEBUG(dumpScopes(AllScopes, "All scopes"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dumpScopes(AllScopes, "All scopes"); } } while (false ); | |||
2014 | ||||
2015 | // Split the scopes if 1) the conditiona values of the biased | |||
2016 | // branches/selects of the inner/lower scope can't be hoisted up to the | |||
2017 | // outermost/uppermost scope entry, or 2) the condition values of the biased | |||
2018 | // branches/selects in a scope (including subscopes) don't share at least | |||
2019 | // one common value. | |||
2020 | SmallVector<CHRScope *, 8> SplitScopes; | |||
2021 | splitScopes(AllScopes, SplitScopes); | |||
2022 | CHR_DEBUG(dumpScopes(SplitScopes, "Split scopes"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dumpScopes(SplitScopes, "Split scopes"); } } while (false); | |||
2023 | ||||
2024 | // After splitting, set the biased regions and selects of a scope (a tree | |||
2025 | // root) that include those of the subscopes. | |||
2026 | classifyBiasedScopes(SplitScopes); | |||
2027 | 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); | |||
2028 | ||||
2029 | // Filter out the scopes that has only one biased region or select (CHR | |||
2030 | // isn't useful in such a case). | |||
2031 | SmallVector<CHRScope *, 8> FilteredScopes; | |||
2032 | filterScopes(SplitScopes, FilteredScopes); | |||
2033 | CHR_DEBUG(dumpScopes(FilteredScopes, "Filtered scopes"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dumpScopes(FilteredScopes, "Filtered scopes"); } } while (false); | |||
2034 | ||||
2035 | // Set the regions to be CHR'ed and their hoist stops for each scope. | |||
2036 | SmallVector<CHRScope *, 8> SetScopes; | |||
2037 | setCHRRegions(FilteredScopes, SetScopes); | |||
2038 | CHR_DEBUG(dumpScopes(SetScopes, "Set CHR regions"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dumpScopes(SetScopes, "Set CHR regions"); } } while (false); | |||
2039 | ||||
2040 | // Sort CHRScopes by the depth so that outer CHRScopes comes before inner | |||
2041 | // ones. We need to apply CHR from outer to inner so that we apply CHR only | |||
2042 | // to the hot path, rather than both hot and cold paths. | |||
2043 | SmallVector<CHRScope *, 8> SortedScopes; | |||
2044 | sortScopes(SetScopes, SortedScopes); | |||
2045 | CHR_DEBUG(dumpScopes(SortedScopes, "Sorted scopes"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dumpScopes(SortedScopes, "Sorted scopes"); } } while (false); | |||
2046 | ||||
2047 | CHR_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs()); } } while (false) | |||
2048 | dbgs() << "RegionInfo:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs()); } } while (false) | |||
2049 | RI.print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dbgs() << "RegionInfo:\n"; RI.print(dbgs()); } } while (false); | |||
2050 | ||||
2051 | // Apply the CHR transformation. | |||
2052 | if (!SortedScopes.empty()) { | |||
2053 | transformScopes(SortedScopes); | |||
2054 | Changed = true; | |||
2055 | } | |||
2056 | } | |||
2057 | ||||
2058 | if (Changed) { | |||
2059 | CHR_DEBUG(dumpIR(F, "after", &Stats))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("chr")) { dumpIR(F, "after", &Stats); } } while (false); | |||
2060 | ORE.emit([&]() { | |||
2061 | return OptimizationRemark(DEBUG_TYPE"chr", "Stats", &F) | |||
2062 | << ore::NV("Function", &F) << " " | |||
2063 | << "Reduced the number of branches in hot paths by " | |||
2064 | << ore::NV("NumBranchesDelta", Stats.NumBranchesDelta) | |||
2065 | << " (static) and " | |||
2066 | << ore::NV("WeightedNumBranchesDelta", Stats.WeightedNumBranchesDelta) | |||
2067 | << " (weighted by PGO count)"; | |||
2068 | }); | |||
2069 | } | |||
2070 | ||||
2071 | return Changed; | |||
2072 | } | |||
2073 | ||||
2074 | bool ControlHeightReductionLegacyPass::runOnFunction(Function &F) { | |||
2075 | BlockFrequencyInfo &BFI = | |||
2076 | getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(); | |||
2077 | DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
2078 | ProfileSummaryInfo &PSI = | |||
2079 | getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); | |||
2080 | RegionInfo &RI = getAnalysis<RegionInfoPass>().getRegionInfo(); | |||
2081 | std::unique_ptr<OptimizationRemarkEmitter> OwnedORE = | |||
2082 | std::make_unique<OptimizationRemarkEmitter>(&F); | |||
2083 | return CHR(F, BFI, DT, PSI, RI, *OwnedORE.get()).run(); | |||
2084 | } | |||
2085 | ||||
2086 | namespace llvm { | |||
2087 | ||||
2088 | ControlHeightReductionPass::ControlHeightReductionPass() { | |||
2089 | parseCHRFilterFiles(); | |||
2090 | } | |||
2091 | ||||
2092 | PreservedAnalyses ControlHeightReductionPass::run( | |||
2093 | Function &F, | |||
2094 | FunctionAnalysisManager &FAM) { | |||
2095 | auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F); | |||
2096 | auto &DT = FAM.getResult<DominatorTreeAnalysis>(F); | |||
2097 | auto &MAMProxy = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(F); | |||
2098 | auto &MAM = MAMProxy.getManager(); | |||
2099 | auto &PSI = *MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent()); | |||
2100 | auto &RI = FAM.getResult<RegionInfoAnalysis>(F); | |||
2101 | auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F); | |||
2102 | bool Changed = CHR(F, BFI, DT, PSI, RI, ORE).run(); | |||
| ||||
2103 | if (!Changed) | |||
2104 | return PreservedAnalyses::all(); | |||
2105 | auto PA = PreservedAnalyses(); | |||
2106 | PA.preserve<GlobalsAA>(); | |||
2107 | return PA; | |||
2108 | } | |||
2109 | ||||
2110 | } // namespace llvm |