LLVM  16.0.0git
TLSVariableHoist.cpp
Go to the documentation of this file.
1 //===- TLSVariableHoist.cpp -------- Remove Redundant TLS Loads ---------===//
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 identifies/eliminate Redundant TLS Loads if related option is set.
10 // The example: Please refer to the comment at the head of TLSVariableHoist.h.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/IR/BasicBlock.h"
16 #include "llvm/IR/Dominators.h"
17 #include "llvm/IR/Function.h"
18 #include "llvm/IR/InstrTypes.h"
19 #include "llvm/IR/Instruction.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/IntrinsicInst.h"
22 #include "llvm/IR/Module.h"
23 #include "llvm/IR/Value.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Support/Casting.h"
27 #include "llvm/Support/Debug.h"
29 #include "llvm/Transforms/Scalar.h"
31 #include <algorithm>
32 #include <cassert>
33 #include <cstdint>
34 #include <iterator>
35 #include <tuple>
36 #include <utility>
37 
38 using namespace llvm;
39 using namespace tlshoist;
40 
41 #define DEBUG_TYPE "tlshoist"
42 
44  "tls-load-hoist", cl::init(false), cl::Hidden,
45  cl::desc("hoist the TLS loads in PIC model to eliminate redundant "
46  "TLS address calculation."));
47 
48 namespace {
49 
50 /// The TLS Variable hoist pass.
51 class TLSVariableHoistLegacyPass : public FunctionPass {
52 public:
53  static char ID; // Pass identification, replacement for typeid
54 
55  TLSVariableHoistLegacyPass() : FunctionPass(ID) {
57  }
58 
59  bool runOnFunction(Function &Fn) override;
60 
61  StringRef getPassName() const override { return "TLS Variable Hoist"; }
62 
63  void getAnalysisUsage(AnalysisUsage &AU) const override {
64  AU.setPreservesCFG();
67  }
68 
69 private:
71 };
72 
73 } // end anonymous namespace
74 
76 
77 INITIALIZE_PASS_BEGIN(TLSVariableHoistLegacyPass, "tlshoist",
78  "TLS Variable Hoist", false, false)
81 INITIALIZE_PASS_END(TLSVariableHoistLegacyPass, "tlshoist",
82  "TLS Variable Hoist", false, false)
83 
85  return new TLSVariableHoistLegacyPass();
86 }
87 
88 /// Perform the TLS Variable Hoist optimization for the given function.
90  if (skipFunction(Fn))
91  return false;
92 
93  LLVM_DEBUG(dbgs() << "********** Begin TLS Variable Hoist **********\n");
94  LLVM_DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
95 
96  bool MadeChange =
97  Impl.runImpl(Fn, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
98  getAnalysis<LoopInfoWrapperPass>().getLoopInfo());
99 
100  if (MadeChange) {
101  LLVM_DEBUG(dbgs() << "********** Function after TLS Variable Hoist: "
102  << Fn.getName() << '\n');
103  LLVM_DEBUG(dbgs() << Fn);
104  }
105  LLVM_DEBUG(dbgs() << "********** End TLS Variable Hoist **********\n");
106 
107  return MadeChange;
108 }
109 
110 void TLSVariableHoistPass::collectTLSCandidate(Instruction *Inst) {
111  // Skip all cast instructions. They are visited indirectly later on.
112  if (Inst->isCast())
113  return;
114 
115  // Scan all operands.
116  for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
117  auto *GV = dyn_cast<GlobalVariable>(Inst->getOperand(Idx));
118  if (!GV || !GV->isThreadLocal())
119  continue;
120 
121  // Add Candidate to TLSCandMap (GV --> Candidate).
122  TLSCandMap[GV].addUser(Inst, Idx);
123  }
124 }
125 
126 void TLSVariableHoistPass::collectTLSCandidates(Function &Fn) {
127  // First, quickly check if there is TLS Variable.
128  Module *M = Fn.getParent();
129 
130  bool HasTLS = llvm::any_of(
131  M->globals(), [](GlobalVariable &GV) { return GV.isThreadLocal(); });
132 
133  // If non, directly return.
134  if (!HasTLS)
135  return;
136 
137  TLSCandMap.clear();
138 
139  // Then, collect TLS Variable info.
140  for (BasicBlock &BB : Fn) {
141  // Ignore unreachable basic blocks.
142  if (!DT->isReachableFromEntry(&BB))
143  continue;
144 
145  for (Instruction &Inst : BB)
146  collectTLSCandidate(&Inst);
147  }
148 }
149 
151  if (Cand.Users.size() != 1)
152  return false;
153 
154  BasicBlock *BB = Cand.Users[0].Inst->getParent();
155  if (LI->getLoopFor(BB))
156  return false;
157 
158  return true;
159 }
160 
161 Instruction *TLSVariableHoistPass::getNearestLoopDomInst(BasicBlock *BB,
162  Loop *L) {
163  assert(L && "Unexcepted Loop status!");
164 
165  // Get the outermost loop.
166  while (Loop *Parent = L->getParentLoop())
167  L = Parent;
168 
169  BasicBlock *PreHeader = L->getLoopPreheader();
170 
171  // There is unique predecessor outside the loop.
172  if (PreHeader)
173  return PreHeader->getTerminator();
174 
175  BasicBlock *Header = L->getHeader();
176  BasicBlock *Dom = Header;
177  for (BasicBlock *PredBB : predecessors(Header))
178  Dom = DT->findNearestCommonDominator(Dom, PredBB);
179 
180  assert(Dom && "Not find dominator BB!");
181  Instruction *Term = Dom->getTerminator();
182 
183  return Term;
184 }
185 
186 Instruction *TLSVariableHoistPass::getDomInst(Instruction *I1,
187  Instruction *I2) {
188  if (!I1)
189  return I2;
190  if (DT->dominates(I1, I2))
191  return I1;
192  if (DT->dominates(I2, I1))
193  return I2;
194 
195  // If there is no dominance relation, use common dominator.
196  BasicBlock *DomBB =
197  DT->findNearestCommonDominator(I1->getParent(), I2->getParent());
198 
199  Instruction *Dom = DomBB->getTerminator();
200  assert(Dom && "Common dominator not found!");
201 
202  return Dom;
203 }
204 
205 BasicBlock::iterator TLSVariableHoistPass::findInsertPos(Function &Fn,
206  GlobalVariable *GV,
207  BasicBlock *&PosBB) {
208  tlshoist::TLSCandidate &Cand = TLSCandMap[GV];
209 
210  // We should hoist the TLS use out of loop, so choose its nearest instruction
211  // which dominate the loop and the outside loops (if exist).
212  Instruction *LastPos = nullptr;
213  for (auto &User : Cand.Users) {
214  BasicBlock *BB = User.Inst->getParent();
215  Instruction *Pos = User.Inst;
216  if (Loop *L = LI->getLoopFor(BB)) {
217  Pos = getNearestLoopDomInst(BB, L);
218  assert(Pos && "Not find insert position out of loop!");
219  }
220  Pos = getDomInst(LastPos, Pos);
221  LastPos = Pos;
222  }
223 
224  assert(LastPos && "Unexpected insert position!");
225  BasicBlock *Parent = LastPos->getParent();
226  PosBB = Parent;
227  return LastPos->getIterator();
228 }
229 
230 // Generate a bitcast (no type change) to replace the uses of TLS Candidate.
231 Instruction *TLSVariableHoistPass::genBitCastInst(Function &Fn,
232  GlobalVariable *GV) {
233  BasicBlock *PosBB = &Fn.getEntryBlock();
234  BasicBlock::iterator Iter = findInsertPos(Fn, GV, PosBB);
235  Type *Ty = GV->getType();
236  auto *CastInst = new BitCastInst(GV, Ty, "tls_bitcast");
237  PosBB->getInstList().insert(Iter, CastInst);
238  return CastInst;
239 }
240 
241 bool TLSVariableHoistPass::tryReplaceTLSCandidate(Function &Fn,
242  GlobalVariable *GV) {
243 
244  tlshoist::TLSCandidate &Cand = TLSCandMap[GV];
245 
246  // If only used 1 time and not in loops, we no need to replace it.
247  if (oneUseOutsideLoop(Cand, LI))
248  return false;
249 
250  // Generate a bitcast (no type change)
251  auto *CastInst = genBitCastInst(Fn, GV);
252 
253  // to replace the uses of TLS Candidate
254  for (auto &User : Cand.Users)
255  User.Inst->setOperand(User.OpndIdx, CastInst);
256 
257  return true;
258 }
259 
260 bool TLSVariableHoistPass::tryReplaceTLSCandidates(Function &Fn) {
261  if (TLSCandMap.empty())
262  return false;
263 
264  bool Replaced = false;
265  for (auto &GV2Cand : TLSCandMap) {
266  GlobalVariable *GV = GV2Cand.first;
267  Replaced |= tryReplaceTLSCandidate(Fn, GV);
268  }
269 
270  return Replaced;
271 }
272 
273 /// Optimize expensive TLS variables in the given function.
275  LoopInfo &LI) {
276  if (Fn.hasOptNone())
277  return false;
278 
279  if (!TLSLoadHoist && !Fn.getAttributes().hasFnAttr("tls-load-hoist"))
280  return false;
281 
282  this->LI = &LI;
283  this->DT = &DT;
284  assert(this->LI && this->DT && "Unexcepted requirement!");
285 
286  // Collect all TLS variable candidates.
287  collectTLSCandidates(Fn);
288 
289  bool MadeChange = tryReplaceTLSCandidates(Fn);
290 
291  return MadeChange;
292 }
293 
296 
297  auto &LI = AM.getResult<LoopAnalysis>(F);
298  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
299 
300  if (!runImpl(F, DT, LI))
301  return PreservedAnalyses::all();
302 
304  PA.preserveSet<CFGAnalyses>();
305  return PA;
306 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::dxil::ParameterKind::I1
@ I1
llvm::tlshoist::TLSCandidate::Users
SmallVector< TLSUser, 8 > Users
Definition: TLSVariableHoist.h:93
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
llvm::Function::hasOptNone
bool hasOptNone() const
Do not optimize this function (-O0).
Definition: Function.h:639
TLSLoadHoist
static cl::opt< bool > TLSLoadHoist("tls-load-hoist", cl::init(false), cl::Hidden, cl::desc("hoist the TLS loads in PIC model to eliminate redundant " "TLS address calculation."))
Scalar.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::Instruction::isCast
bool isCast() const
Definition: Instruction.h:177
Pass.h
oneUseOutsideLoop
static bool oneUseOutsideLoop(tlshoist::TLSCandidate &Cand, LoopInfo *LI)
Definition: TLSVariableHoist.cpp:150
Hoist
TLS Variable Hoist
When an instruction is found to use only loop invariant operands that are safe to hoist,...
Definition: TLSVariableHoist.cpp:82
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5253
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:691
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
tlshoist
tlshoist
Definition: TLSVariableHoist.cpp:81
llvm::initializeTLSVariableHoistLegacyPassPass
void initializeTLSVariableHoistLegacyPassPass(PassRegistry &)
llvm::TLSVariableHoistPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: TLSVariableHoist.cpp:294
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
InstrTypes.h
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
llvm::Instruction
Definition: Instruction.h:42
llvm::AttributeList::hasFnAttr
bool hasFnAttr(Attribute::AttrKind Kind) const
Return true if the attribute exists for the function.
Definition: Attributes.cpp:1486
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:306
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
TLSVariableHoist.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::Function::getAttributes
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:314
BasicBlock.h
llvm::cl::opt< bool >
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:652
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:66
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1741
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::tlshoist::TLSCandidate
Keeps track of a TLS variable candidate and its users.
Definition: TLSVariableHoist.h:92
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::createTLSVariableHoistPass
FunctionPass * createTLSVariableHoistPass()
Definition: TLSVariableHoist.cpp:84
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(TLSVariableHoistLegacyPass, "tlshoist", "TLS Variable Hoist", false, false) INITIALIZE_PASS_END(TLSVariableHoistLegacyPass
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Casting.h
llvm::TLSVariableHoistPass
Definition: TLSVariableHoist.h:103
Function.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
runImpl
static bool runImpl(Function &F, const TargetLowering &TLI)
Definition: ExpandLargeDivRem.cpp:56
llvm::TLSVariableHoistPass::runImpl
bool runImpl(Function &F, DominatorTree &DT, LoopInfo &LI)
Optimize expensive TLS variables in the given function.
Definition: TLSVariableHoist.cpp:274
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:271
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:373
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
SmallVector.h
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
llvm::GlobalValue::getType
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:290
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:413
raw_ostream.h
Value.h
InitializePasses.h
Debug.h
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268