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